数据结构与C语言综合训练习题集

数据结构与C语言综合训练习题集

序号 1． 项目名称 订票系统 任务描述 任务：通过此系统可以实现如下功能： 录入： 可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定） 查询：确定航班是否满仓）； 可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣， 可以输入起飞抵达城市，查询飞机航班情况； 订票：（订票情况可以存在一个数据文件中，结构自己设定） 可以订票，如果该航班已经无票，可以提供相关可选择航班； 退票： 可退票，退票后修改相关数据文件； 客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。 修改航班信息： 当航班信息改变可以修改航班数据文件 设计要求 根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能； 每组学生人数 2． 3． 用Haffman编码压缩文件 统计C程序中关键字的频率 商品管理系统 准备一个文件，统计该文件中各种字符的频率，对各字符进行Huffman编码，将该 文件翻译成Huffman编码文件，再将Huffman编码文件翻译成源文件。 扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现频度。用线性探测法解决Hash冲突。设Hash函数为： Hash(key)=[(key的第一个字母序号)*100+(key的最后一个字母序号)] MOD 37 4． 以链表结构的有序表表示某商场家电部的库存模型，当有提货或进货时需要对该链 表及时进行维护，每个工作日结束以后，将该链表中的数据以文件形式保存，每日开始营业之前，须将文件形式保存的数据恢复成链表结构的有序表。 链表结构的数据域 包括家电名称、品牌、单价和数量，以单价的升序体现链表的有序性。程序功能包括：初始化、创建表、插入、删除、更新数据、查询及链表数据 1

数据结构与C语言综合训练习题集

与文件之间的转换等。 5． 6． 排序算法效率比较 管道铺设施工的最佳方案选择 编程实现插入、希尔、快速、堆排序、归并排序算法，并计算每种算法的比较、交换次数。将待排数据从磁盘文件读入，实施排序后将数据写入另一个文件中。 N(N>10)个居民之间需要铺设煤气管道。假设任意两个居民之间都可以铺设煤气管 道，但代价不同。事先将任意两个居民之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民之间铺设煤气管道所需代价最少，并希望以图形方式在屏幕上输出结果。 对文件file1.txt中的姓名按姓氏进行统计，计算每个姓氏出现的概率，并生产 Haffman树，用另一个文件file2.txt中的姓氏在Haffman树中查询，得出查询完成所用的时间；在file1.txt中查询file2.txt中姓氏，得出查询完成所用的时间，对两者进行对比，得出结论并写进论文。 1)、功能描述：设计你的学校的校园平面图，所含景点不少于10个。以图中顶 点表示学校各景点，存放景点名称，代号，简介等信息；以边表示路径，存放路径长度等相关信息。 2)、为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 3)、为来访客人提供图中任意景点相关信息的查询。 测试数据：由读者根据实际情况指定。 实现提示：一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网，顶点和边均含有相关信息。 1)．问题描述 从文件中读入一个计算机网络以及机器间的双向连线列表，每一条连线允许两端的计算机进行直接的文件传输，其他计算机间若存在一条连通路径，也可以进行间接的文件传输。请写出程序判断：任意指定两台计算机，它们之间是否可以进行文件传输？ 2)．基本要求 7． 建立Haffman树并查询 8． 校园导游咨询 9． 网络检查 2

数据结构与C语言综合训练习题集

（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”； 【问题描述】 设计一个计算机管理系统完成图书管理基本业务。 【基本要求】 1)每种书的登记内容包括书号、书名、著作者、现存量和库存量； 12． 图书管理系统 3

数据结构与C语言综合训练习题集

2)对书号建立索引表（线性表）以提高查找效率； 3)系统主要功能如下： *采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加； *借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量； *归还：注销对借阅者的登记，改变该书的现存量。 【进一步完成内容】 1)系统功能的进一步完善； 2)索引表采用树表。 3)设计内容 4)程序流程图 5)源程序 6)软件测试报告（包括所用到的数据及结果） 13． 散列表的设计与实现 【问题描述】 设计散列表实现电话号码查找系统。 【基本要求】 1)设每个记录有下列数据项：电话号码、用户名、地址； 2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表； 3)采用一定的方法解决冲突； 4)查找并显示给定电话号码的记录； 5)查找并显示给定用户名的记录。 【进一步完成内容】 1)系统功能的完善； 2)设计不同的散列函数，比较冲突率； 3)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长 4

数据结构与C语言综合训练习题集

度的变化。 14． 利用栈求表达式的值，可供小学生作业，并能给出分数 要求：建立试题库文件，随机产生n个题目；题目涉及加减乘除，带括弧的混合运 算；随时可以退出；保留历史分数，能回顾历史，给出与历史分数比较后的评价 15． 二叉平衡排序树 问题描述：从一棵空树开始创建，在创建过程中，保证树的有序性，同时还要针对树的平衡性做些调整。最终要把创建好的二叉排序树转换为二叉平衡排序树。 基本要求：1).创建（插入、调整、改组） 2).输出 16． 算术表达式的求解 问题描述：给定一个算术表达式，通过程序求出最后的结果。 基本要求： 1． 从键盘输入要求解的算术表达式； 2． 采用栈结构进行算术表达式的求解过程； 3． 能够判断算术表达式正确与否； 4． 对于错误表达式给出提示； 5． 对于正确的表达式给出最后的结果； 17． 关键路径问题 问题描述：设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关 键活动。 基本要求： （1）对一个描述工程的AOE网，应判断其是否能够顺利进行。 （2）若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。 问题描述：针对客户的消费情况，进行客户管理，根据客户的消费积分对客户实行不同程度的打折优惠。 基本要求： 1. 采用一定的存储结构进行客户信息的存储； 18． 客户消费积分管理系统 5

数据结构与C语言综合训练习题集

客户的到达事件和客户的离开事件。 （3）可以友好的显示出在某一天中整个银行系统中客户在银行逗留的平均时间。 30． 哈希表的设计与实现 问题描述：设计一个哈希表，实现个人电话号码查询系统。 基本要求： （1）设每个记录有下列数据项：电话号码、用户名、用户住址； （2）从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表； a) 设计不同的哈希函数，比较冲突率； b) 在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。 （3）查找并显示给定电话号码/用户名的记录； 问题描述：文件是管理用户信息和应用程序的一种工具。每个文件有唯一的文件名，可以通过文件名访问文件，同时可对文件进行生成、删除及文件名修改等操作。文件系统对若干文件进行管理时将所有的文件目录组合在一起构成一个目录文件。通过对目录文件的管理达到“按名存取”的目的，目录文件常采用的组织结构是树型目录结构。 基本要求： 函数功能要划分好，程序要有必要的注释。 用户通过界面菜单选择以下操作： （注意，以下操作仅需对目录进行操作，不需要实际生成文件） （1） 生成文件，选择路径和文件名，实现对文件的生成。 （2） 删除文件，对指定文件进行删除操作。 （3） 修改文件，对指定文件进行内容修改或者文件名修改。 （4） 输出该目录结构。 31． 文件目录管理系统 32． 身份证管理程序 该程序应该具有下列功能： (1) 通过键盘可以输入身份证信息，大量信息可存放在文件中。身份证包含的信息请参看自己的身份证； 提供一些统计各类信息的功能。例如男女的人数、比例；以及哪年、 11

数据结构与C语言综合训练习题集

(2) 给定身份证号码，显示其身份证信息； (3) 给定省份的编号，显示该省的人数； (4) 给定某区的编号，显示该区的人数； (5) 给定身份证号码，可以修改该身份证信息； (6) 给定身份证号码，可以删除该身份证信息； 33． 期刊论文管理程序 该程序应该具有下列功能： (1) 通过键盘输入某期刊论文的信息，也可以把大量期刊论文信息放在文件中； (2) 给定期刊论文的论文名称，显示该论文的作者信息，作者单位，发表期刊的名称； (3) 给定作者姓名，显示所有该作者发表的期刊论文情况； (4) 给定期刊名称，显示该期刊的所有论文信息； 哪月、哪日出生的人数等。界面要合理。 提供一些统计各类信息的功能。例如某人发表论文的个数，某期刊出版论文的个数等。 34． 哈夫曼编码 问题描述：利用哈夫曼编码，实现压缩和解压缩。 完成任务描述中的各种基本要求： 功能，自己可以适当增对于给定的一组字符，可以根据其权值进行哈夫曼编码，并能输出对应的哈夫曼树加必要的功能。 和哈夫曼编码；实现哈夫曼解码。 提高要求： (1)能够分析文件，统计文件中出现的字符，统计字符出现的概率，再对文件进行编码，实现文件的压缩和解压缩。 (2)能够对于文件的压缩比例进行统计。 功能：设编号为1，2，3，??，n的n(n>0)个人按顺时针方向围坐一圈，每个要求：用数组和链表分人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺别实现。m和n的值可时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新以由键盘输入。 的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。 设计一个简单的学生宿舍管理查询程序，要求根据菜单处理相应功能。 （1）建立数据文件 ，数据文件按关键字（姓名、学号、房号）进行排序 排序方法任选。基本功能为：建立文件、增加 35． 约瑟夫环问题 36． 学生宿舍管理查询软件 12

数据结构与C语言综合训练习题集

（2）查询菜单: (可以用二分查找实现以下操作) A. 按姓名查询 B. 按学号查询 C. 按房号查询等 （3）可以打印任一查询结果 （4）每个学生的信息包括：序号、学号、性别、房号、楼号等； 37． 学生成绩管理系统 现有学生成绩信息文件1（1.txt），内容如下 学生成绩信息文件2（2.txt）,内容如下: 姓名 学号 语文 数学 英语 姓名 学号 语文 数学 英语 张明明 01 67 78 82 陈果 31 57 68 82 李成友 02 78 91 88 李华明 32 88 90 68 张辉灿 03 68 82 56 张明东 33 48 42 56 王露 04 56 45 77 李明国 34 50 45 87 陈东明 05 67 38 47 陈道亮 35 47 58 77 --------- --- -- -- -- -------- -- -- -- -- 试编写一管理系统,要求如下: 1) 实现对两个文件数据的合并,生成新文件3.txt 2) 抽取出三科成绩中有补考的学生并保存在一个新文件4.txt 3) 对合并后的文件3.txt中的数据按总分降序排序(至少采用两种排序方法实现) 4) 输入一个学生姓名后,能查找到此学生的信息并输出结果 用链式结构建立有序表，结点的数据域应该包括家电名称、品牌型号、单价以及数量，以结点中单价的递增顺序排列。日常的维护操作应该包括初始化，创建链表，插入，删除，更新数据，打印，查询。 基本业务活动包括：对新书的采编入库、清除库存、借阅和归还等等。 图书的基本信息：图书编号，出版社，作者信息，定价，图书名称等。 学生宿舍记录、删除/修改、查询学生宿舍记录。 要求使用结构体链表或数组等实现上述要求. 38． 家电销售系统 界面安排合理，提示信息完善。 完成任务描述中的各种功能，自己可以适当增加必要的功能。 39． 图书管理系统 13

数据结构与C语言综合训练习题集

40． 文本编辑系统 41． （1）分别统计出其中英文字母数和空格数及整篇文章总字数； （2）统计某一字符串在文章中出现的次数，并输出该次数； （3）删除某一子串，并将后面的字符前移。 字串可以任意输入。完成任务描述中的各种功能，自己可以适当增加必要的功能。 作为一个完整的系统，应具有友好的界面和较强的容错能力 问题描述：编写一个通讯录管理系统。本系统应完成以下几方面的功能： 1) 输入信息——enter(); 2) 显示信息———display( ); 通讯录管理系统 3) 查找以姓名作为关键字 search( ); 4) 删除信息———delete( ); 5) 存盘———save ( ); 6) 装入———load( ) ; 要求：（1) 每条信息应包含 ：姓名（NAME ）街道（STREET）城市（CITY） 邮编（EIP）国家（STATE）等信息。 主要是加减乘除的运算，利用栈的思想对表达式求值。要掌握运算符的优先级等，按照运算符的优先级进行判断。 42． 求任一表达式的值 43． 订票系统 有进栈、出栈、判断栈顶元素等操作。 录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据完成任务描述中的各种自定） 功能，自己可以适当增查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，加必要的功能。 航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况； 给定简单的算术表达式，包括加减乘除括号这几种运算操作符，请计算表达式的值。 首先将算术表达式转化(1)能够正确处理加减乘除这四种运算； 成逆波兰式，针对逆波(2)能够正确处理括号运算； 兰式进行运算。 编写程序，不使用标准库函数，实现字符串的拷贝、拼接、字串查找、长度计算等函数。 (1)在不使用相关的标准库函数的情况下，完成本任务； (2)实现两个字符串拼接的函数strcat(str1, str2)； (3)实现字符串拷贝的函数strcpy(str1,str2)； (4)实现字符串查找的函数strcstr(str1,str2)； 完成任务描述中的各种功能，自己可以适当增加必要的功能。 44． 简单算术表达式运算 45． 字符串操作 14

数据结构与C语言综合训练习题集

(5)实现字符串长度计算的函数strlen(str1)； (6)实现字符串查找字符的函数strcchar(str1,c)； (7)实现字符串替换的函数strcreplacestr(str1,str2,str3)； (8)实现字符串替换字符的函数strcreplacechar(str1,str2,c)； 46． 集合操作 用单链表模拟有序集合，实现集合的加入一个元素、删除一个元素、集合的交、并、完成任务描述中的各种差运算。 功能，自己可以适当增(1)用单链表存放集合中的元素，链表中的元素按大小存放； 加必要的功能。 (2)实现集合加入一个元素删除一个元素的元素操作； (3)实现集合的交、并、差集合操作； 编写程序，统计C语言源程序的代码。 1. /* */ 和//的都认为是注释行2. 统计空行3. 非空非注释行,基本上可以认为是有效的代码行 如果同一行中有注释和代码的认为是代码行4, 统计总代码行数、注释行数、空行数 5 输入： codeCounter –filename/filepath 输出列表： filename 总代码行数、注释行、空行 设计一个简单的歌手比赛绩管理程序，对一次歌手比赛的成绩进行管理 功能要求： 1.输入每个选手的数据包括编号、姓名、十个评委的成绩，根据输入计算出总成绩和平均成绩（去掉最高分，去掉最低分）。 2.显示主菜单如下：1）输入选手数据 2）评委打分 3）成绩排序（按平均分）4）数据查询 5）追加学生数据 6）写入数据文件7）退出系统 47． C语言源程序代码行统计工具codeCounter 48． 歌手比赛系统 49． 小学生测验系统 面向小学1~2年级学生，随机选择两个整数和加减法形成算式要求学生解答。 功能要求： （1）电脑随机出10道题，每题10分，程序结束时显示学生得分； （2）确保算式没有超出1~2年级的水平，只允许进行50以内的加减法，不允许两数之和或之差超出0~50的范围，负数更是不允许的； 15

数据结构与C语言综合训练习题集

（3）每道题学生有三次机会输入答案，当学生输入错误答案时，提醒学生重新输入，如果三次机会结束则输出正确答案； （4）对于每道题，学生第一次输入正确答案得10分，第二次输入正确答案得7分，第三次输入正确答案得5分，否则不得分； （5）总成绩90以上显示“SMART”,80-90显示“GOOD”，70-80显示“OK”,60-70显示“PASS”，60以下“TRY AGAIN” 50． 中文分词实现 对中文句子进行划分，得到词组 采用基于字符串匹配的分词方法，即汉字串与一个机器词典（词典文件可网上下载）中的词条进行配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。分别实现以下几种划分方法： 1）正向最大匹配法（由左到右的方向）； 2）逆向最大匹配法（由右到左的方向）； 3）最少切分（使每一句中切出的词数最小）； 4）双向最大匹配法（进行由左到右、由右到左两次扫描） 编写程序，不使用标准库函数，实现字符串的拷贝、拼接、字串查找、长度计算、拆分、等函数。 (1)在不使用相关的标准库函数的情况下，完成本任务； (2)实现两个字符串拼接的函数strcat(str1, str2)； (3)实现字符串拷贝的函数strcpy(str1,str2)； (4)实现字符串查找的函数strcstr(str1,str2)； (5)实现字符串长度计算的函数strlen(str1)； (6)实现字符串查找字符的函数strcchar(str1,c)； (7)实现字符串替换的函数strcreplacestr(str1,str2,str3)； (8)实现字符串替换字符的函数strcreplacechar(str1,str2,c)； (9）实现字符串拆分函数strsplit(str1,c,str[]) 实现万年历程序 1 51． 字符串操作 1 52． 万年历查询程 16

数据结构与C语言综合训练习题集

序。 功能要求： （1）提供菜单方式选择，假定输入的年份在1940-2040年之间。 （2）输入一个年份，输出是在屏幕上显示该年的日历。 （3）输入年月，输出该月的日历。如： （4）输入年份、月份、日期，计算得到的是这一天据今天有多少天，星期几； （5）输入公历的年月日，输出农历年月日。 （6）输入农历节气，输出当年农历的年月日及公历年月日。可以假定只涉及年份是1940年到2040年。 53． 数字游戏的设计 实现一个简单的猜数字游戏 （1）一个四位数，各位上的数字不重复,从1到9。 （2）按以下提示猜出这个四位数。 （3）每次猜测输入的数据给出类似的提示*A*B。 （4）其中A前的*代表你本次猜对了多少个数字。 （5）其中B前的*代表你本次猜对的数字并且位置正确的个数。 （6）给定猜测次数，如果超过次数未猜中，游戏失败 54． 集合操作 用单链表模拟有序集合，实现集合的加入一个元素、删除一个元素、集合的交、并、 差运算。 (1)用单链表存放集合中的元素，链表中的元素按大小存放； (2)实现集合加入一个元素删除一个元素的元素操作； (3)实现集合的交、并、差集合操作； 17

数据结构与C语言综合训练习题集

55． 订票系统 实现一个简单的订票系统 基本要求： (1)录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定） (2)查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）； (3)可以输入起飞抵达城市，查询飞机航班情况； (4)订票：（订票情况可以存在一个数据文件中，结构自己设定），可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号； (5)修改航班信息：当航班信息改变可以修改航班数据文件。 实现简单的个人电话号码查询系统，根据用户输入的信息（如姓名，身份证号，电 话号码、邮件地址等）进行快速查询。 基本要求： (1) 插入：实现将用户的信息插入到系统中； (2) 删除：删除某个用户的信息； (3) 修改：修改某个用户的信息； (4) 查询：根据姓名、身份证号等查询用户信息（包括简单条件查询，组合条件查询、模糊查询等）； (5) 排序：对于用户信息进行排序，提高查询速度； (6) 输出：输出用户信息。 提示： (1) 在内存中，设计数据结构存储电话号码的信息；在外存中，利用文件的形式来保存电话号码信息，系统运行时，将电话号码信息从文件调入内存来进行插入、查找等操作。 (2) 如果数据的插入删除频繁，可以考虑采取二叉排序树组织电话号码信息（也可 56． 个人电话号码查询系统 1 18

数据结构与C语言综合训练习题集

采用较复杂的平衡二叉树），可以提高查找和维护的时间性能。 (3) 选择不同的排序和查找算法，尽可能提高查找和维护性能。 57． 单源最短路径求解 58． 文本文件行编辑程序的设计与实现 给定一个带权有向图G=(V,E)，其中每条边的权是一个非负实数。另外，还给定V中的一个顶点，成为源。现在计算从源到其他各顶点的最短路径。路径的长度是指路上各边权值之和。 1 实现的功能如下： 1、 打开与显示 2、 插入行 3、 删除行 4、 推出程序 操作说明： 1、 以屏幕菜单显示操作方式； 2、 以命令方式打开文本文件的打开与显示，若干行的插入、若干行的删除与退出。 设有一个数组A: array[0..N-1];存放的元素为0-N-1(1

数据结构与C语言综合训练习题集

②显示信息：用以显示输入的数据，包括从内存中读出和从磁盘中读出 ③查找：以姓名作为关键字查找要找的信息 ④删除信息：用以删除选定的输入信息（姓名作为关键字） ⑤存盘：调用此函数将内存中的数据保存至磁盘中 ⑥装入：调用此函数用以将之前保存在磁盘的内容读入到内存中或显示到屏幕上。 注：本课题中输入的数据应包括以下几项信息： 姓名、学校、城市、邮编、国家。 61． Josephus问题 功能：设编号为1，2，3，??，n的n(n>0)个人按顺时针方向围坐一圈，每个 人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。 要求：用数组和链表分别实现。 1 62． 排序方法的比较 编一程序对至少三个排序方法进行比较，比较方法是生成一组数据(≥100)，用选定的排序方法进行排序。输出每种方法数据比较或交换的次数。最后输出所花费的时间。 63． 学生成绩管理系统 现有学生成绩信息文件1（1.txt），内容如下 姓名 学号 语文 数学 英语 张明明 01 67 78 82 李成友 02 78 91 88 张辉灿 03 68 82 56 王露 04 56 45 77 陈东明 05 67 38 47 ... .. .. .. .. 学生成绩信息文件2（2.txt）,内容如下: 1 1 20

数据结构与C语言综合训练习题集

姓名 学号 语文 数学 英语 陈果 31 57 68 82 李华明 32 88 90 68 张明东 33 48 42 56 李明国 34 50 45 87 陈道亮 35 47 58 77 ... .. .. .. .. 试编写一管理系统,要求如下: 1) 实现对两个文件数据的合并,生成新文件3.txt 2) 抽取出三科成绩中有补考的学生并保存在一个新文件4.txt 3) 对合并后的文件3.txt中的数据按总分降序排序(至少采用两种排序方法实现) 4) 输入一个学生姓名后,能查找到此学生的信息并输出结果(至少采用两种查找方法实现) 5) 要求使用结构体,链或数组等实现上述要求. 64． 字符串操作 编写程序，不使用标准库函数，实现字符串的拷贝、拼接、字串查找、长度计算等函数。 (1)在不使用相关的标准库函数的情况下，完成本任务； (2)实现两个字符串拼接的函数strcat(str1, str2)； (3)实现字符串拷贝的函数strcpy(str1,str2)； (4)实现字符串查找的函数strcstr(str1,str2)； (5)实现字符串长度计算的函数strlen(str1)； (6)实现字符串查找字符的函数strcchar(str1,c)； (7)实现字符串替换的函数strcreplacestr(str1,str2,str3)； (8)实现字符串替换字符的函数strcreplacechar(str1,str2,c)； 1 65． 集合操作 用单链表模拟有序集合，实现集合的加入一个元素、删除一个元素、集合的交、并、 21

数据结构与C语言综合训练习题集

差运算。 (1)用单链表存放集合中的元素，链表中的元素按大小存放； (2)实现集合加入一个元素删除一个元素的元素操作； (3)实现集合的交、并、差集合操作； 输入N（2<=N<=100）个数字(在0与9之间),然后统计出这组数种相邻两数字组成的 链环数字对出现的次数。例如： 输入：N=20 {表示要输入数的数目} 0 1 5 9 8 7 2 2 2 3 2 7 8 7 8 7 9 6 5 9 输出(7,8)=2 (8,7)=3{指(7,8)、(8,7)数字对出现次数分别为2次、3次} 四种算法都是前序、中序、后序三种算法要求递归和非递归实现，层遍历用非递归实现。 根据输入文本中每个字符的权重，构建哈夫曼树，并生成对应的哈夫曼编码 任务：用邻接矩阵实现图的遍历，并用克鲁斯卡尔算法求图的最小生成树 66． 找数字对 67． 二叉树遍历算法的实现 68． 哈夫曼编码 70． 克鲁斯卡尔算法求图的最小生成树 69． Prim算法的实现 输入一个含有十个结点的无向图，用prim算法生成一颗最小生成树并显示。 71． n元多项式乘法 (1) 界面友好，函数功能要划分好 (2) 总体设计应画一流程图 (3) 程序要加必要的注释 (4) 要提供程序测试方案 (5) 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。 72． 学生成绩管理程序 设计一个简单的学生成绩管理程序，要求根据菜单处理相应功能。 （1）管理功能包括列表、求平均成绩、查找最高分等。 （2）可按指定的性别或高于指定的个人平均分来筛选列表； （3）可按平均成绩排序； 22

数据结构与C语言综合训练习题集

（4）平均成绩可按个人或科目进行； （5）查找可按最高个人平均分进行，或按指定科目的最高分进行； （6）每个学生的信息包括：序号、学号、性别、成绩1、成绩2、成绩3、成绩4； （7）基本功能为：建立文件、增加学生记录、新建学生信息文件、删除/修改学生记录。 73． 数组操作 设计菜单处理程序，对一维数组进行不同的操作。 （1）操作项目包括求数组最大值、最小值、求和、求平均值、排序、 二分查找、有序插入； （2）设计并利用字符菜单进行操作项目的选择，程序一次运行可根据选择完成一项或多项操作；通过菜单“退出”来结束程序的运行； （3）数组的输入、输出可支持命令行输入文件名、界面输入文件名从数据文件中输入和输出；也支持界面录入。 打印指定年份的公历表和农历表。 （1）输入年份为1990～2050内任一年； （2）可以选择输出公历表或农历表； （3）农历表包括二十四节气。 74． 打印日历表 75． 学生证管理程序 该程序应该具有下列功能： (1) 通过键盘输入某位学生的学生证信息。学生证包含的信息请参看自己的学生证； (2) 给定学号，显示某位学生的学生证信息； (3) 给定某个班级的班号，显示该班所有学生的学生证信息； (4) 给定某位学生的学号，修改该学生的学生证信息； (5) 给定某位学生的学号，删除该学生的学生证信息； (6) 提供一些统计各类信息的功能。 76． 图书登记管理程序 该程序应该具有下列功能： (1) 通过键盘输入某本图书的信息； (2) 给定图书编号，显示该本图书的信息； 23

数据结构与C语言综合训练习题集

(3) 给定作者姓名，显示所有该作者编写的图书信息； (4) 给定出版社，显示该出版社的所有图书信息； (5) 给定图书编号，删除该本图书的信息； (6) 提供一些统计各类信息的功能。 77． 学生学分管理程序 假设每位学生必须完成基础课50学分、专业课50学分、选修课24学分、人文类课 程8学分、实验性课程20学分才能够毕业。因此在管理学分时，要考虑每个学分所属于的课程类别。 该程序应该具有下列功能： (1) 通过键盘输入某位学生的学分； (2) 给定学号，显示某位学生的学分完成情况； (3) 给定某个班级的班号，显示该班所有学生学分完成情况； (4) 给定某位学生的学号，修改该学生的学分信息； (5) 按照某类课程的学分高低进行排序； (6) 提供一些统计各类信息的功能。 假设某门课程一学期要留10次作业，每次老师要进行批改，给出分数后还要进行登记。学期期末要根据每次作业的成绩计算出最终的平时成绩（满分100）。 该程序应该具有下列功能： (1) 通过键盘输入某位学生某次作业的分数； (2) 给定学号，显示某位学生作业完成情况； (3) 给定某个班级的班号，显示该班所有学生的作业完成情况； (4) 给定某位学生的学号，修改该学生的作业完成信息； (5) 给定某位学生的学号，删除该学生的信息； (6) 提供一些统计各类信息的功能。 78． 作业完成情况管理程序 1 79． 旅店POS机管理系统 旅店收款POS机管理系统的简单实现。 （1）前台管理：包括空房分等级显示、入住登记、退房结算、洗衣房管理、娱乐项目管理； 24

数据结构与C语言综合训练习题集

（2）后台管理包括客房预定分析、营业额统计、日报表、月报表、年报表）； （3）设计数据结构文件来实现数据库管理，包括数据录入、查询、删除、修改、更新。 80． 学生通讯录管理系统 用链表方式来实现学生通讯录管理系统。 （1）通过定义一个包含学生通讯录（主要包括：学号、姓名、系别、专业、籍贯、家庭住址、联系电话等）的结构体类型，实现增加学生通讯录的内容、删除某个学生通讯录、输出全部学生通讯录内容、根据用户需求查找某个或某些学生的通讯录内容（如：按系别、专业、学号、姓名等内容进行查找）。 （2）能够实现以上给定的各项功能，具有方便简洁的操作界面，具有一定的容错性。 设计一个算法来完成两个超长正整数的乘法。 算法提示： 首先要设计一种数据结构来表示一个超长的正整数，然后才能够设计算法。 81． 超长正整数的乘法 82． 个人电话号码查询系统 问题描述：实现简单的个人电话号码查询系统，根据用户输入的信息（如姓名，身 份证号，电话号码、邮件地址等）进行快速查询。 基本要求： (1) 插入：实现将用户的信息插入到系统中；(2) 删除：删除某个用户的信息；(3) 修改：修改某个用户的信息；(4) 查询：根据姓名、身份证号等查询用户信息（包括简单条件查询，组合条件查询、模糊查询等）；(5) 排序：对于用户信息进行排序，提高查询速度；(6) 输出：输出用户信息。 提示： (1) 在内存中，设计数据结构存储电话号码的信息；在外存中，利用文件的形式来保存电话号码信息，系统运行时，将电话号码信息从文件调入内存来进行插入、查找等操作。 (2) 如果数据的插入删除频繁，可以考虑采取二叉排序树组织电话号码信息（也可采用较复杂的平衡二叉树），可以提高查找和维护的时间性能。 (3) 选择不同的排序和查找算法，尽可能提高查找和维护性能。 问题描述：利用哈夫曼编码，实现压缩和解压缩。 83． 哈夫曼编码 25

数据结构与C语言综合训练习题集

文件。通过对目录文件的管理达到“按名存取”的目的，目录文件常采用的组织结构是树型目录结构。 基本要求： 函数功能要划分好，程序要有必要的注释。 用户通过界面菜单选择以下操作： （1） 生成文件，选择路径和文件名，实现对文件的生成。 （2） 删除文件，对指定文件进行删除操作。 （3） 修改文件，对指定文件进行内容修改或者文件名修改。 （4） 输出该目录结构。 101． 简单算术表达式运算 给定简单的算术表达式，包括加减乘除括号这几种运算操作符，请计算表达式的值。 (1)能够正确处理加减乘除这四种运算； (2)能够正确处理括号运算； 实现提示： 首先将算术表达式转化成逆波兰式，然后针对逆波兰式进行运算。 布线区域分成m?n的方格阵列。要求确定连接方格s到方格d的最短布线方案。布主要功能： 线的时候，电路只能沿着直线或者直角布线，有障碍的方格做了封锁标记（X），其(1)从文件中读出题目他线路不允许穿过被封锁的方格。 的输入； (2)向屏幕上打印出题目的计算结果； 1 102． 机器人布线 1 31

数据结构与C语言综合训练习题集

(1)用文件保存布线区域，用1、0分别表示某个格子是否有障碍；S,D表示起点和终点； (2)给出最短的布线路径长度； (3)用文件保存布线路径，用*表示布线的方格； 103． 字符串距离 开发计算两个字符串间的编辑距离，LCS距离和N-gram距离的函数。 （1）编辑距离 字符串a和b的编辑距离ED(i,j)表示把字符串a转换成b所需要的最少操作次数，这些操作可以是：插入一个字符，删除一个字符，替换一个字符。显然，ED(i,j)越小，a，b越相似。ED(i,j)可按下列公式计算： 1 32

数据结构与C语言综合训练习题集

ED(0,0)?0ED(0,i)?ED(i,0)?i?ED(i?1,j?1)ED(i,j)???1?MIN(ED(i?1,j),ED(i,j?1),ED(i?1,j?1))ai?bjai?bj（2）LCS相似度 字符串a和b的LCS(Longest Common Subsequence)相似度是a和b间的最大相同子串的长度。显然LCS(i,j)越大，a，b越相似。a，b的LCS相似度定义如下： i?0或j?0?0?LCS(i,j)??1?LCS(i?1,j?1)ai?bj?MAX(LCS(i?1,j),LCS(i,j?1))ai?bj?（3）N-gram相似度 设Ngram(a) 是字符串a中长度为N的子串的集合。两个字符串a,b的N-gram相似度NG(a,b)定义如下： NG(a,b)?Ngram(a)?Ngram(b)Ngram(a)?Ngram(b)NG(a,b)越大，字符串a，b越相似。 104． 字符串操作 编写程序，不使用标准库函数，实现字符串的拷贝、拼接、字串查找、长度计算等函数。 (1)在不使用相关的标准库函数的情况下，完成本任务； (2)实现两个字符串拼接的函数strcat(str1, str2)； (3)实现字符串拷贝的函数strcpy(str1,str2)； (4)实现字符串查找的函数strcstr(str1,str2)； 1 33

数据结构与C语言综合训练习题集

(5)实现字符串长度计算的函数strlen(str1)； (6)实现字符串查找字符的函数strcchar(str1,c)； (7)实现字符串替换的函数strcreplacestr(str1,str2,str3)； (8)实现字符串替换字符的函数strcreplacechar(str1,str2,c)； 105． 集合操作 用单链表模拟有序集合，实现集合的加入一个元素、删除一个元素、集合的交、并、 差运算。 (1)用单链表存放集合中的元素，链表中的元素按大小存放； (2)实现集合加入一个元素删除一个元素的元素操作； (3)实现集合的交、并、差集合操作； 主要功能： (1)从文件中读出题目的输入； (2)向屏幕上打印出题目的计算结果； 1 106． 推箱子 1 推箱子是一个很经典的游戏.今天我们来玩一个简单版本.在一个5×5的房间里有一个箱子和一个搬运工,搬运工的工作就是把箱子推到指定的位置,注意,搬运工只能推箱子而不能拉箱子,因此如果箱子被推到一个角上那么箱子就不能再被移动了,如果箱子被推到一面墙上,那么箱子只能沿着墙移动.同时，房间里头还有若干障碍物（用阴影部分表示）。 现在给定房间的结构,箱子的位置,搬运工的位置和箱子要被推去的位置,请你计算出搬运工至少要推动箱子多少格. 34

数据结构与C语言综合训练习题集

(1)从文件中读出房间布局； (2)计算出推箱子的最小格数； 107． 跳马 在国际象棋中，马的走法与中车象棋类似，即俗话说的“马走日”，下图所示即国际象棋中马（K）在一步能到达的格子（其中黑色的格子是能到达的位置）。 主要功能： (1)从文件中读出题目的输入； (2)向屏幕上打印出题目的计算结果； 1 现有一200*200大小的国际象棋棋盘，棋盘中仅有一个马，给定马的当前位置（S）和目标位置（T），求出马最少需要多少跳才能从当前位置到达目标位置。 （1）输入：每一行有四个以空格分隔的整数，分别表示马当前位置及目标位置的横、纵坐标C（x,y）和G（x,y）。坐标由1开始。 （2）输出：对于每个测例，在单独的一行内输出一个整数，即马从当前位置跳到目标位置最少的跳数。 （3）输入样例： 1 1 2 1 输出样例：3 输入样例： 1 5 5 1 输出样例：4 108． 俄罗斯方块 龙哥小时候最爱的游戏就是俄罗斯方块了,当年他可是个高手,每次游戏他都会选择最快的速度,以至于根本来不及将方块转向而仅仅能够进行左右移动.为了能够坚持更久,必须尽可能地使\落下来方块\与\底下已有方块\上表面完全贴合.在熟悉掌握程序设计后龙哥想要用程序来模拟小时候玩俄罗斯方块的过程,下面请你来帮龙哥参谋一下吧:-) 主要功能： (1)从文件中读出题目的输入； (2)向屏幕上打印出题目的计算结果； 1 35

数据结构与C语言综合训练习题集

（1）输入包括两个部分： 1、落下来方块的矩阵(第一行两个小于5的整数a、b由空格隔开,从下一行开始是一个a行b列的矩阵,1表示方块,0表示空) 2、底下已有方块的矩阵(第一行两个小于10的整数c、d由空格隔开,从下一行开始是一个c行d列的矩阵,1表示方块,0表示空.输入底下已有方块矩阵时需确保不存在朝下的表面) （2）输出： 根据\落下来方块\和\底下已有方块\的形状,若\落下来方块\的下表面与\底下已有 36

数据结构与C语言综合训练习题集

方块\的上表面可能完全贴合则输出一行“YES”否则输出一行“NO” Sample Input 2 3 111 010 3 8 00100000 10100011 11110111 3 2 11 10 10 2 8 11001110 11011111 Sample Output YES NO 37

数据结构与C语言综合训练习题集

109． 棋盘问题 （OJ1255)在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。 输入：每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。 输出：对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。 输入样例： 2 1 #. .# 4 4 ...# ..#. .#.. #... 输出样例： 2 1 主要功能： (1)从文件中读出题目的输入； (2)向屏幕上打印出题目的计算结果； 1 38

数据结构与C语言综合训练习题集

110． 六数码问题 现有一两行三列的表格如下： A B C D E F 把1、2、3、4、5、6六个数字分别填入A、B、C、D、E、F格子中，每个格子一个数字且各不相同。每种不同的填法称为一种布局。如下： 1 3 5 2 4 6 布局1 2 5 6 4 3 1 布局2 定义α变换如下：把A格中的数字放入B格，把B格中的数字放入E格，把E格中的数字放入D格，把D格中的数字放入A格。 定义β变换如下：把B格中的数字放入C格，把C格中的数字放入F格，把F格中的数字放入E格，把E格中的数字放入B格。 问：对于给定的布局，可否通过有限次的α变换和β变换变成下面的目标布局： 1 2 3 4 5 6 输入：本题有多个测例， 第一行为输入测例的个数n，下面是n行测例，每个测例的输入是1到6这六个数字的一个排列，空格隔开，表示初始布局ABCDEF格中依次填入的数字。 输出：每个输出占一行。输出转换到目标格局需要变换的最少次数。（若不能转换则输出-1） 输入样例： 2 2 5 3 1 4 6 2 3 6 1 5 4 输出样例： 1 2 注意不能转换到目标格局的情况应输出-1； 输出格式为：printf(“%d\\n”,min); 39

数据结构与C语言综合训练习题集

111． 求图像的周长 （OJ1145）给一个用 . 和X表示的图形，图形在上、下、左、右、左上、左下、右主要功能： 上、右下8个方向都被看作是连通的，并且图像中间不会出现空洞，求这个图形的边(1)从文件中读出题目长。 的输入； (2)向屏幕上打印出题目的计算结果； 1 输入： 首先给出m、n、x、y四个正整数，下面给出m×n的图形，x、y表示点击的位置，全0表示结束。 输出： 点击的图形的周长。 输入样例： 2 2 2 2 XX XX 6 4 2 3 .XXX .XXX .XXX ...X ..X. X... 0 0 0 0 输出样例： 8 18 40

本文来源：https://www.bwwdw.com/article/znq7.html