(完整版)算法設計與分析期末考試卷及答案a

1、一填空題(每空2分，共30分)1算法的時間復雜性指算法中的執(zhí)行次數(shù)。2. 在忽略常數(shù)因子的情況下，0、Q和©三個符號中，提供了算法運行時間的一個上界。3設Dn表示大小為n的輸入集合，t(I)表示輸入為I時算法的運算時間，p(I)表示輸入I出現(xiàn)的概率，則算法的平均情況下時間復雜性A(n)=。4. 分治算法的時間復雜性常常滿足如下形式的遞歸方程：Jf(n)=d,n=n|f(n)=af(n/c)+g(n),n>ni0其中，g(n)表示。5. 分治算法的基本步驟包括。6. 回溯算法的基本思想是。7. 動態(tài)規(guī)劃和分治法在分解子問題方面的不同點是。8貪心算法中每次做出的貪心選擇都是最優(yōu)選擇

2、。9PQ式的分支限界法中，對于活結(jié)點表中的結(jié)點，其下界函數(shù)值越小，優(yōu)先級越。10選擇排序、插入排序和歸并排序算法中，算法是分治算法。11隨機算法的一個基本特征是對于同一組輸入，不同的運行可能得到的結(jié)果。12對于下面的確定性快速排序算法，只要在步驟3前加入隨機化步驟，就可得到一個隨機化快速排序算法，該隨機化步驟的功能是。算法QUICKSORT輸入：n個元素的數(shù)組A1.n。輸出：按非降序排列的數(shù)組A中的元素。!號i學i一iI欄一I名丨'姓！iiI息II級丨I年丨線i信I1. quicksort(l,n)endQUICKSORT過程quicksort(A,low,high)/對Alow.hi

3、gh沖的元素按非降序排序。2. iflow<highthen3. w=SPLIT(A,low,high)算法SPLIT以Alow為主元將Alow.high劃分成兩部分，返回主元的新位置。4. quicksort(A,low,w-1)5. quicksort(A,w+1,high)6. endifendquicksort13.下面算法的基本運算是運算，該算法的時間復雜性階為o()。算法SPLIT輸入：正整數(shù)n,數(shù)組Al.n。輸出：。i=1x=A1forj=2tonifAj<=xtheni=i+1ifi豐jthenAi分AjendifendforAi今A1w=ireturnw,Aend

4、SPLIT二計算題和簡答題(每小題7分，共21分)1.用0、Q、0表示函數(shù)f與g之間階的關系，并分別指出下列函數(shù)中階最低和最高的函數(shù)：(1)f(n)=100g(n)=1001f(n)=6n+nbogng(n)=3nf(n)=n/logn-1g(n)=2lnf(n)=2n+n2g(n)=3n(5)f(n)=log3ng(n)=logn22.下面是一個遞歸算法，其中，過程prol和pro2的運算時間分別是1和logn。給2出該算法的時間復雜性T(n)滿足的遞歸方程，并求解該遞歸方程，估計T(n)的階(用0表示)。算法EX1輸入：正整數(shù)n，n=2k。輸出：ex1(n)endEX1過程ex1(n)if

5、n=1thenpro1(n)elsei_i二i1r111111111111I1|I1|1!i學|I|1:!:i欄'I1!|:：:|i_i名1名11!1!|1|i姓1息|1:級i年11線1i信1!信!1業(yè)!生專!i!訂i11i考系:!“iii_i11|裝iI1:11i>1院:!i1!1!:；:；1學111i:i111111pro2(n)exl(n/2)endifreturnendex13.用Floyd算法求下圖每一對頂點之間的最短路徑長度，計算矩陣D0,D,D2和D3，其中Dki,j表示從頂點i到頂點j的不經(jīng)過編號大于k的頂點的最短路徑長度。三算法填空題（共34分）1.（10分）設

6、n個不同的整數(shù)按升序存于數(shù)組A1.n中，求使得Ai=i的下標i。下面是求解該問題的分治算法。算法SEARCH輸入：正整數(shù)n，存儲n個按升序排列的不同整數(shù)的數(shù)組A1.n。輸出：A1.n中使得Ai=i的一個下標i,若不存在，則輸出nosolution。i=find(Qifi>0thenoutputielseoutput“nosolution”endSEARCH過程find（low,high）/求Alow.high中使得Ai=i的一個下標并返回，若不存在,thenreturn0則返回0。ifelsemid=L(1ow+high)/2if(3)thenreturnmidelseifAmid<

7、;midthenreturnfind)elsereturn(5)endifendifendifendfind2.（10分）下面是求解矩陣鏈乘問題的動態(tài)規(guī)劃算法。矩陣鏈乘問題：給出n個矩陣M,M2,Mn,叫為rixri+階矩陣,i=l,2,n,求計算MM2Mn所需的最少數(shù)量乘法次數(shù)。記叫j=MiMi+Mj,i<=j。設Ci,j,1<=i<=j<=n,表示計算叫j的所需的最少數(shù)量乘法次數(shù)，則Ci,j二（,i二j'minCi,k-1+Ck,j+rrr,i<jl心jikj+1算法MATCHAIN輸入：矩陣鏈長度n,n個矩陣的階rl.n+l,其中r1.n為n個矩陣的

8、行數(shù)，rn+l為第n個矩陣的列數(shù)。輸出：n個矩陣鏈乘所需的數(shù)量乘法的最少次數(shù)。i號iI學Ii欄ijj級I年I線信二II生業(yè)I訂考系!裝IIfori=1tonCi,i=(1)ford=1ton-1Ifori=1ton-d|j=|Ci,j=sfork=i+ltoj|x=(3)|ifx<Ci,jthen|(4)=xendifiendforIendfor|endfor:return(5)iendMATCHAIN|3.(14分)下面是用回溯法求解馬的周游問題的算法。|馬的周游問題：給出一個nxn棋盤，已知一個中國象棋馬在|棋盤上的某個起點位置(xO,yO)，求一條訪問每個棋盤格點恰好|一次，最后回

9、到起點的周游路線。(設馬走日字。)|算法HORSETRAVEL輸入：正整數(shù)n，馬的起點位置(x0,y0)，1<=x0,y0<=n。|輸出：一條從起點始訪問nxn棋盤每個格點恰好一次，最后回到起點的周游路線；若問題無解，則輸出nosolution。tag1.n,1.n=0|dx1.8=2,l,-l,-2,-2,-l,1,2|dy1.8=1,2,2,1,-1,-2,-2,-1Iflag=falsex=xO;y=yO;tagx,y=1m=n*ni=1;ki=Owhile(1)andnotflagwhileki<8andnotflagki=(2)x1=x+dxki;y1=y+dyki

10、if(x1,y1)無越界andtagx1,y1=0)or(x1,y1)=(x0,y0)andi=m)thenx=x1;y=y1tagx,y=(3)ifi=mthenflag=trueelsei=endifendifendwhilei=i-1endwhileifflagthenoutputroute(k)/輸出路徑elseoutput“nosolution”endHORSETRAVEL號ii學III>>I欄一1IIII>>i一ii名iI姓I:白:息！1級1!年|i一iii信一：信!I業(yè)Ii專II生|IIIIII系II"I考一1考一！ii； I i院II學I|四算

11、法設計題（15分）i1.一個旅行者要駕車從A地到B地，A、B兩地間距離為s。A、B兩地之間有n個加油站，已知第i個加油站離起點A的距離為d.公里,ii0=d<d<<d<s，車加滿油后可行駛m公里，出發(fā)之前汽車:12n|油箱為空。應如何加油使得從A地到B地沿途加油次數(shù)最少？給出|用貪心法求解該最優(yōu)化問題的貪心選擇策略，寫出求該最優(yōu)化問題|的最優(yōu)值和最優(yōu)解的貪心算法，并分析算法的時間復雜性。一.填空題1.元運算算法設計與分析期考試卷標準答案2.O3. 工p(I)t(I)1嗎4. 將規(guī)模為n的問題分解為子問題以及組合相應的子問題的解所需的時間5. 分解，遞歸，組合6. 在問題

12、的狀態(tài)空間樹上作帶剪枝的DFS搜索(或：DFS+剪枝)7. 前者分解出的子問題有重疊的，而后者分解出的子問題是相互獨立(不重疊)的8. 局部9. 高10. 歸并排序算法11. 不同12. v=random(low,high);交換Alow和Av的值隨機選主元13. 比較n二.計算題和簡答題1. 階的關系：(1) f(n)=O(g(n)(2) f(n)=°(g(n)(3) f(n)=°(g(n)(4) f(n)=O(g(n)(5) f(n)=®(g(n)階最低的函數(shù)是：100階最高的函數(shù)是：3n2. 該遞歸算法的時間復雜性T(n)滿足下列遞歸方程:T(n)=1,n=

13、1T(n)=T(n/2)+log2n,n>1將n=2k,a=1,c=2,g(n)=log2n,d=1代入該類遞歸方程解的一般形式得T(n)=1+乞log?2=1+klon-乞ii=0i=0k(k-1)1.K=1+klogn-=log2n+_logn+1222222所以，T(n)=)log2n+logn+1=冋(log2n)。2222-0g2-0g20g2_D=306D=305D=305010501105028503.72D3=0550三.算法填空題：1.(1)1,n(2)low>high(3)Amid=mid(4)mid+1,high(5)find(low,mid-1)2.(1)0

14、(2)i+d(3)Ci,k-1+Ck,j+ri*rk*rj+1(4)Ci,j(5)C1,n3.(1)i>=1(2)ki+1(3)1(4)i+1(5)ki=0(6)tagx,y=0(7)x=x-dxki;y=y-dyki四.算法設計題：1.貪心選擇策略：從起點的加油站起每次加滿油后不加油行駛盡可能遠，直至油箱中的油耗盡前所能到達的最遠的油站為止，在該油站再加滿油。算法MINSTOPS輸入：A、B兩地間的距離s,A、B兩地間的加油站數(shù)n車加滿油后可行駛的公里數(shù)m,存儲各加油站離起點A的距離的數(shù)組d1.no輸出：從A地到B地的最少加油次數(shù)k以及最優(yōu)解xl.k(xi表示第i次加油的加油站序號),若問題無解,則輸出nosolutionodn+l=s;設置虛擬加油站第n+1站。fori=ltonifdi+1-di>mthenou