数据结构与算法课设题目一1

1、2013年秋季学期，数据结构与算法课程设计题目 1.扫雷问题。有些个人计算机会带有一个名为Min esweeper的游戏。该游戏界 面是一个网格，网格中的有些方块是雷。编写一个程序以读取文件，该文件 中存放着网格中的行数、列数以及网格本身。网格会含有一些标记为o的方 块，这些就是雷。其他方块不是雷，将会标记上问号（？）。程序的输出就是 输出这个网格。雷依然会标记成o,而那些不含雷的方块会替换成一个数字， 以表明邻近雷的个数。最大数字将是 b）编写程序，构造与D相对应的某一个数列A,注意A不是唯一的。（4） 7. 占用网格计算问题。考虑一个N*N的网格，其中某些方格已被占用。如果两 个方格共用公

2、共的边，就说它们属于同一个组，如图示，一组为 4个被占用 的方格，3组为两个被占用的方格，2个方格被单独占用。假设格子用二维数 组来表示。请编写实现下列目的程序： 1）给定组中的某个方格，计算组的大小； 2）计算不同组的数目； 3）列出所有的组。（4） 8. 递归替换问题。编写程序，扩展C/C+源文件中的#inelude指令（以递归的 方式）。请以文件名的内容替换形如下面的代码行。 #in elude“ file name ”（ 3） 9. 数据删除问题。编写删除具有N个数据项的数组A中所有重复项的程序，返 回A中仍有的数据项。要求运行时间在 0（ NlogN）。（ 2） 10. 随机走步问题

3、。以下在x-y坐标系上进行的游戏属于二维的随机行走。从原 点（0，0）开始，每次迭代都是由向左、向上、向右和向下一个单位的随机 步构成。当行走者返回原始点时，行走结束。在二维世界这种情况发生的概 率为1，而在三维世界概率小于1。请编写一个进行100次独立随机行走程序， 并计算每个方向的步数的平均数。（4） 11. 表达式转换问题。请编写一个读取中缀表达式并生成后缀表达式的程序。（2） 12. 表达式转换问题。请编写一个读取后缀表达式并生成中缀表达式的程序。（2） 13. 课程选修问题。学生需要修一定数量的课程才能毕业，而这些课程会有一些 必须遵循的选修顺序。假设每个学期都开所有课程，并且学生所

4、修课程数量 不限制。给出课程和先修课程的列表，求出一个满足最小学期数要求的时间 表。以你的专业情况为背景设计。（3） 14. 通过单字符置换可以将一个单词改为另一个单词。假设存在一个5字母单词 的字典。给出一个算法确定单词 A是否可以通过一系列的单字符置换转换为 单词B,并且如果可以的话，输出相应的单词序列。例如， bleed通过序列 bleed、ble nd、bio nd、blood 转换为 blood。 （ 4） 15. 编写一个以行为单位的文本编辑器。内部文件的副本被保存成由各个行组成 的链表。为了能在文件中上移或下移，必须维护一个双链表。大部分命令使 用只有一个字符的字符串表示。有些是

5、两个字符，并且要求一个参数（或者 两个）。（6） 表一，所支持的命令行 命令 功能 l 移到顶部 a 在当前行之后添加文本，直到本行出现.字符 d 删除当前行 dr num num 删除若干行 f n ame 更改当前行的名称 g num 转到指定的行 h 获得帮助 i 与a类似，在当前行之前添加文本行 m num 将当前行移到指定行数之后 mr num num num 将若干行作为一个整体移到指定行数之后 n 标记是否显示行号 P 打印当前行 pr num num 打印若干行 q! 退出，并且放弃写入 r n ame 读取并且粘帖另一个文件到当前文件中 t num 将当前行复制到指定行数之后

6、 tr num num num 将若干行复制到指定行数之后 w 将文件写到磁盘中 x! 写入后退出 $ 转到最后一行 - 往上移动一行 + 往下移到一行 = 打印当前行 # 打印文件中的行和字符 16. 跳马问题。要求在64个国际象棋格子，任意位置放一个马，如何不重复地把 格子走完。（3） 17. 八皇后问题。要求编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的 位置上的算法，并给出所有的解。提示：在国际象棋上放置皇后时，任何一 个皇后的水平、竖直和斜45。都不能有另一个皇后。解决该问题采用逐次试 探的方法，即采用递归调用putchess函数的方法。首先将第一个皇后放于第 一行第一列，然后开

7、始向下一行递归。每一步递归中，首先检测待放置位置 是否与已放置的皇后冲突，如不冲突，贝U进行下一行的放置，否则，选择该 行的下一个位置进行检测。如整行的位置都冲突，则回到上一行，重新选择 位置。（2） 18. 猴子吃桃子问题。有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半 且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这 群猴子共摘了多少个桃子。要求：1）采用数组数据结构实现上述求解；2）采 用链式数据结构实现上述求解；3）采用递归实现上述求解。（2） 19. 病人就医管理模拟问题。编写一个程序定义行医类，反映病人到医院看病， 排队看医生的情况，在病人排队过程中，主要发

8、生两件事： （1）病人到达诊室，将病历本交给护士，排到等待队列中候诊。 （2）护士从等待队列中取出一位病人的病历，该病人进入诊室就诊。 要求程序采用菜单方式，其选项及功能说明如下： （1）排队-输入病人的病历号，加入到病人排队队列中 (2) 就诊 病人排队队列中最前面的病人就诊，并将其从队列中删除。 (3) 查看排队-从队首到队尾列出所有的排队病人的病历号。 (4) 下班退出运行。(5) 20. 图的基本操作与实现。 1自选存储结构,输入含n个顶点(用字符表示顶点)和e条边的图G; (2) 求每个顶点的度,输出结果； (3) 指定任意顶点x为初始顶点,对图G作DFS遍历,输出DFS顶点序列(提

9、示： 使用一个栈实现DFS); 指定任意顶点x为初始顶点,对图G作BFS遍历,输出BFS顶点序列(提示： 使用一个队列实现BFS)； (5) 输入顶点x,查找图G:若存在含x的顶点,则删除该结点及与之相关连的边, 并作DFS遍历(执行操作3);否则输出信息“无x”； (6) 判断图G是否是连通图，输出信息“ YES / “NO； (7) 如果选用的存储结构是邻接矩阵，则用邻接矩阵的信息生成图 G的邻接表, 即复制图G,然再执行操作(2);反之亦然。(4) 21. 散列表的设计与实现。设计散列表实现电话号码查找系统。基本要求：(2) (1) 设每个记录有下列数据项：电话号码、用户名、地址； (2

10、) 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表； (3) 采用双散列法解决冲突； (4) 查找并显示给定电话号码的记录； (5) 查找并显示给定用户名的记录。 较高要求：(3) (1) 系统功能的完善； 设计不同的散列函数，比较冲突率； (3) 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均 查找长度的变化。 22. 队列实现的仿真技术预测理发馆的经营状况 。(5) 问题描述：理发馆一天的工作过程如下： 1) 理发馆有N把理发椅，可同时为N位顾客进行理发。 2）理发师分三个等级（一级、二级、三级），对应不同的服务收费。 3）当顾客进门时，需选择某级别理发师，只

11、要该级别的理发师有空椅，则可 立即坐下理发，否则需排队等候。 4）一旦该级别的理发师有顾客理发完离去，排在队头的顾客便可开始理发。 5）若理发馆每天连续营业T分钟，求： （1）一天内顾客在理发馆内的平均逗留时间； （2）顾客排队等候理发的队列长度平均值； （3）营业时间到点后仍需完成服务的收尾工作时间； （4）统计每天的营业额； （5）统计每天不同级别理发师的创收。 23. 救护车调度模拟系统。问题描述：设计实现一个用事件驱动的“救护车调度” 离散模型，模拟120急救中心响应每个病人的呼救信号统一调度救护车运行的情 况。（5） 对问题作适当简化，假设：某城市共有m个可能的呼救点（居民小区、工厂

12、、 学校、公司、机关、单位等），分布着n所医院（包含在m个点中），有k辆救护 车分派在各医院待命，出现呼救病人时，由急救中心统一指派救护车接送至最近 的医院救治。救护车完成一次接送任务后即消毒， 并回原处继续待命。假定呼救 者与急救中心、急救中心与救护车之间的通讯畅通无阻， 也不考虑道路交通堵塞 的影响。可以用m个顶点的无向网来表示该城市的各地点和道路。时间可以分钟 为单位，路段长可表示为救护车行驶化费的分钟数。 24. 稀疏矩阵的操作。基本要求（4）: 定义稀疏矩阵的数据类型描述（三元组表）,完成稀疏矩阵的加、减、乘和转置运 算.要求： 1）界面友好，函数功能要划分好； 2）总体设计应画流程

13、图； 3）程序要加必要的注释； 4）要提供程序测试方案； 25. 构造可以使n个城市连接的最小生成树。问题描述：给定一个地区的n个城 市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并计算得到的最小 生成树的代价。（4） 要求： 1）城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中 给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无 穷大值.要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显 示得到的最小生成树的代价。 2）表示城市间距离网的邻接矩阵（要求至少6个城市,10条边）； 3）最小生成树中包括的边及其权值,并显示得到的最

14、小生成树的代价。 26. 长整数运算问题。设计程序，实现两个任意长的整数的加、减、乘运算问题。 （4） 27. 哈夫曼码的编/译码系统。编写一个哈夫曼码的编/译码系统，实现对输入的 文本信息自动统计并依此为依据建立一个哈夫曼码的编/译码系统。（2） 28. 集合运算问题。设计一个程序，实现两个集合的并集、交集、差集、显示输 出等，要求结果集合中的元素不重复；实现一个集合的幕集的求解。（1） 29. 排序算法比较问题。设计各类排序算法的程序，通过随机的数据测试，比较 各算法的关键字比较次数和关键字移动次数。（2） 30. 约瑟夫（Joeph）问题。一种描述是：编号为1,2,n的n个人按顺时针方

15、向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上 限值m从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。 报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始 重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列 顺序。（2） 难得的是有份清闲时光，难得的是有种知途迷返，知之为知之，不知 为不知，知你冷暖，懂你悲欢，把你放在了心头上的人。难得的是面对片 深山广林、教你为人，怎样处事，面对人生 ；淡泊世事，践行伯乐，明镜心 扉。 心似无物化有物，道似无情渡有情，佛似无边胜有边，儒似学而不思 厌也，山高不止于流水，流水不止于小桥，除非去哪里在看看，除非去哪 里在历历，除非去哪里在观光！ 一路走马观花，沐浴星星的乐园，想哪，念 那