东北大学秦皇岛分校2022级数据结构课程设计任务书-2班题目.docx

《东北大学秦皇岛分校2022级数据结构课程设计任务书-2班题目.docx》由会员分享，可在线阅读，更多相关《东北大学秦皇岛分校2022级数据结构课程设计任务书-2班题目.docx（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、东北大学秦皇岛分校2022级数据结构课程设计任务书-2班题目 34. 教学计划编制问题 设计要求：针对计算机系本科课程，根据课程之间的依赖关系（如离散数学应在数据结构之前开设）制定课程安排计划，并满足各学期课程数目大致相同。 35. 散列法的实验研究 散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型的散列函数构造方法，做实验观察，不同的解决冲突方法对查询性能的影响。 36. 括号匹配的检验 问题描述 假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（） ）或（ ）等为正确格式，（）或（均为不正确的格

2、式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列： () 12345678 当计算机接受了第1个括号以后，他期待着与其匹配的第8个括号的出现，然而等来的却是第2个括号，此时第1个括号“”只能暂时靠边，而迫切等待与第2个括号相匹配的第7个括号“）”的出现，类似的，因只等来了第3个括号“”，此时，其期待的紧迫程度较第2个括号更紧迫，则第2个括号只能靠边，让位于第3个括号，显然第3个括号的期待紧迫程度高于第2个括号，而第2个括号的期待紧迫程度高于第1个括号；在接受了第4个括号之后，第3个括号的期待得到了满足，消解之后，第2个括号的期待匹配就成了最急迫的任务了，

3、 ，依次类推。可见这个处理过程正好和栈的特点相吻合。 基本要求 读入圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法”。 测试数据 输入（ （），结果“匹配” 输入（），结果“此串括号匹配不合法” 实现提示 设置一个栈，每读入一个括号，若是左括号，则作为一个新的更急迫的期待压入栈中；若是右括号，并且与当前栈顶的左括号相匹配，则将当前栈顶的左括号退出，继续读下一个括号，如果读入的右括号与当前栈顶的左括号不匹配，则属于不合法的情况。在初始和结束时，栈应该是空的。 选作内容 考虑增加大括号的情况。 37. 哈夫曼编码/译码系统（树应用） 问题描述 利用哈夫曼编码进行通信，可以压缩通信的数

4、据量，提高传输效率，缩短信息的传输时间，还有一定的保密性。现在要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。 实现提示 在本例中设置发送者和接受者两个功能， 发送者的功能包括： 输入待传送的字符信息； 统计字符信息中出现的字符种类数和各字符出现的次数（频率）； 根据字符的种类数和各自出现的次数建立哈夫曼树； 利用以上哈夫曼树求出各字符的哈夫曼编码； 将字符信息转换成对应的编码信息进行传送。 接受者的功能包括： 接收发送者传送来的编码信息； 利用上述哈夫曼树对编码信息进行翻译，即将编码信息还原成发送前

5、的字符信息。 从以上分析可发现，在本例中的主要算法有三个： （1）哈夫曼树的建立； （2）哈夫曼编码的生成； （3）对编码信息的翻译。 38. 活期储蓄帐目管理 活期储蓄处理中，储户开户、销户、存入、支出活动频繁，系统设计要求： 1) 能比较迅速地找到储户的帐户，以实现存款、取款记账； 2) 能比较简单，迅速地实现插入和删除，以实现开户和销户的需要。 39. 二叉排序树的实现 用顺序和二叉链表作存储结构，完成学生成绩管理 1) 以回车(n)为输入结束标志,输入数列L，生成一棵二叉排序树T； 2) 对二叉排序树T作中序遍历，输出结果； 3) 输入元素x,查找二叉排序树T,若存在含x的结点,则删除

6、该结点,并作中序遍历(执行操作2)；否则输出信息“无x”； 40. 最小生成树问题 设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 41. 通讯录的制作 设计目的：用数据结构中的双向链表作数据结构，结合C语言基本知识。编写一个通讯录管理系统。以把所学数据结构知识应用到实际软件开发中去。 设计内容：本系统应完成一下几方面的功能： 1) 输入信息enter(); 2) 显示信息display( ); 3) 查找以姓名作为关键字search( ); 4) 删除信息delete( ); 5) 存盘save ( ); 6) 装入load( ) ;

7、 设计要求： 1) 每条信息至包含：姓名（NAME ）街道（STREET）城市（CITY）邮编（EIP）国家（STATE）几项 2) 作为一个完整的系统，应具有友好的界面和较强的容错能力 3) 上机能正常运行，并写出课程设计报告 42. 长途电话区号编码/译码器 设计一个利用哈夫曼算法的编码和译码系统，长途电话区号编码/译码器。 1) 将权值数据(根据人口决定)存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 2) 分别采用动态和静态存储结构 3) 初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树； 4) 编码：利用建好的哈夫曼树生成哈夫曼编码； 5) 输出编

8、码； 1) 译码功能； 2) 显示哈夫曼树； 3) 界面设计的优化。 43. 散列表的设计与实现 设计散列表实现电话号码查找系统。 1) 设每个记录有下列数据项：电话号码、用户名、地址； 2) 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表； 3) 采用一定的方法解决冲突； 4) 查找并显示给定电话号码的记录； 5) 查找并显示给定用户名的记录。 1) 系统功能的完善； 2) 设计不同的散列函数，比较冲突率； 3) 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。 44. 走迷宫游戏 程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有

9、一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。 要求： 1) 老鼠形象可辨认，可用键盘操纵老鼠上下左右移动； 2) 迷宫的墙足够结实，老鼠不能穿墙而过； 3) 正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败； 4) 添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙； 5) 找出走出迷宫的所有路径，以及最短路径。 利用序列化功能实现迷宫地图文件的存盘和读出等功能 45. 顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。 设有一元多项式Am(x)和Bn(x). Am(x)=A0+A1x1+A2x2+A3x3+ +Amxm Bn

10、(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) 要求输出结果的升幂和降幂两种排列情况 45. 利用栈求表达式的值 要求：建立试题库文件，随机产生n个题目；题目涉及加减乘除，带括弧的混合运算；随时可以退出；保留历史分数，能回顾历史，给出与历史分数比较后的评价，可供小学生作业，并能给出分数。 46. 简易文本编辑器 要求： 1) 具有图形菜单界面

11、； 2) 查找，替换（等长，不等长），插入（插串，文本块的插入）、块移动（行块，列块移动），删除 3) 可正确存盘、取盘； 4) 正确显示总行数。 47. 二叉树的算法 二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。 要求：遍历的内容应是多样的。 48. 学生搭配问题 一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴. 请设计一系统模拟动态地显示出上述过程,要求如下: 1) 输出每曲配对情况 2) 计算出任何一

12、个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.至少求出K的两个值. 3) 尽量设计出多种算法及程序,可视情况适当加分 提示:用队列来解决比较方便. 49. 敢死队问题 有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。 排长是不愿意去的，假设排长为

13、1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。 要求：至少采用两种不同的数据结构的方法实现。如果采用三种以上的方法者，可加分。 50. 猴子吃桃子问题 有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。 要求： 1) 采用数组数据结构实现上述求解 2) 采用链数据结构实现上述求解 3) 采用递归实现上述求解 4) 如果采用4种方法者,适当加分 51. 数制转换问题 任意给定一个M进制的数x ，请实现如下要求 1) 求出此数x的10进制值（用MD表示） 2) 实现对

14、x向任意的一个非M进制的数的转换。 3) 至少用两种或两种以上的方法实现上述要求（用栈解决，用数组解决，其它方法解决）。 52. 学生成绩管理系统 现有学生成绩信息文件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 .

15、 . . . 试编写一管理系统,要求如下: 1) 实现对两个文件数据进行合并,生成新文件3.txt 2) 抽取出三科成绩中有补考的学生并保存在一个新文件4.txt 3) 对合并后的文件3.txt中的数据按总分降序排序(至少采用两种排序方法实现) 4) 输入一个学生姓名后,能查找到此学生的信息并输出结果(至少采用两种查找方法实现) 5) 要求使用结构体,链或数组等实现上述要求. 6) 采用多种方法且算法正确者,可适当加分. 53. 图的遍历和生成树求解实现 要求： 1) 先任意创建一个图； 2) 图的DFS,BFS的递归和非递归算法的实现 3) 最小生成树（两个算法）的实现，求连通分量的实现 4

16、) 要求用邻接矩阵、邻接表、十字链表多种结构存储实现 54. 线索二叉树的应用 要求：实现线索树建立、插入、删除、恢复线索的实现。 55. 稀疏矩阵应用 要求：实现三元组，十字链表下的稀疏矩阵的加、转、乘的实现。 56. 交通咨询系统中的最短路径 建立交通图的存储结构、解决单源最短路径问题、再实现两个地点最短路径问题 57.长整数四则运算。 问题描述：设计一个实现任意长的整数进行加法运算的演示程序。 基本要求：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是-(215 - 1) (215 - 1)。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号

17、隔开。 测试数据： （1）0；0；应输出“0”。 （2）-2345,6789；-7654,3211；应输出“-1,0000,0000”。 （3）-9999,9999；1,0000,0000,0000；应输出“9999,0000,0001”。 （4）1,0001,0001；-1,0001,0001；应输出“0”。 （5）1,0001,0001；-1,0001,0000；应输出“1”。 （6）-9999,9999,9999；-9999,9999,9999；应输出“1,9999,9999,9998”。 （7）1,0000,9999,9999；1；应输出“1,0001,0000,0000”。 实现提示

18、： （1）每个结点中可以存放的最大整数为32767，才能保证两数相加不会溢出，但若这样存放，即相当于按32768进制存放，在十进制与32768进制数之间的转换十分不方便，故可以在每个结点中仅存十进制的4位，即不超过9999的非负整数，整个链表表示为万进制。（2）可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。 58.集合的交、并、差运算 问题描述：编制一个能演示执行集合的交、并和差运算的程序。 基本要求：集合元素用小写英文字母，执行各种操作应以对话方式执行

19、。 算法要点：利用单链表表示集合；理解好三种运算的含义 59.文字研究助手问题 问题描述：文字研究人员需要统计某篇英文小说中某些特定单词的出现次数和位置，试写出一个实现这一目标的文字统计系统。这称为“文学研究助手”。 算法输入：文本文件和词集。 算法输出：单词出现的次数，出现位置所在行的行号（同一行出现两次的只输出一个行号）。算法要点：（1）文本串非空且以文件形式存放。 （2）单词定义：用字母组成的字符序列，中间不含空格，不区分大小写。 （3）待统计的单词不跨行出现，它或者从行首开始，或者前置一个空格。 （4）数据结构采用二维链表，单词结点链接成一个链表，每个单词的行号组成一个链表，单词结点作

20、为行号链表的头结点。 60 关键路径算法 问题描述 AOE网(即边表示活动的网络)，在某些工程估算方面非常有用。它可以使人们了解：（1）研究某个工程至少需要多少时间？（2）哪些活动是影响工程进度的关键? 在AOE网络中，从源点到汇点的有向路径可能不止一条，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和，这条路径就叫做关键路径（critical path）。 设计步骤 1 以某一工程为蓝本，采用图的结构表示实际的工程计划时间。 2 调查并分析和预测这个工程计划每个阶段的时间。 3 用调查的结果

21、建立AOE网，并用图的形式表示。 4 用CreateGraphic ()函数建立图的邻接表存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中。 5 用SearchMaxPath()函数求出最大路径，并打印出关键路径。 6 编写代码并调试、测试通过。 测试数据 利用教材p185的图7.30（a）中的数据调试程序。 实现提示 实现的关键和难点在于对四个术语的理解和应用即：ei表示顶点vi所代表的事件的最早发生时间；li表示顶点vi所代表的事件的最迟发生时间；Tes(i,j)表示活动ak的最早开工时间；Tls(i,j)表示活动ak的最迟开工时间。活动ak为关键活动的充分必要条件是活动ak的

22、最早开工时间与它的最迟开工时间相等。 61. 表达式求值 问题描述 当用户输入一个合法的算术表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号；能够计算的操作数要求在实数范围内；对于异常表达式能给出错误提示。 设计步骤 1首先置操作数栈为空栈，表达式起始符为运算符栈的栈底元素； 2依次扫描表达式中每个字符，若是操作数则进OPND栈；若是运算符，则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。 3先做一个适合个位的+-*/运算, 其次就要考虑到对n位和小数点的运算。 测试数据 （1）请输入您所求的表达式 3*(7-2)+5 多项式的结果是: 20

23、（2）请输入您所求的表达式 3.154*(12+18)-23 多项式的结果是: 71.62 实现提示 可以参考教材p53的算法3.4的描述。 62.舞伴问题 假定在一舞会上，男士排成一队，女士排成一队。跳舞开始时，依次从男队和女队的队头各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。设计要求：模拟上述舞伴系统，并能计算对于任何男士A和女士B在哪一轮舞曲中的k次跳舞？ 63.平衡二元树的判定 设计要求：给定一个二元树的先序遍历或后序遍历结果，判定其是否为平衡二元树。 64. 停车场管理系统 设计一个停车场管理系统，模拟停车场的运作，通过此程序具备以下功能： 1、要

24、求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理； 2、要求处理的数据元素包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻； 3、该系统完成以下功能：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）； 4、要求栈以顺序结构实现，队列以链表实现。 65.航空客运订票系统。 每条航线所涉及的信息有：终点站名、航班号、飞机号、飞机周日（星期几）、乘员定额、余票量、订定票的客户名单（包括姓名、订票量、舱位等级1，2或3）以及等候替补的客户名单（包括姓名、

25、所需数量）。 系统能实现的操作和功能如下： 查询航线：根据客户提出的终点站名输出如下信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票额； 承办订票业务：根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若有余票，则为客户办理订票手续，输出座位号；若已满员或余票少余订票额，则需重新询问客户要求。若需要，可登记排队候补； 承办退票业务：根据客户提出的情况（日期、航班号），为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其它排队候补的客户。 实现提示：两个客户名单可分别由线性表和队列实现。为查找方便，已订票客户的线性表应按客户姓名有序，并且，为了插入和删除方便，应以链表作为存储结构。由于预约人数无法预计，队列也应以链表作为存储结构。