1、2006-03-152006 年本科生数据结构上机实习题目题目：1.猴子吃桃子问题5 只猴子一起摘了一堆桃子，因为太累，决定睡一觉后再来分桃，过了不知多久，第 1 只猴子先醒来，它见别的猴子没来，便将一堆桃子平均分成 5 份,结果多了 1 个，就将多的这个吃了，拿走其中的一堆。又过了不知多久，第二只猴子来了，它不知道有一个同伴已经来过，还以为自己是第一个，便将地上的桃子平均分成 5 份，发现也多了一个，同样吃了这一个，拿走其中的一堆。第 3 只，第 4 只，第 5 只猴子都是这样.问这 5 只猴子至少摘了多少个桃子？分析：设第 n 个猴子分的每堆有 Xn 个则有这个关系式：5*X(n+1)+1
2、=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 时，
3、此时栈 stack 中存放的所有结点均为给定结点*p 的祖先，而由这些祖先便构成了一条从根结点到结点*p 之间的路径。3.设计一个公交查询系统，能让乘客查询从任一一个站点到另一站点之间的最短路径或最省钱路径或最省时路径。对于不同查询要求，可输入站点之间的路程或所需时间或所需费用。分析：该题目分三部分，首先要建立公交网络图的存储结构；然后需要解决单源最短路径问题；最后实现两个站点之间的最短路径问题。4.稳定婚姻问题A 是 n 个男子的集合，B 是 n 个女子的集合，每个男子按自己的选择意愿将 n 个女子排成一列，同样的每个女子也将 n 个男子排成一列。将他们组成 n 对夫妇，如果存在这样一个男子
4、和一个女子，这两人不是夫妇，但他们互相喜爱的程度胜于对自己配偶的喜爱，这样的 n 对夫妇称为不稳定婚姻。如果不存在这样的男子和女子，就称为稳定婚姻。问题就是要将这 n 个男子和 n 个女子组成稳定的 n 对夫妇。(1)算法效率越高得分将会越高.分析：该问题可抽象为：设有两个集合 A 和 B，A 的基数等于 B，按照某种条件建立一个2006-03-15A 到 B 的内射（即为 A 中的每一个元素，在 B 中恰好找一个与其搭配，而 B 中每一个元素，最多能与 A 中一个搭配） 。 二、目标结合课程学习与实践经验，进行实际的上机实践，掌握数据结构课程中的队列、二叉树、图及排序等内容，同时在实践中贯彻
5、软件工程的思想。一、要求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/ 下的三个文件夹
