1、算法分析與設計期末復習題(二)一、簡要回答下列問題 ：1. 算法重要特性是什么？ 2. 算法分析的目的是什么？3. 算法的時間復雜性與問題的什么因素相關？4. 算法的漸進時間復雜性的含義？5. 最壞情況下的時間復雜性和平均時間復雜性有什么不同？6. 簡述二分檢索（折半查找）算法的基本過程。7. 背包問題的目標函數和貪心算法最優化量度相同嗎？8. 采用回溯法求解的問題，其解如何表示？有什么規定？9. 回溯法的搜索特點是什么？ 10. n皇后問題回溯算法的判別函數place的基本流程是什么？11. 為什么用分治法設計的算法一般有遞歸調用？12. 為什么要分析最壞情況下的算法時間復雜性？ 13. 簡

2、述漸進時間復雜性上界的定義。14. 二分檢索算法最多的比較次數？15. 快速排序算法最壞情況下需要多少次比較運算？16. 貪心算法的基本思想？17. 回溯法的解（x1,x2,xn）的隱約束一般指什么？18. 闡述歸并排序的分治思路。19. 快速排序的基本思想是什么。 20. 什么是直接遞歸和間接遞歸？消除遞歸一般要用到什么數據結構？21. 什么是哈密頓環問題？22. 用回溯法求解哈密頓環，如何定義判定函數？23. 請寫出prim算法的基本思想。參考答案：1. 確定性、可實現性、輸入、輸出、有窮性2. 分析算法占用計算機資源的情況，對算法做出比較和評價，設計出額更好的算法。3. 算法的時間復雜性

3、與問題的規模相關，是問題大小n的函數。4當問題的規模n趨向無窮大時，影響算法效率的重要因素是T(n)的數量級，而其他因素僅是使時間復雜度相差常數倍，因此可以用T(n)的數量級(階)評價算法。時間復雜度T(n)的數量級(階)稱為漸進時間復雜性。5. 最壞情況下的時間復雜性和平均時間復雜性考察的是n固定時，不同輸入實例下的算法所耗時間。最壞情況下的時間復雜性取的輸入實例中最大的時間復雜度：W(n) = max T(n，I) , IDn平均時間復雜性是所有輸入實例的處理時間與各自概率的乘積和：A(n) =P(I)T(n，I) IDn6. 設輸入是一個按非降次序排列的元素表Ai：j 和x，選取A(i+

4、j)/2與x比較，如果A(i+j)/2=x，則返回(i+j)/2，如果A(i+j)/2<x，則Ai：(i+j)/2-1找x，否則在A (i+j)/2+1：j 找x。上述過程被反復遞歸調用。回溯法的搜索特點是什么7. 不相同。目標函數：獲得最大利潤。最優量度：最大利潤/重量比。8. 問題的解可以表示為n元組：（x1,x2,xn），xiSi, Si為有窮集合，xiSi, （x1,x2,xn）具備完備性，即（x1,x2,xn）是合理的，則（x1,x2,xi）(i<n)一定合理。9. 在解空間樹上跳躍式地深度優先搜索，即用判定函數考察xk的取值，如果xk是合理的就搜索xk為根節點的子樹，如

5、果xk取完了所有的值，便回溯到xk-1。10. 將第K行的皇后分別與前k-1行的皇后比較，看是否與它們相容，如果不相容就返回false，測試完畢則返回true。11 . 子問題的規模還很大時，必須繼續使用分治法，反復分治，必然要用到遞歸。12 最壞情況下的時間復雜性決定算法的優劣，并且最壞情況下的時間復雜性較平均時間復雜性游可操作性。 13 .T(n)是某算法的時間復雜性函數，f(n)是一簡單函數，存在正整數No和C，nNo，有T(n)<f(n)，這種關系記作T(n)=O(f(n)。14 .二分檢索算法的最多的比較次數為 log n 。15.最壞情況下快速排序退化成冒泡排序，需要比較n2

6、次。16. 是一種依據最優化量度依次選擇輸入的分級處理方法。基本思路是：首先根據題意，選取一種量度標準；然后按這種量度標準對這n個輸入排序，依次選擇輸入量加入部分解中。如果當前這個輸入量的加入，不滿足約束條件，則不把此輸入加到這部分解中。17回溯法的解（x1,x2,xn）的隱約束一般指個元素之間應滿足的某種關系。 18. 講數組一分為二，分別對每個集合單獨排序，然后將已排序的兩個序列歸并成一個含n個元素的分好類的序列。如果分割后子問題還很大，則繼續分治，直到一個元素。19.快速排序的基本思想是在待排序的N個記錄中任意取一個記錄，把該記錄放在最終位置后，數據序列被此記錄分成兩部分。所有關鍵字比該

7、記錄關鍵字小的放在前一部分，所有比它大的放置在后一部分，并把該記錄排在這兩部分的中間，這個過程稱作一次快速排序。之后重復上述過程，直到每一部分內只有一個記錄為止。20.在定義一個過程或者函數的時候又出現了調用本過程或者函數的成分，既調用它自己本身，這稱為直接遞歸。如果過程或者函數P調用過程或者函數Q，Q又調用P，這個稱為間接遞歸。消除遞歸一般要用到棧這種數據結構。21.哈密頓環是指一條沿著圖G的N條邊環行的路徑，它的訪問每個節點一次并且返回它的開始位置。22.當前選擇的節點Xk是從未到過的節點,即XkXi(i=1,2,k-1)，且C(Xk-1, Xk)，如果k=-1，則C(Xk, X1) 。2

8、3. 思路是：最初生成樹T為空，依次向內加入與樹有最小鄰接邊的n-1條邊。處理過程：首先加入最小代價的一條邊到T，根據各節點到T的鄰接邊排序，選擇最小邊加入，新邊加入后，修改由于新邊所改變的鄰接邊排序，再選擇下一條邊加入，直至加入n-1條邊。二、復雜性分析1、 MERGESORT(low，high) if low<high； then mid(low，high)/2； MERGESORT(low，mid)； MERGESORT(mid+1，high)； MERGE(low，mid，high)； endif end MERGESORT答: 1、 遞歸方程 設n=2k解遞歸方程：2、 pro

9、cedure S1(P，W，M，X，n) i1; a0 while i n do if W(i)>M then return endif aa+i ii+1 ; repeat end 解： i1 ;s0 時間為：O(1) while i n do 循環n次 循環體內所用時間為 O(1) 所以 總時間為:T(n)=O(1)+ nO(1)= O(n)3.procedure PARTITION(m,p) Integer m,p,i;global A(m:p-1) vA(m);im looploop ii+1 until A(i) v repeatloop pp-1 until A(p) v r

10、epeat if i<p then call INTERCHANGE(A(i),A(p) else exit endif repeat A(m) A(p);A(p) v End PARTITION解：最多的查找次數是p-m+1次 4.procedure F1(n) if n<2 then return(1) else return(F2(2,n,1,1) endif end F1 procedure F2(i,n,x,y) if in then call F2(i+1,n,y,x+y) endif return(y) end F2解：F2（2，n,1,1）的時間復雜度為： T(n)

11、=O(n-2); 因為in時要遞歸調用F2，一共是n-2次 當n1時F1(n)的時間為 O(1)當n>1時F1(n)的時間復雜度與F2(2,n,1,1)的時間復雜度相同即為為 O(n) 5.procedure MAX(A,n,j) xmaxA(1);j1 for i2 to n do if A(i)>xmax then xmaxA(i); ji;endif repeatend MAX 解：xmaxA(1);j1 時間為：O(1) for i2 to n do 循環最多n-1次 所以 總時間為:T(n)=O(1)+ (n-1)O(1)= O(n)6.procedure BINSRCH

12、(A,n,x,j) integer low,high,mid,j,n; low1;highn while lowhigh do mid|_(low+high)/2_| case :x<A(mid):highmid-1:x>A(mid):lowmid+1:else:jmid; return endcase repeat j0 end BINSRCH解：log2n+1三、算法理解1、寫出多段圖最短路經動態規劃算法求解下列實例的過程，并求出最優值。51342678各邊的代價如下：C(1,2)=3， C(1,3)=5 ，C(1,4)=2 C(2,6)=8 ，C(2,7)=4 ，C(3,5)

13、=5 ，C(3,6)=4， C(4,5)=2，C(4,6)=1C(5,8)=4， C(6,8)=5 ，C(7,8)=6解：Cost(4,8)=0Cost(3,7)= C(7,8)+0=6 ，D5=8Cost(3,6)= C(6，8)+0=5, D6=8Cost(3,5)= C(5，8)+0=4 D7=8Cost(2,4)= minC(4，6)+ Cost(3,6), C(4，5)+ Cost(3,5) = min1+ 5, 2+4=6 D4=6Cost(2,3)= minC(3，6)+ Cost(3,6) = min4+5=9 D3=5Cost(2,2)= minC(2，6)+ Cost(3,

14、6), C(2，7)+ Cost(3,7) = min8+5, 4+6=10 D2=7Cost(1,1)= minC(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ Cost(2,4) = min3+10, 5+9,2+6= 8D1=414682、 寫出maxmin算法對下列實例中找最大數和最小數的過程。數組 A=(48,12,61,3,5,19,32,7) 解：寫出maxmin算法對下列實例中找最大數和最小數的過程。數組 A=() 1、 48,12,61,3, 5,19,32,72、48,12 61,3 5,19 32,73、 4861, 123 19

15、32，574、 6132 355、 61 33、 快速排序算法對下列實例排序，算法執行過程中，寫出數組A第一次被分割的過程。 A=(65,70,75,80,85,55,50,2)解：第一個分割元素為65(1) (2) (3) (4) (5) (6) (7) (8) i p65 70 75 80 85 55 50 2 2 865 2 75 80 85 55 50 70 3 765 2 50 80 85 55 75 70 4 665 2 50 55 85 80 75 70 4 655 70 75 80 85 65 50 24、 歸并排序算法對下列實例排序，寫出算法執行過程。 A=(48,12,61

16、,3,5,19,32,7) 解： 48,12,61,3 5,19,32,748,12 61,3 5,19 32,712,48 3,61 5,19 7,32 3, 12, 48, 61 5, 7, 19，323,5, 7,12，19，32，48,61 5、 寫出圖著色問題的回溯算法的判斷Xk是否合理的過程。解：i0while i<k do if Gk,i=1 and Xk= Xi then return false ii+1repeat if i= k then return true6、 對于下圖，寫出圖著色算法得出一種著色方案的過程。1342解：K1X1 1 , 返回 trueX21,

17、返回false; X2X2+1=2, 返回 trueX31 ,返回false; X3X3+1=2, 返回false;X3X3+1=3, 返回 true X41, 返回false; X4X4+1=2, 返回false;X4X4+1=3, 返回 true找到一個解 （1，2，3，3）7、 寫出第7題的狀態空間樹。解：X1=1X2=2X4=33X3=338、寫出歸并排序算法對下列實例排序的過程。(6,2,9,3,5,1,8,7)解：調用第一層次 6,2,9,3 5,1,8,7 分成兩個子問題 調用第二層次 6,2 9,3 5,1 8,7 分成四個子問題 調用第三層次 6 2 9 3 5 1 8 7

18、分成八個子問題 調用第四層次 只有一個元素返回上一層第三層歸并 2 ,6 3, 9 1,5 7,8 返回上一層第二層歸并 2 ,3,6, 9 1,5,7,8 返回上一層第一層歸并 1, 2 ,3, 5 ,6, 7, 8,9 排序結束，返回主函數9、寫出用背包問題貪心算法解決下列實例的過程。 P=(18,12,4,1) W=(12,10,8,3) M=25解: 實例符合P(i)/W(i)P(i+1)/W(i+1)的順序。 CU25,X0 W1< CU: x11; CUCU-W1=13; W2< CU: x21; CUCU-W2=3;W3>CU: x3CU/ W3=3/8;實例的

19、解為：（1，1，3/8，0）11、有一個有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當使用二分查找值為82的結點時，經過多少次比較后查找成功并給出過程。解：有一個有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當使用二分查找值為82的結點時，經過多少次比較后查找成功并給出過程。一共要要執行四次才能找到值為82的數。12、使用prim算法構造出如下圖G的一棵最小生成樹。124356dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5; dist(1,3)=1;

20、dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6解：使用普里姆算法構造出如下圖G的一棵最小生成樹。124356dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5; dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=61316136412645126343313、有如下函數說明int f(int x,int y) f=x Mod y +1;已知a=10,b=4,c=5 則執行k=f(f(a+c,b),f(b,c)后，k

21、的值是多少并寫出詳細過程。解：有如下函數說明int f(int x,int y) f=x Mod y +1;已知a=10,b=4,c=5 則執行k=f(f(a+c,b),f(b,c)后，k的值是多少并寫出詳細過程。 K的值是514、McCathy函數定義如下：當x>100時 m(x)=x-10;當x<=100時 m(x)=m(m(x+11);編寫一個遞歸函數計算給定x的m(x)值。解：McCathy函數定義如下：當x>100時 m(x)=x-10;當x<=100時 m(x)=m(m(x+11);編寫一個遞歸函數計算給定x的m(x)值。int m(int x)int y;

22、 if(x>100) return(x-100);else y=m(x+11); return (m(y); 15、 設計一個算法在一個向量A中找出最大數和最小數的元素。解：設計一個算法在一個向量A中找出最大數和最小數的元素。Void maxmin(A,n)Vector A;int n;int max,min,i; max=A1;min=A1;for(i=2;i<=n;i+)if(Ai>max)max=Ai;else if(Ai<min)min=Ai;printf(“max=%d,min=%dn”,max,min); 四、設計算法 1. 設有n項獨立的作業1,2, n,

23、由m臺相同的機器加工處理。作業i所需要的處理時間為ti。約定：任何一項作業可在任何一臺機器上處理，但未完工前不準中斷處理；任何作業不能拆分更小的子作業。多機調度問題要求給出一種調度方案，使所給的n個作業在盡可能短的時間內由m臺機器處理完。設計算法，并討論是否可獲最優解。解：對于處理機j，用Sj 表示處理機j已有的作業數，用Pj,k表示處理機j的第k個作業的序號 。1）將作業按照t1t2tn排序2）S1:m清零 j0 /從第一個處理機開始安排3) for i1 to n do /安排n個作業 jj mod m +1 /選下一個處理機SjSj+1; Pj,Sji ； Repeat2. 設有n種面值

24、為:d1d2dn的錢幣，需要找零錢M，如何選擇錢幣dk，的數目Xk，滿足 d1×Xidn×Xn=M ，使得XiXn 最小 請選擇貪心策略，并設計貪心算法。解：貪心原則：每次選擇最大面值硬幣。CUM;i1;X0 / X為解向量While CU0 do XiCU div di / Xi為第i中硬幣數CUCU-di*Xiii+1;repeat3. 有n個物品，已知n=7, 利潤為P=(10,5,15,7,6,18,3)，重量W=(2,3,5,7,1,4,1)，背包容積M=15,物品只能選擇全部裝入背包或不裝入背包，設計貪心算法，并討論是否可獲最優解。解：定義結構體數組G，將物品編號、利潤、重量作為一個結構體：例如Gk=1,10,2求最優解，按利潤/重量的遞減序，有 5,6,1,6 1,10,2,56,18,4,9/2 3,15,5,3 7,3,1,32,5,3,5/3 4,7,7,1 算法 procedure KNAPSACK(P，W，M，X，n) /P(1：n)和W(1；n)分別含有按 P(i)/W(i)P(i+1)/W(i+1)排序的n件物品的效益值 和重量。M是背包的容量大小，而x(1：n)是解向量/ real P(1：n)，W(1：n)，X(1：n)，M，cu； integer i，n； X0 /將解向量初始化為零/ cuM /cu