1、一、選擇題（15*2分）1.算法分析是（C）A. 將算法用某種程序設計語言恰當地表示出來B. 在抽象數據集合上執行程序，以確定是否會產生錯誤的結果C. 對算法需要多少計算時間和存儲空間作定量分析D. 證明算法對所有可能的合法輸入都能算出正確的答案2.算法與程序的區別在于算法具有（C）A.能行性B.確定性C.有窮性D.輸入和輸出3.記號0的定義正確的是（B）A.O(g( n) = f(n) |存在正常數c和nO使得當n > no有f（n） < cg（n） B.O(g( n) = f(n) |存在正常數c和nO使得當n>no有cg（n） < f（n） C. (g( n) =

2、 f(n) | 有 f(n)vcg(n) D. (g( n) = f(n) | 有 cg(n) < f(n) 對于任何正常數c>0,存在正數和no >0使得對所有n>no對于任何正常數c>0,存在正數和no >0使得對所有n>no4.衡量一個算法好壞的標準是（C）A.運行速度快B.占用空間少C.時間復雜度低D.代碼短5.二分搜索算法是利用（A）實現的算法。A.分治法B.動態規劃法C.貪心法 D.回溯法6.下面問題（B ）不能使用貪心法解決。A.單源最短路徑問題B. N皇后問題C.最小代價生成樹問題D.背包問題7 .用貪心法設計算法的關鍵是（B ） 0A

3、. 將問題分解為多個子問題來分別處理B. 選好最優量度標準C. 獲取各階段間的遞推關系式D. 滿足最優性原理8.找最小生成樹的算法Kruskal的時間復雜度為（D ）（其中n為無向圖的結點 數，m為邊數）A. O（n2） B . O（mlogn） C . O（nlogm） D . O（mlogm）9.回溯法搜索狀態空間樹是按照（C ）的順序。A.中序遍歷 B.廣度優先遍歷C.深度優先遍歷D.層次優先遍歷10. 一個問題可用動態規劃算法或貪心算法求解的關鍵特征是問題的（B ）A.重疊子問題B.最優子結構性質C.最優量度標準性質 D.定義最優解11.程序塊(A)是回溯法中遍歷排列樹的算法框架程序。

4、A.void backtrack(i nt t)if(t >n )out put(x);elsefor(i nt i=t;i<=n ;i+)swa p(xt,xi);if(legal(t)backtrack(t+1);swa p(xt,xi);B. Void backtrack (i nt t)if(t> n)out pu t(x);elsefor( int i=0;i<=1;i+)xt=i;if(legal(t)backtrack(t+1);C.Void backtrack (i nt t)if(t> n)out pu t(x);elsefor(i nt i=0

5、;iv=1;i+)xt=i; if(legal(t)backtrack(t-1);D.Void backtrack (int t)if(t> n)o ut put(x);elsefor(i nt i=t;i<=n ;i+)Swa p( xt,xi);if(legal(t)backtrack(t+1);12.0-1背包問題的回溯算法所需的計算時間為(A.O(n2n) B.O (nlogn )C.O (2n)A )D.O (n)13.A.O哈弗曼編碼的貪心算法所需的計算時間為(n2n) B.O (nlogn ) C.O (2n) D.O (n)14. 矩陣連乘問題的算法可由(B)設計實

6、現。A.分支界限算法B.動態規劃算法C.貪心算法D.回溯算法15. 采用廣度優先策略搜索的算法是(A )。A.分支界限法B.動態規劃法C.貪心法D.回溯法1.算法的復雜性有之分，衡量一個算法好壞的標準是二、填空題(15*2分)2. 某一問題可用動態規劃算法求解的顯著特征是3. 若序列A=xzyzzyx , B=zxyyzxz,請給出序列A和B的一個最長公共子序列。先求解4. 動態規劃算法的基本思想是將待求解問題分解成若干然后從這些勺解得到原問題的解。5.0-1背包問題的回溯算法所需的計算時間為 用動態規劃算法所需的計算時間為6. 二分法搜索算法是利用7. 所謂最優化問題是指問題給定某些約束條件

7、，。8. 回溯法解決問題時，應明確定義問題的解空間，。9. 描述問題解空間的樹形結構。10. 在分枝限界法中一個活結點只可能一次成為點可能成為E結點。實現的算法。滿足這些約束條件的問題解稱為問題的解空間至少應包含E結點，回溯法中任何一個或結答案：1.時間、空間 時間復雜度空間復雜度。2. 算法效率3. xyzz.4. 子問題 子問題 子問題5.0 (n*2n) o(minnc 2、)6.動態規劃法7.可行解8.2n9. 狀態空間樹10. 多次三、算法設計題（每題10分、共20分）1、設計一個回溯算法，使用可變長度狀態空間樹求解子集和數問題。解、子集和數的回溯算法:void SumOfSub(f

8、loat s,i nt k,float r,i nt*x,float m,float*w) xk=1;if(s+wk=m) for(i nt j=0;j<=k;j+)cout<<xj<< coutvve ndl;else if(s+wk+wk+1v=m)SumOfSub(s+wk,k+1,r-wk,x,m,w);if(s+r-wk>=m)&&(s+wk+1v=m) xk=0;SumOfSub(s,k+1,r-wk,x,m,w);void SumSub(i nt*x,i nt n, float m,float*w)float r=0;for(i

9、 nt i=0;i vn ;i+)r=r+wi;if(r>=m&&w0v=m)SumOfSub(0,0,r,x,m,w);利用貪心算2、假設 n=8,w1,.,w8=100,200,50,90,150,50,20,80,c=400.法時，所考察貨箱的順序為7,3,6,8,4,1,52 貨箱736,8,4,1的總重量為且刀Xi=6.390個單位且已被裝載，剩下的裝載能力為 10,小于剩下的任何一個貨箱。根據貪心解決算法，得到x1,x8=1,0,1,1,0,1,1,1.解、貨箱裝船算法實現：void Contain erLoad in g(i nt X,T w,T c,i n

10、t n)/貨箱裝船問題的貪心算法 /xt=1 當且僅當貨箱t被裝載，1<=t<=n/c是船的容量，w是貨箱的重量/t是間接尋址表 int *t=new in t n+1;In directSort(w,t, n);/ 此時，wtt<=wtt+1,1<=t<n/初始化x for(i nt t=1;t<=n; t+) xt=0;/按重量次序選擇物品 for(t=1;t<=n&&wtt<=c;t+)/剩余容量想 xt=1;c-=wtt;deletet;（貨箱裝船問題。貨箱可以分步裝載，每步裝一個貨箱，且需要考慮裝載哪一個貨箱。根據這種思

11、想可利用如下貪心準則： 從剩下的貨箱中，選擇重量最小的貨箱。這種選擇次序可以保證所選的貨箱總重量最小，從而可以裝載更多的貨箱。根據這種貪心策略，首先選擇最輕的貨箱，然后選擇次輕的貨箱，如此下去，直到所有貨箱均裝上船，或船上不能再容納其他任何一個貨箱。)四、應用題(30分)1 (5分)、設背包問題實例 n=7 , M=15,(w0,w1,w2,w6)=(2,3,5,7,1,4,1),物品裝入背包的 收益為：(p0,p 1,p2,p6)=(10,5,15,7,6,18,3)0求這一實驗的最優解和最大收益。答案：由定理：如果p0/w0>=- >=pn-1/w n-1,則用貪心法求得的背包

12、問題的解是最優解， 知按pi/wi的非增次序選取物品可求得最優解設背包問題的解為x=(x0,x1,x2,x3,x4,x5,x6),由已知條件知(p0/w0,p1/w1,p6/w6)=(5,1.67,3,1,6,4.5,3)使用這一標準得到的解即最優 解為，(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 符 合題目要求最大收益為：maxX P ixi=5*2/3+15*1+6*1+18*1+3*1=55.332 (5)、寫出對下圖所示的多段圖采用向后遞推動態規劃算法求解時的計算過程答案：Bcost(1,0)=0Bcost(2,1)=5Bcost(2,2)=2Bcost(3,3)=mi n3+Bcost(2,1),6+Bcost(2,2)=8Bcost(3,4)=7Bcost(3,5)=mi n3+Bcost(2,1),8+Bcost(2,2)=8Bcost(4,6)=mi n1+Bcost(3,3),6+Bcost(3,4),6+Bcost(3,5)=9Bcost(4,7)=mi n4+Bcost