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

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

2、。9PQ式的分支限界法中，對(duì)于活結(jié)點(diǎn)表中的結(jié)點(diǎn)，其下界函數(shù)值越小，優(yōu)先級(jí)越。10選擇排序、插入排序和歸并排序算法中，算法是分治算法。11隨機(jī)算法的一個(gè)基本特征是對(duì)于同一組輸入，不同的運(yùn)行可能得到的結(jié)果。12對(duì)于下面的確定性快速排序算法，只要在步驟3前加入隨機(jī)化步驟，就可得到一個(gè)隨機(jī)化快速排序算法，該隨機(jī)化步驟的功能是。算法QUICKSORT輸入：n個(gè)元素的數(shù)組A1.n。輸出：按非降序排列的數(shù)組A中的元素。!號(hào)i學(xué)i一iI欄一I名丨'姓！iiI息II級(jí)丨I年丨線i信I1. quicksort(l,n)endQUICKSORT過(guò)程quicksort(A,low,high)/對(duì)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.下面算法的基本運(yùn)算是運(yùn)算，該算法的時(shí)間復(fù)雜性階為o()。算法SPLIT輸入：正整數(shù)n,數(shù)組Al.n。輸出：。i=1x=A1forj=2tonifAj<=xtheni=i+1ifi豐jthenAi分AjendifendforAi今A1w=ireturnw,Aend

4、SPLIT二計(jì)算題和簡(jiǎn)答題(每小題7分，共21分)1.用0、Q、0表示函數(shù)f與g之間階的關(guān)系，并分別指出下列函數(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.下面是一個(gè)遞歸算法，其中，過(guò)程prol和pro2的運(yùn)算時(shí)間分別是1和logn。給2出該算法的時(shí)間復(fù)雜性T(n)滿足的遞歸方程，并求解該遞歸方程，估計(jì)T(n)的階(用0表示)。算法EX1輸入：正整數(shù)n，n=2k。輸出：ex1(n)endEX1過(guò)程ex1(n)if

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

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

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

8、行數(shù)，rn+l為第n個(gè)矩陣的列數(shù)。輸出：n個(gè)矩陣鏈乘所需的數(shù)量乘法的最少次數(shù)。i號(hào)iI學(xué)Ii欄ijj級(jí)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分)下面是用回溯法求解馬的周游問(wèn)題的算法。|馬的周游問(wèn)題：給出一個(gè)nxn棋盤，已知一個(gè)中國(guó)象棋馬在|棋盤上的某個(gè)起點(diǎn)位置(xO,yO)，求一條訪問(wèn)每個(gè)棋盤格點(diǎn)恰好|一次，最后回

9、到起點(diǎn)的周游路線。(設(shè)馬走日字。)|算法HORSETRAVEL輸入：正整數(shù)n，馬的起點(diǎn)位置(x0,y0)，1<=x0,y0<=n。|輸出：一條從起點(diǎn)始訪問(wèn)nxn棋盤每個(gè)格點(diǎn)恰好一次，最后回到起點(diǎn)的周游路線；若問(wèn)題無(wú)解，則輸出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)無(wú)越界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號(hào)ii學(xué)III>>I欄一1IIII>>i一ii名iI姓I:白:息！1級(jí)1!年|i一iii信一：信!I業(yè)Ii專II生|IIIIII系II"I考一1考一！ii； I i院II學(xué)I|四算

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

12、的狀態(tài)空間樹上作帶剪枝的DFS搜索(或：DFS+剪枝)7. 前者分解出的子問(wèn)題有重疊的，而后者分解出的子問(wèn)題是相互獨(dú)立(不重疊)的8. 局部9. 高10. 歸并排序算法11. 不同12. v=random(low,high);交換Alow和Av的值隨機(jī)選主元13. 比較n二.計(jì)算題和簡(jiǎn)答題1. 階的關(guān)系：(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. 該遞歸算法的時(shí)間復(fù)雜性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四.算法設(shè)計(jì)題：1.貪心選擇策略：從起點(diǎn)的加油站起每次加滿油后不加油行駛盡可能遠(yuǎn)，直至油箱中的油耗盡前所能到達(dá)的最遠(yuǎn)的油站為止，在該油站再加滿油。算法MINSTOPS輸入：A、B兩地間的距離s,A、B兩地間的加油站數(shù)n車加滿油后可行駛的公里數(shù)m,存儲(chǔ)各加油站離起點(diǎn)A的距離的數(shù)組d1.no輸出：從A地到B地的最少加油次數(shù)k以及最優(yōu)解xl.k(xi表示第i次加油的加油站序號(hào)),若問(wèn)題無(wú)解,則輸出nosolutionodn+l=s;設(shè)置虛擬加油站第n+1站。fori=ltonifdi+1-di>mthenou