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

數(shù)據(jù)構(gòu)造第六章圖練習(xí)題及答案詳盡分析(精髓版)數(shù)據(jù)構(gòu)造第六章圖練習(xí)題及答案詳盡分析(精髓版)數(shù)據(jù)構(gòu)造第六章圖練習(xí)題及答案詳盡分析(精髓版)圖1.填空題⑴設(shè)無(wú)向圖G中極點(diǎn)數(shù)為n，那么圖G起碼有〔〕條邊，至多有〔〕條邊；假定條邊，至多有〔〕條邊。【解答】0，n(n-1)/2，0，n(n-1)

G為有向圖，那么起碼有〔

〕【剖析】圖的極點(diǎn)會(huì)合是有窮非空的，而邊集能夠是空集；邊數(shù)抵達(dá)最多的圖稱為完整圖，在完整圖中，隨意兩個(gè)極點(diǎn)之間都存在邊。⑵任何連通圖的連通重量只有一個(gè)，即是〔〕?！窘獯稹科渥约孩菆D的儲(chǔ)存構(gòu)造主要有兩種，分別是〔〕和〔〕?！窘獯稹颗従仃嚕彵怼酒饰觥窟@是最常用的兩種儲(chǔ)存構(gòu)造，別的，還有十字鏈表、毗鄰多重表、邊集數(shù)組等。⑷無(wú)向圖G的極點(diǎn)數(shù)為n，邊數(shù)為e，其毗鄰表表示的空間復(fù)雜度為〔〕。【解答】Ｏ(n+e)【剖析】在無(wú)向圖的毗鄰表中，極點(diǎn)表有n個(gè)結(jié)點(diǎn)，邊表有2e個(gè)結(jié)點(diǎn)，共有為Ｏ(n+2e)=Ｏ(n+e)。⑸一個(gè)有向圖的毗鄰矩陣表示，計(jì)算第j個(gè)極點(diǎn)的入度的方法是〔〕。【解答】求第j列的所有元素之和

n+2e個(gè)結(jié)點(diǎn)，其空間復(fù)雜度⑹有向圖G用毗鄰矩陣

A[n][n]

儲(chǔ)存，其第

i行的所有元素之和等于極點(diǎn)

i

的〔〕?！窘獯稹砍龆娶藞D的深度優(yōu)先遍歷近似于樹的〔的〔〕遍歷，它所用到的數(shù)據(jù)構(gòu)造是〔

〕遍歷，它所用到的數(shù)據(jù)構(gòu)造是〔〕。

〕；圖的廣度優(yōu)先遍歷近似于樹【解答】前序，棧，層序，行列⑻對(duì)于含有n個(gè)極點(diǎn)e條邊的連通圖，利用Prim算法求最小生成樹的時(shí)間復(fù)雜度為〔算法求最小生成樹的時(shí)間復(fù)雜度為〔〕?！窘獯稹浚?n2)，Ｏ(elog2e)【剖析】Prim算法采納毗鄰矩陣做儲(chǔ)存構(gòu)造，合適于求濃密圖的最小生成樹；Kruskal做儲(chǔ)存構(gòu)造，合適于求稀少圖的最小生成樹。

〕，利用Kruskal算法采納邊集數(shù)組⑼假如一個(gè)有向圖不存在〔〕，那么該圖的所有極點(diǎn)能夠擺列成一個(gè)拓?fù)湫蛄??！窘獯稹炕芈发卧谝粋€(gè)有向圖中，假定存在弧、、，那么在其拓?fù)湫蛄兄校瑯O點(diǎn)【解答】vi,vj,vk【剖析】對(duì)由極點(diǎn)vi,vj,vk構(gòu)成的圖進(jìn)行拓?fù)渑判颉?/p>

vi,vj,vk

的相對(duì)序次為〔

〕。2.選擇題⑴在一個(gè)無(wú)向圖中，所有極點(diǎn)的度數(shù)之和等于所有邊數(shù)的〔

〕倍。A1/2B1C2D4【解答】C【剖析】設(shè)無(wú)向圖中含有

n個(gè)極點(diǎn)

e條邊，那么

。⑵

n

個(gè)極點(diǎn)的強(qiáng)連通圖起碼有〔

〕條邊，其形狀是〔

〕。AnBn+1Cn-1Dn

×(n-1)E無(wú)回路

F有回路

G環(huán)狀

H樹狀【解答】

A，G⑶含

n

個(gè)極點(diǎn)的連通圖中的隨意一條簡(jiǎn)單路徑，其長(zhǎng)度不行能超出〔

〕。A1Bn/2Cn-1Dn【解答】C【剖析】假定超出n-1，那么路徑中必存在重復(fù)的極點(diǎn)。⑷對(duì)于一個(gè)擁有n個(gè)極點(diǎn)的無(wú)向圖，假定采納毗鄰矩陣儲(chǔ)存，那么該矩陣的大小是〔〕。AnB(n-1)2Cn-1Dn2【解答】D⑸圖的生成樹〔〕，n個(gè)極點(diǎn)的生成樹有〔〕條邊。A獨(dú)一B不獨(dú)一C獨(dú)一性不可以確立DnEn+1Fn-1【解答】C，F(xiàn)⑹設(shè)無(wú)向圖G=(V,E)和G'=(V',E')，假如G'是G的生成樹，那么下邊的說(shuō)法中錯(cuò)誤的選項(xiàng)是〔〕。AG'為G的子圖BG'為G的連通重量CG'為G的極小連通子圖且V=V'DG'是G的一個(gè)無(wú)環(huán)子圖【解答】B【剖析】連通重量是無(wú)向圖的極大連通子圖，此中極大的含義是將依賴于連通重量中極點(diǎn)的所有邊都加上，所以，連通重量中可能存在回路。⑺G是一個(gè)非連通無(wú)向圖，共有28條邊，那么該圖起碼有〔〕個(gè)極點(diǎn)。A6B7C8D9【解答】D【剖析】n個(gè)極點(diǎn)的無(wú)向圖中，邊數(shù)e≤n(n-1)/2，將e=28代入，有n≥8，現(xiàn)無(wú)向圖非連通，那么n=9。⑻最小生成樹指的是〔〕。由連通網(wǎng)所獲得的邊數(shù)最少的生成樹由連通網(wǎng)所獲得的極點(diǎn)數(shù)相對(duì)較少的生成樹連通網(wǎng)中所有生成樹中權(quán)值之和為最小的生成樹連通網(wǎng)的極小連通子圖【解答】C⑼判斷一個(gè)有向圖能否存在回路除了能夠利用拓?fù)渑判蚍椒ㄍ猓€能夠用〔〕。A求重點(diǎn)路徑的方法B求最短路徑的方法C廣度優(yōu)先遍歷算法D深度優(yōu)先遍歷算法【解答】D【剖析】當(dāng)有向圖中無(wú)回路時(shí)，從某極點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷時(shí)，出棧的次序〔退出即為逆向的拓?fù)湫蛄小?/p>

DFSTraverse

算法〕⑽下邊對(duì)于工程方案的AOE網(wǎng)的表達(dá)中，不正確的選項(xiàng)是〔工程的達(dá)成時(shí)間

〕?br/>A

重點(diǎn)活動(dòng)不如期達(dá)成就會(huì)影響整個(gè)任何一個(gè)重點(diǎn)活動(dòng)提早達(dá)成，那么整個(gè)工程將會(huì)提早達(dá)成所有的重點(diǎn)活動(dòng)都提早達(dá)成，那么整個(gè)工程將會(huì)提早達(dá)成某些重點(diǎn)活動(dòng)假定提早達(dá)成，那么整個(gè)工程將會(huì)提早完【解答】B【剖析】AOE網(wǎng)中的重點(diǎn)路徑可能不只一條，假如某一個(gè)重點(diǎn)活動(dòng)提早達(dá)成，還不可以提早整個(gè)工程，而一定同時(shí)提升在幾條重點(diǎn)路徑上的重點(diǎn)活動(dòng)。判斷題⑴一個(gè)有向圖的毗鄰表和逆毗鄰表中的結(jié)點(diǎn)個(gè)數(shù)必定相等?！窘獯稹繉?duì)。毗鄰表和逆毗鄰表的差別僅在于出邊和入邊，邊表中的結(jié)點(diǎn)個(gè)數(shù)都等于有向圖中邊的個(gè)數(shù)。⑵用毗鄰矩陣儲(chǔ)存圖，所占用的儲(chǔ)存空間大小只與圖中極點(diǎn)個(gè)數(shù)相關(guān)，而與圖的邊數(shù)沒(méi)關(guān)。【解答】對(duì)。毗鄰矩陣的空間復(fù)雜度為Ｏ(n2)，與邊的個(gè)數(shù)沒(méi)關(guān)。⑶圖G的生成樹是該圖的一個(gè)極小連通子圖【解答】錯(cuò)。一定包括所有極點(diǎn)。⑷無(wú)向的接矩必定是稱的，有向的接矩必定是不稱的【解答】。有向的接矩不必定稱，比若有向完整的接矩就是稱的。⑸隨意一個(gè)，從某點(diǎn)出行一次深度先或廣度先遍，可的所有點(diǎn)?！窘獯稹?。只有通從某點(diǎn)出行一次遍，可的所有點(diǎn)。⑹在一個(gè)有向的拓?fù)湫蛄兄?，假定點(diǎn)【解答】。只好明從點(diǎn)a到點(diǎn)

a在點(diǎn)b以前，中必有一條弧。b有一條路徑。⑺假定一個(gè)有向的接矩中角以下元素均零，的拓?fù)湫蛄斜厝淮嬖?。【解答】。參?1的明。⑻在AOE網(wǎng)中必定只有一條關(guān)路徑?br/>【解答】。AOE網(wǎng)中可能有不只一條關(guān)路徑，他的路徑度同樣4．n個(gè)點(diǎn)的無(wú)向，采納接表存，回復(fù)以下?br/>⑴中有多少條？⑵隨意兩個(gè)點(diǎn)i和j能否有相？⑶隨意一個(gè)點(diǎn)的度是多少?br/>【解答】⑴表中的點(diǎn)個(gè)數(shù)之和除以2。⑵第i個(gè)表中能否含有點(diǎn)j。⑶點(diǎn)所的表中所含點(diǎn)個(gè)數(shù)。5．n個(gè)點(diǎn)的無(wú)向，采納接矩存，回復(fù)以下：⑴中有多少條？⑵隨意兩個(gè)點(diǎn)i和j能否有相？⑶隨意一個(gè)點(diǎn)的度是多少？【解答】⑴接矩中非零元素個(gè)數(shù)的和除以2。⑵當(dāng)接矩A中A[i][j]=1〔或A[j][i]=1〕，表示兩點(diǎn)之有相。⑶算接矩上點(diǎn)對(duì)應(yīng)的行上非零元素的個(gè)數(shù)。6．明：生成中最路徑的起點(diǎn)和點(diǎn)的度均１?！窘獯稹坑梅捶?。v1,v2,?,vk是生成的一條最路徑，此中，v1起點(diǎn)，vk點(diǎn)。假定vk的度2，取vk的另一個(gè)接點(diǎn)v，因?yàn)樯芍袩o(wú)回路，所以，v在最路徑上，然v1,v2,?,vk,v的路徑最，與假矛盾。所以生成中最路徑的點(diǎn)的度1。同理可起點(diǎn)v1的度不可以大于1，只好1。7．一個(gè)通如6-6所示，出的接矩和接表存表示，假定從點(diǎn)v1出行遍，分出一個(gè)按深度先遍和廣度先遍的點(diǎn)序列。【解答】毗鄰矩陣表示以下：深度優(yōu)先遍歷序列為：

v1v2v3v5v4v6廣度優(yōu)先遍歷序列為：

v1v2v4v6v3v5毗鄰表表示以下：8．圖6-7所示是一個(gè)無(wú)向帶權(quán)圖，請(qǐng)分別按Prim算法和Kruskal算法求最小生成樹?！窘獯稹堪碢rim算法求最小生成樹的過(guò)程以下：按Kruskal算法求最小生成樹的過(guò)程以下：9．對(duì)于圖6-8所示的帶權(quán)有向圖，求從源點(diǎn)v1到其余各極點(diǎn)的最短路徑?！窘獯稹繌脑袋c(diǎn)v1到其余各極點(diǎn)的最短路徑以下表所示。源點(diǎn)終點(diǎn)最短路徑最短路徑長(zhǎng)度v1v7v1v77v1v5v1v511v1v4v1v7v413v1v6v1v7v4v616v1v2v1v7v222v1v3v1v7v4v6v32510．如圖6-9所示的有向網(wǎng)圖，利用Dijkstra算法求從極點(diǎn)v1到其余各極點(diǎn)的最短路徑?！窘獯稹繌脑袋c(diǎn)v1到其余各點(diǎn)的最短路徑以下表所示。源點(diǎn)點(diǎn)最短路徑最短路徑度v1v3v1v315v1v5v1v515v1v2v1v3v225v1v6v1v3v2v640v1v4v1v3v2v44511．明：只需合適地?cái)[列點(diǎn)的序次，就能使有向無(wú)的接矩中主角以下的元素所有0。【解答】隨意n個(gè)點(diǎn)的有向無(wú)都能夠獲得一個(gè)拓?fù)湫蛄?。拓?fù)湫蛄衯0v1v2?vn-1，我來(lái)明此的接矩A上三角矩。明采納反法。假此的接矩不是上三角矩，那么，存在下i和j〔i>j〕，使得A[i][j]不等于零，即中存在從vi到vj的一條有向。由拓?fù)湫蛄械亩芍?，在隨意拓?fù)湫蛄兄?，vi的地點(diǎn)必定在vj以前，而在上述拓?fù)湫蛄衯0v1v2?vn-1中，因?yàn)閕>j，即vi的地點(diǎn)在vj以后，致矛盾。所以命正確。12.算法⑴算法，將一個(gè)無(wú)向的接矩接表?！窘獯稹肯戎靡粋€(gè)空的接表，而后在接矩上找不零的元素，找到后在接表的表中插入相的表點(diǎn)。接矩存構(gòu)定以下：constintMaxSize=10;templatestructAdjMatrix{Tvertex[MaxSize];//寄存中點(diǎn)的數(shù)intarc[MaxSize][MaxSize];//intvertexNum,arcNum;//

寄存中的數(shù)的點(diǎn)數(shù)和數(shù)};接表存構(gòu)定以下：constintMaxSize=10;structArcNode//定表點(diǎn){intadjvex;//接點(diǎn)域ArcNode*next;};templatestructVertexNode//定點(diǎn)表點(diǎn){Tvertex;ArcNode*firstedge;};structAdjList{VertexNodeadjlist[MaxSize];intvertexNum,arcNum;//圖的極點(diǎn)數(shù)和邊數(shù)};詳細(xì)算法以下：⑵設(shè)計(jì)算法，將一個(gè)無(wú)向圖的毗鄰表變換成毗鄰矩陣?！窘獯稹吭谂彵砩洗涡虻厝∶總€(gè)邊表中的結(jié)點(diǎn)，將毗鄰矩陣中對(duì)應(yīng)單元的值置為1。毗鄰矩陣和毗鄰表的儲(chǔ)存構(gòu)造定義與上題同樣。詳細(xì)算法以下：⑶設(shè)計(jì)算法，計(jì)算圖中出度為零的極點(diǎn)個(gè)數(shù)?！窘獯稹吭谟邢驁D的毗鄰矩陣中，一行對(duì)應(yīng)一個(gè)極點(diǎn)，每行的非零元素的個(gè)數(shù)等于對(duì)應(yīng)極點(diǎn)的出度。所以，當(dāng)某行非零元素的個(gè)數(shù)為零時(shí)，那么對(duì)應(yīng)極點(diǎn)的出度為零。據(jù)此，從第一行開始，查找每行的非零元素個(gè)數(shù)能否為零，假定是那么計(jì)數(shù)器加1。詳細(xì)算法以下：⑷以毗鄰表作儲(chǔ)存構(gòu)造，設(shè)計(jì)按深度優(yōu)先遍歷圖的非遞歸算法?！窘獯稹堪菀?.2.1。⑸一個(gè)有向圖的毗鄰表，編寫算法成立其逆毗鄰表。【解答】在有向圖中，假定毗鄰表中極點(diǎn)vi有毗鄰點(diǎn)vj，在逆毗鄰表中vj必定有毗鄰點(diǎn)vi，由此獲得本題算法思路：第一將逆毗鄰表的表頭結(jié)點(diǎn)firstedge域置空，而后逐行將表頭結(jié)點(diǎn)的毗鄰點(diǎn)進(jìn)行轉(zhuǎn)變。⑹分別鑒于深度優(yōu)先搜尋和廣度優(yōu)先搜尋編寫算法，判斷以毗鄰表儲(chǔ)存的有向圖中能否存在由極點(diǎn)vi到極點(diǎn)vj的路徑〔i≠j〕?！窘獯稹竣盆b于深度優(yōu)先遍歷：⑵鑒于廣度優(yōu)先遍歷：學(xué)習(xí)自測(cè)及答案1．某無(wú)向圖的毗鄰矩陣A=A3B6C9D以上答案均不正確

，能夠看出，該圖共有〔

〕個(gè)極點(diǎn)。【解答】

A2．無(wú)向圖的毗鄰矩陣是一個(gè)〔

〕，有向圖的毗鄰矩陣是一個(gè)〔

〕A上三角矩陣B下三角矩陣C對(duì)稱矩陣D無(wú)規(guī)律【解答】C，D3．以下命題正確的選項(xiàng)是〔〕。一個(gè)圖的毗鄰矩陣表示是獨(dú)一的，毗鄰表表示也獨(dú)一一個(gè)圖的毗鄰矩陣表示是獨(dú)一的，毗鄰表表示不獨(dú)一一個(gè)圖的毗鄰矩陣表示不獨(dú)一的，毗鄰表表示是獨(dú)一一個(gè)圖的毗鄰矩陣表示不獨(dú)一的，毗鄰表表示也不獨(dú)一【解答】B4．十字鏈表合適儲(chǔ)存〔

〕，毗鄰多重表合適儲(chǔ)存〔

〕?！窘獯稹坑邢驁D，無(wú)向圖5.在一個(gè)擁有

n個(gè)極點(diǎn)的有向完整圖中包括有〔

〕條邊：An(n-1)/2Bn(n-1)Cn(n+1)/2Dn2【解答】

B6．n個(gè)極點(diǎn)的連通圖用毗鄰矩陣表示時(shí)，該矩陣起碼有〔

〕個(gè)非零元素?！窘獯稹?/p>

2(n-1)7．表示一個(gè)有

100個(gè)極點(diǎn)，

1000條邊的有向圖的毗鄰矩陣有〔

〕個(gè)非零矩陣元素?！窘獯稹?/p>

10008．一個(gè)擁有

n個(gè)極點(diǎn)

k條邊的無(wú)向圖是一個(gè)叢林〔

n>k〕，那么該叢林中必有〔

〕棵樹。Ak

Bn

Cn-k

D1【解答】

C9．用深度優(yōu)先遍歷方法遍歷一個(gè)有向無(wú)環(huán)圖，并在深度優(yōu)先遍歷算法中按退棧序次打印出相應(yīng)的極點(diǎn)，那么輸出的極點(diǎn)序列是〔〕。A逆拓?fù)溆行駼拓?fù)溆行駽無(wú)序D深度優(yōu)先遍歷序