《數(shù)據(jù)結(jié)構(gòu)》-第七章

習(xí)題71選擇題1、在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（B）倍。A、1B、2C、3D、42、對(duì)于有N個(gè)頂點(diǎn)和E條邊的有向圖和無向圖，若采用邊集數(shù)組表示，則存于數(shù)組的邊數(shù)為（D）條。A、N，NB、N，EC、2N，2ED、E，E3、對(duì)用鄰接矩陣表示的圖進(jìn)行任一種遍歷時(shí)，其時(shí)間復(fù)雜度為（A）。A、O（N2）B、O（E）C、O（N）D、O（NE）4、N個(gè)頂點(diǎn)的強(qiáng)連通圖至少有（A）邊。A、NB、N1C、N1D、NN15、在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（B）倍；在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（C）倍。A、1/2B、2C、1D、472填空題1、設(shè)無向圖G的頂點(diǎn)數(shù)為N，圖G最少有（0）邊；最多有（NN1/2）條邊。若G為有向圖，則圖G最少有（0）邊，最多有（NN1）邊。具有N個(gè)頂點(diǎn)的無向完全圖，邊的總數(shù)為（NN1/2）；而具有N個(gè)項(xiàng)點(diǎn)的有向完全圖，邊的總數(shù)為（NN1）。2、在一個(gè)圖G的鄰接表表示中，每個(gè)頂點(diǎn)的鄰接表中所含的結(jié)點(diǎn)數(shù)，對(duì)于有向圖而言等于該頂點(diǎn)的（出度）；而對(duì)于無向圖而言等于該頂點(diǎn)的（度）。3、采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的（先根）遍歷；廣度優(yōu)先遍歷算法類似于二叉樹的（按層）遍歷。4、一個(gè)具有N個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要（N1）條邊；若是有向圖，至少需要（N）條邊。5、在無向圖G的鄰接矩陣A中，若AIJ1，則AJI（1）。73應(yīng)用題1、對(duì)于下面所示的圖（A）和（B），求出0341241230（A）（B）圖720（1）每一個(gè)圖的二元組表示，對(duì)于帶權(quán)圖，可將邊的權(quán)寫在該邊的后面；答（A）圖GAV,EV0,1,2,3,4E0,1,0,2,0,3,0,4,2,1,2,3,3,4（B）圖GBV,EV0,1,2,3,4E,（2）在（A）中的每個(gè)頂點(diǎn)的度，以及每個(gè)頂點(diǎn)的所有鄰接點(diǎn)和所有邊；答0度為4；鄰接點(diǎn)1，2，3，4；邊0,1,0,2,0,3,0,41度為2；鄰接點(diǎn)0，2；邊0,1,1,22度為3；鄰接點(diǎn)0，1，3；邊0,2,1,2,3,23度為3；鄰接點(diǎn)0，2，4；邊0,3,3,2,3,44度為2；鄰接點(diǎn)0，3；邊0,4,3,4（3）在（B）中的每個(gè)頂點(diǎn)的入度、出度和度，以及每個(gè)頂點(diǎn)的所有入邊和出邊；答0入度2；出度2；度4；入邊,；出邊,1入度2；出度1；度3；入邊,；出邊2入度0；出度4；度4；入邊無；出邊,3入度2；出度1；度3；入邊,；出邊4入度2；出度0；度2；入邊,；出邊無（4）在（A）中從0到4的所有簡單路徑及相應(yīng)路徑長度；答（04）1，（034）2，（0234）3，（01234）4（5）在（B）中從0到4的所有簡單路徑及相應(yīng)的帶權(quán)路徑長度；答（034）22、如圖所示有向圖，采用DIJKSTRA算法求出從頂點(diǎn)0到其它頂點(diǎn)的最短路徑，并說明整個(gè)計(jì)算過程。圖721解142350646614235064627（1）選4（2）選11423506462741423506462748（3）選4（4）選6142350646274814235064627486（5）選7（6）選8或選63、寫出上圖的一種拓?fù)湫蛄校粼谒泥徑颖泶鎯?chǔ)結(jié)構(gòu)中，每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從大到小鏈接的，則按此給出惟一一種拓?fù)湫蛄小＝馊我獾耐負(fù)湫蛄袨?312456惟一拓?fù)湫蛄袨?1324564、對(duì)圖722中所示圖分別寫出深度優(yōu)先遍歷和廣度優(yōu)先遍歷的項(xiàng)點(diǎn)序列。如果確定圖以鄰接矩陣存儲(chǔ)，則得到的遍歷頂點(diǎn)序列是什么解深度優(yōu)先遍歷（A）0123402341（B）0134203412廣度優(yōu)先遍歷（A）0123404321（B）0134203142鄰接矩陣存儲(chǔ)時(shí)深度優(yōu)先遍歷（A）01234（B）01342廣度優(yōu)先遍歷（A）01234（B）013425、對(duì)圖721中所示圖分別用克魯斯卡爾算法和普里姆算法（從頂點(diǎn)2開始）求出其最小生成樹。解用克魯斯卡爾算法142023002415253155324646112445666678用普里姆算法142350661462142350641462初始狀態(tài)（1）選1,21，進(jìn)行修改142350641462142350641462（2）選2,32，無需修改（3）選1,04，無需修改14235064141281423506414126（4）選2,54，進(jìn)行修改（5）選4,51，進(jìn)行修改（6）選4,66，結(jié)束142350641412674算法題（不做要求）1、在鄰接表的存儲(chǔ)結(jié)構(gòu)上，實(shí)現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。（可做為上機(jī)實(shí)踐題目）2、假定圖采用鄰接矩陣表示，編寫出進(jìn)行深度優(yōu)先搜索遍歷的非遞歸算法。3、根據(jù)下圖，編寫一個(gè)完整的程序?qū)崿F(xiàn)下列功能（1）建立圖的鄰