單元練習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 雜湊表是一種將關鍵字...
資料結構單元4練習
單元測驗4 一 判斷題 下列各題,正確的請在前面的括號內打 錯誤的打 1 佇列是限制在兩端進行操作的線性表。2 判斷順序隊列為空的標準是頭指標和尾指標都指向同乙個結點。3 在鏈佇列上做出隊操作時,會改變front指標的 值 所指向的位置或儲存空間。4 在迴圈佇列中,若尾指標rear大於頭指標fron...
資料結構單元2練習
單元練習2 一 判斷題 下列各題,正確的請在前面的括號內打 錯誤的打 1 線性表的鏈式儲存結構優於順序儲存。2 鍊錶的每個結點都恰好包含乙個指標域。3 性表的鏈式儲存結構中,邏輯上相鄰的兩個元素在物理位置上並不一定緊鄰。4 順序儲存方式的優點是儲存密度大,插入 刪除效率高。5 線性鍊錶的刪除演算法簡...