單元練習8
一．判斷題（下列各題，正確的請在前面的括號內打√；錯誤的打╳ ）
（√）（1）圖可以沒有邊，但不能沒有頂點。
（ㄨ）（2）在無向圖中，（v1，v2）與（v2，v1）是兩條不同的邊。
（ㄨ）（3）鄰接表只能用於有向圖的儲存。
（√）（4）乙個圖的鄰接矩陣表示是唯一的。
（ㄨ）（5）用鄰接矩陣法儲存乙個圖時，所占用的儲存空間大小與圖中頂點個數無關，而只與圖的邊數有關。
（ㄨ）（6）有向圖不能進行廣度優先遍歷。
（√）（7）若乙個無向圖的以頂點v1為起點進行深度優先遍歷，所得的遍歷序列唯一，則可以唯一確定該圖。
（√）（8）儲存無向圖的鄰接矩陣是對稱的，因此只要儲存鄰接矩陣的上三角（或下三角）部分就可以了。
（ㄨ）（9）用鄰接表法儲存圖時，占用的儲存空間大小只與圖中的邊數有關，而與結點的個數無關。
（√）（10）若乙個無向圖中任一頂點出發，進行一次深度優先遍歷，就可以訪問圖中所有的頂點，則該圖一定是連通的。
二．填空題
（1） 圖常用的儲存方式有鄰接矩陣和鄰接表等。
（2） 圖的遍歷有： 深度優先搜和廣度優先搜等方法。
（3） 有n條邊的無向圖鄰接矩陣中，1的個數是 _2n____。
（4） 有向圖的邊也稱為 _ 弧___ 。
（5） 圖的鄰接矩陣表示法是表示 __頂點____之間相鄰關係的矩陣。
（6） 有向圖g用鄰接矩陣儲存，其第i行的所有元素之和等於頂點i的 __出度____。
（7） n個頂點e條邊的圖若採用鄰接矩陣儲存，則空間複雜度為： o（n2） 。
（8） n個頂點e條邊的圖若採用鄰接表儲存，則空間複雜度為： o（n+e） 。
（9） 設有一稀疏圖g，則g採用 _鄰接表____儲存比較節省空間。
（10） 設有一稠密圖g，則g採用 _鄰接矩陣____儲存比較節省空間。
（11） 圖的逆鄰接表儲存結構只適用於 __有向____圖。
（12） n個頂點的完全無向圖有 n(n-1)/2_ 條邊。
（13） 有向圖的鄰接表表示適於求頂點的出度 。
（14） 有向圖的鄰接矩陣表示中，第i列上非0元素的個數為頂點vi的入度 。
（15） 對於具有n個頂點的圖，其生成樹有且僅有 n-1 條邊。
（16） 對n個頂點，e條弧的有向圖，其鄰接表表示中，需要 n+e 個結點。
（17） 從圖中某一頂點出發，訪遍圖中其餘頂點，且使每一頂點僅被訪問一次，稱這一過程為圖
的遍歷 。
（18） 無向圖的鄰接矩陣一定是對稱矩陣。
（19） 乙個連通網的最小生成樹是該圖所有生成樹中權最小的生成樹。
（20） 若要求乙個稠密圖g的最小生成樹，最好用 prim 演算法來求解。
三．選擇題
（1）在乙個圖中，所有頂點的度數之和等於圖的邊數的( c )倍。
a．1/2b. 1c. 2d. 4
（2）在乙個有向圖中，所有頂點的入度之和等於所有頂點的出度之和的( b )倍。
a．1/2b. 1c. 2d. 4
（3）對於乙個具有n個頂點的有向圖的邊數最多有（ b ）。
a．nb．n(n-1c．n(n-1)/2d．2n
（4）在乙個具有n個頂點的無向圖中，要連通全部頂點至少需要（ c ）條邊。
a．nb．n+1c． n-1d．n/2
（5）有8個結點的有向完全圖有( c )條邊。
a．14b. 28c. 56d. 112
（6）深度優先遍歷類似於二叉樹的( a )。
a．先序遍歷b．中序遍歷 c．後序遍歷 d．層次遍歷
（7）廣度優先遍歷類似於二叉樹的( d )。
a．先序遍歷b．中序遍歷 c．後序遍歷 d．層次遍歷
（8）任何乙個無向連通圖的最小生成樹( a )。
a．只有一棵b．一棵或多棵 c．一定有多棵 d．可能不存在
（9）無向圖頂點v的度是關聯於該頂點（ b ）的數目。
a．頂點b．邊c．序號d．下標
（10）有n個頂點的無向圖的鄰接矩陣是用（ b ）陣列儲存。
a．一維b．n行n列c．任意行n列 d．n行任意列
（11）對於乙個具有n個頂點和e條邊的無向圖，採用鄰接表表示，則表頭向量大小為（ c ）。
a．n-1b．n+1c．nd．n+e
（12）在圖的表示法中，表示形式唯一的是（ a ）。
a．鄰接矩陣表示法b．鄰接表表示法
c．逆鄰接表表示法d．鄰接表和逆鄰接表表示法
（13）在乙個具有n個頂點e條邊的圖中，所有頂點的度數之和等於（ c ）。
a．nb．ec． 2nd．2e
（14）下列圖中，度為3的結點是（ b ）。
a．v1b. v2c. v3d. v4
（15）下列圖是（ a ）。
a．連通圖b. 強連通圖c. 生成樹d. 無環圖
（16）如下圖所示，從頂點a出發，按深度優先進行遍歷，則可能得到的一種頂點序列為（ d ）。
a． a，b，e，c，d，f
b． a，c，f，e，b，d
c. a，e，b，c，f，d
d. a，e，d，f，c，b
（17）如下圖所示，從頂點a出發，按廣度優先進行遍歷，則可能得到的一種頂點序列為（ a ）。
a. a，b，e，c，d，f
b. a，b，e，c，f，d
c. a，e，b，c，f，d
d. a，e，d，f，c，b
（18）最小生成樹的構造可使用（ a ）演算法。
a．prim演算法 b．卡爾演算法c．哈夫曼演算法 d．迪傑斯特拉演算法
（19）下面關於圖的儲存結構的敘述中正確的是（ a ）。
a． 用鄰接矩陣儲存圖，占用空間大小只與圖中頂點數有關，而與邊數無關
b． 用鄰接矩陣儲存圖，占用空間大小只與圖中邊數有關，而與頂點數無關
c． 用鄰接表儲存圖，占用空間大小只與圖中頂點數有關，而與邊數無關
d． 用鄰接表儲存圖，占用空間大小只與圖中邊數有關，而與頂點數無關
（20）連通分量是（ c ）的極大連通子圖。
a．樹b．圖c．無向圖d．有向圖
四．應用題（30分）
1．有向圖如下圖所示，畫出鄰接矩陣和鄰接表
解：（1）鄰接矩陣
1 2 3 4 5
（2）鄰接表
2． 已知乙個無向圖有6個結點，9條邊，這9條邊依次為（0，1）,（0，2）,（0，4）,（0，5），（1，2），（2，3），（2，4），（3，4），（4，5）。試畫出該無向圖，並從頂點0出發，分別寫出按深度優先搜尋和按廣度優先搜尋進行遍歷的結點序列。（5分）
解：從頂點0出發的深度優先搜尋遍歷的結點序列：0 1 2 3 4 5（答案不唯一）
從頂點0出發的廣度優先搜尋遍歷的結點序列：0 1 2 4 5 3（答案不唯一）
3． 已知乙個無向圖的頂點集為：，其鄰接矩陣如下，畫出草圖，寫出頂點a出發按深度優先搜尋進行遍歷的結點序列。（5分）
解：（12）深度優先搜尋：
a b d c e （答案不唯一）
廣度優先搜尋：
a b e d c （答案不唯一）
4．網g的鄰接矩陣如下，試畫出該圖，並畫出它的一棵最小生成樹。
解最小生成樹：
811108
3 4
1373 4
75. 已知某圖g的鄰接矩陣如圖，
（1）畫出相應的圖；
（2）要使此圖為完全圖需要增加幾條邊。
解：（1）
（2） 完全無向圖應具有的邊數為：n*(n-1)1/2=4*(4-1)/2=6，所以還要增加2條邊（如右圖）。
6．已知如圖所示的有向圖，請給出該圖的:
（1） 每個頂點的入/出度；
（2） 鄰接表；
（3） 鄰接矩陣。
解：（12）
（3）7．如圖，請完成以下操作：
（2） 寫出無向帶權圖的鄰接矩陣；
（3） 設起點為a，求其最小生成樹。
資料結構單元練習
單元練習9 一 判斷題 下列各題，正確的請在前面的括號內打 錯誤的打 1 二分查詢法要求待查表的關鍵字值必須有序。2 對有序表而言採用二分查詢總比採用順序查詢法速度快。3 在二叉排序樹中，根結點的值都小於孩子結點的值。4 雜湊儲存法的基本思想是由關鍵字的值決定資料的儲存位址。5 雜湊表是一種將關鍵字...
資料結構單元練習
單元練習8 一 判斷題 下列各題，正確的請在前面的括號內打 錯誤的打 1 圖可以沒有邊，但不能沒有頂點。2 在無向圖中，v1，v2 與 v2，v1 是兩條不同的邊。3 鄰接表只能用於有向圖的儲存。4 乙個圖的鄰接矩陣表示是唯一的。5 用鄰接矩陣法儲存乙個圖時，所占用的儲存空間大小與圖中頂點個數無關，...
資料結構單元4練習
單元測驗4 一 判斷題 下列各題，正確的請在前面的括號內打 錯誤的打 1 佇列是限制在兩端進行操作的線性表。2 判斷順序隊列為空的標準是頭指標和尾指標都指向同乙個結點。3 在鏈佇列上做出隊操作時，會改變front指標的 值 所指向的位置或儲存空間。4 在迴圈佇列中，若尾指標rear大於頭指標fron...