數(shù)據(jù)結(jié)構(gòu)七圖模擬測試題

1、第七章圖復(fù)習(xí)測試題填空題（本題共10分）設(shè)無向圖G中頂點數(shù)為n則圖G至少有（）條邊，至多有（）條邊；若G為有向圖，則至少有（）條邊，至多有（）條邊?！窘獯稹?，n（n-1）/2，0，n（n-1）任何連通圖的連通分量只有一個，即是（）?！窘獯稹科渥陨韴D的存儲結(jié)構(gòu)主要有兩種，分別是（）和（）?！窘獯稹苦徑泳仃?，鄰接表已知無向圖G的頂點數(shù)為n邊數(shù)為e,其鄰接表表示的空間復(fù)雜度為（）。【解答】o（n+e）已知一個有向圖的鄰接矩陣表示，計算第j個頂點的入度的方法是（）?！窘獯稹壳蟮趈列的所有元素之和有向圖G用鄰接矩陣Ann存儲，其第i行的所有元素之和等于頂點i的（）?！窘獯稹砍龆葓D的深度優(yōu)先遍歷類似于樹

2、的（）遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是（）；圖的廣度優(yōu)先遍歷類似于樹的（）遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是（）?！窘獯稹壳靶颍瑮?，層序，隊列對于含有n個頂點e條邊的連通圖，利用Prim算法求最小生成樹的時間復(fù)雜度為（），利用Kruskal算法求最小生成樹的時間復(fù)雜度為（）。【解答】o（n2），o（elog2e）如果一個有向圖不存在（），則該圖的全部頂點可以排列成一個拓撲序列?！窘獯稹炕芈吩谝粋€有向圖中，若存在弧vi,vj、vj,vk、vi,vk，則在其拓撲序列中，頂點vi,vj,vk的相對次序為（）?！窘獯稹縱i,vj,vk（11）.n個頂點的連通圖用鄰接矩陣表示時，該矩陣至少有（）個非零元素。【解答】2

3、（n-1）（12）表示一個有100個頂點，1000條邊的有向圖的鄰接矩陣有（）個非零矩陣元素?！窘獯稹?000（13）十字鏈表適合存儲（），鄰接多重表適合存儲（）?！窘獯稹坑邢驁D，無向圖選擇題（本題20分）在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（）倍。A1/2B1C2D4【解答】Cn個頂點的強連通圖至少有（）條邊，其形狀是（）。AnBn+1Cn-1Dnx（n-1）E無回路F有回路G環(huán)狀H樹狀【解答】A，G含n個頂點的連通圖中的任意一條簡單路徑，其長度不可能超過（）A1Bn/2Cn-1Dn【解答】C對于一個具有n個頂點的無向圖，若采用鄰接矩陣存儲，則該矩陣的大小是（）。AnB（n-1）

4、2Cn-1Dn2【解答】D圖的生成樹（），n個頂點的生成樹有（）條邊。A唯一B不唯一C唯一性不能確定DnEn+1Fn-1【解答】C，F(xiàn)設(shè)無向圖G=（V,E）和G=（V,E），如果G是G的生成樹，則下面的說法中錯誤的是（）。AG為G的子圖BG為G的連通分量CG為G的極小連通子圖且V=VDG是G的一個無環(huán)子圖【解答】BG是一個非連通無向圖，共有28條邊，則該圖至少有（）個頂點。A6B7C8D9【解答】D最小生成樹指的是()。A由連通網(wǎng)所得到的邊數(shù)最少的生成樹B由連通網(wǎng)所得到的頂點數(shù)相對較少的生成樹C連通網(wǎng)中所有生成樹中權(quán)值之和為最小的生成樹D連通網(wǎng)的極小連通子圖判定一個有向圖是否存在回路除了可以利

5、用拓撲排序方法外，還可以用()。A求關(guān)鍵路徑的方法B求最短路徑的方法C廣度優(yōu)先遍歷算法D深度優(yōu)先遍歷算法【解答】D下面關(guān)于工程計劃的AOE網(wǎng)的敘述中，不正確的是()A關(guān)鍵活動不按期完成就會影響整個工程的完成時間B任何一個關(guān)鍵活動提前完成，那么整個工程將會提前完成C所有的關(guān)鍵活動都提前完成，那么整個工程將會提前完成D某些關(guān)鍵活動若提前完成，那么整個工程將會提前完【解答】B.在一個具有n個頂點的有向完全圖中包含有()條邊：An(n-1)/2Bn(n-1)Cn(n+1)/2Dn2【解答】B.個具有n個頂點k條邊的無向圖是一個森林(nk),則該森林中必有()棵樹。AkBnCn-kD1【解答】C.用深度

6、優(yōu)先遍歷方法遍歷一個有向無環(huán)圖，并在深度優(yōu)先遍歷算法中按退棧次序打印出相應(yīng)的頂點，則輸出的頂點序列是()。A逆拓撲有序B拓撲有序C無序D深度優(yōu)先遍歷序列【解答】A.關(guān)鍵路徑是AOE網(wǎng)中()。A從源點到終點的最長路徑B從源點到終點的最長路徑C最長的回路D最短的回路【解答】A(15).無向圖的鄰接矩陣是一個()，有向圖的鄰接矩陣是一個()A上三角矩陣B下三角矩陣C對稱矩陣D無規(guī)律【解答】C，D（16）下列命題正確的是（）。A一個圖的鄰接矩陣表示是唯一的，鄰接表表示也唯一B一個圖的鄰接矩陣表示是唯一的，鄰接表表示不唯一C一個圖的鄰接矩陣表示不唯一的，鄰接表表示是唯一D一個圖的鄰接矩陣表示不唯一的，鄰

7、接表表示也不唯一【解答】B判斷題（本題10分）一個有向圖的鄰接表和逆鄰接表中的結(jié)點個數(shù)一定相等?！窘獯稹繉?。用鄰接矩陣存儲圖，所占用的存儲空間大小只與圖中頂點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。【解答】對。圖G的生成樹是該圖的一個極小連通子圖【解答】錯。無向圖的鄰接矩陣一定是對稱的，有向圖的鄰接矩陣一定是不對稱的【解答】錯。對任意一個圖，從某頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先遍歷，可訪問圖的所有頂點。【解答】錯。在一個有向圖的拓撲序列中，若頂點a在頂點b之前，則圖中必有一條弧?！窘獯稹垮e。若一個有向圖的鄰接矩陣中對角線以下元素均為零，則該圖的拓撲序列必定存在?！窘獯稹繉?。在AOE網(wǎng)中一定只有一條關(guān)鍵路

8、徑。【解答】錯。四、綜合題（本題共45分）1.n個頂點的無向圖，采用鄰接表存儲，回答下列問題?圖中有多少條邊？任意兩個頂點i和j是否有邊相連？任意一個頂點的度是多少?【解答】邊表中的結(jié)點個數(shù)之和除以2。第i個邊表中是否含有結(jié)點j。該頂點所對應(yīng)的邊表中所含結(jié)點個數(shù)。2n個頂點的無向圖，采用鄰接矩陣存儲，回答下列問題：圖中有多少條邊？任意兩個頂點i和j是否有邊相連？任意一個頂點的度是多少？【解答】鄰接矩陣中非零元素個數(shù)的總和除以2。當(dāng)鄰接矩陣A中Aij=l(或Aji=l)時，表示兩頂點之間有邊相連。計算鄰接矩陣上該頂點對應(yīng)的行上非零元素的個數(shù)。3已知一個連通圖如圖6-6所示，試給出圖的鄰接矩陣和鄰

9、接表存儲示意圖，若從頂點v1出發(fā)對該圖進行遍歷，分別給出一個按深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點序列。解答】鄰接矩陣表示如下：01010-101110010010110011011100100100深度優(yōu)先遍歷序列為：v1v2v3v5v4v6廣度優(yōu)先遍歷序列為：v1v2v4v6v3v5鄰接表表示如下：4圖6-7所示是一個無向帶權(quán)圖，請分別按Prim算法和Kruskal算法求最小生成樹。解答】按Prim算法求最小生成樹的過程如下：按Kruskal算法求最小生成樹的過程如下：5對于圖6-8所示的帶權(quán)有向圖，求從源點v1到其他各頂點的最短路徑?！窘獯稹繌脑袋cv1到其他各頂點的最短路徑如下表所示。源點終

10、點最短路徑最短路徑長度v1v7v1v77v1v5v1v511v1v4v1v7v413v1v6v1v7v4v616v1v2v1v7v222v1v3v1v7v4v6v3256如圖6-9所示的有向網(wǎng)圖，利用Dijkstra算法求從頂點v1到其他各頂點的最短路徑。【解答】從源點v1到其他各頂點的最短路徑如下表所示。源點終點最短路徑最短路徑長度v1v3v1v315v1v5v1v515v1v2v1v3v225v1v6v1v3v2v640v1v4v1v3v2v4457.已知無向圖G的鄰接表如圖6-10所示，分別寫出從頂點1出發(fā)的深度遍歷和廣度遍歷序列，并畫出相應(yīng)的生成樹。1*24-A21氣Ar1*J.34.4rA1JA4:3.A二AJul6*5A16-10無向團的鄰接表【解答】深度優(yōu)先遍歷序列為：1，2，3