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

《中南大学现代远程教育课程考试复习试题及参考答案.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、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)ifthen对两元素

4、进行比较;return;else{maxmin(i,m,max1,min1);//其中max1和min1为解子问题1的解}2．Hanoi算法Hanoi(n,a,b,c)Ifn=1thenElse{资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。;Hanoi(n-1,b,a,c);}3．二分检索BINSRCH(A,n,x,j)low←1;high←n;whilelow

5、:_________________high←mid-1;:x>A[mid]:_________________low←mid+1;endcase}j←0;end4．快速排序Quicksort(p,q)ifp>qthen_____________{callpartition(p,j);资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。call_______________________call_______________________}end5．贪心方法的抽象化控制procedureGREEDY(A,n)//A(

6、1:n)包含n个输入//solutions←;fori←1todo{x←SELECT(A)ifFEASIBLE(solution,x)thensolutions←;endif}return(solution)endGREEDY6．背包问题贪心算法procedureGREEDY-KNAPSACK(P,W,M,X,n)X←0;cu←M;fori←1tondo资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。{ifthenexitendifX(i)←_;cu←;}ifi≤nthenX(i)←;endifend

7、GREEDY-KNAPSACK7．分治合并排序算法procedureMERGESORT(low,high)iflow

8、者删除。2;3forto1by－1do4设r是一个这样的结点,(j,r)E且使c(j,r)+COST(r)取最小值5COST(j)←;6;7repeat8P(1)←1;P(k)←n;9fordo10P(j)←D(P(j-1))11repeat12e