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

中南大学现代远程教育课程考试复习试题及参考答案算法分析与设计一 简答题 1. 算法的复杂性分析主要是分析算法的什么耗费情况？ 2. 算法的重要特性是什么？3. 算法的时间复杂度用什么计量？4. 用比较树模型描述三个数排序的过程。5. 分治法的基本思想。6. 二分检索算法为什么可以提高查找的效率？7. 简述顺序选择select算法的基本流程。8. 简述顺序选择select2算法的改进思路。9. 简述快速排序的基本思想。10. 快速排序算法的最坏时间复杂性和平均时间复杂性函数。11. 快速排序算法怎样抽取分割元素？12. partition怎样将数组划分成3段？13. 分治合并排序的是怎样分治的？14. 分治合并排序的二分归并过程在最坏情况下花费多少时间？15. 分治合并排序的二分归并过程在最好情况下花费多少时间？16. MaxMin算法是怎样分治的？17. 贪心法的基本思路是什么？18. 用贪心法求解的问题有什么特点？19. 背包问题的目标函数是什么，最优量度是什么？20. 带限期的作业调度的贪心策略是什么？约束条件是什么？21. 说明n皇后问题的解（x1,x2,.,xn）的含义。22. 简述n皇后算法的place函数的功能。23. 简述动态规划方法所运用最优化原理。24. 用多段图说明最优化原理。二 解释下列动态规划优解的一般递归形式。1） 0/1背包2） 货郎担问题3） 流水作业调度 三 算法分析。1 分析汉诺塔算法的时间复杂性。2 计算冒泡排序算法时间复杂性的阶。3 分析maxmin算法的时间复杂性。4 分析分治合并排序算法的时间复杂性。5 分析二分检索的时间复杂性。6 背包问题贪心算法的时间复杂性。7 快速排序的partition过程中，进行了多少次元素之间的比较。8 多段图算法的时间复杂性。四 算法段填空。 1 MaxMin 算法Maxmin(i,j,max,min)if then 对两元素进行比较;return;else maxmin(i,m,max1,min1); /其中max1和min1为解子问题1的解 2 Hanoi算法Hanoi(n,a,b,c)If n=1 then Else ;Hanoi(n-1,b, a, c);3 二分检索BINSRCH(A,n,x,j)low1;highn;while lowhigh do _ mid(low+high)/2;case ：x=Amid ：jmid; return;：x Amid：_lowmid+1;endcasej0;end4 快速排序Quicksort(p,q)if pq then_ call partition(p,j);call _call _end 5 贪心方法的抽象化控制 procedure GREEDY(A，n) /A(1：n)包含n个输入/ solutions ； for i1 to do xSELECT(A) if FEASIBLE(solution，x) then solutions ； endif return(solution)end GREEDY6 背包问题贪心算法procedure GREEDY-KNAPSACK(P，W，M，X，n) X0 ； cuM ； for i1 to n do if then exit endif X(i) _ ； cu ； if i n then X(i) ； endif end GREEDY-KNAPSACK7 分治合并排序算法procedure MERGESORT(low,high) if low M,i=1,2,3，n。最优解是货船能够装载最多的集装箱。设计贪心算法。4 有n 个程序和长度为L的磁带，程序i的长度为ai，已知，求最优解(xi，x2 ，.，xi， xn)，1, xi =1，表示程序i存入磁带，xi =0，表示程序i不存入磁带，满足，且存放的程序数目最多。参考答案一、 简答题1. 算法的复杂性是算法运行所需要的计算机资源的耗费量，需要的时间资源的耗费量称作时间复杂性。2. 有5个基本特性是：确定性、能行性、输入给定、产生输出、有穷性。3. 算法复杂性用算法的基本运算步骤计量，运算步骤与算法要解的问题的规模、算法的输入有关。4. 比较树模型5. 分治的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。找出各部分的解，然后把各部分的解组合成整个问题的解。6. 分治算法时间是这样确定的：解决子问题所需的工作总量由子问题的个数、解决每个子问题的工作量、合并所有子问题所需的工作量所决定。折半查找最坏情况下，也只需要在原问题一半大小的子问题中查找，而且不需要合并子问题。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算法的最坏情况下的时间复杂性的阶为O(n2)，其原因是ap：j-1和aj+1：q的大小不是均衡的。Select2算法的基本思路就是改随即抽取v为经过经处理产生，保证在最坏情况下ap：j-1和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进行排序。不必进行任何合并操作。10. 快速排序算法的最坏情况下的时间复杂性的阶为O(n2)，其原因是ap：j-1和aj+1：q的大小不是均衡的。快速排序算法的平均时间复杂性的阶为O(n log n)。11. 采用随机抽取。对于数组ap：q，用v= ap作为分割元素。12. 使v= ap，q=q+1while (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=2then 对两元素进行比较产生max,min;return;elsem = (p+q)/2;Maxmin(p,m,max1,min1);maxmin(m+1,q,max2,min2);max=maxnum(max1,max2);min=minnum(min1,min2);17. 贪心算法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。18. 具备最优子结构。19. 目标函数：pi最大，最优量度是选择有最大利润/重量的物品。20. pi最大 ，i属于可完工子集。21. xi表示第i行上的皇后所在的列。22. place函数的功能是判断第k行皇后的位置和前k-1个皇后是否相容。23. 最优化原理：无论过程的初始状态是什么，其余的决策都必须相对于初始决策所产生的状态是最优的。通俗地讲，每一步最优都是上一步最优加上本段的最优。即当前最优只与上一步有关。24. 向前决策到第i段时，第i段的节点j的最优可以用第i-1段的最优值加上本段的长度：cost(i,j)=mincost(i-1,l)+c(j,l) l是i-1段的节点j的后继节点。二、 动态规划递归式1. fi(X)= maxfi-1(X-wi)+pi ，fi-1(X), （0=X1 执行, T(n)=2 T(n-1)+1。用递推式求T(n)。T(n)=2T(n-1)+1=22T(n-2)+1+1=22T(n-2)+2+1=222T(n-3) +2+1=23T(n-3)+ 22+2+1=232T(n-4)+ 1+22+2+1=24T(n-4)+ 23+22+2+1=2n-1T(1)+ 2n-2 +22+2+1=2n-12. 计算冒泡排序算法时间复杂度冒泡排序的主要步骤：for i=1 to n-1 do for j=1 to n-i do if aj aj+1 then 交换aj，aj+1；用比较次数作为算法的计量，比较一次所花的时间为常数，用O(1)表示，内循环所花时间O(1)=O(n-i) ，外循环所花时间：O(n-i)=O(n(n-1)/2)= O(n2)3. 分析MaxMin的比较次数：当n=2，T(2)=1当n2时，比较次数T(n)=2T(n/2)+2设n是2的k次幂， n=2kT(n)=2T(2k-1)+2=22T(2k-1)+2+2=22T(2k-2)+22+2=2k-1T(2)+ 2k-1+22+2=2k-1+ 2k-1+22+2=2k-1+2k-2=3*2k-1-2=3n/2-2T(n)= 3n/2-24. 分治合并排序算法的时间复杂性设n个元素排序的mergesort算法的比较次数为T(n)，当n=1，T(1)=a当n1时：1）分别两次调用mergesort对n/2的元素进行排序，比较次数为2T(n/2)；2）合并两个子问题的解所花时间为n-1T(n)= 2T(n/2)+n-1 设n是2的k次幂， n=2kT(n)=2T(2k-1)+cn=22T(2k-2)+ 2k-1 +n-1= 22T(2k-2)+ 2cn=23T(2k-3)+ 3cn=2kT(1)+kcn=an+c n log n如果2k n2k+1 ，T(n) T(2k+1)T(n)=O(n log n)5. 分析二分检索的时间复杂性当n=1，T(1)=1当n1时：比较1次后，调用原过程在n/2的元素中查找，过程可用一棵二叉树表示。考虑最坏情况：比较到最后，x不在其间，比较次数就是二叉树的深度。所以T(n)= log n+16. 背包问题贪心算法的时间复杂性如果不考虑排序的时间，背包问题贪心算法的时间就是循环语句：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) cu/ w(i)16 分治合并排序算法(low+high)/2; call MERGESORT(low,mid); MERGESORT(mid+1, high)17 多段图动态规划算法COST(n) 0 jn-1 c(j，r)+COST(r) D(j)r j2 to k-118 n后问题递归算法n print(X) call ENQUEENS(k+1) 五.设计算法1. 递归形式的二分检索算法RBINSRCH(A, x, p, q)If p=q then x=Ap then return p else return 0Else mid(low+high)/2;case ：x=Amid ： return (mid) ;：x Amid：return(RBINSRCH(A, x, mid+1,q) );endcaseend2. 设计三分检索算法RSRCH3(A, x, p, q)If p=q then x=Ap then return p else return 0Else i(p+q)/3; j(i+q)/2case ：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