數據結構圖練習

1、圖練習:1圖中有關路徑的定義是（ ） 。A.由頂點和相鄰頂點序偶構成的邊所形成的序列B.由不同頂點所形成的序列C.由不同邊所形成的序列D.上述定義都不是2.設無向圖的頂點個數為n,則該圖最多有（）條邊。A n-1 B n（n-1）/2 C n（n+1）/2 D 0 E n23一個 n 個頂點的連通無向圖，其邊的個數至少為（ ）。A n-1 B n C n+1 D nlogn ；4要連通具有n 個頂點的有向圖，至少需要（ ）條邊。A n-l B n C n+l D 2n5 n 個結點的完全有向圖含有邊的數目（ ） 。A. n*nB . n （n+ 1 ） C , n/2D . n* （n l ）

2、6一個有 n 個結點的圖，最少有（ ）個連通分量，最多有（ ）個連通 分量。A 0B 1C n-1 D n7在一個無向圖中，所有頂點的度數之和等于所有邊數（ ）倍，在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的（ ）倍。A 1/2 B 2 C 1D 48 . 下列說法不正確的是（ ） 。A.圖的遍歷是從給定的源點出發(fā)每一個頂點僅被訪問一次C .圖的深度 遍歷不適用于有向圖B.遍歷的基本算法有兩種：深度遍歷和廣度遍歷D .圖的深度遍歷是一個遞歸過程9 無 向 圖 G=(V,E), 其 中 ：V=a,b,Gd,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,

3、d),(e,d),對該圖進行深度優(yōu)先遍歷，得到的頂點序列正確的是()。A . a,b,e,c,d,fB . a,c,f,e,b,dC. a,e,b,c,f,dD. a,e,d,f,c,b10 .關鍵路徑是事件結點網絡中( )oA.從源點到匯點的最長路徑B .從源點到匯點的最短路徑C.最長回路D.最短回路1.A2.B3.A4.B5.D6.1B6.2D7.1B7.2C8c9D10A二、判斷題1. 樹中的結點和圖中的頂點就是指數據結構中的數據元素。 （）2在n 個結點的無向圖中，若邊數大于n-1, 則該圖必是連通圖。 （）3. 對有n個頂點的無向圖，其邊數e與各頂點度數間滿足下列等式e=0 （4.

4、有 e 條邊的無向圖，在鄰接表中有e 個結點。 （）5. 有向圖中頂點 V 的度等于其鄰接矩陣中第 V 行中的 1 的個數。 （）6強連通圖的各頂點間均可達。（）7鄰接多重表是無向圖和有向圖的鏈式存儲結構。（）8. 十字鏈表是無向圖的一種存儲結構。 （）9用鄰接矩陣法存儲一個圖所需的存儲單元數目與圖的邊數有關。（）10 有 n 個頂點的無向圖 , 采用鄰接矩陣表示, 圖中的邊數等于鄰接矩陣中非零元素之和的一半。 （）11 有向圖的鄰接矩陣是對稱的。 （）12無向圖的鄰接矩陣一定是對稱矩陣，有向圖的鄰接矩陣一定是非對稱矩陣。（）13. 鄰接矩陣適用于有向圖和無向圖的存儲， 但不能存儲帶權的有向圖

5、和無向圖，而只能使用鄰接表存儲形式來存儲它。 （）14. 用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小與圖中結點個數有關，而與圖的邊數無關。 （）15. 廣度遍歷生成樹描述了從起點到各頂點的最短路徑。 （）16任何無向圖都存在生成樹。 （）17. 不同的求最小生成樹的方法最后得到的生成樹是相同的 . （）18帶權無向圖的最小生成樹必是唯一的。（ ）19. 最小代價生成樹是唯一的。 （）20一個網（帶權圖）都有唯一的最小生成樹。 （）21連通圖上各邊權值均不相同，則該圖的最小生成樹是唯一的。 （）22帶權的連通無向圖的最?。ù鷥r）生成樹（支撐樹）是唯一的。 （）23帶權

6、的連通無向圖的最小代價生成樹是唯一的。 （）24. 最小生成樹問題是構造連通網的最小代價生成樹。1"2. X3. x4. X5. X6. V7X8X9. x10.V11X12.X13.14.15.16.17.18.19.20.21.22.2324vzXVXXXXXXVXX三、填空題1 .判斷一個無向圖是一棵樹的條件是 。2 .有向圖G的強連通分量是指 。3 . 一個連通圖的 是一個極小連通子圖。4 .具有10個頂點的無向圖，邊的總數最多為 。5 .若用n表示圖中頂點數目，則有 條邊的無向圖成為完全圖。6 .設無向圖G有n個頂點和e條邊，每個頂點Vi的度為di (1<=i<

7、=n，則 e=7 . G是一個非連通無向圖，共有28條邊，則該圖至少有 個頂點。8 .在有n個頂點的有向圖中，若要使任意兩點間可以互相到達，則至少需要 條弧。9 .在有n個頂點的有向圖中，每個頂點的度最大可達 。10 .設G為具有N個頂點的無向連通圖，則 G中至少有條邊。11 . n個頂點的連通無向圖，其邊的條數至少為 o12 .如果含n個頂點的圖形形成一個環(huán)，則它有 棵生成樹。13 . N個頂點的連通圖的生成樹含有 條邊。14 .構造n個結點的強連通圖，至少有 條弧。15 .有N個頂點的有向圖，至少需要量 條弧 rj分、才能保證是連通的。- -J,.16 .右圖中的強連通分量的個數為()個。

8、17 . N個頂點的連通圖用鄰接矩陣表示時，該矩陣 至少有 個非零元素。18 .在圖G的鄰接表表示中，每個頂點鄰接表中所含的結點數，對于無向圖來說等于該頂點的 ;對于有向圖來說等于該頂點的 。19 .在有向圖的鄰接矩陣表示中，計算第I個頂點入度的方法是 。20 .對于一個具有n個頂點e條邊的無向圖的鄰接表的表示，則表頭向量大小為 ,鄰接表的邊結點個數為。21 .已知一無向圖 G= ( V , E ),其中 V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)現(xiàn)用某一種圖遍歷方法從頂點 a開始遍歷圖，得到的序列為abecd,則采用的是遍歷方法。答案：1 .有n個

9、頂點，n-1條邊的無向連通圖2 .有向圖的極大強連通子圖3 .生成樹4 . 455. n(n-1)/26 .7. 98. n9. 2(n-1) 10. N-111. n-112. n 13. N-114. n15. N16. 3 17. 2(N-1)18. 度 出度19. 第I列非零元素個數 20.n 2e22.深度優(yōu)先23.寬度優(yōu)先遍歷四、應用題1 . (1).如果G1是一個具有n個頂點的連通無向圖，那么G1最多有多少條邊？ G1最少有多少條邊？(2) .如果G2是一個具有n個頂點的強連通有向圖，那么G2最多有多少條邊？ G2最少有多少條邊？(3) .如果G3是一個具有n個頂點的弱連通有向圖

10、，那么G3最多有多少條邊？ G3最少有多少條邊？2 . n個頂點的無向連通圖最少有多少條邊？n個頂點的有向連通圖最少有多少條邊？3 .首先將如下圖所示的無向圖給出其存儲結構的鄰接鏈表表示，然后寫出對其分別進行深度，廣度優(yōu)先遍歷的結果。4 .給出圖G:(1) .畫出G的鄰接表表示圖；(2) .根據你畫出的鄰接表，以頂點為根，畫出G的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。5 .對一個圖進行遍歷可以得到不同的遍歷序列，那么導致得到的遍歷序列不唯一的因素有 哪些？6 .考慮下圖：(1)從頂點A出發(fā)，求它的深度優(yōu)先生成樹(2)從頂點E出發(fā)，求它的廣度優(yōu)先生成樹(3)根據普利姆(Prim)算法，求它的最小生成樹從A點開始(4)根據kruskal算法，求它的最小生成樹7 .考慮下圖：(1)從頂點A出發(fā)，求它的深度優(yōu)先生成樹(2)從頂點E出發(fā)，求它的廣度優(yōu)先生成樹(3)根據普利姆(Prim)算法，求它的最小生成樹從1點開始(4)根據kruskal算法，求它的最小生成樹答案：(1) (1) G1最多n(n-1)/2 條邊，最少n-1條邊(2) G2最多n(n-1)條邊，最少n 條邊(3) G3最多n(n-1)條邊，最少n-1 條邊( 注：弱連通有向圖指把有向圖看作無向圖時，仍是連通的 )2 n-1 ， n3 深度優(yōu)先遍歷序列：125967384寬度優(yōu)先遍歷序列： 123456789注： ( 1)鄰接表不