a數(shù)據(jù)結(jié)構(gòu)習(xí)題圖答案

1、第7章圖一.選擇題1.A2.B3.A4.B5.D6.1B6.2D7.1B7.2C8.A9.A10.1C10.2BDE11.B12.1B12.2B12.3D13.B14.C15.C16.D17.D18.1C18.2C19.AB20.B21.1C21.2A21.3B21.4A22.A23.A24.D25.A26.A27.B28.D29.B30.A31.C32.B二.判斷題1.√2.3.4.5.6.√7.8.9.10.11.√12.13.√1

2、4.15.16.17.√18.19.20.21.22.23.24.25.26.√27.28.√29.30.31.√32.√33.34.35.36.√37.38.39.40.41.√42.43.44.√45.46.47.48.√49.部分答案解釋如下。2.不一定是連通圖，可能有若干連通分量11.對稱矩陣可存儲上（下）三角矩陣14只有有向完全圖的鄰接矩陣是對稱的16.鄰接矩陣中元素值可以存儲權(quán)值21.只有無向連通圖才有生成樹22.最小生成樹

3、不唯一，但最小生成樹上權(quán)值之和相等26.是自由樹，即根結(jié)點不確定35.對有向無環(huán)圖，拓?fù)渑判虺晒?；否則，圖中有環(huán)，不能說算法不適合。42.AOV網(wǎng)是用頂點代表活動，弧表示活動間的優(yōu)先關(guān)系的有向圖叫頂點表示活動的網(wǎng)。45.能求出關(guān)鍵路徑的AOE網(wǎng)一定是有向無環(huán)圖46.只有該關(guān)鍵活動為各關(guān)鍵路徑所共有，且減少它尚不能改變關(guān)鍵路徑的前提下，才可縮短工期。48按著定義，AOE網(wǎng)中關(guān)鍵路徑是從“源點”到“匯點”路徑長度最長的路徑。自然，關(guān)鍵路徑上

4、活動的時間延長多少，整個工程的時間也就隨之延長多少。三填空題1.有n個頂點，n1條邊的無向連通圖2.有向圖的極大強(qiáng)連通子圖3.生成樹4.455.n(n1)26.7.98.n9.2(n1)10.N111.n112.n13.N114.n15.N16.317.2（N1）18.度出度19.第I列非零元素個數(shù)20.n2e5證明：該有向圖頂點編號的規(guī)律是讓弧尾頂點的編號大于弧頭頂點的編號。由于不允許從某頂點發(fā)出并回到自身頂點的弧，所以鄰接矩陣主對角

5、元素均為0。先證明該命題的充分條件。由于弧尾頂點的編號均大于弧頭頂點的編號，在鄰接矩陣中，非零元素（A[i][j]=1）自然是落到下三角矩陣中；命題的必要條件是要使上三角為0，則不允許出現(xiàn)弧頭頂點編號大于弧尾頂點編號的弧，否則，就必然存在環(huán)路。（對該類有向無環(huán)圖頂點編號，應(yīng)按頂點出度順序編號。）6設(shè)圖的頂點個數(shù)為n(n≥0)，則鄰接矩陣元素個數(shù)為n2，即頂點個數(shù)的平方，與圖的邊數(shù)無關(guān)。7（1）n(n1)，n(2)106，不一定是稀疏矩陣

6、（稀疏矩陣的定義是非零個數(shù)遠(yuǎn)小于該矩陣元素個數(shù)，且分布無規(guī)律）（3）使用深度優(yōu)先遍歷，按退出dfs過程的先后順序記錄下的頂點是逆向拓?fù)溆行蛐蛄?。若在?zhí)行dfs(v)未退出前，出現(xiàn)頂點u到v的回邊，則說明存在包含頂點v和頂點u的環(huán)。8(1)（2）開始結(jié)點：（入度為0）K1，K2，終端結(jié)點（出度為0）K6，K7。（3）拓?fù)湫蛄蠯1，K2，K3，K4，K5，K6，K8，K9，K7K2，K1，K3，K4，K5，K6，K8，K9，K7規(guī)則：開始結(jié)