2006年本科生数据结构上机实习题目

最珍贵的财富是时间，最大的浪费是虚度流年。
2006年本科生数据结构上机实习题目

题目：

1.猴子吃桃子问题
5只猴子一起摘了一堆桃子，因为太累，决定睡一觉后再来分桃，过了不知多久，第1只猴子先醒来，它见别的猴子没来，便将一堆桃子平均分成 5 份,结果多了1个，就将多的这个吃了，拿走其中的一堆。又过了不知多久，第二只猴子来了，它不知道有一个同伴已经来过，还以为自己是第一个，便将地上的桃子平均分成 5 份，发现也多了一个，同样吃了这一个，拿走其中的一堆。第3只，第4只，第5 只猴子都是这样......问这5只猴子至少摘了多少个桃子？
分析：设第n个猴子分的每堆有Xn个
则有这个关系式：
5*X(n+1)+1=4*Xn
所以：
X(n+1)==(4/5)^4*X1-(4/5)^3*(1/5)-(4/5)^2*(1/5)-(4/5)*(1/5)-(1/5)
用递归算法效率较高

2.在采用链式存储结构存储的二叉树上，以bt指向根接点，p指向任一给定的接点，编程实现求出从根接点到给定接点之间的路径。
分析：在二叉树上无论采用哪种遍历方法，都能够访问遍树中的所有结点。由于访问结点的顺序不同，前序遍历和中序遍历都很难达到设计的要求；但采用后序遍历二叉树是可行的，因为后序遍历是最后访问根结点，按这个顺序将访问过的结点存储到一个顺序栈中，然后 再输出即可。因此可以非递归地后序遍历二叉树bt，当后序遍历访问到结点*p时，此时栈stack中存放的所有结点均为给定结点*p的祖先，而由这些祖先便构成了一条从根结点到结点*p之间的路径。

3.设计一个公交查询系统，能让乘客查询从任一一个站点到另一站点之间的最短路径或最省钱路径或最省时路径。对于不同查询要求，可输入站点之间的路程或所需时间或所需费用。
分析：该题目分三部分，首先要建立公交网络图的存储结构；然后需要解决单源最短路径问题；最后实现两个站点之间的最短路径问题。


4.稳定婚姻问题
A是n个男子的集合，B是n个女子的集合，每个男子按自己的选择意愿将n个女子排成一列，同样的每个女子也将n个男子排成一列。将他们组成n对夫妇，如果存在这样一个男子和一个女子，这两人不是夫妇，但他们互相喜爱的程度胜于对自己配偶的喜爱，这样的n对夫妇称为不稳定婚姻。如果不存在这样的男子和女子，就称为稳定婚姻。问题就是要将这n个男子和n个女子组成稳定的n对夫妇。
(1)算法效率越高得分将会越高.

分析：该问题可抽象为：设有两个集合A和B，A的基数等于B，按照某种条件建立一个A到B的内射（即为A中的每一个元素，在B中恰好找一个与其搭配，而B中每一个元素，最多能与A中一个搭

配）。

二、 目标
结合课程学习与实践经验，进行实际的上机实践，掌握《数据结构》课程中的队列、二叉树、图及排序等内容，同时在实践中贯彻软件工程的思想。

一、 要求
a) 分组
自由结合，四人或五人一组。每组一名负责人。
b) 需要完成的文档
一、需求分析
二、概要设计
1.抽象数据类型
2.算法
三、详细设计
程序代码（含注释）
四、调试分析
调试过程中所做的工作，时间复杂度等
五、测试结果
输入数据和输出数据示例
六、说明（如果有）

编程语言：C语言或C++语言

二、 评分标准
程序准确、完整，60%
文档完整翔实（符合软件工程规范），30%
团队合作，10%
每推迟提交报告一天，扣10%，直到扣完止。

三、 作业提交
截止时间：2006-6-15上机课结束前
提交说明：每个班一个文件夹，在班级文件夹下，将作业的所有内容压缩成一个rar或zip文件，每个人提交完压缩包将看不到自己的压缩包（不要反复上传），每个人提交内容包括完整程序源码及自己所负责编写程序的那部分文档，压缩文件的命名规则为 学号＋姓名.rar（.zip）。
提交方式：ftp://202.113.12.9/learning/lxh/homewor/ 下的三个文件夹
2006-03-15


最珍贵的财富是时间，最大的浪费是虚度流年。