2022年程序设计语言、数据结构课程设计 .pdf

《2022年程序设计语言、数据结构课程设计 .pdf》由会员分享，可在线阅读，更多相关《2022年程序设计语言、数据结构课程设计 .pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1、关键路径问题（限 1 人完成）问题描述 ：设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。基本要求：（1）对一个描述工程的AOE 网，应判断其是否能够顺利进行。（2）若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。 2、学生成绩管理系统（限1 人完成）现有学生成绩信息文件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、2.txt ）,内容如下 : 姓名学号语文数学英语陈果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)要求使用结构体,链或数组等实现上述要求. 3、飞机订票系统（限1 人完

3、成）任务：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号， 查询起降时间， 起飞抵达城市， 航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；订票： （订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -

4、 - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 当航班信息改变可以修改航班数据文件要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能； 4、树的应用（限1 人完成）要求：实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。5、宿舍管理查询软件（限1 人完成）1)任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：A.采用交互工作方式B.建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种 ) 2)查询菜

5、单 : (用二分查找实现以下操作) A.按姓名查询B.按学号查询C.按房号查询3)打印任一查询结果（可以连续操作）6、.哈夫曼编码 /译码器（限1 人完成）【问题描述】设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。【基本要求】1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 2)分别采用动态和静态存储结构3)初始化：键盘输入字符集大小n、n 个字符和n 个权值，建立哈夫曼树；4)编码：利用建好的哈夫曼树生成哈夫曼编码；5)输出编码；6)设字符集及频度如下表：字符空格A B C D E F G H I J K L M 频度1

6、86 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)界面设计的优化。7、散列表的设计与实现（限1 人完成）【问题描述】设计散列表实现电话号码查找系统。【基本要求】1)设每个记录有下列数据项：电话号码、用户名、地址；2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3)采用一定的方法解决冲突；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - -

7、 - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - 4)查找并显示给定电话号码的记录；5)查找并显示给定用户名的记录。【进一步完成内容】1)系统功能的完善；2)设计不同的散列函数，比较冲突率；3)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。8、动态链表结构下的一元多项式的加法、减法、乘法的实现。（限 1 人完成）设有一元多项式Am(x)和 Bn(x). Am(x)=A0+A1x1+A2x2+A3x3+ +AmxmBn(x)=B0+B1x1+B2x2+B3x3+ +Bnxn请实

8、现求M(x)= Am(x)+Bn(x) 、M(x)= Am(x)-Bn(x)和 M(x)= Am(x) Bn(x)。要求：1)首先判定多项式是否稀疏2)分别采用顺序和动态存储结构实现；3)结果 M(x) 中无重复阶项和无零系数项；4)要求输出结果的升幂和降幂两种排列情况9、利用随机函数产生N 个随机整数（ 20000 以上），对这些数进行多种方法进行排序。要求：至少采用三种方法实现上述问题求解（提示， 可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。10、 图的遍历的实现（限1 人完成）要求：1)先任意创建一个图；2)图的

9、 DFS,BFS 的递归和非递归算法的实现3)要求用有向图和无向图分别实现4)要求用邻接矩阵、邻接表多种结构存储实现11、 .稀疏矩阵应用（限1 人完成）要求：实现三元组，十字链表下的稀疏矩阵的加、转实现。（1）稀疏矩阵的存储（2）稀疏矩阵加法（3）矩阵转置12、 串的查找和替换（限 1 人完成）问题描述： 打开一篇英文文章，在该文章中找出所有给定的单词，然后对所有给定的单词替换为另外一个单词，再存盘。13、 约瑟夫环（限 1 人完成）问题描述： 编号为 1，2 n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m， 从第一个人开始按顺时针方

10、向自1 开始顺序报数，报到 m 时停止报数，报m 的人出列，将他的密码作为新的m 值，从他的顺时针方向上的下一个开始重新从1 报数， 如此下去， 直至所有人全部出列为止，设计一个程序求出出列顺序。基本要求：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 1、利用单循环链表作为存储结构模拟此过程；2、键盘输入总人数、初始报数上限值m 及各人密码；3、按照出列顺序输出各人的编号。14、 .构造可以使n 个城市连接的最小生成树（限 1

11、 人完成）问题描述： 给定一个地区的n 个城市间的距离网，用Prim 算法或Kruskal 算法建立最小生成树，并计算得到的最小生成树的代价。基本要求：1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。2、表示城市间距离网的邻接矩阵（要求至少6 个城市， 10 条边）3、最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。15、 迷宫问题（栈）问题描述：以一个 m*n 的长方阵表示迷宫，0 和 1 分别表

12、示迷宫中的通路和障碍。设计一个程序， 对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。基本要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（ i,j,d ）的形式输出，其中： （i,j ）指示迷宫中的一个坐标，d 表示走到下一坐标的方向， 如：对于下列数据的迷宫，输出的一条通路为： （1，1，1） ， （1,2,2）,(3,2,3),(3,1,2), 。测试数据：迷宫的测试数据如下：左下角（1，1）为入口，右下角（8，9）为出口。实现提示：计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某个方向进行探索，若能走通，则

13、继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设的迷宫没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1） ，出口点的下标为（n,n） 。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。16、 校园导航问题（限1 人完成）设计要求：设计你的学校的平面图，至少包括10 个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。17、二叉排序树的实现（限1 人完成）用顺序和二叉链表作存储结构1)以回车 (n)为输入结束标志,输入数列L，生成一棵二叉排序树 T；2)对二叉排序树T 作中序遍历，输出结果；3)输入元素x,查找二叉排序树T,若存在含x 的结点 ,则删除该结点 ,并作中序遍历(执行操作2)；否则输出信息“ 无 x” ；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -