《大數(shù)據結構圖 作業(yè)及部分問題詳解》由會員分享,可在線閱讀,更多相關《大數(shù)據結構圖 作業(yè)及部分問題詳解(9頁珍藏版)》請在裝配圖網上搜索。
1、word數(shù)據結構習題第七章 圖一、 選擇題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、a
2、cfdeb(2) A、abcedf B、abcefd C、abedfc D、acfdeb6、采用鄰接表存儲的圖的深度和廣度優(yōu)先搜索遍歷算法類似于二叉樹的( B )和( D )。A、中序遍歷 B、先序遍歷 C、后序遍歷 D、層次遍歷7、已知一有向圖的鄰接表存儲結構如下圖所示,分別根據圖的深度和廣度優(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 ),在該圖的最小生成樹中,從
3、v1到v6的路徑為( G )。A、31B、38C、36 D、43 E、v1,v3,v6 F、v1,v4,v6 G、v1,v5,v4,v6 H、v1,v4,v3,v69、正確的AOE網必須是( 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、已知一個圖的鄰接矩陣表示,計算第i
6、個頂點的入度方法為(求矩陣第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 )。圖7.17、任何( 無環(huán) )的有向圖,其所有結點都可以排在一個拓撲序列中,拓撲排序的方法是先從圖中選一個( 前趨 )為0的結點且輸出,然后從圖中刪除該結點及其( 所有以它為尾的弧 ),反復執(zhí)行,直到所有結點都輸出為止。8、在AOE網中,從源點到匯點各活動時間總和最長的路徑為關鍵路徑,某作業(yè)工程表示成如圖7.2所示的AOE網。則事件5的最早完成時間是( 1
7、5 )。事件4的最遲開始時間是( 10 )。事件5的遲緩時間是( 4 )。關鍵路徑是( 0149 )。三、 綜合題1、 簡述無向圖和有向圖有哪幾種存儲結構,并說明各種結構在圖不同操作中有什么優(yōu)越性?無向圖的存儲結構有鄰接矩陣、鄰接表和鄰接多重表,有向圖的存儲結構有鄰接矩陣、鄰接表和十字鏈表。a) 鄰接矩陣:可判定圖中任意兩個頂點之間是否有邊(或弧)相連,并容易求得各個頂點的度;此外,對于圖的遍歷也是可行的。b) 鄰接表:容易找到任一頂點的第一個鄰接點和下一個鄰接點;但要判斷任意兩個頂點之間是否有邊或弧相連,則需搜索第i個及第j個鏈表,這不如鄰接矩陣方便;此外,對于圖的遍歷和有向圖的拓撲排序也是
8、可行的。c) 十字鏈表:容易找到以某頂點為頭或尾的弧,因此容易求得頂點的入度和出度;在有向圖的應用中,十字鏈表是很有用的工具。d) 鄰接多重表:是無向圖的一種非常有效的存儲結構,在其中容易求得頂點和邊的各種信息。2、 給出下圖鄰接表存儲結構。從頂點1出發(fā)進行廣度和深度優(yōu)先搜索遍歷。3、 試列出圖中全部可能的拓撲排序序列。全部可能的拓撲排序序列為:152364、152634、156234、561234、516234、512634、5123644、已知連通網的鄰接矩陣如圖7.3所示,頂點集合為,試畫出它所表示的從頂點開始利用Prim算法得到的最小生成樹。5、圖7.4所示為一無向連通網絡,要求根據Kruskal算法構造出它的最小生成樹。圖7.46、對圖7.5所示的有向網,試利用Dijkstra算法求從源點1到其他各頂點的最短路徑。圖7.57、已知如圖7.6所示的AOE網。求:(1)每項活動的最早開始時間和最晚開始時間;(2)完成此工程最少需要多少單位時間;(3) 關鍵活動與關鍵路徑。9 / 9