《计算机算法设计与分析》答案.doc

中国科学院研究生院软件学院大连教学点 - PAGE 3 - 《计算机算法设计与分析》试卷 考试时间120分钟 2002年-2003年第二学期 学号 姓名 成绩 阐述题 请说明算法的五个基本特性，并进行简要的分析(5分) 答：算法的五个基本特性如下： ① 确定性 算法的每一种运算必须要有确切的定义，即每一种运算应该执行何种动作必须是相当清楚的、无二义性的。 ② 能行性 一个算法是能行的是指算法中有待实现的运算都是基本的运算，每种运算至少在原理上能由人用纸和笔在有限时间内完成。 ③ 输入 一个算法有0个或多个输人，这些输人是在算法开始之前给出的量，它取自特定的对象集合。 ④ 输出 一个算法产生一个或多个输出，这些输出是同输人有某种特定关系的量。 ⑤ 有穷性 一个算法总是在执行了有穷步的运算之后能够终止，且每一步都可在有穷时间内完成。这里的有穷的概念不是纯数学的，而是在实际上是合理的，可以接受的。 凡是算法，都必须满足以上五条特性。只满足前四条特性的一组规则不能称为算法，只能叫做计算过程。 若森林非空，请按照森林和树相互递归的定义，阐述森林的两种遍历的方法。(10分) 答：森林是由m(m≥0)棵互不相交的树构成的集合。对树中的每一个结点而言，其子树的集合即为森林。所以，森林和树是可以相互递归定义的。 对于一个非空的森林F=(T1，T2，…，Tm)，因为至少存在一棵树，不妨假设为T1，则森林F可以分解成T1和由T2，…，Tm构成的森林。于是，可得到森林的两种遍历算法。 先序遍历森林 若森林非空，则可按下述规则遍历这个森林： 访问树中第一棵树的根结点； 先序遍历第一棵中根结点的所有子树构成的森林； 先序遍历除去第一棵树外剩下的树构成的森林。 中序遍历森林 若森林非空，则可按下述规则遍历这个森林： 中序遍历第一棵中根结点的所有子树构成的森林； 访问树中第一棵树的根结点； 中序遍历除去第一棵树外剩下的树构成的森林。 n ， n为非负奇数 n ， n为非负奇数 f1(n)= n ， n为正偶数 n ， 0≤n≤100 f2(n)= n ， n＞100 f3(n)=n 2 3 2 1.5 ， ， ， 考虑下列三个函数 (5分) 填充两个3阶距阵О(i,j)，Ω(i,j)。其中，О(i,j)，Ω(i,j)的定义分别如下： Y，fi(n)=О(fj(n)) Y，fi(n)=Ω(fj(n)) О(i,j)= Ω(i,j)= 1≤i,j≤3 N，else ； N，else ， 。 YYYNNY 请将答案填写在下面的方框中。 Y Y Y N N Y YYYNNNNYYYYYО(i,j) f1 f2 f3f1f Y Y Y N N N N Y Y Y Y Y О(i,j) f1 f f1 f2 f3 Ω(i,j) f1 f f1 f2 f3 答： 设状态空间树的结点形式为由s，k，r构成的三元组，其中s用以记录从根结点到当前结点的路径的加权和(解向量X(i)的取值为左分枝取‘1’，右分枝取‘0’)，k表示结点的序号(也是结点的层次号)，r表示剩余权值的和。由于给定的权值序列是有序的，所以，将要使用的限界函数是 Bk(X(1)，…，X(k))=true 当且仅当 K n k ∑W(i)X(i) + ∑W(i)≥ M 且 ∑W(i)X(i) + W(k+1) ≤ M i=1 i=k+1 i=1 K-1 n 定义s =∑W(i)X(i) ； r = ∑W(i) i=1 i=k 使用过程SumOfSub找出W中使得和数等于M的全部子集的部分状态空间树如下： 0, 0,1,87 X(1) =1 5,2, 5,2,82 0,2,82 0,3,757,3,755,3,75 0,3,75 7,3,75 5,3,75 12,3,75 0,3,650,3,650,3,650,3,65 0,3,65 0,3,65 0,3,65 0,3,65 0,3,65 0,3,65 0,3,65 0,3,65 0,4,500,4,500