算法11年期末考試卷答案

北京航空航天大學(xué)20

班號學(xué)號姓名成績《算法設(shè)計與分析》期末考試卷注意事項：1、關(guān)閉手機(jī)、將考試用文具以外的物品放于講臺上2、嚴(yán)格遵守學(xué)校的考場紀(jì)律，違紀(jì)者請出考場題目：判斷題（21分，每小題3分）請在正確的陳述前面括號中打√，在錯誤的陳述前面括號中打×。1. （ √）基于比較的尋找數(shù)組A[1...n]中最大值元素和最小值元素問題的下界是n/2。2. （ √）合并排序使用了分治策略。3．（×）快速排序算法的平均時間復(fù)雜度是O(nlogn),使用隨機(jī)化快速排序算法可以將平均時間復(fù)雜度降得更低。4．（ ×）如果一個問題是NP問題，則它一定不是P問題。5．（ √）且6．（ ×）下列問題是一個判定問題：給定一個合取范式，對中的所有邏輯變量求一組真值賦值，使得在該組真值賦值下為真。7．（ ×）NP完備（NP-Complete）問題是所有NP問題中最難的，目前還沒有找到用于解決NP完備問題的多項式算法。簡答題（28分，每小題7分）：請給出基于比較的對數(shù)組A[1…n]進(jìn)行排序問題的最緊的下界，并寫出兩個平均時間復(fù)雜度為該下界的排序算法的名稱。nlogn；快速排序、隨機(jī)化的快速排序。按照增長率上升的順序排列以下函數(shù)，即，若在你的排序結(jié)果中，函數(shù)f(n)跟在g(n)的后面，則說明應(yīng)該滿足g(n)是O（f(n)）： ,,,,,推導(dǎo)以下遞推式的解：T(n)=2 當(dāng)n=1時T(n)=4T(n/2)+2n 當(dāng)n≥2時T(n)=4T(n/2)+2n =4(4T(n/4)+2n/2)+2n =…=4lognT(1)+2n(1+2+4+…+n/2) 或設(shè)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）算法的主要區(qū)別前者不一定總能給出解，但給出的解一定是正確的；后者總能給出解，但是給出的解可能是錯誤的。（20分）寫出用動態(tài)規(guī)劃方法求矩陣鏈乘積問題p(l,h)=Al+1×Al+2×…×Ah的遞推公式、偽代碼和時間復(fù)雜性，并用該算法手工計算得出下列矩陣鏈乘積的最優(yōu)策略和該策略對應(yīng)的最小開銷（按照遞推公式給出詳細(xì)步驟）：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最優(yōu)策略是（A3,4×（A4,6×A6,1））×A1,5（16分）用回溯法求解以下SAT問題，請畫出搜索樹，標(biāo)明搜索樹的分支策略和樹中各節(jié)點代表的狀態(tài)（化簡的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分）設(shè)計一