1、第7章 圖 自測(cè)卷解答 姓名 班級(jí) 題號(hào)一二三四五總分題分1620241030100得分一、單選題（每題1分，共16分） 前兩大題全部來(lái)自于全國(guó)自考參考書！（ C ）1. 在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的 倍。 A1/2 B. 1 C. 2 D. 4 （ B ）2. 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 倍。 A1/2 B. 1 C. 2 D. 4 （ B ）3. 有8個(gè)結(jié)點(diǎn)的無(wú)向圖最多有 條邊。 A14 B. 28 C. 56 D. 112 （ C ）4. 有8個(gè)結(jié)點(diǎn)的無(wú)向連通圖最少有 條邊。 A5 B. 6 C. 7 D. 8 （ C ）5. 有8個(gè)結(jié)點(diǎn)的

2、有向完全圖有 條邊。 A14 B. 28 C. 56 D. 112 （ B ）6. 用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采用 來(lái)實(shí)現(xiàn)算法的。A棧 B. 隊(duì)列 C. 樹 D. 圖 （ A ）7. 用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常是采用 來(lái)實(shí)現(xiàn)算法的。A棧 B. 隊(duì)列 C. 樹 D. 圖 A0 2 4 3 1 5 6B. 0 1 3 6 5 4 2C. 0 4 2 3 1 6 5D. 0 3 6 1 5 4 2建議：先畫出圖，再深度遍歷（ C ）8. 已知圖的鄰接矩陣，根據(jù)算法思想，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是（ D ）9. 已知圖的鄰接矩陣同上題8，根據(jù)算法，則從頂點(diǎn)0出發(fā)

3、，按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是A 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 3 4 2 5 6（ B ）10. 已知圖的鄰接矩陣同上題8，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是A 0 2 4 3 6 5 1 B. 0 1 3 6 4 2 5 C. 0 4 2 3 1 5 6 D. 0 1 3 4 2 5 6（建議：0 1 2 3 4 5 6）（ C ）11. 已知圖的鄰接矩陣同上題8，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是A 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1

4、2 3 4 6 5 D. 0 1 2 3 4 5 6（ A ）12. 已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)不是深度優(yōu)先遍歷的結(jié)點(diǎn)序列是A0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3（ A ）14. 深度優(yōu)先遍歷類似于二叉樹的A先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 層次遍歷（ D ）15. 廣度優(yōu)先遍歷類似于二叉樹的A先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 層次遍歷（ A ）16. 任何一個(gè)無(wú)向連通圖的最小生成樹A只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在（注，生成樹不唯一，但最小生成樹唯一，即邊權(quán)之和或樹權(quán)最

5、小的情況唯一）二、填空題（每空1分，共20分）1. 圖有 鄰接矩陣 、 鄰接表 等存儲(chǔ)結(jié)構(gòu)，遍歷圖有 深度優(yōu)先遍歷 、 廣度優(yōu)先遍歷 等方法。2. 有向圖G用鄰接表矩陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的 出度 。3. 如果n個(gè)頂點(diǎn)的圖是一個(gè)環(huán)，則它有 n 棵生成樹。 （以任意一頂點(diǎn)為起點(diǎn)，得到n-1條邊）4. n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接矩陣存儲(chǔ)，則空間復(fù)雜度為 O(n2) 。5. n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接表存儲(chǔ)，則空間復(fù)雜度為 O(n+e) 。6. 設(shè)有一稀疏圖G，則G采用 鄰接表 存儲(chǔ)較省空間。7. 設(shè)有一稠密圖G，則G采用 鄰接矩陣 存儲(chǔ)較省空間。8. 圖的逆鄰接表存儲(chǔ)結(jié)構(gòu)

6、只適用于 有向 圖。9. 已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)頂點(diǎn)出發(fā)邊的方法是 將鄰接矩陣的第i行全部置0，第i列全部置0 。10. 圖的深度優(yōu)先遍歷序列 不是 惟一的。11. n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為 O(n2) ；若采用鄰接表存儲(chǔ)時(shí)，該算法的時(shí)間復(fù)雜度為 O(n+e) 。12. n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，廣度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為 O(n2) ；若采用鄰接表存儲(chǔ)，該算法的時(shí)間復(fù)雜度為 O(n+e) 。13. 圖的BFS(廣度優(yōu)先遍歷)生成樹的樹高比DFS（深度優(yōu)先遍歷）生成樹的樹高 小或相等 。14. 用普里姆(Prim)算法

7、求具有n個(gè)頂點(diǎn)e條邊的圖的最小生成樹的時(shí)間復(fù)雜度為 O(n2) ；用克魯斯卡爾(Kruskal)算法的時(shí)間復(fù)雜度是 O(elog2e) 。15. 若要求一個(gè)稀疏圖G的最小生成樹，最好用 克魯斯卡爾(Kruskal) 算法來(lái)求解。16. 若要求一個(gè)稠密圖G的最小生成樹，最好用 普里姆(Prim) 算法來(lái)求解。17. 用Dijkstra算法求某一頂點(diǎn)到其余各頂點(diǎn)間的最短路徑是按路徑長(zhǎng)度 遞增 的次序來(lái)得到最短路徑的。18. 拓?fù)渑判蛩惴ㄊ峭ㄟ^(guò)重復(fù)選擇具有 0 個(gè)前驅(qū)頂點(diǎn)的過(guò)程來(lái)完成的。三、簡(jiǎn)答題（每題6分，共24分）1. 【嚴(yán)題集7.1】已知如圖所示的有向圖，請(qǐng)給出該圖的:頂點(diǎn)123456入度出度

8、（1） 每個(gè)頂點(diǎn)的入/出度；（2） 鄰接矩陣；（3） 鄰接表；（4） 逆鄰接表。 答案：2. 【嚴(yán)題集7.7】請(qǐng)對(duì)下圖的無(wú)向帶權(quán)圖：（1） 寫出它的鄰接矩陣，并按普里姆算法求其最小生成樹；（2） 寫出它的鄰接表，并按克魯斯卡爾算法求其最小生成樹。 解：設(shè)起點(diǎn)為a?？梢灾苯佑稍紙D畫出最小生成樹，而且最小生成樹只有一種（類）!鄰接矩陣為： 最小生成樹 PRIM算法（橫向變化）： VbcdefghUV-UVexlowcosta4a3aaaaaab,c,d,e,f,g,hVexlowcosta40c5aaac5a,cb, d,e,f,g,hVexlowcost00c5b9aac5a,c,bd,e,f

9、,g,hVexlowcost000d7d6d5d4a,c,b,d e,f,g,hVexlowcost000d7d6d50a,c,b,d ,h e,f,g Vexlowcost000d7g200a,c,b,d ,h ,g f,e Vexlowcost000f3000a,c,b,d ,h ,g, f e Vexlowcost0000000a,c,b,d ,h ,g, f, e 鄰接表為：ab4c3ba4c5d5e9ca3b5d5h5db5c5e7f6g5h4eb9d7f3fd6e3g2gd5f2h6hc5d4g6克魯斯卡爾算法步驟(按邊歸并,堆排序)：先羅列：f-2-g a3-c f3e a4-b

10、 d4h (a,b,c) (e,f,g) (d,h) 取b5d, g5-d 就把三個(gè)連通分量連接起來(lái)了。3. 【嚴(yán)題集7.5】已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。4. 【嚴(yán)題集7.11】試?yán)肈ijkstra算法求圖中從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，寫出執(zhí)行算法過(guò)程中各步的狀態(tài)。解：最短路徑為：（a,c,f,e,d,g,b）四、 【2001年計(jì)考研題】給定下列網(wǎng)G: （10分） 1 試著找出網(wǎng)G的最小生成樹，畫出其邏輯結(jié)構(gòu)圖；2 用兩種不同的表示法畫出網(wǎng)G的存儲(chǔ)結(jié)構(gòu)圖；3 用C語(yǔ)言（或其他算法語(yǔ)言）定義其中一種表示法（

11、存儲(chǔ)結(jié)構(gòu)）的數(shù)據(jù)類型。A BC EF GD解：1. 最小生成樹可直接畫出，如右圖所示。2. 可用鄰接矩陣和鄰接表來(lái)描述：描述存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)類型可參見(jiàn)教材或電子教案：（C參考）注：用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣#define INFINITY INT_MAX /最大值#define MAX_VERTEX_NUM 20 /假設(shè)的最大頂點(diǎn)數(shù)（可取為7）Typedef enum DG, DN, AG,AN GraphKind; /有向/無(wú)向圖，有向/無(wú)向網(wǎng)Typedef struct ArcCell /?。ㄟ叄┙Y(jié)點(diǎn)的定義 VRType adj; /頂點(diǎn)間關(guān)系，無(wú)權(quán)圖取1或0；有權(quán)圖取權(quán)值類型 In

12、foType *info; /該弧相關(guān)信息的指針ArcCell, AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM ;Typedef struct /圖的定義VertexType vexs MAX_VERTEX_NUM ; /頂點(diǎn)表，用一維向量即可AdjMatrix arcs; /鄰接矩陣Int Vernum, arcnum; /頂點(diǎn)總數(shù)（7），?。ㄟ叄┛倲?shù)（9）GraphKind kind; /圖的種類標(biāo)志Mgraph; 鄰接表為：ab12e4ba12c20e8f9cb20d15g12dc15g10ea4b8f6fb9e6gc12d10五、算法設(shè)計(jì)題（每題10分

13、，共30分）1. 【嚴(yán)題集7.14】編寫算法，由依次輸入的頂點(diǎn)數(shù)目、弧的數(shù)目、各頂點(diǎn)的信息和各條弧的信息建立有向圖的鄰接表。解：Status Build_AdjList(ALGraph &G) /輸入有向圖的頂點(diǎn)數(shù),邊數(shù),頂點(diǎn)信息和邊的信息建立鄰接表 InitALGraph(G); scanf(%d,&v); if(v0) return ERROR; /頂點(diǎn)數(shù)不能為負(fù) G.vexnum=v; scanf(%d,&a); if(a0) return ERROR; /邊數(shù)不能為負(fù) G.arcnum=a; for(m=0;mv;m+) G.verticesm.data=getchar(); /輸入各

14、頂點(diǎn)的符號(hào) for(m=1;m=a;m+) t=getchar();h=getchar(); /t為弧尾,h為弧頭 if(i=LocateVex(G,t)0) return ERROR; if(j=LocateVex(G,h)nextarc;q=q-nextarc); q-nextarc=p; p-adjvex=j;p-nextarc=NULL; /while return OK; /Build_AdjList 2. 【嚴(yán)題集7.15】試在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：DeleteArc(G,v,w) ，即刪除一條邊的操作。（如果要?jiǎng)h除所有從第i個(gè)頂點(diǎn)出發(fā)的邊呢？ 提示： 將鄰接矩陣的第

15、i行全部置0 ）解：/本題中的圖G均為有向無(wú)權(quán)圖。 Status Delete_Arc(MGraph &G,char v,char w)/在鄰接矩陣表示的圖G上刪除邊(v,w) if(i=LocateVex(G,v)0) return ERROR; if(j=LocateVex(G,w)nextarc) k=p-adjvex; if(!visitedk&exist_path(k,j) return 1;/i下游的頂點(diǎn)到j(luò)有路徑 /for /else /exist_path_DFS 解2：（以上算法似乎有問(wèn)題：如果不存在路徑，則原程序不能返回0。我的解決方式是在原程序的中引入一變量level來(lái)控

16、制遞歸進(jìn)行的層數(shù)。具體的方法我在程序中用紅色標(biāo)記出來(lái)了。）int visitedMAXSIZE; /指示頂點(diǎn)是否在當(dāng)前路徑上 int level1;/遞歸進(jìn)行的層數(shù)int exist_path_DFS(ALGraph G,int i,int j)/深度優(yōu)先判斷有向圖G中頂點(diǎn)i到頂點(diǎn)j 是否有路徑,是則返回1,否則返回0 if(i=j) return 1; /i就是j else visitedi=1; for(p=G.verticesi.firstarc;p;p=p-nextarc，level-) level+; k=p-adjvex; if(!visitedk&exist_path(k,j) return 1;/i下游的頂點(diǎn)到j(luò)有路徑 /for /else if (level=1) return 0;/exist_path_DFS 附加題：【嚴(yán)題集7.27】采用鄰接表存儲(chǔ)結(jié)構(gòu)，編寫一個(gè)判別無(wú)向圖中任意給定的兩個(gè)頂點(diǎn)之間是否存在一條長(zhǎng)度為k的簡(jiǎn)單路徑的算法。（注1：一條路徑為簡(jiǎn)單路徑指的是其頂點(diǎn)序列中不含有重現(xiàn)的頂點(diǎn)。注2：此題可參見(jiàn)嚴(yán)題集P207-208中有關(guān)按“路徑”遍歷的算法基本框架。）int visitedMAXSIZE; int exist_path_len(ALGraph G,int i,int j,int k)/判斷鄰接表方式存儲(chǔ)的有向圖G 的頂點(diǎn)i到j(luò)是否存