算法設(shè)計試題

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

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

C.貪心法

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

A.單源最短路徑問題 B.N皇后問題

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

A.中序遍歷B.廣度優(yōu)先遍歷C.深度優(yōu)先遍歷D.層次優(yōu)先遍歷10.一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的（B）A.重疊子問題 B.最優(yōu)子結(jié)構(gòu)性質(zhì) C.最優(yōu)量度標準性質(zhì) D.定義最優(yōu)解11.程序塊（A）是回溯法中遍歷排列樹的算法框架程序。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背包問題的回溯算法所需的計算時間為（

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

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

C.貪心算法

D.回溯算法15.采用廣度優(yōu)先策略搜索的算法是（A）。A.分支界限法 B.動態(tài)規(guī)劃法 C.貪心法 D.回溯法二、填空題（15*2分）1.算法的復雜性有______和______之分,衡量一個算法好壞的標準是_____________。2.某一問題可用動態(tài)規(guī)劃算法求解的顯著特征是_________________________。3.若序列A={xzyzzyx}，B={zxyyzxz}，請給出序列A和B的一個最長公共子序列__________________。4.動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干___________先求解_________,然后從這些_____________的解得到原問題的解。5.0-1背包問題的回溯算法所需的計算時間為____________,用動態(tài)規(guī)劃算法所需的計算時間為________________。6.二分法搜索算法是利用___________實現(xiàn)的算法。7.所謂最優(yōu)化問題是指問題給定某些約束條件，滿足這些約束條件的問題解稱為___________。8.回溯法解決問題時，應(yīng)明確定義問題的解空間，問題的解空間至少應(yīng)包含________。9.__________是描述問題解空間的樹形結(jié)構(gòu)。10.在分枝限界法中一個活結(jié)點只可能一次成為E結(jié)點，回溯法中任何一個或結(jié)點可能____成為E結(jié)點。答案：1.時間、空間時間復雜度空間復雜度。2.算法效率3.xyzz.4.子問題子問題子問題5.o（n*2n）o(min{nc2n})6.動態(tài)規(guī)劃法7.可行解8.2n9.狀態(tài)空間樹10.多次三、算法設(shè)計題（每題10分、共20分）1、設(shè)計一個回溯算法，使用可變長度狀態(tài)空間樹求解子集和數(shù)問題。解、子集和數(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.利用貪心算法時，所考察貨箱的順序為7,3,6,8,4,1,5,2.貨箱7,3,6,8,4,1的總重量為390個單位且已被裝載，剩下的裝載能力為10，小于剩下的任何一個貨箱。根據(jù)貪心解決算法，得到[x1,…,x8]=[1,0,1,1,0,1,1,1],且∑Xi=6.解、貨箱裝船算法實現(xiàn)：voidContainerLoading(intX[],Tw[],Tc,intn){//貨箱裝船問題的貪心算法//x[t]=1當且僅當貨箱t被裝載，1<=t<=n//c是船的容量，w是貨箱的重量//t是間接尋址表int*t=newint[n+1];IndirectSort(w,t,n);//此時，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;}（貨箱裝船問題。貨箱可以分步裝載，每步裝一個貨箱，且需要考慮裝載哪一個貨箱。根據(jù)這種思想可利用如下貪心準則：從剩下的貨箱中，選擇重量最小的貨箱。這種選擇次序可以保證所選的貨箱總重量最小，從而可以裝載更多的貨箱。根據(jù)這種貪心策略，首先選擇最輕的貨箱，然后選擇次輕的貨箱，如此下去，直到所有貨箱均裝上船，或船上不能再容納其他任何一個貨箱。）四、應(yīng)用題（30分）1（5分）、設(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)。求這一實驗的最優(yōu)解和最大收益。答案：由定理：如果p0/w0>=…>=pn-1/wn-1,則用貪心法求得的背包問題的解是最優(yōu)解，知按pi/wi的非增次序選取物品可求得最優(yōu)解設(shè)背包問題的解為x=(x0,x1,x2,x3,x4,x5,x6),由已知條件知(p0/w0,p1/w1,…,p6/w6)=(5,1.67,3,1,6,4.5,3),使用這一標準得到的解即最優(yōu)解為，(x0,x1,…,x6)=(1,2/3,1,0,1,1,1)此時∑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）、寫出對下圖所示的多段圖采用向后遞推動態(tài)規(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è)有帶時限的作業(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