中国科学院大学历年计算机算法作业和历年习题.doc

中国科学院大学历年习题
习题一 复杂性分析初步
1. 试确定下述程序的执行步数，该函数实现一个m×n矩阵与一个n×p矩阵之间的乘法：
矩阵乘法运算
template
void Mult(T **a, T **b, int m, int n, int p)
{//m×n矩阵a与n×p矩阵b相成得到m×p矩阵c
for(int i=0; i for(int j=0; j
void Mult(T **a, T **b, int m, int n, int p) 0 0 0

{
for(int i=0; i m*p*n+m*p
Sum+=a[i][k]*b[k][j]; 1 m*p*n m*p*n
C[i][j]=sum; 1 m*p m*p
}
}
总 计 2*m*p*n+4*m*p+2*m+1

其中 s/e 表示每次执行该语句所要执行的程序步数。
频率是指该语句总的执行次数。
2． 函数MinMax用来查找数组a[0:n-1]中的最大元素和最小元素，以下给出两个程序。令n为实例特征。试问：在各个程序中，a中元素之间的比较次数

在最坏情况下各是多少？
找最大最小元素 方法一
template
bool MinMax(T a[], int n, int& Min, int& Max)
{//寻找a[0:n-1]中的最小元素与最大元素
//如果数组中的元素数目小于1，则还回false
if(n<1) return false;
Min=Max=0; //初始化
for(int i=1; ia[i]) Min=i;
if(a[Max]
bool MinMax(T a[], int n, int& Min, int& Max)
{//寻找a[0:n-1]中的最小元素与最大元素
//如果数组中的元素数目小于1，则还回false
if(n<1) return false;
Min=Max=0; //初始化
for(int i=1; ia[i]) Min=i;
else if(a[Max] 5).。错
6). 对
6. 按照渐进阶从低到高的顺序排列以下表达式:

顺序：

7. 1) 假设某算法在输入规模是时为. 在某台计算机上实现并完成该算法的时间是秒.现有另一台计算机,其运行速度为第一台的64倍, 那么,在这台计算机上用同一算法在秒内能解决规模为多大的问题?
规模
时间复杂度（步数）
原运行速度（时间/每步）
总时间

关系式为 时间复杂度（计算步数）*运行速度(时间/每步)=运行所需时间，即

解：设在新机器上秒内能解决规模为的问题，时间复杂度变为，
由于新机器运行速度提高64倍，则运行速度变为，
由关系式，得
，

解得

2) 若上述算法改进后，新算法的计算复杂度为, 则在新机器上用秒时间能解决输入规模为多大的问题？
设在新机器上用秒时间能解决输入规模为的问题，则
由于新复杂度 ，新机器的运行速度为，
代入关系式，得
，
解得

3）若进一步改进算法，最新的算法的时间复杂度为 ，其余条件不变，在新机器上运行，在秒内能够解决输入规模为多大的问题？
设可解决的最大时间复杂度为，则

可解决的最大时间复杂度为，（n为原始的输入规模）。
因为，且为常数不随输入规模n变化，
所以任意规模的n都可在t秒内解决。
8. Fibonacci数有递推关系：

试求出的表达式。
解：方法一：
当时，由递推公式得

特征方程为

解得
，
则可设

由，，解得，
故，
当时，带入验证亦成立。
故

方法二：
也可直接推导

可得

可得
，
设
，

则为等比数列，先求出，然后代入即可求得。

第二章部分习题参考答案
1.证明下列结论：
1）在一个无向图中，如果每个顶点的度大于等于2，则该该图一定含有圈；
2）在一个有向图D中，如果每个顶点的出度都大于等于1，则该图一定含有一个有向圈。
1）证明：设无向图最长的迹每个顶点度大于等于2，故存在与相异的点与相邻，若则得到比更长的迹，与P的取法矛盾。因此，，是闭迹，从而存在圈
证明*：设在无向图G中，有n个顶点，m条边。由题意知，m>=(2n)/2=n，而一个含有n个顶点的树有n-1条边。因m>=n>n-1，故该图一定含有圈。
（定义：迹是指边不重复的途径，而顶点不重复的途径称为路。起点和终点重合的途径称为闭途径，起点和终点重合的迹称为闭迹，顶点不重复的闭迹称为圈。）
2）证明：设有向图最长的有向迹每个顶点出度大于等于1，故存在为的出度连接点，使得成为一条有向边，若则得到比更长的有向迹，与P矛盾，因此必有，从而该图一定含有有向圈。
2.设D是至少有三个顶点的连通有向图。如果D中包含有向的Euler环游（即是通过D中每条有向边恰好一次的闭迹），则D中每一顶点的出度和入度相等。反之，如果D中每一顶点的出度与入度都相等，则D一定包含有向的Euler环游。这两个结论是正确的吗？请说明理由。如果G是至少有三个顶点的无向图，则G包含Euler环游的条件是什么？
证明：1）若图D中包含有向Euler环游，下证明每个顶点的入度和出度相等。
如果该有向图含有Euler环游，那么该环游必经过每个顶点至少一次，每经过一次，必为“进”一次接着“出”一次，从而入度等于出度。从而，对于任意顶点，不管该环游经过该顶点多少次，必有

入度等于出度。
2）若图D中每个顶点的入度和出度相等，则该图D包含Euler环游。证明如下。
对顶点个数进行归纳。
当顶点数|v(D)|=2时，因为每个点的入度和出度相等，易得构成有向Euler环游。
假设顶点数|v(D)|=k时结论成立，则
当顶点数|v(D)|=k + 1时，任取v∈v(D).设S={以v为终点的边}，K={以v为始点的边}，因为v的入度和出度相等，故S和K中边数相等。记G=D-v.对G做如下操作:
任取S和K中各一条边，设在D中，，则对G和S做如下操作 , ，重复此步骤直到S为空。这个过程最终得到的G有k个顶点，且每个顶点的度与在G中完全一样。由归纳假设，G中存在有向Euler环游，设为C。在G中从任一点出发沿C的对应边前行，每当遇到上述添加边v1v2时，都用对应的两条边e1，e2代替，这样可以获得有向Euler环游。
3）G是至少有三个顶点的无向图，则G包含Euler环游等价于G中无奇度顶点。（即任意顶点的度为偶数）。
3．设G是具有n个顶点和m条边的无向图，如果G是连通的，而且满足m = n-1,证明G是树。
证明：思路一：
只需证明G中无圈。
若G中有圈，则删去圈上任一条边G仍连通。而每个连通图边数e>=n(顶点数) – 1，但删去一条边后G中只有n-2条边，此时不连通，从而矛盾，故G中无圈，所以G为树。
思路二：
当时，，两个顶点一条边且连通无环路显然是树。
设当时，命题成立，则
当时，因为G连通且无环路，所以至少存在一个顶点，他的度数为1，设该顶点所关联的边为

那么去掉顶点和，便得到了一个有k-1个顶点的连通无向无环路的子图，且的边数，顶点数。由于m=n-1,所以，由归纳假设知，是树。
由于相当于在中为添加了一个子节点，所以G也是树。
由（1），（2）原命题得证。
4. 假设用一个的数组来描述一个有向图的邻接矩阵，完成下面工作：
1）编写一个函数以确定顶点的出度，函数的复杂性应为：
2）编写一个函数以确定图中边的数目，函数的复杂性应为
3）编写一个函数删除边，并确定代码的复杂性。
解答：（1）邻接矩阵表示为，待确定的顶点为第m个顶点
int CountVout(int *a,int n,int m){
int out = 0;
for(int i=0;i的函数如下：
void deleteEdge(int *a，int i ,int j){

if(a[i-1][j-1]==0) return;
a[i-1][j-1] = 0;
return;
}
代码的时间复杂性为Θ(1)

5.实现图的D-搜索算法，要求用SPARKS语言写出算法的伪代码，或者用一种计算机高级语言写出程序。
解:D搜索算法的基本思想是，用栈代替BFS中的队列，先将起始顶点存入栈中，搜索时，取出栈顶的元素，遍历搜索其相邻接点，若其邻接点还未搜索，则存入栈中并标记，遍历所有邻接点后，取出此时栈顶的元素转入下一轮遍历搜索，直至栈变为空栈。
Proc DBFS (v) //从顶点v开始，数组visited标示顶点被访问的顺序；
PushS(v , S); //首先访问v,将S初始化为只含有一个元素v的栈
count :=count +1; visited[v] := count;
While S 非空 do
u :=PullHead(S); count :=count +1; visited[w] := count; //区别队列先进先出，此先进后出
for 邻接于u的所有顶点w do
if s[w] = 0 then
PushS(w,S); //将w存入栈S
s[w]:= 1;
end{if}
end{for}
end{while}
end{DBFS}
注：PushS(w,S)将w存入栈S; PullHead(S)为取出栈最上面的元素，并从栈中删除
Proc DBFT(G，m) //m为不连通分支数
count:=0 ;计数器，标示已经被访问的顶点个数
for i to n do
s[i]:=0; //数组s用来标示各顶点是否曾被搜索，是则标记为1，否则标记为0；

end{for}
for i to m do //遍历不连通分支的情况
if s[i]=0 then
DBFS (i);
end{if}
end{for}
end{DBFT}

6.下面的无向图以邻接链表存储，而且在关于每个顶点的链表中与该顶点相邻的顶点是按照字母顺序排列的。试以此图为例描述讲义中算法DFNL的执行过程。
一个无向图 G
A
B

E
D
G
C
F
1
1
2
3
4
7
5
6
1
1
1
5
5
4
邻接链表
A->B->E|0
B->A->C|0
C->B->D->E|0
D->C|0
E->A->C->F->G|0
F->E->G|0
G->E->F|0
解：初始化 数组DFN:=0， num=1；
A为树的根节点,对A计算DFNL(A,null)，
DFN(A)：=num=1; L(A)：=num=1; num:=1+1=2。
从邻接链表查到A的邻接点B，
因为DFN(B)=0,对B计算DFNL(B,A)
DFN(B)：= num=2; L(B)：=num=2; num：=2+1=3。
查邻接链表得到B的邻接点A，因为DFN(A)=1¹0, 但A=A,即是B的父节点，无操作。
接着查找邻接链表得到B的邻接点C，
因为DFN(C)=0,对C计算DFNL(C,B)
DFN(C)：= num=3; L(C)：=num=3; num:=3+1=4。

查找C的邻接点B，因为DFN(B)=1¹0, 但B=B,即是C的父节点，无操作。
接着查找邻接链表得到C的邻接点D，
因为DFN(D)=0,对D计算 DFNL(D,C)，
DFN(D)：= num=4; L(D)：=num=4; num:=4+1=5。
查找得D邻接点C，而DFN(C)=3≠0,但C=C，为D的父节点， L(D)保持不变。
D的邻接链表结束，DFNL(D,C)的计算结束。
返回到D的父节点C，查找邻接链表得到C的邻接点E，
因为DFN(E)=0,对E计算DFNL(E,C),
DFN(E)：=num=5; L(E)：=num=5; num:5+1=6;
查找得E邻接点A，因DFN(A)=1≠0，又A≠C，变换L(E)=min(L(E),DFN(A))=1。
查找得E邻接点C，因DFN(C)=3≠0，但C=C，无操作。
查找得E邻接点F，因DFN(F)=0，
对F计算 DFNL(F,E)，
DFN(F)：=num=6; L(F)：=num=6; num:=6+1=7;
查找得F邻接点E，因DFN(E)=5≠0，但E=E，无操作。
查找得F邻接点G，因DFN(G)=0，
对G计算 DFNL(G,F)，
DFN(G)：=num=7; L(G)：=num=7; num=7+1=8；
查找G邻接点E，因DFN(E)=5≠0，又E≠F，L(G)=min(L(G),DFN(E))=5
查找得G邻接点F,因DFN(F)=6≠0，但F=F，无操作。
G的邻接链表结束，DFNL(G,F)的计算结束。
L(F)：=min(L(F)，L(G))=min(6,5)=5
F的邻接链表结束，DFNL(F,E)的计算结束。
L(E):=min(L(E),L(F))=min(1,5)=1
E邻接链表结束， DFNL(E,C)计算结束。
L(C):=min(L(C),L(E))=min(3,1)=1
C的邻接链表结束，DFNL(C,B)计算结束。
L(B):=min(L(B),L(C))=min(2,1)=1

查找B的邻接链表结束，DFNL(B,A)计算结束。
L(A):=min(L(A),L(B))=1
查找得A的邻接点E，因DFN(E)=0，又E≠null,则L(A)=min(L(A),DFN(E))=1
查找A的邻接链表结束，DFNL(A,null)计算结束。
最终结果为：深索数DFN，与最低深索数L如下
DFN(A)=1，DFN(B)=2，DFN(C)=3，DFN(D)=4，DFN(E)=5，DFN(F)=6，DFN(G)=7
L(A)=1; L(B)=1; L(C)=1; L(D)=4; L(E)=1; L(F)=5;L(G)=5.

序
节点
DFN
L
栈顶—栈底
2-连通
割点
1
A
1
(1,0,0,0,0,0,0)
(A,B)

2
B
2
(1,2,0,0,0,0,0)
(B,C),(A,B)

3
C
3
(1,2,30,0,0,0)
(C,D),(B,C),(A,B)

4
D
4
(1,2,3,4,0,0,0)
(B,C),(A,B)
{(C,D)};
C
5
E
5
(1,1,1,4,1,0,0)
(E,F),(E,A),(B,C),(A,B)

6
F
6
(1,1,1,4,1,6,0)
(F,G), (E,F),(E,A),(B,C),(A,B)

7
G
7
(1,1,1,4,1,5,5)
(E,A),(B,C),(A,B)
{(G,E),(F,G), (E,F)}
E
8

(1,1,1,4,1,5,5)

{E,A),(B,C),(A,B)}

附课本讲义程序2-3-1对图2-3-5的执行过程
开始 DFNL(A,*)
DFN(A):=1; L(A):=1; num:=2;
A
B
B
B A
C B
B
C B A
D C B
B
C B A
E C B
B
C B A
F C B
B
F C B A
A F C B
B

∵ DFN(B)=0, ∴ DFNL(B,A)
DFN(B):=2; L(B):=2; num:=3;
∵ DFN(A)=1¹0, 但A=A, ∴不做任何事情

∵ DFN(C)=0, ∴ DFNL(C,B)
DFN(C):=3; L(C):=3; num:=4;
∵ DFN(B)=2¹0, 但B=B, ∴不做任何事情

∵ DFN(D)=0, ∴ DFNL(D,C)
DFN(D):=4; L(D):=4 > DFN( C); num:=5; 弹出（C,D）边
∵ DFN(C)=3¹0, 但C=C, ∴不做任何事情

∵ DFN(E)=0, ∴ DFNL(E,C)
DFN(E):=5; L(E):=5 > DFN( C); num:=6; 弹出（C,E）边
∵ DFN(C)=3¹0, 但C=C,
∵ DFN(F)=0, ∴ DFNL(F,C)
DFN(F):=6; L(F):=6; num:=7;
∵ DFN(A)=1¹0, A¹C, ∴ L(F):=min{6,1}=1;
∵ DFN(C)=3¹0, 但C=C,
F F C B A
G A F C B
B
G F F C B A
H G A F C B
B
G F F C B A
I G A F C B
B
I G F F C B A
F I G A F C B
B
I I G F F C B A
J F I G A F C B
B
J I I G F F C B A
F J F I G A F C B
B
J J I I G F F C B A
G F J F I G A F C B
B

∵ DFN(G)=0, ∴ DFNL(G,F)
DFN(G):=7; L(G):=7; num:=8;
∵ DFN(F)=6¹0, 但F=F,

∵ DFN(H)=0, ∴ DFNL(H,G)
DFN(H):=8; L(H):=8 > DFN(G); num:=9; 弹出（G,H）边
∵ DFN(G)=7¹0, 但G=G,

∵ DFN(I)=0, ∴ DFNL(I,G)
DFN(I):=9; L(I):=9; num:=10;
∵ DFN(F)=6¹0, F¹G, ∴ L(I):=min{9,6}=6;
∵ DFN(G)=7¹0, 但G=G,

∵ DFN(J)=0, ∴ DFNL(J,I)
DFN(J):=10; L(J):=10; num:=11;
∵ DFNF)=6¹0, F¹I, ∴ L(J):=min{10,6}=6;
∵ DFN(G)=7¹0, G¹I, ∴ L(J):=min{6,7}=6;
∵ DFN(I)=9¹0, 但I=I,

L(I):=min{6,6}=6;
L(G):=min{7,6}=6 ³ DFN(F) 弹出(J,G), (J,F), (I,J), (I,F), (GI), (F,G) 边
L(F):=min{1,6}=1;
L(C ):=min{3,1}=1;
L(B):=min{2,1}=1 ³ DFN(A) 弹出(F,A), (C,F), (B,C), (A,B) 边
7 对图的另一种检索方法是 D-Search。该方法与 BFS 的不同之处在于将队列换成栈，即下一个要检测的结点是最新加到未检测结点表的那个结点。
1）写一个D-Search算法；
2）证明由结点v开始的D-Search能够访问v可到达的所有结点；
3）你的算法的时、空复杂度是什么？
解：1）同第5题，
proc DBFS(v) //宽度优先搜索G，从顶点v开始执行，数组visited标示各
//顶点被访问的序数；数组s将用来标示各顶点是否曾被放进待检查队
//列，是则过标记为1，否则标记为0；计数器count计数到目前为止已
//经被访问的顶点个数，其初始化为在v之前已经被访问的顶点个数
PushS(v , S);// 将S初始化为只含有一个元素v的栈
while S非空 do
u:= PullHead(S); count:=count+1; visited[u]:=count;
for 邻接于u的所有顶点w do
if s[w]=0 then
PushS(w , S); //将w压入栈中
s[w]:=1;
end{if}
end{for}
end{while}
end{DBFS}
图的D—搜索算法伪代码：
proc DBFT(G, ν) //count、s同DBFS中的说明，branch是统计图G的连通分支数
count:=0; branch:=0;

for i to n do
s[i]:=0; //将所有的顶点标记为未被访问
end{for}
for i to ν do
if s[i]=0 then
DBFS(i); branch:=branch+1;
end{if}
end{for}
end{DBFT}
2）证明：除结点v外，只有当结点w满足s[w]=0时才被压入栈中，因此每个结点至多有一次被压入栈中，搜索不会出现重叠和死循环现象，对于每一个v可到达的节点，要么直接被访问，要么被压入栈中，只有栈内节点全部弹出被访问后，搜索才会结束，所以由结点v开始的D-Search能够访问v可到达的所有结点。
3）：除结点v外，只有当结点w满足s[w]=0时才被压入栈中，因此每个结点至多有一次被压入栈中。需要的栈 空间至多是ν-1；visited数组变量所需要的空间为ν；其余变量所用的空间为O(1)，所以s(ν,ε)=Θ (ν)。
如果使用邻接链表， for循环要做d(u)次，而while循环需要做ν次，又visited、s和count的赋值都需要ν次操作，因而t(ν， ε)=Θ (ν+ ε)。
如果采用邻接矩阵，则while循环总共需要做ν2次操作，visited、s和count的赋值都需要ν次操作，因而t(ν， ε)=Θ (ν2)。
8.考虑下面这棵假想的对策树：
解：

20
6
4
20
5
4
8
15
6
20
30
5
50
8
4
15
20
5
10
30
5
9
20
50
18
6
15
10
5
5
20
1）使用最大最小方法(24-2)式获取各结点的值
max
max
max
min
min

2）2）弈者A为获胜应该什么棋着？
20
6
4
20
5
4
8
15
6
20
30
5
50
8
4
15
20
5
10
30
5
9
20
50
18
6
15
10
5
5
20
X
X1
X2
X3
X4
X1.1
X1.2
X2.1
X2.2
X3.1
X3.2
X4.1
X4.2
X1.1.1
X1.1.2
X1.1.3
X1.2.1
X2.1.1
X2.2.1
X3.1.1
X3.1.2
X1.1.1.1
X3.1.2.1
X3.2.1
X3.2.2
X3.2.3
X4.1.1
X4.2.1
X4.4.2
X4.2.3
X4.2.4

第三章 分治算法习题
1、编写程序实现归并算法和快速排序算法
参见后附程序
2、用长为100、200、300、400、500、600、700、800、900、1000的10个数组的排列来统计这两种算法的时间复杂性。
有些同学用的微秒us
用s可能需要把上面的长度改为10000，……，100000，都可以
大部分的结果是快速排序算法要比归并算法快一些。
3、讨论归并排序算法的空间复杂性。
解析：归并排序由分解与合并两部分组成，如果用表示归并排序所用的空间。
则由
MergeSort(low, mid) //将第一子数组排序
MergeSort(mid+1, high) //将第二子数组排序
Merge(low, mid, high) //归并两个已经排序的子数组
则

递归推导得

又由存储数组长度为 ，则有
因此，空间复杂度为。
4、说明算法PartSelect的时间复杂性为
证明：提示：假定数组中的元素各不相同，且第一次划分时划分元素是第小元素的概率为。因为Partition中的case语句所要求的时间都是，所以，存在常数，使得算法PartSelect的平均时间复杂度可以表示为

令取试证明。
证明：令表示n个元素的数组A中寻找第k小元素的平均时间复杂度，因的时间复杂度是，故存在常数c，使得算法PartSelect的平均时间复杂度可以表示为
令且不妨设等式在时成立，则满足

以下用第二数学归纳法证明。取
当时，取cC/4,则
当时，成立。

对于一般的n，设对所有小于n的自然数成立，则

得证。
证明：（1）当时，假设数组A中元素互不相同。由于每个具有7个元素的数组的中间值u是该数组中的第4小元素，因此数组中至少有4个元素不大于u，个中间值中至少有个不大于这些中间值的中间值v。因此，在数组A中至少有

个元素不大于v。换句话说，A中至多有

个元素大于v。同理，至多有个元素小于v。这样，以v为划分元素，产生的新数组至多有个元素。当时，。
另一方面，在整个执行过程中，递归调用Select函数一次，涉及规模为，而下一次循环Loop涉及的数组规模为。程序中其他执行步的时间复杂度至多是n的倍数，用表示算法在数组长度为n的时间复杂度，则当时，有递归关系

用数学归纳法可以证明，。所以时间复杂度是。
（2）当时，使用上述方法进行分析，可知在进行划分后数组A中有至多个元素。而递归关系为。若通过归纳法证明出有

的形式，用数学归纳法可以证明，。所以时间复杂度是。
归并排序的 C++语言描述
#include
templatevoid MergeSort(T a[],int left,int right);
templatevoid Merge(T c[],T d[], int l,int m,int r);
templatevoid Copy(T a[],T b[],int l,int r);
void main()
{
int const n(5);
int a[n];

cout<<"Input "<>a[i];
//for(int j=0;jcout<
void MergeSort(T a[],int left,int right) //
{
if(leftft,i,right);
Copy(a,b,left,right);
}

template
void Merge(T c[],T d[],int l,int m,int r)
{
int i=l;
int j=m+1;
int k=l;
while((i<=m)&&(j<=r))
{

if(c[i]<=c[j])d[k++]=c[i++];
else d[k++]=c[j++];
}
if(i>m)
{
for(int q=j;q<=r;q++)
d[k++]=c[q];
}
else
for(int q=i;q<=m;q++)
d[k++]=c[q];
}

template
void Copy(T a[],T b[], int l,int r)
{
for(int i=l;i<=r;i++)
a[i]=b[i];
}

快速排序的 C++语言描述
#include
templatevoid QuickSort(T a[],int p,int r);
templateint Partition(T a[],int p,int r);
void main()
{
int const n(5);
int a[n];
cout<<"Input "<