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

一、简要回答下列问题 ：

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

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

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

:x>A(mid):low←mid+1 :else:j←mid; return

endcase repeat j←0

end BINSRCH

三、算法理解

1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。 2 5 1 3 6 8 4 7 各边的代价如下：

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 3 4 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×XnM ，使得 Xi＋……Xn 最小

请选择贪心策略，并设计贪心算法。

3. 有n个物品，已知n=7, 利润为P=(10,5,15,7,6,18,3)，重量W=(2,3,5,7,1,4,1)，背包容积M=15,物品只能选择全部装入背包或不装入背包，设计贪心算法，并讨论是否可获