數(shù)據(jù)結(jié)構(gòu)(圖)習(xí)題與答案

一、單選題

1、設(shè)有5個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有__________條邊才干確保是一個(gè)連通圖。

A.7

B.8

C.6

D.5

正確答案：A

2、設(shè)圖G=(V,VR),其中:V={A,B,C,D,G),

VR={(A,C),(A,D)/(B,C),(B,D),(G,C),(B,G)},則對(duì)應(yīng)的圖形為。

正確答案：C

3、設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有個(gè)表頭結(jié)點(diǎn)。

A.n-1

B.n+2

C.n

D.n+1

正確答案：c

4、在一個(gè)無向圖中所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的_________倍。

A.1

B.2

C.3

D.1/2

正確答案：B

5、一個(gè)無向連通圖的生成樹是該連通圖的.

A.極小連通子圖

B.強(qiáng)連通子圖

C.連通子圖

D.極大連通子圖

正確答案：A

6、設(shè)某無向圖中有n個(gè)頂點(diǎn)，則該無向圖鄰接矩陣的大小是_________。

A.n(n+l)/2

B.(n-1)2

C.ri2

D.(n+1)2

正確答案：C

7、設(shè)有n個(gè)頂點(diǎn)e條邊的無向圖，采用鄰接矩陣作為物理結(jié)構(gòu)，則刪除與某頂點(diǎn)V)

關(guān)聯(lián)的所有邊算法的時(shí)間復(fù)雜度為。

A.Og)

B.O(n+e)

C.O(n*e)

D.O(n)

正確答案：D

8、設(shè)有n個(gè)頂點(diǎn)e條弧的有向圖，采用鄰接表作為物理結(jié)構(gòu)，則求某頂點(diǎn)Vi度的算

法的時(shí)間復(fù)雜度為。

A.O(n)

B.O(n*e)

C.O(n+e)

D.0(ri2)

正確答案：C

9、設(shè)無向圖G=(V,E)和G'=(V',E'),如果G'是G的生成樹，則下列說法中錯(cuò)誤的是

A.G，是G的連通分量

B.G，是G的一個(gè)無環(huán)子圖

C.G'是G的極小連通子圖且V=V'

D.G'是G的子圖

正確答案：A

10、設(shè)G是一個(gè)非連通的無向圖，共有10條邊，則該圖至少有_____個(gè)頂點(diǎn)。

A.7

B.6

C.5

D.8

正確答案：B

11、n個(gè)頂點(diǎn)的有向圖為強(qiáng)連通圖時(shí)，至少含有________。

A.n條弧

B.n(n-l)/2條弧

C.n(n-l)條弧

D.n-1條弧

正確答案：A

12、如果從無向圖的一個(gè)頂點(diǎn)出發(fā)，進(jìn)行一次深度優(yōu)先搜索能訪問所有頂點(diǎn)，則該無

向圖是一O

A.連通圖

B.強(qiáng)連通圖

C.徹底圖

D.DAG圖

正確答案：A

13、如圖所示的有向圖，共有________個(gè)強(qiáng)連通分量。

A.2

B.1

C.4

D.3

正確答案：A

14、在下圖中，從頂點(diǎn)A出發(fā)進(jìn)行深度優(yōu)先遍歷可得到的序列是

A.ADCBG

B.ABDCG

C.ACDBG

D.ADGBC

正確答案：B

15、對(duì)圖進(jìn)行深度優(yōu)先搜索遍歷，需要借助的數(shù)據(jù)結(jié)構(gòu)為

A.隊(duì)列

B.廣義表

C.棧

D.線索二叉樹

正確答案：C

16、對(duì)圖進(jìn)行廣度優(yōu)先搜索遍歷，需要借助的數(shù)據(jù)結(jié)構(gòu)為

A.廣義表

B.線索二叉樹

C.棧

D.隊(duì)列

正確答案：D

17、最小生成樹是指o

A.連通網(wǎng)的極小連通子圖

B.由連通網(wǎng)得到的邊數(shù)至少的生成樹

C.由連通網(wǎng)得到的頂點(diǎn)數(shù)相對(duì)較少的生成樹

D.連通網(wǎng)的所有生成樹中權(quán)值之和最小的生成樹

正確答案：D

18、在下圖中，從頂點(diǎn)A出發(fā)進(jìn)行廣度優(yōu)先遍歷可得到的序列是__________.

A.AGBDC

B.ADGBC

C.ADCBG

D.ACDGB

正確答案：C

19、對(duì)如圖所示的無向連通網(wǎng)，從頂點(diǎn)A出發(fā)，使用Prim算法得到的最小生成樹是

正確答案：D

20、可借助于__________判別有向圖中是否存在回路。

A.PRIM算法

B.迪杰斯特拉算法

C.FLOYD算法

D.拓?fù)渑判蛩惴?/p>

正確答案：D

21、如圖所示的DAG圖，其拓?fù)渑判蛐蛄袨?/p>

A.ADBGC

B.ADGBC

C.AGBDC

D.ACDGB

正確答案：A

22、下列關(guān)于工程計(jì)劃的AOE網(wǎng)的敘述中,不正確的是_________o

A.某個(gè)關(guān)鍵活動(dòng)提前完成，可能會(huì)提前整個(gè)工程的完成時(shí)間

B.任何一個(gè)關(guān)鍵活動(dòng)的提前完成，整個(gè)工程的完成時(shí)間都會(huì)提前

C.關(guān)鍵活動(dòng)不按期完成，會(huì)影響整個(gè)工程的完成時(shí)間

D.所有關(guān)鍵活動(dòng)都提前完成，會(huì)提前整個(gè)工程的完成時(shí)間

正確答案：B

23、使用迪杰斯特拉最短路徑算法，求一個(gè)源點(diǎn)到其它各頂點(diǎn)的最短路徑，該算法的

時(shí)間復(fù)雜度為?

A.O(nlogn)

B.0(n2)

C.0(n3)

D.O(logn2)

正確答案：B

24、使用弗洛伊德算法，求任意2個(gè)頂點(diǎn)的最短路徑，該算法的時(shí)間復(fù)雜度為

A.0(nlogn)

B.O(n2)

C.0(n3)

D.O(logn2)

正確答案：C

25、某無向圖的鄰接矩陣如下所示,可以得出，該圖共有__________個(gè)頂點(diǎn)。

010

101

.010.

A.9

B.5

C.3

D.4

正確答案：C

二、判斷題

1、如果n（n>2）個(gè)頂點(diǎn)的有向圖有二個(gè)強(qiáng)連通分量，則至少有n-1條弧。（V）

2、n個(gè)頂點(diǎn)的無向圖，至少需要n條邊才可能是連通圖。（x）

3、連通分量是指無向圖的極小連通子圖。（x）

4、無向圖的鄰接矩陣必然是對(duì)稱矩陣。（V）

5、有n（n>l）個(gè)頂點(diǎn)，-2n+2條弧的有向圖不一定是強(qiáng)連通圖。（x）

6、圖的鄰接矩陣大小，非但與圖的頂點(diǎn)數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。（x）

7、使用有向圖的十字鏈表，能非常方便地計(jì)算出任意一個(gè)頂點(diǎn)的出度和入度。（V）

8、一個(gè)有n個(gè)頂點(diǎn)e條邊的無向圖的鄰接表中，有2e個(gè)表結(jié)點(diǎn)。（V）

9、一個(gè)有n個(gè)頂點(diǎn)e條邊的無向圖的鄰接多重表中，有2e個(gè)表結(jié)點(diǎn)。（x）

10、一個(gè)有n個(gè)頂點(diǎn)e條弧的有向圖的逆鄰接表中，有2e個(gè)表結(jié)點(diǎn)。（x）

11.一個(gè)有向圖的鄰接表和逆鄰接表中的表結(jié)點(diǎn)個(gè)數(shù)一定相等。（V）

12、有向圖有n個(gè)頂點(diǎn)e條弧，采用鄰接表存儲(chǔ)，則計(jì)算某頂點(diǎn)度的算法需要訪問

n+e個(gè)單鏈表的表結(jié)點(diǎn)。（x）

13、鄰接表的空間復(fù)雜度為，與邊（或者弧）的條數(shù)無關(guān)。（x）

14、對(duì)于一個(gè)連通圖，通過一次深度優(yōu)先遍歷，能訪問到所有頂點(diǎn)。（V）

15、從無向圖的任一頂點(diǎn)出發(fā)，進(jìn)行一次廣度優(yōu)先搜素，都能訪問到圖的所有頂點(diǎn)。

（x）

16、對(duì)于一個(gè)連通圖，有惟一的一棵深度優(yōu)先遍歷生成樹。（x）

17、當(dāng)無向連通網(wǎng)中的邊較少時(shí)，采用prim算法求其最小生成樹效率較高。（x）

18、Kruskal算法適合求解邊稠密圖的最小生成樹。（x）

19、某無向連通網(wǎng)惟獨(dú)惟一的一棵最小生成樹，則該無向連通網(wǎng)個(gè)邊上的權(quán)值互不相

同。（x）

20、可以借助于拓?fù)渑判蛩惴▉砼袛嘁粋€(gè)有向圖是否有回路。（V）

21、在某AOV網(wǎng)中，頂點(diǎn)Vi到頂點(diǎn)Vj有路徑，則該AOV網(wǎng)的任何拓?fù)渑判蛐蛄兄校?/p>

Vi一定排在Vj的前面。（V）

22、需要借助于深度優(yōu)先遍歷算法來求得AOE網(wǎng)的關(guān)鍵路徑。（x）

23、在某AOE網(wǎng)中，ak是從