《数据结构C语言综合训练作业集》由会员分享，可在线阅读，更多相关《数据结构C语言综合训练作业集（53页珍藏版）》请在金锄头文库上搜索。
1、数据结构与C语言综合训练习题集序号项目名称任务描述设计要求每组学生人数1订票系统任务：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：确定航班是否满仓）；可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣， 可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文
2、件根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；2用Haffman编码压缩文件准备一个文件，统计该文件中各种字符的频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成源文件。3统计C程序中关键字的频率扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现频度。用线性探测法解决Hash冲突。设Hash函数为：Hash(key)=(key的第一个字母序号)*100+(key的最后一个字母序号) MOD 374商品管理系统以链表结构的有序表表示某商场家电部的库存模型，当有提货或进货时需要对该链
3、表及时进行维护，每个工作日结束以后，将该链表中的数据以文件形式保存，每日开始营业之前，须将文件形式保存的数据恢复成链表结构的有序表。链表结构的数据域 包括家电名称、品牌、单价和数量，以单价的升序体现链表的有序性。程序功能包括：初始化、创建表、插入、删除、更新数据、查询及链表数据与文件之间的转换等。5排序算法效率比较 编程实现插入、希尔、快速、堆排序、归并排序算法，并计算每种算法的比较、交换次数。将待排数据从磁盘文件读入，实施排序后将数据写入另一个文件中。6管道铺设施工的最佳方案选择N(N10)个居民之间需要铺设煤气管道。假设任意两个居民之间都可以铺设煤气管道，但代价不同。事先将任意两个居民之间
4、铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民之间铺设煤气管道所需代价最少，并希望以图形方式在屏幕上输出结果。7建立Haffman树并查询对文件file1.txt中的姓名按姓氏进行统计，计算每个姓氏出现的概率，并生产Haffman树，用另一个文件file2.txt中的姓氏在Haffman树中查询，得出查询完成所用的时间；在file1.txt中查询file2.txt中姓氏，得出查询完成所用的时间，对两者进行对比，得出结论并写进论文。8校园导游咨询1)、功能描述：设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称，代号，简介等信息；以边表示路径
5、，存放路径长度等相关信息。2)、为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。3)、为来访客人提供图中任意景点相关信息的查询。测试数据：由读者根据实际情况指定。实现提示：一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网，顶点和边均含有相关信息。9网络检查1)问题描述从文件中读入一个计算机网络以及机器间的双向连线列表，每一条连线允许两端的计算机进行直接的文件传输，其他计算机间若存在一条连通路径，也可以进行间接的文件传输。请写出程序判断：任意指定两台计算机，它们之间是否可以进行文件传输？2)基本要求（1）输入要求：输入若干测试数据组成。对于每一组测
6、试，第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 conn
7、ected.”，否则输出“There are k components.”,其中k是网络中连通集的个数。两组测试数据之间请输出一空行分隔。10产品进销存管理系统问题描述：针对某一种行业的库房的产品进销存情况进行管理。基本要求：1. 采用一定的存储结构对库房的货品及其数量进行分类管理；2. 可以进行产品类的添加、产品的添加、产品数量的添加；能够查询库房每种产品的总量、进货日期、销出数量、销售时间等；11二叉排序树的实现 用顺序和二叉链表作存储结构 1)以回车(n)为输入结束标志,输入数列L，生成一棵二叉排序树T；2)对二叉排序树T作中序遍历，输出结果；3)输入元素x,查找二叉排序树T,若存在含x
8、的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；12图书管理系统【问题描述】设计一个计算机管理系统完成图书管理基本业务。【基本要求】1)每种书的登记内容包括书号、书名、著作者、现存量和库存量；2)对书号建立索引表（线性表）以提高查找效率；3)系统主要功能如下：*采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；*借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；*归还：注销对借阅者的登记，改变该书的现存量。【进一步完成内容】1)系统功能的进一步完善；2)索引表采用树表。3)设计内容4)程序流程图5)
9、源程序6)软件测试报告（包括所用到的数据及结果）13散列表的设计与实现【问题描述】设计散列表实现电话号码查找系统。【基本要求】1)设每个记录有下列数据项：电话号码、用户名、地址；2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3)采用一定的方法解决冲突；4)查找并显示给定电话号码的记录；5)查找并显示给定用户名的记录。【进一步完成内容】1)系统功能的完善；2)设计不同的散列函数，比较冲突率；3)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。14利用栈求表达式的值，可供小学生作业，并能给出分数要求：建立试题库文件，随机产生n个题目；题目涉及加减乘
10、除，带括弧的混合运算；随时可以退出；保留历史分数，能回顾历史，给出与历史分数比较后的评价15二叉平衡排序树问题描述：从一棵空树开始创建，在创建过程中，保证树的有序性，同时还要针对树的平衡性做些调整。最终要把创建好的二叉排序树转换为二叉平衡排序树。基本要求：1).创建（插入、调整、改组） 2).输出16算术表达式的求解问题描述：给定一个算术表达式，通过程序求出最后的结果。基本要求：1 从键盘输入要求解的算术表达式；2 采用栈结构进行算术表达式的求解过程；3 能够判断算术表达式正确与否；4 对于错误表达式给出提示；5 对于正确的表达式给出最后的结果；17关键路径问题问题描述：设计一个程序求出完成整
11、项工程至少需要多少时间以及整项工程中的关键活动。基本要求：（1）对一个描述工程的AOE网，应判断其是否能够顺利进行。（2）若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。18客户消费积分管理系统问题描述：针对客户的消费情况，进行客户管理，根据客户的消费积分对客户实行不同程度的打折优惠。基本要求：1. 采用一定的存储结构进行客户信息的存储；2. 对客户的信息可以进行修改、删除、添加；3. 能够根据消费情况进行客户积分的计算；4. 根据积分情况实行不同程度的打折优惠；19构造可以使n个城市连接的最小生成树问题描述：给定一个地区的
12、n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。基本要求：1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。2、表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）3、最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。20线索二叉树的应用要求：实现线索树建立、插入、删除、恢复线索的实现。21树的应用要求：实现树与二叉树的转换的实现。以及树的前序、后
13、序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。22图的遍历的实现1)先任意创建一个图；2)图的DFS,BFS的递归和非递归算法的实现3)要求用有向图和无向图分别实现4)要求用邻接矩阵、邻接表多种结构存储实现23二叉树遍历要求：遍历的内容应是千姿百态的。树与二叉树的转换的实现。以及树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。要求：遍历的内容应是千姿百态的。24哈夫曼编码/译码器【问题描述】设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。【基本要求】1)将权值数据存放在数据文件(文件名为data.tx
14、t，位于执行程序的当前目录中) 2)分别采用动态和静态存储结构3)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；4)编码：利用建好的哈夫曼树生成哈夫曼编码；5)输出编码；6)设字符集及频度如下表：字符 空格 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 【进一步完成内容】1)译码功能；2)显示哈夫曼树；3)界面设计的优化25背包问题的求解假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + + wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积1，8，4，3，5，2时，可找到下列4组解：（1，4，3，2）（1，4，5）（8，2）（3，5，2）提示：可利用回溯法的设计思想来解决背包问题。首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品太大不能装入，则
