圖練習(xí)題(答案).doc

圖練習(xí)題一、單項選擇題 1、 在一個具有n個頂點的有向圖中，若所有頂點的出度數(shù)之和為s，則所有頂點的度數(shù)之和為()。A. s B. s-1C. s+1D. 2s2、 在一個具有n個頂點的無向完全圖中，所含的邊數(shù)為()。A. nB. n(n-1)C. n(n-1)/2D. n(n+1)/23、 在一個無向圖中，若兩頂點之間的路徑長度為k，則該路徑上的頂點數(shù)為( )。A. k B. k+1 C. k+2 D. 2k4、 對于一個具有n個頂點的無向連通圖，它包含的連通分量的個數(shù)為( )。A. 0 B. 1 C. n D. n+15、 若一個圖中包含有k個連通分量，若要按照深度優(yōu)先搜索的方法訪問所有頂點，則必須調(diào)用( )次深度優(yōu)先搜索遍歷的算法。A. k B. 1 C. k-1 D. k+16、 若要把n個頂點連接為一個連通圖，則至少需要( )條邊。A. n B. n+1 C. n-1 D. 2n7、 在一個具有n個頂點和e條邊的無向圖的鄰接矩陣中，表示邊存在的元素（又稱為有效元素）的個數(shù)為( )。A. n B. ne C. e D. 2e8、 在一個具有n個頂點和e條邊的有向圖的鄰接矩陣中，表示邊存在的元素個數(shù)為( )。A. n B. ne C. e D. 2e9、 在一個有向圖的鄰接表中，每個頂點單鏈表中結(jié)點的個數(shù)等于該頂點的( )。A. 出邊數(shù) B. 入邊數(shù) C. 度數(shù) D. 度數(shù)減110、 若一個圖的邊集為(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)，則從頂點A開始對該圖進(jìn)行深度優(yōu)先搜索，得到的頂點序列可能為( )。A. A,B,C,F,D,E B. A,C,F,D,E,BC. A,B,D,C,F,E D. A,B,D,F,E,C11、 若一個圖的邊集為(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)，則從頂點A開始對該圖進(jìn)行廣度優(yōu)先搜索，得到的頂點序列可能為( )。A. A,B,C,D,E,F B. A,B,C,F,D,EC. A,B,D,C,E,F D. A,C,B,F,D,E12、 若如下圖所示的無向連通圖，則從頂點A開始對該圖進(jìn)行廣度優(yōu)先遍歷，得到的頂點序列可能為( )。A. A,B,C,D,E,F,G B. A,B,C,D,E,G,FC. A,B,F,C,D,E,G D. A,B,F,C,D,G,E二、填空題 1. 在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的_ 2 倍。2. 在一個具有n個頂點的無向完全圖中，包含有_ n*（n-1）/2 條邊，在一個具有n個頂點的有向完全圖中，包含有_ n*（n-1） 條邊。 3. 假定一個有向圖的頂點集為a,b,c,d,e,f，邊集為, , , , , ，則出度為0的頂點個數(shù)為_ 2 ，入度為1的頂點個數(shù)為_ 4 。4. 在一個具有n個頂點的無向圖中，要連通所有頂點則至少需要_ n-1 條邊。5. 圖的_ 深度 優(yōu)先搜索遍歷算法可以使用棧結(jié)果實現(xiàn)或用遞歸算法，圖的_ 廣度 優(yōu)先搜索遍歷算法則需要使用隊列結(jié)構(gòu)。6. 若一個連通圖中每個邊上的權(quán)值均不同，則得到的最小生成樹是_ 唯一 （唯一/不唯一）的。7. 以下有向圖中，從頂點A出發(fā)到達(dá)頂點E的最短路徑長度為_ 34 _。三、判斷題1、 用鄰接矩陣表示圖進(jìn)行深度優(yōu)先遍歷時，通常是采用隊列來實現(xiàn)算法的。( 0 )2、 n個頂點的連通圖，至少有n-1條邊。（ 1 ）3、 有向圖的鄰接矩陣是對稱矩陣，無向圖的鄰接矩陣是非對稱矩陣。（ 0 ）4、 若連通圖G中的一條邊e是所以邊中權(quán)值最小的邊，則圖G必存在著一最小生成棵包含邊e的最小生成樹。（ 1 ）四、應(yīng)用題1、 設(shè)無向網(wǎng)G=（V，E）如下圖所示，頂點集V利用線性表A,B,C,D,E,F進(jìn)行存儲，求該網(wǎng)的鄰接矩陣，并分別求出該圖的深度優(yōu)先和廣度優(yōu)先遍歷結(jié)果。深度：ACBDEF廣度：ACFBDE2、 設(shè)圖G=（V，E），其中V=A,B,C,D,E,F,其鄰接矩陣如下所示，按照Prim方法，從頂點A出發(fā)，求該網(wǎng)的最小生成樹的產(chǎn)生過程，并計算該最小生成樹的代價值。姓名:_ 學(xué)號:_ 年級:_ 專業(yè):_.密封線 最小生成樹：3、 設(shè)無向網(wǎng)G=（V，E）如下圖所示，按照Dijkstra算法，