圖習(xí)習(xí)題參考答案

1、習(xí)題六參考答案一、選擇題1. 在一個(gè)有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度之和為s，則所有頂點(diǎn)的入度之和為（A）。A. sB. s-1C. s+1D. n2. 一個(gè)有向圖有n個(gè)頂點(diǎn)，則每個(gè)頂點(diǎn)的度可能的最大值是（B）。A.n-1B.2(n-1) C.nD.2n3. 具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有（A）條邊才能確保是一個(gè)連通圖。B.64. 一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有（C）條邊。A.nB.nn-1C.nn-1/2D.2n5. 對(duì)某個(gè)無(wú)向圖的鄰接矩陣來(lái)說(shuō)，下列敘述正確的是（A）。A.第i行上的非零元素個(gè)數(shù)和第i列上的非零元素個(gè)數(shù)一定相等B.矩陣中的非零元素個(gè)數(shù)等于圖中的邊數(shù)C.第i行與第i列上的非零

2、元素的總數(shù)等于頂點(diǎn)vi的度數(shù)D.矩陣中非全零行的行數(shù)等于圖中的頂點(diǎn)數(shù)6. 已知一個(gè)有向圖的鄰接矩陣，要?jiǎng)h除所有以第i個(gè)頂點(diǎn)為孤尾的邊，應(yīng)該（B）。A.將鄰接矩陣的第i行刪除B.將鄰接矩陣的第i行元素全部置為0C.將鄰接矩陣的第i列刪除D.將鄰接矩陣的第i列元素全部置為07. 下面關(guān)于圖的存儲(chǔ)的敘述中，哪一個(gè)是正確的（A）A用鄰接矩陣存儲(chǔ)圖，占用的存儲(chǔ)空間只與圖中頂點(diǎn)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)B用鄰接矩陣存儲(chǔ)圖，占用的存儲(chǔ)空間只與圖中邊數(shù)有關(guān)，而與頂點(diǎn)數(shù)無(wú)關(guān)C用鄰接表存儲(chǔ)圖，占用的存儲(chǔ)空間只與圖中頂點(diǎn)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)D用鄰接表存儲(chǔ)圖，占用的存儲(chǔ)空間只與圖中邊數(shù)有關(guān)，而與頂點(diǎn)數(shù)無(wú)關(guān)8. 對(duì)圖的深度優(yōu)

3、先遍歷，類似于對(duì)樹(shù)的哪種遍歷（A）A.先根遍歷B.中根遍歷C后根遍歷D層次遍歷9. 任何一個(gè)無(wú)向連通圖的最小生成樹(shù)（B）。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在10. 下面是三個(gè)關(guān)于有向圖運(yùn)算的敘述：（1）求兩個(gè)指向結(jié)點(diǎn)間的最短路徑，其結(jié)果必定是唯一的（2）求有向圖結(jié)點(diǎn)的拓?fù)湫蛄校浣Y(jié)果必定是唯一的（3）求AOE網(wǎng)的關(guān)鍵路徑，其結(jié)果必定是唯一的其中哪個(gè)（些）是正確的（D）A.只有（1）B.（1）和（2）C.都正確D.都不正確二、填空題1. 若用n表示圖中頂點(diǎn)數(shù)，則有nn-1/2條邊的無(wú)向圖稱為完全圖。2. 若一個(gè)無(wú)向圖有100條邊，則其頂點(diǎn)總數(shù)最少為15個(gè)。3. n個(gè)頂點(diǎn)的連

4、通無(wú)向圖至少有n-1條邊，至多有nn-1/2條邊。4. 若有向圖G的鄰接矩陣為：v0v1v2v3v4v0v1v2v3v40110010101110110000001100則頂點(diǎn)v4的入度是3。5. 對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的度為k1，出度為k2，則對(duì)應(yīng)逆鄰接表中該頂點(diǎn)單鏈表中的邊結(jié)點(diǎn)數(shù)為k1-k2。6. 圖的遍歷算法BFS中用到輔助隊(duì)列，每個(gè)頂點(diǎn)最多進(jìn)隊(duì)1次。7. 在求最小生成樹(shù)的兩種算法中，克魯斯卡爾算法適合于稀疏圖。8. 數(shù)據(jù)結(jié)構(gòu)中的迪杰斯特拉算法是用來(lái)求某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑。9. 除了使用拓?fù)渑判虻姆椒?，還有深度優(yōu)先搜索方法可以判斷出一個(gè)有向圖是否有回路。10. 在用鄰接表表

5、示圖時(shí)，拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度為On+e。三、應(yīng)用題1. 已知如圖所示的有向圖，請(qǐng)給出該圖的123456圖 有向圖(1) 每個(gè)頂點(diǎn)的出/入度；(2) 鄰接矩陣；(3) 鄰接表；(4) 逆鄰接表。答：(1) 每個(gè)頂點(diǎn)的出/入度是：出度入度103222321431512632(2) 鄰接矩陣：123456123456001000010000010000100111101100000010(3) 鄰接表：40123123450312456550014(4) 逆鄰接表：401231234525315632314552. 試對(duì)如圖所示的非連通圖，畫出其廣度優(yōu)先生成森林。圖 Error! No text

6、 of specified style in document.非連通圖GIKHEDACFBLJM答：GIKHEDACFBLJM3. 已知圖的鄰接矩陣如圖所示。試分別畫出自頂點(diǎn)A出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。ABCDEFGHIJABCDEFGHIJ0000010000000001001010100001000000001100100010000010000100000011000100000001000010010001001010000010圖 Error! No text of specified style in document.鄰接矩陣答：IHEDABFGJC I

7、HDABFGJCE4. 請(qǐng)對(duì)如圖所示的無(wú)向網(wǎng)：(1) 寫出它的鄰接矩陣，并按克魯斯卡爾算法求其最小生成樹(shù)；(2) 寫出它的鄰接表，并按普里姆算法求其最小生成樹(shù)。534655圖Error! No text of specified style in document.無(wú)向網(wǎng)5437ABEFDC9GH526答：(1)ABCDEFGHABCDEFGH043405350555509576549765540330220660克魯斯卡爾算法求其最小生成樹(shù)ABEFDCGH23ABEFDCGH23ABEFDCGH23343ABEFDCGH23443ABEFDCGH234543ABEFDCGH234543ABE

8、FDC9GH52(2)ABCD0123EFGH456714320425359415254756654703153557193735364326355267253466普里姆算法求其最小生成樹(shù)，從A開(kāi)始3ABEFDCGH43ABEFDCGH543ABEFDCGH4543ABEFDCGH4543ABEFDCGH54543ABEFDCGH5234543ABEFDCGH525. 試列出圖中全部可能的拓?fù)溆行蛐蛄?。abce圖 有向圖fd答：abcdef、abcef、abecdf、bacdef、bacedf、baecdf、beacdf四、算法設(shè)計(jì)題1. 編寫算法，從鍵盤讀入有向圖的頂點(diǎn)和弧，創(chuàng)建有向圖的鄰

9、接表存儲(chǔ)結(jié)構(gòu)。參考答案:public static ALGraph createDG() Scanner sc = new Scanner;"請(qǐng)分別輸入有向圖的頂點(diǎn)數(shù)和邊數(shù):");int vexNum = ();int arcNum = ();VNode vexs = new VNodevexNum;"請(qǐng)分別輸入有向圖的各個(gè)頂點(diǎn):");for (int v = 0; v < vexNum; v+)/ 構(gòu)造頂點(diǎn)向量vexsv = new VNode();ALGraph G = new ALGraph, vexNum, arcNum, vexs);&q

10、uot;請(qǐng)輸入各個(gè)邊的起點(diǎn)和終點(diǎn):");for (int k = 0; k < arcNum; k+) int v = ();int u = ();(v, u, 0);return G; 2. 無(wú)向圖采用鄰接表存儲(chǔ)結(jié)構(gòu)，編寫算法輸出圖中各連通分量的頂點(diǎn)序列。參考答案:public static void CC_BFS(IGraph G) throws Exception boolean visited = new boolean();/ 訪問(wèn)標(biāo)志數(shù)組for (int v = 0; v < (); v+)/ 訪問(wèn)標(biāo)志數(shù)組初始化visitedv = false;LinkQue

11、ue Q = new LinkQueue();/ 輔助隊(duì)列QLinkQueue P = new LinkQueue();/ 輔助隊(duì)列P,用于記錄連通分量的頂點(diǎn)int i = 0;/ 用于記數(shù)連通分量的個(gè)數(shù)for (int v = 0; v < (); v+) ();/ 隊(duì)列清空if (!visitedv) / v尚未訪問(wèn)visitedv = true;(v);(v);/ v入隊(duì)列while (!() int u = (Integer) ();/ 隊(duì)頭元素出隊(duì)列并賦值給ufor (int w = (u); w >= 0; w = (u,w) if (!visitedw) / w為u的

12、尚未訪問(wèn)的鄰接頂點(diǎn)visitedw = true;(w);(w);"圖的第" + +i + "個(gè)連通分量為：");while (!() + " ");3. 編寫算法判別以鄰接表方式存儲(chǔ)的無(wú)向圖中是否存在由頂點(diǎn)u到頂點(diǎn)v的路徑（uv）。可以采用深度優(yōu)先搜索遍歷策略。當(dāng)頂點(diǎn)u和頂點(diǎn)v在無(wú)向圖的同一連通分量中時(shí)，從頂點(diǎn)u到頂點(diǎn)v一定有路徑，可從頂點(diǎn)u（v）進(jìn)行深度優(yōu)先搜索，一定可以遍歷至頂點(diǎn)v（u）。否則，遍歷不能成功，不存在由頂點(diǎn)u到頂點(diǎn)v的路徑。參考答案:private boolean visited;/ 訪問(wèn)標(biāo)志數(shù)組private b

13、oolean find = false;/ 標(biāo)示是否已找到了指定長(zhǎng)度的路徑public void findPath(IGraph G, int u, int v) throws Exception visited = new boolean();for (int w = 0; w < (); w+)/ 訪問(wèn)標(biāo)志數(shù)組初始化visitedw = false;find_DFS(G, u, v);if (find) + "和" + (v) + "之間至少存在一條路徑！");else + "和" + (v) + "之間不存在路徑！");private void