信管软件11级数据结构课程设计

1、11级软件、信管课程设计要求：本课程设计要求在17-18周完成，课程设计题目如附件所示，共有46题，题目分配方案如下：学号1号和16、31号可做1、16、31题，2号和17、32号可做2、17、32题依此类推，每人可3选1做。信管1101、02、软件1101班19周星期一下午15:00-17:00在我办公室2501答辩（按学号来），课程设计的源程序学习委员将其汇总起来，然后一个班刻录成一个光盘答辩时给我交过来，答辩人则只需带好课程设计报告和演示程序过来。课程设计报告规范见另外一个文件，请大家重视这次课程设计，我会根据你的课程设计报告和答辩情况当时给该门课程的成绩，不再另外安排时间接收课程设计报

2、告的答辩要求，谢谢配合！（光盘名字命名为软件1101数据结构课程设计（每个同学一个文件夹，文件夹命名规则 学号+姓名+课题名） -戴成秋 2012-12-27课程设计题目：1. 运动会分数统计（难度*）任务：参加运动会有10个学校，学校编号为110。比赛分成18个男子项目，和12个女子项目。项目编号为男子118，女子1930。不同的项目取前三名积分，前三名的积分分别为：5、3、2。功能要求：1) 可以输入各个项目的前三名的成绩；2) 能统计各学校总分；3) 可以按学校编号或名称、学校总分、男女团体总分排序输出；4) 数据存入文件并能随时查询 5) 规定：输入数据形式和范围：可以输入学校的名称，

3、运动项目的名称输出形式：有中文提示，各学校分数为整型存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在java语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：测试数据及测试结果请在上交的资料中写明；2. 飞机订票系统（难度*）任务：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况

4、；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能； 3. 文章编辑（难度*）功能：从键盘输入一页文字，静态存储在一个文件中要求：（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、

5、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；4. 哈希表设计问题描述针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。基本要求假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。测试数据取读者周围较熟悉的30个人名。选作内容（1） 从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较他们的地址冲突率（可

6、以用更大的名字集合作实验）。（2） 研究这30个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发生地址冲突。（3） 在哈希函数确定的前提下尝试各种不同处理冲突的方法，考察平均查找长度的变化和造好的哈希表中关键字的聚集性。5. 宿舍管理查询软件（难度*）任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：（1）建立数据文件 ，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种)（2）实现如下查询功能: 按姓名查询 按学号查询 按房号查询（3）打印任一查询结果（可以连续操作）6. 校园导航问题（难度*）设计要求：设计你的学校的平面图，至少包括10个以

7、上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。7. 图书借阅管理系统（难度*） 主要分为两大功能：1) 图书管理(增加图书、查询图书、删除图书、图书借阅、还书)；2) 会员管理(增加会员、查询会员、删除会员、借书信息)；8. 学生成绩管理（难度*） 实现功能：输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出。9. 活期储蓄帐目管理（难度*） 活期储蓄处理中，储户开户、销户、存入、支出活动频繁，系统设计要求：1) 能比较迅速地找到储户的帐户，以实现存款、取款记账；2) 能比较简单，迅速地实现插入和删

8、除，以实现开户和销户的需要。10. 二叉排序树的实现（难度*） 用顺序和二叉链表作存储结构 1) 以回车(n)为输入结束标志,输入数列L，生成一棵二叉排序树T；2) 对二叉排序树T作中序遍历，输出结果；3) 输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；11. 最小生成树问题（难度*）设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。12. 通讯录的制作（难度*）设计目的：用数据结构中的双向链表作数据结构，结合java语言基本知识。编写一个通讯录管理系统。以把所学数据结构知识应用到实际软件开发中去。设计内容

9、：本系统应完成一下几方面的功能：1) 输入信息enter();2) 显示信息display( );3) 查找以姓名作为关键字 search( );4) 删除信息delete( );5) 存盘save ( );6) 装入load( ) ;设计要求：1) 每条信息至包含 ：姓名（NAME ）街道（STREET）城市（CITY）邮编（EIP）国家（STATE）几项2) 作为一个完整的系统，应具有友好的界面和较强的容错能力3) 上机能正常运行，并写出课程设计报告13. 哈夫曼编码/译码器（难度*）【问题描述】设计一个利用哈夫曼算法的编码系统，重复地显示并处理以下项目，直到选择退出为止。【基本要求】1)

10、 将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 2) 初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；3) 编码：利用建好的哈夫曼树生成哈夫曼编码；4) 输出编码；5) 设字符集及频度如下表：字符 空格 A B C D E F G H I J K L M频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 14. 图书管理系统（难度*）【问题描述】设计一个计算机管理系统完成图书管

11、理基本业务。【基本要求】1) 每种书的登记内容包括书号、书名、著作者、现存量和库存量；2) 对书号建立索引表（线性表）以提高查找效率；3) 系统主要功能如下：*采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；*借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；*归还：注销对借阅者的登记，改变该书的现存量。15. 走迷宫游戏（难度*）程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。要求：1) 老鼠形象可辨认，可用键盘操纵老鼠上下左右

12、移动；2) 迷宫的墙足够结实，老鼠不能穿墙而过；3) 正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败；4) 找出走出迷宫的所有路径，以及最短路径。16. 顺序结构、动态链表结构下的一元多项式加法的实现。（难度*） 设有一元多项式Am(x)和Bn(x). Am(x)=A0+A1x1+A2x2+A3x3+ +Amxm Bn(x)=B0+B1x1+B2x2+B3x3+ +Bnxn 请实现求M(x)= Am(x)+Bn(x)要求： 1) 结果M(x)中无重复阶项和无零系数项；2) 要求输出结果的升幂和降幂两种排列情况17. 利用栈求表达式的值，可供小学生作业，并能给出分数。（难度*

13、）要求：（1）判断表达式是否正确，主要是括号问题（2）题目涉及加减乘除，带括弧的混合运算18. 二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。（难度*）要求：遍历的内容应是千姿百态的。19. 敢死队问题（难度*） 有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战

14、士接着去执行任务。以此类推，直到任务完成为止。 排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。 20. 猴子吃桃子问题（难度*） 有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。 要求：1) 采用数组数据结构实现上述求解2) 采用链数据结构实现上述求解3) 采用递归实现上述求解21. 数制转换问题（难度*）将一个十进制数转换为二、八、十六进制数22. 排序综合（难度*） 利用随机函数产生N个随机整数（20000以上），对这些数进行多种

15、方法进行排序。要求：1) 至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、 起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。2) 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。23. 最小生成树求解实现（难度*）要求：1) 先任意创建一个图；2) 设计克鲁斯卡尔类，求出该图的最小生成树24. 线索二叉树的应用（难度*）要求：建立线索树。25. 稀疏矩阵应用（难度*）要求：实现三元组下的稀疏矩阵的乘法。26. 树的应用（难度*）要求：实现树与二叉树的转换的实现。27. HTML文档标记匹

16、配算法（难度*）要求：输入一段HTML代码，判断该代码是否符合HTML的语法提示：HTML文档由不同的标记划分为不同的部分与层次。与括号类似，这些标记需要成对出现，对于名为的起始标记，相应的结束标记为。常用的HTML标记：l :HTML文档l :文档标题l :文档体l :节的头部l :居中对齐l :左对齐l :段落l 。HTML语言有合理的嵌套，如 28. 语言中平衡符号的问题（难度*）要求：设java语言中包含如下符号/* */，（），编写程序检测一段java代码中富豪是否正确。29. 烫手山芋问题（难度*）一群小孩编号为1，2，n(n0)围成一圈，有一个刚出锅的山芋在他们之间传递。假设刚开

17、始由1号拿着山芋，然后依次计数把山芋交给下一个小孩，当数到某个特定的k时，拿着山芋的小孩退出游戏，然后从下一个小孩重新开始计数，如此不断，最后剩下的那个孩子就是幸运者。要求设计一个程序模拟次过程，并给出不同的n，k组合下那个幸运者是谁？30. 商场商品信息管理系统（难度*）31. 停车场管理系统（难度*）32. 编写一个基数排序算法，将一组英文单词按字典序排序（难度*）设最大的单词有n个字母33.设计程序按从大到小的次序依次输出函数f(a,b)=2*a2+b2的最小的100个函数值及相应的两个参数的值，其中a和b均为自然数。（难易度80） 要求：（1）作为函数值的存储结构应尽可能节省空间。（2

18、）所设计算法及整个程序的时间复杂度应尽可能小。34.采用十字链表表示稀疏矩阵，并实现矩阵的加法运算。（难易度90）要求：要检查有关运算的条件，并对错误的条件产生报警。 35选择合适的存储结构表示广义表，并能实现下列运算要求：（难易度95）（1）用大写字母表示广义表，用小写字母表示原子，并提供设置广义表的值的功能。（2）取广义表L的表头和表尾的函数head(L)和tail(L)。（3）能用这两个函数的复合形式求出广义表中的指定元素。（4）由广义表的字符串形式到广义表的转换函数Lists Str_ToLists_(S)；例如Str_ToLists_(“ (a,(a,b),c)”)的值为一个广义表。

19、（5）由广义表到广义表的字符串形式的转换函数char * Lists_To_Str(L)。（6）最好能设置多个广义表 。36.设计程序完成如下功能：对给定的图结构和起点，产生其所有的深度优先搜索遍历序列，并给出求解过程的动态演示。（难易度95）说明：可以使用实验工具中的有关功能。 37设计程序完成如下功能：对给定的网和起点，用PRIM算法的基本思想求解出所有的最小生成树，并给出求解过程的动态演示。（难易度95）说明：可以使用实验工具中的有关功能。 38.（马的遍历问题）：设计程序完成如下要求：在中国象棋棋盘上，对任一位置上放置的一个马，均能选择一个合适的路线，使得该棋子能按象棋的规则不重复地走

20、过棋盘上的每一位置。（难易度95）要求：（1）依次输出所走过的各位置的坐标。（2）最好能画出棋盘的图形形式，并在其上动态地标注行走过程。（3）程序能方便地地移植到其它规格的棋盘上。 39 长整数运算问题描述设计一个程序实现两个任意长的整数求和运算。基本要求利用双项循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是-（215-1）（215-1）。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。测试数据（1） 0；0；应输出“0”。（2） -2345,6789；-7654,3211；应输出“-1,0000,0000”。（3） -9999,9999；1,0

21、000,0000,0000；应输出“9999,0000,0001”。（4） 1,0001,000；-1,0001,0001；应输出“0”。（5） 1,0001,0001；-1,0001,0000；应输出“1”。实现提示（1） 每个结点中可以存放的最大整数为215-1=32767，才能保证两数相加不会溢出。但若这样存，即相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不方便。故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表视为万进制数。（2） 可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。

22、两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。选作内容修改上述程序，使它在整型量范围是-（2n-1）（2n-1）的计算机上都能有效地运行。其中，n是由程序读入的参量。输入数据的分组方法可以另行规定。40 回文判断问题描述试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是属该模式的字符序列，而+&则不是。实现提示首先，序列1进栈，然后序列1出栈并与序列2比较。测试数据由学生依据软件工程的测试技术自己确定。注意测试边界数据，如序列1和序列

23、2均为空串。41 商品货架管理问题描述商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近。上货时，需要倒货架，以保证生产日期较近的商品在较下的位置。基本要求针对一种特定商品，实现上述管理过程。实现提示用栈模拟货架和周转空间。测试数据由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空栈。42 括号匹配的检验问题描述假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（） ）或（ ）等为正确格式，（ ）或（均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列：()12345678当计算机接受了第1个括号以后

24、，他期待着与其匹配的第8个括号的出现，然而等来的却是第2个括号，此时第1个括号“”只能暂时靠边，而迫切等待与第2个括号相匹配的 第7个括号“）”的出现，类似的，因只等来了第3个括号“”，此时，其期待的紧迫程度较第2个括号更紧迫，则第2个括号只能靠边，让位于第3个括号，显然第3个括号的期待紧迫程度高于第2个括号，而第2个括号的期待紧迫程度高于第1个括号；在接受了第4个括号之后，第3个括号的期待得到了满足，消解之后，第2个括号的期待匹配就成了最急迫的任务了， ，依次类推。可见这个处理过程正好和栈的特点相吻合。基本要求读入圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法”。测试数据 输入（ （），结果“匹配”输入 （ ），结果“此串括号匹配不合法”实现提示设置一个栈，每读入一个括号，若是左括号，则作为一个新的更急迫的期待压入栈中；若是右括号，并且与当前栈顶的左括号相匹配，则将当前栈顶的左括号退出，继续读下一个括号，如果读入的右括号与当前栈顶的左括号不匹配，则属于不合法的情况。在初始和结束时，栈应该是空的。选作内容考虑增加大括号的情况。43 打印二叉树结构问题描述按凹入表形式横向打印二叉树结构，即二叉树的根在屏幕的最左边，二叉树的左子树在屏幕的下边，二叉树的右