計算機(jī)算法基礎(chǔ)第三版_課后習(xí)題答案-閱讀頁
2025-07-08 17:33本頁面
【正文】 ORT(A,n) integer i, k for i= to 1 step –1 do RESTORE(A, i, n) repeat for i=n to 2 step –1 do k←A[1]。 A[i]←k RESTORE(A, 1, i1) repeat end HEAPSORT．① 證明如果一棵樹的所有內(nèi)部節(jié)點的度都為k，則外部節(jié)點數(shù)n滿足n mod (k1)=1.② 證明對于滿足 n mod (k1)=1的正整數(shù)n，存在一棵具有n個外部節(jié)點的k元樹T(在一棵k元樹中，每個節(jié)點的度至多為k)。 (k1)m=n1 222。當(dāng)n=1時，存在外部結(jié)點數(shù)目為1的k元樹T，并且T中內(nèi)部結(jié)點的度為k；假設(shè)當(dāng) n≤m，且滿足n mod (k1)=1時，存在一棵具有n個外部結(jié)點的k元樹T，且所有內(nèi)部結(jié)點的度為k；我們將外部結(jié)點數(shù)為n(n為滿足n≤m，且n mod (k1)=1的最大值)的符合上述性質(zhì)的樹T中某個外部結(jié)點用內(nèi)部結(jié)點a替代，且結(jié)點a生出k個外部結(jié)點，易知新生成的樹T’中外部結(jié)點的數(shù)目為n+(k1)，顯然n為滿足n mod (k1)=1，且比m大的最小整數(shù)，而樹T’每個內(nèi)結(jié)點的度為k，即存在符合性質(zhì)的樹。．① 證明如果n mod (k1)=1，（,…, ）生成一棵最優(yōu)的k元歸并樹。解：①通過數(shù)學(xué)歸納法證明：對于n=1，返回一棵沒有內(nèi)部結(jié)點的樹且這棵樹顯然是最優(yōu)的。不失一般性，假定≤≤…≤，且,…, 是算法所找到的k棵樹的WEIGHT信息段的值。設(shè)P是距離根最遠(yuǎn)的一個內(nèi)部結(jié)點。因此也是一棵最優(yōu)歸并樹中的子樹。由歸納假設(shè)，在使用其權(quán)為++…+的那個外部結(jié)點代換了以后，過程TREE轉(zhuǎn)化成去求取一棵關(guān)于(++…+,…,)的最優(yōu)歸并樹。．修改過程ALL_PATHS，使其輸出每對結(jié)點（i,j）間的最短路徑，這個新算法的時間和空間復(fù)雜度是多少？ Procedure ShortestPath(COST, n, A, Max)integer i , j, kreal COST(n, n), A(n, n), Path(n, n), Maxfor i←1 to n do for j←1 to n do A(i ,j)←COST(i ,j) if i≠j and A(i, j)≠Max then Path(i, j )←j else Path(i, j)←0 endif repeatrepeatfor k←1 to n do for i←1 to n do for j←1 to n do if A(i,j)A(i,k)+A(k,j)then A(i,j)←A(i,k)+A(k,j) Path(i,j)←Path(i,k)endif repeat repeatrepeatfor i←1 to n do for j←1 to n do print(“the path of i to j is ” i ) k←path(i, j) while k≠0 do print( ,k) k←path(k, j) repeat repeatrepeat end ShortestPath時間復(fù)雜度O(n3)，空間復(fù)雜度O(n2) ．①證明算法OBST的計算時間是O(n2)。證明這樣的樹能在O(n)時間內(nèi)構(gòu)造出來。．給出一個使得DKNAP()出現(xiàn)最壞情況的例子，它使得|Si|=2i, 0≤in。解：取(P1,P2,…,Pi,…)=(W1,W2,…,Wi,…)=(20,21,…,2i1,…)P和W取值相同，使支配原則成立，也就是說不會因為支配原則而刪除元素；只要說明不會出現(xiàn)相同元素被刪除一個的情形，即可知是最壞的情況。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1