算法分析期末考試集答案套

1、算法分析與設計一、 解答題1. 機器調(diào)度問題。問題描述：現(xiàn)在有n件任務和無限多臺的機器，任務可以在機器上得到處理。每件任務的開始時間為si，完成時間為fi，si n) / 到達葉結(jié)點 更新最優(yōu)解bestx,bestw;return; r -= wi; if (cw + wi bestw) xi = 0; / 搜索右子樹 backtrack(i + 1); r += wi; 5. 用分支限界法解裝載問題時，對算法進行了一些改進，下面的程序段給出了改進部分；試說明斜線部分完成什么功能，以及這樣做的原因，即采用這樣的方式，算法在執(zhí)行上有什么不同。/ 檢查左兒子結(jié)點 Type wt = Ew + wi

2、; / 左兒子結(jié)點的重量 if (wt bestw) bestw = wt; / 加入活結(jié)點隊列 if (i bestw & i 0 故Ew+rbestw總是成立。也就是說，此時右子樹測試不起作用。為了使上述右子樹測試盡早生效，應提早更新bestw。又知算法最終找到的最優(yōu)值是所求問題的子集樹中所有可行結(jié)點相應重量的最大值。而結(jié)點所相應得重量僅在搜索進入左子樹是增加，因此，可以在算法每一次進入左子樹時更新bestw的值。7. 最長公共子序列問題：給定2個序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長公共子序列。 由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關系。用

3、cij記錄序列Xi和Yj的最長公共子序列的長度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。當i=0或j=0時，空序列是Xi和Yj的最長公共子序列。故此時Cij=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關系如下：在程序中，bij記錄Cij的值是由哪一個子問題的解得到的。（1） 請?zhí)顚懗绦蛑械目崭?，以使函?shù)LCSLength完成計算最優(yōu)值的功能。void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0; for (i = 1; i = n; i+

4、) c0i = 0; for (i = 1; i = m; i+) for (j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; （2） 函數(shù)LCS實現(xiàn)根據(jù)b的內(nèi)容打印出Xi和Yj的最長公共子序列。請?zhí)顚懗绦蛑械目崭瘢允购瘮?shù)LCS完成構(gòu)造最長公共子序列的功能（請將bij的取值與（1）中您填寫的取值對應，否則視為錯誤）。void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1，j-1，x，b); cout0 ) printf(%

5、dn ,k); f(k-1); f(k-1); 二、復雜性分析1、 MERGESORT(low，high) if lowM then return endif aa+i ii+1 ; repeat end 解： i1 ;s0 時間為：O(1) while i n do 循環(huán)n次 循環(huán)體內(nèi)所用時間為 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

6、A(p) v repeat if ip then call INTERCHANGE(A(i),A(p) else exit endif repeat A(m) A(p);A(p) v End PARTITION解：最多的查找次數(shù)是p-m+1次 4.procedure F1(n) if n1時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

7、時間為：O(1) for i2 to n do 循環(huán)最多n-1次 所以 總時間為:T(n)=O(1)+ (n-1)O(1)= O(n) 6.procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low1;highn while lowhigh do mid|_(low+high)/2_| case :xA(mid):lowmid+1:else:jmid; return endcase repeat j0 end BINSRCH解：log2n+1三、算法理解1、寫出多段圖最短路經(jīng)動態(tài)規(guī)劃算法求解下列實例的過程，并求出最優(yōu)值。52863174各邊

8、的代價如下：C(1,2)=3， C(1,3)=5 ，C(1,4)=2 C(2,6)=8 ，C(2,7)=4 ，C(3,5)=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

9、(3，6)+ Cost(3,6) = min4+5=9 D3=5Cost(2,2)= minC(2，6)+ Cost(3,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算法對下列實例中找最大數(shù)和最小數(shù)的過程。數(shù)組 A=(48,12,61,3,5,19,32,7) 解：寫出maxmin算法對下列實例中找最大數(shù)和最小數(shù)的過程。數(shù)組 A=()

10、1、 48,12,61,3, 5,19,32,72、48,12 61,3 5,19 32,73、 4861, 123 1932，574、 6132 355、 61 33、 快速排序算法對下列實例排序，算法執(zhí)行過程中，寫出數(shù)組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

11、655 70 75 80 85 65 50 24、 歸并排序算法對下列實例排序，寫出算法執(zhí)行過程。 A=(48,12,61,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 ik do if Gk,i=1 and Xk= Xi then return false ii+1repeat if i= k then return

12、true6、 對于下圖，寫出圖著色算法得出一種著色方案的過程。2314解：K1X1 1 , 返回 trueX21,返回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題的狀態(tài)空間樹。解：X1=1X2=2X3=33X4=338、寫出歸并排序算法對下列實例排序的過程。(6,2,9,3,5,1,8,7)解：調(diào)用第一層次 6,2,9,3 5,1,8,7 分成兩個子

13、問題 調(diào)用第二層次 6,2 9,3 5,1 8,7 分成四個子問題 調(diào)用第三層次 6 2 9 3 5 1 8 7 分成八個子問題 調(diào)用第四層次 只有一個元素返回上一層第三層歸并 2 ,6 3, 9 1,5 7,8 返回上一層第二層歸并 2 ,3,6, 9 1,5,7,8 返回上一層第一層歸并 1, 2 ,3, 5 ,6, 7, 8,9 排序結(jié)束，返回主函數(shù)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;

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

15、st(4,1)=5; dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6解：使用普里姆算法構(gòu)造出如下圖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、有如下函數(shù)說明int f(int x,int y) f=x Mod y +1;已知a=10,b=4,c=5 則執(zhí)

16、行k=f(f(a+c,b),f(b,c)后，k的值是多少并寫出詳細過程。解：有如下函數(shù)說明int f(int x,int y) f=x Mod y +1;已知a=10,b=4,c=5 則執(zhí)行k=f(f(a+c,b),f(b,c)后，k的值是多少并寫出詳細過程。 K的值是514、McCathy函數(shù)定義如下：當x100時 m(x)=x-10;當x100時 m(x)=x-10;當x100) return(x-100);else y=m(x+11); return (m(y); 15、 設計一個算法在一個向量A中找出最大數(shù)和最小數(shù)的元素。解：設計一個算法在一個向量A中找出最大數(shù)和最小數(shù)的元素。Void

17、 maxmin(A,n)Vector A;int n;int max,min,i; max=A1;min=A1;for(i=2;imax)max=Ai;else if(Aicu then exit endif X(i) 1 cucu-W(i) repeat end GREEDY-KNAPSACK 根據(jù)算法得出的解： X=（1,1,1,1,1,0,0）獲利潤52， 而解（1,1,1,1, 0, 1,0）可獲利潤54 因此貪心法不一定獲得最優(yōu)解。4. 設計只求一個哈密頓環(huán)的回溯算法。解：Hamiltonian(n)k1; xk 0; While k0 do xk xk+1; while B(k)=

18、false and xkn do xk xk+1; repeat If xkn then if k=n then print x; return else k k+1; xk0; endif else k k-1 endifrepeatendprocedure B(k) Gxk-1,xk 1 then return false; for i1 to k-1 do if xi=xk then return false;endif repeat return true; 5利用對稱性設計算法，求n為偶數(shù)的皇后問題所有解。解：利用對稱性設計算法，求n為偶數(shù)的皇后問題所有解。procedure NQU

19、EENS1(n)a0 /計數(shù)器清零X(1)0；k1 /k是當前行；X(k)是當前列/ While k0 do /對所有的行執(zhí)行以下語句/1) X(k)X(k)+1 /移到下一列/While X(k)n and not PLACE(k) do 2) X(k)X(k)十l if X(k)n then if k=n / then print(X)，aa+1 /找到一個解計數(shù)器a加1/ if a=n/2 then return / 找到n/2個解算法結(jié)束 3) else kk+1；X(k)0； 4) else kk1 /回溯/ end NQUEENS1、對于下列各組函數(shù)f(n)和g(n)，確定f(n)

20、=O(g(n)或或，并簡述理由。（12分）(1) (2) (3) 解：簡答如下： （1），（2），（3）2、試用分治法實現(xiàn)有重復元素的排列問題：設是要進行排列的個元素，其中元素可能相同，試計算的所有不同排列。（13分）解：解答如下： Templatevoid Perm(Type list,int k,int m) if(k= =m) for(int i=0;i=m;i+) coutlisti; .（4分） coutendl;else for(int i=k;i=m;i+) if(ok(list,k,i) swap(listk,listi); Perm(list,k+1,m); swap(lis

21、tk,listi); .（8分） ; 其中ok用于判別重復元素。 Template int ok(Type list,int k,int i) if(ik) for(int t=k;tI;t+) if(listt= =listi) return 0; return 1;.（13分）3、試用分治法對一個有序表實現(xiàn)二分搜索算法。（12分）解：解答如下： Templateint BinarySearch(Type a,const Type& x,int n)/假定數(shù)組a已按非遞減有序排列，本算法找到x后返回其在數(shù)組a中的位置，/否則返回-1 int left=0,right=n-1; while(l

22、eftamiddle) left=middle+1; .（8分） else right=middle-1;return -1;.（12分）4、試用動態(tài)規(guī)劃算法實現(xiàn)0-1閉包問題。（15分）解：解答如下：Templatevoid Knapsack(Type v,int w,int c,int n,Type *m) Int jMax=min(wn-1,c); for(int j=0;j=jMax;j+) mnj=0; for(int j=wn;j1;i-) jMax=min(wi-1,c); for(int j=0;j=jMax;j+) mij=mi+1j; for(int j=wi;j=w1)

23、m1c=max(m1c,m2c-w1+v1); .（10分）TemplateVoid Traceback(Type *m,int w,int c,int n,int x) for(int i=1;in;i+) if(mic= =mi+1c) xi=0; .（12分）else xi=1,c-=wi;xn=(mnc)?1:0;.（15分）5、試用貪心算法求解下列問題：將正整數(shù)n分解為若干個互不相同的自然數(shù)之和，使這些自然數(shù)的乘積最大。（15分）解：解答如下：void dicomp(int n,int a) k=1;if(n3) a1=0;return;if(nak) k+; ak=ak-1+1;

24、n-=ak;.（10分）if(n= =ak) ak+;n-;for(int i=0;in;i+) ak-i+;.（15分）6、試用動態(tài)規(guī)劃算法實現(xiàn)最大子矩陣和問題：求矩陣A的一個子矩陣，使其各元素之各為最大。（15分）解：解答如下：int MaxSum2(int m,int n,int *a) int sum=0;int *b=new intn+1;for(int i=1;i=m;i+) for(int k=1;k=n;k+) bk=0; .（5分） for(int j=i;j=m;j+) for(int k=1;ksum) sum=max; return sum; .（10分） int Ma

25、xSum(int n,int *a) int sum=0,b=0; for(int i=1;i0) b+=ai; else b=ai; if(bsum) sum=b;Return sum; .（15分）7、試用回溯法解決下列整數(shù)變換問題：關于整數(shù)的變換和定義如下：。對于給定的兩個整數(shù)和，要求用最少的變換和變換次數(shù)將變?yōu)?。?8分）解：解答如下：void compute() k=1; while(!search(1,n) k+; if(kmaxdep) break; init();.（6分）if(found) output(); else cout”No Solution!”k) return

26、false; for(int i=0;i2;i+) int n1=f(n,i);tdep=i; .（12分） if(n1= =m|search(dep+1,n1) Found=true; Out(); return true; return false; .（18分） 一、排序和查找是經(jīng)常遇到的問題。按照要求完成以下各題：（20分）（1） 對數(shù)組A=15，29，135，18，32，1，27，25，5，用快速排序方法將其排成遞減序。（2） 請描述遞減數(shù)組進行二分搜索的基本思想，并給出非遞歸算法。（3） 給出上述算法的遞歸算法。（4） 使用上述算法對（1）所得到的結(jié)果搜索如下元素，并給出搜索過程：

27、18，31，135。答案：（1）第一步：15 29 135 18 32 1 27 25 5 第二步：29 135 18 32 27 25 15 1 5 【1分】第三步：135 32 29 18 27 25 15 5 1 【1分】第四步：135 32 29 27 25 18 15 5 1 【1分】（2）基本思想：首先將待搜索元素v與數(shù)組的中間元素進行比較，如果，則在前半部分元素中搜索v；若，則搜索成功；否則在后半部分數(shù)組中搜索v。【2分】非遞歸算法：輸入：遞減數(shù)組Aleft:right，待搜索元素v。【1分】輸出：v在A中的位置pos，或者不在A中的消息（-1）?！?分】步驟：【3分】int B

28、inarySearch(int A,int left,int right,int v)int mid;while (leftAmid) right=mid-1;else left=mid+1;return -1;（3）遞歸算法：輸入：遞減數(shù)組Aleft:right，待搜索元素v。【1分】輸出：v在A中的位置pos，或者不在A中的消息（-1）?！?分】步驟：【3分】int BinarySearch(int A,int left,int right,int v)int mid;if (leftAmid) return BinarySearch(A,left,mid-1,v);else return

29、 BinarySearch(A,mid+1,right,v);elsereturn -1;（4）搜索18：首先與27比較，1827，在前半部分搜索；再次32比較，3129，此時只有一個元素，未找到，返回-1?！?分】 搜索135：首先與27比較，13527，在前半部分搜索；再次32比較，13532，在前半部分搜索；與135比較，相同，返回0。【2分】二、 對于下圖使用Dijkstra算法求由頂點a到頂點h的最短路徑。（20分）。答案：用V1表示已經(jīng)找到最短路徑的頂點，V2表示與V1中某個頂點相鄰接且不在V1中的頂點；E1表示加入到最短路徑中的邊，E2為與V1中的頂點相鄰接且距離最短的路徑。【1

30、分】步驟 V1 V2 E1 E21. ab ab2. a,bd ab bd3. a,b,d c,f ab,bd dc,df4. a,b,d,c f ab,bd df5. a,b,c,d,f e ab,bd,dc,df fe6. a,b,c,d,e,fg ab,bd,dc,df,fe eg7. a,b,c,d,e,f,gh ab,bd,dc,df,fe,eggh8. a,b,c,d,e,f,g,h ab,bd,de,df,fe,eg,gh 【以上每步2分】結(jié)果：從a到h的最短路徑為，權(quán)值為18?！?分】三假設有7個物品，它們的重量和價值如下表所示。若這些物品均不能被分割，且背包容量M150，使用

31、回溯方法求解此背包問題。請寫出狀態(tài)空間搜索樹（20分）。物品ABCDEFG重量35306050401025價值10403050354030答案：求所有頂點對之間的最短路徑可以使用Dijkstra算法，使其起始節(jié)點從a循環(huán)到h，每次求起始節(jié)點到其他節(jié)點的最短路徑，最終可以求得所有頂點對之間的最短路徑?！?分】三、按照單位效益從大到小依次排列這7個物品為：FBGDECA。將它們的序號分別記為17。則可生產(chǎn)如下的狀態(tài)空間搜索樹。其中各個節(jié)點處的限界函數(shù)值通過如下方式求得：【排序1分】【狀態(tài)空間搜索樹及其計算過程17分，每個節(jié)點1分】a b. c d. e. f. g. h. i.j. 在Q1處獲得該

32、問題的最優(yōu)解為，背包效益為170。即在背包中裝入物品F、B、G、D、A時達到最大效益，為170，重量為150?！窘Y(jié)論2分】三、 已知，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩陣鏈積A1A2A3A4A5A6的最佳求積順序。（要求：給出計算步驟）（20分）答案：使用動態(tài)規(guī)劃算法進行求解。求解矩陣為：【每個矩陣18分】12345610150330405165520102036033024301950301809301770403000186050150060123456101224220222230344404450560因此，最佳乘積序列為（A1A2）（A3A4）（A5A6），共執(zhí)行乘法2010次。【結(jié)論2分】七、算法設計題（本題10分）通過鍵盤輸入一個高精度的正整數(shù)n(n的有效位數(shù)240)，去掉其中任意s個數(shù)字后，剩下的數(shù)字按原左右次序?qū)⒔M成一個新的正整數(shù)。編程對給定的n 和s，尋找一種方案，使得剩下的數(shù)字組成的新數(shù)最小?！緲永斎搿?78543S=4【樣例輸出】13六、算法設計題（