圖習(xí)題參考答案

1、習(xí)題六參考答案一、選擇題1. 在一個(gè)有個(gè)極點(diǎn)的有向圖中，若所有極點(diǎn)的出度之和為，則所有極點(diǎn)的人度之和為（A）。A.B.-1C.+1D.2. 一個(gè)有向圖有個(gè)極點(diǎn)，則每一個(gè)極點(diǎn)的度可能的最大值是（B）oA.n1B.2（n1）C.nD.2n3 .具有6個(gè)極點(diǎn)的無(wú)向圖至少應(yīng)有（A）條邊才能確保是一個(gè)連通圖。4 .一個(gè)有n個(gè)極點(diǎn)的無(wú)向圖最多有（C）條邊。A.nB.n（n1）C.n（n-1）/2D.2n5 .對(duì)某個(gè)無(wú)向圖的鄰接矩陣來(lái)講，下列敘述正確的是（A）。A.第i行上的非零元素個(gè)數(shù)和第i列上的非零元素個(gè)數(shù)必然相等B.矩陣中的非零元素個(gè)數(shù)等于圖中的邊數(shù)C.第i行與第i列上的非零元素的總數(shù)等于極點(diǎn)%的度數(shù)

2、D.矩陣中非全零行的行數(shù)等于圖中的極點(diǎn)數(shù)6 .已知一個(gè)有向圖的鄰接矩陣，要?jiǎng)h除所有以第i個(gè)頂點(diǎn)為孤尾的邊，應(yīng)該（B）。A.將鄰接矩陣的第i行刪除B.將鄰接矩陣的第i行元素全數(shù)置為0C.將鄰接矩陣的第i列刪除D.將鄰接矩陣的第i列元素全數(shù)置為07 .下面關(guān)于圖的存儲(chǔ)的敘述中，哪個(gè)是正確的？（A）A.用鄰接矩陣存儲(chǔ)圖，占用的存儲(chǔ)空間只與圖中頂點(diǎn)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)B.用鄰接矩陣存儲(chǔ)圖，占用的存儲(chǔ)空間只與圖中邊數(shù)有關(guān)，而與頂點(diǎn)數(shù)無(wú)關(guān)C.用鄰接表存儲(chǔ)圖，占用的存儲(chǔ)空間只與圖中頂點(diǎn)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)D.用鄰接表存儲(chǔ)圖，占用的存儲(chǔ)空間只與圖中邊數(shù)有關(guān)，而與頂點(diǎn)數(shù)無(wú)關(guān)8 .對(duì)圖的深度優(yōu)先遍歷，類似于對(duì)樹(shù)的

3、哪一種遍歷？（A）A.先根遍歷B.中根遍歷C.后根遍歷D.層次遍歷9 .任何一個(gè)無(wú)向連通圖的最小生成樹(shù)（B）。A.只有一棵B.有一棵或多棵C.必然有多棵D.可能不存在10 .下面是三個(gè)關(guān)于有向圖運(yùn)算的敘述：（1）求兩個(gè)指向結(jié)點(diǎn)間的最短路徑，其結(jié)果一定是唯一的（2）求有向圖結(jié)點(diǎn)的拓?fù)湫蛄?，其結(jié)果一定是唯一的（3）求AOE網(wǎng)的關(guān)鍵路徑，其結(jié)果一定是唯一的其中哪個(gè)（些）是正確的？（D）A,只有B. (1)和(2)C.都正確D.都不正確二、填空題1 .若用n表示圖中極點(diǎn)數(shù)，則有九江1)/2條邊的無(wú)向有稱為完全圖。2 .若一個(gè)無(wú)向圖有100條邊，則其極點(diǎn)總數(shù)最少為15個(gè).3 . n個(gè)極點(diǎn)的連通無(wú)向圖至少

4、有4 .如有向圖G的鄰接矩陣為:n -1條邊,最多有一%必%(01 01 °%10 11 1v201 01 1%00 00 1%1o0 10 0/n(n -1)/2 條邊。則極點(diǎn)做的入度是35 .對(duì)于一個(gè)有向圖，若一個(gè)極點(diǎn)的度為kl,出度為k2,則對(duì)應(yīng)逆鄰接表中該極點(diǎn)單鏈表中的邊結(jié)點(diǎn)數(shù)為kl一k2.6 .圖的遍歷算法BFS頂用到輔助隊(duì)列，每一個(gè)極點(diǎn)最多進(jìn)隊(duì)1次。7 .在求最小生成樹(shù)的兩種算法中，克魯斯卡爾算法適合于稀疏圖。8 .數(shù)據(jù)結(jié)構(gòu)中的迪杰斯特拉算法是用來(lái)求某個(gè)源點(diǎn)到其余各極點(diǎn)的最短路徑。9 .除利用拓?fù)渑判虻姆绞?，還有深度優(yōu)先搜索方式能夠判斷出一個(gè)有向圖是不是有回路。10 .在

5、用鄰接表表示圖時(shí)，拓?fù)渑判蛩惴ǖ臅r(shí)刻復(fù)雜度為O(n+e),三、應(yīng)用題(1)每一個(gè)極點(diǎn)的出/入度:(2)鄰接矩陣；(3)鄰接表：(4)逆鄰接表。答：(1)每一個(gè)極點(diǎn)的出/入度是:出度入度1032223214315126321234561/00000021001003010001400101151000006110010)鄰接矩陣:鄰接表:(4)逆鄰接表:0123450123452.試對(duì)如圖所示的非連通圖，畫(huà)出其廣度優(yōu)先生成叢林。答:圖錯(cuò)誤!文檔中沒(méi)有指定樣式的文字.非連通圖3.己知圖的鄰接矩陣如圖所示。試別離畫(huà)出自極點(diǎn)A動(dòng)身進(jìn)行遍歷所得的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。ABCDEFGHIJABC

6、/O00OOI000000000110001100000100D0010000100E0001000010FGHIJ010100100000100000101000100000000010001001001J10000/圖錯(cuò)誤!文檔中沒(méi)有指定樣式的文字鄰接矩陣答:4.請(qǐng)對(duì)如圖所示的無(wú)向網(wǎng):(1)寫(xiě)出它的鄰接矩陣，并按克魯斯卡爾算法求其最小生成樹(shù):(2)寫(xiě)出它的鄰接表，并按普里姆算法求其最小生成樹(shù)。圖錯(cuò)誤!文檔中沒(méi)有指定樣式的文字.無(wú)向網(wǎng)ABCDEFGH43co004 3oooo05595 05co55079oo70cooo63cocosooco54oo克魯斯卡爾算法求其最小生成樹(shù)0123456

7、7©oo©A二DcHEBAD一普里姆算法求其最小生成樹(shù),從A開(kāi)始A5.試列出圖中全數(shù)可能的拓?fù)溆行蛐蛄小c圖有向圖答：abcdef>abcef、abecdfxbacdefxbacedf>baecdfbeacdf四、算法設(shè)計(jì)題1.編寫(xiě)算法，從鍵盤(pán)讀入有向圖的極點(diǎn)和弧，創(chuàng)建有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)。參考答案：publicstaticALGraphcreateDGOScannersc=newScanner;"請(qǐng)別離輸入有向圖的極點(diǎn)數(shù)和邊數(shù):")；intvexNum=();intarcNum=();VNodevexs=newVNodevexNum;&

8、quot;請(qǐng)別離輸入有向圖的各個(gè)極點(diǎn)門(mén)；for(intv=0;v<vexNum;v+)錯(cuò)誤味定義書(shū)簽。H叫KqKetKey()>heapArrayj+l.getKey()j+；)if()<=hcapArrayfjJ.getKeyO)etKeyO<=()ength);)publicbooleandiffer(Objectu.Objectv)booleanisDiffer=false;intcount=0;for(inti=0;i<i+)if(Vi!=null&&(Vi.equals(u)IIVi.equals(v)+count;if(count=0I

9、Icount=2)isDiffer=true;returnisDiffer;)publicvoidunion(Objectu,Objectv)booleanisHaveU=false:quals(u)isHaveU=true;elseif(Si.equals(v)isHaveV=true;)if(JisHaveU)Si=u;if(JisHaveV)Si=v;)克魯斯卡爾算法只需取所有邊中知足條件的v-1條邊組成最小生成樹(shù)。因此可用最小堆存儲(chǔ)所有的邊，從最小堆上掏出知足條件的V-1條邊即可，其時(shí)刻復(fù)雜度接近最壞情形下也為°(山陪©)。另外，判斷新加入的邊是不是會(huì)形成回路，則可

10、轉(zhuǎn)化為判斷邊的兩個(gè)極點(diǎn)是不是在同一等價(jià)類中。五、上機(jī)實(shí)踐題1.在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的大體操作：InsertArc(Gvw),DeleteArc(Gv,w)o參考答案：packagechO6Exercise;import;import;publicclassExercise5_lpublicfinalstaticintINFINITY=;voidinsertArc(MGraphG,Objectv.Objectw,intP)intiv=(v);intiw=(w);intarcs=();arcsiviw=P：(arcs);()+1);)voiddeleteArc(MGraphGObjectv,

11、Objectw)intiv=(v);intiw=(w);arcs=();arcsiviw=INFINITY;(arcs);()-1)；publicstaticvoidmain(Stringargs)throwsExceptionObjectvexs=Mv0nv2Hv3M,Hv4Hv5,f);arcs=0.7,1,5,INFINITY.INFINITY),7,0,6,INFINITY,3JNFINITY),1,6,0,7,6,4,5,INFINITY.7,0,INFINITY.2,INFINITY,3,6,INFINITY,0,7,INFINITY.INFINITY.4,2,7,0);MGrap

12、hG=newMGraph,6.10.vexs.arcs);”修改前圖的邊數(shù)為：”+()；Exercise5_lexercise5_l=newExercise5_l();(Gnv0'HvlM);"刪除V0-V1邊后，圖的邊數(shù)為："+();(G7);"增加V0-V1邊后,圖的邊數(shù)為："+();)(1)求最短路徑的迪杰斯特拉算法。(2)設(shè)計(jì)一個(gè)測(cè)試主函數(shù)，使其實(shí)際運(yùn)行來(lái)求從某個(gè)源點(diǎn)到其余各個(gè)極點(diǎn)的最短路徑。參考答案：packagechO6Exercise;import;import;import;publicclassExercise5_2(privatebooleanP：ength);Pww=true;publicint|getD()returnD;)publicbooleangctP()returnP:publicstaticvoidmain(Stringargs)th