《中南大学现代远程教育课程考试复习试题及参考答案》由会员分享，可在线阅读，更多相关《中南大学现代远程教育课程考试复习试题及参考答案（10页珍藏版）》请在金锄头文库上搜索。
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. pi最大 ，i属于可完工子集。21. xi表示第i行上的皇后所在的列。22. place函数的功能是判断第k行皇后的位置和前k-1个皇后是否相容。23. 最优化原理：无论过程的初始状态是什么，其余的决策都必须相对于初始决策所产生的状态是最优的。通俗地讲，每一步最优都是上一步最优加上本段的最优。即当前最优只与上一步
