数据结构C语言综合训练作业集

数据结构与C语言综合训练习题集序号项目名称任务描述设计要求每组学生人数1订票系统任务：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：确定航班是否满仓）；可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣， 可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；2用Haffman编码压缩文件准备一个文件，统计该文件中各种字符的频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成源文件。3统计C程序中关键字的频率扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现频度。用线性探测法解决Hash冲突。设Hash函数为：Hash(key)=(key的第一个字母序号)*100+(key的最后一个字母序号) MOD 374商品管理系统以链表结构的有序表表示某商场家电部的库存模型，当有提货或进货时需要对该链表及时进行维护，每个工作日结束以后，将该链表中的数据以文件形式保存，每日开始营业之前，须将文件形式保存的数据恢复成链表结构的有序表。链表结构的数据域 包括家电名称、品牌、单价和数量，以单价的升序体现链表的有序性。程序功能包括：初始化、创建表、插入、删除、更新数据、查询及链表数据与文件之间的转换等。5排序算法效率比较 编程实现插入、希尔、快速、堆排序、归并排序算法，并计算每种算法的比较、交换次数。将待排数据从磁盘文件读入，实施排序后将数据写入另一个文件中。6管道铺设施工的最佳方案选择N(N>10)个居民之间需要铺设煤气管道。假设任意两个居民之间都可以铺设煤气管道，但代价不同。事先将任意两个居民之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民之间铺设煤气管道所需代价最少，并希望以图形方式在屏幕上输出结果。7建立Haffman树并查询对文件file1.txt中的姓名按姓氏进行统计，计算每个姓氏出现的概率，并生产Haffman树，用另一个文件file2.txt中的姓氏在Haffman树中查询，得出查询完成所用的时间；在file1.txt中查询file2.txt中姓氏，得出查询完成所用的时间，对两者进行对比，得出结论并写进论文。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散列表的设计与实现【问题描述】设计散列表实现电话号码查找系统。【基本要求】1)设每个记录有下列数据项：电话号码、用户名、地址；2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3)采用一定的方法解决冲突；4)查找并显示给定电话号码的记录；5)查找并显示给定用户名的记录。【进一步完成内容】1)系统功能的完善；2)设计不同的散列函数，比较冲突率；3)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。14利用栈求表达式的值，可供小学生作业，并能给出分数要求：建立试题库文件，随机产生n个题目；题目涉及加减乘除，带括弧的混合运算；随时可以退出；保留历史分数，能回顾历史，给出与历史分数比较后的评价15二叉平衡排序树问题描述：从一棵空树开始创建，在创建过程中，保证树的有序性，同时还要针对树的平衡性做些调整。最终要把创建好的二叉排序树转换为二叉平衡排序树。基本要求：1).创建（插入、调整、改组） 2).输出16算术表达式的求解问题描述：给定一个算术表达式，通过程序求出最后的结果。基本要求：1 从键盘输入要求解的算术表达式；2 采用栈结构进行算术表达式的求解过程；3 能够判断算术表达式正确与否；4 对于错误表达式给出提示；5 对于正确的表达式给出最后的结果；17关键路径问题问题描述：设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。基本要求：（1）对一个描述工程的AOE网，应判断其是否能够顺利进行。（2）若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。18客户消费积分管理系统问题描述：针对客户的消费情况，进行客户管理，根据客户的消费积分对客户实行不同程度的打折优惠。基本要求：1. 采用一定的存储结构进行客户信息的存储；2. 对客户的信息可以进行修改、删除、添加；3. 能够根据消费情况进行客户积分的计算；4. 根据积分情况实行不同程度的打折优惠；19构造可以使n个城市连接的最小生成树问题描述：给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。基本要求：1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。2、表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）3、最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。20线索二叉树的应用要求：实现线索树建立、插入、删除、恢复线索的实现。21树的应用要求：实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。22图的遍历的实现1)先任意创建一个图；2)图的DFS,BFS的递归和非递归算法的实现3)要求用有向图和无向图分别实现4)要求用邻接矩阵、邻接表多种结构存储实现23二叉树遍历要求：遍历的内容应是千姿百态的。树与二叉树的转换的实现。以及树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。要求：遍历的内容应是千姿百态的。24哈夫曼编码/译码器【问题描述】设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。【基本要求】1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 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件物品，若该件物品"太大"不能装入，则