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

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