数据结构课程设计

安徽农业大学·信息与计算机学院·《数据结构课程设计》

24. 二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。（限1 人完成）

要求：遍历的内容应是千姿百态的。

五、树与二叉树的转换的实现。以及树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。 要求：遍历的内容应是千姿百态的。

25. 学生搭配问题（限1 人完成）

一班有m个女生，有n个男生(m不等于n)，现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时，依次从男生和女生中各出一人配对跳舞，本曲没成功配对者坐着等待下一曲找舞伴。

请设计一系统模拟动态地显示出上述过程,要求如下： 1) 输出每曲配对情况

2) 计算出任何一个男生(编号为X)和任意女生(编号为Y)，在第K曲配对跳舞的情况.至少求出K的两个值。

3) 尽量设计出多种算法及程序，可视情况适当加分 提示：用队列来解决比较方便。

26. 敢死队问题（限1 人完成） 有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。

排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。

要求：至少采用两种不同的数据结构的方法实现。如果采用三种以上的方法者，可加分。

27. 猴子吃桃子问题（限1 人完成）

有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。

要求：

1) 采用数组数据结构实现上述求解 2) 采用链数据结构实现上述求解 3) 采用递归实现上述求解

第 13 页 共 30 页

安徽农业大学·信息与计算机学院·《数据结构课程设计》

4) 如果采用4种方法者,适当加分

28. 数制转换问题（限1 人完成）

任意给定一个M进制的数x ，请实现如下要求 1) 求出此数x的10进制值（用MD表示） 2) 实现对x向任意的一个非M进制的数的转换。

3) 至少用两种或两种以上的方法实现上述要求（用栈解决，用数组解决，其它方法解决）。

29. 排序综合（限1 人完成） 利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。 要求：

1) 至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。

2) 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。

3) 如果采用4种或4种以上的方法者，可适当加分。

30. 学生成绩管理系统（限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.txt），内容如下： 姓名 学号 语文 数学 英语 陈果 31 57 68 82 李华明 32 88 90 68 张明东 33 48 42 56 李明国 34 50 45 87 陈道亮 35 47 58 77 …. .. .. .. … 试编写一管理系统,要求如下：

第 14 页 共 30 页

安徽农业大学·信息与计算机学院·《数据结构课程设计》

1) 实现对两个文件数据进行合并，生成新文件3.txt

2) 抽取出三科成绩中有补考的学生并保存在一个新文件4.txt

3) 对合并后的文件3.txt中的数据按总分降序排序(至少采用两种排序方法实现)

4) 输入一个学生姓名后，能查找到此学生的信息并输出结果(至少采用两种查找方法实现) 5) 要求使用结构体，链或数组等实现上述要求。 6) 采用多种方法且算法正确者,可适当加分。

31. 图的遍历和生成树求解实现（限1 人完成） 要求：

1) 先任意创建一个图；

2) 图的DFS,BFS的递归和非递归算法的实现

3) 最小生成树（两个算法）的实现，求连通分量的实现 4) 要求用邻接矩阵、邻接表、十字链表多种结构存储实现

32. 线索二叉树的应用（限1 人完成）

要求：实现线索树建立、插入、删除、恢复线索的实现。

33. 稀疏矩阵应用（限1 人完成）

要求：实现三元组，十字链表下的稀疏矩阵的加、转、乘的实现。

34. 树的应用（限1 人完成）

要求：实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。

第 15 页 共 30 页

安徽农业大学·信息与计算机学院·《数据结构课程设计》

附录C课程设计实验报告格式

数据结构课程设计

报 告

班 级： 学 号： 姓 名： 指导老师：

信息与计算机学院 二○一○ 年 六 月

第 16 页 共 30 页