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

2、= O(maxg1(n), g2(n)證明：根據f1(n)=O(g1(n)可知，存在正常數(shù)C1，當nn0時，使得|f1(n)|C1|g1(n)|；同理，根據f2(n)= O(g2(n)可知，存在正常數(shù)C2，當nn0時，使得|f2(n)|C2|g2(n)| 當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)=maxg1(n),g2(n)，k=1,2當nn0時，取C=（C1+C2），據定義命題得證。4如果f1(n)= (g1(n)并且f2(n)= (g2(n)

3、，下列說法是否正確？試說明之。（a） f1(n) +f2(n)= (g1(n)+ g2(n)（b） f1(n) +f2(n)= (ming1(n), g2(n)（c） f1(n) +f2(n)= (maxg1(n), g2(n)答：（a）和（c）均正確，（b）錯誤。（a）正確可以根據定義直接證得。（b）錯誤可舉反例。例：f1(n)= 2n，f2(n)=2 n2下面證明（c）正確性.根據上題已經證明f1(n)+f2(n)= O(maxg1(n),g2(n)，下面只需證明f1(n)+f2(n)= (maxg1(n), g2(n)，即存在正常數(shù)C，使得|f1(n)+f2(n)|C(maxg1(n),

4、 g2(n) 根據f1(n)= (g1(n)并且f2(n)= (g2(n) 得到，當nn0時，存在正常數(shù)C1、C2 、C3、C4C1|g1(n)|f1(n)|C3|g1(n)| C2|g2(n)|f2(n)|C4|g2(n)|不妨設maxg1(n), g2(n)= g1(n)由于|f1(n)+f2(n)|f1(n)|-|f2(n)|C1|g1(n)|-C3|g2(n)|=C|maxg1(n), g2(n)|取C|C1-C3|的正常數(shù)，由定義得f1(n)+f2(n) = (maxg1(n), g2(n)命題得證。5證明 |log2n|= O(n)證明：對于任意的正整數(shù)n，|log2n|log2（

5、n+1）|n+1|2|n|取n0=1，C=2，根據定義知命題成立。6證明 3nlog2n= O(n2)證明：對于任意的正整數(shù)n，|3nlog2n|3nlog2n|3|n2|取n0=1，C=3，根據定義知命題成立。7用數(shù)學歸納法證明：當n1時，.證明：當n=1時，n(n+1)/2=1，命題成立； 假設n=k-1時，成立;（k2） 當n=k時，=k(k+1)/2綜上可知，命題成立。8在下列情況下求解遞歸關系式 T(n)= 當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(2k-1)+f(2k)=2(2

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

7、。則 T(n)=T(2k)=c2k+ 2k-1d+2k-2d+20d=c2k+d(2k-1)=(c+d)n-d= O(n)9求解遞推關系式： 解：構造生成函數(shù)求解 分解成冪級數(shù)令 則A=-1 B=1 所以10求解遞推關系式：解：11求解遞推關系式： 解：以為系數(shù)，構成生成函數(shù) 其中 12分治法的三個步驟是什么？給出使用SPARKS語言描述的分治策略抽象化控制。答:分治法的三個步驟是: 分解 解決 合并用SPARKS語言描述的分治策略抽象化控制為:Procedure DANDC(p,q)Global n,A(1:n);integer m,p,q;If SMALL(p,q)Then return(

8、G(p,q)Else mDIVIDE(p,q)Return(COMBINE(DANDC(p,m), DANDC(m+1,q) Endif End DANDC13根據教材中所給出的二分檢索策略，寫一個二分檢索的遞歸過程。Procedure BINSRCH(A, low, high, x, j)integer midif lowhigh then mid if x=A(mid) then jmid; endifif xA(mid) then BINSRCH(A, mid+1, high, x, j); endifif xA(mid) then BINSRCH(A, low, mid-1, x, j

9、); endifelse j0; endifend BINSRCH14作一個“三分”檢索算法。它首先檢查n/3處的元素是否等于某個x的值，然后檢查2n/3處的元素；這樣，或者找到x，或者把集合縮小到原來的1/3。分析此算法在各種情況下的計算復雜度。 Procedure ThriSearch(A, x, n, j)integer low, high, p1, p2low1; highnwhile lowhigh do p1 ; p2 case :x=A(p1): jp1; return :x=A(p2): jp2; return :xA(p2): lowp2+1:else: lowp1+1; h

10、ighp2-1 end caserepeatj0end ThriSearchT(n)= 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個內部結點的二元樹，證明E=I+2n，其中，E，I分別為外部和內部路徑長度。證明：數(shù)學歸納法當n=1時，易知E=2，I=0，所以E=I+2n成立；假設nk(k0)時，E=I+2n成立；則當n=k+1時，不妨假定找到某個內結點x為葉結點（根據二元擴展樹的定義，一定存在這樣的結點x，且設該結點的層數(shù)為h

11、），將結點x及其左右子結點（外結點）從原樹中摘除，生成新二元擴展樹。此時新二元擴展樹內部結點為k個，則滿足Ek=Ik+2k，考察原樹的外部路徑長度為Ek+1= Ek-（h-1）+2h，內部路徑長度為Ik+1=Ik+（h-1），所以Ek+1= Ik+2k+h+1= Ik+1+2k+2= Ik+1+2(k+1)，綜合知命題成立。16以比較為基礎（基本操作）的分類算法最壞情況的時間下界是什么？答： 17對線性存儲的有序表中元素的以比較為基礎的檢索算法最壞時間的下界是什么？簡要說明理由。答： 對線性存儲的有序表中元素的以比較為基礎的檢索算法的執(zhí)行過程都可以用二元判定樹來描述。該樹的每個內結點表示一次元

12、素比較，因此對檢索的最壞情況而言，該樹最少含有n個不同的內結點。檢索算法最壞時間不大于該樹中由根到一個葉子的最長路徑長（樹高）。對有n個結點的二元樹其最小樹高為，所以對線性存儲的有序表中元素的以比較為基礎的檢索算法最壞時間的下界是。18簡要說明選擇問題算法中二次取中值規(guī)則的作用。答：通過選擇劃分元素V使其盡量靠近元素集合的中間可以得到一個最壞情況時間復雜度是O（n）的選擇算法。使用二次取中值規(guī)則可以選出滿足要求的劃分元素V。19給出斯特拉森矩陣乘法算法執(zhí)行時間的遞歸關系式，并對其求解計算時間復雜度。答：斯特拉森矩陣乘法算法執(zhí)行時間的遞歸關系式為： T(n)= 其中a和b是常數(shù)。求解這個遞歸式，

13、得20通過手算證明（4.9）和(4.10)式確實能得到C11,C12,C21和C22的正確值。P=(A11+A22)(B11+B22) T=(A11+A12)B22Q=(A21+A22)B11 U=(A21-A11)(B11+B12)R=A11(B12-B22) V=(A12-A22)(B21+B22)S=A22(B21-B11)C11=P+S-T+V=(A11+A22)(B11+B22) +A22(B21-B11) -(A11+A12)B22 +(A12-A22)(B21+B22)=A11B11+A22B11+A11B22+A22B22+A22B21-A22B11-A11B22-A12B22

14、+A12B21+A12B22-A22B21-A22B22=A11B11 +A12B21C12=R+T= A11B12-A11B22 +A11B22+A12B22= A11B12 +A12B22C21=Q+S= A21B11+A22B11 +A22B21-A22B11= A21B11 +A22B21C22=P+R-Q+U=(A11+A22)(B11+B22)+A11(B12+B22)-(A21+A22)B11 +(A21-A11)(B11+B12)=A11B11+A22B11+A11B22+A22B22+A11B12-A11B22-A21B11-A22B11+A21B11+A21B12-A11B

15、11-A11B12=A22B22+A21B1221過程MERGESORT的最壞情況時間是O(nlogn)，它的最好情況時間是什么？能說歸并分類的時間是(nlogn)嗎？最好情況：是對有序文件進行排序。分析：在此情況下歸并的次數(shù)不會發(fā)生變化-log(n)次歸并中比較的次數(shù)會發(fā)生變化（兩個長n/2序列歸并）最壞情況兩個序列交錯大小，需要比較n-1次最好情況一個序列完全大于/小于另一個序列，比較n/2次差異都是線性的，不改變復雜性的階因此最好情況也是nlogn, 平均復雜度nlogn。可以說歸并分類的時間是(nlogn)22寫一個“由底向上”的歸并分類算法，從而取消對棧空間的利用。答：見數(shù)據結構算法

16、MPass（R，n，1engthX） MP1 初始化 i1 MP2 合并相鄰的兩個長度為length的子文件 WHILE i n 2*length + 1 DO （Merge（R，i，ilengthl，i2*length1X）. ii2*length ） MP3 處理余留的長度小于2*length的子文件 IF i+length1 n THEN Merge（R，i，i+length1，n. X） ELSE FOR j = i TO n DO XjRj 算法MSort(R，n) / 直接兩路合并排序算法，X是輔助文件，其記錄結構與R相同MS1 初始化 length1 MS2 交替合并 WHILE

17、 length n then FOR j = 1 TO n DO RjXj else MPass（X，n，lengthR）. length2*length）endif)23什么是約束條件？什么是可行解？什么是目標函數(shù)？什么是最優(yōu)解？并舉例說明。答：有一類問題，解由輸入的某個子集組成，但是這個子集必須滿足某些事先給定的條件。那些必須滿足的條件稱為約束條件。滿足約束條件的子集稱為可行解。為了衡量可行解的優(yōu)劣，事先也給出一定的標準，這些標準一般以函數(shù)形式給出，稱為目標函數(shù)。使目標函數(shù)取極值的可行解稱為最優(yōu)解。26什么是貪心方法? 給出使用SPARKS語言描述的貪心方法的抽象化控制。答：對求取最優(yōu)解問

18、題，選取一種度量標準，將輸入按度量標準排序，并按此序一次輸入一個量。如果這個輸入和前面輸入產生的在這種度量意義下的部分最優(yōu)解加在一起產生一個可行解，將其加入形成新的在這種度量意義下的部分最優(yōu)解；若不能構成一個可行解，則去掉該輸入；重復此過程直到將輸入枚舉完成。這種能夠得到某種度量意義下的最優(yōu)解的分級處理方法稱為貪心方法。貪心方法的SPARKS語言描述的抽象化控制為：Procedure GREEDY(A,n) soltion for i1 to n do xSELECT(A) if FEASIBLE(soltion,x) then soltionUNION(soltion,x) endif re

19、peat return(soltion) end GREEDY24 求以下情況背包問題的最優(yōu)解，n=7，m=15，=(10,5,15,7,6,18,3)和=(2,3,5,7,1,4,1)。 將以上數(shù)據情況的背包問題記為I。設FG(I)是物品按的非增次序輸入時由GREEDY-KNAPSACK所生成的解，F(xiàn)O(I)是一個最優(yōu)解。問FO(I)/ FG(I)是多少? 當物品按的非降次序輸入時，重復的討論。解： 按照/的非增序可得(/，/，/，/，/，/，/)= (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,

20、2/3,1,0,1,1,1）FO(I)=166/3 按照Pi的非增次序輸入時得到(,)= (18,15,10,7,6,5,3)，對應的(,)= (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. 按照的非降次序輸入時得到(,)=(1,1,2,3,4,5,7)相應的(,)=(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

21、（0/1背包問題）如果將5.3節(jié)討論的背包問題修改成 極大化 約束條件 xi=0或1 1in這種背包問題稱為0/1背包問題。它要求物品或者整件裝入背包或者整件不裝入。求解此問題的一種貪心策略是：按/的非增次序考慮這些物品，只要正被考慮的物品能裝進的就將其裝入背包。證明這種策略不一定能得到最優(yōu)解。證明：當按照/的非增次序考慮物品存放背包時，如果所裝入的物品恰能裝滿背包時，易證為最優(yōu)解，否則未必是最優(yōu)解。可舉例如下：設n=3，M=6，（, , ）=(3,4,8)，（, , ）=(1,2,5)，按照/的非增序得到（/, /, /）=(3,2,1.6)，則其解為（1,1,0），而事實上最優(yōu)解是(1,0

22、,1)，問題得證。26假定要將長為, 的n個程序存入一盤磁帶，程序i被檢索的頻率是。如果程序按, 的次序存放，則期望檢索時間（ERT）是 證明按的非降次序存放程序不一定得到最小的ERT。 證明按的非增次序存放程序不一定得到最小的ERT。 證明按/的非增次序來存放程序時ERT取最小值。證明：只需證明結論是正確的即可，現(xiàn)證明如下： 假設, 按照/的非增次序存放，即/，則得到 ERT=+(+)+(+ /假設該問題的一個最優(yōu)解是按照, 的順序存放，并且其期望檢索式件是，我們只需證明，即可證明按照/的非增次序存放得到的是最優(yōu)解。易知=+(+)+(+ )/從前向后考察最優(yōu)解中的程序，不妨設程序是第一個與其

23、相鄰的程序存在關系/，則交換程序和程序，得到的期望檢索時間記為-=-0 顯然也是最優(yōu)解，將原來的最優(yōu)解中所有這樣類似于反序對的程序互換位置，得到的解不比原來的最優(yōu)解差，所以最終變換后得到的解也是最優(yōu)解，而最終的解恰是程序按/的非增次序來存放得到的順序。命題得證。27.假定要把長為, 的n個程序分布到兩盤磁帶和上，并且希望按照使最大檢索時間取最小值的方式存放，即，如果存放在和上的程序集合分別是A和B，那么就希望所選擇的A和B使得max,取最小值。一種得到A和B的貪心方法如下：開始將A和B都初始化為空，然后一次考慮一個程序，如果=min,，則將當前正在考慮的那個程序分配給A，否則分配給B。證明無論

24、是按或是按的次序來考慮程序，這種方法都不能產生最優(yōu)解。證明：按照存放不會得到最優(yōu)解，舉例如下：3個程序（a,b,c）長度分別為（1,2,3），根據題中的貪心算法，產生的解是A=a,cB=b，則max,=4，而事實上，最優(yōu)解應為3，所以得證.按照的次序存放也不會得到最優(yōu)解，舉例如下：5個程序（a,b,c,d,e）長度分別為（10,9,8,6,4）根據題中的貪心算法，產生的解是A=a,d,eB=b,c，則max,=20，而事實上，最優(yōu)解應為19，所以得證。28.當n=7，=(3,5,20,18,1,6,30) 和=(1,3,4,3,2,1,2)時，算法5.4所生成的解是什么？ 證明即使作業(yè)有不同的

25、處理時間定理5.3亦真。這里，假定作業(yè)I的效益0，要用的處理時間0，限期.解：根據的非增排序得到(,)=(30,20,18,6,5,3,1)，對應的期限為(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；證明：顯然即使0（），如果J中的作業(yè)可以按照s的次序而又不違反任何一個期限來處理，即對s次序中的任一個作業(yè)k，應滿足 ，則J就是一個可行解。下面證明如果J是可行解，則使得J中的作業(yè)可以按照, 排列的序列s處理而又不違反任何一個期限。因為

26、J是可行解，則必存在=，使得對任意的，都有，我們設s是按照,排列的作業(yè)序列。假設s，那么令a是使的最小下標，設=，顯然ba，在中將與相交換，因為，顯然和可以按期完成作業(yè)。還要證明和之間的作業(yè)也能按期完成。因為，而顯然二者之間的所有作業(yè)，都有，又由于s是可行解，所以。所以作業(yè)和交換后，所有作業(yè)可依新產生的排列=的次序處理而不違反任何一個期限，連續(xù)使用這種方法，就可轉換成s且不違反任何一個期限，定理得證。29 已知n-1個元素已按min-堆的結構形式存放在A(1),A(n-1)。現(xiàn)要將另一存放在A(n)的元素和A(1:n-1)中元素一起構成一個具有n個元素的min-堆。對此寫一個計算時間為O(lo

27、gn)的算法。 在A(1:n)中存放著一個min-堆，寫一個從堆頂A(1)刪去最小元素后將其余元素調整成min-堆的算法，要求這新的堆存放在A(1:n-1)中，且算法時間為O(logn). 利用所寫出的算法，寫一個對n個元素按非增次序分類的堆分類算法。分析這個算法的計算復雜度。解： procedure INSERT(A,n) integer i, j, k jn ; i while i1 and AiAj do kAj; AjAi; Aik ji ;i repeat end INSERT procedure RESTORE(A,l,n) integer i, j, k xAn;AnAl i1

28、j2*i while jn-1 do if (j Aj+1) then jj+1endif if (xAj) then AiAj; ij;j2*ielse inendifrepeatend RESTORE procedure HEAPSORT(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 kA1; A1Ai; Aik RESTORE(A, 1, i-1) repeat end HEAPSORT30 證明如果一棵樹的所有內部節(jié)點的度都為k，則外部節(jié)點數(shù)n滿足n mod

29、(k-1)=1. 證明對于滿足 n mod (k-1)=1的正整數(shù)n，存在一棵具有n個外部節(jié)點的k元樹T(在一棵k元樹中，每個節(jié)點的度至多為k)。進而證明T中所有內部節(jié)點的度為k.證明： 設某棵樹內部節(jié)點的個數(shù)是m，外部結點的個數(shù)是n，邊的條數(shù)是e，則有 e=m+n-1和 e=mkmk=m+n-1 (k-1)m=n-1 n mod (k-1)=1 利用數(shù)學歸納法。當n=1時，存在外部結點數(shù)目為1的k元樹T，并且T中內部結點的度為k；假設當 nm，且滿足n mod (k-1)=1時，存在一棵具有n個外部結點的k元樹T，且所有內部結點的度為k；我們將外部結點數(shù)為n(n為滿足nm，且n mod (k

30、-1)=1的最大值)的符合上述性質的樹T中某個外部結點用內部結點a替代，且結點a生出k個外部結點，易知新生成的樹T中外部結點的數(shù)目為n+(k-1)，顯然n為滿足n mod (k-1)=1，且比m大的最小整數(shù)，而樹T每個內結點的度為k，即存在符合性質的樹。綜合上述結果可知,命題成立。31 證明如果n mod (k-1)=1，則在定理5.4后面所描述的貪心規(guī)則對于所有的（, ）生成一棵最優(yōu)的k元歸并樹。 當（, ）=（3,7,8,9,15,16,18,20,23,25,28）時，畫出使用這一規(guī)則所得到的最優(yōu)3元歸并樹。解：通過數(shù)學歸納法證明：對于n=1，返回一棵沒有內部結點的樹且這棵樹顯然是最優(yōu)的

31、。假定該算法對于（, ），其中m =(k-1)s+1 (0 s)，都生成一棵最優(yōu)樹.則只需證明對于(, )，其中n=(k-1)(s+1)+1，也能生成最優(yōu)樹即可。不失一般性，假定，且, 是算法所找到的k棵樹的WEIGHT信息段的值。于是, 棵生成子樹，設是一棵對于（, ）的最優(yōu)k元歸并樹。設P是距離根最遠的一個內部結點。如果P的k個兒子不是, ，則可以用, 和P現(xiàn)在的兒子進行交換，這樣不增加的帶權外部路徑長度。因此也是一棵最優(yōu)歸并樹中的子樹。于是在中如果用其權為q1+q2+qk的一個外部結點來代換，則所生成的樹是關于(+,)的一棵最優(yōu)歸并樹。由歸納假設，在使用其權為+的那個外部結點代換了以后，

32、過程TREE轉化成去求取一棵關于(+,)的最優(yōu)歸并樹。因此TREE生成一棵關于(, )的最優(yōu)歸并樹。32對n=7, ( )=(35，30，25，20，15，10，5) 和( )=(4，2，4，3，4，8，3)的有限期作業(yè)調度問題使用教材中作業(yè)排序的更快算法求解最優(yōu)解。（要求描述時間片數(shù)組F（i）和對應集合的變化過程）33當作業(yè)數(shù)n7，（p1，p2，p7）（7, 6, 5, 4, 3, 2, 1）（d1，d2，d7）（4, 2, 4, 3, 1, 4, 6）時，利用算法5.5（作業(yè)排序的更快算法）求解上述作業(yè)排序問題的最優(yōu)解。（要求按步驟運行并給出集合樹的變化情況及當前最優(yōu)解）。34舉例說明最優(yōu)

33、性原理是什么？最優(yōu)性原理是指，過程的最優(yōu)決策序列具有如下性質：無論過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對于初始決策所產生的狀態(tài)構成一個最優(yōu)決策序列。例如：35舉例說明支配規(guī)則的內容。36由最優(yōu)性原理指出的過程的最優(yōu)決策序列具有的性質是什么？答：無論過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對于初始決策所產生的狀態(tài)構成一個最優(yōu)決策序列。37什么樣的決策過程構成多階段決策過程？ 答：活動過程可以分為若干個階段，而且在任一階段后的行為都僅依賴于i 階段的過程狀態(tài)，而與i 階段之前如何到達這種狀態(tài)的方式無關，這樣的過程就構成一個多階段決策過程。38使用動態(tài)規(guī)劃求解問題的前提條件是

34、什么？試舉出兩個例子，這兩個例子都可以看作是多階段決策問題，但一個例子可以用動態(tài)規(guī)劃來解，而另一個例子不能用動態(tài)規(guī)劃求解。39修改過程ALL_PATHS，使其輸出每對結點（i,j）間的最短路徑，這個新算法的時間和空間復雜度是多少？ Procedure ShortestPath(COST, n, A, Max)integer i , j, kreal COST(n, n), A(n, n), Path(n, n), Maxfor i1 to n do for j1 to n do A(i ,j)COST(i ,j) if ij and A(i, j)Max then Path(i, j )j e

35、lse Path(i, j)0 endif repeatrepeatfor k1 to n do for i1 to n do for j1 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 i1 to n do for j1 to n do print(“the path of i to j is ” i ) kpath(i, j) while k0 do print( ,k) kpath(k, j) repeat repeatrepeat

36、 end ShortestPath時間復雜度O(n3)，空間復雜度O(n2) 40.已知圖的鄰接矩陣（1）按照每對結點間的最短路徑算法ALL-PATH，求每對結點間的最短路徑長度矩陣A4 （2）求路徑結點矩陣P。P(i,j)表示從i到j的最短路徑的第一步結點。P初始如下：（3）根據P和A4，分別給出結點2到結點4，結點1到結點3的最短路徑及長度解: 計算得: A1 = P1= A2 = P2=A3 = P3=A4 = P4=結點2到結點4的最短路徑長為9，最短路徑是214.結點1到結點3的最短路徑長為9，最短路徑是143.41給出一個使得DKNAP(算法6.7)出現(xiàn)最壞情況的例子，它使得|Si|=2i, 0in。還要求對n的任意取值都適用。解：取(P1,P2,Pi,)=(W1,W2,Wi,)=(20,21,2i-1,)P和W取值相同，使支配原則成立，也就是說不會因為支配原則而刪除元素；只要說明不會出現(xiàn)相同元素被刪除一個的情形，即可知是最壞的情況。可用歸納法證明此結論。42遞推關系式（6.8）對(P151,圖6.16)成立嗎？為什么？ 遞推關系式（6.8）為什么對于含有負長度環(huán)的圖不能成