《计算机算法设计与分析》答案
- 格式：doc
- 大小：96.00 KB
- 文档页数：5
中国科学院研究生院软件学院大连教学点
- 1 - 《计算机算法设计与分析》试卷 考试时间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分)
填充两个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 ， 。
n ， n为非负奇数
f1(n)=
n ， n为正偶数 n ， 0≤n≤100
f2(n)=
n ， n＞100 f3(n)=n 2
3 2 1.5
， ， ， 中国科学院研究生院软件学院大连教学点
- 2 - 请将答案填写在下面的方框中。
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的全部子集的部分状态空间树如下：
О(i,j) f1 f2 f3
f1
f2
f3 Ω(i,j) f1 f2 f3
f1
f2
f3 Y
Y
Y N
Y Y
Y N
N Y Y
N
N Y
N
Y
Y
Y
0,1,87
0,3,65
0,3,65
0,3,65 0,3,65
0,4,50
0,4,50
0,1,87 0,1,87 0,1,87 0,1,87 0,1,87 0,3,65 0,4,50 0,4,50 0,4,50 0,4,50 0,1,87 0,3,65
0,4,50
0,1,87 0,1,87 5,2,82 0,2,82
12,3,75 5,3,75 7,3,75 0,3,75 X(1) =1
0,3,65 0,3,65
0,4,50 0,4,50 中国科学院研究生院软件学院大连教学点
- 3 - 三、证明题
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)
证毕
中国科学院研究生院软件学院大连教学点
- 4 -
2．折半查找过程的判定树上，定义根结点到每个内部结点(查找成功的结点)的路径长度之和为内部路径长度，记为I；定义根结点到每个外部结点(查找不成功的结点)的路径长度之和外部路径长度，记为E。
试证明：具有n个内部结点的这样的判定树，满足E = I + 2n 。 (10分)
3． 证明该等式不成立n32n+6n23n=Ο(n32n)。 (5分)
四、算法题
1. 对于下表左部给定的算法，计算该算法的时间渐进复杂性。 (10分)
语句 s/e 频率 总步数
bool Bubble(elemTyoe a[],int n) {
//把a[0:n-1]中的最大元素冒泡至最后
bool swapped = false; //尚未发生交换
for(int i = 0; i
if(a[i]>a[i+1]) {
Swap(a[i],a[i+1]);
swapped = true; //发生了交换
};
return swapped;
}
void BubbleSort(elemTyoe a[],int n) {
//及时终止的冒泡排序算法
for(int i = n; i>1 && Bubble(a,i);i--);
}
总计
2. 下面的算法是依据分治策略设计出来的，仔细阅读该算法思路，在划线处填写适当的语句以完成整个算法。 (15分)
问题：编写出函数reverse(s)的递归程序，使字符串s反序。
算法思路：令指针i，j分别指示字符串s的头、尾字符，然后交换i，j分别指示的字符，并修改对i指针做加1操作；对j指针做减1操作，直到i≥j。
#include
void reverse(char s[])
{
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
