數(shù)據(jù)結構圖作業(yè)及部分答案

1、數(shù)據(jù)結構習題第七章 圖 一、 選擇題1、一個有n個頂點的無向圖最多有（ c ）條邊。a、n b、n(n-1) c、n(n-1)/2 d、2n2、具有4個頂點的無向完全圖有（ a ）條邊。a、6 b、12 c、16 d、203、具有6個頂點的無向圖至少有（ a ）條邊才能保證是一個連通圖。a、5 b、6 c、7 d、84、設連通圖g的頂點數(shù)為n，則g的生成樹的邊數(shù)為（ a ）。a、n-1 b、n c、2n d、2n-15、已知一個圖，若從頂點a出發(fā)進行深度和廣度優(yōu)先搜索遍歷，則可能得到的頂點序列分別為（ d ）和（ b ）（1） a、abecdf b、acfebd c、acebfd d、acfd

2、eb（2） a、abcedf b、abcefd c、abedfc d、acfdeb6、采用鄰接表存儲的圖的深度和廣度優(yōu)先搜索遍歷算法類似于二叉樹的（ b ）和（ d ）。a、中序遍歷 b、先序遍歷 c、后序遍歷 d、層次遍歷7、已知一有向圖的鄰接表存儲結構如下圖所示，分別根據(jù)圖的深度和廣度優(yōu)先搜索遍歷算法，從頂點v1出發(fā)，得到的頂點序列分別為（ c ）和（ b ）。a、v1,v2,v3,v4,v5 b、v1,v3,v2,v4,v5 c、v1,v2,v3,v5,v4 d、v1,v4,v3,v5,v28、已知一個圖如下，在該圖的最小生成樹中各邊上權值之和為（ c ），在該圖的最小生成樹中，從v1到

3、v6的路徑為（ g ）。a、31 b、38 c、36 d、43 e、v1,v3,v6 f、v1,v4,v6 g、v1,v5,v4,v6 h、v1,v4,v3,v69、正確的aoe網(wǎng)必須是（ c ）a、完全圖 b、哈密爾頓圖 c、無環(huán)圖 d、強連通圖10、已知一個圖如下，則由該圖得到的一種拓撲序列為（ a ）。a、v1,v4,v6,v2,v5,v3 b、v1,v2,v3,v4,v5,v6 c、v1,v4,v2,v3,v6,v5 d、v1,v2,v4,v6,v3,v511、下面結論中正確的是（ b ）a、在無向圖中，邊的條數(shù)是頂點度數(shù)之和。 b、在圖結構中，頂點可以沒有任何前驅和后繼。 c、在n個

4、頂點的無向圖中，若邊數(shù)大于n-1，則該圖必定是連通圖 d、圖的鄰接矩陣必定是對稱矩陣。12、下面結論不正確的是（ d ）。a、無向圖的連通分量是該圖的極大連通子圖。 b、有向圖用鄰接矩陣表示容易實現(xiàn)求頂點度數(shù)的操作。 c、無向圖用鄰接矩陣表示，圖中的邊數(shù)等于鄰接矩陣元素之和的一半。 d、無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣一定是不對稱的。13、下面結論中正確的是（ c ）。a、按深度優(yōu)先搜索遍歷圖時，與始點相鄰的頂點先于不與始點相鄰的頂點訪問。 b、一個圖按深度優(yōu)先搜索遍歷的結果是唯一的。 c、若有向圖g中包含一個環(huán)，則g的頂點間不存在拓撲排序。 d、圖的拓撲排序序列是唯一的。14、在一

5、個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（ c ）倍。a、1/2 b、1 c、2 d、4二、 填空題1、對具有n個頂點的圖，其生成樹有且僅有( n-1 )條邊。2、一個無向圖有n個頂點和e條邊，則所有頂點的度數(shù)之和為（ 2e ），其鄰接矩陣是一個關于( 對角線 )對稱的矩陣。3、具有n個頂點的無向完全圖，邊的總數(shù)為（ n(n-1)/2 ）條，而有n個頂點的有向完全圖，邊的總數(shù)為（ n(n-1) ）條。4、在無權圖g的鄰接矩陣a中，若(vi,vj)或屬于g的邊/弧的集合，則對應元素aij等于（ 1 ），否則等于（ 0 ），若aij=1，則aji等于（ 1 ）。5、已知一個圖的鄰接矩陣表示，計算第

6、i個頂點的入度方法為（求矩陣第i列非零元素的和 ）6、已知圖g的鄰接表如圖7.1所示，其從頂點v1出發(fā)的深度優(yōu)先搜索序列為( v1,v2,v3,v6,v5,v4 )，其從頂點v1出發(fā)的廣度優(yōu)先搜索序列為( v1,v2,v5,v4,v3,v6 )。v1143v2v3v4v5v6245352012345圖7.1 7、任何（ 無環(huán) ）的有向圖，其所有結點都可以排在一個拓撲序列中，拓撲排序的方法是先從圖中選一個（ 前趨 ）為0的結點且輸出，然后從圖中刪除該結點及其（ 所有以它為尾的弧 ），反復執(zhí)行，直到所有結點都輸出為止。8、在aoe網(wǎng)中，從源點到匯點各活動時間總和最長的路徑為關鍵路徑，某作業(yè)工程表示

7、成如圖7.2所示的aoe網(wǎng)。則事件5的最早完成時間是( 15 )。事件4的最遲開始時間是( 10 )。事件5的遲緩時間是( 4 )。關鍵路徑是( 0149 )。1925867304e1=5e3=14e2=9e6=3e7=7e4=4e8=12e5=10e10=10e11=5e14=8e13=8e12=5圖7.2e9=6三、 綜合題1、 簡述無向圖和有向圖有哪幾種存儲結構，并說明各種結構在圖不同操作中有什么優(yōu)越性？無向圖的存儲結構有鄰接矩陣、鄰接表和鄰接多重表，有向圖的存儲結構有鄰接矩陣、鄰接表和十字鏈表。a) 鄰接矩陣：可判定圖中任意兩個頂點之間是否有邊(或弧)相連，并容易求得各個頂點的度；此外

8、，對于圖的遍歷也是可行的。b) 鄰接表：容易找到任一頂點的第一個鄰接點和下一個鄰接點；但要判斷任意兩個頂點之間是否有邊或弧相連，則需搜索第i個及第j個鏈表，這不如鄰接矩陣方便；此外，對于圖的遍歷和有向圖的拓撲排序也是可行的。c) 十字鏈表：容易找到以某頂點為頭或尾的弧，因此容易求得頂點的入度和出度；在有向圖的應用中，十字鏈表是很有用的工具。d) 鄰接多重表：是無向圖的一種非常有效的存儲結構，在其中容易求得頂點和邊的各種信息。2、 給出下圖鄰接表存儲結構。從頂點1出發(fā)進行廣度和深度優(yōu)先搜索遍歷。3、 試列出圖中全部可能的拓撲排序序列。全部可能的拓撲排序序列為：152364、152634、156234、561234、516234、512634、5123644、已知連通網(wǎng)的鄰接矩陣如圖7.3所示，頂點集合為，試畫出它所表示的從頂點開始利用prim算法得到的最小生成樹。圖7.3 5、圖7.4所示為一無向連通網(wǎng)絡，要求根據(jù)kruskal算法構造出它的最小生成樹。1235461425483234567圖7.46、對圖7.5所示的有向網(wǎng)，試利用dijkstra算法求從源點1到其他各頂點的最短路徑。526411