2016年算法与数据结构任务书

1、算法与数据结构课程设计任务书（2014级计算机科学与技术本科专业）学生姓名：学号：班级：2014级计算机科学与技术题目类型：软件工程（R）指导教师：题目简介扫雷问题。有些个人计算机会带有一个名为Minesweeper的游戏。该游戏界面是一个网 格，网格中的有些方块是雷。编写一个程序以读取文件，该文件中存放着网格中的行数、 列数以及网格本身。网格会含有一些标记为o的方块，这些就是雷。其他方块不是雷， 将会标记上问号（？）。程序的输出就是输出这个网格。雷依然会标记成o,而那些不含 雷的方块会替换成一个数字，以表明邻近雷的个数。最大数字将是8。（4）例如： TOC o 1-5 h z 5 5?o?2

2、2o211o?o?3o33o2?o?o434o4ooo?o?5oo4o2?o?63o311求素数问题。埃拉托色尼筛法（Sieve of Eratosthenes）是一种用来求所有小于N的素数 的方法。从建立一个整数2N的表着手，寻找ij）组成的数列。例如，A=0，1， 5，8，那么 D=1，3，4，5，7，8。请完成：a）编写程序，根据A构造D；b）编写程序，构造与D相对应的某一个数列A，注意A不是唯一的。（4）占用网格计算问题。考虑一个N*N的网格，其中某些方格已被占用。如果两个方格共 用公共的边，就说它们属于同一个组，如图示，一组为4个被占用的方格，3组为两个 被占用的方格，2个方格被单独

3、占用。假设格子用二维数组来表示。请编写实现下列目 的程序：1）给定组中的某个方格，计算组的大小；2）计算不同组的数目；3）列出所有的组。（4）.递归替换问题。编写程序，扩展C/C+源文件中的#include指令（以递归的方式）。请以 文件名的内容替换形如下面的代码行。#include “filename”（3）数据删除问题。编写删除具有N个数据项的数组A中所有重复项的程序，返回A中仍 有的数据项。要求运行时间在O（NlogN）。（2）随机走步问题。以下在x-y坐标系上进行的游戏属于二维的随机行走。从原点（0, 0） 开始，每次迭代都是由向左、向上、向右和向下一个单位的随机步构成。当行走者返回

4、原始点时，行走结束。在二维世界这种情况发生的概率为1，而在三维世界概率小于1。 请编写一个进行100次独立随机行走程序，并计算每个方向的步数的平均数。（4）表达式转换问题。请编写一个读取中缀表达式并生成后缀表达式的程序。（2）表达式转换问题。请编写一个读取后缀表达式并生成中缀表达式的程序。（2）课程选修问题。学生需要修一定数量的课程才能毕业，而这些课程会有一些必须遵循的 选修顺序。假设每个学期都开所有课程，并且学生所修课程数量不限制。给出课程和先 修课程的列表，求出一个满足最小学期数要求的时间表。以你的专业情况为背景设计。（3）通过单字符置换可以将一个单词改为另一个单词。假设存在一个5字母单词

5、的字典。给 出一个算法确定单词A是否可以通过一系列的单字符置换转换为单词B，并且如果可以 的话，输出相应的单词序列。例如，bleed通过序列bleed、blend、blond、blood转换为 bloodo （4）编写一个以行为单位的文本编辑器。内部文件的副本被保存成由各个行组成的链表。为 了能在文件中上移或下移，必须维护一个双链表。大部分命令使用只有一个字符的字符 串表示。有些是两个字符，并且要求一个参数（或者两个）。（6）表一，所支持的命令行命令功能l移到顶部a在当前行之后添加文本，直到本行出现,字符d删除当前行dr num num删除若干行f name更改当前行的名称g num转到指定的

6、行h获得帮助i与a类似，在当前行之前添加文本行m num将当前行移到指定行数之后mr num num num将若干行作为一个整体移到指定行数之后n标记是否显示行号p打印当前行pr num num打印若干行q!退出，并且放弃写入r name读取并且粘帖另一个文件到当前文件中t num将当前行复制到指定行数之后tr num num num将若干行复制到指定行数之后w将文件写到磁盘中x！写入后退出$转到最后一行-往上移动一行+往下移到一行=打印当前行#打印文件中的行和字符跳马问题。要求在64个国际象棋格子，任意位置放一个马，如何不重复地把格子走完。（3）八皇后问题。要求编写程序实现将八个皇后放置在国

7、际象棋棋盘的无冲突的位置上的算法，并给出所有的解。提示：在国际象棋上放置皇后时，任何一个皇后的水平、竖直 和斜45都不能有另一个皇后。解决该问题采用逐次试探的方法，即采用递归调用 putchess函数的方法。首先将第一个皇后放于第一行第一列，然后开始向下一行递归。每一步递归中，首先检测待放置位置是否与已放置的皇后冲突，如不冲突，则进行下一 行的放置，否则，选择该行的下一个位置进行检测。如整行的位置都冲突，则回到上一 行，重新选择位置。（2）猴子吃桃子问题。有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一 个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个

8、桃子。要求：1）采用数组数据结构实现上述求解；2）采用链式数据结构实现上述求解； 3）采用递归实现上述求解。（2）病人就医管理模拟问题。编写一个程序定义行医类，反映病人到医院看病，排队看医 生的情况，在病人排队过程中，主要发生两件事：（1）病人到达诊室，将病历本交给护士，排到等待队列中候诊。（2）护士从等待队列中取出一位病人的病历，该病人进入诊室就诊。要求程序采用菜单方式，其选项及功能说明如下：（1）排队-输入病人的病历号，加入到病人排队队列中（2）就诊病人排队队列中最前面的病人就诊，并将其从队列中删除。（3）查看排队-从队首到队尾列出所有的排队病人的病历号。（4） 下班退出运行。（5）图的基

9、本操作与实现。（1）自选存储结构，输入含n个顶点（用字符表示顶点）和e条边的图G；（2）求每个顶点的度，输出结果；（3）指定任意顶点x为初始顶点，对图G作DFS遍历，输出DFS顶点序列（提示:使用一个栈 实现DFS）；（4）指定任意顶点x为初始顶点，对图G作BFS遍历，输出BFS顶点序列（提示:使用一个队 列实现BFS）；（5）输入顶点x，查找图G:若存在含x的顶点，则删除该结点及与之相关连的边，并作DFS 遍历（执行操作3）；否则输出信息“无x”；（6）判断图G是否是连通图，输出信息“YES” / “NO”；（7）如果选用的存储结构是邻接矩阵,则用邻接矩阵的信息生成图G的邻接表，即复制图G，

10、 然再执行操作（2）；反之亦然。（4）散列表的设计与实现。设计散列表实现电话号码查找系统。基本要求：（2）（1）设每个记录有下列数据项：电话号码、用户名、地址；（2）从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；（3）采用双散列法解决冲突；（4）查找并显示给定电话号码的记录；（5）查找并显示给定用户名的记录。较高要求：（3）（1）系统功能的完善；（2）设计不同的散列函数，比较冲突率；（3）在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均 查找长度的变化。队列实现的仿真技术预测理发馆的经营状况。（5）问题描述：理发馆一天的工作过程如下：1）理发馆有N把理发椅，可同时

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

12、调度救护车运行的情况。（5）对问题作适当简化，假设：某城市共有m个可能的呼救点（居民小区、工厂、学校、公 司、机关、单位等），分布着n所医院（包含在m个点中），有k辆救护车分派在各医院待命， 出现呼救病人时，由急救中心统一指派救护车接送至最近的医院救治。救护车完成一次接送 任务后即消毒，并回原处继续待命。假定呼救者与急救中心、急救中心与救护车之间的通讯 畅通无阻，也不考虑道路交通堵塞的影响。可以用m个顶点的无向网来表示该城市的各地点 和道路。时间可以分钟为单位，路段长可表示为救护车行驶化费的分钟数。稀疏矩阵的操作。基本要求（4）:定义稀疏矩阵的数据类型描述（三元组表），完成稀疏矩阵的加、减、乘

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

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

15、， 每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始 按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的 m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列 为止。试设计一个程序求出出列顺序。（2）二、各题目的设计与实现要求查阅文献资料，一般在3篇以上；要求每个学生所做题目难度系数之和不小于6;建立每个题目用到的数据的逻辑结构和物理结构；完成相应算法的设计；完成程序的实现；完成测试工作，分析算法复杂度；撰写设计说明书；做好答辩工作。三、提交的成果设计说明书一份，内容包括：1）中文摘要100字；关键词3-

16、5个；2）序言；3）采用类C或C+语言定义相关的数据类型（数据结构）4）各模块流程图或伪码描述的算法5）描述函数的调用关系图6）调试分析a、调试中遇到的问题及对问题的解决方法；b、算法的时间复杂度和空间复杂度。7）测试结果8）源程序（带注释）9）设计总结、参考文献、致谢等。刻制光盘一张。四、主要参考文献1严蔚敏，吴伟民.数据结构（C语言版）.清华大学出版社.2严蔚敏，吴伟民.数据结构题集（C语言版）.清华大学出版社.3DATA STRUCTURE WITH C+. William Ford,William Topp.清华大学出版社（影 印版）.4谭浩强.c语言程序设计.清华大学出版社.5.数据结构与算法分析（Java 版），A Pr