數(shù)據(jù)結(jié)構(gòu)-圖（選擇題）

數(shù)據(jù)結(jié)構(gòu)——圖（選擇題）

1.在一個有向圖中，所有頂點的入度和等于所有結(jié)點的出度之和的（）倍。

簡單，圖的基本概念，02707001［單選題］*

A、1/2

B、1（正確答案）

C、2

D、4

2.對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大

小為0o

簡單，圖的鄰接表存儲，（）27（）7003［單選題］*

A、n

B、n+1

C、n-1

D、n+e

3.具有n個頂點的無向完全圖，邊的總數(shù)為（）條。

簡單，圖的基本概念，02707001［單選題］*

A、n-1

B、n

C、n+1

D、n*（n-l）/2（正確答案）

4.設(shè)圖G有n個頂點和e條邊，當(dāng)G是非孤立頂點的連通圖時，有2史n,故可推

得深度優(yōu)先搜索的時間復(fù)雜度為()O

簡單，圖的遍歷，02707006［單選題］*

A、O(e)(正確答案)

B、O(n)

C、O(ne)

D、O(n+e)

5.最小代價生成樹()。

簡單，最小生成樹，02707007［單選題］*

A、是唯一的

B、不是唯一的

C、唯一性不確定

D、唯一性與原樹的邊的權(quán)數(shù)有關(guān)

6.在無向圖G的鄰接矩陣A中，若等于1,則等于()o

簡單，圖的鄰接矩陣存儲，()2707()02［單選題］*

A、i+j

B、i-j

C、1

D、0

7.圖的深度優(yōu)先或廣度優(yōu)先遍歷的空間復(fù)雜性均為()。(訪問標(biāo)志位數(shù)組空間)

簡單，圖的遍歷，()2707006［單選題］*

A、O(n)：確答案?

B、0(e)

C、O(n-e)

D、O（n+e）

8.在一個具有n個頂點的有向圖中，若所有頂點的出度數(shù)之和為s,則所有頂點的

入度數(shù)之和為（）O

簡單,圖的基本概念,02707001［單選題］*

A、s；

B、s-1

C、s+1

D、N'

9.在一個具有n個頂點的有向圖中，若所有頂點的出度數(shù)之和為s,則所有頂點的

度數(shù)之和為（）。

簡單，圖的基本概念，02707001［單選題］*

A、s

B、s-1

C、s+1

D、2s（正確答案）

10.在一個具有n個頂點的無向圖中，若具有e條邊，則所有頂點的度數(shù)之和為

（）。

簡單，圖的基本概念，（）2707001［單選題］*

A、n

B、e

C、n+e

D、2e（正確答案）

11.在一個具有n個頂點的無向完全圖中，所含的邊數(shù)為（）。

簡單，圖的基本概念，02707001［單選題］*

A、n

B、n（n-l）

C、n（n-l）/2

D、n（n+l）/2

12.在一個無向圖中，若兩頂點之間的路徑長度為k,則該路徑上的頂點數(shù)為（）。

簡單，圖的遍歷，02707006］單選題］*

A、k

B、k+1（正確答案）

C、k+2

D、2k

13.對于一個具有n個頂點的無向連通圖，它包含的連通分量的個數(shù)為（）。

無向圖G的極大連通子圖稱為G的連通分量（ConnectedComponent）o任何連通圖

的連通分量只有一個，即是其自身，非連通的無向圖有多個連通分量。

簡單，圖的基本概念，02707001［單選題］*

A、0

B、1（正確答案）

C、n

D、n+1

14.若一個圖中包含有k個連通分量，若要按照深度優(yōu)先搜索的方法訪問所有頂

點，則必須調(diào)用（）次深度優(yōu)先搜索遍歷的算法。

簡單，圖的遍歷，（）2707006［單選題］*

A、k（正確答案）

B、1

C、k-1

D、k+1

15.若要把n個頂點連接為一個連通圖，則至少需要()條邊。

簡單，圖的基本概念，02707001［單選題］*

A、n

B、n+1

C、n-l(正確答案)

D、2n

16.在一個具有n個頂點和e條邊的無向圖的鄰接矩陣中，表示邊存在的元素(又稱

為有效元素)的個數(shù)為()O

簡單，圖的鄰接矩陣存儲，027()7002［單選題］*

A、n

B、nxe

C、e

D、2xe

17.在一個具有n個頂點和e條邊的有向圖的鄰接矩陣中，表示邊存在的元素個數(shù)

為0o

簡單，圖的鄰接矩陣存儲，()2707()02［單選題］*

A、n

B、nxe

C、e

D、2xe

18.在一個具有n個頂點和e條邊的有向圖的鄰接表中，保存頂點單鏈表的表頭指

針向量的大小至少為()O

簡單，圖的鄰接表存儲，02707003［單選題］*

A、n

B、2n

C、e

D、2e

19.在一個無權(quán)圖的鄰接表示中，每個邊結(jié)點至少包含（）域。

簡單，圖的鄰接表存儲，02707003［單選題］*

A、1

B、2（正確答案）

C、3

D、4

20.對于一個有向圖，若一個頂點的度為kl,出度為k2,則對應(yīng)鄰接表中該頂點單

鏈表中的邊結(jié)點數(shù)為（）。

簡單，圖的基本概念，02707001［單選題］*

A、kl

B、k2

C、kl-k2

D、kl+k2

21.對于一個有向圖，若一個頂點的度為kl,出度為k2,則對應(yīng)逆鄰接表中該頂點

單鏈表中的邊結(jié)點數(shù)為（）O

簡單，圖的鄰接表存儲，（）2707003［單選題］*

A、kl

B、k2

C、kl-k2

D、kl+k2

22.對于一個無向圖，下面()種說法是正確的。

簡單，圖的基本概念，02707001［單選題］*

A、每個頂點的入度等于出度

B、每個頂點的度等于其入度與出度之和

C、每個頂點的入度為。

D、每個頂點的出度為0

23.在一個有向圖的鄰接表中，每個頂點單鏈表中結(jié)點的個數(shù)等于該頂點的()o

簡單，圖的鄰接表存儲，()27()7003［單選題］*

A、出度數(shù)(正確答案)

B、入度數(shù)

C、度數(shù)

D、度數(shù)減1

24.若一個圖的邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},則從頂點A開始對該

圖進(jìn)行深度優(yōu)先搜索，得到的頂點序列可能為()O

簡單，圖的遍歷，02707006［單選題］*

A、A,B,C,F,D,E

B、A,C,F,D,E,B(正確答案)

C、A,B,D,C,F,E

D、A,B,D,F,E,C

25.若一個圖的邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},則從頂點A開始對該

圖進(jìn)行廣度優(yōu)先遍歷，得到的頂點序列可能為0O

簡單，圖的遍歷，02707006［單選題］*

A、A,B,C,D,E,F

B、A,B,C,F,D,E

C、A,B,D,C,E,F

D、A,C,B,F,D,ED答案）

26.若一個圖的邊集為{<1,2>,<1,4>,<2,5>,<3/>,<3,5>,<4,3>},則從頂點1開始對該

圖進(jìn)行深度優(yōu)先遍歷，得到的頂點序列可能是（）O

有向圖

簡單，圖的遍歷，02707006］單選題］*

A、125,4,3確答案）

B、1,2,3,4,5

C、1,2,5,3,4

D、1,4,325

27.若一個圖的邊集為{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},則從頂點1開始對該

圖進(jìn)行廣度優(yōu)先搜索，得到的頂點序列可能為（）O

有向圖

簡單，圖的遍歷，02707006［單選題］*

A、1,2,3,4,5

B、1,2,4,3,5

C、1,2,4,5,3（正確答案）

D、1,4,2,5,3

28.由一個具有n個頂點的連通圖生成的最小生成樹中，具有（）條邊。

簡單，最小生成樹，02707（）07［單選題］*

A、n

B、n-1溝答案）

C、n+1

D、2xn

29.已知一個有向圖的邊集為{<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>},則由該圖產(chǎn)生

的一種可能的拓?fù)湫蛄袨椋ǎ㎡

一般，拓?fù)渑判蚝完P(guān)鍵路徑，02707009［單選題］*

A、a,b,c,d,e

B