2023年圖練習題及答案

第七章圖一、單選題（C）1.在一個圖中，所有頂點的度數之和等于圖的邊數的倍。A．1/2B.1C.2D.42.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（B）倍。A．1/2B.1C.2D.4（B）3.有8個結點的無向圖最多有條邊。A．14B.28C.56D.（A）一個n個頂點的連通無向圖，其邊的個數至少為（）。A．n-1B．nC．n+1D．nlogn；（C）5.有8個結點的有向完全圖有條邊。A．14B.28C.56D.（B）6.用鄰接表表達圖進行廣度優(yōu)先遍歷時，通常是采用來實現算法的。A．棧B.隊列C.樹D.圖（A）7.用鄰接表表達圖進行深度優(yōu)先遍歷時，通常是采用來實現算法的。A．棧B.隊列C.樹D.圖8.下面關于求關鍵途徑的說法不對的的是（

C）。

A．求關鍵途徑是以拓撲排序為基礎的

B．一個事件的最早開始時間同以該事件為尾的弧的活動最早開始時間相同

C．一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該活動的連續(xù)時間的差

D．關鍵活動一定位于關鍵途徑上9.已知圖的鄰接矩陣如下，根據算法思想，則從頂點0出發(fā)，按深度優(yōu)先遍歷的結點序列是（D）A．0243156B.0135642C.0423165D.013425610、設數據結構A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>，<4,2>}，則數據結構A是（C）。 (A)線性結構 (B)樹型結構 (C)圖型結構 (D)集合（C）11.已知圖的鄰接矩陣同上題9，根據算法，則從頂點0出發(fā)，按廣度優(yōu)先遍歷的結點序列是A．0243165B.0135642C.0123465D.012345612.已知圖的鄰接表如下所示，根據算法，則從頂點0出發(fā)按深度優(yōu)先遍歷的結點序列是（D）A．0132B.A．0132B.0231C.0321D.0123（A）13.已知圖的鄰接表如下所示，根據算法，則從頂點0出發(fā)按廣度優(yōu)先遍歷的結點序列是A．0321B.A．0321B.0123C.0132D.0312（A）14.深度優(yōu)先遍歷類似于二叉樹的A．先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷（D）15.廣度優(yōu)先遍歷類似于二叉樹的A．先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷（D）16、下面結構中最適于表達稀疏無向圖的是。A．鄰接矩陣B．逆鄰接表C．十字鏈表D．鄰接表（B）17、下列哪一種圖的鄰接矩陣是對稱矩陣？A．有向圖B．無向圖C．AOV網D．AOE網18、在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數為(Ｄ)A．eB．2eC．n2－eD．n2－2e19、下列關于無向連通圖特性的敘述中，對的的是

（A）I．所有頂點的度之和為偶數

II.邊數大于頂點個數減1

III.至少有一個頂點的度為1

A.只有I

B.

只有II

C.I和II

D.I和III

20、假設一個有n個頂點和e條弧的有向圖用鄰接表表達,則刪除與某個頂點vi相關的所有弧的時間復雜度是(Ｃ)A．O(n)B．O(e)C．O(n+e)D．O(n*e)21、無向圖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)}，對該圖進行深度優(yōu)先遍歷，得到的頂點序列對的的是（

）。A．a,b,e,c,d,f

B．a,c,f,e,b,d

C．a,e,b,c,f,d

D．a,e,d,f,c,b22、在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前，則下列情形不也許出現的是（

D

）。

A．G中有弧<Vi，Vj>

B．G中有一條從Vi到Vj的途徑C．G中沒有弧<Vi,Vj>

D．G中有一條從Vj到Vi的途徑

23、下面哪一方法可以判斷出一個有向圖是否有環(huán)（回路）(B)A．深度優(yōu)先遍歷

B.拓撲排序

C.求最短途徑

D.求關鍵途徑24、下列關于AOE網的敘述中，不對的的是（

B

）。A．關鍵活動不按期完畢就會影響整個工程的完畢時間B．任何一個關鍵活動提前完畢，那么整個工程將會提前完畢C．所有的關鍵活動提前完畢，那么整個工程將會提前完畢D．某些關鍵活動提前完畢，那么整個工程將會提前完畢25、設無向圖G中有n個頂點e條邊，則其相應的鄰接表中的表頭結點和表結點的個數分別為（D）。 (A)n，e (B)e，n (C)2n，e (D)n，2e二、填空題1.圖有鄰接矩陣、鄰接表、十字鏈表、鄰接多重表等存儲結構，其中鄰接矩陣、鄰接表既用于存儲有向圖，也用于存儲無向圖。遍歷圖深度優(yōu)先遍歷、廣度優(yōu)先遍歷等方法。2.有向圖G用鄰接表矩陣存儲，其第i行的所有元素之和等于頂點i的出度。3.拓撲排序算法是通過反復選擇具有0個前驅頂點的過程來完畢的。4.n個頂點e條邊的圖，若采用鄰接矩陣存儲，則空間復雜度為O(n2)，若采用鄰接表存儲，則空間復雜度為O(n+e)。5.n個頂點e條邊的圖采用鄰接矩陣存儲，廣度優(yōu)先遍歷算法的時間復雜度為O(n2)；若采用鄰接表存儲，該算法的時間復雜度為O(n+e)。6.設有一稀疏圖G，則G采用鄰接表存儲較省空間，設有一稠密圖G，則G采用鄰接矩陣存儲較省空間。7.n個頂點的連通無向圖，其邊的條數至少為__n-1____。若用n表達圖中頂點數目，則有___n(n-1)/2____條邊的無向圖成為完全圖。8.具有8個頂點的有向完全圖有56條弧。具有10個頂點的無向圖，邊的總數最多為_45_。9.在無向圖G的鄰接矩陣A中，若A[i][j]等于1，則A[j][i]等于1。10.G是一個非連通無向圖，共有28條邊，則該圖至少有_9_個頂點。11.為了實現圖的廣度優(yōu)先搜索，除了一個標志數組標志已訪問的圖的結點外，還需_隊列存放被訪問的結點以實現遍歷。12.一無向圖G（V，E），其中V（G）={1,2,3,4,5,6,7}，E（G）={（1,2）,(1,3），（2,4），（2,5），（3,6），（3,7），（6,7）（5,1）},對該圖從頂點3開始進行遍歷，去掉遍歷中未走過的邊，得一生成樹G’(V，E’）,V（G’）=V（G），E（G’）={（1,3），（3,6），（7,3），（1,2），（1,5），（2,4）}，則采用的遍歷方法是___廣度優(yōu)先遍歷___13.在圖G的鄰接表表達中，每個頂點鄰接表中所含的結點數，對于無向圖來說等于該頂點的_度_；對于有向圖來說等于該頂點的_出度_。14.已知一無向圖G=（V，E），其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}現用某一種圖遍歷方法從頂點a開始遍歷圖，得到的序列為abecd，則采用的是__深度優(yōu)先遍歷方法。三、判斷題1、(r)在拓樸序列中，假如結點Vi排在結點Vj的前面，則一定存在從Vi到Vj的途徑。2、(√)用鄰接矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結點個數有關，而與圖的邊數無關。3、(×)拓撲排序是按AOE網中每個結點事件的最早發(fā)生時間對結點進行排序。4（×）采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似二叉樹的按層次遍歷算法。5、(√)若一個有向圖的鄰接矩陣中對角線以下元素均為零，則該圖的拓撲有序序列必然存在。6．在n個結點的無向圖中，若邊數大于n-1,則該圖必是連通圖。（

×

）7.有e條邊的無向圖，在鄰接表中有e個結點。（

×

）8.有向圖中頂點V的度等于其鄰接矩陣中第V行中的1的個數。（

×）9．強連通圖的各頂點間均可達。（

√）10．連通分量指的是有向圖中的極大連通子圖。（

×

）11．任何有向圖的結點都可以排成拓撲排序，并且拓撲序列不唯一。（

×

）12．用鄰接矩陣法存儲一個圖所需的存儲單元數目與圖的邊數有關。（

×

）13．有n個頂點的無向圖,采用鄰接矩陣表達,圖中的邊數等于鄰接矩陣中非零元素之和的一半。（

√

）14.當改變網上某一關鍵途徑上任一關鍵活動后，必將產生不同的關鍵途徑(

×)15．不同的求最小生成樹的方法最后得到的生成樹是相同的.（

×

）16、有向圖的鄰接表和逆鄰接表中表結點的個數一定相等。(√)四、簡答題1.請對下圖的無向帶權圖：寫出它的鄰接矩陣，并按普里姆算法求其最小生成樹；寫出它的鄰接表，并按克魯斯卡爾算法求其最小生成樹。解：設起點為a?？梢灾苯佑稍紙D畫出最小生成樹，并且最小生成樹只有一種（類）!鄰接矩陣為：最小生成樹最小生成樹→2.已知二維數組表達的圖的鄰接矩陣如下圖所示。試分別畫出自頂點1出發(fā)進行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。解：3、圖2表達一個地區(qū)的通訊網，邊表達城市間的通訊線路，邊上的權值表達架設線路花費的代價，請找出能連通每個城市、且總代價最省的n-1條線路。答：圖24.已知有向圖如下所示，對該圖進行拓撲排序。GGABCEHIDF（4152526）（1525）答：拓撲序列為：A、B、C、D、E、F、G、H、I（不唯一）（4152526）（1525）5.已知圖的鄰接矩陣為：

V1V2V3V4V5V6V7V8V9V10V10111000000V20001100000V30001010000V40000011010V50000001000V60000000110V70000000010V80000000001V90000000001V100000000000當用鄰接表作為圖的存儲結構，且鄰接表都按序號從大到小排序時，試寫出：（1）．以頂點V1為出發(fā)點的唯一的深度優(yōu)先遍歷；（2）．以頂點V1為