word數(shù)據(jù)結(jié)構(gòu)習(xí)題第七章 圖一、 選擇題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、設(shè)連通圖G的頂點數(shù)為n，則G的生成樹的邊數(shù)為（ A ）。A、n-1 B、n C、2n D、2n-15、已知一個圖，若從頂點a出發(fā)進(jìn)行深度和廣度優(yōu)先搜索遍歷，則可能得到的頂點序列分別為（ D ）和（ B ）（1） A、abecdf B、acfebd C、acebfd D、acfdeb（2） A、abcedf B、abcefd C、abedfc D、acfdeb6、采用鄰接表存儲的圖的深度和廣度優(yōu)先搜索遍歷算法類似于二叉樹的（ B ）和（ D ）。A、中序遍歷 B、先序遍歷 C、后序遍歷 D、層次遍歷7、已知一有向圖的鄰接表存儲結(jié)構(gòu)如下圖所示，分別根據(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、已知一個圖如下，在該圖的最小生成樹中各邊上權(quán)值之和為（ C ），在該圖的最小生成樹中，從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網(wǎng)必須是（ C ）A、完全圖 B、哈密爾頓圖 C、無環(huán)圖 D、強連通圖10、已知一個圖如下，則由該圖得到的一種拓?fù)湫蛄袨椋?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、下面結(jié)論中正確的是（ B ）A、在無向圖中，邊的條數(shù)是頂點度數(shù)之和。 B、在圖結(jié)構(gòu)中，頂點可以沒有任何前驅(qū)和后繼。 C、在n個頂點的無向圖中，若邊數(shù)大于n-1，則該圖必定是連通圖 D、圖的鄰接矩陣必定是對稱矩陣。12、下面結(jié)論不正確的是（ D ）。A、無向圖的連通分量是該圖的極通子圖。 B、有向圖用鄰接矩陣表示容易實現(xiàn)求頂點度數(shù)的操作。 C、無向圖用鄰接矩陣表示，圖中的邊數(shù)等于鄰接矩陣元素之和的一半。 D、無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣一定是不對稱的。13、下面結(jié)論中正確的是（ C ）。A、按深度優(yōu)先搜索遍歷圖時，與始點相鄰的頂點先于不與始點相鄰的頂點訪問。 B、一個圖按深度優(yōu)先搜索遍歷的結(jié)果是唯一的。 C、若有向圖G中包含一個環(huán)，則G的頂點間不存在拓?fù)渑判颉?D、圖的拓?fù)渑判蛐蛄惺俏ㄒ坏摹?4、在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（ C ）倍。A、1/2 B、1 C、2 D、4二、 填空題1、對具有n個頂點的圖，其生成樹有且僅有( n-1 )條邊。2、一個無向圖有n個頂點和e條邊，則所有頂點的度數(shù)之和為（ 2e ），其鄰接矩陣是一個關(guān)于( 對角線 )對稱的矩陣。3、具有n個頂點的無向完全圖，邊的總數(shù)為（ n(n-1)/2 ）條，而有n個頂點的有向完全圖，邊的總數(shù)為（ n(n-1) ）條。4、在無權(quán)圖G的鄰接矩陣A中，若(vi,vj)或<vi,vj>屬于G的邊/弧的集合，則對應(yīng)元素Aij等于（ 1 ），否則等于（ 0 ），若Aij=1，則Aji等于（ 1 ）。5、已知一個圖的鄰接矩陣表示，計算第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 )。圖7.17、任何（ 無環(huán) ）的有向圖，其所有結(jié)點都可以排在一個拓?fù)湫蛄兄?，拓?fù)渑判虻姆椒ㄊ窍葟膱D中選一個（ 前趨 ）為0的結(jié)點且輸出，然后從圖中刪除該結(jié)點及其（ 所有以它為尾的弧 ），反復(fù)執(zhí)行，直到所有結(jié)點都輸出為止。8、在AOE網(wǎng)中，從源點到匯點各活動時間總和最長的路徑為關(guān)鍵路徑，某作業(yè)工程表示成如圖7.2所示的AOE網(wǎng)。則事件5的最早完成時間是( 15 )。事件4的最遲開始時間是( 10 )。事件5的遲緩時間是( 4 )。關(guān)鍵路徑是( 0149 )。三、 綜合題1、 簡述無向圖和有向圖有哪幾種存儲結(jié)構(gòu)，并說明各種結(jié)構(gòu)在圖不同操作中有什么優(yōu)越性？無向圖的存儲結(jié)構(gòu)有鄰接矩陣、鄰接表和鄰接多重表，有向圖的存儲結(jié)構(gòu)有鄰接矩陣、鄰接表和十字鏈表。a) 鄰接矩陣：可判定圖中任意兩個頂點之間是否有邊(或弧)相連，并容易求得各個頂點的度；此外，對于圖的遍歷也是可行的。b) 鄰接表：容易找到任一頂點的第一個鄰接點和下一個鄰接點；但要判斷任意兩個頂點之間是否有邊或弧相連，則需搜索第i個及第j個鏈表，這不如鄰接矩陣方便；此外，對于圖的遍歷和有向圖的拓?fù)渑判蛞彩强尚械摹) 十字鏈表：容易找到以某頂點為頭或尾的弧，因此容易求得頂點的入度和出度；在有向圖的應(yīng)用中，十字鏈表是很有用的工具。d) 鄰接多重表：是無向圖的一種非常有效的存儲結(jié)構(gòu)，在其中容易求得頂點和邊的各種信息。2、 給出下圖鄰接表存儲結(jié)構(gòu)。從頂點1出發(fā)進(jìn)行廣度和深度優(yōu)先搜索遍歷。3、 試列出圖中全部可能的拓?fù)渑判蛐蛄?。全部可能的拓?fù)渑判蛐蛄袨椋?52364、152634、156234、561234、516234、512634、5123644、已知連通網(wǎng)的鄰接矩陣如圖7.3所示，頂點集合為，試畫出它所表示的從頂點開始利用Prim算法得到的最小生成樹。5、圖7.4所示為一無向連通網(wǎng)絡(luò)，要求根據(jù)Kruskal算法構(gòu)造出它的最小生成樹。圖7.46、對圖7.5所示的有向網(wǎng)，試?yán)肈ijkstra算法求從源點1到其他各頂點的最短路徑。圖7.57、已知如圖7.6所示的AOE網(wǎng)。求：（1）每項活動的最早開始時間和最晚開始時間；（2）完成此工程最少需要多少單位時間；（3） 關(guān)鍵活動與關(guān)鍵路徑。9 / 9