數(shù)據(jù)結(jié)構(gòu)答案 job8

8-1 畫出1個(gè)頂點(diǎn)、2個(gè)頂點(diǎn)、3個(gè)頂點(diǎn)、4個(gè)頂點(diǎn)和5個(gè)頂點(diǎn)的無(wú)向完全圖。試證明在n個(gè)頂點(diǎn)的無(wú)向完全圖中，邊的條數(shù)為n(n-1)/2。8-2 右邊的有向圖是強(qiáng)連通的嗎？請(qǐng)列出所有的簡(jiǎn)單路徑。8-3 給出右圖的鄰接矩陣、鄰接表和鄰接多重表表示。8-4 用鄰接矩陣表示圖時(shí)，若圖中有1000個(gè)頂點(diǎn)，1000條邊，則形成的鄰接矩陣有多少矩陣元素？有多少非零元素？是否稀疏矩陣？【解答】一個(gè)圖中有1000個(gè)頂點(diǎn)，其鄰接矩陣中的矩陣元素有10002 = 1000000個(gè)。它有1000個(gè)非零元素（對(duì)于有向圖）或2000個(gè)非零元素（對(duì)于無(wú)向圖），因此是稀疏矩陣。8-5 用鄰接矩陣表示圖時(shí)，矩陣元素的個(gè)數(shù)與頂點(diǎn)個(gè)數(shù)是否相關(guān)？與邊的條數(shù)是否相關(guān)？【解答】用鄰接矩陣表示圖，矩陣元素的個(gè)數(shù)是頂點(diǎn)個(gè)數(shù)的平方，與邊的條數(shù)無(wú)關(guān)。矩陣中非零元素的個(gè)數(shù)與邊的條數(shù)有關(guān)。8-6 有n個(gè)頂點(diǎn)的無(wú)向連通圖至少有多少條邊？有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖至少有多少條邊？試舉例說(shuō)明?！窘獯稹縩個(gè)頂點(diǎn)的無(wú)向連通圖至少有n-1條邊，n個(gè)頂點(diǎn)的有向強(qiáng)連通圖至少有n條邊。例如：8-7對(duì)于有n個(gè)頂點(diǎn)的無(wú)向圖，采用鄰接矩陣表示，如何判斷以下問(wèn)題： 圖中有多少條邊？任意兩個(gè)頂點(diǎn)i和j之間是否有邊相連？任意一個(gè)頂點(diǎn)的度是多少？【解答】用鄰接矩陣表示無(wú)向圖時(shí)，因?yàn)槭菍?duì)稱矩陣，對(duì)矩陣的上三角部分或下三角部分檢測(cè)一遍，統(tǒng)計(jì)其中的非零元素個(gè)數(shù)，就是圖中的邊數(shù)。如果鄰接矩陣中Aij 不為零，說(shuō)明頂點(diǎn)i與頂點(diǎn)j之間有邊相連。此外統(tǒng)計(jì)矩陣第i行或第i列的非零元素個(gè)數(shù)，就可得到頂點(diǎn)i的度數(shù)。8-8對(duì)于如右圖所示的有向圖，試寫出：(1) 從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2) 從頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹； 8-9 試擴(kuò)充深度優(yōu)先搜索算法，在遍歷圖的過(guò)程中建立生成森林的左子女-右兄弟鏈表。算法的首部為viod Graph:DFS ( const int v, int visited , TreeNode * t ) 其中，指針t指向生成森林上具有圖頂點(diǎn)v信息的根結(jié)點(diǎn)。（提示：在繼續(xù)按深度方向從根v的某一未訪問(wèn)過(guò)的鄰接頂點(diǎn)w向下遍歷之前，建立子女結(jié)點(diǎn)。但需要判斷是作為根的第一個(gè)子女還是作為其子女的右兄弟鏈入生成樹。）8-10 用鄰接表表示圖時(shí)，頂點(diǎn)個(gè)數(shù)設(shè)為n，邊的條數(shù)設(shè)為e，在鄰接表上執(zhí)行有關(guān)圖的遍歷操作時(shí)，時(shí)間代價(jià)是O(n*e)？還是O(n+e)？或者是O(max(n,e)？【解答】在鄰接表上執(zhí)行圖的遍歷操作時(shí)，需要對(duì)鄰接表中所有的邊鏈表中的結(jié)點(diǎn)訪問(wèn)一次，還需要對(duì)所有的頂點(diǎn)訪問(wèn)一次，所以時(shí)間代價(jià)是O(n+e)。8-15 右圖是一個(gè)連通圖，請(qǐng)畫出(1) 以頂點(diǎn)為根的深度優(yōu)先生成樹；(2) 如果有關(guān)節(jié)點(diǎn)，請(qǐng)找出所有的關(guān)節(jié)點(diǎn)。(3) 如果想把該連通圖變成重連通圖，至少在圖中加幾條邊？如何加？ 【解答】(1) 從頂點(diǎn)出發(fā)的深度優(yōu)先生成樹為 此答案不唯一(2) 8-16試證明在一個(gè)有n個(gè)頂點(diǎn)的完全圖中，生成樹的數(shù)目至少有2n-1-1。8-17 編寫一個(gè)完整的程序，首先定義堆和并查集的結(jié)構(gòu)類型和相關(guān)操作，再定義Kruskal求連通網(wǎng)絡(luò)的最小生成樹算法的實(shí)現(xiàn)。并以右圖為例，寫出求解過(guò)程中堆、并查集和最小生成樹的變化。8-18 利用Dijkstra算法的思想，設(shè)計(jì)一個(gè)求最小生成樹的算法。8-19以右圖為例，按Dijkstra算法計(jì)算得到的從頂點(diǎn)到其它各個(gè)頂點(diǎn)的最短路徑和最短路徑長(zhǎng)度。8-20 在以下假設(shè)下，重寫Dijkstra算法：(1) 用鄰接表表示帶權(quán)有向圖G，其中每個(gè)邊結(jié)點(diǎn)有3個(gè)域：鄰接頂點(diǎn)vertex，邊上的權(quán)值length和邊鏈表的鏈接指針link。(2)用集合T = V(G) - S代替S(已找到最短路徑的頂點(diǎn)集合)，利用鏈表來(lái)表示集合T。試比較新算法與原來(lái)的算法，計(jì)算時(shí)間是快了還是慢了，給出定量的比較。8-22使用Floyd算法計(jì)算8-19題所用的帶權(quán)有向圖的各對(duì)頂點(diǎn)之間的最短路徑。8-23 下面是基于元素0到4的一些優(yōu)先關(guān)系的集合，試問(wèn)它們是否定義了一個(gè)偏序關(guān)系？為什么？01;13;12;23;24;40 8-24 試證明：對(duì)于一個(gè)無(wú)向圖G = (V, E)，若G中各頂點(diǎn)的度均大于或等于2，則G中必有回路?！窘獯稹糠醋C法：對(duì)于一個(gè)無(wú)向圖G=（V，E），若G中各頂點(diǎn)的度均大于或等于2，則G中沒有回路。此時(shí)從某一個(gè)頂點(diǎn)出發(fā)，應(yīng)能按拓?fù)溆行虻捻樞虮闅v圖中所有頂點(diǎn)。但當(dāng)遍歷到該頂點(diǎn)的另一鄰接頂點(diǎn)時(shí)，又可能回到該頂點(diǎn)，沒有回路的假設(shè)不成立。8-25 設(shè)有一個(gè)有向圖存儲(chǔ)在鄰接表中。試設(shè)計(jì)一個(gè)算法，按深度優(yōu)先搜索策略對(duì)其進(jìn)行拓?fù)渑判?。并以右圖為例檢驗(yàn)?zāi)愕乃惴ǖ恼_性?！窘獯稹?1) 定義鄰接表結(jié)構(gòu)const n = ;頂點(diǎn)個(gè)數(shù)type pointer = node node = record adj : integer;鄰接頂點(diǎn)號(hào) cost : real;邊上的權(quán)值 link : pointer; end; vex = record ind : integer;頂點(diǎn)入度 fout : pointer;出邊表頭指針 end; nodelist = array1.n of vex;鄰接表 另設(shè)一個(gè)輔助數(shù)組，記錄訪問(wèn)順序：visited : array1.n of integer。 初始時(shí)，各結(jié)點(diǎn)的visitedi均為0。 還有一個(gè)訪問(wèn)計(jì)數(shù)count，初始時(shí)為0。(2) 拓?fù)渑判蛩惴╬rocedure dfs ( G : nodelist; v : integer );var w : integer; p : pointer; begin count := count + 1;visitedv := count; p := Gv.fout; while p nil do begin w := p.adj; Gw.ind := Gw.ind - 1; if ( visitedw = 0 ) and ( Gw.ind = 0 ) then dfs ( G, w ); p := p.link; end; end;主程序for i := 1 to n do visitedi := 0;count := 0;read ( i, j, w);while ( i 0 ) and ( j 0 ) do begin new(p); p.adj := j; p.cost := w; Gj.ind := Gj.ind + 1; p.link := Gi.fout; Gi.fout := p; read ( i, j, w); end;for i := 1 to n do if ( visitedi = 0 ) and ( Gi.ind = 0 ) then dfs ( G, i );if count n then write (排序失敗);8-26 試對(duì)右圖所示的AOE網(wǎng)絡(luò)(1) 這個(gè)工程最早可能在什么時(shí)間結(jié)束。(2) 求每個(gè)活動(dòng)的最早開始時(shí)間e( )和最遲開始時(shí)間l( )。(3) 確定哪些活動(dòng)是關(guān)鍵活動(dòng)。 【解答】按拓?fù)溆行虻捻樞蛴?jì)算各個(gè)頂點(diǎn)的最早可能開始時(shí)間Ve和最遲允許開始時(shí)間Vl。然后再計(jì)算各個(gè)活動(dòng)的最早可能開始時(shí)間e和最遲允許開始時(shí)間l，根據(jù)l - e = 0? 來(lái)確定關(guān)鍵活動(dòng)，從而確定關(guān)鍵路徑。 1 2 3 4 5 6 Ve 0 19 15 29 38 43 Vl 0 19 15 37 38 43 e 0 0 15 19 19 15 29 38 l 17 0 15 27 19 27 37 38l-e 17 0 0 8 0 12 8 0此工程最早完成時(shí)間為43。關(guān)鍵路徑為8-27 若AOE網(wǎng)絡(luò)的每一項(xiàng)活動(dòng)都是關(guān)鍵活動(dòng)。令G是將該網(wǎng)絡(luò)的邊去掉方向和權(quán)后得到的無(wú)向圖。 (1) 如果圖中有一條邊處于從開始頂點(diǎn)到完成頂點(diǎn)的每一條路徑上，則僅加速該邊表示的活動(dòng)就