数据结构课程设计题目
地图着色
马踏棋盘
栈的实现
八皇后算法
车厢调度
公园导游图
通讯录实现
同学录实现
导游系统实现
最小生成树实现
统计成绩系统
利用学到的编程知识和编程技巧，通过布置具有一定难度的程序设计题目，让学生自己到图书馆查阅资料或网上咨询独立完成程序的编写，并能运用学过的技巧独立上机调试完成。
系统类题目：
题目１：学生信息管理系统设计
试设计一学生信息管理系统，使之能提供以下功能：
系统以菜单方式工作
学生信息包括：学号，姓名，年龄，别，出生年月，地址，电话，E-mail 等。
3http://www.huoluoyou.net、学生信息录入功能（学生信息用文件保存）---输入
4、学生信息浏览功能---输出
5、查询、排序功能---算法
6、学生信息的删除与修改（可选项）
题目２ ：职工信息管理系统设计
试设计一职工信息管理系统，使之能提供以下功能：
1、系统以菜单方式工作。
2、职工信息包括职工号、姓名、别、年龄、学历、工资、住址、电话等（职工号不重复）。
3、职工信息录入功能(职工信息用文件保存) －－输入。
4、职工信息浏览功能 －－输出。
5、查询和排序功能：(至少一种查询方式) －－算法。
6、职工信息删除、修改功能(任选项) 。
题目３： 一堆猴子都有编号，编号是1，2，3 ...m , 这群猴子（m 个）按照1到m 的顺序围坐一圈，从第1开始数，每数到第n 个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
要求：输入数据输入m 、,n 其中m 、,n 为整数，n 输出形式提示按照m 个猴子，数n 个数的方法，输出为大王的猴子是几号。
难度1：编程先由计算机‚想‛一个1到100之间的数请人猜，如果人猜对了，则计算机给出提示：‚Right! ‛， 否则提示：‚Wrong! ‛，并告诉人所猜的数是大(Too high)还是小(Too low)，然后结束游戏。要求每次运行程序时机器所‚想‛的数不能都是一样的。
难度2：编程先由计算机‚想‛一个1到100之间的数请人猜，如果人猜对了，则结束游戏，并在屏幕上输出人猜了多少次才猜对此数，以此来反映猜数者‚猜‛的水平，否则计算机给出提示，告诉人所猜的数是太大还是太小，直到人猜对为止。
难度3：编程先由计算机‚想‛一个1到100之间的数请人猜，如果人猜对了，则结束游戏，并在屏幕上输出人猜了多少次才猜对此数，以此来反映猜数者‚猜‛的水平，否则计算机给出提示，告诉人所猜的数是太大还是太小，最多可以猜10次，如果猜了10次仍未猜中的话，则结束游戏。
难度4：编程先由计算机‚想‛一个1到100之间的数请人猜，如果人猜对
了，并在屏幕上输出人猜了多少次才猜对此数，以此来反映猜数者‚猜‛的水平，则结束游戏，否则计算机给出提示，告诉人所猜的数是太大还是太小，最多可以猜10次，如果猜了10次仍未猜中的话，则停止本次猜数，然后继续猜下一个数。每次运行程序可以反复猜多个数，直到操作者想停止时才结束。
题目４．停车场管理
问题描述：
设停车场是一个可停放n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在停车场的最北端）, 若停车场内已停满n 辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。
基本要求
以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车‚到达‛或‚离去‛信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。
测试数据
设n=2，输入数据为：（‘A ’,1,5）, （‘A ’,2,10）, （‘D ’,1,15）, （‘A ’,3,20）, （‘A ’,4,25）, （‘A ’5,30）, （‘D ’,2,35）, （‘D ’,4,40）, （‘E ’,0,0）。其中：‘A ’表示到达（arrival ）；‘D ’表示离去（departure ）；‘E ’表示输出结束（end ）。
实现提示
需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。
选作内容
（1）两个栈共享空间，思考应开辟数组的空间是多少？
（2）汽车可有不同种类，则他们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。
（3）汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。
题目５．魔王语言解释
问题描述
有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没有人能听懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：
（1）α->β1β2……βm
（2）（θδ1δ2……δn ）—>θδn θδn-1……θδ1θ
在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话；
基本要求
用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。
（1）B->tAdA
（2）A->sae
测试数据
B （ehnxgz ）B 解释成tsaedsaeezegexenehetsaedsae
若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：‚天上一
将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈，将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者思考应如何处理。应首先实现栈和队列的基本操作。 选作内容
（1）由于问题的特殊性，可以实现栈和队列的顺序存储空间共享。
（2）代换变量的数目不限，则在程序开始运行时首先读入一组第一种形式的规则，而不是把规则固定在程序中（第二种形式的规则只能固定在程序中）。
题目６．校园导游咨询
问题描述
设计一个校园导游程序，为来访的客人提供各种信息查询服务。
基本要求
（1）设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息：以边表示路径，存放路径长度等相关信息。
（2）为来访客人提供图中任意景点相关信息的查询。
（3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
测试数据
由读者根据实际情况指定。
实现提示
一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。
选作内容
（1）提供图中任意景点问路查询，即求任意两个景点之间的所有路径。
（2）扩充道路信息，如道路类别（车道、人行道等）、沿途景色等级，以至可按客人所需分别查询人行路径或车行路径或观景路径等。
（3）实现校园导游图的仿真界面
题目７迷宫问题
问题描述
以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
基本要求
首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d ）的形式输出，其中：（i,j ）指示迷宫中的一个坐标,d 表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：
（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2）……
题目８ 成绩管理
问题描述：给出n 个学生的考试成绩表，成绩表包括学生的学号、姓名、考试成绩（高等数
学、英语、物理），设计一个简单的成绩管理程序。
基本要求：
（1）建立成绩表，能够插入、删除、修改学生的成绩记录；
（2）按任一单科成绩排序；
(3) 计算每名学生的平均成绩；
(4) 统计任一单科成绩不及格的学生人数, 输出不及格人数及不及格的学生名单
(5) 根据平均成绩将成绩表按由高到低的次序排列，统计每名学生在考试中获得的名次，分数相同的为同一名次，按名次输出成绩表。
(6) 成绩表保存在文件中, 可以从文件读取数据。
测试数据：学生可以根据自己班级的考试成绩单，任意截取一部分做为测试数据 提高要求：成绩表用链式结构表示，实现上述全部要求。
题目９：一元多项式简单计算
问题描述：设计一个简单一元多项式计算器。
基本要求：(1)输入并建立多项式；
(2)输出多项式；
(3)两个多项式相加，输出结果多项式；
(4)两个多项式相减，输出结果多项式。
测试数据：可任意选取两个一元多项式，可以是一般的多项式，也可以是稀疏多项式。 提高要求：可以根据输入变量的值，计算出多项式的结果，且算法的效率高。
题目10：舞伴问题
问题描述：一班有m 个女生、n 个男生(m不等于n), 举办一场舞会. 男女生分别编号坐在舞池两边的椅子上，每曲开始时, 依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴，设计一个程序模拟舞伴配对过程。
基本要求：输入男、女学生的姓名、性别，由程序自动为男女生编号，可以顺序编号，也可以随机编号，输出每曲配对情况（包括男、女生的姓名、性别和编号）。原始数据和结果数据要保存到文件中。
测试数据：分别选择男生多于女生、女生多于男生、男女生相等的三组测试数据
提高要求：计算出任意一位男生(编号为X) 和任意一位女生(编号为Y), 在第K 曲配对跳舞的情况。
题目１１：文学研究助手（*）
问题描述：文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。
基本要求：英文小说存于一个文本文件中，待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计, 结果保存到文件中。
测试数据：以你的C/C++/JAVA源程序模拟英文小说，相应语言的保留字集作为待统计的词汇集。
题目１２：哈希表的设计与实现（*）
问题描述：针对某个单位电话号码簿，设计一个哈希表，并完成相应的建表和查表程序。 基本要求：设每个记录有下列数据项：电话号码、用户名、住址。从键盘输入各记录，以用户名为关键字建立哈希表，哈希函数用除留取余数法构造，采用线性探测法解决冲突。可以插入、查找、删除并显示给定用户名的记录，并计算查找长度, 哈希表保存到文件中，并能从文件中读取数据。
测试数据：取某个单位电话号码簿中的30个记录。
提高要求：将电话号码薄以文件形式保存到盘上，能够按用户名和电话号码两种形式建立哈希表并实现插入、查找、删除表中元素的功能。
注意事项：不能用类库中的类完成题目
题目１３：管道铺设施工的最佳方案（*）
问题描述:需要在某个城市的n 个小区铺设管道，则在这n 个小区之间铺设n-1条管道即可，假设任意两个居民区之间都可以架设管道，但由于地理环境的不同，所需经费不同，选择最优的施工方案使总投资尽可能的少。
基本要求：输入表示小区间关系的图及每条管道的权值，选择出n-1条管道, 使总投资最小。图的信息输入一次后, 保存到文件中, 选择的n-1条管道输出到显示器的同时, 也保存于文件中。
测试用例：任意选择一个图，模拟小区间可能铺设的管道及费用。
提高要求：显示原始图及选择n-1条管道后的图。
题目１４：安排教学计划（**）
问题描述：大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两个学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排上必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课程恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。
基本要求：输入参数包括学期总数，一学期的学分上限，每门课程的课程号、学分和直接先修课的课程号；允许两种策略，一是使学生在各学期的学习负担尽量均匀，二是使课程尽量集中在前几个学期；若根据给定的条件问题无解，则报告适当的信息，否则将教学计划输出到用户指定的文件中。教学计划的表格格式自行设定, 可以从键盘读取数据也可以从文件读取数据, 结果保存到文件中。
测试数据：学期总数为6，学分上限为10，该专业共开设12门。以08级某专业必修课与选修课为例，选择12门课程及相应学分，制定一个表明各门课程先后约束关系的有向图。
提高要求：产生多种不同的方案，并使方案之间的差异尽可能地大。
题目１５：计算表达式的值(**)
问题描述：对于给定的一个表达式，表达式中可以包括常数、算术运行符（“+”、“-”、“*”、“/”）和括号，编写程序计算表达式的值。
基本要求：从键盘输入一个正确的中缀表达式，将中缀表达式转换为对应的后缀表达式，计算后缀表达式的值。
测试数据：任意选取一个符合题目要求的表达式。
提高要求：（1）对于表达式中的简单错误，能够给出提示；
（2）不仅提示错误，也能给出错误信息
（3）表达式中可以包括单个字母表示的变量
（4）能够处理多种操作符
（5）实现包含简单运算的计算器
（6）实现一个包含简单运算和函数运算的计算器
题目１５：设计Huffman 编码器与解码器（**）
问题描述：利用哈夫曼编码进行信息通讯可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码；在接受端将传来的数据进行译码。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个哈夫曼码的编/译码系统。
基本要求：根据某字符文件统计字符出现频度，构造Huffman 树，编制Huffman 编码，并将给定字符文件编码，生成编码文件；再将给定编码文件解码，生成字符文件。（要求按二进制位表示编码）
测试数据：英文文件。
题目１６：银行业务模拟（**）
问题描述：设银行有四个服务窗口，一个等待队列, 每个窗口均可以办理存款、取款、挂失、还贷业务，每种业务所需的服务时间不同，客户到达银行后，先到打号机上打号，号票上包括到达时间、编号和需要办理的业务，然后在银行内等候, 当任一服务窗口空闲时, 处理等候客户中排在最前面的客户的业务。写一个上述银行业务的模拟系统, 通过模拟方法求出客户在银行内逗留的平均时间和每个窗口办理的客户数及办理的每种业务数。
基本要求：每个客户到达银行的时间和需要办理的业务随机产生，输出一天客户在银行的平均逗留时间和每个窗口每天办理的客户数和每种业务数。
测试数据：营业时间为8小时，其他模拟量自行设定。
题目１７：真值表的设计与实现（**）
问题描述：对给出的任意一个合式公式（不超过四个命题变元），用C 语言的程序编程表示出来，并且能够计算它在各组真值指派下所应有的真值，画出其真值表。
基本要求：
（1）已知命题p 和q 的真值，求出它们的合取、析取、蕴涵和等价的真值；
（2）表示出合式公式；
（3）给出任意一个合式公式（不超过四个命题变元），设计程序把它表示出来，并且能够计算它在各组真值指派下所应有的真值（或是逻辑运算的结果）。
提高要求：构造任意合式公式的真值表
题目１８：程序源代码的相似性（***）
问题描述：对于两个C++语言的源程序代码，用哈希表的方法分别统计两个程序中使用C++语言关键字的情况，并最终按定量的计算结果，得出两份程序的相似性。
基本要求：建立C++语言关键字的哈希表，统计在每个源程序中C++关键字出现的频度, 得到两个向量X1和X2，通过计算向量X1和X2的相对距离来判断两个源程序的相似性。
例如:
关键字 Void Int For Char if else while do break class 程序1关键字频度 4 3 0 4 3 0 7 0 0 2 程序2关键字频度 4 2 0 5 4 0 5 2 0 1 X1=[4,3,0,4,3,0,7,0,0,2]
X2=[4,2,0,5,4,0,5,2,0,1]
设s 是向量X1和X2的相对距离，s =sqrt( ∑(xi1-x i2) 2 ) ，当X1=X2时，s=0, 反映出可能是同一个程序；s 值越大，则两个程序的差别可能也越大，分析计算结果，给出相似度的结论。
测试数据: 选择若干组编译和运行都无误的C++程序，程序之间有相近的和差别大的，用上述方法求s, 对比两个程序的相似性。
提高要求：建立源代码用户标识符表，比较两个源代码用户标识符出现的频度，综合关键字频度和用户标识符频度判断两个程序的相似性。
题目１９：小型文本编辑器（***）
问题描述：设计一个行编辑程序，使其具有通常行编辑器(如Vi 、Edlin ) 应具备的基本功能。
基本要求：编辑器应具备对文本文件的查找、插人、删除、修改、字符串替换、统计字数，统计行数等功能，对于超过一屏的长文件，应能够分页显示，查找功能用字符串匹配算法实现。设计用户接口命令，实现对文本的编辑。具体的编辑命令，可参考数据结构算法网络教学平台上提供的edlin 、Vi 的命令集。
测试数据：任一文本文件。
提高要求：１. 可以支持“* ”、“? ”等通配符；
２. 支持复制、粘贴等功能
3. 支持多文档同时编辑；
提示：可以考虑用双向链表实现，每一结点表示一行字符，注意每行字符不能超过255。 题目２０：小型英汉词典（***）
问题描述：设计一个英汉词典，支持Member 的查找、插入、删除操作。
基本要求：实现字典的常用方法有：有序线性表（用二分检索实现）、A VL 树（二叉搜索树）、Patricia Tree、散列表等，任选一种方法实现字典的操作，查找单词、插入单词（插入时，先查找，找不到插入，找到提示用户）、删除单词（删除时，先查找，找到删除，找不到提示用户）。字典是按字母顺序排列的，不能用顺序查找，插入或删除单词后，要保持字典的有序性。
测试数据：任一英文单词。
提高要求：选用两种以上的方法实现字典的操作，并比较不同实现算法的时间复杂度和空间复杂度。
提示：字典可以自己建立，但必须按字母a~z建立26个文件，建议从网上下载，文件类型为txt 。
题目２１：关系的计算与判断问题（***）
问题描述：设计一个程序，求出给定集合上所有不同的等价关系和偏序关系，并且判断给定集合上的关系是否为等价和偏序关系。
基本要求：
(1)输入集合的元素首先求出给定集合上所有不同的划分，
(2)求给定集合上所有不同的等价关系；
(3) 求给定集合上所有不同的偏序关系；
(4)判断给定集合上的关系是否为等价和偏序关系；
(5)原始数据和结果数据要保存到文件中。
测试数据：分别选择自然数和字母作为集合中元素，用这两种数据测试
提高要求：设计求给定集合上关系的自反闭包、对称闭包，以及用Warshall 算法求传递闭包的程序。
题目２２：加密系统的设计与实现（***）
基于Lorenz 系统的密码算法的设计与实现
问题描述：设计用基于类H énon 系统生成的混沌序列加密文件并用程序实现 基本要求：
（1）求出混沌序列；
（2）编程实现；
（3）原始数据和结果数据要保存到文件中。
提高要求：构造基于Lorenz 系统的加密程序
题目２３：地图着色（***）
问题描述：对中国地图进行着色，两个共同边界的省份染不同的颜色，当可以选择7、6、5、4种不同的颜色的情况下，由程序自动进行处理，给出具体的染色方案。
基本要求：
（1）建立以省为节点，以是否相邻为边的一个无向图；
（2）从颜色模板中选取一个颜色赋值给每个节点；
(3) 相邻节点颜色不能相同；
测试数据：学生可以自己选取颜色模板做为测试数据；分别需要测试7、6、5、4种不同的颜色。
提高要求：当用4种颜色染色时，给出不同的染色方案，计算染色的效率。 题目２４ 漫游中国（***）
问题描述：从任一省会出发，走遍所有省会，给出某种评价指标，然后根据该指标由计
算机选择最优的漫游路线。
基本要求：
（1）建立以省会为节点，以是否相邻为边的一个无向赋权图；
（2）只能选择陆路和水路交通；
(3) 每条边的权重为两地之间的距离，以公里为单位；
测试数据：学生可以自己选取评价指标，如费用最少、时间最短等等。 提高要求：不同的出发点结果是否一致，并讨论多目标模型。
数据结构课程设计题目
地图着色
马踏棋盘
栈的实现
八皇后算法
车厢调度
公园导游图
通讯录实现
同学录实现
导游系统实现
最小生成树实现
统计成绩系统
利用学到的编程知识和编程技巧，通过布置具有一定难度的程序设计题目，让学生自己到图书馆查阅资料或网上咨询独立完成程序的编写，并能运用学过的技巧独立上机调试完成。
系统类题目：
题目１：学生信息管理系统设计
试设计一学生信息管理系统，使之能提供以下功能：
系统以菜单方式工作
学生信息包括：学号，姓名，年龄，别，出生年月，地址，电话，E-mail 等。
3http://www.huoluoyou.net、学生信息录入功能（学生信息用文件保存）---输入
4、学生信息浏览功能---输出
5、查询、排序功能---算法
6、学生信息的删除与修改（可选项）
题目２ ：职工信息管理系统设计
试设计一职工信息管理系统，使之能提供以下功能：
1、系统以菜单方式工作。
2、职工信息包括职工号、姓名、别、年龄、学历、工资、住址、电话等（职工号不重复）。
3、职工信息录入功能(职工信息用文件保存) －－输入。
4、职工信息浏览功能 －－输出。
5、查询和排序功能：(至少一种查询方式) －－算法。
6、职工信息删除、修改功能(任选项) 。
题目３： 一堆猴子都有编号，编号是1，2，3 ...m , 这群猴子（m 个）按照1到m 的顺序围坐一圈，从第1开始数，每数到第n 个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
要求：输入数据输入m 、,n 其中m 、,n 为整数，n 输出形式提示按照m 个猴子，数n 个数的方法，输出为大王的猴子是几号。
难度1：编程先由计算机‚想‛一个1到100之间的数请人猜，如果人猜对了，则计算机给出提示：‚Right! ‛， 否则提示：‚Wrong! ‛，并告诉人所猜的数是大(Too high)还是小(Too low)，然后结束游戏。要求每次运行程序时机器所‚想‛的数不能都是一样的。
难度2：编程先由计算机‚想‛一个1到100之间的数请人猜，如果人猜对了，则结束游戏，并在屏幕上输出人猜了多少次才猜对此数，以此来反映猜数者‚猜‛的水平，否则计算机给出提示，告诉人所猜的数是太大还是太小，直到人猜对为止。
难度3：编程先由计算机‚想‛一个1到100之间的数请人猜，如果人猜对了，则结束游戏，并在屏幕上输出人猜了多少次才猜对此数，以此来反映猜数者‚猜‛的水平，否则计算机给出提示，告诉人所猜的数是太大还是太小，最多可以猜10次，如果猜了10次仍未猜中的话，则结束游戏。
难度4：编程先由计算机‚想‛一个1到100之间的数请人猜，如果人猜对
了，并在屏幕上输出人猜了多少次才猜对此数，以此来反映猜数者‚猜‛的水平，则结束游戏，否则计算机给出提示，告诉人所猜的数是太大还是太小，最多可以猜10次，如果猜了10次仍未猜中的话，则停止本次猜数，然后继续猜下一个数。每次运行程序可以反复猜多个数，直到操作者想停止时才结束。
题目４．停车场管理
问题描述：
设停车场是一个可停放n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在停车场的最北端）, 若停车场内已停满n 辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。
基本要求
以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车‚到达‛或‚离去‛信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。
测试数据
设n=2，输入数据为：（‘A ’,1,5）, （‘A ’,2,10）, （‘D ’,1,15）, （‘A ’,3,20）, （‘A ’,4,25）, （‘A ’5,30）, （‘D ’,2,35）, （‘D ’,4,40）, （‘E ’,0,0）。其中：‘A ’表示到达（arrival ）；‘D ’表示离去（departure ）；‘E ’表示输出结束（end ）。
实现提示
需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。
选作内容
（1）两个栈共享空间，思考应开辟数组的空间是多少？
（2）汽车可有不同种类，则他们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。
（3）汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。
题目５．魔王语言解释
问题描述
有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没有人能听懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：
（1）α->β1β2……βm
（2）（θδ1δ2……δn ）—>θδn θδn-1……θδ1θ
在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话；
基本要求
用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。
（1）B->tAdA
（2）A->sae
测试数据
B （ehnxgz ）B 解释成tsaedsaeezegexenehetsaedsae
若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：‚天上一
将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈，将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者思考应如何处理。应首先实现栈和队列的基本操作。 选作内容
（1）由于问题的特殊性，可以实现栈和队列的顺序存储空间共享。
（2）代换变量的数目不限，则在程序开始运行时首先读入一组第一种形式的规则，而不是把规则固定在程序中（第二种形式的规则只能固定在程序中）。
题目６．校园导游咨询
问题描述
设计一个校园导游程序，为来访的客人提供各种信息查询服务。
基本要求
（1）设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息：以边表示路径，存放路径长度等相关信息。
（2）为来访客人提供图中任意景点相关信息的查询。
（3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
测试数据
由读者根据实际情况指定。
实现提示
一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。
选作内容
（1）提供图中任意景点问路查询，即求任意两个景点之间的所有路径。
（2）扩充道路信息，如道路类别（车道、人行道等）、沿途景色等级，以至可按客人所需分别查询人行路径或车行路径或观景路径等。
（3）实现校园导游图的仿真界面
题目７迷宫问题
问题描述
以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
基本要求
首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d ）的形式输出，其中：（i,j ）指示迷宫中的一个坐标,d 表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：
（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2）……
题目８ 成绩管理
问题描述：给出n 个学生的考试成绩表，成绩表包括学生的学号、姓名、考试成绩（高等数
学、英语、物理），设计一个简单的成绩管理程序。
基本要求：
（1）建立成绩表，能够插入、删除、修改学生的成绩记录；
（2）按任一单科成绩排序；
(3) 计算每名学生的平均成绩；
(4) 统计任一单科成绩不及格的学生人数, 输出不及格人数及不及格的学生名单
(5) 根据平均成绩将成绩表按由高到低的次序排列，统计每名学生在考试中获得的名次，分数相同的为同一名次，按名次输出成绩表。
(6) 成绩表保存在文件中, 可以从文件读取数据。
测试数据：学生可以根据自己班级的考试成绩单，任意截取一部分做为测试数据 提高要求：成绩表用链式结构表示，实现上述全部要求。
题目９：一元多项式简单计算
问题描述：设计一个简单一元多项式计算器。
基本要求：(1)输入并建立多项式；
(2)输出多项式；
(3)两个多项式相加，输出结果多项式；
(4)两个多项式相减，输出结果多项式。
测试数据：可任意选取两个一元多项式，可以是一般的多项式，也可以是稀疏多项式。 提高要求：可以根据输入变量的值，计算出多项式的结果，且算法的效率高。
题目10：舞伴问题
问题描述：一班有m 个女生、n 个男生(m不等于n), 举办一场舞会. 男女生分别编号坐在舞池两边的椅子上，每曲开始时, 依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴，设计一个程序模拟舞伴配对过程。
基本要求：输入男、女学生的姓名、性别，由程序自动为男女生编号，可以顺序编号，也可以随机编号，输出每曲配对情况（包括男、女生的姓名、性别和编号）。原始数据和结果数据要保存到文件中。
测试数据：分别选择男生多于女生、女生多于男生、男女生相等的三组测试数据
提高要求：计算出任意一位男生(编号为X) 和任意一位女生(编号为Y), 在第K 曲配对跳舞的情况。
题目１１：文学研究助手（*）
问题描述：文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。
基本要求：英文小说存于一个文本文件中，待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计, 结果保存到文件中。
测试数据：以你的C/C++/JAVA源程序模拟英文小说，相应语言的保留字集作为待统计的词汇集。
题目１２：哈希表的设计与实现（*）
问题描述：针对某个单位电话号码簿，设计一个哈希表，并完成相应的建表和查表程序。 基本要求：设每个记录有下列数据项：电话号码、用户名、住址。从键盘输入各记录，以用户名为关键字建立哈希表，哈希函数用除留取余数法构造，采用线性探测法解决冲突。可以插入、查找、删除并显示给定用户名的记录，并计算查找长度, 哈希表保存到文件中，并能从文件中读取数据。
测试数据：取某个单位电话号码簿中的30个记录。
提高要求：将电话号码薄以文件形式保存到盘上，能够按用户名和电话号码两种形式建立哈希表并实现插入、查找、删除表中元素的功能。
注意事项：不能用类库中的类完成题目
题目１３：管道铺设施工的最佳方案（*）
问题描述:需要在某个城市的n 个小区铺设管道，则在这n 个小区之间铺设n-1条管道即可，假设任意两个居民区之间都可以架设管道，但由于地理环境的不同，所需经费不同，选择最优的施工方案使总投资尽可能的少。
基本要求：输入表示小区间关系的图及每条管道的权值，选择出n-1条管道, 使总投资最小。图的信息输入一次后, 保存到文件中, 选择的n-1条管道输出到显示器的同时, 也保存于文件中。
测试用例：任意选择一个图，模拟小区间可能铺设的管道及费用。
提高要求：显示原始图及选择n-1条管道后的图。
题目１４：安排教学计划（**）
问题描述：大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两个学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排上必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课程恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。
基本要求：输入参数包括学期总数，一学期的学分上限，每门课程的课程号、学分和直接先修课的课程号；允许两种策略，一是使学生在各学期的学习负担尽量均匀，二是使课程尽量集中在前几个学期；若根据给定的条件问题无解，则报告适当的信息，否则将教学计划输出到用户指定的文件中。教学计划的表格格式自行设定, 可以从键盘读取数据也可以从文件读取数据, 结果保存到文件中。
测试数据：学期总数为6，学分上限为10，该专业共开设12门。以08级某专业必修课与选修课为例，选择12门课程及相应学分，制定一个表明各门课程先后约束关系的有向图。
提高要求：产生多种不同的方案，并使方案之间的差异尽可能地大。
题目１５：计算表达式的值(**)
问题描述：对于给定的一个表达式，表达式中可以包括常数、算术运行符（“+”、“-”、“*”、“/”）和括号，编写程序计算表达式的值。
基本要求：从键盘输入一个正确的中缀表达式，将中缀表达式转换为对应的后缀表达式，计算后缀表达式的值。
测试数据：任意选取一个符合题目要求的表达式。
提高要求：（1）对于表达式中的简单错误，能够给出提示；
（2）不仅提示错误，也能给出错误信息
（3）表达式中可以包括单个字母表示的变量
（4）能够处理多种操作符
（5）实现包含简单运算的计算器
（6）实现一个包含简单运算和函数运算的计算器
题目１５：设计Huffman 编码器与解码器（**）
问题描述：利用哈夫曼编码进行信息通讯可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码；在接受端将传来的数据进行译码。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个哈夫曼码的编/译码系统。
基本要求：根据某字符文件统计字符出现频度，构造Huffman 树，编制Huffman 编码，并将给定字符文件编码，生成编码文件；再将给定编码文件解码，生成字符文件。（要求按二进制位表示编码）
测试数据：英文文件。
题目１６：银行业务模拟（**）
问题描述：设银行有四个服务窗口，一个等待队列, 每个窗口均可以办理存款、取款、挂失、还贷业务，每种业务所需的服务时间不同，客户到达银行后，先到打号机上打号，号票上包括到达时间、编号和需要办理的业务，然后在银行内等候, 当任一服务窗口空闲时, 处理等候客户中排在最前面的客户的业务。写一个上述银行业务的模拟系统, 通过模拟方法求出客户在银行内逗留的平均时间和每个窗口办理的客户数及办理的每种业务数。
基本要求：每个客户到达银行的时间和需要办理的业务随机产生，输出一天客户在银行的平均逗留时间和每个窗口每天办理的客户数和每种业务数。
测试数据：营业时间为8小时，其他模拟量自行设定。
题目１７：真值表的设计与实现（**）
问题描述：对给出的任意一个合式公式（不超过四个命题变元），用C 语言的程序编程表示出来，并且能够计算它在各组真值指派下所应有的真值，画出其真值表。
基本要求：
（1）已知命题p 和q 的真值，求出它们的合取、析取、蕴涵和等价的真值；
（2）表示出合式公式；
（3）给出任意一个合式公式（不超过四个命题变元），设计程序把它表示出来，并且能够计算它在各组真值指派下所应有的真值（或是逻辑运算的结果）。
提高要求：构造任意合式公式的真值表
题目１８：程序源代码的相似性（***）
问题描述：对于两个C++语言的源程序代码，用哈希表的方法分别统计两个程序中使用C++语言关键字的情况，并最终按定量的计算结果，得出两份程序的相似性。
基本要求：建立C++语言关键字的哈希表，统计在每个源程序中C++关键字出现的频度, 得到两个向量X1和X2，通过计算向量X1和X2的相对距离来判断两个源程序的相似性。
例如:
关键字 Void Int For Char if else while do break class 程序1关键字频度 4 3 0 4 3 0 7 0 0 2 程序2关键字频度 4 2 0 5 4 0 5 2 0 1 X1=[4,3,0,4,3,0,7,0,0,2]
X2=[4,2,0,5,4,0,5,2,0,1]
设s 是向量X1和X2的相对距离，s =sqrt( ∑(xi1-x i2) 2 ) ，当X1=X2时，s=0, 反映出可能是同一个程序；s 值越大，则两个程序的差别可能也越大，分析计算结果，给出相似度的结论。
测试数据: 选择若干组编译和运行都无误的C++程序，程序之间有相近的和差别大的，用上述方法求s, 对比两个程序的相似性。
提高要求：建立源代码用户标识符表，比较两个源代码用户标识符出现的频度，综合关键字频度和用户标识符频度判断两个程序的相似性。
题目１９：小型文本编辑器（***）
问题描述：设计一个行编辑程序，使其具有通常行编辑器(如Vi 、Edlin ) 应具备的基本功能。
基本要求：编辑器应具备对文本文件的查找、插人、删除、修改、字符串替换、统计字数，统计行数等功能，对于超过一屏的长文件，应能够分页显示，查找功能用字符串匹配算法实现。设计用户接口命令，实现对文本的编辑。具体的编辑命令，可参考数据结构算法网络教学平台上提供的edlin 、Vi 的命令集。
测试数据：任一文本文件。
提高要求：１. 可以支持“* ”、“? ”等通配符；
２. 支持复制、粘贴等功能
3. 支持多文档同时编辑；
提示：可以考虑用双向链表实现，每一结点表示一行字符，注意每行字符不能超过255。 题目２０：小型英汉词典（***）
问题描述：设计一个英汉词典，支持Member 的查找、插入、删除操作。
基本要求：实现字典的常用方法有：有序线性表（用二分检索实现）、A VL 树（二叉搜索树）、Patricia Tree、散列表等，任选一种方法实现字典的操作，查找单词、插入单词（插入时，先查找，找不到插入，找到提示用户）、删除单词（删除时，先查找，找到删除，找不到提示用户）。字典是按字母顺序排列的，不能用顺序查找，插入或删除单词后，要保持字典的有序性。
测试数据：任一英文单词。
提高要求：选用两种以上的方法实现字典的操作，并比较不同实现算法的时间复杂度和空间复杂度。
提示：字典可以自己建立，但必须按字母a~z建立26个文件，建议从网上下载，文件类型为txt 。
题目２１：关系的计算与判断问题（***）
问题描述：设计一个程序，求出给定集合上所有不同的等价关系和偏序关系，并且判断给定集合上的关系是否为等价和偏序关系。
基本要求：
(1)输入集合的元素首先求出给定集合上所有不同的划分，
(2)求给定集合上所有不同的等价关系；
(3) 求给定集合上所有不同的偏序关系；
(4)判断给定集合上的关系是否为等价和偏序关系；
(5)原始数据和结果数据要保存到文件中。
测试数据：分别选择自然数和字母作为集合中元素，用这两种数据测试
提高要求：设计求给定集合上关系的自反闭包、对称闭包，以及用Warshall 算法求传递闭包的程序。
题目２２：加密系统的设计与实现（***）
基于Lorenz 系统的密码算法的设计与实现
问题描述：设计用基于类H énon 系统生成的混沌序列加密文件并用程序实现 基本要求：
（1）求出混沌序列；
（2）编程实现；
（3）原始数据和结果数据要保存到文件中。
提高要求：构造基于Lorenz 系统的加密程序
题目２３：地图着色（***）
问题描述：对中国地图进行着色，两个共同边界的省份染不同的颜色，当可以选择7、6、5、4种不同的颜色的情况下，由程序自动进行处理，给出具体的染色方案。
基本要求：
（1）建立以省为节点，以是否相邻为边的一个无向图；
（2）从颜色模板中选取一个颜色赋值给每个节点；
(3) 相邻节点颜色不能相同；
测试数据：学生可以自己选取颜色模板做为测试数据；分别需要测试7、6、5、4种不同的颜色。
提高要求：当用4种颜色染色时，给出不同的染色方案，计算染色的效率。 题目２４ 漫游中国（***）
问题描述：从任一省会出发，走遍所有省会，给出某种评价指标，然后根据该指标由计
算机选择最优的漫游路线。
基本要求：
（1）建立以省会为节点，以是否相邻为边的一个无向赋权图；
（2）只能选择陆路和水路交通；
(3) 每条边的权重为两地之间的距离，以公里为单位；
测试数据：学生可以自己选取评价指标，如费用最少、时间最短等等。 提高要求：不同的出发点结果是否一致，并讨论多目标模型。