2023年圖練習(xí)題及答案

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

C）。

A．求關(guān)鍵途徑是以拓撲排序為基礎(chǔ)的

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

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

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

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

II.邊數(shù)大于頂點個數(shù)減1

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

A.只有I

B.

只有II

C.I和II

D.I和III

20、假設(shè)一個有n個頂點和e條弧的有向圖用鄰接表表達,則刪除與某個頂點vi相關(guān)的所有弧的時間復(fù)雜度是(Ｃ)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(chǎn),b,e,c,d,f

B．a(chǎn),c,f,e,b,d

C．a(chǎn),e,b,c,f,d

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

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.求關(guān)鍵途徑24、下列關(guān)于AOE網(wǎng)的敘述中，不對的的是（

B

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

×

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

×

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

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

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

×

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

×

）12．用鄰接矩陣法存儲一個圖所需的存儲單元數(shù)目與圖的邊數(shù)有關(guān)。（

×

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

√

）14.當改變網(wǎng)上某一關(guān)鍵途徑上任一關(guān)鍵活動后，必將產(chǎn)生不同的關(guān)鍵途徑(

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

×

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

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