【正文】 else /*左子樹非空*/ { if(prtag==0) /*右子樹非空，右孩子就是前驅*/ q=prchild。 if(prtag==1) /*右子樹為空，左孩子就是前驅*/ q=plchild。 } return(q)。}習題七解答1. 填空題 ⑴0，n(n1)/2，0，n(n1) 圖的頂點集合是有窮非空的，而邊集可以是空集；邊數(shù)達到最多的圖稱為完全圖，在完全圖中，任意兩個頂點之間都存在邊。⑵鄰接矩陣，鄰接表 這是最常用的兩種存儲結構，此外，還有十字鏈表、鄰接多重表等。⑶Ｏ(n+e) 在無向圖的鄰接表中，頂點表有n個結點，邊表有2e個結點，共有n+2e個結點，其空間復雜度為Ｏ(n+2e)=Ｏ(n+e)。⑷求第i行的所有元素之和⑸前序，棧，層序，隊列⑹回路⑺2000⑻從源點到匯點的最長路徑⑼m頂點所代表的事件要優(yōu)先于n頂點所代表的事件完成(10)n1（11）全部（n0 n1(12)有向(13)稠密 稀疏(14)O（n2），O（n+e）(15)m=2e2. 選擇題⑴B 設無向圖中含有n個頂點e條邊，則 。⑵D⑶C 若超過n1，則路徑中必存在重復的頂點。⑷D n個頂點的無向圖中，邊數(shù)e≤n(n1)/2，將e=41，有n≥9，現(xiàn)已知無向圖非連通，則n=10。⑸D⑹D 當有向圖中無回路時，從某頂點出發(fā)進行深度優(yōu)先遍歷時，出棧的順序（退出DFSTraverse算法）即為逆向的拓撲序列。⑺C，D⑻A(9)B(10)B(11)A 鄰接矩陣的存儲空間為O(n2)，鄰接表的存儲空間為O(n+e)(12)D3. 判斷題⑴對。鄰接表和逆鄰接表的區(qū)別僅在于出邊和入邊，邊表中的結點個數(shù)都等于有向圖中邊的個數(shù)。⑵對。鄰接矩陣的空間復雜度為Ｏ(n2)，與邊的個數(shù)無關。⑶錯。有向圖的鄰接矩陣不一定不對稱，例如有向完全圖的鄰接矩陣就是對稱的。⑷錯。只有連通圖從某頂點出發(fā)進行一次遍歷，可訪問圖的所有頂點。⑸錯。只能說明從頂點a到頂點b有一條路徑。⑹錯。只有在仍舊保持關鍵活動所在路徑仍是關鍵路徑的前提下才可以。4．（1）鏈接矩陣：⑴ 鄰接矩陣中非零元素個數(shù)的總和除以2。⑵ 當鄰接矩陣A中A[i][j]=1（或A[j][i]=1）時，表示兩頂點之間有邊相連。⑶ 計算鄰接矩陣上該頂點對應的行上非零元素的個數(shù)。鄰接表：⑴ 邊表中的結點個數(shù)之和除以2。⑵ 第i個邊表中是否含有結點j。⑶ 該頂點所對應的邊表中所含結點個數(shù)。（2）鄰接矩陣表示如下：鄰接表表示如下： 各頂點的度：TD(v1)=3 TD(v2)=4 TD(v3)=2 TD(v4)=4 TD(v5)=3 TD(v6)=2深度優(yōu)先遍歷序列為：v1 v2 v3 v5 v4 v6廣度優(yōu)先遍歷序列為：v1 v2 v4 v6 v3 v5（3）按Prim算法求最小生成樹的過程如下：按Kruskal算法求最小生成樹的過程如下：（4）拓撲序列為：v0 v1 v5 v2 v3 v6 v v0 v1 v5 v2 v6 v3 v v0 v1 v5 v6 v2 v3 vv0 v5 v1 v2 v3 v6 v v0 v5 v1 v2 v6 v3 vv0 v5 v1 v6 v2 v3 v v1 v0 v5 v2 v3 v6 vv1 v0 v5 v2 v6 v3 v v1 v0 v5 v6 v2 v3 vv1 v5 v0 v2 v3 v6 v v1 v5 v0 v2 v6 v3 v v1 v5 v0 v6 v2 v3 vv5 v0 v1 v2 v3 v6 vv5 v0 v1 v2 v6 v3 vv5 v0 v1 v6 v2 v3 vv5 v1 v0 v2 v3 v6 v v5 v1 v0 v2 v6 v3 v v5 v1 v0 v6 v2 v3 v4（5）所有事件的最早發(fā)生時間ve[k]： ve (1)=0 ve (2)=3 ve (3)= max{ve(1)+2,ve(2)+6,ve(4)+2}=9 ve (4)=5 ve (5)=max{ve(2)+5,ve(3)+8}=17 ve (6)= max{ve(3)+4,ve(4)+8}=13 ve (7)=max{ve(3)+9,ve(5)+8,ve(6)+7}=25 所有事件的最晚發(fā)生時間vl[k]： vl (7)= ve(7) =25 vl (6)= vl (7)7=18 vl (5)= vl (7) 8=17 vl (4)= min{ vl (3)2, vl (6)8}=7 vl (3)=min{ vl (7)9, vl (5)8, vl (6)4}=9 vl (2)=min{ vl (5)5, vl (3)6}=3 vl (1)= min{ vl (4)5, vl (3)2, vl (2)3}=0 所有活動ai的最早開始時間e[i]和最晚開始時間l[i]： 活動a1 e (1)=ve (1)=0 l (1)=vl (2) 3 =0 活動a2 e (2)=ve (1)=0 l (2)=vl (3) 2=7 活動a3 e (3)=ve (2)=0 l (3)=vl (4) 5=2 活動a4 e (4)=ve (2)=3 l (4)=vl (5) 5=12 活動a5 e (5)=ve (3)=3 l (5)=vl (3) 6=3 活動a6 e (6)=ve (3)=5 l (6)=vl (3) 2=7 活動a7 e (7)=ve (4)=5 l (7)=vl (6) 8=10 活動a8 e (8)=ve (5)=9 l (8)=vl (5) 8=9 活動a9 e (9)=ve (5)=9 l (9)=vl (7) 9=16 活動a10 e (10)=ve (6)=9 l (10)=vl (6) 4=14 活動a11 e (11)=ve (7)=17 l (11)=vl (7) 8=17 活動a12 e (12)=ve (8)=13 l (12)=vl (7) 7=18 最后，比較e[i]和l[i]的值可判斷出a1,a5,a8,a11這些活動的e[i]和l[i]的值相等，沒有時間余量，所以它們是關鍵活動，關鍵路徑如下圖所示。v2v5 a1=3 a5= 6 a11=8v7v3v1 a8= 8 （6）注：從V0到其余點的最短路徑10060V5 ∞ ∞ 10 ∞ 30 100 ∞ ∞ 5 ∞ ∞ ∞30V4V0 ∞ ∞ ∞ 50 ∞ ∞201010 ∞ ∞ ∞ ∞ ∞ 10V3V1 ∞ ∞ ∞ 20 ∞ 60505V2 ∞ ∞ ∞ ∞ ∞ ∞終點 從V0到各終點的Dist值和最短路徑的求解過程 i=1 i=2 i=3 i=4 i=5 V1 ∞ ∞ ∞ ∞ ∞無 V2 10 (V0,V2) V3 ∞ 60 (V0,V2,V3) 50 (V0,V4,V3) V4 30 (V0