《計(jì)算機(jī)算法基礎(chǔ)》第三版_課后習(xí)題答案

上機(jī)實(shí)驗(yàn) 書上 121 頁 5。 2 5。 3 書上 151 6。 1 6。 3 6。 6 他說搞懂這幾題和實(shí)驗(yàn)就沒問題了 T(n)= ()2 ( / 2 ) ( )n f n否則足夠小n 當(dāng) n=2k g(n)= O(1)和 f(n)= O(n)； n=2k g(n)= O(1)和 f(n)= O(1)。 解 : T(n)=T(2k)=2 T(2f(2k)=2(2 T(2f(2 +f(2k) =22T(221 f(2 f(2k) = =2)+2)+22)+2 0f(2k) =2kg(n)+ 2)+22)+2 0f(2k) 當(dāng) g(n)= O(1)和 f(n)= O(n)時(shí)， 不妨設(shè) g(n)=a， f(n)=a， 則 T(n)=T(2k)= 22b+22b+2 0*22ka+ =an+O( 當(dāng) g(n)= O(1)和 f(n)= O(1)時(shí)， 不妨設(shè) g(n)=c， f(n)=d， c， 則 T(n)=T(2k)=2+2 0d=d(2=(c+d)O(n) 一個(gè)二分檢索的遞歸過程。 , x, j) if 2/)( if x=A(j if xA(, , x, j); if xA( : ; j 0 (n)= )()3/()( 否則足夠小n g(n)= O(1) f(n)= O(1) 成功 : O(1), O(n), O(n) 最好， 平均， 最壞 失敗 : O(n), O(n), O(n) 最好， 平均， 最壞 于含有 n 個(gè)內(nèi)部結(jié)點(diǎn)的二元樹，證明 E=I+2n，其中， E， I 分別為外部和內(nèi)部路徑長度。 證明：數(shù)學(xué)歸納法 當(dāng) n=1時(shí)，易知 E=2， I=0，所以 E=I+2n 成立； 假設(shè) n k(k0)時(shí)， E=I+2 則當(dāng) n=k+1 時(shí)，不妨假 定 找到 某個(gè)內(nèi)結(jié)點(diǎn) x 為葉結(jié)點(diǎn)（根據(jù)二元擴(kuò)展樹的定義，一定存在這樣的結(jié)點(diǎn) x，且設(shè)該結(jié)點(diǎn)的層數(shù) 為 h），將結(jié)點(diǎn) 結(jié)點(diǎn)）從原樹中摘除， 生成 新二元擴(kuò)展樹 。 此時(shí)新二元擴(kuò)展樹內(nèi)部結(jié)點(diǎn)為 k 個(gè)，則滿足 k+2k，考察原樹的外部路徑長度為 = +2h，內(nèi)部路徑長度為 = ，所以 = k+h+1= +2k+2= +2(k+1)， 綜合 知 命題成立。 最壞情況時(shí)間是 O( 它的最好情況時(shí)間是什么 ？能說歸并分類的時(shí)間是 ( ？ 最好情況 ： 是 對有序文件進(jìn)行排序 。 分析 ：在此情況下 歸并的次數(shù)不會發(fā)生變化 n)次 歸并中比較的次數(shù)會發(fā)生變化（兩個(gè)長 n/2序列歸并） 最壞情況 兩個(gè)序列交錯(cuò)大小 ， 需要比較 最好情況 一個(gè)序列完全大于 /小于另一個(gè)序列 ， 比較 n/2次 差異都是線性的，不改變復(fù)雜性的階 因此 最好情況也是 平均復(fù)雜度 可以說 歸并分類的時(shí)間是 ( 由底向上 ” 的歸并分類算法，從而取消對?？臻g的利用。 答： 見數(shù)據(jù)結(jié)構(gòu) 算法 R， n， 1X） 初始化 i1 合并相鄰的兩個(gè)長度為 子文件 i n 2* 1 R， i， i l， i 2*1 X） . ii 2* 處理余留的長度小于 2*子文件 i+1 n j = 1 n Xj X， n， R） . * (確實(shí)能得到 12,22的正確值。 P=(22)(22) T=(12)=(22) U=(12) R=12 V=(22) S=21+ =(22)(22) +21-(12)(22) =22112222121212=R+T = 12 21=Q+S = 22 22=P+ =(22)(22)+12+(22)(12) =22112211212121 求以下情況背包問題的最優(yōu)解， n=7， m=15， ）（71 ,. 10,5,15,7,6,18,3)和 ）（71 ,. 2,3,5,7,1,4,1)。 將以上數(shù)據(jù)情況的背包問題記為 I。設(shè) )是物品按生成的解， )是一個(gè)最優(yōu)解。問 )/ )是多少 ? 當(dāng)物品按復(fù) 的討論。 解： 按照ip/(5p/5w， 1p / 1w ，6p/6w，3p/3w，7p/7w， 2p / 2w ， 4p / 4w ) = (6,5,9/2,3,3,5/3,1) 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） )=166/3 按照 到 (6p,3p, 1p , 4p ,5p, 2p ,7p)= (18,15,10,7,6,5,3)， 對應(yīng)的 (6w,3w, 1w , 4w ,5w, 2w ,7w)= (4,5,2,7,1,3,1) 解為 (1,1,1,4/7,0,0,0) 所以 )的解為（ 1,0,1,4/7,0,1,0） )=47，所以 )/ )=166/141. 按照到 (5w,7w, 1w , 2w ,6w,3w, 4w )=(1,1,2,3,4,5,7) 相應(yīng)的 (5p,7p, 1p , 2p ,6p,3p, 4p )=(6,3,10,5,18,15,7) 解為 (1,1,1,1,1,4/5,0) 則 )的解為（ 1,1,4/5,0,1,1,1） )=54，所以 )/ )=83/81. 0/1背包問題）如果將 極大化 約束條件 M 或 1 1in 這種背包問題稱為 0/1背包問題。它要求物品或者整件裝入背包或者整件不裝入。求解此問題的一種貪心策略是：按ip/要正被考慮的物品能裝進(jìn)的就將其裝入背包。證明這種策略不一定能得到最優(yōu)解。 證明：當(dāng)按照ip/如果所裝入的物品恰能裝滿背包時(shí)，易證為最優(yōu)解，否則未必是最優(yōu)解。 可舉例如下：設(shè) n=3， M=6，（ 1 p , 2p , 3p） =(3,4,8)，（ 1 w , 2w , 3w）=(1,2,5)，按照ip/1p / 1w , 2p / 2w , 3p/3w） =(3,2,則其解為（ 1,1,0），而事實(shí)上最優(yōu)解是 (1,0,1)，問題得證。 假定要將長為 1l ,2l , n 個(gè)程序存入一盤磁帶，程序 i 被檢索的頻率是果程序按 1i ,2i , 期望檢索時(shí)間（ ni jk ii 1 1 /)( 證明按 證明按 證明按if/最小值。 證明：只需證明結(jié)論 是正確的即可，現(xiàn)證明如下： 假設(shè)1, 1得到 1+ + ni j , 2j , 且其期望檢索式件是 ，我們只需證明 ，即可證明按照if/知 =1+ + ni 妨設(shè)程序交換程序到的期望檢索時(shí)間記為 - =0 顯然 也是最優(yōu)解，將原來的最優(yōu)解中所有這樣類似于反序?qū)Φ某绦蚧Q位置，得到的解不比原來的最優(yōu)解差，所以最終變換后得到的解也是最優(yōu)解，而最終的解恰是程序按if/題得證。 l ,2l , T 和 2T 上，并且希望按照使最大檢索時(shí)間取最小值的方式存放，即，如果存放在 1T 和 2T 上的程序集合分別是 ，那么就希望所選擇的 使得 Ai Bi 最小值。一種得到 的貪心方法如下：開始將 都初始化為空，然后一次考慮一個(gè)程序，如果 Ai il=Ai Bi 則將當(dāng)前正在考慮的那個(gè)程序分配給 A，否則分配給 B。證明無論是按 1l 2l l 2l 種方法都不能產(chǎn)生最優(yōu)解。 證明：按照 1l 2l 例如下： 3 個(gè)程序（ a,b,c）長度分別為（ 1,2,3），根據(jù)題中的貪心算法，產(chǎn)生的解是 A=a,cB=b，則 Ai Bi 4，而事實(shí)上，最優(yōu)解應(yīng)為 3，所以得證 . 按照 1l 2l 例如下： 5 個(gè)程序（ a,b,c,d,e）長度分別為（ 10,9,8,6,4）根據(jù)題中的貪心算法，產(chǎn)生的解是 A=a,d,eB=b,c，則 Ai Bi 20，而事實(shí)上，最優(yōu)解應(yīng)為 19，所以得證。 當(dāng) n=7， ）（71 ,. 3,5,20,18,1,6,30) 和 ）（71 ,. 1,3,4,3,2,1,2)時(shí)，算法 證明即使作業(yè)有不同的處理時(shí)間定理 里，假定作業(yè) ，要用的處理時(shí)間，限期id解： 根據(jù) 增 排 序 得 到(7p,3p, 4p ,6p, 2p , 1p ,5p)=(30,20,18,6,5,3,1) ，對應(yīng)的期限為(2,4,3,1,3,1,2)，按照算法 )=7 )=7,J(2)=3 )=7,J(2)=4,J(3)=3 )=6, J(2)=7,J(3)=4,J(4)=3； 證明：顯然即使（id如果 J 中的作業(yè)可以按照 的次序而又不違反任何一個(gè)期限來處理，即對 次序中的任一個(gè)作業(yè) k，應(yīng)滿足kj 下面證明如果 J 是可行解，則使得 , 處理而又不違反任何一個(gè)期限 。 因?yàn)?必存在 =1r 2r 得對任意的有kj 們設(shè) 是按照1,設(shè) ，那么令 br=然 ba，在 中將為然 還要證明為顯然二者之間的所有作業(yè)有由于 是可行解，所以 bk 以作業(yè)有作業(yè)可依新產(chǎn)生的排列 =1s 2s 續(xù)使用這種方法， 就可轉(zhuǎn)換成 且不違反任何一個(gè)期限，定理得證。 已知 (1),A(n 現(xiàn)要將另一存放在 A(n)的元素和 A(1:元素一起構(gòu)成一個(gè)具有 n 個(gè)元素的 此寫一個(gè)計(jì)算時(shí)間為 O(算法。 在 A(1:n)中存放著一個(gè) 一個(gè)從堆頂 A(1)刪去最小元素后將其余元素調(diào)整成 求這新的堆存放在 A(1:，且算法時(shí)間為 O( 利用 所寫出的算法，寫一個(gè)對 析這個(gè)算法的計(jì)算復(fù)雜度。 解： ,n) i, j, k j n ; i n/2 i 1 iAj do k Aj; Aj Ai; Ai k j i ; i i/2 ,l,n) i, j, k x An; An Al i 1 j 2*i j j Aj+1) j j+1 xAj) i Aj; i j;j 2*i i n ,n) i, k i= n/2 1 , i, n) i=n 1 k A1; A1 Ai; Ai k , 1, 證明如果一棵樹的所有內(nèi)部節(jié)點(diǎn)的度都為 k，則外部節(jié)點(diǎn)數(shù) n 1. 證明對于滿足 n 1 的正整數(shù) n，存在一棵具有 n 個(gè)外部節(jié)點(diǎn)的 k 元樹 T(在一棵 k 元樹中，每個(gè)節(jié)點(diǎn)的度至多為 k)。進(jìn)而證明 T 中所有內(nèi)部節(jié)點(diǎn)的度為 k. 證明： 設(shè)某棵樹內(nèi)部節(jié)點(diǎn)的個(gè)數(shù)是 m，外部結(jié)點(diǎn)的個(gè)數(shù)是 n，邊的條數(shù)是 e，則有 e=m+ e=mk mk=m+ (m= n 1 利用數(shù)學(xué)歸納法。 當(dāng) n=1時(shí)，存在外部結(jié)點(diǎn)數(shù)目為 1的 k 元樹 T，并且 假設(shè)當(dāng) n m，且滿足 n 1 時(shí)，存在一棵具有 n 個(gè)外部結(jié)點(diǎn)的，且所有內(nèi)部結(jié)點(diǎn)的度為 k； 我們將外部結(jié)點(diǎn)數(shù) 為 n(n m，且 n 1的最大值 )的符合上述性質(zhì)的樹 結(jié)點(diǎn) 知新生成的樹 T 中外部結(jié)點(diǎn)的數(shù)目為 n+(顯然 n 為滿足 n 1，且比 樹 T 每個(gè)內(nèi)結(jié)點(diǎn)的度為 k， 即 存在符合性質(zhì)的樹。 綜合上述結(jié)果可知 ,命題 成立 。 證明如果 n 1，則在定理 面所描述的貪心規(guī)則對于所有的（ 1q , 2q , 成一棵最優(yōu)的 當(dāng)（ 1q , 2q , 11q ） =（ 3,7,8,9,15,16,18,20,23,25,28）時(shí)，畫出使用這一規(guī)則所得到的最優(yōu) 3元?dú)w并樹。 解： 通過數(shù)學(xué)歸納法證明： 對于 n=1，返回一棵沒有內(nèi)部結(jié)點(diǎn)的樹且這棵樹顯然是最優(yōu)的。 假定該算法對于（ 1q , 2q , 其中 m =(s+1 (0 s)，都生成一棵最優(yōu)樹 . 則只需證明對于 (1q , 2q , 其中 n=(s+1)+1，也能生成最優(yōu)樹即可。 不失一般性，假定 1q 2q 1q , 2q , 是 1q , 2q , ，設(shè) T 是一棵對于（ 1q , 2q , 最優(yōu) k 元?dú)w并樹。設(shè) P 是距離根最遠(yuǎn)的一個(gè)內(nèi)部結(jié)點(diǎn)。如果 P的 q , 2q , 可以用 1q , 2q , 現(xiàn)在的兒子進(jìn)行交換，這樣不增加 T 的帶權(quán)外部路徑長度。因此 T 也是一棵最優(yōu)歸并樹中的子樹。于是在 T 中如果用其權(quán)為 q1+ + ，則所生成的樹 T 是關(guān)于 (1q + 2q + + ,一棵最優(yōu)歸并樹。由歸納假設(shè)，在使用其權(quán)為 1q + 2q + + 以后，過程 化成去求取一棵關(guān)于 (1q + 2q + + ,最優(yōu)歸并樹。因此 q , 2q , 最優(yōu)歸并樹。 改過程 其輸出每對結(jié)點(diǎn)（ i,j）間的最短路徑，這個(gè)新算法的時(shí) 間和空間復(fù)雜度是多少？ n, A, i , j, k n, n), A(n, n), n, n), i 1 to n j 1 to n A(i ,j) i ,j) if i j (i, j) i, j ) j i, j) 0 k 1 to n i 1 to n j 1 to n (i,j)A(i,k)+A(k,j) (i,j) A(i,k)+A(k,j) i,j) i,k) i 1 to n j 1 to n do of i to j i ) k i, j) k 0 ,k) k k, j) 間復(fù)雜度 O(空間復(fù)雜度 O( 證明算法 計(jì)算時(shí)間是 O( 在已知根 R(i, j)， 0 i j 4 的情況下寫一個(gè)構(gòu)造最優(yōu)二分檢索樹 明這樣的樹能在 O(n)時(shí)間內(nèi)構(gòu)造出來。 解： 將 C 中元素的加法看做基本運(yùn)算，則算法 時(shí)間復(fù)雜性為： 20( ( 1 , ) ( , 1 ) 1 )n n i j R i j 20( ( , ) ( , 1 ) 1 )n n i i m R i i m 2( ( 1 , ) ( 0 , 1 ) 1 )n m n R m n m O( m, n, R, (n,n),