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

1、资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。中南大学现代远程教育课程考试复习试题及参考答案算法分析与设计一 简答题1.2.3.4.5.6.7.算法的复杂性分析主要是分析算法的什么耗费情况?算法的重要特性是什么?算法的时间复杂度用什么计量?用比较树模型描述三个数排序的过程。分治法的基本思想。二分检索算法为什么能够提高查找的效率?简述顺序选择select算法的基本流程。8. 简述顺序选择 select2 算法的改进思路。9. 简述快速排序的基本思想。10. 快速排序算法的最坏时间复杂性和平均时间复杂性函数。11. 快速排序算法怎样抽取分割元素 ?12. partition怎样将数

2、组划分成3 段 ?13. 分治合并排序的是怎样分治的 ?14. 分治合并排序的二分归并过程在最坏情况下花费多少时间?15. 分治合并排序的二分归并过程在最好情况下花费多少时间?16. MaxMin算法是怎样分治的 ?17. 贪心法的基本思路是什么 ?18. 用贪心法求解的问题有什么特点 ?资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。19. 背包 的目 函数是什么 , 最 量度是什么 ?20. 限期的作 度的 心策略是什么? 束条件是什么 ?21. 明 n 皇后 的解 ( x 1,x 2, .,x n) 的含 。22. 述 n 皇后算法的 place 函数的功能。23. 述 划

3、方法所运用最 化原理。24. 用多段 明最 化原理。二解 下列 划 解的一般 形式。1）0/1 背包2） 郎担 3）流水作 度三算法分析。1 分析 塔算法的 复 性。2 算冒泡排序算法 复 性的 。3 分析 maxmin 算法的 复 性。4 分析分治合并排序算法的 复 性。5 分析二分 索的 复 性。6 背包 心算法的 复 性。7 快速排序的 partition 程中 , 行了多少次元素之 的比 。8 多段 算法的 复 性。资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。四 算法段填空。1 MaxMin 算法Maxmin(i,j,max,min)ifthen对两元素进行比较;re

4、turn;elsemaxmin(i,m,max1,min1); /其中 max1和 min1 为解子问题1 的解2 Hanoi 算法Hanoi(n,a,b,c)If n=1 thenElse资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。;Hanoi(n-1,b, a, c);3 二分检索BINSRCH(A,n,x,j)low 1;high n;while lowhigh do _ mid (low+high)/2; case: x=Amid : j mid; return;: x Amid: _low mid+1;endcasej 0; end4 快速排序Quicksort(p

5、,q)if pq then_call partition(p,j);资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。call _call _end5 贪心方法的抽象化控制procedure GREEDY(A, n)/A(1: n)包含 n 个输入 /solutions;for i1 todox SELECT(A)if FEASIBLE(solution, x)then solutions;endifreturn(solution)end GREEDY6 背包问题贪心算法procedure GREEDY-KNAPSACK(P, W, M, X, n)X 0 ; cu M ;for

6、i1 to n do资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。 ifthen exit endifX(i) _;cu;if in then X(i);endifend GREEDY-KNAPSACK7 分治合并排序算法procedure MERGESORT(low,high)if low high thenmid_MERGE(low,mid,high)endifend MERGESORT8 多段图动态规划算法procedureFGRAPH(E, k, n, P)1realCOST(n), integerD(n一1), P(k), r, j, k, n资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。2;3forto 1by 1do4设 r 是一个这样的结点, (j, r) E且使 c(j, r)+COST(r)取最小值5COST(j);6;7repeat8P(1) 1; P(k)n;9fordo10 P(j) D ( P(j-1) )11 repeat12 end FGRAPH9n 后问题递归