中南大学现代远程教育课程考试复习试题及参考答案

1、中南大学现代远程教育课程考试复习试卷及参考答案 算法分析与设计 简答题 1. 算法的复杂性分析主要是分析算法的什么耗费情况？ 2. 算法的重要特性是什么？ 3. 算法的时间复杂度用什么计量？ 4. 用比较树模型描述三个数排序的过程。 5. 分治法的基本思想。 6. 二分检索算法为什么可以提高查找的效率？ 7. 简述顺序选择 select 算法的基本流程。 8. 简述顺序选择 select2 算法的改进思路。 9. 简述快速排序的基本思想。 10. 快速排序算法的最坏时间复杂性和平均时间复杂性函数。 11. 快速排序算法怎样抽取分割元素？ 12. partition 怎样将数组划分成 3 段？

2、13. 分治合并排序的是怎样分治的？ 14. 分治合并排序的二分归并过程在最坏情况下花费多少时间？ 15. 分治合并排序的二分归并过程在最好情况下花费多少时间？ 16. MaxMin 算法是怎样分治的？ 17. 贪心法的基本思路是什么？ 18. 用贪心法求解的问题有什么特点？ 19. 背包问题的目标函数是什么，最优量度是什么？ 20. 带限期的作业调度的贪心策略是什么？约束条件是什么？ 21. 说明n皇后问题的解(Xi,X2,.,x n)的含义。 22. 简述 n 皇后算法的 place 函数的功能。 23. 简述动态规划方法所运用最优化原理。 24. 用多段图说明最优化原理。 二 解释下列动

3、态规划优解的一般递归形式。 1 ) 0/1 背包 2) 货郎担问题 3) 流水作业调度 三 算法分析。 1分析汉诺塔算法的时间复杂性。 2计算冒泡排序算法时间复杂性的阶。 3分析 maXmin 算法的时间复杂性。 4分析分治合并排序算法的时间复杂性。 5分析二分检索的时间复杂性。 6背包问题贪心算法的时间复杂性。 7快速排序的 partition 过程中，进行了多少次元素之间的比较。 8. 多段图算法的时间复杂性。 四算法段填空。 1. MaxMin 算法 Maxmi n(i,j,max,mi n) if then 对两元素进行比较。return。 else maxmin(i,m,max1,m

4、in1)。/ 其中 maxi和 mini 为解子问题 1 的解 2. Hanoi 算法 Hano i( n, a,b,c) If n=1 the n Else Hanoi(n-1,b, a, c) 3. 二分检索 BINSRCH(A, n,x,j) low j 1。 high jn。 while lowhigh do mid j (low+high)/2 。 case :x=Amid : j j mid。 return 。 :x Amid : low j mid+1。 endcase j J 0。 end 4 快速排序 Quicksort(p,q) if pq then call partit

5、i on( p,j)。 call call end 5. 贪心方法的抽象化控制 procedure GREEDY(A , n) A(1: n)包含n个输入/ soluti ons J； for ij 1 to do x JSELECT(A) if FEASIBLE(solution, x) then solutionsJ ; en dif retur n( soluti on) end GREEDY 6. 背包问题贪心算法 procedure GREEDY-KNAPSACK(P W M X , n) X J 0； cu J M ; for i j 1 to n do ifthe n exite

6、 ndif X(i) J； cu j； if i n then X(i) j; en dif end GREEDY-KNAPSACK 7. 分治合并排序算法 procedure MERGESORT(low,high) if low M,i=1,2,3 ，n。最优解是货船能够装载最多的集装箱。设计贪 心算法。 4. 有n个程序和长度为 L的磁带，程序i的长度为a,已知ai - L，求最优解(Xi, i 4 X2 , . , Xi,，x n) , 1, x i =1，表示程序i存入磁带，Xi =0 ,表示程序i不存入 n 磁带，满足v xia L，且存放的程序数目最多。 i 4 参考答案 一、简答

7、题 1. 算法的复杂性是算法运行所需要的计算机资源的耗费量，需要的时间资源的耗费量称 作时间复杂性。 2. 有5个基本特性是：确定性、能行性、输入给定、产生输出、有穷性。 3. 算法复杂性用算法的基本运算步骤计量，运算步骤与算法要解的问题的规模、算法的 输入有关。 4. 比较树模型 5. 分治的基本思想是将一个规模为 n的问题分解为k个规模较小的子问题，这些子问题 互相独立且与原问题相同。找出各部分的解，然后把各部分的解组合成整个问题的 解。 6. 分治算法时间是这样确定的：解决子问题所需的工作总量由子问题的个数、解决每个 子问题的工作量、 合并所有子问题所需的工作量所决定。折半查找最坏情况下

8、，也只 需要在原问题一半大小的子问题中查找，而且不需要合并子问题。 7. 首先对于数组 ap : q进行划分，以元素 v为基准元素将 a划分为三段ap : j-1, aj和aj+1 : q，使得ap : j-1中任何一个元素都小于 v, aj+1 : q中任何一个元 素大于等于v,下标j在划分中确定。 如果k = j ，则返回v； 如果k j ，则在aj+1 : q中选择； 8. select算法的最坏情况下的时间复杂性的阶为0(n)，其原因是ap : j-1和aj+1 : q 的大小不是均衡的。Select2算法的基本思路就是改随即抽取v为经过经处理产生，保 证在最坏情况下 ap : j-1

9、和aj+1 : q的元素个数不会小于原规模的1/4。 9. 快速排序是基于分治策略的一个排序算法。基本思路： a) 分解(Divide) 以元素v为基准元素将a划分为三段 ap : j-1 , aj和 aj+1 : q，使得ap : j-1中任何一个元素都小于 v, aj+1 : q中任何一个 元素大于等于v,下标j在划分中确定。 b) 递归求解，通过递归调用快速排序算法分别对ap:j-1 和aj+1:q进行排 序。 不必进行任何合并操作。 2 10. 快速排序算法的最坏情况下的时间复杂性的阶为O(n)，其原因是ap : j-1和 aj+1 : q的大小不是均衡的。快速排序算法的平均时间复杂性

10、的阶为O(n log n)。 11. 采用随机抽取。对于数组 ap : q，用v= ap作为分割元素。 12. 使 v= ap , q=q+1 while (pq) do do p+ 。while (ap v)。 if (pq) 交换 ap和 aq; 13. if问题不可分then求解 else m = (p+q)/2。 对ap,m排序； 对am+1, q排序； 将 ap,m和 am+1, q合并； 14. 分治合并排序的二分归并过程在最坏情况下需比较n-1次，花费可用cn表示。 15. 最好情况下需比较n/2次。 16. Maxmin(p,q,max,min) if 问题不可分：n=2 th

11、en对两元素进行比较产生max,min。 return 。 else m = (p+q)/2。 Maxmin(p,m,max1,min1)。 maxmin(m+1,q,max2,min2)。 max=max num (max1,max2。 min=minnum(min1,min2)。 17. 贪心算法的基本思路： 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当 达到某算法中的某一步不能再继续前进时，算法停止。 18. 具备最优子结构。 19. 目标函数：刀 pi最大，最优量度是选择有最大利润/重量的物品。 20. 刀pi最大，i属于可完工子集。 21. Xi表示第i

12、行上的皇后所在的列。 22. place函数的功能是判断第k行皇后的位置和前 k-1个皇后是否相容。最优化原理：无 论过程的初始状态是什么，其余的决策都必须相对于初始决策所产生的状态是最优 的。通俗地讲，每一步最优都是上一步最优加上本段的最优。即当前最优只与上一步 有关。向前决策到第i段时，第i段的节点j的最优可以用第i-1段的最优值加上本 段的长度： cost(i,j)=mincost(i-1,l)+c(j,l) l是 i-1 段的节点 j 的后继节点。 二、动态规划递归式 1. fi(X)= maxf i-1 (X-wJ+pi, fi-1 (X),(0=X1执行，T(n)=2 T(n-1)

13、+1。用递推式求T(n)。 T(n )=2T( n-1)+1 2 =22T (n-2)+1+1=2T( n-2)+2+1 2 32 =2 2T(n-3) +2+1=2T(n-3)+ 2+2+1 3 2432 =2 2T(n-4)+ 1+2+2+1=2 T(n-4)+ 2 +2 +2+1 =2n-1 T(1)+ 2 n-2 +22+2+1 =2n-1 2. 计算冒泡排序算法时间复杂度 冒泡排序的主要步骤： for i=1 to n-1 do for j=1 to n-i do if aj aj+1 then交换 aj , aj+1; 用比较次数作为算法的计量，比较一次所花的时间为常数，用0(1)

14、表示，内循环所花 时间工O(1)=O(n-i)，外循环所花时间： 2 工 O(n-i)=O(n(n-1)/2)= O(n ) 3. 分析MaxMin的比较次数： 当 n=2, T(2)=1 当n2时，比较次数 T(n)=2T(n/2)+2 设n是2的k次幕，n=2 k k-1 T( n)=2T(2)+2 k-12k-22 =22T(2)+2+2=2 T(2 )+2 +2 =2k-1 T(2)+ 2 k-1+2 2+2 =2k-1 + 2 k-1+2 2+2 =2k-1 +2k-2 k-1 =3*2 k-1 -2=3n/2-2 T(n)= 3n/2-2 4. 分治合并排序算法的时间复杂性 设 n

15、 个元素排序的 mergesort 算法的比较次数为 T(n) ， 当 n=1， T(1)=a 当 n1 时： 1)分别两次调用 mergesort 对 n/2 的元素进行排序，比较次数为 2T(n/2) ； 2)合并两个子问题的解所花时间为n-1 T(n)= 2T(n/2)+n-1 设 n 是 2 的 k 次幂， n=2 k k-1 T(n)=2T(2 k-1)+cn =22T(2 k-2)+ 2 k-1 +n-1= 2 2T(2 k-2 )+ 2cn =23T(2 k-3)+3cn =2kT(1)+kcn =an+c n log n k k+1 k+1 如果 2 w nW2 , T(n)

16、1 时： 比较 1 次后，调用原过程在 n/2 的元素中查找，过程可用一棵二叉树表示。 考虑最坏情况：比较到最后， x 不在其间，比较次数就是二叉树的深度。 所以 T(n)= log n+1 6. 背包问题贪心算法的时间复杂性 如果不考虑排序的时间，背包问题贪心算法的时间就是 循环语句： for i=1 to n do 执行的时间，循环体语句可以用常数 c 表示， 算法的时间复杂性为： T(n)=cn 。 7. 快速排序的 partition 的比较次数 partition 的主要步骤： while (pq) do do p+ 。 while (ap v)。 if (pcu 1 cu-w(i)

17、 cu/ w(i) 16. 分治合并排序算法 (low+high)/2 。 call MERGESORT(low,mid) 。MERGESORT(mid+1, high) 17. 多段图动态规划算法 COST(n) 0 j j n-1 c(j , r)+COST(r) D(j) j rj j 2 to k-1 18. n后问题递归算法 nprin t(X)call ENQUEENS(k+1) 五. 设计算法 1. 递归形式的二分检索算法 RBINSRCH(A, x, p, q) If p=q the n x=Ap the n retur n p else retur n 0 Else mid

18、j (low+high)/2 。 case :x=Amid : return (mid) 。 :x Amid : return(RBINSRCH(A, x, mid+1,q) endcase end 2. 设计三分检索算法 RSRCH3(A, x, p, q) If p=q then x=Ap then return p else return 0 Else i J(P+q3。j (i+q)/2 case ： x=Ai： return (i)。 ： x=Aj： return (j)。 ：x Ai and xAj：return(RBINSRCH(A, x, i+1,j-1) )。 else return(RBINSRCH(A, x, j+1,