數據結構(圖)習題與答案

一、單選題

1、設有5個結點的無向圖，該圖至少應有__________條邊才干確保是一個連通圖。

A.7

B.8

C.6

D.5

正確答案：A

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

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

正確答案：C

3、設某有向圖中有n個頂點，則該有向圖對應的鄰接表中有個表頭結點。

A.n-1

B.n+2

C.n

D.n+1

正確答案：c

4、在一個無向圖中所有頂點的度數之和等于所有邊數的_________倍。

A.1

B.2

C.3

D.1/2

正確答案：B

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

A.極小連通子圖

B.強連通子圖

C.連通子圖

D.極大連通子圖

正確答案：A

6、設某無向圖中有n個頂點，則該無向圖鄰接矩陣的大小是_________。

A.n(n+l)/2

B.(n-1)2

C.ri2

D.(n+1)2

正確答案：C

7、設有n個頂點e條邊的無向圖，采用鄰接矩陣作為物理結構，則刪除與某頂點V)

關聯(lián)的所有邊算法的時間復雜度為。

A.Og)

B.O(n+e)

C.O(n*e)

D.O(n)

正確答案：D

8、設有n個頂點e條弧的有向圖，采用鄰接表作為物理結構，則求某頂點Vi度的算

法的時間復雜度為。

A.O(n)

B.O(n*e)

C.O(n+e)

D.0(ri2)

正確答案：C

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

A.G，是G的連通分量

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

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

D.G'是G的子圖

正確答案：A

10、設G是一個非連通的無向圖，共有10條邊，則該圖至少有_____個頂點。

A.7

B.6

C.5

D.8

正確答案：B

11、n個頂點的有向圖為強連通圖時，至少含有________。

A.n條弧

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

C.n(n-l)條弧

D.n-1條弧

正確答案：A

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

向圖是一O

A.連通圖

B.強連通圖

C.徹底圖

D.DAG圖

正確答案：A

13、如圖所示的有向圖，共有________個強連通分量。

A.2

B.1

C.4

D.3

正確答案：A

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

A.ADCBG

B.ABDCG

C.ACDBG

D.ADGBC

正確答案：B

15、對圖進行深度優(yōu)先搜索遍歷，需要借助的數據結構為

A.隊列

B.廣義表

C.棧

D.線索二叉樹

正確答案：C

16、對圖進行廣度優(yōu)先搜索遍歷，需要借助的數據結構為

A.廣義表

B.線索二叉樹

C.棧

D.隊列

正確答案：D

17、最小生成樹是指o

A.連通網的極小連通子圖

B.由連通網得到的邊數至少的生成樹

C.由連通網得到的頂點數相對較少的生成樹

D.連通網的所有生成樹中權值之和最小的生成樹

正確答案：D

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

A.AGBDC

B.ADGBC

C.ADCBG

D.ACDGB

正確答案：C

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

正確答案：D

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

A.PRIM算法

B.迪杰斯特拉算法

C.FLOYD算法

D.拓撲排序算法

正確答案：D

21、如圖所示的DAG圖，其拓撲排序序列為

A.ADBGC

B.ADGBC

C.AGBDC

D.ACDGB

正確答案：A

22、下列關于工程計劃的AOE網的敘述中,不正確的是_________o

A.某個關鍵活動提前完成，可能會提前整個工程的完成時間

B.任何一個關鍵活動的提前完成，整個工程的完成時間都會提前

C.關鍵活動不按期完成，會影響整個工程的完成時間

D.所有關鍵活動都提前完成，會提前整個工程的完成時間

正確答案：B

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

時間復雜度為?

A.O(nlogn)

B.0(n2)

C.0(n3)

D.O(logn2)

正確答案：B

24、使用弗洛伊德算法，求任意2個頂點的最短路徑，該算法的時間復雜度為

A.0(nlogn)

B.O(n2)

C.0(n3)

D.O(logn2)

正確答案：C

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

010

101

.010.

A.9

B.5

C.3

D.4

正確答案：C

二、判斷題

1、如果n（n>2）個頂點的有向圖有二個強連通分量，則至少有n-1條弧。（V）

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

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

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

5、有n（n>l）個頂點，-2n+2條弧的有向圖不一定是強連通圖。（x）

6、圖的鄰接矩陣大小，非但與圖的頂點數有關，而且與圖的邊數也有關。（x）

7、使用有向圖的十字鏈表，能非常方便地計算出任意一個頂點的出度和入度。（V）

8、一個有n個頂點e條邊的無向圖的鄰接表中，有2e個表結點。（V）

9、一個有n個頂點e條邊的無向圖的鄰接多重表中，有2e個表結點。（x）

10、一個有n個頂點e條弧的有向圖的逆鄰接表中，有2e個表結點。（x）

11.一個有向圖的鄰接表和逆鄰接表中的表結點個數一定相等。（V）

12、有向圖有n個頂點e條弧，采用鄰接表存儲，則計算某頂點度的算法需要訪問

n+e個單鏈表的表結點。（x）

13、鄰接表的空間復雜度為，與邊（或者弧）的條數無關。（x）

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

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

（x）

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

17、當無向連通網中的邊較少時，采用prim算法求其最小生成樹效率較高。（x）

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

19、某無向連通網惟獨惟一的一棵最小生成樹，則該無向連通網個邊上的權值互不相

同。（x）

20、可以借助于拓撲排序算法來判斷一個有向圖是否有回路。（V）

21、在某AOV網中，頂點Vi到頂點Vj有路徑，則該AOV網的任何拓撲排序序列中，

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

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

23、在某AOE網中，ak是從