算法設(shè)計(jì)試題

一、選擇題(15*2分)1.算法分析是（C）A.將算法用某種程序設(shè)計(jì)語(yǔ)言恰當(dāng)?shù)乇硎境鰜?lái)B.在抽象數(shù)據(jù)集合上執(zhí)行程序,以確定是否會(huì)產(chǎn)生錯(cuò)誤的結(jié)果C.對(duì)算法需要多少計(jì)算時(shí)間和存儲(chǔ)空間作定量分析D.證明算法對(duì)所有可能的合法輸入都能算出正確的答案2.算法與程序的區(qū)別在于算法具有（C）A.能行性B.確定性C.有窮性D.輸入和輸出3.記號(hào)的定義正確的是（B）A.O(g(n))={f(n)|存在正常數(shù)c和n0使得當(dāng)nn0有f(n)cg(n)}B.O(g(n))={f(n)|存在正常數(shù)c和n0使得當(dāng)nn0有cg(n)f(n)}C.(g(n))={f(n)|對(duì)于任何正常數(shù)c>0，存在正數(shù)和n0>0使得對(duì)所有nn0有f(n)<cg(n)}D.(g(n))={f(n)|對(duì)于任何正常數(shù)c>0，存在正數(shù)和n0>0使得對(duì)所有nn0有cg(n)<f(n)}衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（C）

A.運(yùn)行速度快B.占用空間少C.時(shí)間復(fù)雜度低D.代碼短5.二分搜索算法是利用（A）實(shí)現(xiàn)的算法。A.分治法B.動(dòng)態(tài)規(guī)劃法

C.貪心法

D.回溯法下面問(wèn)題（B）不能使用貪心法解決。

A.單源最短路徑問(wèn)題 B.N皇后問(wèn)題

C.最小代價(jià)生成樹(shù)問(wèn)題 D.背包問(wèn)題7．用貪心法設(shè)計(jì)算法的關(guān)鍵是（B）。A.將問(wèn)題分解為多個(gè)子問(wèn)題來(lái)分別處理B.選好最優(yōu)量度標(biāo)準(zhǔn)C.獲取各階段間的遞推關(guān)系式D.滿足最優(yōu)性原理8.找最小生成樹(shù)的算法Kruskal的時(shí)間復(fù)雜度為（D）（其中n為無(wú)向圖的結(jié)點(diǎn)數(shù)，m為邊數(shù)）O(n2)B．O(mlogn)C．O(nlogm)D．O(mlogm)9.回溯法搜索狀態(tài)空間樹(shù)是按照（C）的順序。

A.中序遍歷B.廣度優(yōu)先遍歷C.深度優(yōu)先遍歷D.層次優(yōu)先遍歷10.一個(gè)問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問(wèn)題的（B）A.重疊子問(wèn)題 B.最優(yōu)子結(jié)構(gòu)性質(zhì) C.最優(yōu)量度標(biāo)準(zhǔn)性質(zhì) D.定義最優(yōu)解11.程序塊（A）是回溯法中遍歷排列樹(shù)的算法框架程序。A.voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(legal(t))backtrack(t+1);swap(x[t],x[i]);}}B.Voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t+1);}}C.Voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t-1);}}D.Voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){Swap(x[t],x[i]);if(legal(t))backtrack(t+1);}}12.0-1背包問(wèn)題的回溯算法所需的計(jì)算時(shí)間為（

A）A.O（n2n） B.O（nlogn） C.O（2n） D.O（n）13．哈弗曼編碼的貪心算法所需的計(jì)算時(shí)間為（B）A.O（n2n） B.O（nlogn） C.O（2n）D.O（n）14.矩陣連乘問(wèn)題的算法可由（B）設(shè)計(jì)實(shí)現(xiàn)。A.分支界限算法

B.動(dòng)態(tài)規(guī)劃算法

C.貪心算法

D.回溯算法15.采用廣度優(yōu)先策略搜索的算法是（A）。A.分支界限法 B.動(dòng)態(tài)規(guī)劃法 C.貪心法 D.回溯法二、填空題（15*2分）1.算法的復(fù)雜性有______和______之分,衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是_____________。2.某一問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征是_________________________。3.若序列A={xzyzzyx}，B={zxyyzxz}，請(qǐng)給出序列A和B的一個(gè)最長(zhǎng)公共子序列__________________。4.動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問(wèn)題分解成若干___________先求解_________,然后從這些_____________的解得到原問(wèn)題的解。5.0-1背包問(wèn)題的回溯算法所需的計(jì)算時(shí)間為_(kāi)___________,用動(dòng)態(tài)規(guī)劃算法所需的計(jì)算時(shí)間為_(kāi)_______________。6.二分法搜索算法是利用___________實(shí)現(xiàn)的算法。7.所謂最優(yōu)化問(wèn)題是指問(wèn)題給定某些約束條件，滿足這些約束條件的問(wèn)題解稱為_(kāi)__________。8.回溯法解決問(wèn)題時(shí)，應(yīng)明確定義問(wèn)題的解空間，問(wèn)題的解空間至少應(yīng)包含________。9.__________是描述問(wèn)題解空間的樹(shù)形結(jié)構(gòu)。10.在分枝限界法中一個(gè)活結(jié)點(diǎn)只可能一次成為E結(jié)點(diǎn)，回溯法中任何一個(gè)或結(jié)點(diǎn)可能____成為E結(jié)點(diǎn)。答案：1.時(shí)間、空間時(shí)間復(fù)雜度空間復(fù)雜度。2.算法效率3.xyzz.4.子問(wèn)題子問(wèn)題子問(wèn)題5.o（n*2n）o(min{nc2n})6.動(dòng)態(tài)規(guī)劃法7.可行解8.2n9.狀態(tài)空間樹(shù)10.多次三、算法設(shè)計(jì)題（每題10分、共20分）1、設(shè)計(jì)一個(gè)回溯算法，使用可變長(zhǎng)度狀態(tài)空間樹(shù)求解子集和數(shù)問(wèn)題。解、子集和數(shù)的回溯算法：voidSumOfSub(floats,intk,floatr,int*x,floatm,float*w){x[k]=1;if(s+w[k]==m){for(intj=0;j<=k;j++)cout<<x[j]<<’’;cout<<endl;}elseif(s+w[k]+w[k+1]<=m)SumOfSub(s+w[k],k+1,r-w[k],x,m,w);if((s+r-w[k]>=m)&&(s+w[k+1]<=m)){x[k]=0;SumOfSub(s,k+1,r-w[k],x,m,w);}}voidSumSub(int*x,intn,floatm,float*w){floatr=0;for(inti=0;i<n;i++)r=r+w[i];if(r>=m&&w[0]<=m)SumOfSub(0,0,r,x,m,w);}假設(shè)n=8,[w1,….,w8]=[100,200,50,90,150,50,20,80],c=400.利用貪心算法時(shí)，所考察貨箱的順序?yàn)?,3,6,8,4,1,5,2.貨箱7,3,6,8,4,1的總重量為390個(gè)單位且已被裝載，剩下的裝載能力為10，小于剩下的任何一個(gè)貨箱。根據(jù)貪心解決算法，得到[x1,…,x8]=[1,0,1,1,0,1,1,1],且∑Xi=6.解、貨箱裝船算法實(shí)現(xiàn)：voidContainerLoading(intX[],Tw[],Tc,intn){//貨箱裝船問(wèn)題的貪心算法//x[t]=1當(dāng)且僅當(dāng)貨箱t被裝載，1<=t<=n//c是船的容量，w是貨箱的重量//t是間接尋址表int*t=newint[n+1];IndirectSort(w,t,n);//此時(shí)，w[t[t]]<=w[t[t+1]],1<=t<n//初始化xfor(intt=1;t<=n;t++)x[t]=0;//按重量次序選擇物品for(t=1;t<=n&&w[t[t]]<=c;t++){//剩余容量想x[[t]]=1;c-=w[t[t]];}delete[]t;}（貨箱裝船問(wèn)題。貨箱可以分步裝載，每步裝一個(gè)貨箱，且需要考慮裝載哪一個(gè)貨箱。根據(jù)這種思想可利用如下貪心準(zhǔn)則：從剩下的貨箱中，選擇重量最小的貨箱。這種選擇次序可以保證所選的貨箱總重量最小，從而可以裝載更多的貨箱。根據(jù)這種貪心策略，首先選擇最輕的貨箱，然后選擇次輕的貨箱，如此下去，直到所有貨箱均裝上船，或船上不能再容納其他任何一個(gè)貨箱。）四、應(yīng)用題（30分）1（5分）、設(shè)背包問(wèn)題實(shí)例n=7，M=15,(w0,w1,w2…,w6)=(2,3,5,7,1,4,1),物品裝入背包的收益為：(p0,p1,p2,…,p6)=(10,5,15,7,6,18,3)。求這一實(shí)驗(yàn)的最優(yōu)解和最大收益。答案：由定理：如果p0/w0>=…>=pn-1/wn-1,則用貪心法求得的背包問(wèn)題的解是最優(yōu)解，知按pi/wi的非增次序選取物品可求得最優(yōu)解設(shè)背包問(wèn)題的解為x=(x0,x1,x2,x3,x4,x5,x6),由已知條件知(p0/w0,p1/w1,…,p6/w6)=(5,1.67,3,1,6,4.5,3),使用這一標(biāo)準(zhǔn)得到的解即最優(yōu)解為，(x0,x1,…,x6)=(1,2/3,1,0,1,1,1)此時(shí)∑WiXi=(1*2+2/3*3+1*5+0*7+1*1+1*4+1)=15符合題目要求最大收益為：max∑pixi=5*2/3+15*1+6*1+18*1+3*1=55.332（5）、寫(xiě)出對(duì)下圖所示的多段圖采用向后遞推動(dòng)態(tài)規(guī)劃算法求解時(shí)的計(jì)算過(guò)程0010256478t856332542671632答案：Bcost(1,0)=0Bcost(2,1)=5Bcost(2,2)=2Bcost(3,3)=min{3+Bcost(2,1),6+Bcost(2,2)}=8Bcost(3,4)=7Bcost(3,5)=min{3+Bcost(2,1),8+Bcost(2,2)}=8Bcost(4,6)=min{1+Bcost(3,3),6+Bcost(3,4),6+Bcost(3,5)}=9Bcost(4,7)=min{4+Bcost(3,3),2+Bcost(3,4),3+Bcot(3,5)}=9Bcost(5,8)=min{7+Bcost(4,6),3+Bcost(4,7)}=123（10分）、設(shè)有帶時(shí)限的作業(yè)排序?qū)嵗簄=4,(p0,d0,t0)=(5,1,1),(p1,d1,t0)=(10,3,2),(p2,d2,t2)=(6,2,1)和(p3,d3,t3)=(3,1,1),求使得總收益最大的作業(yè)子集J。c=8u=241c=8u=24114351191015c=02