中國(guó)鐵道出版社數(shù)據(jù)結(jié)構(gòu)(第二版)單元8練習(xí)參考答案

1、單元練習(xí)判斷題(下列各題，正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打V；錯(cuò)誤的打X)(V)(1)圖可以沒有邊，但不能沒有頂點(diǎn)。(X)(2)在無向圖中，(V,V2)與(V2,V)是兩條不同的邊。(X)(3)鄰接表只能用于有向圖的存儲(chǔ)。(V)(4)一個(gè)圖的鄰接矩陣表示是唯一的。(X)(5)用鄰接矩陣法存儲(chǔ)一個(gè)圖時(shí)，所占用的存儲(chǔ)空間大小與圖中頂點(diǎn)個(gè)數(shù)無關(guān)，而只與圖的邊數(shù)有關(guān)。(X)(6)有向圖不能進(jìn)行廣度優(yōu)先遍歷。(V)(7)若一個(gè)無向圖的以頂點(diǎn)V為起點(diǎn)進(jìn)行深度優(yōu)先遍歷，所得的遍歷序列唯一，則可以唯一確定該圖。(V)(8)存儲(chǔ)無向圖的鄰接矩陣是對(duì)稱的，因此只要存儲(chǔ)鄰接矩陣的上三角(或下三角)部分就可以了。(X)(9)

2、用鄰接表法存儲(chǔ)圖時(shí)，占用的存儲(chǔ)空間大小只與圖中的邊數(shù)有關(guān)，而與結(jié)點(diǎn)的個(gè)數(shù)無關(guān)。(V)(10)若一個(gè)無向圖中任一頂點(diǎn)出發(fā)，進(jìn)行一次深度優(yōu)先遍歷，就可以訪問圖中所有的頂點(diǎn)，則該圖一定是連通的。填空題圖常用的存儲(chǔ)方式有鄰接矩陣和鄰接表等。圖的遍歷有：深度優(yōu)先搜和廣度優(yōu)先搜等方法。有條邊的無向圖鄰接矩陣中，的個(gè)數(shù)是n有向圖的邊也稱為弧。圖的鄰接矩陣表示法是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。有向圖用鄰接矩陣存儲(chǔ)，其第行的所有元素之和等于頂點(diǎn)的出度。n個(gè)頂點(diǎn)e條邊的圖若采用鄰接矩陣存儲(chǔ)，則空間復(fù)雜度為：OW)。n個(gè)頂點(diǎn)e條邊的圖若采用鄰接表存儲(chǔ)，則空間復(fù)雜度為：O(n+e)。設(shè)有一稀疏圖，則采用鄰接表存儲(chǔ)比較節(jié)

3、省空間。設(shè)有一稠密圖，則采用鄰接矩陣存儲(chǔ)比較節(jié)省空間。圖的逆鄰接表存儲(chǔ)結(jié)構(gòu)只適用于有向圖。個(gè)頂點(diǎn)的完全無向圖有條邊。有向圖的鄰接表表示適于求頂點(diǎn)的出度。有向圖的鄰接矩陣表示中，第i列上非0元素的個(gè)數(shù)為頂點(diǎn)V.的入度。1對(duì)于具有n個(gè)頂點(diǎn)的圖，其生成樹有且僅有n-1條邊。對(duì)n個(gè)頂點(diǎn)，e條弧的有向圖，其鄰接表表示中，需要n+e個(gè)結(jié)點(diǎn)。從圖中某一頂點(diǎn)出發(fā)，訪遍圖中其余頂點(diǎn)，且使每一頂點(diǎn)僅被訪問一次，稱這一過程為圖的遍歷。無向圖的鄰接矩陣一定是對(duì)稱矩陣。（19）一個(gè)連通網(wǎng)的最小生成樹是該圖所有生成樹中權(quán)最小的生成樹。（20）若要求一個(gè)稠密圖G的最小生成樹，最好用Prim算法來求解。三選擇題TOC o 1

4、-5 h z（）在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的倍。（）在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的倍。（）對(duì)于一個(gè)具有個(gè)頂點(diǎn)的有向圖的邊數(shù)最多有（）。（）在一個(gè)具有個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要（）條邊。（）有個(gè)結(jié)點(diǎn)的有向完全圖有條邊。（）深度優(yōu)先遍歷類似于二叉樹的。.先序遍歷.中序遍歷.后序遍歷.層次遍歷7）廣度優(yōu)先遍歷類似于二叉樹的（D。.先序遍歷.中序遍歷.后序遍歷.層次遍歷8）任何一個(gè)無向連通圖的最小生成樹（A。.只有一棵.一棵或多棵.定有多棵可能不存在（）無向圖頂點(diǎn)的度是關(guān)聯(lián)于該頂點(diǎn)（）的數(shù)目。.頂點(diǎn).邊序號(hào).下標(biāo)D（0有個(gè)頂點(diǎn)的無向圖的鄰接矩陣

5、是用（.）數(shù)組存儲(chǔ)。.一維.行歹U.任意行列.行任意列（1對(duì)于一個(gè)具有個(gè)頂點(diǎn)和條邊的無向圖，采用鄰接表表示，則表頭向量大小為（）。）。.鄰接表表示法.鄰接表和逆鄰接表表示法12）在圖的表示法中，表示形式唯一的是（.鄰接矩陣表示法逆鄰接表表示法（3在一個(gè)具有個(gè)頂點(diǎn)條邊的圖中，所有頂點(diǎn)的度數(shù)之和等于（）。14）下列圖中，度為3的結(jié)點(diǎn)是（B）。.連通圖強(qiáng)連通圖生成樹無環(huán)圖（16）如下圖所示，從頂點(diǎn)a出發(fā)，按深度優(yōu)先進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（D）。（17）如下圖所示，從頂點(diǎn)a出發(fā)，按廣度優(yōu)先進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（A）。18）最小生成樹的構(gòu)造可使用（A）算法。.算法.卡爾算法

6、.哈夫曼算法.迪杰斯特拉算法19）下面關(guān)于圖的存儲(chǔ)結(jié)構(gòu)的敘述中正確的是（A）。用鄰接矩陣存儲(chǔ)圖，占用空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，而與邊數(shù)無關(guān)用鄰接矩陣存儲(chǔ)圖，占用空間大小只與圖中邊數(shù)有關(guān)，而與頂點(diǎn)數(shù)無關(guān)用鄰接表存儲(chǔ)圖，占用空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，而與邊數(shù)無關(guān)用鄰接表存儲(chǔ)圖，占用空間大小只與圖中邊數(shù)有關(guān)，而與頂點(diǎn)數(shù)無關(guān)（0連通分量是（）的極大連通子圖。.樹.圖無向圖.有向圖四.應(yīng)用題（30分）有向圖如下圖所示，畫出鄰接矩陣和鄰接表解：（1）鄰接矩陣101101,2000102）鄰接表2已知一個(gè)無向圖有6個(gè)結(jié)點(diǎn)，9條邊，這9條邊依次為（0，1）,（0，2）,（0，4）,（0，5），（1，2），

7、（2，3），（2，4），（3，4），（4，5）。試畫出該無向圖，并從頂點(diǎn)0出發(fā)，分別寫出按深度優(yōu)先搜索和按廣度優(yōu)先搜索進(jìn)行遍歷的結(jié)點(diǎn)序列。（5分）解：從頂點(diǎn)0出發(fā)的深度優(yōu)先搜索遍歷的結(jié)點(diǎn)序列：012345（答案不唯一）從頂點(diǎn)0出發(fā)的廣度優(yōu)先搜索遍歷的結(jié)點(diǎn)序列：012453（答案不唯一）3.已知一個(gè)無向圖的頂點(diǎn)集為：a,b,c,d,e，其鄰接矩陣如下，畫出草圖，寫出頂點(diǎn)a出發(fā)按深度優(yōu)先搜索進(jìn)行遍歷的結(jié)點(diǎn)序列。（5分）01001100100001101101101102）深度優(yōu)先搜索：abdce廣度優(yōu)先搜索：abedc答案不唯一）答案不唯一），并畫出它的一棵最小生成樹。08101108030131

8、03040110407013070已知某圖的鄰接矩陣如圖,解：（1）0110011001100110（）畫出相應(yīng)的圖；2）要使此圖為完全圖需要增加幾條邊。2）完全無向圖應(yīng)具有的邊數(shù)為：n*（n-l）l/2=4*（4-l）/2=6，所以還要增加2條邊（如右圖）。3已知如圖所示的有向圖，請(qǐng)給出該圖的33出度；頂點(diǎn)123456入度321122出度022313LJK5-EI*1*A1iA3OOOOOO-)0010001000I0Q0I100000.110010-如圖，請(qǐng)完成以下操作：2）寫出無向帶權(quán)圖的鄰接矩陣；（）設(shè)起點(diǎn)為，求其最小生成樹。33可以直接由原一0000000000鄰）命(解（35a5g

9、00008548860g5g206刃6302刃g(shù)7038855076543505000000888一0000給定下列網(wǎng)解：鄰接矩陣（2）最小生成樹g12gg4gg12g20g89gg20g15gg12gg15ggg1048ggg6gg9gg6gggg1210ggg五程序題填空題圖G為有向無權(quán)圖，試在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)刪除一條邊的操作：DeleteArc（G,v,w）。若無頂點(diǎn)v或w,返回“”；若成功刪除，則邊數(shù)減，并返回“”。（提示：刪除一條邊的操作，可以將鄰接矩陣的第i行全部置0）解：在鄰接矩陣表示的圖上刪除邊（或六算法題1編寫一個(gè)無向圖的鄰接矩陣轉(zhuǎn)換成鄰接表的算法。2.以知有n個(gè)頂點(diǎn)的

10、有向圖鄰接表，設(shè)計(jì)算法分別實(shí)現(xiàn)以下功能:（1）求出圖G中每個(gè)頂點(diǎn)的出度、入度。（2）求出G中出度最大的一個(gè)頂點(diǎn)，輸出其頂點(diǎn)序號(hào)。3）計(jì)算圖中度為0的頂點(diǎn)數(shù)。1.解：本題思想是逐個(gè)掃描鄰接矩陣的各個(gè)元素，若第i行第j列的元素為1,貝I相應(yīng)的鄰接表的第i個(gè)單鏈表上增加一個(gè)j結(jié)點(diǎn)。（）求出度的思想：計(jì)算出鄰接表中第個(gè)單鏈表的結(jié)點(diǎn)數(shù)即可。求入度的思想：計(jì)算出鄰接表中結(jié)點(diǎn)的結(jié)點(diǎn)數(shù)即可。2）求最大度的算法3）求度為0的頂點(diǎn)數(shù)的算法已知如圖所示的有向圖，請(qǐng)給出該圖的頂點(diǎn)123456入度321122出度022313模擬考題度和出度;解：(1)鄰接矩陣(2)從A出發(fā)的深度優(yōu)先遍歷的序列:0110000，ABDCEGF（不唯一）100100010010000110110000100100010010000110已知圖的鄰接表如下，以頂點(diǎn)為出發(fā)點(diǎn)，完成下列問題:(