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

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

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

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

3、，high)；MERGE(low，mid，high)；endifendMERGESORT2、procedureS1(P，W，M，X，n)i←1;a←0whilei≤ndoifW(i)>Mthenreturnendifa←a+ii←i+1;repeatend3.procedurePARTITION(m,p)Integerm,p,i;globalA(m:p-1)v←A(m);i←mlooploopi←i+1untilA(i)≥vrepeatloopp←p-1untilA(p)≤vrepeatifi

4、eatA(m)←A(p);A(p)←vEndPARTITION4.procedureF1(n)ifn<2thenreturn(1)elsereturn(F2(2,n,1,1))endifendF1procedureF2(i,n,x,y)ifi≤nthencallF2(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,hig

5、h,mid,j,n;low←1;high←nwhilelow≤highdomid←

6、_(low+high)/2_

7、case:xA(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，

8、C(7,8)=62、写出maxmin算法对下列实例中找最大数和最小数的过程。数组A=(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、对于下图，写出图着色算法得出一种着色方案的过程。23141、写出第7

9、题的状态空间树。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的一棵最小生成树。124356dis