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

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

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过程中，进行了多少次元素之间的比较。1．多段图算法的时间复杂性。四算法段填空。1．MaxMin算法Maxmin(i,j,max,min)ifthen对两元素进行比较;return;else{maxmin(i,m,max1,min1);//其中max1和min1为解子问题1的解}2．Hanoi算法Hanoi(n

4、,a,b,c)Ifn=1thenElse{;Hanoi(n-1,b,a,c);}3．二分检索BINSRCH(A,n,x,j)low←1;high←n;whilelowA[mid]：_________________low←mid+1;endcase}j←0;end1．快速排序Quicksort(p,q)ifp>qthen_____________{c

5、allpartition(p,j);call_______________________call_______________________}end2．贪心方法的抽象化控制procedureGREEDY(A，n)//A(1：n)包含n个输入//solutions←；fori←1todo{x←SELECT(A)ifFEASIBLE(solution，x)thensolutions←；endif}return(solution)endGREEDY3．背包问题贪心算法procedureGREEDY-KNAPSACK(P，W，M，X，n)X←0；cu←M；fori←1

6、tondo{ifthenexitendifX(i)←_；cu←；}ifi≤nthenX(i)←；endifendGREEDY-KNAPSACK4．分治合并排序算法procedureMERGESORT(low,high)iflow

7、r，j，k，n2；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))11repeat12endFGRAPH2．n后问题递归算法procedureRNQUEENS(K)globalx(1:m),n;forx(k)←1to_____doifplace(k)=truethenifk=nthen________else_____________endifendifrepeatendENQUEENS五.设计算法

8、1．写递归