《2022年数据结构C语言综合训练习题集29203》由会员分享,可在线阅读,更多相关《2022年数据结构C语言综合训练习题集29203(29页珍藏版)》请在金锄头文库上搜索。
1、个人资料整理仅限学习使用1 / 29 序号工程名称任务描述设计要求1身份证管理程序该程序应该具有下列功能:(1 通过键盘可以输入身份证信息,大量信息可存放在文件中。身份证包含的信息请参看自己的身份证;(2 给定身份证号码,显示其身份证信息;(3 给定省份的编号,显示该省的人数;(4 给定某区的编号,显示该区的人数;(5 给定身份证号码,可以修改该身份证信息;(6 给定身份证号码,可以删除该身份证信息;提供一些统计各类信息的功能。例如男女的人数、比例;以及哪年、哪月、哪日出生的人数等。界面要合理。2期刊论文管理程序该程序应该具有下列功能:(1 通过键盘输入某期刊论文的信息,也可以把大量期刊论文信
2、息放在文件中;(2 给定期刊论文的论文名称,显示该论文的作者信息,作者单位,发表期刊的名称;(3 给定作者姓名,显示所有该作者发表的期刊论文情况;(4 给定期刊名称,显示该期刊的所有论文信息;提供一些统计各类信息的功能。例如某人发表论文的个数,某期刊出版论文的个数等。3哈夫曼编码问题描述:利用哈夫曼编码,实现压缩和解压缩。基本要求:对于给定的一组字符,可以根据其权值进行哈夫曼编码,并能输出对应的哈夫曼树和哈夫曼编码;实现哈夫曼解码。提高要求:(1 能够分析文件,统计文件中出现的字符,统计字符出现的概率,再对文件进行编码,实现文件的压缩和解压缩。(2 能够对于文件的压缩比例进行统计。完成任务描述
3、中的各种功能,自己可以适当增加必要的功能。4运动会分数统计任务:参加运动会有n 个学校,学校编号为1n。比赛分成m个男子工程,和w个女子工程。工程编号为男子1m ,女子m+1 m+w 。不同的工程取前五名或前三名积分;取前五名的积分分别为:7、 5、3、2、1,前三名的积分分别为:5、3、2;哪些取前五名或前三名由学生自己设定。m=20,n可以输入各个工程的前三名或前五名的成绩;2能统计各学校总分,3可以按学校编号或名称、学校总分、男女团体总分排序输出;输出形式:有合理的提示,各学校分数为整形界面要求:有合理的提示,每个功能可以设立菜单,根据提示,可以完成相关的功能要求。存储结构:学生自己根据
4、系统功能要求自己设计,但是要求运动会的相关数据要存储在数据文件中。可以按学校编号查询学校某个工程的情况;可以按工程编号查询取得前三或前五名的学校。5数据存入文件并能随时查询6规定:输入数据形式和范围:可以输入学校的名称,运动工程的名称件的数据读写方法等相关内容在c 语言程序设计的书上,请自学解决)请在最后的上交资料中指明你用到的存储结构;测试数据:要求使用1、全部合法数据; 2、整体非法数据;3、局部非法数据。进行程序测试,以保证程序的稳定。测试数据及测试结果请在上交的资料中写明;5背包问题的求解假设有一个能装入总体积为T 的背包和n 件体积分别为w1 , w2 , , wn 的物品,能否从n
5、 件物品中挑选若干件恰好装满背包,即使w1 +w2 + + wn=T ,要求找出所有满足上述条件的解。例如:当T=10,各件物品的体积1 ,8, 4,3,5,2时,可找到下列4 组解:1,4,3,2)1,4,5)8,2)- 输入;3、通过程序,实现图的建立;4、联系人之间的关系浏览功能- 输出;5、查询和排序功能:( 至少一种查询方式算法1按与某个人的亲密程度升序或者降序排序2按亲密值的大小范围查询6、联系人信息的删除、修改功能( 任选项 。要求:设计合理的存储结构,设计界面,设计程序完成功能;11工作人员被访问频率统计系统通过此系统可以实现如下功能:1、系统以菜单的方式工作;2、首先从文件“
6、原始数据”中读入“人员”信息;3、计算访问频率,并输出频率值,以他们的访问频率为权重建立赫夫曼树;4、通过系统查询相关人员的信息,每次查询后都从新修正访问次数和访问频率;5、系统根据第 4)步得到的值对赫夫曼树进行修正;6、层序遍历赫夫曼树,并将访问结果写入“层序遍历”下“层序遍历.csv ”。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页,共 29 页个人资料整理仅限学习使用4 / 29 要求: 1、设计合理的存储结构,设计界面,设计程序完成功能; 2、人员信息包括:姓名,访问次数,访问频率; 3、通过窗体界面实现所有的功能12订票系统录
7、入:可以录入航班情况数据可以存储在一个数据文件中,数据结构、具体数据自定)查询:可以查询某个航线的情况 能够正确处理加减乘除这四种运算;(2 能够正确处理括号运算;首先将算术表达式转化成逆波兰式,针对逆波兰式进行运算。14失物招领系统通过此系统可以实现如下功能:1、系统以菜单的方式工作;2、系统内部维护“寻物.CSV”、“捡到物品.CSV”、“已归还物品.CSV”三张表;3、捡到物品时先在“寻物.CSV”中查询,若存在,删除该物品的信息;若不存在,把它记录到“捡到物品.CSV”文件中;4、已经被领走的物品,先把该物品的信息记录到“已归还物品.CSV”文件中,再从文件“捡到物品.CSV”中删除该
8、物品的信息;5、当有人来认领时,先在“捡到物品.CSV”表里查询,若没有找到,则在文件“寻物 .CSV”中记录下该物品的信息;要求: 1、设计合理的存储结构,设计界面,设计程序完成功能;2、通过窗体界面实现所有的功能;3、“捡到物品.CSV”表里每条记录包括:物品名称,捡到者的联系方式,捡拾时间、地点,值班人;4、已归还物品.CSV”表里的每条记录包括:物品名称,捡到者的联系方式,捡拾时间、地点,招领者的学号,联系方式,所在学院,专业,班级,招领时间,值班人;5、“寻物 .CSV”表里的每条记录包括:物品名称,丢失者的联系方式,丢失时间、地点,值班人。精选学习资料 - - - - - - -
9、- - 名师归纳总结 - - - - - - -第 4 页,共 29 页个人资料整理仅限学习使用5 / 29 6、自己建立所需的表。15集合操作用单链表模拟有序集合,实现集合的加入一个元素、删除一个元素、集合的交、并、差运算。(1 用单链表存放集合中的元素,链表中的元素按大小存放;(2 实现集合加入一个元素删除一个元素的元素操作;(3 实现集合的交、并、差集合操作;完成任务描述中的各种功能,自己可以适当增加必要的功能。16C 语言源程序代码 行 统 计 工 具codeCounter 编写程序,统计C语言源程序的代码。1. /* */ 和 / 的都认为是注释行2. 统计空行3. 非空非注释行,
10、基本上可以认为是有效的代码行如果同一行中有注释和代码的认为是代码行4, 统计总代码行数、注释行数、空行数5 输入: codeCounter filename/filepath 输出列表: filename 总代码行数、注释行、空行17实现链表按节点的数值域值升序排序的系统通过此系统可以实现如下功能:1、系统以菜单方式工作;2、每个节点包括三个域:next 、prior 、data ;3、根据输入的值构造出节点,并以头插的方式存储在链表里;4、输入完毕后,用相关菜单能实现将所有节点按数值域值升序排序,用prior指针域连接。5、能分别打印输出沿next 指向和沿prior指向的所有节点信息;要求
11、:设计合理的存储结构,设计界面,设计程序完成功能;存储空间有伸缩性;18一个简单的栈和队列的演示系统通过此系统可以实现如下功能:1、 系统以菜单的方式工作;2、 从窗体上输入相应的信息,能够生成对应的节点,分别保存到栈和队列里面;3、 通过相应的菜单实现,输出栈和队列里面的内容;4、 实现将栈置空、判空、弹栈、压栈基本操作;实现队列的置空、判空、入队、出队基本操作;要求: 1、设计合理的存储结构,设计界面,设计程序完成功能;2、所有功能均通过窗体界面实现,输出的内容显示在窗体上;19二叉树的重构和遍历系统通过此系统可以实现如下功能:1、系统以菜单的方式工作;2、能实现从已有文件中读入原二叉树的
12、后序遍历结果和中序遍历结果;要求:设计合理的存储结构,设计界面,设计程序完成功能;精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页,共 29 页个人资料整理仅限学习使用6 / 29 3、根据第(2 步的信息,重构出原来的二叉树,并将树的先序遍历结果输出到Output 目录的“先序遍历.CSV”文件中;4、可以将 Output 里的数据显示到窗体上。20多项式的加法和乘法实现系统通过此系统可以实现如下功能:1、从指定的 .csv文件读入多项式f(x 和 g(x 的系数和相应的指数信息;2、将多项式f(x 按照指数递增的顺序排列,并将结果写入f(
13、x 排序结果 .csv 文件中;3、将多项式g(x 按照指数递减的顺序排列,并将结果写入g(x 排序结果 .csv文件中;4、将两个多项式相加,结果写入多项式相加结果.csv 文件中;5、将两个多项式相乘,将结果写入多项式相乘结果.csv 文件中。要求:设计合理的存储结构,设计界面,设计程序完成功能;将最后的相加结果和相乘结果,以多项式的形式显示在自己设定的窗体界面上;21万 年 历 查 询 程序。实现万年历程序功能要求:1)提供菜单方式选择,假定输入的年份在1940-2040 年之间。2)输入一个年份,输出是在屏幕上显示该年的日历。3)输入年月,输出该月的日历。如:4)输入年份、月份、日期,
14、计算得到的是这一天据今天有多少天,星期几;5)输入公历的年月日,输出农历年月日。6)输入农历节气,输出当年农历的年月日及公历年月日。可以假定只涉及年份是1940 年到 2040 年。22学生成绩管理实现功能:输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出。23散列法的实验研究散列法中,散列函数构造方法多种多样,同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型的散列函数构造方精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页,共 29 页个人资料整理仅限学习使用7
15、 / 29 法,做实验观察,不同的解决冲突方法对查询性能的影响。24利用栈求表达式的值,可供小学生作业,并能给出分数。建立试卷库文件,随机产生n 个题目;题目涉及加减乘除,带括弧的混合运算;随时可以退出;保留历史分数,能回顾历史,给出与历史分数比较后的评价25个人电话号码查询系统实现简单的个人电话号码查询系统,根据用户输入的信息如姓名,身份证号,电话号码、邮件地址等)进行快速查询。基本要求:(1) 插入:实现将用户的信息插入到系统中;(2) 删除:删除某个用户的信息;(3) 修改:修改某个用户的信息;(4) 查询:根据姓名、身份证号等查询用户信息 在内存中,设计数据结构存储电话号码的信息;在外
16、存中,利用文件的形式来保存电话号码信息,系统运行时,将电话号码信息从文件调入内存来进行插入、查找等操作。(2 如果数据的插入删除频繁,可以考虑采取二叉排序树组织电话号码信息 选择不同的排序和查找算法,尽可能提高查找和维护性能。26单源最短路径求解给定一个带权有向图G=(V,E,其中每条边的权是一个非负实数。另外,还给定V中的一个顶点,成为源。现在计算从源到其他各顶点的最短路径。路径的长度是指路上各边权值之和。27散列表的设计与实现【问题描述】设计散列表实现电话号码查找系统。【基本要求】1设每个记录有下列数据项:电话号码、用户名、地址;2从键盘输入各记录,分别以电话号码和用户名为关键字建立散列表
17、;3采用一定的方法解决冲突;精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页,共 29 页个人资料整理仅限学习使用8 / 29 4查找并显示给定电话号码的记录;5查找并显示给定用户名的记录。【进一步完成内容】1系统功能的完善;2设计不同的散列函数,比较冲突率;3在散列函数确定的前提下,尝试各种不同类型处理冲突的方法,考察平均查找长度的变化。28数组编码和解码问题的求解设计与实现设有一个数组A: array0.N-1。存放的元素为0-N-1(1N 之间的整数,且。例如当N=6时,有: A=(4,3,0,5,1,2。此时,数组A的编码定义如下 :
18、 A0 编码为 0;Ai编码为:在A0,A1,Ai-1中比 Ai 的值小的个数(i=1,2,N-1 上面数组A的编码为: B=(0,0,0,3,1,2 要求如下:(1)给出数组A, 利用 C 求解 A的编码 . 给出数组A的编码后,求出A中原数据。29通讯录的制作本系统应完成一下几方面的功能:输入信息:调用此函数用以输入数据到内存中,此过程包括建立相应的链表或相应的数组,便于读取 显 示 信 息 : 用 以 显 示 输 入 的 数 据 , 包 括 从 内 存 中 读 出 和 从 磁 盘 中 读 出查找:以姓名作为关键字查找要找的信息 删 除 信 息 : 用 以 删 除 选 定 的 输 入 信
19、息 能比较迅速地找到储户的帐户,以实现存款、取款记账;精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页,共 29 页个人资料整理仅限学习使用9 / 29 2能比较简单,迅速地实现插入和删除,以实现开户和销户的需要。31排序方法的比较利用随机函数产生N个随机整数 至少采用三种方法实现上述问题求解统计每一种排序方法的性能如果采用4 种或 4 种以上的方法者,可适当加分。32学生成绩管理系统现有学生成绩信息文件11.txt),内容如下姓名学号语文数学英语张明明 01 67 78 82 李成友 02 78 91 88 张辉灿 03 68 82 56
20、王露 04 56 45 77 陈东明 05 67 38 47 . . . . . 学生成绩信息文件2实现对两个文件数据的合并,生成新文件3.txt 2 抽 取 出 三 科 成 绩 中 有 补 考 的 学 生 并 保 存 在 一 个 新 文 件4.txt 3对合并后的文件3.txt中的数据按总分降序排序( 至少采用两种排序方法实现 4输入一个学生姓名后, 能查找到此学生的信息并输出结果( 至少采用两种查找方法实现 5要求使用结构体, 链表实现上述要求. 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页,共 29 页个人资料整理仅限学习使用10
21、/ 29 33字符串操作编写程序,不使用标准库函数,实现字符串的拷贝、拼接、字串查找、长度计算等函数。(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 实现字符串替换字符的函数strcreplacech
22、ar(str1,str2,c;34集合操作用单链表模拟有序集合,实现集合的加入一个元素、删除一个元素、集合的交、并、差运算。(1 用单链表存放集合中的元素,链表中的元素按大小存放;(2 实现集合加入一个元素删除一个元素的元素操作;(3 实现集合的交、并、差集合操作;35找数字对输入 N2=N, 然后统计出这组数种相邻两数字组成的链环数字对出现的次数。例如:输入: 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 次 36二叉树遍历算法的实现四种
23、算法都是前序、中序、后序三种算法要求递归和非递归实现,层遍历用非递归实现。37哈夫曼编码根据输入文本中每个字符的权重,构建哈夫曼树,并生成对应的哈夫曼编码38Prim算 法 的 实现输入一个含有十个结点的无向图,用prim 算法生成一颗最小生成树并显示。39克鲁斯卡尔算法求图的最小生成树任务:用邻接矩阵实现图的遍历,并用克鲁斯卡尔算法求图的最小生成树40n 元多项式乘法(1 界面友好,函数功能要划分好(2 总体设计应画一流程图(3 程序要加必要的注释精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页,共 29 页个人资料整理仅限学习使用11
24、/ 29 (4 要提供程序测试方案(5 程序一定要经得起测试,宁可功能少一些,也要能运行起来,不能运行的程序是没有价值的。41学生成绩管理程序设计一个简单的学生成绩管理程序,要求根据菜单处理相应功能。1)管理功能包括列表、求平均成绩、查找最高分等。2)可按指定的性别或高于指定的个人平均分来筛选列表;3)可按平均成绩排序;4)平均成绩可按个人或科目进行;5)查找可按最高个人平均分进行,或按指定科目的最高分进行;6)每个学生的信息包括:序号、学号、性别、成绩1、成绩 2、成绩 3、成绩 4;7)基本功能为:建立文件、增加学生记录、新建学生信息文件、删除/ 修改学生记录。42数组操作设计菜单处理程序
25、,对一维数组进行不同的操作。1)操作工程包括求数组最大值、最小值、求和、求平均值、排序、二分查找、有序插入;2)设计并利用字符菜单进行操作工程的选择,程序一次运行可根据选择完成一项或多项操作;通过菜单“退出”来结束程序的运行;每种书的登记内容包括书号、书名、著作者、现存量和库存量;2对书号建立索引表系统主要功能如下:* 采编入库:新购一种书,确定书号后,登记到图书帐目表中,如果表中已有,则只将库存量增加;* 借阅:如果一种书的现存量大于0,则借出一本,登记借阅者的书证号和归还期限,改变现存量;*归还:注销对借 阅者的登记,改变该书的现存量。【进一步完成内容】精选学习资料 - - - - - -
26、 - - - 名师归纳总结 - - - - - - -第 11 页,共 29 页个人资料整理仅限学习使用12 / 29 1系统功能的进一步完善;2索引表采用树表。44学生搭配问题一班有m 个女生 , 有 n 个男生 (m 不等于n, 现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上. 每曲开始时 , 依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴. 请设计一系统模拟动态地显示出上述过程, 要求如下 : 1输出每曲配对情况2计算出任何一个男生( 编号为X和任意女生 ( 编号为Y, 在第K 曲配对跳舞的情况. 至少求出K的两个值 . 3尽量设计出多种算法及程序,
27、可视情况适当加分提示 : 用队列来解决比较方便.45图书登记管理程序该程序应该具有下列功能:(1 通过键盘输入某本图书的信息;(2 给定图书编号,显示该本图书的信息;(3 给定作者姓名,显示所有该作者编写的图书信息;(4 给定出版社,显示该出版社的所有图书信息;(5 给定图书编号,删除该本图书的信息;(6 提供一些统计各类信息的功能。46学生学分管理程序假设每位学生必须完成基础课50 学分、专业课50 学分、选修课24 学分、人文类课程8 学分、实验性课程20 学分才能够毕业。因此在管理学分时,要考虑每个学分所属于的课程类别。该程序应该具有下列功能:(1 通过键盘输入某位学生的学分;(2 给定
28、学号,显示某位学生的学分完成情况;(3 给定某个班级的班号,显示该班所有学生学分完成情况;(4 给定某位学生的学号,修改该学生的学分信息;(5 按照某类课程的学分高低进行排序;(6 提供一些统计各类信息的功能。47作业完成情况管理程序假设某门课程一学期要留10 次作业,每次老师要进行批改,给出分数后还要进行登记。学期期末要根据每次作业的成绩计算出最终的平时成绩 通过键盘输入某位学生某次作业的分数;(2 给定学号,显示某位学生作业完成情况;(3 给定某个班级的班号,显示该班所有学生的作业完成情况;(4 给定某位学生的学号,修改该学生的作业完成信息;(5 给定某位学生的学号,删除该学生的信息;(6
29、 提供一些统计各类信息的功能。48旅店 POS机管理系统旅店收款POS机管理系统的简单实现。1)前台管理:包括空房分等级显示、入住登记、退房结算、洗衣房管理、娱乐工程管理;2)后台管理包括客房预定分析、营业额统计、日报表、月报表、年报表);3)设计数据结构文件来实现数据库管理,包括数据录入、查询、删除、修改、更新。49学生通讯录管理系统用链表方式来实现学生通讯录管理系统。1)通过定义一个包含学生通讯录主要包括:学号、姓名、系别、专业、籍贯、家庭住址、联系电话等)的结构体类型,实现增加学生通讯录的内容、删除某个学生通讯录、输出全部学生通讯录内容、根据用户需求查找某个或某些学生的通讯录内容 如:按
30、系别、专业、学号、姓名等内容进行查找)。2)能够实现以上给定的各项功能,具有方便简洁的操作界面,具有一定的容错性。50超长正整数的加法利用双向循环链表,设计一个实现任意长的整数进行加法运算的演示程序。要求输入和输出每四位一组,组间用逗号隔开。如:1,0000,0000, 0000,0000。提高要求:完成两个超长正整数的乘法。51个人电话号码查询系统问题描述:实现简单的个人电话号码查询系统,根据用户输入的信息 插入:实现将用户的信息插入到系统中;(2 删除:删除某个用户的信息; (3 修改:修改某个用户的信息;(4 查询:根据姓名、身份证号等查询用户信息 排序:对于用户信息进行排序,提高查询速
31、度;(6 输出:输出用户信息。提示:(1 在内存中,设计数据结构存储电话号码的信息;在外存中,利用文件的形式来保存电话号码信息,系统运行时,将电话号码信息从文件调入内存来进行插入、查找等操作。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页,共 29 页个人资料整理仅限学习使用14 / 29 (2 如果数据的插入删除频繁,可以考虑采取二叉排序树组织电话号码信息 选择不同的排序和查找算法,尽可能提高查找和维护性能。52哈夫曼编码问题描述:利用哈夫曼编码,实现压缩和解压缩。基本要求:对于给定的一组字符,可以根据其权值进行哈夫曼编码,并能输出对应
32、的哈夫曼树和哈夫曼编码;实现哈夫曼解码。提高要求:(1 能够分析文件,统计文件中出现的字符,再对文件进行编码,实现文件的压缩和解压缩。(2 能够对于文件的压缩比例进行统计。(3 能够打印文件。53订票系统基本要求:(1 录入:可以录入航班情况 查询:可以查询某个航线的情况 可以输入起飞抵达城市,查询飞机航班情况;(4 订票: 修改航班信息:当航班信息改变可以修改航班数据文件。54学籍管理系统问题描述:建立学籍管理系统,实现对于学生信息的添加和维护管理。基本要求:完成学籍登记表中的下面功能登记表中包括学号、姓名、性别、出生日期、政治面貌、联系方式、家庭住址等信息)。 插入:将某学生的基本信息插入
33、到登记表中; 删除:将满足条件的基本信息删除; 修改:对基本信息的数据项进行修改; 查询:查找满足条件的学生; 输出:将登记表中的全部或满足条件)基本信息输出。提高要求:可以添加课程信息求出此数x 的 10 进制值 实现对 x 向任意的一个非M进制的数的转换。3至少用两种或两种以上的方法实现上述要求用栈解决,用数组解决,其它方法解决)。56稀疏矩阵的应用实现三元组表下的稀疏矩阵的加、转、乘的实现。1)把给定的稀疏矩阵用为三元组表示;同时把三元组转换为稀疏矩阵形式。2)稀疏矩阵加法3)矩阵乘法4)矩阵转置57文章编辑输入一页文字,程序可以统计出文字、数字、空格的个数。静态存储一页文章,每行最多不
34、超过80 个字符。要求:1)分别统计出其中英文字母数和空格数及整篇文章总字数;2)统计某一字符串在文章中出现的次数,并输出该次数; 分行输出用户输入的各行字符;(2 分 4 行输出 全部字母数 、 数字个数 、空格个数 、文章总字数 (3 输出删除某一字符串后的文章;58拓扑排序建立有向无环图,并输出拓扑的序列. 59图的遍历及用克任务:用邻接矩阵实现图的遍历,并用克鲁斯卡尔算法求图的最小生成树精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页,共 29 页个人资料整理仅限学习使用16 / 29 鲁斯卡尔算法求图的最小生成树60公园的导游图给
35、出一张某公园的导游图,游客通过终端询问可知:从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口出口就在入口旁边)。分步实施:5、 初步完成总体设计,建好框架,确定人机对话的界面,确定函数个数;6、 完成最低要求:建立一个文件,包括5 个景点情况,能完成遍历功能;7、 进一步要求:进一步扩充景点数目,画出景点图,有兴趣的同学可以自己扩充系统功能。61商店存货管理系统建立一商店存货管理系统,要求每次出货时取进货时间最早且最接近保质期中止时间的货物。分步实施:1)初步完成总体设计,建好框架,确定人机对话的界面,确定函数个数;2)完成最低要求
36、:建立一个文件,包括5 个种类的货物情况,能对商品信息进行扩充 追加),修改和删除以及简单的排序;0 个人按顺时针方向围坐一圈,每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m ,从第一个人开始顺时针方向自1 起顺序报数,报到m时停止报数,报m的人出列,将他的密码作为新的m值,从他的下一个人开始重新从1 报数。如此下去,直到所有人全部出列为止。令n 最大值取30。要求设计一个程序模拟此过程,求出出列编号序列。要求:用数组和链表分别实现。63二叉树遍历算法的实现四种算法都是前序、中序、后序三种算法要求递归和非递归实现,层序遍历用非递归实现,应包含建树的实现。64链表的综合算法设计设有
37、一职工文件,其结构为:职工号(no 、姓名 (name、部门号 (depno 、工资数(salary、职工号指针(pno 、部门号指针(pdepno 、工资数指针(psalary,设计一程序,从一文件中读取记录到单链表中,并完成如下功能:(1 输入:添加一个职工记录;(2 输出:输出全部职工记录;(3 按 no 排序:通过pno 指针将职工记录按no 从小到大链接起来;(4 按 no 输出:沿pno 链输出全部职工记录;(5 按 depno 排序:通过pdepno 指针将职工记录按depno 从小到大链接起精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - -
38、-第 16 页,共 29 页个人资料整理仅限学习使用17 / 29 来;(6 按 depno 输出:沿 pdepno 链输出全部职工记录;(7 按 salary排序:通过psalary指针将职工记录按salary从小到大链接起来;(8 按 salary输出:沿psalary链输出全部职工记录;(9 全清:删除职工文件中的全部记录;(10 存贮退出:将单链表中的全部结点存贮到职工文件中,然后退出程序运行。65哈希表的设计与实现设计一个哈希表,实现个人电话号码查询系统基本要求:(1) 设每个记录有下列数据项:电话号码、用户名、用户住址;(2) 从键盘输入各记录,分别以电话号码和用户名为关键字建立哈
39、希表;a)设计不同的哈希函数,比较冲突率;b 在哈希函数确定的前提下,尝试各种不同类型处理冲突的方法,考察平均查找长度的变化。(3)查找并显示给定电话号码/用户名的记录;66关键路径问题基本要求:1)对一个描述工程的AOE网,建立其存储结构;注:数据的输入可以是键盘输入或文件输入两种方式)2)判断该AOE网是否能够顺利进行。3)若该工程能顺利进行,输出完成整项工程至少需要多少时间,以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。注:结果的输出可以是屏幕输出和文件输出两种方式)67邮路问题问题描述:一个邮递员从邮局选好邮件去投递,然后回到邮局。当然他必须经过他所管辖的每条街至少一
40、次。请为他设计一条投递路线,使其所行的路程尽可能地短。基本要求:精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页,共 29 页个人资料整理仅限学习使用18 / 29 2)按照输入邮局所在位置,为邮递员设计一条最佳投递路线,要能考虑到辖区一般情况。 界面友好,函数功能要划分好(2 总体设计应画一流程图(3 程序要加必要的注释(4 要提供程序测试方案(5 程序一定要经得起测试,宁可功能少一些,也要能运行起来,不能运行的程序是没有价值的。69文件目录管理系统问题描述:文件是管理用户信息和应用程序的一种工具。每个文件有唯一的文件名,可以通过文件名访
41、问文件,同时可对文件进行生成、删除及文件名修改等操作。文件系统对若干文件进行管理时将所有的文件目录组合在一起构成一个目录文件。通过对目录文件的管理达到“按名存取”的目的,目录文件常采用的组织结构是树型目录结构。基本要求:函数功能要划分好,程序要有必要的注释。用户通过界面菜单选择以下操作:(1)生成文件,选择路径和文件名,实现对文件的生成。(2)删除文件,对指定文件进行删除操作。(3)修改文件,对指定文件进行内容修改或者文件名修改。(4)输出该目录结构。70简单算术表达式运算给定简单的算术表达式,包括加减乘除括号这几种运算操作符,请计算表达式的值。(1 能够正确处理加减乘除这四种运算;(2 能够
42、正确处理括号运算;实现提示:首先将算术表达式转化成逆波兰式,然后针对逆波兰式进行运算。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页,共 29 页个人资料整理仅限学习使用19 / 29 71机器人布线布线区域分成的方格阵列。要求确定连接方格s 到方格d 的最短布线方案。布线的时候,电路只能沿着直线或者直角布线,有障碍的方格做了封锁标记 用文件保存布线区域,用1、0 分别表示某个格子是否有障碍;S,D 表示起点和终点;(2 给出最短的布线路径长度;(3 用文件保存布线路径,用* 表示布线的方格;主要功能:(1 从文件中读出题目的输入;(2
43、向 屏 幕 上 打 印 出 题 目 的 计 算 结果;72图的遍历的实现要求:1先任意创建一个图;2图的 DFS,BFS的递归和非递归算法的实现3要求用有向图和无向图分别实现4要求用邻接矩阵、邻接表多种结构存储实现73线索二叉树的应用要求:实现线索树建立、插入、删除、恢复线索的实现。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页,共 29 页个人资料整理仅限学习使用20 / 29 74二叉平衡排序树问题描述:从一棵空树开始创建,在创建过程中,保证树的有序性,同时还要针对树的平衡性做些调整。最终要把创建好的二叉排序树转换为二叉平衡排序树。基
44、本要求: 1. 创建 主要功能:(1 从文件中读出题目的输入;(2 向 屏 幕 上 打 印 出 题 目 的 计 算 结果;精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页,共 29 页个人资料整理仅限学习使用21 / 29 2、底下已有方块的矩阵( 第一行两个小于10 的整数c、d 由空格隔开 , 从下一行开始是一个c 行 d 列的矩阵 ,1 表示方块 ,0 表示空 . 输入底下已有方块矩阵时需确保不存在朝下的表面 2)输出:根据 落下来方块 和 底下已有方块 的形状 , 若落下来方块 的下表面与 底下已有方块 的上表面可能完全贴合则输出一
45、行“YES ”否则输出一行“NO ”Sample Input 2 3 111 010 3 8 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页,共 29 页个人资料整理仅限学习使用22 / 29 00100000 10100011 11110111 3 2 11 10 10 2 8 11001110 11011111 Sample Output YES NO 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页,共 29 页个人资料整理仅限学习使用23 / 29 78六数码问题现有一两行三列
46、的表格如下: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 输入:
47、本题有多个测例,第一行为输入测例的个数n,下面是n 行测例,每个测例的输入是1 到 6 这六个数字的一个排列,空格隔开,表示初始布局 ABCDEF 格中依次填入的数字。输出:每个输出占一行。输出转换到目标格局需要变换的最少次数。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页,共 29 页个人资料整理仅限学习使用24 / 29 79算 24 每局 4个整数,运用四则运算可以加括号),但为了降低程序设计的难度,除法的结果只保留整数部分,即5/2=2 。给出计算出 24的方法。输入:本题包含多个测例。数据的第一行有一个整数N 从文件中读出题目的
48、输入;(2 向 屏 幕 上 打 印 出 题 目 的 计 算 结果;80城市之间Vela 在玩游戏时遇到麻烦了,需要你帮忙:这个游戏有M个城市,有的城市有传送点,可以直接到达另外一些城市,如a23表示可以从城市2直接到达3。无法直接到达的城市,有的可以通过某些城市中转到达。Vela 在城市 X ,她想知道是否可以到达某城市Z。输入:此题第一行输入N表示城镇数目 (N 为小于 10的正整数 ;从第二行开始输入一个 N*N的矩阵,若amk=1(0=m,k,就可以从城市m直接到达k,否则不可以直接到达。第N+2行输入两个数字P,Q。输出:如果可以从P到达 Q ,输出 1,否则输出 0。输入样例:3 1
49、 1 0 0 1 1 0 0 1 0 2 输出样例:1 提示: 0不能直接到达 2,但可以先到达1,再从 1到达 2。主要功能:(1 从文件中读出题目的输入;(2 向 屏 幕 上 打 印 出 题 目 的 计 算 结果;精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 24 页,共 29 页个人资料整理仅限学习使用25 / 29 81算 12 。主要功能:(1 从文件中读出题目的输入;(2 向 屏 幕 上 打 印 出 题 目 的 计 算 结果;82树转换为二叉树树和二叉树是两种不同的数据结构,树实现起来比较麻烦,二叉树实现起来比较容易,因此可以通过把树
50、转换为二叉树进行处理,处理完后在从二叉树还原为树。树和二叉树的定义及转换请参考清华版数据结构 )要求: a: 实现树与二叉树的相互转换。b: 树的前序、后序的递归遍历。c: 包含树的创建。83本班同学通讯录设计要求:小巧实用,具有添加,查询和删除功能。姓、名、英文名、QQ号、电子邮箱、籍贯、电话号码组成,姓名可以由字符和数字混合编码。电话号码可由字符和数字组成。实现功能为:系统以菜单方式工作、信息录入功能、信息浏览功能。输入个人关键字信息电话 / 籍贯 /QQ号/ 邮箱等,)能实现查询功能、信息修改功能、系统退出功能。84模拟银行自动取款机程序要求: 1. 要能开户 2.模拟一个账户:1000
51、1 10002 3.工商银行的账号:6222020200003518966 4.验证客户信息 : 请输入密码 6位密码 5.显示子菜单,例如= 中国银行西北农科大支行支行行长: XXX 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 25 页,共 29 页个人资料整理仅限学习使用26 / 29 = 1. 存款 4.密码重置2. 取款 5.其他业务3. 转账 6.退出= 85打字测试系统设计要求: 1.可以练习中文,英文,字符 2.可以自己设定文件内容 3.打完需要系统给出正确率、错误率、每分钟打字的速度。提示:可以通过文件I/O 操作,从文件中读取
52、要练习的篇幅。字符串文件 I/O 等知识的综合应用。86最小生成树问题(1)根据普里姆算法思想,画出构造该无向带权图最小生成树的过程。根据克鲁斯卡尔算法思想,画出构造该无向带权图最小生成树的过程。87设计 C 语言实现字符统计设计C 语言实现字符统计,统计一段用户输入的文字中包含的英文字符数、数字、空格及其他类型字符数88. 排班系统学校实验楼有7 名保安人员:钱、赵、孙、李、周、吴、陈。由于工作需要进行轮休制度,一星期中每人休息一天。预先让每一个人选择自己认为合适的休息日。请编制程序,打印轮休的所有可能方案。当然使每个人都满意,例如每人选择的休息日如下:钱:星期一、星期六赵:星期二、星期四孙
53、:星期三、星期日李:星期五周:星期一、星期四、星期六吴:星期二、星期五陈:星期三、星期六、星期日运行结果 : Solution: 1 赵 钱 孙 李 周 吴 陈= 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 26 页,共 29 页个人资料整理仅限学习使用27 / 29 星期四星期一星期三星期五星期六星期二星期日Solution: 2 赵 钱 孙 李 周 吴 陈= 星期四星期一星期日星期五星期六星期二星期三Solution: 3 赵 钱 孙 李 周 吴 陈= 星期四星期六星期三星期五星期一星期二星期日Solution: 4 赵 钱 孙 李 周 吴
54、 陈= 星期四星期六星期日星期五星期一星期二星期三89学生选课系统假定有n 门课程,每门课程有课程编号,课程名称,课程性质,学时,授课学时,实验或上机学时,学分,开课学期等信息,学生可按要求如总学分不得少于15 自由选课。试设计一个选修课程系统,使之能提供以下功能:1)系统以菜单方式工作 2)课程信息和学生选课信息录入功能课程信息用文件保存)3)课程信息浏览功能4)查询功能5)按学分查询6)某门课程学生选修情况可选项)90机房收费管理系统1)输入功能:输入30 名学生的学号、班级、姓名、上机起始时间。2)计算功能:计算每个下机学生的上机费用,每小时1 元。上机费用 =上机时间 * 1.0/h
55、,不足一小时按一小时计算)3)查询功能:按条件班级、学号、姓名)显示学生的上机时间。4)机器使用情况的显示显示方式不限但要一目了然)精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 27 页,共 29 页个人资料整理仅限学习使用28 / 29 91班级成绩管理系统对一个有N 个学生的班级,每个学生有M 门课程。该系统实现对班级成绩的录入、显示、修改、排序、保存等操作的管理。功能要求:1)本系统采用一个结构体数组,每个数据的结构应当包括:学号、姓名、M 门课程名称。2)本系统显示这样的菜单:请选择系统功能项:a、成绩录入b、成绩显示c、成绩保存d、成绩
56、排序e、成绩修改 要求先输入密码)f 、成绩统计92机房机位预定系统20 台机器,编号1 到 20,从早八点到晚八点。两小时一个时间段,每次可预定一个时间段。功能要求:1)系统以菜单方式工作2)查询,根据输入时间,输出机位信息。3)机位预定,根据输入的时间查询是否有空机位,若有则预约,若无则提供最近的时间段,另:若用户在非空时间上机,则将用户信息列入等待列表。4)退出预定,根据输入的时间,机器号撤销该事件的预定!5)查询是否有等待信息,若有则提供最优解决方案等待时间尽量短),若无则显示提示信息。93西北农科大学员嘉年华抽奖系统1. 把学生姓名保存在数组中2. 随机抽取幸运的学生进行奖励3. 预
57、留文件保存的接口保存幸运学生名单)4. 三等奖 IPOD4 8G 5. 二等奖 IPHONE4S 16GB WIFI 6. 一等奖 IPAD2 16GB WIFI 3G 7. 特等奖苹果 MACBOOK PRO 15.4 94简单的超市收银系统设计简单的超市收银系统,应该具有收款过程,货物清单,货物种类和数量等基本功能精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 28 页,共 29 页个人资料整理仅限学习使用29 / 29 95歌手比赛系统对一次歌手比赛的成绩进行管理,功能要求:1、输入每个选手的数据包括编号、姓名、十个评委的成绩,根据输入计算出总成绩和平均成绩去掉最高分,去掉最低分)。 2、显示主菜单如下:1)输入选手数据 2 )评委打分 3 )成绩排序按平均分) 4)数据查询 5 )追加学生数据 6 )写入数据文件7)退出系统。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 29 页,共 29 页