算法分析与设计考试复习题及参考答案.doc

一、简要回答下列问题 ：
1. 算法重要特性是什么？
2. 算法分析的目的是什么？
3. 算法的时间复杂性与问题的什么因素相关？
4. 算法的渐进时间复杂性的含义？
5. 最坏情况下的时间复杂性和平均时间复杂性有什么不同？
6. 简述二分检索（折半查找）算法的基本过程。
7. 背包问题的目标函数和贪心算法最优化量度相同吗？
8. 采用回溯法求解的问题，其解如何表示？有什么规定？
9. 回溯法的搜索特点是什么？
10. n皇后问题回溯算法的判别函数place的基本流程是什么？
11. 为什么用分治法设计的算法一般有递归调用？
12. 为什么要分析最坏情况下的算法时间复杂性？
13. 简述渐进时间复杂性上界的定义。
14. 二分检索算法最多的比较次数？
15. 快速排序算法最坏情况下需要多少次比较运算？
16. 贪心算法的基本思想？
17. 回溯法的解（x1,x2,……xn）的隐约束一般指什么？
18. 阐述归并排序的分治思路。
19. 快速排序的基本思想是什么。
20. 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？
21. 什么是哈密顿环问题？
22. 用回溯法求解哈密顿环，如何定义判定函数？
23. 请写出prim算法的基本思想。

二、复杂性分析
1、 MERGESORT(low，high)
if low<high；
then mid←(low，high)/2；
MERGESORT(low，mid)；
MERGESORT(mid+1，high)；
MERGE(low，mid，high)；
endif
end MERGESORT
2、 procedure S1(P，W，M，X，n)
i←1; a←0
while i≤ n do
if W(i)>M then return endif
a←a+i
i←i+1 ;
repeat
end

3.procedure PARTITION(m,p)
Integer m,p,i;global A(m:p-1)
v←A(m);i←m
loop
loop i←i+1 until A(i) ≥v repeat
loop p←p-1 until A(p) ≤v repeat
if i<p
then call INTERCHANGE(A(i),A(p))
else exit
endif
repeat
A(m) ←A(p);A(p) ←v
End PARTITION

4.procedure F1(n)
if n<2 then return(1)
else return(F2(2,n,1,1))
endif
end F1
procedure F2(i,n,x,y)
if i≤n
then call F2(i+1,n,y,x+y)
endif
return(y)
end F2

5.procedure MAX(A,n,j)
xmax←A(1);j←1
for i←2 to n do
if A(i)>xmax then xmax←A(i); j←i;endif
repeat
end MAX

6.procedure BINSRCH(A,n,x,j)
integer low,high,mid,j,n;
low←1;high←n
while low≤high do
mid←|_(low+high)/2_|
case
:x<A(mid):high←mid-1
:x>A(mid):low←mid+1
:else:j←mid; return
endcase
repeat
j←0
end BINSRCH

三、算法理解
1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。

5
2

8
6
3
1

7
4

各边的代价如下：
C(1,2)=3， C(1,3)=5 ，C(1,4)=2
C(2,6)=8 ，C(2,7)=4 ，C(3,5)=5 ，C(3,6)=4， C(4,5)=2，C(4,6)=1
C(5,8)=4， C(6,8)=5 ，C(7,8)=6

2、 写出maxmin算法对下列实例中找最大数和最小数的过程。
数组 A=(48,12,61,3,5,19,32,7)
3、 给出5个数(3,6,9,1,7),M=13，用递归树描述sumofsub算法求和数=M的一个子集的过程。
4、 快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。
A=(65,70,75,80,85,55,50,2)
5、 归并排序算法对下列实例排序，写出算法执行过程。
A=(48,12,61,3,5,19,32,7)
6、 写出图着色问题的回溯算法的判断X[k]是否合理的过程。
7、 对于下图，写出图着色算法得出一种着色方案的过程。
2

3

1

4

8、 写出第7题的状态空间树。
9、 写出归并排序算法对下列实例排序的过程。
(6,2,9,3,5,1,8,7)
10、 写出用背包问题贪心算法解决下列实例的过程。
P=(18,12,4,1)
W=(12,10,8,3)
M=25
11、有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当使用二分查找值为82的结点时，经过多少次比较后查找成功并给出过程。
12、使用prim算法构造出如下图G的一棵最小生成树。

1
2
4
3
5
6

dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;
dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6
13、有如下函数说明
int f(int x,int y)
{
f=x Mod y +1;
}
已知a=10,b=4,c=5 则执行k=f(f(a+c,b),f(b,c))后，k的值是多少并写出详细过程。
14、McCathy函数定义如下：
当x>100时 m(x)=x-10;
当x<=100时 m(x)=m(m(x+11));
编写一个递归函数计算给定x的m(x)值。
15、 设计一个算法在一个向量A中找出最大数和最小数的元素。

四、设计算法
1. 设有n项独立的作业{1,2,…, n},由m台相同的机器加工处理。作业i所需要的处理时间为ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业。
多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。设计算法，并讨论是否可获最优解。
2. 设有n种面值为:
d1≥d2≥……≥dn的钱币，需要找零钱M，如何选择钱币dk，的数目Xk，满足
d1×Xi＋……dn×Xn=M ，使得
Xi＋……Xn 最小
请选择贪心策略，并设计贪心算法。
3. 有n个物品，已知n=7, 利润为P=(10,5,15,7,6,18,3)，重量W=(2,3,5,7,1,4,1)，背包容积M=15,物品只能选择全部装入背包或不装入背包，设计贪心算法，并讨论是否可获最优解。
4. 设计只求一个哈密顿环的回溯算法。
5．利用对称性设计算法，求n为偶数的皇后问题所有解。

参考答案
一、简要回答下列问题 ：
1. 确定性、可实现性、输入、输出、有穷性
2. 分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。
3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。
4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。
5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：
W(n) = max{ T(n，I) } , I∈Dn
平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：
A(n) =∑P(I)T(n，I) I∈Dn
6. 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较，如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]<x，则A[i：(i+j)/2-1]找x，否则在A[ (i+j)/2+1：j] 找x。上述过程被反复递归调用。
回溯法的搜索特点是什么
7. 不相同。目标函数：获得最大利润。最优量度：最大利润/重量比。
8. 问题的解可以表示为n元组：（x1,x2,……xn），xi∈Si, Si为有穷集合，xi∈Si, （x1,x2,……xn）具备完备性，即（x1,x2,……xn）是合理的，则（x1,x2,……xi）(i<n)一定合理。
9. 在解空间树上跳跃式地深度优先搜索，即用判定函数考察x[k]的取值，如果x[k]是合理的就搜索x[k]为根节点的子树，如果x[k]取完了所有的值，便回溯到x[k-1]。
10. 将第K行的皇后分别与前k-1行的皇后比较，看是否与它们相容，如果不相容就返回false，测试完毕则返回true。
11 . 子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。
12 最坏情况下的时间复杂性决定算法的优劣，并且最坏情况下的时间复杂性较平均时间复杂性游可操作性。
13 .T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数No和C，n〉No，有T(n)<f(n)，这种关系记作T(n)=O(f(n))。
14 .二分检索算法的最多的比较次数为 log n 。
15．.最坏情况下快速排序退化成冒泡排序，需要比较n2次。
16. 是一种依据最优化量度依次选择输入的分级处理方法。基本思路是：首先根据题意，选取一种量度标准；然后按这种量度标准对这n个输入排序，依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。
17．回溯法的解（x1,x2,……xn）的隐约束一般指个元素之间应满足的某种关系。
18. 讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。
19.快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一次快速排序。之后重复上述过程，直到每一部分内只有一个记录为止。
20.在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。
21.哈密顿环是指一条沿着图G的N条边环行的路径，它的访问每个节点一次并且返回它的开始位置。
22.当前选择的节点X[k]是从未到过的节点,即X[k]≠X[i](i=1,2,…,k-1)，且C(X[k-1], X[k])≠∞，如果k=-1，则C(X[k], X[1]) ≠∞。
23. 思路是：最初生成树T为空，依次向内加入与树有最小邻接边的n-1条边。处理过程：首先加入最小代价的一条边到T，根据各节点到T的邻接边排序，选择最小边加入，新边加入后，修改由于新边所改变的邻接边排序，再选择下一条边加入，直至加入n-1条边。

二、复杂性分析
1、 递归方程

设n=2k
解递归方程：

2、
i←1 ;s←0 时间为：O(1)
while i≤ n do 循环n次
循环体内所用时间为 O(1)
所以 总时间为:
T(n)=O(1)+ nO(1)= O(n)

3、最多的查找次数是p-m+1次

4、F2（2，n,1,1）的时间复杂度为：
T(n)=O(n-2); 因为i≤n时要递归调用F2，一共是n-2次
当n＝1时F1(n)的时间为 O(1)
当n>1时F1(n)的时间复杂度与F2(2,n,1,1)的时间复杂度相同即为为 O(n)
5、
xmax←A(1);j←1 时间为：O(1)
for i←2 to n do 循环最多n-1次
所以 总时间为:
T(n)=O(1)+ (n-1)O(1)= O(n)
6、log2n+1
三、算法理解
1、
Cost(4,8)=0
Cost(3,7)= C(7,8)+0=6 ，D[5]=8
Cost(3,6)= C(6，8)+0=5, D[6]=8
Cost(3,5)= C(5，8)+0=4 D[7]=8

Cost(2,4)= min{C(4，6)+ Cost(3,6), C(4，5)+ Cost(3,5)}
= min{1+ 5, 2+4}=6 D[4]=6
Cost(2,3)= min{C(3，6)+ Cost(3,6) }
= min{4+5}=9 D[3]=5
Cost(2,2)= min{C(2，6)+ Cost(3,6), C(2，7)+ Cost(3,7)}
= min{8+5, 4+6}=10 D[2]=7

Cost(1,1)= min{C(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ Cost(2,4)}
= min{3+10, 5+9,2+6}= 8
D[1]=4
1→4→6→8
2、 写出maxmin算法对下列实例中找最大数和最小数的过程。
数组 A=()
1、 48,12,61,3, 5,19,32,7
2、48,12 61,3 5,19 32,7
3、 48～61, 12～3 19～32，5～7
4、 61～32 3～5
5、 61 3
3、 给出5个数(3,6,9,1,7),M=12，用递归树描述sumofsub算法求和数=M的一个子集的过程。
1，28，0

2，25，3

3，19，3

4，10，12

4、第一个分割元素为65
(1) (2) (3) (4) (5) (6) (7) (8) i p
65 70 75 80 85 55 50 2 2 8
65 2 75 80 85 55 50 70 3 7
65 2 50 80 85 55 75 70 4 6
65 2 50 55 85 80 75 70 4 6
55 70 75 80 85 65 50 2

5、
48,12,61,3 5,19,32,7
48,12 61,3 5,19 32,7
12,48 3,61 5,19 7,32
3, 12, 48, 61 5, 7, 19，32
3,5, 7,12，19，32，48,61
6、
i←0
while i<k do
if G[k,i]=1 and X[k]= X[i] then
return false
i←i+1
repeat
if i= k then return true
7、
K←1
X[1] ←1 , 返回 true
X[2]←1,返回false; X[2]←X[2]+1=2, 返回 true
X[3]←1 ,返回false; X[3]←X[3]+1=2, 返回false;X[3]←X[3]+1=3, 返回 true
X[4]←1, 返回false; X[4]←X[4]+1=2, 返回false;X[4]←X[4]+1=3, 返回 true
找到一个解 （1，2，3，3）

8、

X[1]=1

X[2]=2

X[3]=33

X[4]=33

9、
调用第一层次 6,2,9,3 5,1,8,7 分成两个子问题
调用第二层次 6,2 9,3 5,1 8,7 分成四个子问题
调用第三层次 6 2 9 3 5 1 8 7 分成八个子问题
调用第四层次 只有一个元素返回上一层
第三层归并 2 ,6 3, 9 1,5 7,8 返回上一层
第二层归并 2 ,3,6, 9 1,5,7,8 返回上一层
第一层归并 1, 2 ,3, 5 ,6, 7, 8,9 排序结束，返回主函数
10、实例符合P(i)/W(i)≥P(i+1)/W(i+1)的顺序。
CU←25,X←0
W[1]< CU: x[1]←1; CU←CU-W[1]=13;
W[2]< CU: x[2]←1; CU←CU-W[2]=3;
W[3]>CU: x[3]←CU/ W[3]=3/8;
实例的解为：（1，1，3/8，0）
11 有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当使用二分查找值为82的结点时，经过多少次比较后查找成功并给出过程。
一共要要执行四次才能找到值为82的数。

12．使用普里姆算法构造出如下图G的一棵最小生成树。

1
2
4
3
5
6

dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;
dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6

1
3
1
6
1
3
6
4
1
2
6
4
5
1
2
6
3
4
3
3

13.有如下函数说明
int f(int x,int y)
{
f=x Mod y +1;
}
已知a=10,b=4,c=5 则执行k=f(f(a+c,b),f(b,c))后，k的值是多少并写出详细过程。

}
K的值是5

14.McCathy函数定义如下：
当x>100时 m(x)=x-10;
当x<=100时 m(x)=m(m(x+11));
编写一个递归函数计算给定x的m(x)值。
int m(int x)
{
int y;
if(x>100) return(x-100);
else
{
y=m(x+11);
return (m(y));
}
}
15 设计一个算法在一个向量A中找出最大数和最小数的元素。
Void maxmin(A,n)
Vector A;
int n;
{
int max,min,i;
max=A[1];min=A[1];
for(i=2;i<=n;i++)
if(A[i]>max)max=A[i];
else if(A[i]<min)min=A[i];
printf(“max=%d,min=%d\n”,max,min);
}
四、设计算法
1. 设有n项独立的作业{1,2,…, n},由m台相同的机器加工处理。作业i所需要的处理时间为ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业。
多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。设计算法，并讨论是否可获最优解。
2. 设有n种面值为:
d1≥d2≥……≥dn的钱币，需要找零钱M，如何选择钱币dk，的数目Xk，满足
d1×Xi＋……dn×Xn=M ，使得
Xi＋……Xn 最小
请选择贪心策略，并设计贪心算法。
3. 有n个物品，已知n=7, 利润为P=(10,5,15,7,6,18,3)，重量W=(2,3,5,7,1,4,1)，背包容积M=15,物品只能选择全部装入背包或不装入背包，设计贪心算法，并讨论是否可获最优解。
4. 设计只求一个哈密顿环的回溯算法。
5．利用对称性设计算法，求n=2k（K为正整数）的皇后问题所有解。
1.
解：对于处理机j，用S[j] 表示处理机j已有的作业数，用P[j,k]表示处理机j的第k个作业的序号 。
1）将作业按照t[1]≥t[2]≥……≥t[n]排序
2）S[1:m]清零 j←0 //从第一个处理机开始安排
3) for i←1 to n do //安排n个作业
j←j mod m +1 //选下一个处理机
S[j]←S[j]+1;
P[j,S[j]]←i ；
Repeat
2.
贪心原则：每次选择最大面值硬币。

CU←M;i←1;X←0 // X为解向量
While CU≠0 do
X[i]←CU div d[i] // X[i]为第i中硬币数
CU←CU-d[i]*X[i]
i←i+1;
repeat
3、
定义结构体数组G，将物品编号、利润、重量作为一个结构体：例如G[k]={1,10,2}
求最优解，按利润/重量的递减序，有
{5,6,1,6} {1,10,2,5}{6,18,4,9/2} {3,15,5,3} {7,3,1,3}{2,5,3,5/3} {4,7,7,1}
算法
procedure KNAPSACK(P，W，M，X，n)
//P(1：n)和W(1；n)分别含有按
P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值
和重量。M是背包的容量大小，而x(1：n)是解向量//
real P(1：n)，W(1：n)，X(1：n)，M，cu；
integer i，n；
X←0 //将解向量初始化为零//
cu←M //cu是背包剩余容量//
for i←1 to n do
if W(i)>cu then exit endif
X(i) ←1
cu←cu-W(i)
repeat
end GREEDY-KNAPSACK
根据算法得出的解：
X=（1,1,1,1,1,0,0）获利润52， 而解
（1,1,1,1, 0, 1,0）可获利润54
因此贪心法不一定获得最优解。

4．
Hamiltonian(n)
{k←1; x[k] ←0;
While k>0 do
x[k] ← x[k]+1;
while B(k)=false and x[k]≤n do
x[k] ← x[k]+1; repeat
If x[k]≤n then
if k=n then {print x; return}
else {k← k+1; x[k]←0;} endif
else k← k-1
endif
repeat
end

procedure B(k)
{ G[x[k-1],x[k] ]≠1 then return false;
for i←1 to k-1 do
if x[i]=x[k] then return false;endif
repeat
return true;
}
5．利用对称性设计算法，求n为偶数的皇后问题所有解。
procedure NQUEENS1(n)
a←0 //计数器清零
X(1)←0；k←1 //k是当前行；X(k)是当前列//
While k>0 do //对所有的行执行以下语句//
1) { X(k)←X(k)+1 //移到下一列//
While X(k)≤n and not PLACE(k) do
2) X(k)←X(k)十l
if X(k)≤n
then if k=n /
then
{print(X)，a←a+1 //找到一个解计数器a加1//
if a=n/2 then return // 找到n/2个解算法结束
3) else {k←k+1；X(k)←0；}
4) else k←k－1 //回溯//
　 }
end NQUEENS