算法分析與設(shè)計模擬試題5

1、算法設(shè)計與分析復(fù)習(xí)題參考答案1什么是算法？算法必須滿足的五個特性是什么？算法：一組有窮的規(guī)則，規(guī)定了解決某一特定類型問題的一系列運(yùn)算。 （有限指令的集合，遵循它可以完成一個特定的任務(wù)） .必須滿足的五個特性是 ( 遵循以下五條準(zhǔn)則 ) ：1有窮（限）性2確定性3可（能）行性4輸入（ n0）5輸出（ n1）2對算法進(jìn)行分析分哪兩個階段？各自完成什么任務(wù)（分別得到什么結(jié)果）？對一個算法要作出全面的分析可分成兩個階段進(jìn)行，即：事前分析和事后測試。事前分析求出該算法的一個時間界限函數(shù)；事后測試搜集此算法的執(zhí)行時間和實(shí)際占用空間的統(tǒng)計資料。3證明：若 f 1(n)= O(g 1(n) 并且 f 2(n)

2、= O(g 2(n) ，那么 f 1 (n) +f 2 (n)= O(maxg 1 (n), g2(n)證明：根據(jù) f1(n)=O(g1(n)可知，存在正常數(shù) C1，當(dāng) nn0 時，使得 |f1(n)| C1|g1(n)|；同理，根據(jù) f 2(n)= O(g 2(n) 可知，存在正常數(shù) C2，當(dāng) nn0 時，使得 |f2(n)|C2|g2(n)|當(dāng) nn0 時， |f1(n)+f2 (n)|f1(n)|+|f2(n)|C1|g1(n)|+C2|g2(n)| C1|gk(n)|+C2|gk(n)|（ C1+C2）|gk(n)|， 其中 gk(n)=maxg 1(n),g2(n) ，k=1,2當(dāng)

3、nn0 時，取 C=（C1+C2），據(jù)定義命題得證。4如果 f 1(n)= (g 1 (n)并且 f 2(n)= (g 2(n) ，下列說法是否正確？試說明之。（a） f 1 (n) +f2(n)=(g 1(n)+ g 2(n)（b） f 1 (n) +f2(n)=(ming 1 (n), g2(n)（c） f 1 (n) +f2(n)=(maxg 1 (n), g2(n)答：（ a）和（ c）均正確，（b）錯誤。（a）正確可以根據(jù)定義直接證得。2（b）錯誤可舉反例。例： f1(n)= 2n， f 2(n)=2 n下面證明（ c）正確性 .根據(jù) 上題已經(jīng)證明f 1(n)+f2(n)=O(max

4、g 1(n),g 2(n) ，下面只需證明f 1(n)+f 2(n)= (maxg1 (n), g 2(n) ，即存在正常數(shù)C，使得 |f1(n)+f 2 (n)| 12(n)C(maxg (n), g1(n)= (g12(n)=20時，存在正常根據(jù) f(n) 并且 f(g (n) 得到，當(dāng) n n數(shù) C1、C2 、C3、C4C1|g1(n)| |f 1(n)| C3|g 1(n)|C2|g2(n)| |f 2(n)| C4|g 2(n)|不妨設(shè) maxg (n), g (n)= g1(n)12由于 |f 1(n)+f2 (n)| |f1(n)|-|f2(n)| |C1|g 1 (n)|-C

5、3|g 2 (n)|=C|maxg1(n), g 2 (n)|取 C|C 1-C3| 的正常數(shù)，由定義得f 1(n)+f 2 (n) = (maxg 1(n), g 2(n)命題得證。5證明 | log 2n |= O(n)證明：對于任意的正整數(shù)n，| log 2n| |log 2（ n+1）| |n+1| 2|n|取 n0=1， C=2，根據(jù)定義知命題成立。6證明 3n log 2n= O(n 2)證明：對于任意的正整數(shù) n，|3n log 2 n | |3n log 2n| 3|n 2| 取 n0=1， C=3，根據(jù)定義知命題成立。7用數(shù)學(xué)歸納法證明：當(dāng) n 1 時，nin( n 1) /

6、 2 .i 1n證明：當(dāng) n=1 時，i1 ，n(n+1)/2=1 ，命題成立；i1假設(shè) n=k-1 時，nin(n1) / 2 成立 ; （k2）i 1nn當(dāng) n=k 時，in(n1)/2=i k(k 1) / 2 k =k(k+1)/2i1i1綜上可知，命題成立。8在下列情況下求解遞歸關(guān)系式g(n)n足夠小T(n)=f ( n)2T ( n/ 2)否則當(dāng) n=2kg(n)=O(1) 和 f(n)=O(n) ；n=2kg(n)=O(1) 和 f(n)=O(1) 。解 : T(n)=T(2 k)=2 T(2 k-1 )+f(2 k)=2(2 T(2k-2 )+f(2 k-1 ) +f(2k )

7、=22T(2 k-2 )+2 1 f(2 k-1 )+ f(2 k)=2kT(1)+2 k-1 f(2)+2 k-2 f(2 2)+ +20f(2 k )=2kg(n)+ 2 k-1 f(2)+2k-2 f(2 2 )+ +20f(2 k)當(dāng) g(n)= O(1) 和 f(n)= O(n) 時，不妨設(shè) g(n)=a ，f(n)=bn ，a，b 為正常數(shù)。則T(n)=T(2k)= 2 ka+ 2 k-1 *2b+2k-2 *2 2b+20*2 kb =2 k a+kb2k=an+bnlog 2n= O(nlog 2n)當(dāng) g(n)= O(1) 和 f(n)=O(1) 時，不妨設(shè) g(n)=c ，

8、f(n)=d ，c，d 為正常數(shù)。則T(n)=T(2 k)=c2 k+ 2 k-1 d+2k-2 d+20d=c2k+d(2 k-1)=(c+d)n-d=O(n)9求解遞推關(guān)系式： h(1) 11)1h(n)2h( n解：構(gòu)造生成函數(shù)H ( x) h(1) x h(2) x2h( k) x kk1H (x)h(1) xh(2) x 2求解 H ( x)2h(1) x22h(2) x 32xH ( x)(1 2x)H ( x) x x2x 3x( x 1)1 xH ( x)x2 x)(1 x)(1分解 H (x) 成冪級數(shù)令 H ( x)AB則 A=-1B=11x12xH ( x)11(1 x

9、x 2) (1 2x (2x)2(2x)3)1x1 2x(21) x(221) x2( 2n1) xnk 1(2k1) x k所以 h(n)2 n110求解遞推關(guān)系式：解：T11Tn2Tn 12Tn 2Tn 1 2 2(Tn 2 2) 2 22 Tn 2 222 2n 1T1 (2 n 12) 3 * 2n 12F1111求解遞推關(guān)系式：F21FnFn 1Fn2 (n2)解：以 Fn 為系數(shù)，構(gòu)成生成函數(shù)F ( x)F ( x) F1 xF2 x2xF ( x) F1 x2F2 x3x 2 F ( x) F1 x3F2 x4(1 x x2) F ( x) F1 x (F2F1 )x 2(F3F

10、2F1 ) x3xF ( x)xx 2xABx1(x 15 )( x 15 ) x 1 5x 1 52222A111)B1( 11(2)255F ( x)1 () x ( 22 )x 25其中151522Fn1 (nn )5Fn1(15) nn5212分治法的三個步驟是什么？給出使用 SPARKS語言描述的分治策略抽象化控制。答 : 分治法的三個步驟是 : 分解 解決 合并用 SPARKS語言描述的分治策略抽象化控制為 :Procedure DANDC(p,q)Global n,A(1:n);integer m,p,q;If SMALL(p,q)Then return(G(p,q)Else m

11、 DIVIDE(p,q)Return(COMBINE(DANDC(p,m), DANDC(m+1,q)EndifEnd DANDC13根據(jù)教材中所給出的二分檢索策略，寫一個二分檢索的遞歸過程。Procedure BINSRCH(A, low, high, x, j)integer midif lowhigh thenmid(lowhigh) / 2if x=A(mid) then j mid; endifif x>A(mid) then BINSRCH(A, mid+1, high, x, j); endif if x<A(mid) then BINSRCH(A, low, mid

12、-1, x, j); endifelse j0; endifend BINSRCH14作一個“三分”檢索算法。它首先檢查 n/3 處的元素是否等于某個 x 的值，然后檢查 2n/3 處的元素；這樣，或者找到 x，或者把集合縮小到原來的 1/3 。分析此算法在各種情況下的計算復(fù)雜度。Procedure ThriSearch(A, x, n, j)integer low, high, p1, p2low 1; high nwhile lowhigh dop1( 2lowhigh) / 3; p2(low2high) / 3case:x=A(p1): j:x=A(p2): j:x<A(p1):

13、 high:x>A(p2): low:else:lowp1; returnp2; returnp1-1p2+1p1+1; highp2-1end caserepeatj 0end ThriSearchg (n)n足夠小T(n)=f (n)T (n / 3)否則g(n)= O(1)f(n)= O(1)成功 :O(1),O(log3(n),O(log3(n)最好，平均，最壞失敗 :O(log3(n),O(log3(n),O(log3(n)最好，平均，最壞15對于含有n 個內(nèi)部結(jié)點(diǎn)的二元樹，證明E=I+2n，其中， E， I分別為外部和內(nèi)部路徑長度。證明：數(shù)學(xué)歸納法當(dāng) n=1 時，易知 E=2

14、，I=0 ，所以 E=I+2n 成立；假設(shè) nk(k>0) 時， E=I+2n 成立；則當(dāng) n=k+1 時，不妨假定找到某個內(nèi)結(jié)點(diǎn) x 為葉結(jié)點(diǎn)（根據(jù)二元擴(kuò)展樹的定義，一定存在這樣的結(jié)點(diǎn) x，且設(shè)該結(jié)點(diǎn)的層數(shù)為 h），將結(jié)點(diǎn) x 及其左右子結(jié)點(diǎn)（外結(jié)點(diǎn)）從原樹中摘除，生成新二元擴(kuò)展樹。此時新二元擴(kuò)展樹內(nèi)部結(jié)點(diǎn)為 k 個，則滿足 Ek=I k+2k，考察原樹的外部路徑長度為Ek+1= Ek- （h-1 ）+2h，內(nèi)部路徑長度為 Ik+1=I +（h-1 ），所以 E = I+2k+h+1= I+2k+2= Ik+1+2(k+1) ，kk+1kk+1綜合知命題成立。16以比較為基礎(chǔ)（基本操作

15、）的分類算法最壞情況的時間下界是什么？答：（ n log n）17 對線性存儲的有序表中元素的以比較為基礎(chǔ)的檢索算法最壞時間的下界是什么？簡要說明理由。答：log(n1)對線性存儲的有序表中元素的以比較為基礎(chǔ)的檢索算法的執(zhí)行過程都可以用二元判定樹來描述。 該樹的每個內(nèi)結(jié)點(diǎn)表示一次元素比較， 因此對檢索的最壞情況而言，該樹最少含有 n 個不同的內(nèi)結(jié)點(diǎn)。 檢索算法最壞時間不大于該樹中由根到一個葉子的最長路徑長（樹高） 。對有 n 個結(jié)點(diǎn)的二元樹其最小樹高為 log(n 1) ，所以對線性存儲的有序表中元素的以比較為基礎(chǔ)的檢索算法最壞時間的下界是 log(n 1) 。18簡要說明選擇問題算法中二次取

16、中值規(guī)則的作用。答：通過選擇劃分元素 V 使其盡量靠近元素集合的中間可以得到一個最壞情況時間復(fù)雜度是 O（n）的選擇算法。使用二次取中值規(guī)則可以選出滿足要求的劃分元素 V。19給出斯特拉森矩陣乘法算法執(zhí)行時間的遞歸關(guān)系式， 并對其求解計算時間復(fù)雜度。答：斯特拉森矩陣乘法算法執(zhí)行時間的遞歸關(guān)系式為：bn2T(n)=2n27T (n / 2) an其中 a 和 b 是常數(shù)。求解這個遞歸式，得T (n) 77T (n / 4) a( n / 2) 2 an272 T (n / 4)an 2 (1 7 / 4)72 7T (n / 8)a(n / 4)2 an2 (17/4)7k T (1)an217

17、/4 (7/4)2.(7 / 4) k 1 7kan 2 ( 7 / 4) k1/(7/4 1)(c1)7 k(c1)nlog 7O(nlog 7 )O(n 2. 81)20通過手算證明（ 4.9 ）和 (4.10)式確實(shí)能得到 C11,C 12,C21 和 C22 的正確值。P=(A +A)(B11+B )T=(A11+A )B2211222212Q=(A21+A22)B11U=(A21-A11)(B 11+B12)R=A (B12-B )V=(A12-A22)(B+B )11222122S=A22(B21-B11)C11=P+S-T+V=(A11+A22)(B 11+B22) +A 22(

18、B21-B11) -(A11+A12)B22 +(A 12-A22)(B 21+B22)=A11B11+A22B11+A11B22+A22B22+A22B21-A 22B11-A11B22-A12B22+A12B21+A12B22-A22B21-A22B22 =A11B11 +A12B21= A11B12-A11B22 +A11B22+A12B22= A11B12 +A12B22= A21B11+A22B11 +A22B21-A22B11= A21B11 +A22B21C22=P+R-Q+U=(A11+A22)(B 11+B22)+A11(B12+B22)-(A 21+A22)B11 +(A

19、21-A11)(B 11+B12)=A11B11+A22B11+A11B22+A22B22+A11B12-A11B22-A21B11-A22B11+A21B11+A21B12 -A11B11-A 11B12=A22B22+A21B1221過程 MERGESORT的最壞情況時間是O(nlogn) ，它的最好情況時間是什么？能說歸并分類的時間是 (nlogn) 嗎？最好情況：是對有序文件進(jìn)行排序。分析：在此情況下歸并的次數(shù)不會發(fā)生變化-log(n)次歸并中比較的次數(shù)會發(fā)生變化（兩個長n/2 序列歸并）最壞情況兩個序列交錯大小，需要比較n-1 次最好情況一個序列完全大于 / 小于另一個序列，比較 n

20、/2 次差異都是線性的，不改變復(fù)雜性的階因此最好情況也是nlogn,平均復(fù)雜度 nlogn ?？梢哉f歸并分類的時間是(nlogn)22寫一個“由底向上”的歸并分類算法，從而取消對棧空間的利用。答：見數(shù)據(jù)結(jié)構(gòu)算法 MPass（R，n，1ength X）MP1 初始化 i1 MP2 合并相鄰的兩個長度為length的子文件 WHILE i n 2*length + 1 DO（ Merge（R，i ，i length l ，i 2*length 1X）.ii 2*length） MP3 處理余留的長度小于2*length的子文件 IFi+length1 < n算法THENMerge （R，i

21、，i+length 1， n. X ）ELSEFOR j = i TO n DO XjRjMSort(R，n) /直接兩路合并排序算法，X 是輔助文件，其記錄結(jié)構(gòu)與 R相同MS1 初始化 length1 MS2 交替合并 WHILE length < n DO（ MPass（R，n，length X） .length2*lengthif length > nthen FOR j = 1 TO n DO Rjelse MPass（X，n，lengthlength2*length ）endifR）.Xj) 23什么是約束條件？什么是可行解？什么是目標(biāo)函數(shù)？什么是最優(yōu)解？并舉例說明。答：

22、有一類問題， 解由輸入的某個子集組成， 但是這個子集必須滿足某些事先給定的條件。那些必須滿足的條件稱為約束條件。滿足約束條件的子集稱為可行解。為了衡量可行解的優(yōu)劣， 事先也給出一定的標(biāo)準(zhǔn)， 這些標(biāo)準(zhǔn)一般以函數(shù)形式給出，稱為目標(biāo)函數(shù)。使目標(biāo)函數(shù)取極值的可行解稱為最優(yōu)解。26什么是貪心方法 ? 給出使用 SPARKS語言描述的貪心方法的抽象化控制。答：對求取最優(yōu)解問題，選取一種度量標(biāo)準(zhǔn)，將輸入按度量標(biāo)準(zhǔn)排序，并按此序一次輸入一個量。如果這個輸入和前面輸入產(chǎn)生的在這種度量意義下的部分最優(yōu)解加在一起產(chǎn)生一個可行解，將其加入形成新的在這種度量意義下的部分最優(yōu)解；若不能構(gòu)成一個可行解，則去掉該輸入；重復(fù)此

23、過程直到將輸入枚舉完成。這種能夠得到某種度量意義下的最優(yōu)解的分級處理方法稱為貪心方法。貪心方法的 SPARKS語言描述的抽象化控制為：Procedure GREEDY(A,n)soltionfor i1 to n doxSELECT(A)if FEASIBLE(soltion,x)then soltionUNION(soltion,x)endifrepeatreturn(soltion)end GREEDY24 求以下情況背包問題的最優(yōu)解， n=7，m=15，（p1,.p7）=(10,5,15,7,6,18,3)和（w1 ,.w7）=(2,3,5,7,1,4,1)。 將以上數(shù)據(jù)情況的背包問題記

24、為I 。設(shè) FG(I) 是物品按 pi 的非增次序輸入時由 GREEDY-KNAPSACK所生成的解， FO(I) 是一個最優(yōu)解。問 FO(I)/ FG(I) 是多少 ? 當(dāng)物品按 wi 的非降次序輸入時，重復(fù)的討論。解：按照 pi / wi 的非增序可得( p5 / w5 ， p1 / w1 ， p6 / w6 ， p3 / w3 ， p7 / w7 ， p2 / w2 ， p4 / w4 )= (6,5,9/2,3,3,5/3,1)W的次序為 (1,2,4,5,1,3,7),解為 (1,1,1,1,1,2/3,0)所以最優(yōu)解為：（1,2/3,1,0,1,1,1）FO(I)=166/3 按照

25、 Pi 的非增次序輸入時得到( p6 , p3 , p1 , p4 , p5 , p2 , p7 )= (18,15,10,7,6,5,3)，對應(yīng)的 ( w6, w3 , w1 , w4 , w5 , w2 , w7 )= (4,5,2,7,1,3,1)解為 (1,1,1,4/7,0,0,0)所以 FG(I) 的解為（ 1,0,1,4/7,0,1,0）FG(I)=47 ，所以 FO(I)/ FG(I)=166/141. 按照 wi 的非降次序輸入時得到( w5 , w7 , w1 , w2 , w6 , w3 , w4 )=(1,1,2,3,4,5,7)相應(yīng)的 ( p5 , p7 , p1 ,

26、 p2 , p6 , p3 , p4 )=(6,3,10,5,18,15,7)解為 (1,1,1,1,1,4/5,0)則 FW(I) 的解為（ 1,1,4/5,0,1,1,1）FW(I)=54，所以 FO(I)/ FW(I)=83/81.25（ 0/1 背包問題）如果將5.3 節(jié)討論的背包問題修改成n極大化p xii1約束條件nMxi=0或 1 1 i nw xii1這種背包問題稱為 0/1 背包問題。它要求物品或者整件裝入背包或者整件不裝入。求解此問題的一種貪心策略是：按pi / wi 的非增次序考慮這些物品，只要正被考慮的物品能裝進(jìn)的就將其裝入背包。證明這種策略不一定能得到最優(yōu)解。證明：當(dāng)

27、按照 pi / wi 的非增次序考慮物品存放背包時，如果所裝入的物品恰能裝滿背包時，易證為最優(yōu)解，否則未必是最優(yōu)解?？膳e例如下：設(shè)n=3，M=6，（ p1 ,p2 ,p3 ）=(3,4,8) ，（ w1 , w2 , w3 ）=(1,2,5) ，按照 pi/ wi 的非增序得到（p1 / w1 ,p2 / w2 , p3 / w3 ）=(3,2,1.6) ，則其解為（ 1,1,0 ），而事實(shí)上最優(yōu)解是(1,0,1)，問題得證。26假定要將長為 l1 ,l 2 , , l n 的 n 個程序存入一盤磁帶，程序i 被檢索的頻率是 f i 。如果程序按 i1 ,i 2 , , i n 的次序存放，則

28、期望檢索時間（ERT）是njn( f i jl ik ) /fij1k 1i 1 證明按l i 的非降次序存放程序不一定得到最小的ERT。 證明按f i 的非增次序存放程序不一定得到最小的ERT。 證明按f i / l i 的非增次序來存放程序時ERT取最小值。證明：只需證明結(jié)論是正確的即可，現(xiàn)證明如下：假 設(shè)l i1,li 2, ,l in按 照fi/l i的 非 增 次 序 存 放 ， 即fi1 / l i1 fi2/ li2 f in/ lin，則得到ERT= fi1nl i1 + fi2 ( l i1+li2 )+ +f in ( li1+ li2+l in /fii 1假設(shè)該問題的一

29、個最優(yōu)解是按照j1 ,j 2 , , jn 的順序存放，并且其期望檢索式件是 ERT，我們只需證明 ERT ERT ，即可證明按照 f i/ l i 的非增次序存放得到的是最優(yōu)解。易知nERT=+f j2(l j1+l)+ +(l j 1+)/fif j1 l j1j2f jnl j 2l jni 1從前向后考察最優(yōu)解中的程序， 不妨設(shè)程序 j k 是第一個與其相鄰的程序 j k 1存在關(guān)系 f j k / l jk f jk1 /l jk 1，則交換程序 j k和程序 j k1 ，得到的期望檢索時間記為 ERTERT -ERT = f jkl jk1 - f jk 1l jk 0ERT ER

30、T顯然 ERT 也是最優(yōu)解，將原來的最優(yōu)解中所有這樣類似于反序?qū)Φ某绦蚧Q位置，得到的解不比原來的最優(yōu)解差，所以最終變換后得到的解也是最優(yōu)解，而最終的解恰是程序按f i / l i 的非增次序來存放得到的順序。命題得證。27. 假定要把長為 l 1 , l 2 , , l n 的 n 個程序分布到兩盤磁帶 T1 和 T2 上，并且希望按照使最大檢索時間取最小值的方式存放， 即，如果存放在 T1 和 T2 上的程序集合分別是 A 和 B，那么就希望所選擇的A 和一種得到 A 和 B 的貪心方法如下： 開始將個程序，如果i A l i =min i A l i ,i B liB 使得 maxl i

31、 ,i Bl i 取最小值。i AA 和 B 都初始化為空，然后一次考慮一 ，則將當(dāng)前正在考慮的那個程序分配給 A，否則分配給 B。證明無論是按 l 1 l 2 l n 或是按 l 1 l 2 l n 的次序來考慮程序，這種方法都不能產(chǎn)生最優(yōu)解。證明：按照 l1 l 2 l n 存放不會得到最優(yōu)解，舉例如下：3 個程序（ a,b,c ）長度分別為（ 1,2,3 ），根據(jù)題中的貪心算法，產(chǎn)生的解是 A=a,cB=b ，則 maxli,i B l i =4 ，而事實(shí)上，最優(yōu)解應(yīng)為，所以i A3得證 .按照 l1 l 2 l n 的次序存放也不會得到最優(yōu)解，舉例如下：5 個程序（ a,b,c,d,e

32、）長度分別為（ 10,9,8,6,4）根據(jù)題中的貪心算法，產(chǎn)生的解是 A=a,d,eB=b,c，則 maxi A l i ,i B l i=20，而事實(shí)上， 最優(yōu)解應(yīng)為 19，所以得證。28. 當(dāng) n=7，（）和（d1,.d 7）=(1,3,4,3,2,1,2)p1 ,.p7=(3,5,20,18,1,6,30)時，算法 5.4 所生成的解是什么？ 證明即使作業(yè)有不同的處理時間定理5.3 亦真。這里，假定作業(yè) I 的效益pi>0，要用的處理時間 ti>0，限期 di ti .解：根據(jù)pi的非增排序得到(p7 , p3 , p4 ,p6 , p2, p1 ,p5)=(30,20,18

33、,6,5,3,1)，對應(yīng)的期限為(2,4,3,1,3,1,2)，按照算法 5.4 生成的解為：a.J(1)=7b.J(1)=7,J(2)=3c.J(1)=7,J(2)=4,J(3)=3d.J(1)=6, J(2)=7,J(3)=4,J(4)=3；證明：顯然即使 t i >0（ di ti ），如果 J 中的作業(yè)可以按照的次序而又不k違反任何一個期限來處理，即對次序中的任一個作業(yè)k，應(yīng)滿足 d k t j ，j1則 J 就是一個可行解。下面證明如果 J 是可行解，則使得 J 中的作業(yè)可以按照 di, di, , di排列12n的序列 處理而又不違反任何一個期限。因為 J 是可行解，則必存在

34、= r1 r2 rn ，使得對任意的 r k ，都有 d k kt j ，j 1我們設(shè) 是按照 di di2 , , di 排列的作業(yè)序列。 假設(shè)，那么令 a 是使1nr a ia 的最小下標(biāo)，設(shè) rb =ia ，顯然 b>a，在中將 ra 與 rb 相交換，因為 drb d ra ，顯然 r a 和 rb 可以按期完成作業(yè)。還要證明 r a 和 rb 之間的作業(yè)也能按期完成。因為 dr dr ，而顯然二者之間bab的所有作業(yè) rt ，都有 dr> dr ，又由于 是可行解，所以t k dr dr 。所以作tbk 1bt業(yè) ra 和 rb 交換后，所有作業(yè)可依新產(chǎn)生的排列= s1

35、s2 sn 的次序處理而不違反任何一個期限，連續(xù)使用這種方法， 就可轉(zhuǎn)換成 且不違反任何一個期限，定理得證。29 已知 n-1 個元素已按 min- 堆的結(jié)構(gòu)形式存放在A(1), ,A(n -1) ?，F(xiàn)要將另一存放在A(n) 的元素和A(1:n-1) 中元素一起構(gòu)成一個具有n 個元素的 min-堆。對此寫一個計算時間為O(logn) 的算法。 在 A(1:n) 中存放著一個 min- 堆，寫一個從堆頂 A(1) 刪去最小元素后將其余元素調(diào)整成 min- 堆的算法，要求這新的堆存放在 A(1:n-1) 中，且算法時間為 O(logn). 利用所寫出的算法， 寫一個對 n 個元素按非增次序分類的堆

36、分類算法。分析這個算法的計算復(fù)雜度。解： procedure INSERT(A,n) integer i, j, kj n ; i n/2while i 1 and Ai>Aj dokAj;Aj Ai;Ai kji ;i i/2repeatend INSERT procedure RESTORE(A,l,n) integer i, j, kxAn;An Ali 1j 2*iwhile jn-1 doif (j< n-1) and (Aj> Aj+1)then jj+1endifif (x>Aj)then AiAj; ij;j2*ielse inendifrepeaten

37、d RESTORE procedure HEAPSORT(A,n) integer i, kfor i=n/2 to 1 step 1 doRESTORE(A, i, n)repeatfor i=n to 2 step 1 dokA1; A1 Ai; Ai kRESTORE(A, 1, i-1)repeatend HEAPSORT30 證明如果一棵樹的所有內(nèi)部節(jié)點(diǎn)的度都為k，則外部節(jié)點(diǎn)數(shù)n 滿足n mod(k-1)=1. 證明對于滿足 n mod (k-1)=1的正整數(shù) n，存在一棵具有n 個外部節(jié)點(diǎn)的 k 元樹 T( 在一棵 k 元樹中，每個節(jié)點(diǎn)的度至多為k) 。進(jìn)而證明 T 中所有內(nèi)部節(jié)點(diǎn)

38、的度為 k.證明：設(shè)某棵樹內(nèi)部節(jié)點(diǎn)的個數(shù)是m，外部結(jié)點(diǎn)的個數(shù)是n，邊的條數(shù)是 e，則有e=m+n-1和e=mkmk=m+n-1(k-1)m=n-1n mod (k-1)=1 利用數(shù)學(xué)歸納法。當(dāng) n=1 時，存在外部結(jié)點(diǎn)數(shù)目為1 的k 元樹T，并且T 中內(nèi)部結(jié)點(diǎn)的度為k；假設(shè)當(dāng) n m，且滿足 n mod (k-1)=1時，存在一棵具有n 個外部結(jié)點(diǎn)的k 元樹 T，且所有內(nèi)部結(jié)點(diǎn)的度為k；我們將外部結(jié)點(diǎn)數(shù)為 n(n 為滿足 nm，且 n mod (k-1)=1 的最大值 ) 的符合上述性質(zhì)的樹 T 中某個外部結(jié)點(diǎn)用內(nèi)部結(jié)點(diǎn) a 替代，且結(jié)點(diǎn) a 生出 k 個外部結(jié)點(diǎn)，易知新生成的樹 T中外部結(jié)點(diǎn)

39、的數(shù)目為 n+(k-1) ，顯然 n 為滿足 n mod (k-1)=1 ，且比 m大的最小整數(shù)， 而樹 T每個內(nèi)結(jié)點(diǎn)的度為 k，即存在符合性質(zhì)的樹。綜合上述結(jié)果可知 , 命題成立。31 證明如果 n mod (k-1)=1 ，則在定理5.4 后面所描述的貪心規(guī)則對于所有的（ q1 , q2 , , qn ）生成一棵最優(yōu)的k 元?dú)w并樹。 當(dāng)（ q1 , q2 , , q11 ）=（3,7,8,9,15,16,18,20,23,25,28）時，畫出使用這一規(guī)則所得到的最優(yōu)3 元?dú)w并樹。解：通過數(shù)學(xué)歸納法證明：對于 n=1，返回一棵沒有內(nèi)部結(jié)點(diǎn)的樹且這棵樹顯然是最優(yōu)的。假定該算法對于（ q1 ,

40、q2 , , qm ），其中 m =(k-1)s+1 (0 s) ，都生成一棵最優(yōu)樹 .則只需證明對于 ( q1 , q2 , , qn ) ，其中 n=(k-1)(s+1)+1，也能生成最優(yōu)樹即可。不失一般性，假定 q1 q2 qn ，且 q1 , q2 , , qk 是算法所找到的 k 棵樹的 WEIGHT信息段的值。于是 q1 , q2 , , qk 棵生成子樹 T ，設(shè) T 是一棵對于（ q1 , q2 , , qn ）的最優(yōu) k 元?dú)w并樹。設(shè) P 是距離根最遠(yuǎn)的一個內(nèi)部結(jié)點(diǎn)。如果 P 的 k 個兒子不是 q1 , q2 , , qk ，則可以用 q1 , q2 , , qk 和 P

41、現(xiàn)在的兒子進(jìn)行交換，這樣不增加 T 的帶權(quán)外部路徑長度。 因此 T 也是一棵最優(yōu)歸并樹中的子樹。于是在 T 中如果用其權(quán)為 q1+q2+qk 的一個外部結(jié)點(diǎn)來代換 T ，則所生成的樹 T 是關(guān)于 ( q1 + q2 +qk , q k 1 , , qn ) 的一棵最優(yōu)歸并樹。由歸納假設(shè)，在使用其權(quán)為 q1 + q2 + qk 的那個外部結(jié)點(diǎn)代換了 T 以后，過程 TREE轉(zhuǎn)化成去求取一棵關(guān)于 ( q1 + q2 + qk , qk 1 , , qn ) 的最優(yōu)歸并樹。 因此 TREE生成一棵關(guān)于 ( q1 , q2 , , qn ) 的最優(yōu)歸并樹。32對 n=7,(p1 ,., p7 )=(35 ，30，25，20， 15，10，5) 和(d1 ,.,d7 )=(4 ，2，4，3，4，8，3) 的有限期作業(yè)調(diào)度問題使用教材中作業(yè)排序的更快算法求解最優(yōu)解。（要求描述時間片數(shù)組 F（i ）和對應(yīng)集合的變化過程）33當(dāng)作業(yè)數(shù) n7，（ p1，p2， p7）（ 7, 6, 5, 4, 3