a. n b. (n-1)2 c. n-1 [, ]
9．對於乙個具有n個頂點和e條邊的無向圖，若採用鄰接表表示，則表頭向量的大小為_①___；所有鄰接表中的接點總數是_②___。
① b. n+1 c. n-1 d. n+e
② a. e/2 b. e d. n+e
10．已知乙個圖如圖7.1所示，若從頂點a出發按深度搜尋法進行遍歷，則可能得到的一種頂點序列為__①__；按寬度搜尋法進行遍歷，則可能得到的一種頂點序列為__②__。
① a. a,b,e,c,d,f b. e,c,f,e,b,d c.
a,e,b,c,f,dt': 'span', 'c': ' d.
a,e,d,f,c,b'}]
② a. a,b,c,e,d,f
c. v1,v2,v3,v5,v4 d. v1,v4,v3,v5,v2
12．採用鄰接表儲存的圖的深度優先遍歷演算法類似於二叉樹的____。
[, , , ]
14．關鍵路徑是事件結點網路中 。
[, , , , , , , , {'t': 'span', 'c': '2c.k1-k2 d.k1+k2
19．對於乙個有向圖，若乙個頂點的入度為k1,、出度為k2，則對應逆鄰接表中該頂點單鏈表中的結點數為 。
[{'t': 'span', 'c': 'a.k1b.k2c.k1-k2 d.k1+k2
7.2 填空題（將正確的答案填在相應餓空中）
1．n個頂點的連通圖至少_n-1_條邊。
2．在無權圖g的鄰接矩陣a中，若(vi,vj)或＜vi,vj＞屬於圖g的邊集合，則對應元素a[i][j]等於_1_，否則等於_0__。
3．在無向圖g的鄰接矩陣a中，若a[i][j]等於1，則a[j][i ]等於_1__。
4．已知圖g的鄰接表如圖7.4所示，其從頂點v1出發的深度有限搜尋序列為__ v1,v2,v3,v6,v5, v4__，其從頂點v1出發的寬度優先搜尋序列為_ v1,v2,v5,v4,v3, v6___。
圖7.4 圖g的鄰接表
5．已知乙個有向圖的鄰接矩陣表示，計算第i個結點的入度的方法是_求矩陣第i列非零元素之和_。
6．已知乙個圖的鄰接矩陣表示，刪除所有從第i個結點出發的邊的方法是__將矩陣第i行全部置為零。
7．遍歷圖的過程實質上是對每個頂點查詢其鄰接點的過程； 。bfs遍歷圖的時間複雜度為 o（e）（e為圖中的邊數），dfs遍歷圖的時間複雜度為 o（e）； ，兩者不同之處在於遍歷圖的順序不同 ，反映在資料結構上的差別是 dfs採用棧儲存訪問過的結點，bfs採用佇列儲存訪問過的結點。
8．乙個圖的鄰接矩陣表示法是唯一的，而鄰接表表示法是不唯一的。
9．有向圖中的結點前驅後繼關係的特徵是乙個結點可能有若干個前驅，也可能有若干個後繼 。
10．若無向圖g的頂點度數最小值大於等於 2 時，g至少有一條迴路。
11．根據圖的儲存結構進行某種次序的遍歷，得到的頂點序列是唯一的。
7.3 綜合題
1．已知如圖7.5所示的有向圖，請給出該圖的:
（1）每個頂點的入/出度；
（2）鄰接距陣；
（3）鄰接表；
（4）逆鄰接表；
（5）強連通分量。
3．試列出圖7.8中全部的拓撲排序序列。
圖7.8
152364
152634
156234
561234
516234
512634
512364
4．請用圖示說明圖7.9從頂點a到其餘各頂點之間的最短路徑。
圖7.9
5．已知aoe網有9個結點：v1，v2，v3，v4，v5，v6，v7，v8，v9，其鄰接矩陣如下：
(1)請畫出該aoe圖。
(2)計算完成整個計畫需要的時間。
(3)求出該aoe網的關鍵路徑。
5．(1)該aoe圖為：
(2)完成整個計畫需要18天。
(3)關鍵路徑為：（v1，v2，v5，v7，v9）和（v1，v2， v5，v8，v9，）
資料結構練習題
習題3 棧和佇列 一 基本內容 棧和佇列的結構特點 在兩種儲存結構上如何實現棧和佇列的基本操作以及棧和佇列在程式設計中的應用。二 學習要點 1.掌握棧和佇列的特點。2 熟練掌握棧型別的兩種實現方法，即兩種儲存結構表示時的基本操作實現演算法，特別應注意棧滿和棧空的條件以及它們的描述方法。3 熟練掌握迴...
資料結構練習題
習題5 陣列和廣義表 一 基本內容 陣列定義及表示方式 特殊矩陣和稀疏矩陣的壓縮儲存方法及運算的實現 廣義表的邏輯結構和儲存結構。二 學習要點 1.了解陣列的兩種儲存表示方法，並掌握陣列在以行為主的儲存結構中的位址計算方法。2 掌握對特殊矩陣進行壓縮儲存時的下標變換公式。3 了解稀疏矩陣的兩種壓縮儲...
資料結構練習題
1 3個結點可構成棵不同形態的樹。2 利用直接選擇排序演算法對n個記錄進行排序，最壞的情況下，記錄交換的次數為 3 乙個圖的 表示法是唯一的，而 表示法是不唯一的。4 一棵深度為h的滿二叉樹上的結點總數為 一棵深度為h的完全二叉樹上的結點總數的最小值為 最大值為 5 在一棵完全二叉樹中有n個結點，對...