《算法分析与设计考试复习题及参考答案.pdf》由会员分享，可在线阅读，更多相关《算法分析与设计考试复习题及参考答案.pdf（13页珍藏版）》请在三一文库上搜索。
1、一、简要回答下列问题： 1.算法重要特性是什么？ 2.算法分析的目的是什么？ 3.算法的时间复杂性与问题的什么因素相关？ 4.算法的渐进时间复杂性的含义？ 5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？ 6.简述二分检索（折半查找）算法的基本过程。 7.背包问题的目标函数和贪心算法最优化量度相同吗？ 8.采用回溯法求解的问题，其解如何表示？有什么规定？ 9.回溯法的搜索特点是什么？ 10. n 皇后问题回溯算法的判别函数place 的基本流程是什么？ 11. 为什么用分治法设计的算法一般有递归调用？ 12. 为什么要分析最坏情况下的算法时间复杂性？ 13. 简述渐进时间复杂性上界的定义
2、。 14. 二分检索算法最多的比较次数？ 15. 快速排序算法最坏情况下需要多少次比较运算？ 16. 贪心算法的基本思想？ 17. 回溯法的解（ x1,x2, xn）的隐约束一般指什么？ 18. 阐述归并排序的分治思路。 19. 快速排序的基本思想是什么。 20. 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？ 21. 什么是哈密顿环问题？ 22. 用回溯法求解哈密顿环，如何定义判定函数？ 23. 请写出 prim 算法的基本思想。 二、复杂性分析 1、 MERGESORT(low，high) if lowM then return endif aa+i ii+1 ; repeat
3、 end 3.procedure PARTITION(m,p) Integer m,p,i;global A(m:p-1) vA(m);i m loop loop ii+1 until A(i) v repeat loop p p-1 until A(p) v repeat if ixmax then xmaxA(i); ji;endif repeat end MAX 6.procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low1;high n while lowhigh do mid|_ (low+high)/2_| case :xA(
4、mid):lowmid+1 :else:j mid; return endcase repeat j0 end BINSRCH 三、算法理解 1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。 各边的代价如下： 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、出 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、 写出图着色问题的回溯算法的判断Xk 是否合理的过程。 7、 对于下图，写出图着色算法得出一种着色方案的过程。 8、 写出第 7 题的状态空间树。 9、 写出归并排序算法对下列实例排序的过程。 (6,2,9,3,5,1,8,7) 10、 写出
6、用背包问题贪心算法解决下列实例的过程。 P=(18,12,4,1) 5 1 3 4 2 6 7 8 1 3 4 2 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的一棵最小生成树。 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)=
7、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 函数定义如下： 当 x100 时 m(x)=x-10; 当 x1 时 F1(n) 的时间复杂度与F2(2,n,1,1)的时间复杂度相同即为为 O(n) 5、 xmaxA(1);j1 时间为： O(1) for i2 to n do 循环最多 n-1 次 所以总时间为 : T(n)=O(1)+ (n-1)O(1)= O(n) 6、log2n+1
8、三、算法理解 1、 1)2/(2 1 )( ncnnT na nT ncnan kcnT cnnT cncnnTnT k log )1 (2 2)4/(4 )2/)4/(2(2)( Cost(4,8)=0 Cost(3,7)= C(7,8)+0=6 ，D5=8 Cost(3,6)= C(6，8)+0=5, D6=8 Cost(3,5)= C(5，8)+0=4 D7=8 Cost(2,4)= minC(4，6)+ Cost(3,6), C(4，5)+ Cost(3,5) = min1+ 5, 2+4=6 D4=6 Cost(2,3)= minC(3，6)+ Cost(3,6) = min4+5=
9、9 D3=5 Cost(2,2)= minC(2，6)+ Cost(3,6), C(2，7)+ Cost(3,7) = min8+5, 4+6=10 D2=7 Cost(1,1)= minC(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ Cost(2,4) = min3+10, 5+9,2+6= 8 D1=4 14 68 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 1932，57 4、 61
10、 32 35 5、 61 3 3、给出 5 个数 (3,6,9,1,7),M=12， 用递归树描述sumofsub 算法求和数 =M的一个子集 的过程。 4、第一个分割元素为65 5、 1，28，0 2，25，3 3，19，3 4，10，12 (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 48,12,61,3
11、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 iCU: x3CU/ W3=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的一棵最小生成树。 dist(1,2)=6;dis
12、t(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; 1 2 4 3 5 6 1 3 1 6 1 3 6 4 1 2 6 4 5 1 2 6 3 4 3 3 已知 a=10,b=4,c=5 则执行 k=f(f(a+c,b),f(b,c)后， k 的值是多少并写出详细过程。 K 的值是 5 14. McCathy 函数定义如下： 当 x100 时 m(
13、x)=x-10; 当 x100) 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=A1;min=A1; for(i=2;imax)max=Ai; else if(Aicu 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
14、, 1,0）可获利润54 因此贪心法不一定获得最优解。 4 Hamiltonian(n) k 1; xk 0; While k0 do xk xk+1; while B(k)=false and xkn do xk xk+1; repeat If xkn then if k=n then print x; return else k k+1; xk0; endif else k k-1 endif repeat end procedure B(k) Gxk-1,xk 1 then return false; for i1 to k-1 do if xi=xk then return false
15、;endif repeat return true; 5利用对称性设计算法，求n 为偶数的皇后问题所有解。 procedure NQUEENS1(n) a0 /计数器清零 X(1) 0；k1 /k是当前行； X(k) 是当前列 / While k0 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) ，aa+1 /找到一个解计数器a加 1/ if a=n/2 then return / 找到 n/2 个解算法结束 3) else kk+1；X(k) 0； 4) else k k1 /回溯 / end NQUEENS