數(shù)據(jù)結(jié)構(gòu)-第7章習(xí)題答案

第7章《圖》習(xí)題參考答案一、單項(xiàng)選擇題〔每題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)的無向圖最多有條邊。A．14B.28C.56D.112〔C〕4.有8個(gè)結(jié)點(diǎn)的無向連通圖最少有條邊。A．5B.6C.7D.8〔C〕5.有8個(gè)結(jié)點(diǎn)的有向完全圖有條邊。A．14B.28C.56D.112〔B〕6.用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采用來實(shí)現(xiàn)算法的。A．棧B.隊(duì)列C.樹D.圖〔A〕7.用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常是采用來實(shí)現(xiàn)算法的。A．棧B.隊(duì)列C.樹D.圖A．0243156B.0136542C.01342A．0243156B.0136542C.01342560361542〔D〕9.圖的鄰接矩陣同上題8，根據(jù)算法，那么從頂點(diǎn)0出發(fā)，按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是A．0243156B.0135642C.0423165D.0123465〔D〕10.圖的鄰接表如下所示，根據(jù)算法，那么從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是A．0132B.A．0132B.0231C.0321D.0123〔A〕11.圖的鄰接表如下所示，根據(jù)算法，那么從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是A．0321B.A．0321B.0123C.0132D.0312〔A〕12.深度優(yōu)先遍歷類似于二叉樹的A．先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷〔D〕13.廣度優(yōu)先遍歷類似于二叉樹的A．先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷〔A〕14.任何一個(gè)無向連通圖的最小生成樹A．只有一棵B.一棵或多棵C.一定有多棵D.可能不存在〔注，生成樹不唯一，但最小生成樹唯一，即邊權(quán)之和或樹權(quán)最小的情況唯一〕二、填空題〔每空1分，共20分〕1.圖有鄰接矩陣、鄰接表等存儲(chǔ)結(jié)構(gòu)，遍歷圖有深度優(yōu)先遍歷、廣度優(yōu)先遍歷等方法。2.有向圖G用鄰接表矩陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的出度。3.如果n個(gè)頂點(diǎn)的圖是一個(gè)環(huán)，那么它有n棵生成樹。〔以任意一頂點(diǎn)為起點(diǎn)，得到n-1條邊〕4.n個(gè)頂點(diǎn)e條邊的圖，假設(shè)采用鄰接矩陣存儲(chǔ)，那么空間復(fù)雜度為O(n2)。5.n個(gè)頂點(diǎn)e條邊的圖，假設(shè)采用鄰接表存儲(chǔ)，那么空間復(fù)雜度為O(n+e)。6.設(shè)有一稀疏圖G，那么G采用鄰接表存儲(chǔ)較省空間。7.設(shè)有一稠密圖G，那么G采用鄰接矩陣存儲(chǔ)較省空間。8.圖的逆鄰接表存儲(chǔ)結(jié)構(gòu)只適用于有向圖。9.一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)頂點(diǎn)出發(fā)的方法是將鄰接矩陣的第i行全部置0。10.圖的深度優(yōu)先遍歷序列不是惟一的。11.n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為O(n2)；假設(shè)采用鄰接表存儲(chǔ)時(shí)，該算法的時(shí)間復(fù)雜度為O(n+e)。12.n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，廣度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為O(n2)；假設(shè)采用鄰接表存儲(chǔ)，該算法的時(shí)間復(fù)雜度為O(n+e)。13.圖的BFS生成樹的樹高比DFS生成樹的樹高小或相等。14.用普里姆(Prim)算法求具有n個(gè)頂點(diǎn)e條邊的圖的最小生成樹的時(shí)間復(fù)雜度為O(n2)；用克魯斯卡爾(Kruskal)算法的時(shí)間復(fù)雜度是O(elog2e)。15.假設(shè)要求一個(gè)稀疏圖G的最小生成樹，最好用克魯斯卡爾(Kruskal)算法來求解。16.假設(shè)要求一個(gè)稠密圖G的最小生成樹，最好用普里姆(Prim)算法來求解。17.用Dijkstra算法求某一頂點(diǎn)到其余各頂點(diǎn)間的最短路徑是按路徑長(zhǎng)度遞增的次序來得到最短路徑的。18.拓?fù)渑判蛩惴ㄊ峭ㄟ^重復(fù)選擇具有0個(gè)前驅(qū)頂點(diǎn)的過程來完成的。三、簡(jiǎn)答題〔每題6分，共24分〕1.【嚴(yán)題集7.1①】如下圖的有向圖，請(qǐng)給出該圖的:頂點(diǎn)12頂點(diǎn)123456入度出度鄰接矩陣；鄰接表；逆鄰接表。答案：

2.【嚴(yán)題集7.7②】請(qǐng)對(duì)以下圖的無向帶權(quán)圖：寫出它的鄰接矩陣，并按普里姆算法求其最小生成樹；寫出它的鄰接表，并按克魯斯卡爾算法求其最小生成樹。解：設(shè)起點(diǎn)為a?？梢灾苯佑稍紙D畫出最小生成樹，而且最小生成樹只有一種〔類〕!鄰接矩陣為：最小生成樹最小生成樹→PRIM算法〔橫向變化〕：VbcdefghUV-UVexlowcosta4a3a∞a∞a∞a∞a∞{a}{b,c,d,e,f,g,h}Vexlowcosta40c5a∞a∞a∞c5{a,c}{b,d,e,f,g,h}Vexlowcost00c5b9a∞a∞c5{a,c,b}{d,e,f,g,h}Vexlowcost000d7d6d5d4{a,c,b,d}{e,f,g,h}Vexlowcost000d7d6d50{a,c,b,d,h}{e,f,g}Vexlowcost000d7g200{a,c,b,d,h,g}{f,e}Vexlowcost000f3000{a,c,b,d,h,g,f}{e}Vexlowcost0000000{a,c,b,d,h,g,f,e}{}鄰接表為：a→b4→c3b→a4→c5→d5→e9^c→a3→b5→d5→h5^d→b5→c5→e7→f6→g5→h4^e→b9→d7→f3^f→d6→e3→g2^g→d5→f2→h6^h→c5→d4→g6^克魯斯卡爾算法步驟克魯斯卡爾算法步驟(按邊歸并,堆排序)：先羅列：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è)連通分量連接起來了。3.【嚴(yán)題集7.5②】二維數(shù)組表示的圖的鄰接矩陣如以下圖所示。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。4.【嚴(yán)題集7.11②】試?yán)肈ijkstra算法求圖中從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，寫出執(zhí)行算法過程中各步的狀態(tài)。解：最短路徑為：〔a,c,f,e,d,g,b〕

四、【2001年計(jì)考研題】給定以下網(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ù)類型。AB———————CAB———————CE————FG————D2.可用鄰接矩陣和鄰接表來描述：描述存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)類型可參見教材或電子教案：注：描述存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)類型可參見教材或電子教案：注：用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//假設(shè)的最大頂點(diǎn)數(shù)〔可取為7〕Typedefenum{DG,DN,AG,AN}GraphKind;//有向/無向圖，有向/無向網(wǎng)TypedefstructArcCell{//弧〔邊〕結(jié)點(diǎn)的定義VRTypeadj;//頂點(diǎn)間關(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];//頂點(diǎn)表，用一維向量即可AdjMatrixarcs;//鄰接矩陣IntVernum,arcnum;//頂點(diǎn)總數(shù)〔7〕，弧〔邊〕總數(shù)〔9〕GraphKindkind;//圖的種類標(biāo)志}Mgraph;鄰接表為：a→b12→e4^b→a12→c20→e8→f9^c→b20→d15→g12^d→c15→g10^e→a4→b8→f6^f→b9→e6^g→c12→d10五、算法設(shè)計(jì)題〔每題10分，共30分〕1.【嚴(yán)題集7.14③】編寫算法，由依次輸入的頂點(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;scanf("%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為弧尾,h為弧頭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_AdjList2.【嚴(yán)題集7.15③】試在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的根本操作：DeleteArc(G,v,w)，即刪除一條邊的操作。〔如果要?jiǎng)h除所有從第i個(gè)頂點(diǎn)出發(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_Arc3.【嚴(yán)題集7.22③】試基于圖的深度優(yōu)先搜索策略寫一算法，判別以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)vi到頂點(diǎn)vj的路徑〔i≠j〕。注意：算法中涉及的圖的根本操作必須在此存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)。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就是jelse{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：〔以上算法似乎有問題：如果不存在路徑，那么原程序不能返回0。我的解決方式是在原程序的中引入一變量level來控制遞歸進(jìn)行的層數(shù)。具體的方法我在程序中用紅色標(biāo)記出來了。〕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--)