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

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

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

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

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

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

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

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

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

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

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