数据结构与算法任务书-总论.doc

算法与数据结构课程设计任务书（2014级软件工程本科专业）题目类型：软件工程（R） 指导教师： 李睿 一 题目简介1. 扫雷问题。有些个人计算机会带有一个名为Minesweeper的游戏。该游戏界面是一个网格，网格中的有些方块是雷。编写一个程序以读取文件，该文件中存放着网格中的行数、列数以及网格本身。网格会含有一些标记为o的方块，这些就是雷。其他方块不是雷，将会标记上问号（？）。程序的输出就是输出这个网格。雷依然会标记成o，而那些不含雷的方块会替换成一个数字，以表明邻近雷的个数。最大数字将是8。（4）例如：1 5 52 ?o? 2 2o2113 o?o? 3 o33o24 ?o?o 4 34o4o5 oo?o? 5 oo4o26 ?o? 6 3o3112. 求素数问题。埃拉托色尼筛法（Sieve of Eratosthenes）是一种用来求所有小于N的素数的方法。从建立一个整数2N的表着手，寻找i的整数，编程实现此算法，并讨论运算时间。（1）3. 方程求解问题。方程A5+B5+C5+D5+E5=F5刚好有一个满足0ABCDEF75的整数解。请编写一个求出该解的程序。（3）4. 最短字符串问题。编写一个程序，从输入中读取字符串，并按长度顺序，最短字符串优先的原则输出它们。如果有若干字符串具有相同的长度，就按字母顺序输出它们。（3）5. 计算1的个数问题。编写递归程序，返回十进制数N的二进制表示中1的个数。（2）6. 排序重构问题。令A为一个由N个已特殊排序数组成的数列：A1，A2，AN，其中A1=0。令B为N（N-1）/2个数（定义为Bij=Ai-Aj(ij)）组成的数列。例如，A=0，1，5，8，那么D=1，3，4，5，7，8。请完成：1) 编写程序，根据A构造D；2) 编写程序，构造与D相对应的某一个数列A，注意A不是唯一的。（4）7. 占用网格计算问题。考虑一个N*N的网格，其中某些方格已被占用。如果两个方格共用公共的边，就说它们属于同一个组，如图示，一组为4个被占用的方格，3组为两个被占用的方格，2个方格被单独占用。假设格子用二维数组来表示。请编写实现下列目的程序：1) 给定组中的某个方格，计算组的大小；2) 计算不同组的数目；3）列出所有的组。（4）8. 递归替换问题。编写程序，扩展C/C+源文件中的#include指令（以递归的方式）。请以文件名的内容替换形如下面的代码行。 #include “filename” （3）9. 数据删除问题。编写删除具有N个数据项的数组A中所有重复项的程序，返回A中仍有的数据项。要求运行时间在O（NlogN）。（2）10. 随机走步问题。以下在x-y坐标系上进行的游戏属于二维的随机行走。从原点（0，0）开始，每次迭代都是由向左、向上、向右和向下一个单位的随机步构成。当行走者返回原始点时，行走结束。在二维世界这种情况发生的概率为1，而在三维世界概率小于1。请编写一个进行100次独立随机行走程序，并计算每个方向的步数的平均数。（4）11. 表达式转换问题。请编写一个读取中缀表达式并生成后缀表达式的程序。（2）12. 表达式转换问题。请编写一个读取后缀表达式并生成中缀表达式的程序。（2）13. 课程选修问题。学生需要修一定数量的课程才能毕业，而这些课程会有一些必须遵循的选修顺序。假设每个学期都开所有课程，并且学生所修课程数量不限制。给出课程和先修课程的列表，求出一个满足最小学期数要求的时间表。以你的专业情况为背景设计。（3）14. 通过单字符置换可以将一个单词改为另一个单词。假设存在一个5字母单词的字典。给出一个算法确定单词A是否可以通过一系列的单字符置换转换为单词B，并且如果可以的话，输出相应的单词序列。例如，bleed通过序列bleed、blend、blond、blood转换为blood。（4）15. 编写一个以行为单位的文本编辑器。内部文件的副本被保存成由各个行组成的链表。为了能在文件中上移或下移，必须维护一个双链表。大部分命令使用只有一个字符的字符串表示。有些是两个字符，并且要求一个参数（或者两个）。（6）表一，所支持的命令行命令功能l移到顶部a在当前行之后添加文本，直到本行出现.字符d删除当前行dr num num删除若干行f name更改当前行的名称g num转到指定的行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！写入后退出$转到最后一行-往上移动一行+往下移到一行=打印当前行#打印文件中的行和字符16. 跳马问题。要求在64个国际象棋格子,任意位置放一个马,如何不重复地把格子走完。（3）17. 八皇后问题。要求编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法，并给出所有的解。 提示：在国际象棋上放置皇后时，任何一个皇后的水平、竖直和斜45都不能有另一个皇后。解决该问题采用逐次试探的方法，即采用递归调用putchess函数的方法。首先将第一个皇后放于第一行第一列，然后开始向下一行递归。每一步递归中，首先检测待放置位置是否与已放置的皇后冲突，如不冲突，则进行下一行的放置，否则，选择该行的下一个位置进行检测。如整行的位置都冲突，则回到上一行，重新选择位置。（2）18. 猴子吃桃子问题。有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。要求：1)采用数组数据结构实现上述求解；2)采用链式数据结构实现上述求解；3)采用递归实现上述求解。（2）19. 病人就医管理模拟问题。 编写一个程序定义行医类，反映病人到医院看病，排队看医生的情况，在病人排队过程中，主要发生两件事：（1） 病人到达诊室，将病历本交给护士，排到等待队列中候诊。（2） 护士从等待队列中取出一位病人的病历，该病人进入诊室就诊。要求程序采用菜单方式，其选项及功能说明如下：（1） 排队-输入病人的病历号，加入到病人排队队列中（2） 就诊-病人排队队列中最前面的病人就诊，并将其从队列中删除。（3） 查看排队-从队首到队尾列出所有的排队病人的病历号。（4） 下班-退出运行。（5）20. 图的基本操作与实现。(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,然再执行操作(2)；反之亦然。（4）21. 散列表的设计与实现。设计散列表实现电话号码查找系统。基本要求：（2）(1)设每个记录有下列数据项：电话号码、用户名、地址；(2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；(3)采用双散列法解决冲突；(4)查找并显示给定电话号码的记录；(5) 查找并显示给定用户名的记录。较高要求：（3）(1)系统功能的完善；(2)设计不同的散列函数，比较冲突率；(3)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。22. 队列实现的仿真技术预测理发馆的经营状况。（5）问题描述：理发馆一天的工作过程如下：1) 理发馆有N把理发椅，可同时为N位顾客进行理发。2) 理发师分三个等级（一级、二级、三级），对应不同的服务收费。3) 当顾客进门时，需选择某级别理发师，只要该级别的理发师有空椅，则可立即坐下理发，否则需排队等候。4) 一旦该级别的理发师有顾客理发完离去，排在队头的顾客便可开始理发。 5) 若理发馆每天连续营业T分钟，求：（1） 一天内顾客在理发馆内的平均逗留时间；（2） 顾客排队等候理发的队列长度平均值；（3） 营业时间到点后仍需完成服务的收尾工作时间；（4） 统计每天的营业额；（5） 统计每天不同级别理发师的创收。23.救护车调度模拟系统。问题描述：设计实现一个用事件驱动的“救护车调度”离散模型，模拟120急救中心响应每个病人的呼救信号统一调度救护车运行的情况。（5）对问题作适当简化，假设：某城市共有m个可能的呼救点(居民小区、工厂、学校、公司、机关、单位等)，分布着n所医院(包含在m个点中)，有k辆救护车分派在各医院待命，出现呼救病人时，由急救中心统一指派救护车接送至最近的医院救治。救护车完成一次接送任务后即消毒，并回原处继续待命。假定呼救者与急救中心、急救中心与救护车之间的通讯畅通无阻，也不考虑道路交通堵塞的影响。可以用m个顶点的无向网来表示该城市的各地点和道路。时间可以分钟为单位，路段长可表示为救护车行驶化费的分钟数。24.稀疏矩阵的操作。基本要求（4）:定义稀疏矩阵的数据类型描述(三元组表),完成稀疏矩阵的加、减、乘和转置运算. 要求: 1) 界面友好,函数功能要划分好；2) 总体设计应画流程图；3) 程序要加必要的注释；4) 要提供程序测试方案；25. 构造可以使n个城市连接的最小生成树。问题描述:给定一个地区的n个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并计算得到的最小生成树的代价。（4）要求:1）城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本中给出的定义,若两个城市之间不存在道路,则将相应边的权值设为自己定义的无穷大值.要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路,并显示得到的最小生成树的代价。2）表示城市间距离网的邻接矩阵(要求至少6个城市,10条边)；3）最小生成树中包括的边及其权值,并显示得到的最小生成树的代价。26. 长整数运算问题。设计程序，实现两个任意长的整数的加、减、乘运算问题。（4）27. 哈夫曼码的编/译码系统。编写一个哈夫曼码的编/译码系统，实现对输入的文本信息自动统计并依此为依据建立一个哈夫曼码的编/译码系统。（2）28. 集合运算问题。设计一个程序，实现两个集合的并集、交集、差集、显示输出等，要求结果集合中的元素不重复；实现一个集合的幂集的求解。（1）29. 排序算法比较问题。设计各类排序算法的程序，通过随机的数据测试，比较各算法的关键字比较次数和关键字移动次数。（2）30. 约瑟夫（Joeph）问题。一种描述是：编号为1,2,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。（2）31. 运动会分数统计。功能要求：（5）1）可以输入各个项目的前三名或前五名的成绩；2）能统计各学校总分；3）可以按学校编号、学校总分、男女团体总分排序输出；4）可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。32. 一元稀疏多项式求解问题. 使用链式存储结构(带表头结点的单链表)和顺序存储结构存储一稀疏元多项式，主要功能有：输入并建立多项式、输出多项式、多项式a和b相加、多项式a和b相减、多项式a和b相乘等. 一元多项式的输入/输出形式为整数序列：n，c1，e1，c2，e2cn，en，其中n是多项式的项数，ci，ei分别为第i项的系数和指数。序列按指数降序排列。（3）33. 学校教师工资管理。使用链表或顺序表实现数据的录入（顺序表或链表的创建）或用文件存放教师工资信息，实现以下功能：、查找、修改、插入、追加、删除、排序、统计、输出等功能。工资基本情况包括的数据项有：职员代码、职员姓名、职务工资、基本津贴、扣公积金、扣所得税、应发总计、扣款总计、实发合计等。（5）34. 学校超市选址问题。校园平面图采用邻接矩阵（或邻接表）表示，主要功能有：校园平面图邻接矩阵（或邻接表）的建立、路径的查询、从某一点到另一景的最短路径查找、按查找出的最短路径确定超市的地址、显示输出等功能。一般情况下，校园的道路是双向通行的，可设校园平面图是一无向网，边表示路径，边上的权值存放路径长度等相关信息。（4）35.学生宿舍楼宇房间管理问题。使用链表存储相关信息，主要功能有：管辖区域的添加、查看、修改、删除、公寓楼信息的查询、统计、公寓宿舍信息的添加、修改、 汇总、统计空宿舍等。（5）36. 学生搭配问题。一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上。每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴。请设计一系统模拟动态地显示出上述过程。（1）分别用顺序存储结构和链式存储结构来实现；（2）输出每曲配对情况；（3) 计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况。至少求出K的两个值。（4）37. 学生成绩管理问题。该设计要求学生以算法与数据结构课程成绩管理为背景，设计出一个简单的能够实现成绩管理功能的系统。使用链表或顺序表实现数据的录入（顺序表或链表的创建）、查找、修改、插入、追加、删除、排序、统计、输出等功能，学生基本情况包括的数据项有：姓名、学号、名次、成绩等。（5）38. 学籍管理。设计出一个简单的能够实现成绩管理功能的系统。使用链表或顺序表实现数据的录入、浏览（对于学生记录的整体浏览和逐一浏览）、添加（可以添加任何符合记录格式的学生档案记录）、删除(可以删除数据库中任一条学生记录)、修改（可以修改其中的任一条学生数据内容）、查找（可以根据学生学号，查找某学生信息，也可以查找具有相同特征的学生的集合（比如：相同年龄、相同系别、相同籍贯、相同性别、相同专业等）、排序（如可按年龄排序）等功能。学生基本情况包括的数据项有：学号、姓名、年龄、性别、系别、专业、籍贯等。（5）39. 校园导游咨询。设计一个校园导游程序，查询任意两个景点之间的一条最短的简单路径。校园平面图采用邻接矩阵（或邻接表）表示，主要功能有：校园平面图邻接矩阵（或邻接表）的建立、路径的查询、从某一景点到另一景点的最短路径查找、游客从大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在大门旁边）、显示输出等功能。一般情况下，校园的道路是双向通行的，可设校园平面图是一无向网，网中顶点表示校内各景点，以边表示路径，边上的权值存放路径长度等相关信息。（5）40. 图书借阅管理。设计出一个简单的能够实现图书借阅管理功能的系统。使用链表或顺序表实现图书添加、图书查询、图书资料删除、借书、还书、增加会员、查询会员、删除会员、查询会员借书信息、输出显示等功能。图书的结构体包括的数据项有：图书编号、书名、书的价格、借阅人、判断书是否存在或者已经借出的数据项（1存在,0借出）等；会员的结构包括的数据项有：会员的姓名、会员的性别、会员的年龄、等。（5）41. 通讯录。设计、开发出一个简单的通讯录。使用链式存储结构或顺序存储结构实现数据的输入（顺序表或链表的创建）、显示、查找（以姓名为关键字）、修改、插入、追加、删除、排序、输出等功能；通讯簿基本情况包括的数据项有：姓名、电话号码、住址等。（3）42. 停车场管理。（4）设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列 (大门在最南端，最先到达的第一辆车停放在车场的最北端)，若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入;当停车场内某辆车要离开时，在它之后开入的车辆必须退出车场为它让路，待该辆车开出大门外，其它车辆按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。该设计要求为停车场编制按上述要求进行管理的模拟程序。（1）使用顺序栈模拟停车场，链队列模拟车场外的便道，实现车辆入栈、出栈、入队列、出队列、信息输出等功能；（2）至少要用10辆各种车型的车作为测试数据，每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，A表示到达；D表示离去，E表示输入结束。例：设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）。算法对于这些合法的输入数据都能产生满足规格说明要求的结果；（3）车辆信息有：车牌号、到达信息、到达时刻、离去信息、离去时刻等；输出的信息有：如果是到达的车辆，输出其在停车场中或便道上的位置；如果是离去的车辆，则输出其在停车场中停留的时间和应交的费用；43. 商店存货管理。建立一商店存货管理系统。使用链表存储商品的相关信息。主要功能有：商品信息的输入、输出、插入、删除、追加、查找、保存等，要求每次出货时取进货时间最早且最接近保质期中止时间的货物。（5）44. 人事管理。设计出一个简单的能够实现人事管理功能的系统。使用链表或顺序表实现员工各种信息的输入（包括员工基本信息、学历信息等）；浏览（对于员工基本信息、学历信息的整体浏览和逐一浏览）；员工各种信息的修改（可以修改其中的任一条学生数据内容）；插入；删除；按照某种条件，查询统计符合条件的员工信息；并将相应结果输出等功能；员工基本情况包括的数据项有：员工号、员工姓名、性别、所在部门、职称、身份证号等；员工学历信息包括的数据项有：员工号、员工姓名、学历、专业、毕业时间、毕业学校等。（5）45. 迷宫问题。对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。用二维数组表示迷宫数据，主要功能是对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论：求得的通路以二元组( i , j )的形式输出，其中（i, j）指示迷宫中的一个坐标；迷宫应随机生成，但要保证迷宫最外围必须是不通的，假设用1表示。（3）46. 兰州道路交通网络信息查询。设计一个简单的能够实现兰州道路交通网络信息查询功能的系统。兰州道路交通网采用邻接矩阵（或邻接表）表示，包括道路交通网邻接矩阵（或邻接表）的建立、路径（或时间）的查询、最短路径（或最短时间）的查找、显示输出等功能；兰州道路交通网中顶点表示地名、图上的弧表示两地之间有路径存在、弧上的权值表示两地之间的距离（或时间）。（5）47. 教学计划编制问题。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。基本要求：1)输入参数：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串，规定从C01C12)、学分和直接先修课的课程号；2)输出参数：输出提示信息，由用户在键盘上输入运行程序中规定的命令来指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中；3)若根据给定的条件问题无解，则报告适当的信息，否则将教学计划输出到用户指定的文件中。（5）48. 个人帐簿管理。设计程序，实现个人帐簿管理，此系统记录某人每月的全部收入及各项开支情况，包括食品消费，房租，子女教育费用，水电费，医疗费，储蓄等。进入系统后可以输入和修改某月的收支情况，可以对每月的开支从小到大进行排序，可以根据输入的月份查询每月的收支情况等。使用链表和顺序表分别存储个人帐簿的相关信息（包括：食品消费，房租，子女教育费用，水电费，医疗费，储蓄等），主要功能有：库存货品信息的输入、输出、插入、删除、查找、排序（按每月的开支从小到大进行）等。（5）49. 敢死队问题。（4）有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。至少采用两种不同的数据结构来实现以完成任务；排长不愿意去，假设排长为1号，请设计程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。50. 二叉树操作。设计程序，实现二叉树的相关操作。分别使用二叉链表和三叉链表存储二叉树，主要功能有：已知二叉树的前序、中序序列，恢复此二叉树；求二叉树高度、分支结点数和叶子结点数；插入结点到指定位置、删除指定结点；将二叉树中所有结点的左右子树交换；对二叉树进行层序、非递归中序遍历等。假设二叉树中的数据元素为整数，输入时以回车符作为结束标志。(3)51. 二叉排序树问题。设计程序，实现二叉排序树的相关操作。使用二叉链表存储二叉排序树，主要功能有：生成一棵二叉排序树T；计算二叉排序树T的平均查找长度，输出结果；插入元素x，重新计算二叉排序树T的平均查找长度以及统计各结点所在的层次；输入元素x，查找二叉排序树T：若存在含x的结点，则删除该结点；否则输出信息“无x”；判断二叉排序树T是否为平衡二叉树；遍历二叉排序树等；假设二叉排序树中的数据元素为整数，输入时以回车符作为结束标志。（4）52. 仓库产品管理。设计程序，设计一个库存货品信息管理系统软件，使用链表或顺序表存储产品信息（产品信息包括产品名称、入库时间、库存总量、产品入库价格、货品种类等）。系统的基本功能：1) 产品入库功能：可在界面中方便地输入产品信息包括产品名称、入库时间、库存总量、产品入库价格、货品种类等，需要判断是新产品还是原有商品做不同的操作。2) 产品出库功能：通过修改产品的库存总量实现。3) 库存管理功能：能自动按照产品分类，生成每类产品的库存数量。4) 查询功能：可根据产品名称或入库时间两种条件来查询相应的产品信息。提醒功能：如果产品库存低于设定的最低限额，自动发出提醒管理员补货的通知。（5）53. 宾馆客房