第7章自測題與答案

經(jīng)典word整理文檔，僅參考，雙擊此處可刪除頁眉頁腳。本資料屬于網(wǎng)絡整理，如有侵權，請聯(lián)系刪除，謝謝！WORD格式可編輯第71（B）3.有8A．（C）4.有8A．（C）5.有8A．（B）A．棧B.隊列C.樹D.圖（A）A．棧B.隊列C.樹D.圖（C）0A．（D）0A．0243156B.0135642C.0423165D.0134256（B）10.已知圖的鄰接矩陣同上題0A（建議：0123456）專業(yè)知識整理分享WORD格式可編輯1專業(yè)知識整理分享WORD格式可編輯（D）0（A）0A．（A）14.深度優(yōu)先遍歷類似于二叉樹的AB.中序遍歷C.后序遍歷D.層次遍歷（D）15.廣度優(yōu)先遍歷類似于二叉樹的AB.中序遍歷C.后序遍歷D.層次遍歷（A）AB.一棵或多棵C.一定有多棵D.可能不存在11.2.Gii3.nn)。4.ne5.neO(n+e)。6.G7.G8.9.ii0。10.2專業(yè)知識整理分享WORD格式可編輯211.neO(n+e)。)；若采用鄰接12.neO(n+e)。13.2)；用克魯14.用普里姆(Prim)算法求具有ne斯卡爾(Kruskal)算法的時間復雜度是e)。215.G的最小生成樹，最好用克魯斯卡爾(Kruskal)算法來求解。16.G的最小生成樹，最好用普里姆(Prim)算法來求解。17.用18.061.已知如圖所示的有向圖，請給出該圖的:（123456（（3專業(yè)知識整理分享WORD格式可編輯19.（（a?？梢灾苯佑稍紙D畫出最小生成樹，而且最小生40559→35055a→b4→c3f→d6→e3→g2^專業(yè)知識整理分享WORD格式可編輯4專業(yè)知識整理分享WORD格式可編輯g→d5→f2→h6^h→c5→d4→g6^卡爾算法步驟(按邊歸并,堆排序)：—3--cf—3—ea—h取5—d,g—5--d20.121.a解：最短路徑為：（a,c,f,e,d,g,b）5專業(yè)知識整理分享WORD格式可編輯G:（3用C22.489//最大值∞#defineMAX_VERTEX_NUM20//假設的最大頂點數(shù)（可取為//有向/無向圖，有向/無向網(wǎng)TypedefstructArcCell{//?。ㄟ叄┙Y點的定義VRTypeadj;//頂點間關系，無權圖取1或InfoType*info;//該弧相關信息的指針Typedefstruct{//圖的定義VertexTypevexs[MAX_VERTEX_NUM];//頂點表，用一維向量即可AdjMatrixarcs;//鄰接矩陣IntVernum,arcnum;//79a→b12→e4^b→a12→c20→e8→f9^c→b20→d15→g12^d→c15→g10^e→a4→b8→f6^f→b9→e6^g→c12→d102.解：StatusBuild_AdjList(ALGraph&G)//輸入有向圖的頂點數(shù),邊數(shù),頂點信息和邊的信息建立鄰接表{if(v<0)returnERROR;//頂點數(shù)不能為負6專業(yè)知識整理分享WORD格式可編輯if(a<0)returnERROR;//邊數(shù)不能為負{{}23.試在鄰接矩陣存儲結構上實現(xiàn)圖的基本操作：DeleteArc(G,v,w)，即刪除一條邊的操作。（如果要刪除所ii0）GStatusDelete_Arc(MGraph&G,charv,charw)//在鄰接矩陣表示的圖G{{}vvi24.j≠intvisited[MAXSIZE];//指示頂點是否在當前路徑上intexist_path_DFS(ALGraphG,inti,intj)//深度優(yōu)先判斷有向圖Gij是否有路徑,是則返回1,否則返回0{j7專業(yè)知識整理分享WORD格式可編輯{{j解intvisited[MAXSIZE];//指示頂點是否在當前路徑上intlevel＝1;//intexist_path_DFS(ALGraphG,inti,intj)//深度優(yōu)先判斷有向圖Gij是否有路徑,是則返回1,否則返回0{j{，jk的注intexist_path_len(ALGraphG,inti,intj,intk)//判斷鄰接表方式存儲的