数据结构与C语言综合训练习题集
序号项目名称任务描述设计要求每组学生
人数
1．订票系统任务：通过此系统可以实现如下功能：
录入：
可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）
查询：确定航班是否满仓）；
可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，
可以输入起飞抵达城市，查询飞机航班情况；
订票：（订票情况可以存在一个数据文件中，结构自己设定）
可以订票，如果该航班已经无票，可以提供相关可选择航班；
退票：可退票，退票后修改相关数据文件；
客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。
修改航班信息：
当航班信息改变可以修改航班数据文件根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；
2．用Haffman编码
压缩文件准备一个文件，统计该文件中各种字符的频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成源文件。
3．统计C程序中关
键字的频率
扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现频度。用线性探测法解决Hash冲突。设Hash函数为：
Hash(key)=[(key的第一个字母序号)*100+(key的最后一个字母序号)] MOD 37
4．商品管理系统以链表结构的有序表表示某商场家电部的库存模型，当有提货或进货时需要对该链表及时进行维护，每个工作日结束以后，将该链表中的数据以文件形式保存，每日
开始营业之前，须将文件形式保存的数据恢复成链表结构的有序表。
链表结构的数据域包括家电名称、品牌、单价和数量，以单价的升序体现链表的有
序性。程序功能包括：初始化、创建表、插入、删除、更新数据、查询及链表数据
与文件之间的转换等。
5．排序算法效率比
较编程实现插入、希尔、快速、堆排序、归并排序算法，并计算每种算法的比较、交换次数。将待排数据从磁盘文件读入，实施排序后将数据写入另一个文件中。
6．管道铺设施工的
最佳方案选择N(N>10)个居民之间需要铺设煤气管道。假设任意两个居民之间都可以铺设煤气管道，但代价不同。事先将任意两个居民之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民之间铺设煤气管道所需代价最少，并希望以图形方式在屏幕上输出结果。
7．建立Haffman树
并查询对文件中的姓名按姓氏进行统计，计算每个姓氏出现的概率，并生产Haffman树，用另一个文件中的姓氏在Haffman树中查询，得出查询完成所用的时间；在中查询中姓氏，得出查询完成所用的时间，对两者进行对比，得出结论并写进论文。
8．校园导游咨询1)、功能描述：设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称，代号，简介等信息；以边表示路径，存放路径
长度等相关信息。
2)、为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一
条最短的简单路径。
3)、为来访客人提供图中任意景点相关信息的查询。
测试数据：由读者根据实际情况指定。
实现提示：一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网，
顶点和边均含有相关信息。
9．网络检查1)．问题描述
从文件中读入一个计算机网络以及机器间的双向连线列表，每一条连线允许两端的计算机进行直接的文件传输，其他计算机间若存在一条连通路径，也可以进行
间接的文件传输。请写出程序判断：任意指定两台计算机，它们之间是否可以进行
文件传输？
2)．基本要求
（1）输入要求：输入若干测试数据组成。对于每一组测试，第1行包含一个整数N（≤10000），即网络中计算机的总台数，因而每台计算机可用1到N之间的一个正整数表示。接下来的几行输入格式为I C1 C2或者 C或者C C1C2或者S，其中C1和C2是两台计算机的序号，I表示在C1和C2间输入一条连线，C表示检查C1和C2间是否可以传输文件，S表示该组测试结束。
当N为0时，表示全部测试结束，不要对该数据做任何处理。
（2）输出要求：对每一组C开头的测试，检查C1和C2间是否可以传输文件，若可以，则在一行中输出“yes”，否则输出“no”。
当读到S时，检查整个网络。若网络中任意两机器间都可以传输文件，则在一行中输出“The network is connected.”，否则输出“There are k components.”,其中k是网络中连通集的个数。
两组测试数据之间请输出一空行分隔。
10．产品进销存管理
系统问题描述：针对某一种行业的库房的产品进销存情况进行管理。
基本要求：
1.采用一定的存储结构对库房的货品及其数量进行分类管理；
2.可以进行产品类的添加、产品的添加、产品数量的添加；
能够查询库房每种产品的总量、进货日期、销出数量、销售时间等；
11．二叉排序树的实
数据结构与算法论文现
用顺序和二叉链表作存储结构
1)以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；
2)对二叉排序树T作中序遍历，输出结果；
3)输入元素x,查二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；
12．图书管理系统【问题描述】
设计一个计算机管理系统完成图书管理基本业务。
【基本要求】
1)每种书的登记内容包括书号、书名、著作者、现存量和库存量；
2)对书号建立索引表（线性表）以提高查效率；
3)系统主要功能如下：
*采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；
*借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；
*归还：注销对借阅者的登记，改变该书的现存量。
【进一步完成内容】
1)系统功能的进一步完善；
2)索引表采用树表。
3)设计内容
4)程序流程图
5)源程序
6)软件测试报告（包括所用到的数据及结果）
13．散列表的设计与
实现【问题描述】
设计散列表实现电话号码查系统。