《计算机算法设计与分析》试卷 考试时间120分钟
2002年-2003年第二学期
学号 姓名 成绩
一、阐述题
1． 请说明算法的五个基本特性，并进行简要的分析(5分) 答：算法的五个基本特性如下：
① 确定性 算法的每一种运算必须要有确切的定义，即每一种运算应该执行何种动作必须是相当清楚的、无二义性的。
② 能行性 一个算法是能行的是指算法中有待实现的运算都是基本的运算，每种运算至少在原理上能由人用纸和笔在有限时间内完成。
③ 输入 一个算法有0个或多个输人，这些输人是在算法开始之前给出的量，它取自特定的对象集合。
④ 输出 一个算法产生一个或多个输出，这些输出是同输人有某种特定关系的量。 ⑤ 有穷性 一个算法总是在执行了有穷步的运算之后能够终止，且每一步都可在有穷时间内完成。这里的有穷的概念不是纯数学的，而是在实际上是合理的，可以接受的。
凡是算法，都必须满足以上五条特性。只满足前四条特性的一组规则不能称为算法，只能叫做计算过程。
2． 若森林非空，请按照森林和树相互递归的定义，阐述森林的两种遍历的方法。(10分) 答：森林是由m(m≥0)棵互不相交的树构成的集合。对树中的每一个结点而言，其子树的集合即为森林。所以，森林和树是可以相互递归定义的。
对于一个非空的森林F=(T1，T2，…，Tm)，因为至少存在一棵树，不妨假设为T1，则森林F可以分解成T1和由T2，…，Tm构成的森林。于是，可得到森林的两种遍历算法。
① 先序遍历森林
若森林非空，则可按下述规则遍历这个森林： （1） 访问树中第一棵树的根结点；
（2） 先序遍历第一棵中根结点的所有子树构成的森林； （3） 先序遍历除去第一棵树外剩下的树构成的森林。 ② 中序遍历森林
若森林非空，则可按下述规则遍历这个森林：
（1） 中序遍历第一棵中根结点的所有子树构成的森林； （2） 访问树中第一棵树的根结点；
（3） 中序遍历除去第一棵树外剩下的树构成的森林。 二、计算题
1. 考虑下列三个函数 (5分)
2 ， n为非负奇数 n n ， 0≤n≤100
f1(n)= f2(n)= f3(n)=n 1.5
3 ， n为正偶数 2 ， n＞100 ， ， ， n n 填充两个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 ， 。
- 1 -
中国科学院研究生院软件学院大连教学点
请将答案填写在下面的方框中。
О(i,j) f1 f2 f3
f1 Y f2 Y f3 Y
N Y Y
N N Y
Ω(i,j) f1 f2 f3
f1 Y f2 N f3 N
Y Y N
Y Y Y
2. 设W=(5，7，10，12，15，18，20)和M=35，使用过程SumOfSub找出W中使得和数等于M的全部子集并画出所生成的部分状态空间树。 (5分)
答：
设状态空间树的结点形式为由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,4,50 0,4,50 0,4,50 0,4,50
- 2 -
X(1) =1 5,2,82 0,1,87 0,2,82 12,3,75 5,3,75 7,3,75 0,3,75 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,50 0,4,50 0,4,50 0,4,50 0,4,50 0,1,87 0,1,87 0,1,87 0,1,87 0,1,87 0,1,87 0,1,87 0,1,87 中国科学院研究生院软件学院大连教学点
三、证明题
1. 在已知根R(i,j)（0≤i＜j≤n）的情况下写一个构造最优二分检索树T的算法。 证明这样的树能在О(n)时间内构造出来。 (10分)
答：R(i,j)（0≤i＜j≤n）中记录的是构造最优二分检索树Tij时满足最小成本的k值。
根据最优二分检索树的定义知道，给定的n个标识符是单调有序的（无重复）。 若Tij的根为ak，则aK的左子树上的标识符是{ai，ai+1，，ak-1}，而则aK的右子树上的标识符是{ak+1，ak+2，，aj},且当i=j时，Tij是外部结点。
根据上述思路，可依据如下算法构造一棵最优二分检索树。
采用二叉链表作为存储结构，结点的定义如下： typedef struct OBSTNode {
char data; //标识符类型，可以是字符串
struct OBSTNode *lchild, *rchild; //左右孩子结点的指针 } OBSTNode,* OBSTree
Void OBSTCreate(OBSTree P, int i,int j) {
int k； OBSTree S； if (i〈〉j) {
k=r[i][j]； //数组R[][]是全局变量
new(S)； //产生一个新的结点,让S指向该结点 S->data=a[k]； //数据A[]是全局变量 If(!P) {P=S}； //产生根结点 Else {
if(S->data < P->data) { //新产生的结点是P结点的左孩子
P->lchild=S； P = S；}
else { //新产生的结点是P结点的右孩子
P->rchild=S； P = S；} } ；
OBSTCreate(P,i,k-1)； OBSTCreate(P,k+1,j)； }
}// OBSTCreate
main OBST0(OBSTree &T，int n) {
//数组A[]和R[][]是全局变量 if(n<1) return error； OBSTCreate(T,0,n)；
}
时间复杂度证明
T(n) = T(k) + T(n-k) + c c为常数 0≤k≤n
= …
= (n+1)*T(0) + n*c 因为T(0)=0 所以T(n)= cn 即，T(n)= ○(n) 证毕
- 3 -
中国科学院研究生院软件学院大连教学点
2．折半查找过程的判定树上，定义根结点到每个内部结点(查找成功的结点)的路径长度之和为内部路径长度，记为I；定义根结点到每个外部结点(查找不成功的结点)的路径长度之和外部路径长度，记为E。
试证明：具有n个内部结点的这样的判定树，满足E = I + 2n 。 (10分) 3． 证明该等式不成立n四、算法题
1. 对于下表左部给定的算法，计算该算法的时间渐进复杂性。 (10分)
语句 bool Bubble(elemTyoe a[],int n) { //把a[0:n-1]中的最大元素冒泡至最后 bool swapped = false; //尚未发生交换 for(int i = 0; i 2+6n3=Ο(n2)。 (5分) 2n3n s/e 频率 总步数 总计 2. 下面的算法是依据分治策略设计出来的，仔细阅读该算法思路，在划线处填写适当的语句以 完成整个算法。 (15分) 问题：编写出函数reverse(s)的递归程序，使字符串s反序。 算法思路：令指针i，j分别指示字符串s的头、尾字符，然后交换i，j分别指示的字符，并修改对i指针做加1操作；对j指针做减1操作，直到i≥j。 #include void reverser(char s[],int i,int len)； reverser(s, ① ,strlen(s))； } void reverser(char s[],int i,int len) { int c，j； j = ② ； if (i 中国科学院研究生院软件学院大连教学点 { c = s[i]； s[i] = s[j]； s[j] = c； reverser(s,++i, ③ )； } } 3. 阅读下面的算法，并回答给定的问题(行号是为了说明问题而设置，它不属于算法本身)。(15分) void ABC(A，n) { //A(0:n)是一个一维数组，共有n个可比较值大小的元素； //且A(0)未存放元素；变量x是与A(i)同类型的数据元素。 1 integer i,j； 2 for(j=2；j<=n；j++) { 3 i=j-l； 4 A[0]=A[j]； 5 while(A[0] ③ 程序中变量x是否可省，为什么？ ④ 给出while语句的最少执行次数的示例(列出数组A的数据元素例子) 4． 著名的Hanoi塔问题描述如下：有 A，B，C三根针，和一些中间有大小不等的孔的金片。 初始时，金片由小到大全在A针上，其中最大的在下面，最小的在最上面。要求将A针上的金片全部移至B针上，每次只能移动一张金片，且任何时刻不允许将大的金片放在小金片的上面。C针可以作为移动金片的辅助位置。要求利用分治法给出金片移动过程的算法描述。(10分) - 5 - 因篇幅问题不能全部显示，请点此查看更多更全内容