数据结构课程设计题目
《数据结构》方向选题
|
序号
|
数据结构（选题）
|
适用专业
|
题目类型
|
课题来源与性质
|
供题
教师
|
题目简介与要求
|
|
1
|
PC机泡泡堂游戏
|
计算机及相关专业
|
设计
|
生产/社会实际模拟题
|
邹飚/王志高
|
编写一个应用程序实现泡泡堂游戏，要求有游戏菜单，选择不同的菜单会出现不同的效果，游戏方式为人与人之间的对战，实现泡泡堂游戏的所有规则，有不同的道具，不同的道具让玩家有不同的增益或减益；游戏胜利或失败后能重新开始。
|
|
2
|
坦克大战
|
计算机及相关专业
|
设计
|
生产/社会实际模拟题
|
邹飚/王志高
|
编写应用程序实现坦克大战游戏，人机对战，模拟红白机上坦克大战游戏，一次出现四辆NPC坦克，有简单的AI，能发射子弹攻击，实现不同的道具，不同的道具有不责骂的增益或减益效果，实现不同的障碍，不同的障碍有不同的效果，比如水面，坦克不可通行，但子弹能通行；游戏胜利过关，失败结束退回游戏菜单。
|
|
3
|
俄罗斯方块
|
计算机及相关专业
|
设计
|
生产/社会实际模拟题
|
邹飚/王志高
|
编写应用程序实现俄罗斯方块游戏，实现俄罗斯方块游戏所有的规则，实现下一个方块的提示，实现过关后速度的增加，显示得分，有游戏界面。
|
|
4
|
贪吃蛇游戏
|
计算机及相关专业
|
设计
|
生产/社会实际模拟题
|
邹飚/王志高
|
编写应用程序实现贪吃蛇游戏，实现蛇的移动，比如按蛇在往右过程中按左键操作不能有反应，食物的不同的种类，不同的食物会对蛇产生不同的效果，比如有一种食物能让蛇临时增加速度，实现关卡的切换，有随机的出现的障碍，会对蛇产生阻碍，有游戏界面。
|
|
5
|
2D地图编辑器
|
计算机及相关专业
|
设计
|
生产/社会实际模拟题
|
邹飚/王志高
|
编写走格子类型游戏的2D地图编辑器，要求实现地图编辑和地图预览，能实现数据的存储和读取，数据的任意修改。
|
|
6
|
约瑟夫生死游戏
|
计算机及相关专业
|
设计
|
人工智能模拟题
|
邹飚/王志高
|
约瑟夫生死游戏：30个人围成一个圈由第一个人数起，依次报数，数到第九个人，便把他剔除，然后再从他的下一个人数起，数到第九个人，再将他剔除剩下15个乘客为止，问那些位置将是被扔下大海的位置。
|
|
7
|
彩票开奖问题
|
计算机及相关专业
|
设计
|
生产/社会实际模拟题
|
邹飚/王志高
|
写出6＋1彩票开奖的情况，当前6个号码和特别号都对的时候，这个时候是特等奖。如果前面6个号码都对的时候，中的是一等奖。在前面6个数字中连续的对了5个的时候，中的是二等奖。在前面6个数字中连续的对了4个的时候，中的是三等奖。请编写程序，实现连续多个输入，并在每次输入以后显示号码中奖的情况。
|
|
8
|
日历系统的设计
|
计算机及相关专业
|
设计
|
生产/社会实际模拟题
|
邹飚/王志高
|
编写一程序实现对输入的任一年份中所有月份日期对应星期计算的万年日历系统。1、输入任一年将显示出该年的所有月份日期，对应的星期；2、注意闰年情况；
|
|
9
|
八皇后游戏
|
计算机及相关专业
|
设计
|
人工智能模拟题
|
邹飚/王志高
|
八皇后是个古老而有趣的游戏，是由高斯于1850年首先提出的。要求在国际象棋的棋盘上放置八个皇后，使其不能相互攻击，即任意两个皇后不能处于棋盘的同一行、同一列和同一条对角线上。试问有多少种放法？
|
|
10
|
比较同学的年龄
|
计算机及相关专业
|
设计
|
人工智能模拟题
|
邹飚/王志高
|
编写类student，其中包含生日（年、月、日）的私有变量，要求能比较两位学生的年龄差距（精确到多少天），用重载“－”运算符实现年龄差的计算。
|
|
11
|
比我疆土
|
计算机及相关专业
|
设计
|
人工智能模拟题
|
邹飚/王志高
|
四位分别来自中国、美国、俄罗斯、加拿大的小学生都以自己的国土面积大而骄傲不已，但是他们想知道到底谁的国土最大，谁的最小，他们的判断如下：加拿大学生：加拿大最大，美国最小，俄罗斯第三。美国学生：美国最大，加拿大最小，俄罗斯第二，中国第三。中国学生：美国最小，加拿大第三。他们互不相让，最后老师下定结论：对于上述四国面积的判断，他们每人只判断对了一个国家。对于老师的提示，四位小学生还是绞尽脑汁推断不出到底是谁的国土最大，谁的最小！现请编制程序告诉四位小学生正确顺序。
|
|
12
|
汉诺塔游戏
|
计算机及相关专业
|
设计
|
生产/社会实际模拟题
|
邹飚/王志高
|
传说婆罗门庙里有一个塔台，台上有3根标号为A,B,C的用钻石做成的柱子，在A柱子上放着64个金盘，每一个都比下面的略小一些。把A柱子上的金盘子全部移到C柱上的那一天就是世界末日。移到的条件是：一次只能移到一个金盘，移到过程中大金盘不能放在小金盘上面。庙里的僧人一直在移个不停。因为全部的移动是264－1次，如果每秒移动一次的话需要500亿年。
|
|
13
|
文本文件复制
|
计算机及相关专业
|
设计
|
人工智能模拟题
|
邹飚/王志高
|
将一个文本文件复制到另一个文件中（要求用两种方法实现：一个一个字符复制及按行进行复制）。
|
|
14
|
石头剪刀布游戏
|
计算机及相关专业
|
设计
|
生产/社会实际模拟题
|
邹飚/王志高
|
编写一个小游戏实现石头，剪刀，布的游戏规则，人机对战，能输入游戏次数，能统计玩家和电脑的总比分，最终判断玩家胜利还是电脑胜利。
|
|
15
|
深度寻路算法
|
计算机及相关专业
|
设计
|
人工智能模拟题
|
邹飚/王志高
|
要求根据当前的不同地图情况，采用深度遍历的方法寻找出一条可通行的路径。
|
|
16
|
广度寻路算法
|
计算机及相关专业
|
设计
|
人工智能模拟题
|
邹飚/王志高
|
要求根据当前的不同地图情况，采用广度遍历的方法寻找出一条可通行的路径。
|
|
17
|
A*寻路算法
|
计算机及相关专业
|
设计
|
人工智能模拟题
|
邹飚/王志高
|
要求根据当前的不同地图情况，采用智能型寻路算法（A*）寻找出一条可通行的路径。
|
|
18
|
泡泡堂游戏泡泡爆算法
|
计算机及相关专业
|
设计
|
人工智能模拟题
|
邹飚/王志高
|
要求根据当前地图上泡泡的释放情况，实现地图上所有泡泡在某一时刻的爆炸状态，已方便NPC完成自动寻路过程。
|
|
19
|
泡泡龙游戏的消除算法
|
计算机及相关专业
|
设计
|
人工智能模拟题
|
邹飚/王志高
|
要求根据当前游戏地图中泡泡的存在情况，实时检测当前可能消除的泡泡，要求应用递归算法完成。
|
|
20
|
飞机游戏中的跟踪导弹算法
|
计算机及相关专业
|
设计
|
人工智能模拟题
|
邹飚/王志高
|
要求以数据的形式，完成对竖版飞机游戏中的跟踪导弹算法。
|
|
21
|
飞机游戏中的旋转保护罩算法
|
计算机及相关专业
|
设计
|
人工智能模拟题
|
邹飚/王志高
|
要求以数据的形式，完成对竖版飞机游戏中的旋转保护罩算法。
|
1. 运动会分数统计
任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20,）
功能要求：
1) 可以输入各个项目的前三名或前五名的成绩；
2) 能统计各学校总分，
3) 可以按学校编号或名称、学校总分、男女团体总分排序输出；
4) 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。
5) 数据存入文件并能随时查询
6) 规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称
输出形式：有中文提示，各学校分数为整形
界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；
测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；
2. 飞机订票系统
任务：通过此系统可以实现如下功能：
录入：
可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）
查询：
可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；
订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；
退票：可退票，退票后修改相关数据文件；
客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。
修改航班信息：当航班信息改变可以修改航班数据文件
要求：
根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；
3. 文章编辑
功能：输入一页文字，程序可以统计出文字、数字、空格的个数。
静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。
存储结构使用线性表，分别用几个子函数实现相应的功能；
输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。
输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"（3）输出删除某一字符串后的文章；
4. 纸牌游戏
任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后…从第4张开始，以4为基数，是4的倍数的牌翻一次，直到最后一张牌；...再依次5的倍数的牌翻一次，6的，7的直到以52为基数的翻过，输出：这时正面向上的牌有哪些？
5. 宿舍管理查询软件
1) 任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：
A. 采用交互工作方式
B. 建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种)
2) 查询菜单: (用二分查找实现以下操作)
A. 按姓名查询
B. 按学号查询
C. 按房号查询
3) 打印任一查询结果（可以连续操作）
6. 地图着色问题
设计要求：已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少（4种）。
要求：
1、地图数据的输入采取从文件中读取。
2、结果输出方式可以采用图形方式或者文本方式。
7. 校园导航问题
设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。
1、 基本要求：
1） 设计校园平面图，在校园景点选10个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。
2） 为来访客人提供图中任意景点相关信息的查询。
3） 为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。
2、 实现提示：一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。
8、建立二叉树，层序、先序、中序、后序遍历（分别用递归和非递归的方法实现）
任务：能按一定方式（键盘、文件）输入树的各个结点，并能输出用不同方法遍历的遍历序列；
要求：提供良好的菜单操作界面（可以是文本模式或图形模式）
9、赫夫曼树的建立
任务：按给定的数据建立赫夫曼树
要求：可以建立函数输入二叉树，并输出其赫夫曼树。在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、输入输出、源程序、测试数据和结果。提供良好的菜单操作界面
10、纸牌游戏
任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后…从第4张开始，以4为基数，是4的倍数的牌翻一次，直到最后一张牌；...再依次5的倍数的牌翻一次，6的，7的，直到以52为基数的翻过，输出：这时正面向上的牌有哪些？
要求：提供良好的菜单操作界面
11、图的建立及输出
任务：建立图的存储结构（图的类型可以是有向图、无向图），输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。（提高部分：以图形模式输出实际图形）
要求：提供良好的菜单操作界面。
12、实现两个链表的合并
基本功能要求：
（1） 建立两个链表A和B，链表元素个数分别为m和n个。
（2） 假设元素分别为(x1,x2,…xm)，和(y1,y2, …yn)。把它们合并成一个线形表C，使得：
当m>=n时，C=x1,y1,x2,y2,…xn,yn,…,xm
当n>m时，C=y1,x1,y2,x2,…ym,xm,…,yn
输出线形表C
（3） 用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。
测试数据：
（1） A表（30，41，15，12，56，80）
B表（23，56，78，23，12，33，79，90，55）
（2） A表（30，41，15，12，56，80，23，12，34）
B表（23，56，78，23，12）
13、超大整数加法与乘法运算器设计。
任务：实现两个超大整数（成千上万位数的大整数）的加法和乘法运算，并能精确的按位输出。
要求：采用合理的存储结构，尽量节省存储空间。
14、超大整数减法与除法运算器设计。
任务：实现两个超大整数（成千上万位数的大整数）的减法和除法运算，并能精确的按位输出。（除不尽时输出整数商和余数）
要求：采用合理的存储结构，尽量节省存储空间。
15、超大整数进制转换器设计。
任务：将10进制的超大整数（成千上万位数的大整数）转换为其他任意进制的数，并能精确的按位输出。
要求：采用合理的存储结构，尽量节省存储空间。
16. 最小生成树问题
设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。
17. 通讯录的制作
模块要求：
第一个模块——主函数main()的功能是：根据选单的选项调用各函数，并完成相应的功能。
第二个模块——Menu()的功能是：显示英文提示选单。
第三个模块——Quit()的功能是：退出选单。
第四个模块——Create()的功能是：创建新的通讯录。
第五个模块——Add()的功能是：在通讯录的末尾，写入新的信息，并返回选单。
第六个模块——Find()的功能是：查询某人的信息，如果找到了，则显示该人的信息，如果未找到，则提示通讯录中没有此人的信息，并返回选单。
第七个模块——Alter()的功能是：修改某人的信息，如果未找到要修改的人，则提示通讯录中没有此人的信息，并返回选单。
第八个模块——Delete()的功能是：删除某人的信息，如果未找到要删除的人，则提示通讯录中没有此人的信息，并返回选单。
第九个模块——List()的功能是：显示通讯录中的所有记录。;
设计要求：
1) 每条信息至包含：姓名（NAME ）、性别(GENDER)、电话（TEL）、城市（CITY）邮编（EIP）几项。
2) 作为一个完整的系统，应具有友好的界面和较强的容错能力
18. 哈夫曼编码/译码器
[问题描述]
利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。
[基本要求]
一个完整的系统应具有以下功能：
（1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
（2）E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
（3）D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
（4）P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。
（5）T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
[测试数据]
（1）数据一：已知某系统在通信联络中只可能出现8种字符，其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,以此设计哈夫曼编码。利用此数据对程序进行调试。
（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。
|
字符
|
[空格]
|
A
|
B
|
C
|
D
|
E
|
F
|
G
|
H
|
I
|
J
|
K
|
L
|
M
|
|
频度
|
186
|
64
|
13
|
22
|
32
|
103
|
21
|
15
|
47
|
57
|
1
|
5
|
32
|
20
|
|
字符
|
N
|
O
|
P
|
Q
|
R
|
S
|
T
|
U
|
V
|
W
|
X
|
Y
|
Z
|
|
|
频度
|
57
|
63
|
15
|
1
|
48
|
51
|
80
|
23
|
8
|
18
|
1
|
16
|
1
|
|
[实现提示]
（1）文件CodeFile的基类型可以设为子界型bit = 0..1。
（2）用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示运行Quit。请用户键入一个先把功能符，些功能执行完毕后再经菜单，直至某次用户先把了“E”为止。
（3）在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。
19. 图书管理系统
【问题描述】
设计一个计算机管理系统完成图书管理基本业务。
【基本要求】
1) 每种书的登记内容包括书号、书名、著作者、现存量和库存量；
2) 对书号建立索引表（线性表）以提高查找效率；
3) 系统主要功能如下：
*采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；
*借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；
*归还：注销对借阅者的登记，改变该书的现存量。
【进一步完成内容】
1) 系统功能的进一步完善；
2) 索引表采用树表。
3) 设计内容
4) 程序流程图
5) 源程序
6) 软件测试报告（包括所用到的数据及结果）
20. 散列表的设计与实现
【问题描述】
设计散列表实现电话号码查找系统。
【基本要求】
1) 设每个记录有下列数据项：电话号码、用户名、地址；
2) 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；
3) 采用一定的方法解决冲突；
4) 查找并显示给定电话号码的记录；
5) 查找并显示给定用户名的记录。
【进一步完成内容】
1) 系统功能的完善；
2) 设计不同的散列函数，比较冲突率；
3) 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。
21. 走迷宫游戏
程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。
要求：
1) 老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；
2) 迷宫的墙足够结实，老鼠不能穿墙而过；
3) 正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败；
4) 添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；
5) 找出走出迷宫的所有路径，以及最短路径。
利用序列化功能实现迷宫地图文件的存盘和读出等功能
22.一元多项式的运算。（限1 人完成）
设有一元多项式Am(x)和Bn(x).
Am(x)=A0+A1x1+A2x2+A3x3+… +Amxm
Bn(x)=B0+B1x1+B2x2+B3x3+… +Bnxn
请实现求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)×Bn(x)。
要求：
1) 首先判定多项式是否稀疏
2) 分别采用顺序和动态存储结构实现；
3) 结果M(x)中无重复阶项和无零系数项；
4) 要求输出结果的升幂和降幂两种排列情况
23. 学生选修课程系统设计
假定有n门课程，每门课程有课程编号，课程名称，课程性质，总学时，授课学时，实验或上机学时，学分，开课学期等信息，学生可按要求（如总学分不得少于60）自由选课。试设计一选修课程系统，使之能提供以下功能：
课程信息录入功能(课程信息用文件保存)
课程信息浏览功能
查询功能：(至少一种查询方式)
按学分查询
按课程性质查询
学生选修课程
24. 中心对称字符串问题
(1)问题描述
有n个字符的字符串，用c或c++语言编写程序判断该字符串是否中心对称。例如，abbccdccbba与abba都是中心对称的字符串。
（2）要求
采用单链表数据结构或栈数据结构的方法实现上述问题的求解。如果采用两种或两种以上数据结构实现者，可加分。
25、利用栈求表达式的值
(1)问题描述
用c或c++语言编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。表达式从键盘输入后，按以下方法对该表达式中成份逐个进行分析：
（a）若是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。
（b）若是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。
（c）若是其它字符，则返回错误信息。
若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。
(2)要求
（a)用栈数据结构实现，且程序中应主要编写如下几个功能函数：
void initstack()：初始化堆栈。
int Make_str()：语法检查并计算。
int push_operate(int operate)：将操作码压入堆栈。
int push_num(double num)：将操作数压入堆栈。
int procede(int operate)：处理操作码。
int change_opnd(int operate)：将字符型操作码转换成优先级。
int push_opnd(int operate)：将操作码压入堆栈。
int pop_opnd()：将操作码弹出堆栈。
int caculate(int cur_opnd)：简单计算+，-，*，/。
double pop_num()：弹出操作数。
（b)如果采用两种或两种以上数据结构实现者，可加分。
26、简易文本编辑器
(1)问题描述
用c或c++语言编写一个具有简单的文字或图形菜单界面的文本编辑器。
（2）要求
（a) 具有简单的文字或图形菜单界面。
（b)能实现串或文本块的查找、替换、插入、移动、删除操作。
（c)能实现文本文件的存盘和读取功能。
（d)如果采用两种或两种以上数据结构实现者，可加分。
27、二叉树操作
（1）问题描述
用c或c++语言编写程序实现二叉树的创建，以及中序、前序、后序遍历的递归算法与非递归算法。
（2）要求
（a) 创建的二叉树以树形结构显示出来，结点需带上序号和数据值两项。
（b) 遍历的方法可以选择，遍历的结果应显示结点序号和数据值。
（c)如果采用两种或两种以上数据结构实现者，可加分。
28、舞伴问题
（1）问题描述
假设一个班有m个女生,有n个男生(m不等于n),现要开一个舞会。男女生分别编号坐在舞池的两边的椅子上，每曲开始时,依次从男生和女生中各出一人配对跳舞，本曲没成功配对者坐着等待下一曲找舞伴。用c或c++语言编写程序模拟动态地显示出上述过程。
（2）要求
（a)输出每曲男女配对情况。
（b)计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况,至少求出K的两个值。
(c)采用队列数据结构或其他数据结构实现上述问题的求解。如果采用两种或两种以上数据结构实现者，可加分。
29、敢死队问题
(1)问题描述
有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。
排长是不愿意去的，假设排长为1号，用c或c++语言编写程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。
（2)要求
采用数组数据结构、链数据结构或递归的方法实现上述问题的求解。如果采用两种或两种以上数据结构实现者，可加分。
30、猴子吃桃子问题
(1)问题描述
有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用c或c++语言编写程序实现求出原来这群猴子共摘了多少个桃子。
（3）要求
采用数组数据结构或链数据结构或递归的方法实现上述问题的求解。如果采用两种或两种以上数据结构实现者，可加分。
31、数制转换问题
(1)问题描述
用c或c++语言编写程序，实现从键盘任意输入一个M进制（2、8、10、16）的数，对其转换为其他三种进制的功能。
（2）要求
（a)要转换的数制可以选择，转换的结果以（转换前为XXXX，转换后为XXXX）的形式应显示。若输入的是2进制数，则通过选择可将其转换为8、10、16三种进制的数。
（b) 采用数组数据结构或栈数据结构或递归的方法实现上述问题的求解。如果采用两种或两种以上数据结构实现者，可加分。
32. 排序综合
利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。
要求：
1) 至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。
2) 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。
3) 如果采用4种或4种以上的方法者，可适当加分。
33. 学生成绩管理系统
现有学生成绩信息文件1（1.txt），内容如下
姓名 学号 语文 数学 英语
张明明 01 67 78 82
李成友 02 78 91 88
张辉灿 03 68 82 56
王露 04 56 45 77
陈东明 05 67 38 47
…. .. .. .. …
学生成绩信息文件2（2.txt）,内容如下:
姓名 学号 语文 数学 英语
陈果 31 57 68 82
李华明 32 88 90 68
张明东 33 48 42 56
李明国 34 50 45 87
陈道亮 35 47 58 77
…. .. .. .. …
试编写一管理系统,要求如下:
1) 实现对两个文件数据进行合并,生成新文件3.txt
2) 抽取出三科成绩中有补考的学生并保存在一个新文件4.txt
3) 对合并后的文件3.txt中的数据按总分降序排序(至少采用两种排序方法实现)
4) 输入一个学生姓名后,能查找到此学生的信息并输出结果(至少采用两种查找方法实现)
5) 要求至少使用结构体实现上述要求,若增加其他实现方式更好.
6) 采用多种方法且算法正确者,可适当加分.
34. 图的遍历和生成树求解实现
要求：
1) 先任意创建一个图；
2) 图的DFS,BFS的递归和非递归算法的实现
3) 最小生成树（两个算法）的实现，求连通分量的实现
4) 要求至少用邻接矩阵结构存储实现。若增加邻接表、十字链表多种其他的存储结构实现更好
5) 采用多种方法且算法正确者,可适当加分.
35. 线索二叉树的应用
要求：实现线索树建立、插入、删除、恢复线索的实现。
36. 稀疏矩阵实现与应用
要求：实现三元组，十字链表下的稀疏矩阵的加、转置、乘的实现。
37. 树的应用
要求：实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。
38.简单的职工管理系统
1）问题描述
对单位的职工进行管理，包括插入、删除、查找、排序等功能。
2）.要求
职工对象包括姓名、性别、出生年月、工作年月、学历、职务、住址、电话等信息。
（1）新增一名职工：将新增职工对象按姓名以字典方式职工管理文件中。
（2）删除一名职工：从职工管理文件中删除一名职工对象。
（3）查询：从职工管理文件中查询符合某些条件的职工。
（4）修改：检索某个职工对象，对其某些属性进行修改。
（5）排序：按某种需要对职工对象文件进行排序。
3）.实现提示
职工对象数不必很多，便于一次读入内存，所有操作不经过内外存交换。
（1）由键盘输入职工对象，以文件方式保存。程序执行时先将文件读入内存。
（2）对职工对象中的"姓名"按字典顺序进行排序。
（3）对排序后的职工对象进行增、删、查询、修改、排序等操作。
4）选做内容
将职工对象按散列法存储，并设计解决冲突的方法。在此基础上实现增、删、查询、修改、排序等操作。
39.铁路运输网火车站管理
1）问题背景描述
这是上海铁路局目前仍在使用的行包托运软件中的一部分内部算法。该题目采用1995年年底我国铁路运输网的真实数据进行编程和运行验证。
铁路运输网络中由铁路线和火车站的两个主要概念，譬如：1号铁路线表示京广线，2号铁路线表示京沪线等。
铁路线对象包括铁路线编号,铁路线名称，起始站编号,终点站编号,该铁路线长度，通行标志(00B客货运禁行,01B货运通行专线，10B客运通行专线，11B客货运通行)。
火车站对象包括所属铁路线编号，车站代码，车站名，车站简称，离该铁路线起点站路程及终点站路程。
2）题目要求
写一个火车站管理程序，添加、删除火车站，修改火车站的各项数据，按照车站名查询火车站的各项数据。
40. 铁路运输网铁路线管理
1）问题背景描述
这是上海铁路局目前仍在使用的行包托运软件中的一部分内部算法。该题目采用1995年年底我国铁路运输网的真实数据进行编程和运行验证。
铁路运输网络中由铁路线和火车站的两个主要概念，譬如：1号铁路线表示京广线，2号铁路线表示京沪线等。
铁路线对象包括铁路线编号,铁路线名称，起始站编号,终点站编号,该铁路线长度，通行标志(00B客货运禁行,01B货运通行专线，10B客运通行专线，11B客货运通行)。
火车站对象包括所属铁路线编号，车站代码，车站名，车站简称，离该铁路线起点站路程及终点站路程。
2）题目要求
写一个铁路线管理程序，添加、删除铁路线，修改铁路线的各项数据，给铁路线添加火车站，查询铁路线的各项数据。
41.旅游交通线路问题
有一些城镇和公路，由于沿途路况和其他因素的影响，每条旅行线路所需的旅行费用也不同，要求设计一种数据结构，能够存储各个城镇之间的公路费用与长度（若存在的话），在此基础上设计相关算法，使得用户任意输入起始城镇名称和终点城镇名称后，可以给出一条最便宜的线路以及总里程最短的线路，并给出途径的每一个城镇和总共所需的费用和总长度。
42.某银行营业厅共有6个营业窗口，设有排队系统广播叫号，该银行的业务分为公积金、银行卡、理财卡等三种。公积金业务指定1号窗口，银行卡业务指定2、3、4号窗口，理财卡业务指定5、6号窗口。但如果5、6号窗口全忙，而2、3、4号窗口有空闲时，理财卡业务也可以在空闲的2、3、4号窗口之一办理。
客户领号、业务完成可以作为输入信息，要求可以随时显示6个营业窗口的状态。
43. 课程设置问题
某专业计划进行课程设置调整，请专家确定要在m个学期中开设的n门课程，并给出每门课程的先修课程列表，专业负责人把这些数据交给你，并告诉你每个学期能开设的课程的数目。请问能否按照要求完成课程设置任务，如果可行，输出一种排课计划。
