第7章自測題與答案

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

n個頂點e條邊的圖采用鄰接矩陣存儲，深度優(yōu)先遍歷算法的時間復雜度為O(n 2)；若采用鄰接表存儲時，該算法的時間復雜度為O(n+e)。 —n個頂點e條邊的圖采用鄰接矩陣存儲，廣度優(yōu)先遍歷算法的時間復雜度為O(n 2)；若采用鄰接表存儲，該算法的時間復雜度為O(n+e)。圖的BFS生成樹的樹高比DFS生成樹的樹高小或相等」^—用普里姆(Prim)算法求具有n個頂點e條邊的圖的最小生成樹的時間復雜度為O(n2)；用克魯斯卡爾(Kruskal)算法的時間復雜度是O(eloge)。2 ——若要求一個稀疏圖G的最小生成樹，最好用克魯斯卡爾(Kruskal)算法來求解。若要求一個稠密圖G的最小生成樹，最好用普里姆(Prim)算法來求解。用Dijkstra算法求某一頂點到其余各頂點間的最短路徑是按路徑長度遞增的次序來得到最短路徑的。拓撲排序算法是通過重復選擇具有0個前驅(qū)頂點的過程來完成的。三、簡答題(每題6分，共24分)已知如圖所示的有向圖，請給出該圖的：出度(4)逆鄰接表。答案：(1)每個頂點的入/出度；頂點123456(2)鄰接矩陣;入度(3出度(4)逆鄰接表。答案：請對下圖的無向帶權(quán)圖：（1） 寫出它的鄰接矩陣，并按普里姆算法求其最小生成樹；（2） 寫出它的鄰接表，并按克魯斯卡爾算法求其最小生成樹。解：設起點為a?？梢灾苯佑稍紙D畫出最小生成樹，而且最小生成樹只有一種（類）！鄰接矩陣為：-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就把三個連通分量連接起來了。已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分別畫出自頂點1出發(fā)進行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。1Z341Z34S67891010000001010Z001000]00030001000100400001000105000001000161100000000700100000018100100001090000101001101000010000深度優(yōu)先生成棚廣度優(yōu)先生成樹試利用Dijkstra算法求圖中從頂點a到其他各頂點間的最短路徑，寫出執(zhí)行算法過程中各步的狀態(tài)。解：最短路徑為：（a，c，f，e，d，g，b）四、給定下列網(wǎng)G:（10分）1試著找出網(wǎng)G的最小生成樹，畫出其邏輯結(jié)構(gòu)圖;2用兩種不同的表示法畫出網(wǎng)G的存儲結(jié)構(gòu)圖；3用C語言（或其他算法語言）定義其中一種表示法（存儲結(jié)構(gòu)）的數(shù)據(jù)類型。解：1.最小生成樹可直接畫出，如右圖所示。22.1試著找出網(wǎng)G的最小生成樹，畫出其邏輯結(jié)構(gòu)圖;2用兩種不同的表示法畫出網(wǎng)G的存儲結(jié)構(gòu)圖；3用C語言（或其他算法語言）定義其中一種表示法（存儲結(jié)構(gòu)）的數(shù)據(jù)類型。解：1.最小生成樹可直接畫出，如右圖所示。22.可用鄰接矩陣和鄰接表來描述:1212□c20201512'486描述存儲結(jié)構(gòu)的數(shù)據(jù)類型可參見教材或電子教案：頂點表和鄰接矩陣1510#defineINFINITYINT_MAX//最大值8.#defineMAX_VERTEX_NUM20//假設的最大頂點數(shù)（可取為7）Typed?fendm{DG,DN^AG,AN}GraphKind;//有向/無向圖，有向/無向網(wǎng)96注：用兩個數(shù)組分別存儲:8 8 00 8TypedefstructArcCell{//弧（邊）結(jié)點的定義VRTypeadj;//頂點間關(guān)系，無權(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];//頂點表，用一維向量即可AdjMatrixarcs;//鄰接矩陣IntVernum,arcnum;//79頂點總數(shù)（），?。ㄟ叄┛倲?shù)（）GraphKindkind;//圖的種類標志鄰接表為：}Mgraph;五、算法設計題（每題10分，共30分）編寫算法，由依次輸入的頂點數(shù)目、弧的數(shù)目、各頂點的信息和各條弧的信息建立有向圖的鄰接表。解：StatusBuild_AdjList（ALGraph&G）//輸入有向圖的頂點數(shù)，邊數(shù)，頂點信息和邊的信息建立鄰接表{InitALGraph（G）;scanf（〃％d〃，&v）;if（v<0）returnERROR;//頂點數(shù)不能為負G.vexnum二v;6scanf(〃%d〃,&a);if(a<0)returnERROR;//邊數(shù)不能為負G.arcnum=a;for(m=0;m<v;m++)G.vertices[m].data二getchar();//輸入各頂點的符號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;//頂點未找到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試在鄰接矩陣存儲結(jié)構(gòu)上實現(xiàn)圖的基本操作：DeleteArc(G,v,w)，即刪除一條邊的操作。(如果要刪除所有從第i個頂點出發(fā)的邊呢？提示：將鄰接矩陣的第i行全部置0)解：//本題中的圖G均為有向無權(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)先搜索策略寫一算法，判別以鄰接表方式存儲的有向圖中是否存在由頂點v.到頂點v.的路徑(iUj)。注意：算法中涉及的圖的基本操作必須在此存儲結(jié)構(gòu)上實現(xiàn)。 1 'intvisited[MAXSIZE];//指示頂點是否在當前路徑上intexist_path_DFS(ALGraphG,inti,intj)//深度優(yōu)先判斷有向圖G中頂點i到頂點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下游的頂點到j有路徑}//for}//else}//exist_path_DFS解2：(以上算法似乎有問題：如果不存在路徑，則原程序不能返回0。我的解決方式是在原程序的中引入一變量level來控制遞歸進行的層數(shù)。具體的方法我在程序中用紅色標記出來了。)intvisited[MAXSIZE];//指示頂點是否在當前路徑上intlevel=1;//遞歸進行的層數(shù)intexist_path_DFS(ALGraphG,inti,intj)//深度優(yōu)先判斷有向圖G中頂點i到頂點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