算法11年期末考试卷答案

北京航空航天大学20

班号学号姓名成绩《算法设计与分析》期末考试卷注意事项：1、关闭手机、将考试用文具以外的物品放于讲台上2、严格遵守学校的考场纪律，违纪者请出考场题目：判断题（21分，每小题3分）请在正确的陈述前面括号中打√，在错误的陈述前面括号中打×。1. （ √）基于比较的寻找数组A[1...n]中最大值元素和最小值元素问题的下界是n/2。2. （ √）合并排序使用了分治策略。3．（×）快速排序算法的平均时间复杂度是O(nlogn),使用随机化快速排序算法可以将平均时间复杂度降得更低。4．（ ×）如果一个问题是NP问题，则它一定不是P问题。5．（ √）且6．（ ×）下列问题是一个判定问题：给定一个合取范式，对中的所有逻辑变量求一组真值赋值，使得在该组真值赋值下为真。7．（ ×）NP完备（NP-Complete）问题是所有NP问题中最难的，目前还没有找到用于解决NP完备问题的多项式算法。简答题（28分，每小题7分）：请给出基于比较的对数组A[1…n]进行排序问题的最紧的下界，并写出两个平均时间复杂度为该下界的排序算法的名称。nlogn；快速排序、随机化的快速排序。按照增长率上升的顺序排列以下函数，即，若在你的排序结果中，函数f(n)跟在g(n)的后面，则说明应该满足g(n)是O（f(n)）： ,,,,,推导以下递推式的解：T(n)=2 当n=1时T(n)=4T(n/2)+2n 当n≥2时T(n)=4T(n/2)+2n =4(4T(n/4)+2n/2)+2n =…=4lognT(1)+2n(1+2+4+…+n/2) 或设n=2^k,4kT(1)+2n(1+2+4+…+2k-1)=2n2+2n(2logn-1) =4n2-2n(n-1)=2n2+2n=O(n2) 简述拉斯维加斯（LasVegas）算法和蒙特卡洛（MonteCarlo）算法的主要区别前者不一定总能给出解，但给出的解一定是正确的；后者总能给出解，但是给出的解可能是错误的。（20分）写出用动态规划方法求矩阵链乘积问题p(l,h)=Al+1×Al+2×…×Ah的递推公式、伪代码和时间复杂性，并用该算法手工计算得出下列矩阵链乘积的最优策略和该策略对应的最小开销（按照递推公式给出详细步骤）：d=A3,4×A4,6×A6,1×A1,5,注：这里Ax,y表示一个x×y阶矩阵m[l,h]＝0ifl+1=h＝minl<i<h(m[l,i]+m[i,h]+dldidh)ifl+1<hMatrixChain(d,n)for(l=n-1;l>0;l){//iterate(迭代)overrows(行)for(h=l+1;hn;h++){//iterateoverthecolums(列)if(hl=1)bestcost=0;elsebestcost=;for(i=l+1;i<h;i++){//considerl<i<ha=m[l,i];//look-upsolutionb=m[i,h];//look-upsolutionc=d[l]d[i]d[h];//costoflastmultiplicationatpositionibestcost=min(bestcost,a+b+c);}m[l,h]=bestcost;}//storeobtainedresult}returnm[0,n];Complexityanalysis:O(nnn)=O(n3).0min{3×4×6,}=72min{72+3×6×1,24+3×4×1}=36min{36+3×1×5,44+3×4×5}=510min{4×6×1,}=24min{24+4×1×5,30+4×6×5}=440min{6×1×5,}=300最优策略是（A3,4×（A4,6×A6,1））×A1,5（16分）用回溯法求解以下SAT问题，请画出搜索树，标明搜索树的分支策略和树中各节点代表的状态（化简的CNF形式）。(pÚqÚs)Ù(ØqÚr)Ù(ØpÚr)Ù(ØrÚs)(pÚqÚs)Ù(ØqÚr)Ù(ØpÚr)Ù(ØrÚs)p:1/\0(ØqÚr)ÙrÙ(ØrÚs)(qÚs)Ù(ØqÚr)Ù(ØrÚs)q:1/\01/ \0rÙrÙ(ØrÚs)rÙ(ØrÚs)rÙ(ØrÚs)sÙ(ØrÚs)r:1/\01/\01/\01/\0 s0s0s0sss:1/\01/\01/\01/\01/\01010101010P=1,q=1,r=1,s=1.（15分）设计一