圖練習(xí)題(答案)演示教學(xué)

1、資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除圖練習(xí)題一、單項(xiàng)選擇題1、在一個(gè)具有 n 個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度數(shù)之和為s，則所有頂點(diǎn)的度數(shù)之和為 () 。A. sB. s-1C. s+1D. 2s2、在一個(gè)具有 n 個(gè)頂點(diǎn)的無向完全圖中，所含的邊數(shù)為() 。A. nB. n(n-1)C. n(n-1)/2D. n(n+1)/23、在一個(gè)無向圖中， 若兩頂點(diǎn)之間的路徑長度為k，則該路徑上的頂點(diǎn)數(shù)為()。A. kB. k+1C. k+2D. 2k4、對于一個(gè)具有n 個(gè)頂點(diǎn)的無向連通圖，它包含的連通分量的個(gè)數(shù)為()。A. 0B. 1C. nD. n+15、若一個(gè)圖中包含有k 個(gè)連通分量， 若要按

2、照深度優(yōu)先搜索的方法訪問所有頂點(diǎn)，則必須調(diào)用 ()次深度優(yōu)先搜索遍歷的算法。A. kB. 1C. k-1D. k+16、若要把 n 個(gè)頂點(diǎn)連接為一個(gè)連通圖，則至少需要()條邊。A. nB. n+1C. n-1D. 2n7、在一個(gè)具有 n 個(gè)頂點(diǎn)和 e 條邊的無向圖的鄰接矩陣中，表示邊存在的元素 （又稱為有效元素）的個(gè)數(shù)為()。A. nB. neC. eD. 2e8、在一個(gè)具有 n 個(gè)頂點(diǎn)和 e 條邊的有向圖的鄰接矩陣中，表示邊存在的元素個(gè)數(shù)為()。A. nB. neC. eD. 2e9、在一個(gè)有向圖的鄰接表中，每個(gè)頂點(diǎn)單鏈表中結(jié)點(diǎn)的個(gè)數(shù)等于該頂點(diǎn)的()。A. 出邊數(shù)B. 入邊數(shù)C. 度數(shù)D.

3、度數(shù)減 110、 若一個(gè)圖的邊集為(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)，則從頂點(diǎn) A 開始對該圖進(jìn)行深度優(yōu)先搜索，得到的頂點(diǎn)序列可能為()。A. A,B,C,F,D,EB. A,C,F,D,E,BC. A,B,D,C,F,ED. A,B,D,F,E,C11、 若一個(gè)圖的邊集為(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)，則從頂點(diǎn) A 開始對該圖進(jìn)行廣度優(yōu)先搜索，得到的頂點(diǎn)序列可能為()。A. A,B,C,D,E,FB. A,B,C,F,D,EC. A,B,D,C,E,FD. A,C,B,F,D,E12、 若如下圖所示的無向連通圖，則從

4、頂點(diǎn)A 開始對該圖進(jìn)行廣度優(yōu)先遍歷，得到的頂點(diǎn)序列可能為 () 。word 可編輯資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除ABFCDGEA. A,B,C,D,E,F,GB. A,B,C,D,E,G,FC. A,B,F,C,D,E,GD. A,B,F,C,D,G ,E二、填空題1.在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的_2倍。2.在一個(gè)具有 n 個(gè)頂點(diǎn)的無向完全圖中，包含有_ n*（ n-1）/2條邊，在一個(gè)具有n 個(gè)頂點(diǎn)的有向完全圖中，包含有_ n* （ n-1）條邊。3.假定一個(gè)有向圖的頂點(diǎn)集為a,b,c,d,e,f，邊集為 , , , , ，則出度為 0 的頂點(diǎn)個(gè)數(shù)為 _2，入度為

5、1 的頂點(diǎn)個(gè)數(shù)為 _4。4.在一個(gè)具有 n 個(gè)頂點(diǎn)的無向圖中，要連通所有頂點(diǎn)則至少需要_n-1條邊。5.圖的_ 深度優(yōu)先搜索遍歷算法可以使用棧結(jié)果實(shí)現(xiàn)或用遞歸算法，圖的_廣度優(yōu)先搜索遍歷算法則需要使用隊(duì)列結(jié)構(gòu)。6.若一個(gè)連通圖中每個(gè)邊上的權(quán)值均不同，則得到的最小生成樹是_唯一（唯一/不唯一）的。7.以下有向圖中，從頂點(diǎn)A 出發(fā)到達(dá)頂點(diǎn)E 的最短路徑長度為 _34_。3DE17912B2011A15307F17C三、判斷題1、 用鄰接矩陣表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常是采用隊(duì)列來實(shí)現(xiàn)算法的。(0)2、 n 個(gè)頂點(diǎn)的連通圖，至少有n-1 條邊。（ 1）3、 有向圖的鄰接矩陣是對稱矩陣，無向圖的鄰接

6、矩陣是非對稱矩陣。（ 0）4、5、 若連通圖G 中的一條邊e 是所以邊中權(quán)值最小的邊，則圖G 必存在著一最小生成棵包含邊e 的最小生成樹。 （1）四、應(yīng)用題1、 設(shè)無向網(wǎng) G=（ V，E）如下圖所示，頂點(diǎn)集 V 利用線性表 A,B,C,D,E,F 進(jìn)行存儲(chǔ)，求該網(wǎng)的鄰接矩陣，并分別求出該圖的深度優(yōu)先和廣度優(yōu)先遍歷結(jié)果。word 可編輯資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除A60FB1030205EC11D50深度： ACBDEF廣度： ACFBDE2、3、 設(shè)圖 G=（V， E），其中 V=A,B,C,D,E,F,其鄰接矩陣如下所示，按照Prim 方法，從頂點(diǎn) A 出發(fā)，求該網(wǎng)的最小生成樹的產(chǎn)生過程，并計(jì)算該最小生成樹的代價(jià)值。ABCDEF01030100A05B105050CA (G)5002010D3020060E10010600FAF3010EB10205D最小生成樹：C4、5、6、7、 設(shè)無向網(wǎng) G=（ V， E）如下圖所示，按照 Dijkstra 算法，求從 A 出發(fā)到達(dá)其余各頂點(diǎn)的最短路徑AB7C10592