數(shù)據(jù)結(jié)構(gòu)第六章圖練習(xí)題及答案詳細(xì)解析(精華版)1888

圖1.填空題⑴設(shè)無向圖G中頂點數(shù)為n，則圖G至少有（）條邊，至多有（）條邊；若G為有向圖，則至少有（）條邊，至多有（）條邊?！窘獯稹?，n(n-1)/2，0，n(n-1)【分析】圖的頂點集合是有窮非空的，而邊集可以是空集；邊數(shù)達(dá)到最多的圖稱為完全圖，在完全圖中，任意兩個頂點之間都存在邊。⑵任何連通圖的連通分量只有一個，即是（）?！窘獯稹科渥陨恝菆D的存儲結(jié)構(gòu)主要有兩種，分別是（）和（）。【解答】鄰接矩陣，鄰接表【分析】這是最常用的兩種存儲結(jié)構(gòu)，此外，還有十字鏈表、鄰接多重表、邊集數(shù)組等。⑷已知無向圖G的頂點數(shù)為n，邊數(shù)為e，其鄰接表表示的空間復(fù)雜度為（）?！窘獯稹浚?n+e)【分析】在無向圖的鄰接表中，頂點表有n個結(jié)點，邊表有2e個結(jié)點，共有n+2e個結(jié)點，其空間復(fù)雜度為Ｏ(n+2e)=Ｏ(n+e)。⑸已知一個有向圖的鄰接矩陣表示，計算第j個頂點的入度的方法是（）?！窘獯稹壳蟮趈列的所有元素之和⑹有向圖G用鄰接矩陣A[n][n]存儲，其第i行的所有元素之和等于頂點i的（）?！窘獯稹砍龆?/p>

【解答】前序，棧，層序，隊列A1/2B1C2D4【解答】C【分析】設(shè)無向圖中含有n個頂點e條邊，則。⑵n個頂點的強(qiáng)連通圖至少有（）條邊，其形狀是（）。AnBn+1Cn-1Dn×(n-1)E無回路F有回路G環(huán)狀H樹狀【解答】A，G⑶含n個頂點的連通圖中的任意一條簡單路徑，其長度不可能超過（）。A1Bn/2Cn-1Dn【解答】C【分析】若超過n-1，則路徑中必存在重復(fù)的頂點。⑷對于一個具有n個頂點的無向圖，若采用鄰接矩陣存儲，則該矩陣的大小是（）。AnB(n-1)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=V'DG'是G的一個無環(huán)子圖【解答】B

【分析】連通分量是無向圖的極大連通子圖，其中極大的含義是將依附于連通分量中頂點的所有邊都加上，所以，連通分量中可能存在回路。⑺G是一個非連通無向圖，共有28條邊，則該圖至少有（）個頂點。A6B7C8D9【解答】D【分析】n個頂點的無向圖中，邊數(shù)e≤n(n-1)/2，將e=28代入，有n≥8，現(xiàn)已知無向圖非連通，則n=9。⑻最小生成樹指的是（）。A由連通網(wǎng)所得到的邊數(shù)最少的生成樹B由連通網(wǎng)所得到的頂點數(shù)相對較少的生成樹C連通網(wǎng)中所有生成樹中權(quán)值之和為最小的生成樹D連通網(wǎng)的極小連通子圖【解答】C⑼判定一個有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以用（）。A求關(guān)鍵路徑的方法C廣度優(yōu)先遍歷算法【解答】DB求最短路徑的方法D深度優(yōu)先遍歷算法【分析】當(dāng)有向圖中無回路時，從某頂點出發(fā)進(jìn)行深度優(yōu)先遍歷時，出棧的順序（退出DFSTraverse算法）即為逆向的拓?fù)湫蛄小＂蜗旅骊P(guān)于工程計劃的AOE網(wǎng)的敘述中，不正確的是（）?br/>A關(guān)鍵活動不按期完成就會影響整個工程完的成時間

B任何一個關(guān)鍵活動提前完成，那么整個工程將會提前完成C所有的關(guān)鍵活動都提前完成，那么整個工程將會提前完成D某些關(guān)鍵活動若提前完成，那么整個工程將會提前完【解答】B【分析】AOE網(wǎng)中的關(guān)鍵路徑可能不止一條，如果某一個關(guān)鍵活動提前完成，還不能提前整個工程，而必須同時提高在幾條關(guān)鍵路徑上的關(guān)鍵活動。3.判斷題⑴一個有向圖的鄰接表和逆鄰接表中的結(jié)點個數(shù)一定相等?！窘獯稹繉Α｀徑颖砗湍驵徑颖淼膮^(qū)別僅在于出邊和入邊，邊表中的結(jié)點個數(shù)都等于有向圖中邊的個數(shù)。⑵用鄰接矩陣存儲圖，所占用的存儲空間大小只與圖中頂點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)?！窘獯稹繉Α｀徑泳仃嚨目臻g復(fù)雜度為Ｏ(n2)，與邊的個數(shù)無關(guān)。⑶圖G的生成樹是該圖的一個極小連通子圖【解答】錯。必須包含全部頂點。⑷無向圖的鄰接矩陣一定是對稱的，有向圖的鄰接矩陣一定是不對稱的【解答】錯。有向圖的鄰接矩陣不一定對稱，例如有向完全圖的鄰接矩陣就是對稱的。⑸對任意一個圖，從某頂點出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先遍歷，可訪問圖的所有頂點?！窘獯稹垮e。只有連通圖從某頂點出發(fā)進(jìn)行一次遍歷，可訪問圖的所有頂點。⑹在一個有向圖的拓?fù)湫蛄兄?，若頂點a在頂點b之前，則圖中必有一條弧?！窘獯稹垮e。只能說明從頂點a到頂點b有一條路徑。

⑺若一個有向圖的鄰接矩陣中對角線以下元素均為零，則該圖的拓?fù)湫蛄斜囟ù嬖?。【解答】對。參見?1題的證明。⑻在AOE網(wǎng)中一定只有一條關(guān)鍵路徑?br/>【解答】錯。AOE網(wǎng)中可能有不止一條關(guān)鍵路徑，他們的路徑長度相同4．n個頂點的無向圖，采用鄰接表存儲，回答下列問題?br/>⑴圖中有多少條邊？⑵任意兩個頂點i和j是否有邊相連？⑶任意一個頂點的度是多少?br/>【解答】⑴邊表中的結(jié)點個數(shù)之和除以2。⑵第i個邊表中是否含有結(jié)點j。⑶該頂點所對應(yīng)的邊表中所含結(jié)點個數(shù)。5．n個頂點的無向圖，采用鄰接矩陣存儲，回答下列問題：⑴圖中有多少條邊？⑵任意兩個頂點i和j是否有邊相連？⑶任意一個頂點的度是多少？【解答】⑴鄰接矩陣中非零元素個數(shù)的總和除以2。⑵當(dāng)鄰接矩陣A中A[i][j]=1（或A[j][i]=1）時，表示兩頂點之間有邊相連。⑶計算鄰接矩陣上該頂點對應(yīng)的行上非零元素的個數(shù)。

【解答】用反證法證明。同理可證起點v1的度不能大于1，只能為1?！窘獯稹苦徑泳仃嚤硎救缦拢荷疃葍?yōu)先遍歷序列為：v1v2v3v5v4v6廣度優(yōu)先遍歷序列為：v1v2v4v6v3v5鄰接表表示如下：【解答】按Prim算法求最小生成樹的過程如下：按Kruskal算法求最小生成樹的過程如下：【解答】從源點v1到其他各頂點的最短路徑如下表所示。源點終點最短路徑最短路徑長度v1v7v1v77v1v5v1v511v1v4v1v7v413v1v6v1v7v4v616v1v2v1v7v222【解答】從源點v1到其他各頂點的最短路徑如下表所示。源點終點最短路徑最短路徑長度v1v3v1v315v1v5v1v515v1v2v1v3v225v1v6v1v3v2v640v1v4v1v3v2v44511．證明：只要適當(dāng)?shù)嘏帕许旤c的次序，就能使有向無環(huán)圖的鄰接矩陣中主對角線以下的元素全部為0?！窘獯稹咳我鈔個結(jié)點的有向無環(huán)圖都可以得到一個拓?fù)湫蛄?。設(shè)拓?fù)湫蛄袨関0v1v2…vn-1，我們來證明此時的鄰接矩陣A為上三角矩陣。證明采用反證法。假設(shè)此時的鄰接矩陣不是上三角矩陣，那么，存在下標(biāo)i和j（i>j），使得A[i][j]不等于零，即圖中存在從vi到vj的一條有向邊。由拓?fù)湫蛄械亩x可知，在任意拓?fù)湫蛄兄校瑅i的位置一定在vj之前，而在上述拓?fù)湫蛄衯0v1v2…vn-1中，由于i>j，即vi的位置在vj之后，導(dǎo)致矛盾。因此命題正確。12.算法設(shè)計⑴設(shè)計算法，將一個無向圖的鄰接矩陣轉(zhuǎn)換為鄰接表?！窘獯稹肯仍O(shè)置一個空的鄰接表，然后在鄰接矩陣上查找值不為零的元素，找到后在鄰接表的對應(yīng)單鏈表中插入相應(yīng)的邊表結(jié)點。鄰接矩陣存儲結(jié)構(gòu)定義如下：constintMaxSize=10;templatestructAdjMatrix{Tvertex[MaxSize];存//放圖中頂點的數(shù)組intarc[MaxSize][MaxSize];存//放圖中邊的數(shù)組intvertexNum,arcNum;圖//的頂點數(shù)和邊數(shù)};鄰接表存儲結(jié)構(gòu)定義如下：constintMaxSize=10;structArcNode定//義邊表結(jié)點{

intadjvex;鄰//接點域ArcNode*next;};templatestructVertexNode定//義頂點表結(jié)點{Tvertex;ArcNode*firstedge;};structAdjList{VertexNodeadjlist[MaxSize];intvertexNum,arcNum;圖//的頂點數(shù)和邊數(shù)};具體算法如下：

⑵設(shè)計算法，將一個無向圖的鄰接表轉(zhuǎn)換成鄰接矩陣。⑶設(shè)計算法，計算圖中出度為零的頂點個數(shù)?！窘獯稹吭谟邢驁D的鄰接矩陣中，一行對應(yīng)一個頂點，每行的非零元素的個數(shù)等于對應(yīng)頂點的出度。因此，⑷以鄰接表作存儲結(jié)構(gòu)，設(shè)計按深度優(yōu)先遍歷圖的非遞歸算法?！窘獯稹繀⒁?.2.1。⑸已知一個有向圖的鄰接表，編寫算法建立其逆鄰接表?！窘獯稹吭谟邢驁D中，若鄰接表中頂點vi有鄰接點vj，在逆鄰接表中vj一定有鄰接點vi，由此得到本題算法思路：首先將逆鄰接表的表頭結(jié)點firstedge域置空，然后逐行將表頭結(jié)點的鄰接點進(jìn)行轉(zhuǎn)化。⑵基于廣度優(yōu)先遍歷：1．某無向圖的鄰接矩陣A=，可以看出，該圖共有（）個頂點。A3B6C9D以上答案均不正確【解答】A2．無向圖的鄰接矩陣是一個（），有向圖的鄰接矩陣是一個（）A上三角矩陣B下三角矩陣C對稱矩陣D無規(guī)律【解答】C，D3．下列命題正確的是（）。A一個圖的鄰接矩陣表示是唯一的，鄰接表表示也唯一B一個圖的鄰接矩陣表示是唯一的，鄰接表表示不唯一C一個圖的鄰接矩陣表示不唯一的，鄰接表表示是唯一D一個圖的鄰接矩陣表示不唯一的，鄰接表表示也不唯一【解答】B4．十字鏈表適合存儲（），鄰接多重表適合存儲（）。【解答】有向圖，無向圖5.在一個具有n個頂點的有向完全圖中包含有（）條邊：An(n-1)/2Bn(n-1)Cn(n+1)/2Dn2【解答】B6．n個頂點的連通圖用鄰接矩陣表示時，該矩陣至少有（）個非零元素?！窘獯稹?(n-1)7．表示一個有100個頂點，1000條邊的有向圖的鄰接矩陣有（）個非零矩陣元素。【解答】10008．一個具有n個頂點k條邊的無向圖是一個森林（n>k），則該森林中必有（）棵樹。AkBnCn-kD1【解答】C9．用深度優(yōu)先遍歷方法遍歷一個有向無環(huán)圖，并在深度優(yōu)先遍歷算法中按退棧次序打印出