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

《数据结构与算法课设题目一.docx》由会员分享，可在线阅读，更多相关《数据结构与算法课设题目一.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法课设题2018年秋季学期，数据结构与算法课程设计题目1扫雷问题。有些个人计算机会带有一个名为Minesweeper的游 戏。该游戏界面是一个网格，网格中的有些方块是雷。编写一个程序以读取文 件，该文件中存放着网格中的行数、列数以及网格本身。网格会含有 一些标记为。的方块，这些就是雷。其他方块不是雷，将会标记上问 号 ?)。程序的输出就是输出这个网格。雷依然会标记成。，而那些 不含雷的方块会替换成一个数字，以表明邻近雷的个数。最大数字将 是 8。4)例如：15 52?o? 2 2o2113o?o? 3 o33o24?o?o 4 34o4o5oo?o? 5 oo4o26?o? 6 3

2、o311求素数问题。埃拉托色尼筛法1) 方程求解问题。方程A5 + B5+C5 + D5 + E5=F5刚好有一个满足 0ABCDEF75的整数解。请编写一个求出该解的程序。3 )最短字符串问题。编写一个程序，从输入中读取字符串，并按长 度顺序，最短字符串优先的原则输出它们。如果有若干字符串具有相 同的长度，就按字母顺序输出它们。3)5.计算1的个数问题。编写递归程序，返回十进制数N的二进制 表示中1的个数。2)排序重构问题。令A为一个由N个已特殊排序数组成的数列：A1 , A2 ,.,AN，其中A1=0o 令 B 为 N定义为 b IJ=AI-AJ（ij ）组成的数歹I。例如，A=0 , 1

3、 , 5 , 8 ,那么 D=1 , 3,4 , 5 , 7 , 8。请完 成：a）编写程序，根据A构造D;b ）编写程序，构造与D相对应的某一个数列A ,注意A不是唯 一的。4 ）占用网格计算问题。考虑一个N*N的网格，其中某些方格已被占 用。如果两个方格共用公共的边，就说它们属于同一个组，如图示， 一组为4个被占用的方格，3组为两个被占用的方格，2个方格被单独 占用。假设格子用二维数组来表示。请编写实现下列目的程序：1）给定组中的某个方格，计算组的大小；2）计算不同组的数目；3）列出所有的组。4）递归替换问题。编写程序，扩展C/C+源文件中的include指令以递归的方式)。请以文件名的内

4、容替换形如下面的代码行。#include “filename” 3)数据删除问题。编写删除具有N个数据项的数组A中所有重复项 的程序，返回A中仍有的数据项。要求运行时间在CRnlogn)。2 ) p=随机走步问题。以下在x-y坐标系上进行的游戏属于二维的随机行 走。从原点0,0 )开始，每次迭代都是由向左、向上、向右和向下 一个单位的随机步构成。当行走者返回原始点时，行走结束。在二维 世界这种情况发生的概率为1 ,而在三维世界概率小于lo请编写一个 进行100次独立随机行走程序，并计算每个方向的步数的平均数。4 )11 .表达式转换问题。请编写一个读取中缀表达式并生成后缀表达 式的程序。2)1

5、2 .表达式转换问题。请编写一个读取后缀表达式并生成中缀表达 式的程序。2)课程选修问题。学生需要修一定数量的课程才能毕业，而这些课 程会有一些必须遵循的选修顺序。假设每个学期都开所有课程，并且 学生所修课程数量不限制。给出课程和先修课程的列表，求出一个满 足最小学期数要求的时间表。以你的专业情况为背景设计。3)通过单字符置换可以将一个单词改为另一个单词。假设存在一个5 字母单词的字典。给出一个算法确定单词A是否可以通过一系列的单 字符置换转换为单词B ,并且如果可以的话，输出相应的单词序列。例 如，bleed 通过序列 bleed、blend、blond、blood 转换为 bloodo 4

6、)编写一个以行为单位的文本编辑器。内部文件的副本被保存成由 各个行组成的链表。为了能在文件中上移或下移，必须维护一个双链 表。大部分命令使用只有一个字符的字符串表示。有些是两个字符， 并且要求一个参数或者两个)。6)表一，所支持的命令行命令功能1移到顶部a在当前行之后添加文本，直到本行出现.字符d删除当前行dr num num删除若干行f name更改当前行的名称g num转到指定的行h获得帮助 1与a类似，在当前行之前添加文本行m num将当前行移到指定行数之后mr num num num将若干行作为一个整体移到指定行数之后n标记是否显示行号P打印当前行pr num num打印若干行q!退出

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

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

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

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

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

12、顾客便可 开始理发。5 若理发馆每天连续营业T分钟，求：1）一天内顾客在理发馆内的平均逗留时间；2 ）顾客排队等候理发的队列长度平均值；3 ）营业时间到点后仍需完成服务的收尾工作时间；4 ）统计每天的营业额；5 ）统计每天不同级别理发师的创收。22 .救护车调度模拟系统。问题描述：设计实现一个用事件驱动的 救护车调度离散模型，模拟120急救中心响应每个病人的呼救信 号统一调度救护车运行的情况。 5 ）对问题作适当简化，假设：某城市共有m个可能的呼救点（居民小 区、工厂、学校、公司、机关、单位等，分布着n所医院（包含在m 个点中，有k辆救护车分派在各医院待命，出现呼救病人时，由急救 中心统一指派

13、救护车接送至最近的医院救治。救护车完成一次接送任 务后即消毒，并回原处继续待命。假定呼救者与急救中心、急救中心 与救护车之间的通讯畅通无阻，也不考虑道路交通堵塞的影响。可以 用m个顶点的无向网来表示该城市的各地点和道路。时间可以分钟为 单位，路段长可表示为救护车行驶化费的分钟数。23 .稀疏矩阵的操作。基本要求4 ）:定义稀疏矩阵的数据类型描述（三元组表，完成稀疏矩阵的加、减、 乘和转置运算.要求：1界面友好，函数功能要划分好；2总体设计应画流程图；3程序要加必要的注释；4要提供程序测试方案；24 .构造可以使n个城市连接的最小生成树。问题描述:给定一个地 区的n个城市间的距离网，用Prim算

14、法或Kruskal算法建立最小生成 树,并计算得到的最小生成树的代价。4 ）要求：1 ）城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义 采用课本中给出的定义,若两个城市之间不存在道路，则将相应边的权值 设为自己定义的无穷大值.要求在屏幕上显示得到的最小生成树中包括 了哪些城市间的道路，并显示得到的最小生成树的代价。2 ）表示城市间距离网的邻接矩阵（要求至少6个城市,10条边；3 ）最小生成树中包括的边及其权值,并显示得到的最小生成树的 代价。26.长整数运算问题。设计程序，实现两个任意长的整数的加、 减、乘运算问题。4）27 .哈夫曼码的编/译码系统。编写一个哈夫曼码的编/译码系统，

15、实现对输入的文本信息自动统计并依此为依据建立一个哈夫曼码的编/ 译码系统。2）28 .集合运算问题。设计一个程序，实现两个集合的并集、交集、 差集、显示输出等，要求结果集合中的元素不重复；实现一个集合的 募集的求解。1）29 .排序算法比较问题。设计各类排序算法的程序，通过随机的数 据测试，比较各算法的关键字比较次数和关键字移动次数。2 ）30 .约瑟夫joeph ）问题。一种描述是：编号为1,2，,n的n个人 按顺时针方向围坐一圈，每人持有一个密码正整数）。一开始任选一 个正整数作为报数上限值m ,从第一个人开始按顺时针方向自1开始 顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的 m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去, 直至所有人全部出列为止。试设计一个程序求出出列顺序。2） p=/joeph ）问题。一种描述是：编号为1,2，,n的n个人按顺时针 方向围坐一圈，每人持有一个密码正整数）。一开始任选一个正整数 作为报数上限值m ,从第一个人开始按顺时针方向自1开始顺序报数, 报到m时停止报数。报m的人出列，将他的密码作为新的m值，从 他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所 有人全部出列为止。试设计一个程序求出出列顺序。2) /nlogn ) o 2 )