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

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