數(shù)據(jù)結(jié)構(gòu)第07章 圖習(xí)題

第七章圖

一、選擇題

1、對(duì)于具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則該矩陣的大小為（）。

A.nB.n2C.n-1D.（n-1）2

2、如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則該圖一定是

（）?

A.完全圖B.連通圖C.有回路D.一棵樹

3、關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（）o

A.從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑B.從源點(diǎn)到匯點(diǎn)的最短路徑

C.最長(zhǎng)的回路D.最短的回路

4、下面（）可以判斷出一個(gè)有向圖中是否有環(huán)（回路）。

A.廣度優(yōu)先遍歷B.拓?fù)渑判?/p>

C.求最短路徑D.求關(guān)鍵路徑

5、帶權(quán)有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度等于A中（）o

A.第i行非無窮的元素之和B.第i列非無窮的元素個(gè)數(shù)之和

C.第i行非無窮且非0的元素個(gè)數(shù)D.第i行與第i列非無窮且非0的元素之和

6、采用鄰接表存儲(chǔ)的圖，其深度優(yōu)先遍歷類似于二叉樹的（）。

A.中序遍歷B.先序遍歷C.后序遍歷D.按層次遍歷

7、無向圖的鄰接矩陣是一個(gè)（

A.對(duì)稱矩陣B.零矩陣C.上三角矩陣D.對(duì)角矩陣

8、當(dāng)利用大小為N的數(shù)組存儲(chǔ)循環(huán)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度是（）.

A.N-2B.N-1C.ND.N+1

9、鄰接表是圖的一種（）。

A.順序存儲(chǔ)結(jié)構(gòu)B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C.索引存儲(chǔ)結(jié)構(gòu)D.散列存儲(chǔ)結(jié)構(gòu)

10、下面有向圖所示的拓?fù)渑判虻慕Y(jié)果序列是（）。

A.125634B.516234C.123456D.521643

11、在無向圖中定義頂點(diǎn)vi與vj之間的路徑為從vi到vj的一個(gè)（）。

A.頂點(diǎn)序列B.邊序列C.權(quán)值總和D.邊的條數(shù)

12、在有向圖的逆鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（）鄰接點(diǎn)。

A.入邊B.出邊C.入邊和出邊D,不是出邊也不是入邊

13、設(shè)G1=（V1,E1）和G2=（V2,E2）為兩個(gè)圖，如果VlqV2,EluE2則稱（）。

A.G1是G2的子圖B.G2是G1的子圖C.G1是G2的連通分量D.G2是

G1的連通分量

14、已知一個(gè)有向圖的鄰接矩陣表示，要?jiǎng)h除所有從第i個(gè)結(jié)點(diǎn)發(fā)出的邊，應(yīng)（）。

A.將鄰接矩陣的第i行刪除B.將鄰接矩陣的第i行元素全部置為0

C.將鄰接矩陣的第i列刪除D.將鄰接矩陣的第i列元素全部置為0

15、任一個(gè)有向圖的拓?fù)湫蛄校ǎ﹐

A.不存在B.有一個(gè)C.一定有多個(gè)D.有一個(gè)或多個(gè)

16、在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（）倍。

A.1/2B.1C.2D.4

17、下列關(guān)于圖遍歷的說法不正確的是（）。

A.連通圖的深度優(yōu)先搜索是一個(gè)遞歸過程

B.圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特征

C.非連通圖不能用深度優(yōu)先搜索法

D.圖的遍歷要求每一頂點(diǎn)僅被訪問一次

18、帶權(quán)有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度為A中：（）。

A.第i行非8的元素之和B.第i列非8的元素之和

C.第i行非8且非0的元素個(gè)數(shù)D.第i列非8且非0的元素個(gè)數(shù)

19、采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于二叉樹的（）。

A.先序遍歷B.中序遍歷C.后序遍歷D.按層次遍歷

20、一個(gè)具有n個(gè)頂點(diǎn)的有向圖最多有（）條邊。

A.nx（n-l）/2B.nx（n-l）C.nx（n+l）/2D.n2

21、已知一個(gè)有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖所示，根據(jù)深度優(yōu)先遍歷算法，從頂點(diǎn)vl出發(fā)，

所得到的頂點(diǎn)序列是（）o

A.vl,v2,v3,v5,v4B.vl,v2,v3,v4,v5

C.vl,v3,v4,v5,v2D.vI,v4,v3,v5,v2

22、關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（）.

A.從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑B.從源點(diǎn)到匯點(diǎn)的最短路徑

C.最長(zhǎng)的回路D.最短的回路

23、以下說法正確的是（）。

A.連通分量是無向圖中的極小連通子圖

B.強(qiáng)連通分量是有向圖中的極大強(qiáng)連通子圖

C.在一個(gè)有向圖的拓?fù)湫蛄兄腥繇旤c(diǎn)a在頂點(diǎn)b之前，則圖中必有一條弧<a,b>

D.對(duì)有向圖G,如果以任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每個(gè)

頂點(diǎn)，則該圖一定是完全圖

24、假設(shè)有向圖含n個(gè)頂點(diǎn)及e條弧，則表示該圖的鄰接表中包含的弧結(jié)點(diǎn)個(gè)數(shù)為（）。

A.nB.eC.2eD.n*e

’011

25、設(shè)圖的鄰接矩陣為001,則該圖為()o

10,

A.有向圖B.無向圖C.強(qiáng)連通圖D.完全圖

26、為便于判別有向圖中是否存在回路，可借助于（）。

A.廣度優(yōu)先搜索算法B.最小生成樹算法

C.最短路徑算法D.拓?fù)渑判蛩惴?/p>

27、任何一個(gè)無向連通圖的最小生成樹（）。

A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在

28、己知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖所示，根據(jù)有向圖的廣度優(yōu)先遍歷算法，從頂點(diǎn)vl

A.vl,v2,v3,v4,v5B.vl,v3,v2,v4,v5C.vl,v2,v3,v5,v4D.vl,v4,v3,v5,v2

29、對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的入度為kl、出度為k2,則對(duì)應(yīng)鄰接表中該頂點(diǎn)單鏈表中

的結(jié)點(diǎn)數(shù)為（

A.klB.k2C.kl+k2D.kl-k2

30、無向圖中一個(gè)頂點(diǎn)的度是指圖中（）o

A.通過該頂點(diǎn)的簡(jiǎn)單路徑數(shù)B.與該頂點(diǎn)相鄰接的頂點(diǎn)數(shù)

C.與該頂點(diǎn)連通的頂點(diǎn)數(shù)D.通過該頂點(diǎn)的回路數(shù)

二、填空題

1、n個(gè)頂點(diǎn)的連通圖至少有邊。

2、一個(gè)連通圖的生成樹是一個(gè),它包含圖中所有頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1

條邊。

3、一個(gè)圖的表示法是惟一的。

4、遍歷圖的基本方法有深度優(yōu)先搜索和廣度優(yōu)先搜索，其中是一個(gè)遞歸過程。

5、在無向圖G的鄰接矩陣A中，若等于1,則等于。

6、判定一個(gè)有向圖是否存在回路，可以利用。

7、己知一個(gè)圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是o

8、n個(gè)頂點(diǎn)的無向圖最多有邊。

9、己知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是。

10、若以鄰接矩陣表示有向圖，則鄰接矩陣上第i行中非零元素的個(gè)數(shù)即為頂點(diǎn)vi的一。

三、判斷題

1、圖的連通分量是無向圖的極小連通子圖。

2、一個(gè)圖的廣度優(yōu)先搜索樹是惟一的。

3、圖的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列不是惟一的。

4、鄰接表只能用于存儲(chǔ)有向圖，而鄰接矩陣則可存儲(chǔ)有向圖和無向圖。

5、存儲(chǔ)圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點(diǎn)數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。

6、AOV網(wǎng)是一個(gè)帶權(quán)的有向圖。

7、從源點(diǎn)到終點(diǎn)的最短路徑是唯一的。

8、鄰接表只能用于存儲(chǔ)有向圖，而鄰接矩陣則可存儲(chǔ)有向圖和無向圖。

9、圖的生成樹是惟一的。

10、一個(gè)具有8個(gè)頂點(diǎn)的有向圖中，所有頂點(diǎn)的入度之和與所有頂點(diǎn)的出度之和的差等于0。

四、綜合題

1、寫出下圖中全部可能的拓?fù)渑判蛐蛄小?/p>

1——2——?3'~