圖習(xí)題解析(答)

1、第六章圖習(xí)題解析1一、選擇題1、設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n,則該無向圖最多有條邊。A、n-1 B、n (n-1) /2 C、n (n+1) /2 D、0 E、n22、在下列兩種求圖的最小生成樹的算法中， 算法適合于求邊稀疏的網(wǎng)的最小生 成樹。A、Prim B、Kruskal3、下面的敘述中不正確的是 。A、關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B、任何一個(gè)關(guān)鍵活動(dòng)提前完成，將使整個(gè)工程提前完成C所有關(guān)鍵活動(dòng)都提前完成，則整個(gè)工程將提前完成D、某些關(guān)鍵活動(dòng)若提前完成，將使整個(gè)工程提前完成4、采用鄰接表存儲的圖，其深度優(yōu)先遍歷類似于二叉樹的 。A、中序遍歷B、先序遍歷C后序遍歷D、按層次遍歷5、

2、采用鄰接表存儲的圖，其廣度優(yōu)先遍歷類似于二叉樹的 。A、按層次遍歷B、中序遍歷C、后序遍歷D、先序遍歷6、具有n個(gè)頂點(diǎn)的有向圖最多有 條邊。A、n B、n (n-1) C、n (n+1) D、n27、一個(gè)n個(gè)頂點(diǎn)的連通無向圖，其邊的個(gè)數(shù)至少為 。A、n-1 B、n G n+1 D、nlog2n8、下列說法中，正確的有。A、最小生成樹也是哈夫曼樹B、最小生成樹唯一C普里姆最小生成樹算法時(shí)間復(fù)雜度為 O (n2)D、克魯斯卡爾最小生成樹算法普里姆算法更適合與邊稠密的網(wǎng)。10、判定一個(gè)有向圖是否存在回路，除了可以利用拓?fù)渑判虻姆椒ㄍ猓€可以利用 。A、求關(guān)鍵路徑的方法 B、求最短路徑的Dijkstr

3、a方法C、深度優(yōu)先遍歷算法D、廣度優(yōu)先遍歷算法11、在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度之和為s,則所有頂點(diǎn)的入度之和為。A、s B s-1 G s+1 D n12、在一個(gè)無向圖中，若兩個(gè)頂點(diǎn)之間的路徑長度為k,則該路徑上的頂點(diǎn)數(shù)為 。A、k B、k+1 C k+2 D 2k13、一個(gè)有n個(gè)頂點(diǎn)的無向連通圖，它所包含的連通分量個(gè)數(shù)為 。A、0 B、1 C n D、n+114、對于一個(gè)有向圖，若一個(gè)頂點(diǎn)的入度為k1、出度k2,則對應(yīng)鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為。A、k1 B、k2 C k1-k2 D、k1+k215、對于一個(gè)有向圖，若一個(gè)頂點(diǎn)的入度為k1、出度k2,則對應(yīng)逆鄰接表中

4、該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為。A、k1 B、k2 C k1-k2 D k1+k216、為了方便地對圖狀結(jié)構(gòu)的數(shù)據(jù)進(jìn)行存取操作，則其中數(shù)據(jù)存儲結(jié)構(gòu)宜采用 。A、順序存儲B、鏈?zhǔn)酱鎯、索引存儲D、散列存儲二、填空題1、具有10個(gè)頂點(diǎn)的無向圖，邊的總數(shù)最多為45。2、在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)2 (n-1)。3、克魯斯卡爾算法的時(shí)間復(fù)雜度為O (elog2e)，它對稀疏圖較為適合。4、若一個(gè)連通圖中每個(gè)邊上的權(quán)值均不同，則得到的最小生成樹是唯一 的。5、深度優(yōu)先搜索遍歷類似于樹的前序 遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是 棧；廣度優(yōu)先搜 索遍歷類似于樹的 按層次 遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是 隊(duì)

5、列6、一個(gè)圖的鄰接矩陣表示法是唯一的，而鄰接表 表示法是不唯一的。7、對無向圖，若它有n 個(gè)頂點(diǎn) e 條邊，則其鄰接表中需要2e+n 個(gè)結(jié)點(diǎn)。其中，2e 個(gè)結(jié)點(diǎn)構(gòu)成鄰接表，n 個(gè) 結(jié)點(diǎn)構(gòu)成頂點(diǎn)表。三、判斷題1、在n個(gè)結(jié)點(diǎn)的無向圖中，若邊數(shù)n-1,則該圖必是連通圖。（錯(cuò)）2、任何AOV網(wǎng)拓?fù)渑判虻慕Y(jié)果都是唯一的。（錯(cuò)）3、有回路的圖不能進(jìn)行拓?fù)渑判?。?對 ）4、一個(gè)圖的廣度優(yōu)先搜索使是唯一的。（ 錯(cuò) ）5、圖的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列不是唯一的。（ 對 ）第六章圖的習(xí)題解析21. 填空題 設(shè)無向圖G中頂點(diǎn)數(shù)為n,則圖G至少有（0）條邊，至多有（n（n-1）/2 ）條邊；若G為有向圖，

6、則至少有（0）條邊，至多有（n（n-1）條邊。 任何連通圖的連通分量只有一個(gè)，即是（其自身 ） 。 圖的存儲結(jié)構(gòu)主要有兩種，分別是（鄰接矩陣 ）和（ 鄰接表 ） 。 已知無向圖G的頂點(diǎn)數(shù)為n,邊數(shù)為e,其鄰接表表示的空間復(fù)雜度為（O（n+e）。 已知一個(gè)有向圖的鄰接矩陣表示，計(jì)算第j 個(gè)頂點(diǎn)的入度的方法是（求第 j 列的所有元素之和 ） 。 有向圖 G 用鄰接矩陣Ann 存儲，其第i 行的所有元素之和等于頂點(diǎn)i 的（ 出度 ） 。 圖的深度優(yōu)先遍歷類似于樹的（前序 ）遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是（棧 ） ；圖的廣度優(yōu)先遍歷類似于樹的（層序 ）遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是（隊(duì)列 ） 。 對于含有n個(gè)

7、頂點(diǎn)e條邊的連通圖，利用Prim算法求最小生成樹的時(shí)間復(fù)雜度為（O （n2）,利用Kruskal算法求最小生成樹的時(shí)間復(fù)雜度為（O（elog2e）。 如果一個(gè)有向圖不存在（回路 ） ，則該圖的全部頂點(diǎn)可以排列成一個(gè)拓?fù)湫蛄小?. 選擇題 在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（）倍。A、1/2B、1C、2D、4 n 個(gè)頂點(diǎn)的強(qiáng)連通圖至少有（）條邊，其形狀是（） 。A、nB、 n+1 C、n-1 D、 nX（n-1）E、無回路F、有回路G、環(huán)狀 H、樹狀 含 n 個(gè)頂點(diǎn)的連通圖中的任意一條簡單路徑，其長度不可能超過（） 。A 、 1B、 n/2C、 n-1D 、 n 對于一個(gè)具有n 個(gè)

8、頂點(diǎn)的無向圖，若采用鄰接矩陣存儲，則該矩陣的大小是（） 。A、nB、（n-1）2 C 、 n-1D、n2 圖的生成樹（） ， n 個(gè)頂點(diǎn)的生成樹有（）條邊。A、唯一B、不唯一C、唯一性不能確定D、nE、n +1F、n-1 設(shè)無向圖G=（V, E和G'=（V', E'），如果G'是G的生成樹，則下面的說法中錯(cuò)誤的是（）A、G為G的子圖B、G'為G的連通分量C、G為G的極小連通子圖且 V = V' D、G'是G的一個(gè)無環(huán)子圖 G 是一個(gè)非連通無向圖，共有28 條邊，則該圖至少有（）個(gè)頂點(diǎn)。A、6B、7C、 8D、9 最小生成樹指的是（）。A、

9、由連通網(wǎng)所得到的邊數(shù)最少的生成樹B、由連通網(wǎng)所得到的頂點(diǎn)數(shù)相對較少的生成樹C、 連通網(wǎng)中所有生成樹中權(quán)值之和為最小的生成樹D、連通網(wǎng)的極小連通子圖 判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以用（A、求關(guān)鍵路徑的方法B、求最短路徑的方法C、廣度優(yōu)先遍歷算法D、深度優(yōu)先遍歷算法3. 判斷題 一個(gè)有向圖的鄰接表和逆鄰接表中的結(jié)點(diǎn)個(gè)數(shù)一定相等。對 用鄰接矩陣存儲圖，所占用的存儲空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。 對 圖 G 的生成樹是該圖的一個(gè)極小連通子圖。錯(cuò) 無向圖的鄰接矩陣一定是對稱的，有向圖的鄰接矩陣一定是不對稱的。錯(cuò) 對任意一個(gè)圖，從某頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或

10、廣度優(yōu)先遍歷，可訪問圖的所有頂點(diǎn)。 錯(cuò) 在一個(gè)有向圖的拓?fù)湫蛄兄校繇旤c(diǎn)a 在頂點(diǎn) b 之前，則圖中必有一條弧。錯(cuò) 若一個(gè)有向圖的鄰接矩陣中對角線以下元素均為零，則該圖的拓?fù)湫蛄斜囟ù嬖凇λ?應(yīng)用題1 . n 個(gè)頂點(diǎn)的無向圖，采用鄰接表存儲，回答下列問題 圖中有多少條邊 任意兩個(gè)頂點(diǎn)i 和 j 是否有邊相連 任意一個(gè)頂點(diǎn)的度是多少解答】 邊表中的結(jié)點(diǎn)個(gè)數(shù)之和除以2。 第 i 個(gè)邊表中是否含有結(jié)點(diǎn)j。 該頂點(diǎn)所對應(yīng)的邊表中所含結(jié)點(diǎn)個(gè)數(shù)。2 n 個(gè)頂點(diǎn)的無向圖，采用鄰接矩陣存儲，回答下列問題： 圖中有多少條邊 任意兩個(gè)頂點(diǎn)i 和 j 是否有邊相連 任意一個(gè)頂點(diǎn)的度是多少【解答】 鄰接矩陣中非零元

11、素個(gè)數(shù)的總和除以 2。 當(dāng)鄰接矩陣A中Aij=1 (或Aji=1 )時(shí)，表示兩頂點(diǎn)之間有邊相連。 計(jì)算鄰接矩陣上該頂點(diǎn)對應(yīng)的行上非零元素的個(gè)數(shù)。3 .已知一個(gè)連通圖如圖6-6所示，試給出圖的鄰接矩陣和鄰接表存儲示意圖，若從頂點(diǎn)v1出發(fā)對該圖進(jìn)行遍歷，分別給出一個(gè)按深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點(diǎn)序列。圖第了題圖解答：鄰接矩陣表示如下:0101(J110 111001C01011CG11011100100130V.-深度優(yōu)先遍歷序列為：v1 v2 v3 v5 v4 v6廣度優(yōu)先遍歷序列為：v1 v2 v4 v6 v3 v5鄰接表表示如下：4.圖6-7所示是一個(gè)無向帶權(quán)圖，請分別按 Prim算法和Kruskal算法求最小生成樹。13 6-7第X題圖【解答】按Prim算法求最小生成樹的過程如下:按Kruskal算法求最小生成樹的過程如下:5.對于圖6-8所示的帶權(quán)有向圖，求從源點(diǎn)v1到其他各頂點(diǎn)的最短路徑解答:第1廣V2PYAV-.心忡T?7W3 口2GTOPlbEWAHP力AW加色,叫u»gw13：v：.-J,',n；國ir加耳二，A口舉22-' LVX3g*13；TLVJ.V4)ip'CVI55)*WP方 (VL77)(即m不g。13CV|,V：>心 m.rmw*<VLV7>*的A(Vl.VV.VSk小(V