算法分析与设计考试复习题及参考答案

《算法分析与设计考试复习题及参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、中南大学现代远程教育课程考试复习题及参考答案算法分析与设计一、简要回答下列问题：1.算法重要特性是什么？2.算法分析的目的是什么？3.算法的时间复杂性与问题的什么因素相关？4.算法的渐进时间复杂性的含义？5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？6.简述二分检索（折半查找）算法的基本过程。7.背包问题的目标函数和贪心算法最优化量度相同吗？8.采用回溯法求解的问题，其解如何表示？有什么规定？9.回溯法的搜索特点是什么？10.n皇后问题回溯算法的判别函数place的基本流程是什么？11.为什么用分治法

2、设计的算法一般有递归调用？12.为什么要分析最坏情况下的算法时间复杂性？13.简述渐进时间复杂性上界的定义。14.二分检索算法最多的比较次数？15.快速排序算法最坏情况下需要多少次比较运算？16.贪心算法的基本思想？17.回溯法的解（x1,x2,……xn）的隐约束一般指什么？18.阐述归并排序的分治思路。19.快速排序的基本思想是什么。20.什么是直接递归和间接递归？消除递归一般要用到什么数据结构？21.什么是哈密顿环问题？22.用回溯法求解哈密顿环，如何定义判定函数？23.请写出prim算法的基本思想。二、

3、复杂性分析1、MERGESORT(low，high)iflowMthenreturnendifa←a+i13i←i+1;repeatend3.procedurePARTITION(m,p)Integerm,p

4、,i;globalA(m:p-1)v←A(m);i←mlooploopi←i+1untilA(i)≥vrepeatloopp←p-1untilA(p)≤vrepeatifi

5、thencallF2(i+1,n,y,x+y)endifreturn(y)endF25.procedureMAX(A,n,j)xmax←A(1);j←1fori←2tondoifA(i)>xmaxthenxmax←A(i);j←i;endifrepeatendMAX6.procedureBINSRCH(A,n,x,j)integerlow,high,mid,j,n;low←1;high←nwhilelow≤highdomid←

6、_(low+high)/2_

7、case:x

8、:x>A(mid):low←mid+1:else:j←mid;returnendcaserepeatj←0endBINSRCH三、算法理解1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。52863174各边的代价如下：C(1,2)=3，C(1,3)=5，C(1,4)=2C(2,6)=8，C(2,7)=4，C(3,5)=5，C(3,6)=4，C(4,5)=2，C(4,6)=1C(5,8)=4，C(6,8)=5，C(7,8)=62、写出maxmin算法对下列实例中找最大数和最小数的过程。数组A

9、=(48,12,61,3,5,19,32,7)1、给出5个数(3,6,9,1,7),M=13，用递归树描述sumofsub算法求和数=M的一个子集的过程。2、快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。A=(65,70,75,80,85,55,50,2)3、归并排序算法对下列实例排序，写出算法执行过程。A=(48,12,61,3,5,19,32,7)4、写出图着色问题的回溯算法的判断X[k]是否合理的过程。5、对于下图，写出图着色算法得出一种着色方案的过程。2314131、写出第

10、7题的状态空间树。2、写出归并排序算法对下列实例排序的过程。(6,2,9,3,5,1,8,7)3、写出用背包问题贪心算法解决下列实例的过程。P=(18,12,4,1)W=(12,10,8,3)M=2511、有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当使用二分查找值为82的结点时，经过多少次比较后查找成功并给出过程。12、使用prim算法构造出如下图G