数据结构课程设计指导

1、数据结构课程设计指导数据结构课程设计指导一、设计目的一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、设计要求二、设计要求在本课程设计过程中要求：（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩。（3）认真编写课程设计报告。课程设计报告的书写格式及要求见附录 2。三、设计步骤三、设计步骤1、 问题分析和任务定义；2、 数据类型和系统设计；3、 编码实现

2、和静态检查；4、 上机调试；5、总结和整理课程设计报告。四、考核方式和成绩评定四、考核方式和成绩评定考核分为两个部分：程序运行情况：按规定时间到机房运行程序，由老师检查运行情况。学生能对自己的程序面对教师提问并能熟练地解释清楚。实验报告：是否按规定书写实验报告的各项内容。课程设计成绩采用五级分制。100%=上机检查（50%）+课程设计报告（50%）五、上交相关内容要求五、上交相关内容要求上交的成果的内容必须由以下四个部分组成，缺一不可1 上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中） ；2 上交程序的说明文件：（保存在.doc 中）在说明文档中应该写明上交程序

3、所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明；3 课程设计报告：（保存在 word 文档中，文件名要求 按照姓名-学号-课程设计报告起名，如文件名为张三-101-课程设计报告.doc ）按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成；1、需求分析、需求分析1 程序的功能；2 输入输出的要求；3 测试数据。2、概要设计、概要设计包括程序设计组成框图，程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义） 。3、详细设计、详细设计包括模块功能说明（如函数功能、入口及出口参数说明，函数调用关系描述等） ，每个模块的算法设计说明（

4、可以是描述算法的流程图） 。源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。4、调试分析、调试分析测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？） ，算法的改进设想。5、核心源程序清单和执行结果、核心源程序清单和执行结果源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。附录 1 数据结构课程设计的具体内容本次课程设计完成如下模块（共 36 个模块，抽签决定自己所做题目的序号）1、一元多项式乘法、一元多项式乘法1) 问题描述问题描述已知 a

5、(x)=a0+a1x+a2x2+anxn和 b(x)=b0+b1x+b2x2+bmxm，并且在 a(x)和 b(x)中指数相差很多，求 a(x)=a(x)*b(x)。2) 基本要求基本要求(1)设计存储结构表示一元多项式；(2)设计算法实现一元多项式乘法；(3)分析算法的时间复杂度和空间复杂度。2、 迷宫问题迷宫问题1)问题描述问题描述迷宫求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。例如，图 2 所示为一个迷宫示意图，其中双边

6、矩形表示迷宫，1代表有障碍，0 代表无障碍。2) 基本要求基本要求(1) 设计数据结构存储迷宫；(2) 设计存储结构保存从入口到出口的通路；(3) 设计算法完成迷宫问题的求解；(4) 分析算法的时间复杂度。3) 设计思想设计思想可以采用回溯法实现该问题的求解。回溯法是一种不断试探及时纠正错误的搜索方法。从入口出发，按某一方向向前探索，若能走通（未走过的） ，即某处可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都搜索到，0123456789011111111111101110111121101011111310100

7、0001141011101111511001100016101100110171111111111入口(1, 1)出口(6, 8) 图 2 迷宫示意图，其中 1 代表有障碍，0 代表无障碍前进的方向有八个，分别是上、下、左、右、左上、左下、右上、右下或找到一条通路，或无路可走又返回到入口点。在求解过程中，为了保证在任何位置上都能沿原路退回，需要一个后进先出的栈来保存从入口到当前位置的路径。可以将迷宫定义成一个二维数组，则每个点有 8 个试探方向，如当前点的坐标是(x, y)，与其相邻的 8个点的坐标都可根据与该点的相邻方位而得到，规定试探顺序为顺时针方向，将这 8 个方向的坐标增量放在一个结构

8、数组 move8中，在 move 数组中，每个元素由两个域组成：x 表示横坐标增量，y 表示纵坐标增量。这样会很方便地求出从某点(x，y)按某一方向 v (0v7) 到达新点（i，j）的坐标：i=x+movev.x ； j=y+movev.y。算法用伪代码描述如下：1. 栈初始化；2. 将入口点坐标(x , y)及该点的方向 d（设为-1）入栈；3. 当栈不空时循环执行下述操作：3.1 (x , y , d)容忍值，则在 j 处放置放大器; 2.2 否则 d(i) = maxd(i)，d(j) +d(j) ;【思考题思考题】本题假设分布网络是一棵二叉树结构，如果是树结构应如何设计算法？5、哈夫

9、曼编码、哈夫曼编码1) 问题描述问题描述设某编码系统共有 n 个字符，使用频率分别为w1, w2, , wn，设计一个不等长的编码方案，使得该编码系统的空间效率最好。2) 基本要求基本要求(1) 设计数据结构；(2) 设计编码算法；(3) 分析时间复杂度和空间复杂度。3) 设计思想设计思想 利用 huffman 编码树求得最佳的编码方案。根据哈夫曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个结构型的一维数组 hufftree，保存哈夫曼树中各结点的信息，每个结点包括：权值、左孩子、右孩子、双亲，如图 6 所示。由于哈夫曼树中共有 2n-1 个结点，并且进行 n-1 次合并操作，所以该数组的长

10、度为 2n-1。 构造哈夫曼树的伪代码如下：1. 数组 hufftree 初始化，所有元素结点的双亲、左右孩子都置为-1； 2. 数组 hufftree 的前 n 个元素的权值置给定权值 wn； 3. 进行 n-1 次合并 3.1 在二叉树集合中选取两个权值最小的根结点，其下标分别为 i1, i2； 3.2 将二叉树 i1、i2 合并为一棵新的二叉树 k； 在哈夫曼树中，设左分支为 0，右分支为 1，从根结点出发，遍历整棵哈夫曼树，求得各个叶子结点所表示字符的哈夫曼编码。【思考题思考题】对于采用哈夫曼编码树进行的编码，如何设计解码算法？6、tsp 问题问题1) 问题描述问题描述所谓 tsp 问

11、题是指旅行家要旅行 n 个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。2) 基本要求基本要求(1) 上网查找 tsp 问题的应用实例；(2) 分析求 tsp 问题的全局最优解的时间复杂度；(3) 设计一个求近似解的算法；(4) 分析算法的时间复杂度。3) 设计思想设计思想对于 tsp 问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅行路线，从中选择最佳的一条。但是用穷举法求解 tsp 问题的时间复杂度为(n!)，当 n 大到一定程度后是不可解的。本实验只要求近似解，可以采用贪心法

12、求解：任意选择某个城市作为出发点，然后前往最近的未访问的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。为便于查找离某顶点最近的邻接点，可以采用邻接矩阵存储该图。算法用伪代码描述如下：1. 任意选择某个顶点 v 作为出发点； 2. 执行下述过程，直到所有顶点都被访问： 2.1 v=最后一个被访问的顶点； 2.2 在顶点 v 的邻接点中查找距离顶点 v 最近的未被访问的邻接点 j； 2.2 访问顶点 j； 3. 从最后一个访问的顶点直接回到出发点 v；weight lchild rchild parent 图 6 哈夫曼树的结点结构【思考题思考题】上网查找 tsp 问题的应用实例

13、，写一篇综述报告。7、医院选址问题、医院选址问题1)问题描述问题描述n 个村庄之间的交通图可以用有向网图来表示，图中边上的权值表示从村庄 i 到村庄 j 的道路长度。现在要从这 n 个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？2) 基本要求基本要求(1) 建立模型，设计存储结构；(2) 设计算法完成问题求解；(3) 分析算法的时间复杂度。3) 设计思想设计思想医院选址问题实际是求有向图中心点的问题。首先定义顶点的偏心度。设图 g=（v，e） ，对任一顶点 k，称 e(k)=maxd(i, k)（iv）为顶点 k 的偏心度。显然，偏心度最小的顶点即

14、为图 g 的中心点。如图 7(a)所示是一个带权有向图，其各顶点的偏心度如图(b)所示。医院选址问题的算法用伪代码描述如下：1对加权有向图，调用 floyd 算法，求每对顶点间最短路径长度的矩阵；2对最短路径长度矩阵的每列求大值，即得到各顶点的偏心度；3具有最小偏心度的顶点即为所求。【思考题思考题】图的存储结构和算法的设计需要一定的灵活性和技巧。从医院选址问题的求解过程，你有什么感想？8、简单个人电话号码查询系统简单个人电话号码查询系统1) 问题描述问题描述人们在日常生活中经常需要查找某个人或某个单位的电话号码，本实验将实现一个简单的个人电话号码查询系统，根据用户输入的信息（例如姓名等）进行快

15、速查询。abcde1253214顶点偏心度a b 6b 8d 5e 7 (a) (b) 图 7 带权有向图及各顶点的偏心度2) 基本要求基本要求(1) 在外存上，用文件保存电话号码信息；(2) 在内存中，设计数据结构存储电话号码信息；(3) 提供查询功能：根据姓名实现快速查询；(4) 提供其他维护功能：例如插入、删除、修改等；(5) 按电话号码进行排序。3) 设计思想设计思想 由于需要管理的电话号码信息较多，而且要在程序运行结束后仍然保存电话号码信息，所以电话号码信息采用文件的形式存放到外存中。在系统运行时，需要将电话号码信息从文件调入内存来进行查找等操作，为了接收文件中的内容，要有一个数据结

16、构与之对应，可以设计如下结构类型的数组来接收数据： const int max=10; struct telenumber string name; /姓名 string phonenumber; /固定电话号码 string mobilenumber; /移动电话号码 string email; /电子邮箱 telemax;为了实现对电话号码的快速查询，可以将上述结构数组排序，以便应用折半查找，但是，在数组中实现插入和删除操作的代价较高。如果记录需频繁进行插入或删除操作，可以考虑采用二叉排序树组织电话号码信息，则查找和维护都能获得较高的时间性能。更复杂地，需要考虑该二叉排序树是否平衡，如何使

17、之达到平衡。9、各种排序算法时间性能的比较、各种排序算法时间性能的比较1) 问题描述问题描述 对各种排序方法（直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排序）的时间性能进行比较。2) 基本要求基本要求(1) 设计并实现上述各种排序算法；(2) 产生正序和逆序的初始排列分别调用上述排序算法，并比较时间性能；(3) 产生随机的初始排列分别调用上述排序算法，并比较时间性能。3) 设计思想设计思想上述各种排序方法都是基于比较的内排序，其时间主要消耗在排序过程中进行的记录的比较次数和移动次数，因此，统计在相同数据状态下不同排序算法的比较次数和移动次数，即可实现比较各种排序算法

18、的目的。直接插入排序、起泡排序、直接选择排序在教材中已经实现，请仿照教材中的方法在其他排序算法中的适当位置插入计数器统计元素的比较次数和移动次数。【思考题思考题】如果测算每种排序算法所用实际的时间，应如何修改排序算法？10、机器调度问题、机器调度问题1)问题描述问题描述机器调度是指有 m 台机器需要处理 n 个作业，设作业 i 的处理时间为 ti，则对 n 个作业进行机器分配，使得：(1) 一台机器在同一时间内只能处理一个作业；(2) 一个作业不能同时在两台机器上处理；(3) 作业 i 一旦运行，则需要 ti个连续时间单位。设计算法进行合理调度，使得在 m 台机器上处理 n 个作业所需要的处理

19、时间最短。2) 基本要求基本要求(1) 建立问题模型，设计数据结构；(2) 设计调度算法，为每个作业分配一台可用机器；(3) 给出分配方案。3) 设计思想设计思想假设有七个作业，所需时间分别为2, 14, 4, 16, 6, 5, 3，有三台机器，编号分别为 m1、m2和 m3。这七个作业在三台机器上进行调度的情形如图 9 所示，阴影区代表作业的运行区间。作业 4 在 0 到 16 时间被调度到机器 1 上运行，在这 16 个时间单位中，机器 1 完成了对作业 4 的处理；作业 2 在 0 到 14 时间被调度到机器 2 上处理，之后机器 2 在 14 到 17 时间处理作业 7；在机器 3

20、上，作业 5 在 06 时间完成，作业6 在 611 时间完成，作业 3 在 1115 时间完成，作业 1 在 1517 时间完成。注意到作业 i 只能在一台机器上从 si时刻到 si +ti时间完成且任何机器在同一时刻仅能处理一个作业，因此最短调度长度为 17。 在上述处理中，采用了最长时间优先（lpt）的简单调度策略。在 lpt 算法中，作业按其所需时间的递减顺序排列，在分配一个作业时，将其分配给最先变为空闲的机器。m1m2m3时间分配 作业作业 5作业作业 6 作业作业 3 作业作业 1作业作业 2 作业作业 7 作业作业 41716图 9 三台机器的调度示例654 下面设计完成下面设计

21、完成 lpt 算法的存储结构。算法的存储结构。 为每个机器设计数据类型： struct machinenode int id; /机器号int avail; /机器可用时刻 ; 为每个作业设计数据类型： struct jobnode int id; /作业号int time; /处理时间 ;lpt 算法用伪代码描述如下：1. 如果作业数 n机器数 m，则 1.1 将作业 i 分配到机器 i 上； 1.2 最短调度长度等于 n 个作业中处理时间最大值；2. 否则，重复执行以下操作，直到 n 个作业都被分配： 2.1 将 n 个作业按处理时间建成一个大根堆 h1； 2.2 将 m 个机器按可用时刻

22、建立一个小根堆 h2； 2.3 将堆 h1 的堆顶作业分配给堆 h2 的堆顶机器； 2.4 将 h2 的堆顶机器加上 h1 的堆顶作业的处理时间重新插入 h2 中； 2.5 将堆 h1 的堆顶元素删除；3. 堆 h2 的堆顶元素就是最短调度时间；11、 运动会分数统计运动会分数统计1)问题描述问题描述参加运动会有 n 个学校，学校编号为 1n。比赛分成 m 个男子项目，和 w 个女子项目。项目编号为男子 1m，女子 m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）2

23、)2) 基本要求基本要求(1)可以输入各个项目的前三名或前五名的成绩；(2)能统计各学校总分，(3)可以按学校编号、学校总分、男女团体总分排序输出；(4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 规定：输入数据形式和范围：20 以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整型界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在 c 语言程序设计的书上，请自

24、学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用 1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；12、 订票系统订票系统1)问题描述问题描述通过此系统可以实现如下功能：(1)录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）(2)查询： 可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓） ；可以输入起飞抵达城市，查询飞机航班情况；(3)订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经

25、无票，可以提供相关可选择航班；(4)退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。(5)修改航班信息：当航班信息改变可以修改航班数据文件2) 基本要求基本要求根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能。 13、 文章编辑文章编辑1)1)问题描述问题描述输入一页文字，程序可以统计出文字、数字、空格的个数。2)2) 基本要求基本要求静态存储一页文章，每行最多不超过 80 个字符，共 n 行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串

26、，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分 4 行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；14、停车场管理、停车场管理1)1)问题描述问题描述设停车场内只有一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满 n 辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开

27、走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。2)2)基本要求基本要求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交

28、纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。3)3)测试数据测试数据设 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）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，a表示到达；d表示离去，e表示输入结束。4)4)实现提示实现提示需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据

29、项：汽车的牌照号码和进入停车场的时刻。5)5)选作内容选作内容（1） 两个栈共享空间，思考应开辟数组的空间是多少？（2） 汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如 1 辆客车和 1.5 辆小汽车的占地面积相同，1 辆十轮卡车占地面积相当于 3 辆小汽车的占地面积。（3） 汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。（4） 停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。15、简单行编辑程序、简单行编辑程序1)1)问题描述问题描述文本编辑程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入

30、、删除等修改操作。限制这些操作以行为单位进行的编辑程序称为行编辑程序。被编辑的文本文件可能很大，全部读入编辑程序的数据空间（内存）的做法既不经济，也不总能实现。一种解决方法是逐段地编辑。任何时刻只把待编辑文件的一段放在内存，称为活区。试按照这种方法实现一个简单的行编辑程序。设文件每行不超过 320 个字符，很少超过 80 字符。2)2)基本要求基本要求实现以下 4 条基本编辑命令：（1） 行插入。格式：i将插入活区中第行之后（2）行删除。格式：d删除活区中第行（到第行）。两种格式的例子是：“d10”和“d1014”（3）活区切换。格式：n将活区写入输出文件，并从输入文件中读入下一段，作为新的活

31、区。（4）活区显示。格式：p逐页地（每页 20 行）显示活区内容，每显示一页之后请用户决定是否继续显示以后各页（如果存在）。印出的每一行要前置以行号和一个空格符，行号固定占 4 位，增量为 1。各条命令中的行号均须在活区中各行行号范围之内，只有插入命令的行号可以等于活区第一行行号减1，表示插入当前屏幕中第一行之前，否则命令参数非法。3)3)测试数据测试数据由学生依据软件工程的测试技术自己确定。注意测试边界数据，如首行、尾行。4)4)实现提示实现提示（1） 设活区的大小用行数 activemaxlen（可设为 100）来描述。考虑到文本文件行长通常为正态分布，且峰值在 60 到 70 之间，用

32、320activemaxlen 大小的字符数组实现存储将造成大量浪费。可以以标准行块为单位为各行分配存储，每个标准行块含 81 个字符。这些行块可以组成一个数组，也可以利用动态链表连接起来。一行文字可能占多个行块。行尾可用一个特殊的 ascii 字符（如(012)8）标识。此外，还应记住活区起始行号。行插入将引起随后各行行号的顺序下推。（2） 初始化过程包括：请用户提供输入文件名（空串表示无输入文件）和输出文件名，两者不能相同。然后尽可能多地从输入文件中读入各行，但不超过 activemaxlen-x。x 的值可以自定，例如 20。（3） 在执行行插入命令的过程中，每接收到一行时到要检查活区大

33、小是否已达 activemaxlen。如果是，则为了在插入这一行之后仍保持活区大小不超过 activemaxlen，应将插入点之前的活区部分中第一行输出到输出文件中；若插入点为第一行之前，则只得将新插入的这一行输出。（4） 若输入文件尚未读完，活区切换命令可将原活区中最后几行留在活区顶部，以保持阅读连续性；否则，它意味着结束编辑或开始编辑另一个文件。（5） 可令前三条命令执行后自动调用活区显示。5)5)选作内容选作内容（1） 对于命令格式非法等一切错误作严格检查和适当处理。（2） 加入更复杂的编辑操作，如对某行进行串替换；在活区内进行模式匹配等，格式可以为 s和 m。16、哈希表设计、哈希表设

34、计1)1)问题描述问题描述针对某个集体中人名设计一个哈希表，使得平均查找长度不超过 r，并完成相应的建表和查表程序。2)2)基本要求基本要求假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有 30 个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。3)3)测试数据测试数据取读者周围较熟悉的 30 个人名。4)4)选作内容选作内容（1） 从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较他们的地址冲突率（可以用更大的名字集合作实验）。（2） 研究这 30 个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发

35、生地址冲突。（3） 在哈希函数确定的前提下尝试各种不同处理冲突的方法，考察平均查找长度的变化和造好的哈希表中关键字的聚集性。17、统计成绩、统计成绩1)1)问题描述问题描述给出 n 个学生的 m 门考试的成绩表，每个学生的信息由学号、姓名以及各科成绩组成。对学生的考试成绩进行有关统计，并打印统计表。2)2)基本要求基本要求（1） 按总数高低次序，打印出名次表，分数相同的为同一名次；（2） 按名次打印出每个学生的学号、姓名、总分以及各科成绩。3)3)测试数据测试数据由学生依据软件工程的测试技术自己确定。注意测试边界数据。4)4)选作内容选作内容对各科成绩设置不同的权值。18、校园导游程序、校园导

36、游程序 1)1)问题描述问题描述用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。2)2)基本要求基本要求（1） 查询各景点的相关信息；（2） 查询图中任意两个景点间的最短路径。（3） 查询图中任意两个景点间的所有路径。（4） 增加、删除、更新有关景点和道路的信息。3)3)选作内容选作内容（1） 求多个景点的最佳（最短）游览路径。（2） 区分机动车道和人行道。（3） 实现导游图的仿真界面。19、员工管理系统、员工管理系统1 1）问题描述）问题描述每个员工的信息包

37、括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。系统能够完成员工信息的查询、更新、插入、删除、排序等功能。2 2）基本要求）基本要求（1） 排序：按不同关键字，对所有员工的信息进行排序。（2） 查询：按特定条件查找员工。（3） 更新：按编号对某个员工的某项信息进行修改。（4） 插入：加入新员工的信息。（5） 删除：按编号删除已离职的员工的信息。20、 排序二叉树的遍历（排序二叉树的遍历（ 用递归或非递归的方法都可以）用递归或非递归的方法都可以） 1)1)问题描述问题描述输入树的各个结点，建立排序二叉树，对建立的排序二叉树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。

38、2)2)基本要求基本要求 (1)用菜单实现 (2)能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列和叶子结点的数目。21、个人帐簿管理系统设计、个人帐簿管理系统设计1)问题描述问题描述个人帐簿管理系统记录某人每月的全部收入及各项开支情况，包括食品消费，房租，子女教育费用，水电费，医疗费，储蓄等。进入系统后可以输入和修改某月的收支情况，可以对每月的开支从小到大进行排序，可以根据输入的月份查询每月的收支情况。2) 基本要求基本要求1初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2完成最低要求：建立一个文件，包括某人 5 个月的收支情况，能对文件中的信息进行扩充（追加），修改

39、和删除；3进一步要求：完成对每月的开支排序，以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。22、学分管理程序、学分管理程序1) 问题描述问题描述请设计一个学生的学分管理程序。假设每位学生必须完成基础课 50 学分、专业课 50 学分、选修课 24 学分、人文类课程 8 学分、实验性课程 20 学分才能够毕业。因此在管理学分时，要考虑每个学分所属于的课程类别。学分信息应该包括学号、姓名、课程类别、学分等。2) 基本要求基本要求该程序应该具有下列功能：(1) 通过键盘输入某位学生的学分； (2) 给定学号，显示某位学生的学分完成情况；(3) 给定某个班级的班号，显示该班所有学生学分完成情

40、况；(4) 给定某位学生的学号，修改该学生的学分信息；(5) 按照某类课程的学分高低进行排序；(6) 提供一些统计各类信息的功能。23、销售管理系统、销售管理系统1)问题描述问题描述 某公司有四个销售员（编号：1-4） ，负责销售五种产品（编号：1-5） 。每个销售员都将当天出售的每种产品各写一张便条交上来。每张便条包含内容： 1）销售员的代号 2）产品的代号 3）这种产品的当天的销售额 每位销售员每天可能上缴 0-5 张便条。假设，收集到了上个月的所有便条，编写一个处理系统，读取上个月的销售情况（自己设定） ，进行如下处理。 2) 基本要求基本要求1）计算上个月每个人每种产品的销售额。2）按

41、销售额对销售员进行排序，输出排序结果（销售员代号）3）统计每种产品的总销售额，对这些产品按从高到底的顺序，输出排序结果（需输出产品的代号和销售额）24、宿舍管理软件、宿舍管理软件 1)问题描述问题描述设某宿舍有:101,102,201,202 四个房间,每个房间有 4 个床位,学生信息包括学号、姓名、房间号，为学生宿舍管理人员编写一个宿舍管理软件。2) 基本要求基本要求该程序应该具有下列功能：(1) 学生的入住处理；(2) 学生退房处理；(3) 输出学生入住信息(按房间号和床号有序)；(4) 修改入住信息；(5) 学生调换宿舍或床位处理；(6) 按给定学号、姓名、房号查询；(7) 查询房间使用

42、情况。25、排序系统设计、排序系统设计1)问题描述问题描述设编号为 1，2，3，n 的 n(n0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限 m，从第一个人开始顺时针方向自 1 起顺序报数，报到 m 是停止报数，报 m 的人出列，将他的密码作为新的 m 值，从他的下一个人开始重新从 1 报数。如此下去，直到所有人全部出列为止。令 n 最大值取 30。要求设计一个程序模拟此过程，求出出列编号序列。2) 基本要求基本要求（1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；（2）完成最低要求：建立一个文件，包括某 5 个人的情况。26、库存管

43、理系统、库存管理系统1)问题描述问题描述试设计一库存管理系统，产品信息包括产品编号、名称、价格、数量等（产品编号不重复） 。2) 基本要求基本要求该系统应具有以下功能：1、产品信息录入功能(产品信息用文件保存)输入2、产品信息浏览功能 输出3、产品入库4、产品出库5、查询和排序功能： 1）按价格从大到小排序 2）按名称查询6、产品信息删除、修改功能。27、学生作业完成情况管理程序、学生作业完成情况管理程序1)问题描述问题描述请设计一个学生作业完成情况管理程序。假设某门课程一学期要留 10 次作业，每次老师要进行批改，给出分数后还要进行登记。学期期末要根据每次作业的成绩计算出最终的平时成绩（满分

44、 100） 。作业登记信息应该包含：学号、姓名、10 次作业的完成情况。2) 基本要求基本要求该程序应该具有下列功能：(1) 通过键盘输入某位学生某次作业的分数；(2) 给定学号，显示某位学生作业完成情况；(3) 给定某个班级的班号，显示该班所有学生的作业完成情况；(4) 给定某位学生的学号，修改该学生的作业完成信息；(5) 给定某位学生的学号，删除该学生的信息；(6) 按学生的最终平时成绩进行排序；(7) 输出平均分数。28、学生籍贯管理系统、学生籍贯管理系统1)问题描述问题描述编制一个学生籍贯信息记录簿，每个学生信息包括：学号、姓名、籍贯、通信地址。2) 基本要求基本要求该程序应该具有下列

45、功能：（1）输入学生信息并以磁盘文件保存；（2）读取磁盘文件并显示输出所有学生的籍贯信息；（3）按学号或姓名查询其籍贯；（4）按籍贯查询并输出该籍贯的所有学生；（5）能添加、删除和修改学生的籍贯信息；（6）显示输出天津籍和非天津籍学生的信息并可分别存盘；（7） 按学号进行排序。29、机票管理系统、机票管理系统1)问题描述问题描述一机场每天有 n 个航班，每个班次都有一班次号（1、2、3n） ，固定的起飞时间，固定的路线（起始站、终点站） ，大致的飞行车时间，固定的额定载客量。如班次 起飞时间 起点站 终点站 飞行时间 额定载量 已定票人数1 8:00 天津 广汉 2 145 1302 6:30

46、 天津 成都 0.5 140 1403 7:00 天津 成都 0.5 140 1204 10:00 天津 成都 0.5 140 120试设计一个机票管理系统，对机场的售票情况进行管理。2) 基本要求基本要求功能要求：（1）录入班次信息(信息用文件保存),可不定时地增加班次数据；（2）浏览班次信息,可显示出所有班次当前状况(如果当前系统时间超过了某班次的起飞时间,则显示“此班已发出”的提示信息)。（3）查询路线：可按班次号查询 ,可按终点站查询；（4）售票和退票功能 a：当查询出已定票人数小于额定载量且当前系统时间小于起飞时间时才能售票，自动更新已售票人数b：退票时，输入退票的班次，当本航班飞机

47、未发出时才能退票，自动更新已售票人数。30、学生成绩系统、学生成绩系统1)问题描述问题描述使用下面的数据，设计一个简单的成绩管理系统，实现出最基本的功能。学生基本信息文件(a.txt)及其内容：a.txt 文件不需要编程录入数据，可用文本编辑工具直接生成学号 姓名 性别 宿舍号码 电话号码01 张成成 男 501 8773211102 李成华 女 101 8772311203 王成凤 女 101 8772311204 张明明 男 502 87734333 . . .学生成绩基本信息文件(b.txt)及其内容：学号 课程编号 课程名称 学分 平时成绩 实验成绩 卷面成绩 综合成绩 实得学分01

48、a01 大学物理 3 66 78 82 02 b03 高等数学 4 78 -1 9001 b03 高等数学 4 45 -1 8802 c01 vf 3 65 76 66 . . . . 2) 基本要求基本要求功能要求及说明：(1) 数据录入功能: 对 b.txt 进行数据录入,只录入每个学生的学号、课程编号、课程名称、学分、平时成绩、实验成绩、卷面成绩共 7 个数据. 综合成绩、学分由程序根据条件自动运算。 综合成绩的计算:如果本课程的实验成绩为-1，则表示无实验，综合成绩=平时成绩*30%+卷面成绩*70%; 如果实验成绩不为-1,表示本课程有实验,综合成绩=平时成绩*15%+实验成绩*.1

49、5%+卷面成绩*70% . 实得学分的计算: 采用等级学分制. 综合成绩在 90-100 之间 ,应得学分=学分*100% 综合成绩在 70-90 之间 ,应得学分=学分*80%综合成绩在 60-70 之间 ,应得学分=学分*65%综合成绩在 60 以下 ,应得学分=学分*0%（2）删除功能：当在 a.txt 中删除一个学生时，自动地在 b.txt 中删除此人所有信息。（3）排序功能：能实现选择按综合成绩或实得学分升序或降序排序并显示数据。（4）查询功能：分为学生基本情况查询和成绩查询两种 a：学生基本情况查询：a1-输入一个学号或姓名（可实现选择） ，查出此生的基本信息并显示输出。a2-输入

50、一个宿舍号码，可查询出本室所有的学生的基本信息并显示输出。 b：成绩查询：b1：输入一个学号时，查询出此生的所有课程情况，格式如下：学 号：xx 姓 名：xxxxx课程编号：xxx 课程名称：xxxxx 综合成绩：xxxx 实得学分: xx课程编号：xxx 课程名称：xxxxx 综合成绩：xxxx 实得学分: xx课程编号：xxx 课程名称：xxxxx 综合成绩：xxxx 实得学分: xx 共修：xx 科，实得总学分为: xxx31、单项选择题标准化考试系统、单项选择题标准化考试系统1)问题描述问题描述设计一单项选择题标准化考试系统，实现考试的标准化管理。2) 基本要求基本要求功能要求：（1）

51、用文件保存试题库。 （每个试题包括题干、4 个备选答案、标准答案）（2）试题录入：可随时增加试题到试题库中（3）试题抽取：每次从试题库中可以随机抽出 n 道题（n 由键盘输入）（4）答题：用户可实现输入自己的答案（5）自动判卷：系统可根据用户答案与标准答案的对比实现判卷并给出成绩。注意：在 c 语言中产生随机数的方法：使用随机数函数在使用随机数函数 random()之前，应包含文件#include 然后使用下述函数初始化：randomize();/* init the random number generator */以后就可以直接使用 random()函数来产生需要的数据：如果需要产生 1

52、0 以内的数，使用 random(10)就可以了；产生 100 以内的数，使用 random(100)就可以了。在 c+中，产生随机数：#include #include 然后 srand(time(0); /以当前时间当做随机种子 rand(); /产生一个位于 0-32767 之间的随机数32、通信录管理系统、通信录管理系统1)问题描述问题描述设计出模拟手机通信录管理系统，实现对手机中的通信录进行管理。2) 基本要求基本要求功能要求：（1）查看功能：选择此功能时，列出下列三类选择。a 工作类 b 家庭类 c 朋友类 ，当选中某类时，显示出此类所有数据中的姓名和电话号码）（2）增加功能：能录

53、入新数据（一个结点包括：姓名、电话号码、分类（可选项有：a 工作类 b 家庭类 c 朋友类） 、家庭住址） 。例如杨春商务类 南开区当录入了重复的姓名和电话号码时，则提示数据录入重复并取消录入；当通信录中超过 10 条信息时，存储空间已满，不能再录入新数据；录入的新数据能按递增的顺序自动进行条目编号。（3）修改功能：选中某个人的姓名时，可对此人的相应数据进行修改（4） 删除功能：选中某个人的姓名时，可对此人的相应数据进行删除，并自动调整后续条目的编号。33、成绩管理系统、成绩管理系统1)问题描述问题描述现有学生成绩信息，内容如下姓名 学号 语文 数学 英语 张明明 0

54、1 67 78 82李成友 02 78 91 88张辉灿 03 68 82 56王露 04 56 45 77陈东明 05 67 38 47. . . . 请编写一系统，实现学生信息管理。2) 基本要求基本要求功能要求：（1）信息维护：要求：学生信息数据要以文件的形式保存，能实现学生信息数据的维护。此模块包括子模块有：增加学生信息、删除学生信息、修改学生信息（2）信息查询：要求：查询时可实现按姓名查询、按学号查询（3）成绩统计：要求：a 输入任意的一个课程名（如数学）和一个分数段（如 60-70） ，统计出在此分数段的学生情况。排序：能对用户指定的任意课程名，按成绩升序或降序排列学生数据并显示排

55、序结果（使用表格的形式显示排序后的输出结果） （使用多种方法排序者，加分）34、图书管理系统、图书管理系统1)问题描述问题描述设计一个系统，对图书信息进行管理，信息描述：有关该系统基本信息的描述，如：图书名称、图书编号、单价、作者、存在状态、借书人姓名、性别、学号等。2) 基本要求基本要求基本功能：1、新进图书基本信息的输入。2、图书基本信息的查询。3、对撤消图书信息的删除。4、为借书人办理注册。5、办理借书手续（非注册会员不能借书） 。6、办理还书手续。7、统计图书库存、已借出图书数量。35、商店存货管理系统、商店存货管理系统1)问题描述问题描述试设计一商店存货管理系统，要求每次出货时取进货

56、时间最早且最接近保质期中止时间的货物。2) 基本要求基本要求该系统应具有以下功能：1、商品信息录入功能(商品信息用文件保存)输入2、商品信息浏览功能 输出3、商品入库4、商品出库5、查询和排序功能： 1）按价格从大到小排序 2）按名称查询6、商品信息删除、修改功能。36、集合运算集合运算1)问题描述问题描述使用链表来表示集合，完成集合的合并，求交集等操作。2) 基本要求基本要求（1）用链表表示两个集合（2）对两个集合分别从小到大排序（3）两个集合合并成另一个新集合，如数值相同，合并为一个数据项（4）求出两个集合的交集建立一个新的集合。设计题目（二）设计题目（二）1 1、 运动会分数统计运动会分

57、数统计*问题描述：参加运动会有 n 个学校，学校编号为 1n。比赛分成 m 个男子项目，和 w 个女子项目。项目编号为男子 1m，女子 m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）*功能要求：1).可以输入各个项目的前三名或前五名的成绩；2)能统计各学校总分，3)可以按学校编号、学校总分、男女团体总分排序输出；4).可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。规定：输入数据形式和范围：20 以内的整数（如果做得更好可以输入学校

58、的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。*存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在 c 语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用 1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；2 2、 一元多项式计算一元多项式计算*问题描述：能够按照指数降序排列建立并输出多项式；能够完成两个多项式

59、的相加、相减，并将结果输入；在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；3 3、 订票系统订票系统*问题描述：通过此系统可以实现如下功能：1）录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）2）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；3）订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；4

60、）退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。5）修改航班信息：当航班信息改变可以修改航班数据文件*要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；4 4、 迷宫求解迷宫求解*问题描述：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；*要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；5 5、 文章编辑文章编辑*问题描述：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，