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

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

C）。

A．求關(guān)鍵途徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的

B．一個(gè)事件的最早開始時(shí)間同以該事件為尾的弧的活動最早開始時(shí)間相同

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

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

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

II.邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1

III.至少有一個(gè)頂點(diǎn)的度為1

A.只有I

B.

只有II

C.I和II

D.I和III

20、假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表達(dá),則刪除與某個(gè)頂點(diǎn)vi相關(guān)的所有弧的時(shí)間復(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)}，對該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列對的的是（

）。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的拓?fù)湫蛄兄?，若頂點(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不也許出現(xiàn)的是（

D

）。

A．G中有弧<Vi，Vj>

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

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

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

B.拓?fù)渑判?/p>

C.求最短途徑

D.求關(guān)鍵途徑24、下列關(guān)于AOE網(wǎng)的敘述中，不對的的是（

B

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

×

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

×

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

×）9．強(qiáng)連通圖的各頂點(diǎn)間均可達(dá)。（

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

×

）11．任何有向圖的結(jié)點(diǎn)都可以排成拓?fù)渑判?，并且拓?fù)湫蛄胁晃ㄒ?。?/p>

×

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

×

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

√

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

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

×

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

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