數(shù)據(jù)結(jié)構(gòu)與算法材料第七章圖圖-練習

1、圖1將n階對稱矩陣只存儲下三角部分，共需_個存儲空間。 n(n-1)/22判斷無向圖的鄰接矩陣一定是對稱矩陣，而有向圖的鄰接矩陣一定是非對稱矩陣 錯3算法應(yīng)用對下圖所示的加權(quán)無向圖，用prim算法求最小生成樹，設(shè)從結(jié)點a開始，畫出構(gòu)造過程。4下圖所示的有向無環(huán)圖，寫出所有的拓撲序列：b a d e cb d a e c d b a e c5在有向圖G的拓撲序列中，若頂點vi在頂點vj之前，則下列情況不可能出現(xiàn)的是（） AG中有弧 BG中有一條從vi到vj的路徑 CG中沒有弧 DG中有一條從vj到vi的路徑D6設(shè)圖G用鄰接表存儲，則求每個頂點入度的算法時間復雜度為（）。 AO(n) B O(n+

2、e) CO(n*e) DO(n*n)B7判斷一個有向圖的鄰接表和逆鄰接表中的結(jié)點個數(shù)不一定相等。錯8由頂點v1,v2,v3構(gòu)成的圖的鄰接矩陣如下，則該圖中頂點v1的出度為（） A0 B1 C2 D3C9設(shè)無向圖的鄰接表如下圖所示，則該圖的邊數(shù)為（） A4 B5 C10 D20 B10有向圖G的鄰接矩陣為A，如果圖中存在弧，則Aij的值為（） 111下列哪一方法可以判斷出一個有向圖是否有環(huán)（回路）： A深度優(yōu)先遍歷 B拓撲排序 C求最短路徑 D廣度優(yōu)先遍歷B12下列說法不正確的是（）。A. 圖的遍歷是從給定的源點出發(fā)每一個頂點僅被訪問一次 B. 圖的深度遍歷不適用于有向圖C. 圖遍歷的基本算法有

3、兩種：深度遍歷和廣度遍歷D. 圖的深度遍歷是一個遞歸過程B13設(shè)G=(V,E)以鄰接表存儲，如下圖所示，試畫出圖的深度優(yōu)先和廣度優(yōu)先生成樹14最短路徑的生成算法可用（）。A. 普里姆算法 B. 克魯斯卡爾算法C. 迪杰斯特拉算法D. 哈夫曼算法C15圖的鄰接表如下呼所示，那么從頂點v0出發(fā)進行深度優(yōu)先搜索，經(jīng)歷的結(jié)點順序為（）A. v0 v3 v2 v1 B. v0 v1 v2 v3C. v0 v2 v1 v3D. v0 v1 v3 v2B16圖的鄰接表如下呼所示，那么從頂點v0出發(fā)進行廣度優(yōu)先搜索，經(jīng)歷的結(jié)點順序為（）A. v0 v3 v2 v1 B. v0 v1 v2 v3C. v0 v2

4、 v1 v3D. v0 v1 v3 v2D17關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中（）。A. 從源點到匯點的最長路徑 B. 從源點到匯點的最短路徑C. 最長的回路D. 最短的回路A18n個頂點的強連通圖至少有（）條邊A. n B. n+1C. n-1 D. n(n-1)A19上題，n個頂點的強連通圖的形狀是（）A. 無回路 B. 有回路C. 環(huán)狀 D. 樹狀C20設(shè)圖G有n個頂點和e條邊，若采用鄰接表存儲，則進行深度搜索的時間復雜度為（），廣度搜索的時間復雜度為（）。A. O(n*e) B. O(n+e)C. O(elog2n) D. O(e)E. O(n*n)EE21設(shè)圖G有n個頂點和e條邊，若采用鄰接矩陣存儲，則進行深度搜索的時間復雜度為（），廣