第7章自測(cè)題與答案

第7章圖自測(cè)卷解答姓名班級(jí)題號(hào).二三四五總分題分16202410301)0得分-、單選題（每題1分，共16分）（C）1.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的倍。A.1/2B.1C.2D.4（B） 2.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的倍。A.1/2B.1C.2D.4（B） 3.有8個(gè)結(jié)點(diǎn)的無(wú)向圖最多有條邊。A.14B.28C.56D.112（C） 4.有8個(gè)結(jié)點(diǎn)的無(wú)向連通圖最少有條邊。A.5B.6C.7D.8（C） 5.有8個(gè)結(jié)點(diǎn)的有向完全圖有條邊。A.14B.28C.56D.112（B）6.用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采用來(lái)實(shí)現(xiàn)算法的。A.棧B.隊(duì)列C.樹D.圖（A）7.用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常是采用來(lái)實(shí)現(xiàn)算法的。A.棧B.隊(duì)列C.樹D.圖"011110110010011000100B.0136542C.042316511001101011010L00011011100010"011110110010011000100B.0136542C.042316511001101011010L00011011100010A.0243156D.0361542建議：0134256（D）9.已知圖的鄰接矩陣同上題8,根據(jù)算法，則從頂點(diǎn)0出發(fā)，按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是IIA.0243156B.0135642C.0423165D.0134256（B）10.已知圖的鄰接矩陣同上題8,根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是A.0243651B.0136425C.0423156D.0134256（建議:0123456）（C）11.已知圖的鄰接矩陣同上題8,根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是A.0243165B.0135642C.0123465D.0123456（D） 12.已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是A.0132B.0231C.0321D.0123（A）13.已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是A.0321B.0123C.0132D.0312（A）14.深度優(yōu)先遍歷類似于二叉樹的A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷（D） 15.廣度優(yōu)先遍歷類似于二叉樹的A?先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷（A）16.任何一個(gè)無(wú)向連通圖的最小生成樹A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在（注，生成樹不唯一，但最小生成樹唯一，即邊權(quán)之和或樹權(quán)最小的情況唯一）二、填空題（每空1分，共20分）圖有鄰接矩陣、鄰接表等存儲(chǔ)結(jié)構(gòu)，遍歷圖有深度優(yōu)先遍歷、廣度優(yōu)先遍歷等方法。 .有向圖G用鄰接表矩陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的出度?！绻鹡個(gè)頂點(diǎn)的圖是一個(gè)環(huán)，則它有n棵生成樹。（以任意一頂點(diǎn)為起點(diǎn)，得到n-1條邊）n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接矩陣存儲(chǔ)，則空間復(fù)雜度為O（n 2）。n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接表存儲(chǔ)，則空間復(fù)雜度為O（n+e）。設(shè)有一稀疏圖G，則G采用鄰接表存儲(chǔ)較省空間。設(shè)有一稠密圖G，則G采用鄰接矩.陣存儲(chǔ)較省空間。圖的逆鄰接表存儲(chǔ)結(jié)構(gòu)只適用于有向圖。已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)頂點(diǎn)出發(fā)的方法是將鄰接矩陣的第i行全部置0。圖的深度優(yōu)先遍歷序列不是惟一的。

n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為O(n 2)；若采用鄰接表存儲(chǔ)時(shí)，該算法的時(shí)間復(fù)雜度為O(n+e)。 —n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，廣度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為O(n 2)；若采用鄰接表存儲(chǔ)，該算法的時(shí)間復(fù)雜度為O(n+e)。圖的BFS生成樹的樹高比DFS生成樹的樹高小或相等」^—用普里姆(Prim)算法求具有n個(gè)頂點(diǎn)e條邊的圖的最小生成樹的時(shí)間復(fù)雜度為O(n2)；用克魯斯卡爾(Kruskal)算法的時(shí)間復(fù)雜度是O(eloge)。2 ——若要求一個(gè)稀疏圖G的最小生成樹，最好用克魯斯卡爾(Kruskal)算法來(lái)求解。若要求一個(gè)稠密圖G的最小生成樹，最好用普里姆(Prim)算法來(lái)求解。用Dijkstra算法求某一頂點(diǎn)到其余各頂點(diǎn)間的最短路徑是按路徑長(zhǎng)度遞增的次序來(lái)得到最短路徑的。拓?fù)渑判蛩惴ㄊ峭ㄟ^(guò)重復(fù)選擇具有0個(gè)前驅(qū)頂點(diǎn)的過(guò)程來(lái)完成的。三、簡(jiǎn)答題(每題6分，共24分)已知如圖所示的有向圖，請(qǐng)給出該圖的：出度(4)逆鄰接表。答案：(1)每個(gè)頂點(diǎn)的入/出度；頂點(diǎn)123456(2)鄰接矩陣;入度(3出度(4)逆鄰接表。答案：請(qǐng)對(duì)下圖的無(wú)向帶權(quán)圖：（1） 寫出它的鄰接矩陣，并按普里姆算法求其最小生成樹；（2） 寫出它的鄰接表，并按克魯斯卡爾算法求其最小生成樹。解：設(shè)起點(diǎn)為a。可以直接由原始圖畫出最小生成樹，而且最小生成樹只有一種（類）！鄰接矩陣為：-043□c乂oC■140 5 59X□cs1最小生成樹315 0 5乂oCoC5|—550765489703°□c81J1s言302s1bo1x喜2068Losoc2T5460.JVexOOOOOOO^a,costiY鄰接表為：lowa3^b5&灑”VexOOOOOOO^a,costiY鄰接表為：lowa3^b5&灑”d5^h5"d^lb5—C5Te7f6^g5h4JVbcdel'ghUV-UVexaaaaazlowcost4：aa{a}I{b,c,de,f,g,h}Vexa0caazac{a,c}{8b,dOO^e,f,88g,h}lowcost4f558O*Vex00cbajlowcost5Sac{a,)5c,bHde,f,gTR8}8Vex000dd(1cbccu+7,ld{a,)54c,b,d}{e,f,g,h}Vex000dd(1cbccc?+7.10{a,)5}c,b,d,i{e,i1g}Vex000dg(?1nwpnoT)0{a,>n}c,b,d,】,{f,e}_LOWcosU■ZVex000f0(lowcost3(^1^)0{a,gyf}c,b,d,】,{e}PRIM算法（橫向變化）：l,b,drhr{a—e—b9—d7—f3f—d6—e3—g2g—d5—h—c5—克魯斯卡爾算法步驟（按邊歸并，堆排序）:先羅列：f—2—ga—3一一cf—3—ea—4—bd—4—h（a，b,c）（e,f,g）（d，h）取b—5—d,g—5--d就把三個(gè)連通分量連接起來(lái)了。已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。1Z341Z34S67891010000001010Z001000]00030001000100400001000105000001000161100000000700100000018100100001090000101001101000010000深度優(yōu)先生成棚廣度優(yōu)先生成樹試?yán)肈ijkstra算法求圖中從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，寫出執(zhí)行算法過(guò)程中各步的狀態(tài)。解：最短路徑為：（a，c，f，e，d，g，b）四、給定下列網(wǎng)G:（10分）1試著找出網(wǎng)G的最小生成樹，畫出其邏輯結(jié)構(gòu)圖;2用兩種不同的表示法畫出網(wǎng)G的存儲(chǔ)結(jié)構(gòu)圖；3用C語(yǔ)言（或其他算法語(yǔ)言）定義其中一種表示法（存儲(chǔ)結(jié)構(gòu)）的數(shù)據(jù)類型。解：1.最小生成樹可直接畫出，如右圖所示。22.1試著找出網(wǎng)G的最小生成樹，畫出其邏輯結(jié)構(gòu)圖;2用兩種不同的表示法畫出網(wǎng)G的存儲(chǔ)結(jié)構(gòu)圖；3用C語(yǔ)言（或其他算法語(yǔ)言）定義其中一種表示法（存儲(chǔ)結(jié)構(gòu)）的數(shù)據(jù)類型。解：1.最小生成樹可直接畫出，如右圖所示。22.可用鄰接矩陣和鄰接表來(lái)描述:1212□c20201512'486描述存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)類型可參見教材或電子教案：頂點(diǎn)表和鄰接矩陣1510#defineINFINITYINT_MAX//最大值8.#defineMAX_VERTEX_NUM20//假設(shè)的最大頂點(diǎn)數(shù)（可取為7）Typed?fendm{DG,DN^AG,AN}GraphKind;//有向/無(wú)向圖，有向/無(wú)向網(wǎng)96注：用兩個(gè)數(shù)組分別存儲(chǔ):8 8 00 8TypedefstructArcCell{//弧（邊）結(jié)點(diǎn)的定義VRTypeadj;//頂點(diǎn)間關(guān)系，無(wú)權(quán)圖取1或0；有權(quán)圖取權(quán)值類型InfoType*info;//該弧相關(guān)信息的指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];Typedefstruct{//圖的定義VertexTypevexs[MAX_VERTEX_NUM];//頂點(diǎn)表，用一維向量即可AdjMatrixarcs;//鄰接矩陣IntVernum,arcnum;//79頂點(diǎn)總數(shù)（），弧（邊）總數(shù)（）GraphKindkind;//圖的種類標(biāo)志鄰接表為：}Mgraph;五、算法設(shè)計(jì)題（每題10分，共30分）編寫算法，由依次輸入的頂點(diǎn)數(shù)目、弧的數(shù)目、各頂點(diǎn)的信息和各條弧的信息建立有向圖的鄰接表。解：StatusBuild_AdjList（ALGraph&G）//輸入有向圖的頂點(diǎn)數(shù)，邊數(shù)，頂點(diǎn)信息和邊的信息建立鄰接表{InitALGraph（G）;scanf（〃％d〃，&v）;if（v<0）returnERROR;//頂點(diǎn)數(shù)不能為負(fù)G.vexnum二v;6scanf(〃%d〃,&a);if(a<0)returnERROR;//邊數(shù)不能為負(fù)G.arcnum=a;for(m=0;m<v;m++)G.vertices[m].data二getchar();//輸入各頂點(diǎn)的符號(hào)for(m=1;m<=a;m++){t=getchar();h=getchar();//t為弧尾山為弧頭if((i=LocateVex(G,t))<0)returnERROR;if((j二LocateVex(G,h))<0)returnERROR;//頂點(diǎn)未找到p=(ArcNode*)malloc(sizeof(ArcNode));if(!G.vertices.[i].firstarc)G.vertices[i].firstarc二p;else{for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc);q->nextarc=p;}p->adjvex=j;p->nextarc二NULL;}//whilereturnOK;}//Build_AdjList試在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：DeleteArc(G,v,w)，即刪除一條邊的操作。(如果要?jiǎng)h除所有從第i個(gè)頂點(diǎn)出發(fā)的邊呢？提示：將鄰接矩陣的第i行全部置0)解：//本題中的圖G均為有向無(wú)權(quán)圖。StatusDelete_Arc(MGraph&G,charv,charw)//在鄰接矩陣表示的圖G上刪除邊(v,w){if((i二LocateVex(G,v))<0)returnERROR;if((j二LocateVex(G,w))<0)returnERROR;if(G.arcs[i][j].adj){G.arcs[i][j].adj=0;G.arcnum--;}returnOK;}//Delete_Arc試基于圖的深度優(yōu)先搜索策略寫一算法，判別以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)v.到頂點(diǎn)v.的路徑(iUj)。注意：算法中涉及的圖的基本操作必須在此存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)。 1 'intvisited[MAXSIZE];//指示頂點(diǎn)是否在當(dāng)前路徑上intexist_path_DFS(ALGraphG,inti,intj)//深度優(yōu)先判斷有向圖G中頂點(diǎn)i到頂點(diǎn)j是否有路徑，是則返回1,否則返回0{if(i==j)return1;//i就是j7else{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;if(!visited[k]&&exist_path(k,j))return1;//i下游的頂點(diǎn)到j(luò)有路徑}//for}//else}//exist_path_DFS解2：(以上算法似乎有問(wèn)題：如果不存在路徑，則原程序不能返回0。我的解決方式是在原程序的中引入一變量level來(lái)控制遞歸進(jìn)行的層數(shù)。具體的方法我在程序中用紅色標(biāo)記出來(lái)了。)intvisited[MAXSIZE];//指示頂點(diǎn)是否在當(dāng)前路徑上intlevel=1;//遞歸進(jìn)行的層數(shù)intexist_path_DFS(ALGraphG,inti,intj)//深度優(yōu)先判斷有向圖G中頂點(diǎn)i到頂點(diǎn)j是否有路徑，是則返回1,否則返回0{if(i==j)return1;//i就是jelse{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p->nextarc，level--){level++;k=p->ad