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

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)練習(xí)第七章圖數(shù)據(jù)結(jié)構(gòu)練習(xí)第七章圖

一、選擇題

1.設(shè)有6個結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有()條邊才能確保是一個連通圖。A.5B.6C.7D.82.設(shè)某完全無向圖中有n個頂點(diǎn)，則該完全無向圖中有（）條邊。

22

A.n(n-1)/2B.n(n-1)C.nD.n-1

3．設(shè)某有向圖中有n個頂點(diǎn)，則該有向圖對應(yīng)的鄰接表中有（）個表頭結(jié)點(diǎn)。A.n-1B.nC.n+1D.2n-14．設(shè)無向圖G中有n個頂點(diǎn)e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個數(shù)分別為（）。

A.n，eBe，nC2n，eDn，2e5．設(shè)某強(qiáng)連通圖中有n個頂點(diǎn)，則該強(qiáng)連通圖中至少有（）條邊。

A.n(n-1)B.n+1C.nD.n(n+1)6．設(shè)某無向圖中有n個頂點(diǎn)e條邊，則該無向圖中所有頂點(diǎn)的入度之和為（）。A.nB.eC.2nD.2e

7．設(shè)某有向圖的鄰接表中有n個表頭結(jié)點(diǎn)和m個表結(jié)點(diǎn)，則該圖中有（）條有向邊。

A.nB.n-1C.mD.m-18．設(shè)連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為（）。A.abedfcB.acfebdC.aebdfcD.aedfcb9．設(shè)某無向圖中有n個頂點(diǎn)e條邊，則建立該圖鄰接表的時間繁雜度為（）。A.O(n+e)B.O(n2)C.O(ne)D.O(n3)10．設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為（）。A.第i行非0元素的個數(shù)之和B.第i列非0元素的個數(shù)之和C.第i行0元素的個數(shù)之和D.第i列0元素的個數(shù)之和

11．設(shè)某無向圖有n個頂點(diǎn)，則該無向圖的鄰接表中有（）個表頭結(jié)點(diǎn)。A.2nB.nC.n/2D.n(n-1)12．設(shè)無向圖G中有n個頂點(diǎn)，則該無向圖的最小生成樹上有（）條邊。A.nB.n-1C.2nD.2n-113．設(shè)無向圖的頂點(diǎn)個數(shù)為n，則該圖最多有（）條邊。A．n-1B．n(n-1)/2C．n(n+1)/2C．0

14．設(shè)有向無環(huán)圖G中的有向邊集合E={，，，}，則以下屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖牵ǎ?。A.1，2，3，4B.2，3，4，1C.1，4，2，3D.1，2，4，315．在一個具有n個頂點(diǎn)的無向圖中，要連通所有頂點(diǎn)則至少需要（）條邊。A．nB．2nC．n-1D．n+116．在一個圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（）倍。A．2B．1C．3D．4

1

17．在用鄰接表表示圖時,對圖進(jìn)行深度優(yōu)先探尋遍歷的算法的時間繁雜度為______。

A.Ｏ(n)B.Ｏ(n+e)C.Ｏ(n2)D.Ｏ(n3)

(b)在用鄰接表存儲圖時，故整個算法的時間繁雜度為O(n+e)。假使用鄰接矩陣表示圖，則算法的時間繁雜度就是O(n2)。

18．一個具有n個頂點(diǎn)的無向連通圖，它所包含的連通分量數(shù)為（）A.0B.1C.nD.不確定19．以下說法中不正確的是（）．．．A.無向圖的極大連通子圖稱為連通分量

B.連通圖的廣度優(yōu)先探尋中一般要采用隊列來暫存剛訪問過的頂點(diǎn)C.連通圖的深度優(yōu)先探尋中一般要采用棧來暫存剛訪問過的頂點(diǎn)D.有向圖的遍歷不可采用廣度優(yōu)先探尋算法20．鄰接矩陣為對稱矩陣的圖是()A.有向圖B.帶權(quán)有向圖C.有向圖或無向圖D.無向圖21．在一個具有n個頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要的邊數(shù)為()A.n-1B.n

C.n+1D.

n2

22．有4個頂點(diǎn)的無向完全圖的邊數(shù)為()

A.6B.12C.16D.20

?0?23．設(shè)圖的鄰接矩陣為?0?0?1011??1?0??，則該圖為()

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

24．在一個具有n個頂點(diǎn)的無向圖中，每個頂點(diǎn)度的最大值為（）

A．nB.n-1C.n+1D.2(n-1)25．關(guān)于無向圖的鄰接矩陣的說法中正確的是（）A．矩陣中非全零元素的行數(shù)等于圖中的頂點(diǎn)數(shù)

B.第i行上與第i列上非零元素總和等于頂點(diǎn)Vi的度數(shù)C.矩陣中的非零元素個數(shù)等于圖的邊數(shù)

D.第i行上非零元素個數(shù)和第i列上非零元素個數(shù)一定相等26．有n個結(jié)點(diǎn)的有向完全圖的弧數(shù)是（）A.n2B.2nC.n(n-1)D.2n(n+1)27．設(shè)圖的鄰接鏈表如題12圖所示，則該圖的邊的數(shù)目是（）

題12圖

A.4B.5C.10D.20

28．若采用鄰接表存儲結(jié)構(gòu)，則圖的深度優(yōu)先探尋類似于二叉樹的（）A.先根遍歷B.中根遍歷C.后根遍歷D.層次遍歷

2

29．具有n個頂點(diǎn)的無向圖，若要連通全部頂點(diǎn)，至少需要（）

A.（n-1）條邊B.n條邊C.n(n-1)條邊D.n(n-1)/2條邊30．一個帶權(quán)的無向連通圖的最小生成樹（）

A．有一棵或多棵B．只有一棵C．一定有多棵D．可能不存在31．以下有關(guān)圖遍歷的說法中不正確的是（）A．連通圖的深度優(yōu)先探尋是一個遞歸過程

B．圖的廣度優(yōu)先探尋中鄰接點(diǎn)的尋覓具有“先進(jìn)先出〞的特征C．非連通圖不能用深度優(yōu)先探尋法

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

32．設(shè)有向圖有n個頂點(diǎn)和e條邊，采用領(lǐng)接表作為其存儲表示，在進(jìn)行拓?fù)渑判驎r，總的計算時間為（）。

A．O（nlog2e）B．O（n+e）C．O(ne)D．O(n2)33．在一個無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（）倍。

A．3B．2C．1D．1/234．圖中有關(guān)路徑的定義是（A）。

A．由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列B．由不同頂點(diǎn)所形成的序列

C．由不同邊所形成的序列D．上述定義都不是35．要連通具有n個頂點(diǎn)的有向圖，至少需要（B）條邊。

A．n-lB．nC．n+lD．2n

36．一個有n個結(jié)點(diǎn)的圖，最少有（B）個連通分量，最多有（D）個連通分量。

A．0B．1C．n-1D．n

37．在一個無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（B）倍，在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（C）倍。A．1/2B．2C．1D．438．用鄰接表存儲圖所用的空間大小（A）。

A.與圖的頂點(diǎn)數(shù)和邊數(shù)都有關(guān)B.只與圖的邊數(shù)有關(guān)C.只與圖的頂點(diǎn)數(shù)有關(guān)D.與邊數(shù)的平方有關(guān)39．圖的BFS生成樹的樹高比DFS生成樹的樹高（A）

A.小或相等B.小C.大或相等D.大40．以下說法不正確的是（C）。

A．圖的遍歷是從給定的源點(diǎn)出發(fā)每個頂點(diǎn)僅被訪問一次B．遍歷的基本方法有兩種：深度遍歷和廣度遍歷C．圖的深度遍歷不適用于有向圖D．圖的深度遍歷是一個遞歸過程

41．無向圖G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，對該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（D）。A．a(chǎn),b,e,c,d,fB．a(chǎn),c,f,e,b,dC．a(chǎn),e,b,c,f,dD．a(chǎn),e,d,f,c,b42．在圖采用鄰接表存儲時，求最小生成樹的Prim算法的時間繁雜度為(B)。

A.O(n)B.O(n+e)C.O(n2)D.O(n3)

43．在有向圖的鄰接表存儲結(jié)構(gòu)中，頂點(diǎn)v在鏈表中出現(xiàn)的次數(shù)是(B)。

3

A.頂點(diǎn)v的度B.頂點(diǎn)v的出度C.頂點(diǎn)v的入度D.依附于頂點(diǎn)v的邊數(shù)

44．(1).求從指定源點(diǎn)到其余各頂點(diǎn)的迪杰斯特拉（Dijkstra）最短路徑算法中弧上權(quán)不能為負(fù)的原因是在實(shí)際應(yīng)用中無意義；

(2).利用Dijkstra求每一對不同頂點(diǎn)之間的最短路徑的算法時間是O(n3)；（圖用鄰接矩陣表示）

(3).Floyed求每對不同頂點(diǎn)對的算法中允許弧上的權(quán)為負(fù)，但不能有權(quán)和為負(fù)的回路。

上面不正確的是（C）。

A．(1),(2),(3)B．(1)C．(1),(3)D．(2),(3)45．當(dāng)各邊上的權(quán)值(A)時，BFS算法可用來解決單源最短路徑問題。A．均相等B．均互不相等C．不一定相等

46．在有向圖G的拓?fù)湫蛄兄校繇旤c(diǎn)Vi在頂點(diǎn)Vj之前，則以下情形不可能出現(xiàn)的是（D）。

A．G中有弧B．G中有一條從Vi到Vj的路徑C．G中沒有弧D．G中有一條從Vj到Vi的路徑47．關(guān)鍵路徑是AOE網(wǎng)中(B)

A.從始點(diǎn)到終點(diǎn)的最短路徑B.從始點(diǎn)到終點(diǎn)的最長路徑

C.從始點(diǎn)到終點(diǎn)的邊數(shù)最多的路徑D.從始點(diǎn)到終點(diǎn)的邊數(shù)最少的路徑48．以下關(guān)于AOE網(wǎng)的表達(dá)中，不正確的是（B）。A．關(guān)鍵活動不按期完成就會影響整個工程的完成時間

B．任何一個關(guān)鍵活動提前完成，那么整個工程將會提前完成C．所有的關(guān)鍵活動提前完成，那么整個工程將會提前完成D．某些關(guān)鍵活動若提前完成，那么整個工程將會提前完成49．以下有關(guān)圖的說法錯誤的是（C）A．在有向圖中，出度為0的結(jié)點(diǎn)稱為葉子。

B．用鄰接矩陣表示圖，簡單判斷任意兩個結(jié)點(diǎn)之間是否有邊相連，并求得各結(jié)點(diǎn)的度。

C．按深度方向遍歷圖和先根次序遍歷樹類似，得到的結(jié)果是唯一的。

D．若有向圖G中從結(jié)點(diǎn)Vi到結(jié)點(diǎn)Vj有一條路徑，則在圖G的結(jié)點(diǎn)的線性序列中結(jié)點(diǎn)Vi必在結(jié)點(diǎn)Vj之前的話，則稱為一個拓?fù)湫蛄小?0．n個頂點(diǎn)的無向圖的鄰接表最多有(B)個表結(jié)點(diǎn)。

A．n2B．n(n-1)C．n(n+1)D．n(n-1)/251．設(shè)無向圖的頂點(diǎn)個數(shù)n，則該無向圖最多有（B）條邊

A．n-1B．n(n-1)/2C．n(n+1)/2D．052．采用鄰接表存儲的圖，其DFS類似于二叉樹的（B）

A．中序遍歷B．先序遍歷C．后序遍歷D．按層次遍歷53．用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時打印相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是(A)。

A．逆拓?fù)溆行駼．拓?fù)溆行駽．無序的

54．要連通具有n個頂點(diǎn)的有向圖，至少需要（B）條邊。

A．n-lB．nC．n+lD．2n55.以下說法不正確的是（C）。

A．圖的遍歷是從給定的源點(diǎn)出發(fā)每個頂點(diǎn)僅被訪問一次

4

B．遍歷的基本方法有兩種：深度遍歷和廣度遍歷C．圖的深度遍歷不適用于有向圖D．圖的深度遍歷是一個遞歸過程

56.圖的BFS生成樹的樹高比DFS生成樹的樹高（A）

A.小或相等B.小C.大或相等D.大57.設(shè)無向圖的頂點(diǎn)個數(shù)為n，則該圖最多有（B）條邊。

A．n-1B．n(n-1)/2C．n(n+1)/2D．0

58.在一個具有n個頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度數(shù)之和為s，則所有頂點(diǎn)的入度數(shù)之和為(A)。

A.sB.s-1C.s+1D.n

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

A.sB.s-1C.s+1D.2s

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

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

61.在一個具有n個頂點(diǎn)的無向完全圖中，則所含的邊數(shù)為(C)。A.nB.n(n-1)C.n(n-1)/2D.n(n+1)/262.在一個具有n個頂點(diǎn)的有向完全圖中，則所含的邊數(shù)為(B)。A.nB.n(n-1)C.n(n-1)/2D.n(n+1)/2

63.在一個無權(quán)圖中，若兩頂點(diǎn)之間的路徑長度為k，則該路徑上的頂點(diǎn)數(shù)為(B)。

A.kB.k+1C.k+2D.2k

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

A.0B.1C.nD.n+1

65.若一個圖中包含有k個連通分量，若要依照深度優(yōu)先探尋的方法訪問所有頂點(diǎn)