数据结构与C语言综合训练习题集.doc
《数据结构与C语言综合训练习题集.doc》由会员分享,可在线阅读,更多相关《数据结构与C语言综合训练习题集.doc(53页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、序号项目名称任务描述设计要求每组学生人数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个。以图中顶点表示学校各景点,存放景点名称,代号,简介等信息;以边表示路径,存放路径长度等相关信息。2)
5、、为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一条最短的简单路径。3)、为来访客人提供图中任意景点相关信息的查询。测试数据:由读者根据实际情况指定。实现提示:一般情况下,校园的道路是双向通行的,可设校园平面图是一个无向网,顶点和边均含有相关信息。9网络检查1)问题描述从文件中读入一个计算机网络以及机器间的双向连线列表,每一条连线允许两端的计算机进行直接的文件传输,其他计算机间若存在一条连通路径,也可以进行间接的文件传输。请写出程序判断:任意指定两台计算机,它们之间是否可以进行文件传输?2)基本要求(1)输入要求:输入若干测试数据组成。对于每一组测试,第1行包含一个整数N(10
6、000),即网络中计算机的总台数,因而每台计算机可用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.”,否则输出“Th
7、ere 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)源程序6)软件测试报告(包括所
9、用到的数据及结果)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个城市连接的最小生成树问题描述:给定一个地区的n个城市间的距离网,用Prim
12、算法或Kruskal算法建立最小生成树,并计算得到的最小生成树的代价。基本要求:1、城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本中给出的定义,若两个城市之间不存在道路,则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路,并显示得到的最小生成树的代价。2、表示城市间距离网的邻接矩阵(要求至少6个城市,10条边)3、最小生成树中包括的边及其权值,并显示得到的最小生成树的代价。20线索二叉树的应用要求:实现线索树建立、插入、删除、恢复线索的实现。21树的应用要求:实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法,层次序的
13、非递归算法的实现,应包含建树的实现。22图的遍历的实现1)先任意创建一个图;2)图的DFS,BFS的递归和非递归算法的实现3)要求用有向图和无向图分别实现4)要求用邻接矩阵、邻接表多种结构存储实现23二叉树遍历要求:遍历的内容应是千姿百态的。树与二叉树的转换的实现。以及树的前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的实现,应包含建树的实现。要求:遍历的内容应是千姿百态的。24哈夫曼编码/译码器【问题描述】设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理以下项目,直到选择退出为止。【基本要求】1)将权值数据存放在数据文件(文件名为data.txt,位于执行程序的当前目录中)
14、 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件体积分别
15、为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件物品,若该件物品太大不能装入,则弃之而继续选取下一件,直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包,则说明刚刚装入背包的那件物品不合适,应将它取出弃
16、之一边,继续再从它之后的物品中选取,如此重复,直至求得满足条件的解,或者无解。由于回溯求解的规则规则是后进先出因此自然要用到栈。26运动会分数统计任务:参加运动会有n个学校,学校编号为1n。比赛分成m个男子项目,和w个女子项目。项目编号为男子1m,女子m+1m+w。不同的项目取前五名或前三名积分;取前五名的积分分别为:7、5、3、2、1,前三名的积分分别为:5、3、2;哪些取前五名或前三名由学生自己设定。(m=20,n0)个人按顺时针方向围坐一圈,每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m,从第一个人开始顺时针方向自1起顺序报数,报到m时停止报数,报m的人出列,将他的密码作为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 语言 综合 训练 习题集
限制150内