《算法分析与设计》期末试题及参考答案

《算法分析与设计》期末试题及参考答案一、简要回答下列问题：1.算法重要特性是什么？1.确定性、可行性、输入、输出、有穷性2.2.算法分析的目的是什么？2.分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。3.3.算法的时间复杂性与问题的什么因素相关？3.算法的时间复杂性与问题的规模相关，是问题大小n的函数。4.算法的渐进时间复杂性的含义？4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？5.最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n)=max{T(n，I)},I∈Dn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n)=∑P(I)T(n，I)I∈Dn6.简述二分检索（折半查找）算法的基本过程。6.设输入是一个按非降次序排列的元素表A[i：j]和x，选取A[(i+j)/2]与x比较，如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]x，则A[i：(i+j)/2-1]找x，否则在A[(i+j)/2+1：j]找x。上述过程被反复递归调用。7.背包问题的目标函数和贪心算法最优化量度相同吗？7.不相同。目标函数：获得最大利润。最优量度：最大利润/重量比。8.采用回溯法求解的问题，其解如何表示？有什么规定？8.问题的解可以表示为n元组：（x1,x2,……xn），xi∈Si,Si为有穷集合，xi∈Si,（x1,x2,……xn）具备完备性，即（x1,x2,……xn）是合理的，则（x1,x2,……xi）(in)一定合理。9.回溯法的搜索特点是什么？9.在解空间树上跳跃式地深度优先搜索，即用判定函数考察x[k]的取值，如果x[k]是合理的就搜索x[k]为根节点的子树，如果x[k]取完了所有的值，便回溯到x[k-1]。10.n皇后问题回溯算法的判别函数place的基本流程是什么？10.将第K行的皇后分别与前k-1行的皇后比较，看是否与它们相容，如果不相容就返回false，测试完毕则返回true。11.为什么用分治法设计的算法一般有递归调用？11.子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。12.为什么要分析最坏情况下的算法时间复杂性？、12最坏情况下的时间复杂性决定算法的优劣，并且最坏情况下的时间复杂性较平均时间复杂性游可操作性。13.简述渐进时间复杂性上界的定义。13.T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数No和C，n〉No，有T(n)f(n)，这种关系记作T(n)=O(f(n))。14.二分检索算法最多的比较次数？14.二分检索算法的最多的比较次数为logn。15.快速排序算法最坏情况下需要多少次比较运算？15．.最坏情况下快速排序退化成冒泡排序，需要比较n2次。16.贪心算法的基本思想？16.是一种依据最优化量度依次选择输入的分级处理方法。基本思路是：首先根据题意，选取一种量度标准；然后按这种量度标准对这n个输入排序，依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。17.回溯法的解（x1,x2,……xn）的隐约束一般指什么？17．回溯法的解（x1,x2,……xn）的隐约束一般指个元素之间应满足的某种关系。18.阐述归并排序的分治思路。18.讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。19.快速排序的基本思想是什么。19.快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一次快速排序。之后重复上述过程，直到每一部分内只有一个记录为止。20.什么是直接递归和间接递归？消除递归一般要用到什么数据结构？20.在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。21.什么是哈密顿环问题？21.哈密顿环是指一条沿着图G的N条边环行的路径，它的访问每个节点一次并且返回它的开始位置。22.用回溯法求解哈密顿环，如何定义判定函数？22.当前选择的节点X[k]是从未到过的节点,即X[k]≠X[i](i=1,2,…,k-1)，且C(X[k-1],X[k])≠∞，如果k=-1，则C(X[k],X[1])≠∞。23.请写出prim算法的基本思想。23.思路是：最初生成树T为空，依次向内加入与树有最小邻接边的n-1条边。处理过程：首先加入最小代价的一条边到T，根据各节点到T的邻接边排序，选择最小边加入，新边加入后，修改由于新边所改变的邻接边排序，再选择下一条边加入，直至加入n-1条边。二、复杂性分析1、MERGESORT(low，high)iflowhigh；thenmid←(low，high)/2；MERGESORT(low，mid)；MERGESORT(mid+1，high)；MERGE(low，mid，high)；endifendMERGESORT答2、procedureS1(P，W，M，X，n)i←1;a←0whilei≤ndoifW(i)Mthenreturnendifa←a+ii←i+1;repeatend解：3.procedurePARTITION(m,p)Integerm,p,i;globalA(m:p-1)v←A(m);i←mlooploopi←i+1untilA(i)≥vrepeatloopp←p-1untilA(p)≤vrepeatifipthencallINTERCHANGE(A(i),A(p))elseexitendifrepeatA(m)←A(p);A(p)←vEndPARTITION3解：、最多的查找次数是p-m+1次4.procedureF1(n)ifn2thenreturn(1)elsereturn(F2(2,n,1,1))endifendF1procedureF2(i,n,x,y)ifi≤nthencallF2(i+1,n,y,x+y)endifreturn(y)endF24、解：F2（2，n,1,1）的时间复杂度为：T(n)=O(n-2);因为i≤n时要递归调用F2，一共是n-2次当n＝1时F1(n)的时间为O(1)当n1时F1(n)的时间复杂度与F2(2,n,1,1)的时间复杂度相同即为为O(n)5.procedureMAX(A,n,j)xmax←A(1);j←1fori←2tondoifA(i)xmaxthenxmax←A(i);j←i;endifrepeatendMAX答案5、xmax←A(1);j←1时间为：O(1)fori←2tondo循环最多n-1次所以总时间为:T(n)=O(1)+(n-1)O(1)=O(n)6.procedureBINSRCH(A,n,x,j)integerlow,high,mid,j,n;low←1;high←nwhilelow≤highdomid←|_(low+high)/2_|case:xA(mid):high←mid-1:xA(mid):low←mid+1:else:j←mid;returnendcaserepeatj←0endBINSRCH答案6、log2n+1三、算法理解1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。各边的代价如下：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)=6答案：513426781、Cost(4,8)=0Cost(3,7)=C(7,8)+0=6，D[5]=8Cost(3,6)=C(6，8)+0=5,D[6]=8Cost(3,5)=C(5，8)+0=4D[7]=8Cost(2,4)=min{C(4，6)+Cost(3,6),C(4，5)+Cost(3,5)}=min{1+5,2+4}=6D[4]=6Cost(2,3)=min{C(3，6)+Cost(3,6)}=min{4+5}=9D[3]=5Cost(2,2)=min{C(2，6)+Cost(3,6),C(2，7)+Cost(3,7)}=min{8+5,4+6}=10D[2]=7Cost(1,1)=min{C(1,2)+Cost(2,2),C(1,3)+Cost(2,3),C(1,4)+Cost(2,4)}=min{3+10,5+9,2+6}=8D[1]=41→4→6→82、写出maxmin算法对下列实例中找最大数和最小数的过程。数组A=(48,12,61,3,5,19,32,7)答案2、写出maxmin算法对下列实例中找最大数和最小数的过程。数组A=()1、48,12,61,3,5,19,32,72、48,1261,35,1932,73、48～61,12～319～32，5～74、61～323～55、6133、给出5个数(3,6,9,1,7),M=13，用递归树描述sumofsub算法求和数=M的一个子集的过程。4、快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。A=(65,70,75,80,85,55,50,2)5、归并排序算法对下列实例排序，写出算法执行过程。A=(48,12,61,3,5,19,32,7)5、48,12,61,35,19,32,748,1261,35,1932,712,483,615,197,323,12,48,615,7,19，323,5,7,12，19，32，48,616、写出图着色问题的回溯算法的判断X[k]是否合理的过程。6、i←0whileikdoifG[k,i]=1andX[k]=X[i]thenreturnfalsei←i+1repeatifi=kthenreturntrue7、对于下图，写出图着色算法得出一种着色方案的过程。13427、K←1X[1]←1,返回trueX[2]←1,返回false;X[2]←X[2]+1=2,返回trueX[3]←1,返回false;X[3]←X[3]+1=2,返回false;X[3]←X[3]+1=3,返回trueX[4]←1,返回false;X[4]←X[4]+1=2,返回false;X[4]←X[4]+1=3,返回true找到一个解（1，2，3，3）8、写出第7题的状态空间树。9、写出归并排序算法对下列实例排序的过程。(6,2,9,3,5,1,8,7)9、调用第一层次6,2,9,35,1,8,7分成两个子问题调用第二层次6,29,35,18,7分成四个子问题调用第三层次62935187分成八个子问题调用第四层次只有一个元素返回上一层第三层归并2,63,91,57,8返回上一层第二层归并2,3,6,91,5,7,8返回上一层第一层归并1,2,3,5,6,7,8,9排序结束，返回主函数10、写出用背包问题贪心算法解决下列实例的过程。P=(18,12,4,1)W=(12,10,8,3)M=2510、实例符合P(i)/W(i)≥P(i+1)/W(i+1)的顺序。CU←25,X←0W[1]CU:x[1]←1;CU←CU-W[1]=13;W[2]CU:x[2]←1;CU←CU-W[2]=3;W[3]CU:x[3]←CU/W[3]=3/8;实例的解为：（1，1，3/8，0）11、有一个有序表为{1，3，9，12，32，41，