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

《2023年中南大学现代远程教育课程考试复习试题及参考答案.doc》由会员分享，可在线阅读，更多相关《2023年中南大学现代远程教育课程考试复习试题及参考答案.doc（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、14. 分治合并排序的二分归并过程在最坏情况下花费多少时间？15. 分治合并排序的二分归并过程在最佳情况下花费多少时间？16. MaxMin算法是如何分治的？17. 贪心法的基本思绪是什么？18. 用贪心法求解的问题有什么特点？19. 背包问题的目的函数是什么，最优量度是什么？20. 带限期的作业调度的贪心策略是什么？约束条件是什么？21. 说明n皇后问题的解（x1,x2,.,xn）的含义。22. 简述n皇后算法的place函数的功能。23. 简述动态规划方法所运用最优化原理。24. 用多段图说明最优化原理。二 解释下列动态规划优解的一般递归形式。1） 0/1背包2） 货郎担问题3） 流水作业

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

4、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

5、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。最优解是

6、货船可以装载最多的集装箱。设计贪心算法。4 有n 个程序和长度为L的磁带，程序i的长度为ai，已知，求最优解(xi，x2 ，.，xi， xn)，1, xi =1，表达程序i存入磁带，xi =0，表达程序i不存入磁带，满足，且存放的程序数目最多。参考答案一、 简答题1. 算法的复杂性是算法运营所需要的计算机资源的花费量，需要的时间资源的花费量称作时间复杂性。2. 有5个基本特性是：拟定性、能行性、输入给定、产生输出、有穷性。3. 算法复杂性用算法的基本运算环节计量，运算环节与算法要解的问题的规模、算法的输入有关。4. 比较树模型5. 分治的基本思想是将一个规模为n的问题分解为k个规模较小的子问题

7、，这些子问题互相独立且与原问题相同。找出各部分的解，然后把各部分的解组合成整个问题的解。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算法的最坏

8、情况下的时间复杂性的阶为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. 快速排序算法的

9、最坏情况下的时间复杂性的阶为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

10、/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. p

11、i最大 ，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

12、=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)表达，内循环所

13、花时间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）分别两

14、次调用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不在

15、其间，比较次数就是二叉树的深度。所以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)

16、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

17、(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, j+1,q) );endcaseend3. 集装箱问题由于货船的容积没有受限制，约束是船的载重，因此可以选择最当前重量最小的集装箱，使船装载的货品总重量增长得最慢。Greedy-trunk /输入按w(1)w(2) cu then break;X(i) 1;cu cu-w(i);repeatend4. 磁带由于求的是长度约束下的装最多的程序，应当选择长度最小的程序装入，使磁带消耗最慢。Greedy-tape /输入按a(1)a(2) cu then break;X(i) 1;cu cu-a(i);repeatend