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.對(duì)稱矩陣可存儲(chǔ)上（下）三角矩陣14只有有向完全圖的鄰接矩陣是對(duì)稱的16.鄰接矩陣中元素值可以存儲(chǔ)權(quán)值21.只有無向連通圖才有生成樹22.最小生成樹

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

4、活動(dòng)的時(shí)間延長(zhǎng)多少，整個(gè)工程的時(shí)間也就隨之延長(zhǎng)多少。三填空題1.有n個(gè)頂點(diǎ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列非零元素個(gè)數(shù)20.n2e5證明：該有向圖頂點(diǎn)編號(hào)的規(guī)律是讓弧尾頂點(diǎn)的編號(hào)大于弧頭頂點(diǎn)的編號(hào)。由于不允許從某頂點(diǎn)發(fā)出并回到自身頂點(diǎn)的弧，所以鄰接矩陣主對(duì)角

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

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