正文內容

數據結構作業題(編輯修改稿)

2026-04-21 03:01 本頁面

　

【文章內容簡介】 76對于有n個頂點的無向圖，采用鄰接矩陣表示，如何判斷以下問題：圖中有多少條邊？任意兩個頂點i和j之間是否有邊相連？任意一個頂點的度是多少？用鄰接矩陣表示無向圖時，因為是對稱矩陣，對矩陣的上三角部分或下三角部分檢測一遍，統計其中的非零元素個數，就是圖中的邊數。如果鄰接矩陣中A[i][j] 不為零，說明頂點i與頂點j之間有邊相連。此外統計矩陣第i行或第i列的非零元素個數，就可得到頂點i的度數。④①②③⑤77對于如右圖所示的有向圖，試寫出： (1) 從頂點①出發進行深度優先搜索所得到的深度優先生成樹； (2) 從頂點②出發進行廣度優先搜索所得到的廣度優先生成樹； 1) 從頂點①出發進行深度優先遍歷不唯一，得到的深度優先生成樹； ①①例如: 12345 或13425等……③②②⑤③ ⑤④④①(2) 從頂點②出發進行廣度優先遍歷，12345，所得到的廣度優先生成樹③②⑤④78利用普里姆（prim和克魯斯卡爾(Kruskal)算法，求下圖的最小生成樹。16②①5192114269⑥③611⑤18④⑤①⑤14②16①⑤14②16③5①⑤14②16①⑤14②16①⑤14prim算法④③56③5①⑥11 ④65①②④③⑥⑤6111416克魯斯卡爾(Kruskal)①②④③⑥⑤5①②④③⑥⑤6115①②④③⑥⑤65①②④③⑥⑤5①②④③⑥⑤61114 79 試對右圖所示的AOE網絡，解答下列問題。 (1) 這個工程最早可能在什么時間結束。(2) 求每個事件的最早開始時間Ve[i]和最遲開始時間Vl[i]。(3) 求每個活動的最早開始時間e(i)和最遲開始時間l(i)。 (4) 確定哪些活動是關鍵活動。畫出由所有關鍵活動構成的圖，指出哪些活動加速可使整個工程提前完成。按拓撲有序的順序計算各個頂點的最早可能開始時間Ve和最遲允許開始時間Vl。然后再計算各個活動的最早可能開始時間e和最遲允許開始時間l，根據l e = 0? 來確定關鍵活動，從而確定關鍵路徑。 1 182。 2 184。 3 4 185。 5 186。 6 187。 Ve 0 19 15 29 38 43 Vl 0 19 15 37 38 431, 21, 33, 22, 42, 53, 54, 65, 6 e 0 0 15 19 19 15 29 38 l 17 0 15 27 19 27 37 38le 17 0 0 8 0 12 8 0 此工程最早完成時間為43。關鍵路徑為1, 33, 22, 55, 6710以右圖為例，按Dijkstra算法計算得到的從頂點①(A)到其它各個頂點的最短路徑和最短路徑長度。2185522ABCDE2102源點終點最短路徑最短路徑長度 A B(A,B)(A,B)(A,B)(A,B)10101010 C(A,C)(A,C)(A,C)(A,C)18181818 D 190。(A,B,D)(A,B,D)(A,B,D)165。151515 E 190。190。(A,B,D,E)(A,B,D,E)165。165。1717第八章查找表習題81 設有序順序表中的元素依次為017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。試畫出對其進行折半查找時的二叉判定樹, 并計算查找成功的平均查找長度和查找不成功的平均搜索長度。82 設有一個輸入數據的序列是 { 46, 25, 78, 62, 12, 37, 70, 29 }, 試畫出從空樹起，逐個輸入各個數據而生成的二叉排序樹。83將關鍵碼DEC, FEB, NOV, OCT, JUL, SEP, AUG, APR, MAR, MAY, JUN, JAN 依次插入到一棵初始為空的AVL樹（平衡二叉樹）中，畫出每插入一個關鍵碼后的AVL樹，并標明平衡旋轉的類型。84設散列表為HT[13], 散列函數為 H (key) = key %13。用閉散列法解決沖突, 對下列關鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。采用線性探查法尋找下一個空位, 畫出相應的散列表, 并計算等概率下搜索成功的平均搜索長度和搜索不成功的平均搜索長度。 (2) 采用雙散列法尋找下一個空位, 再散列函數為 RH (key) = (7*key) % 10 + 1, 尋找下一個空位的公式為 Hi = (Hi1 + RH (key)) % 13, H1 = H (key)。畫出相應的散列表, 并計算等概率下搜索成功的平均搜索長度。第九章作業設待排序的排序碼序列為{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 試分別寫出使用以下排序方法每趟排序后的結果。并說明做了多少次排序碼比較。 (1) 直接插入排序 (2) 希爾排序(增量為5,2,1) (3) 起泡排序 (4) 快速排序 (5) 直接選擇排序 (6) 基數排序 (7) 堆排序 (8) 二路歸并排序【解答】(1) 直接插入排序初始排列 0 1 2 3 4 5 6 7 8 9 排序碼比較次數 i = 1[ 12 ] 21630281016*20 618 1 i = 2[ 212 ]16302

點擊復制文檔內容

范文總結相關推薦

數據結構作業題(編輯修改稿)

數據結構作業-線性表-資料下載頁

數據結構作業電子版-資料下載頁

數據結構應用題總結-資料下載頁

數據結構實驗題及講解-資料下載頁

數據結構課后題及答案-資料下載頁

數據結構選擇題集錦-資料下載頁

數據庫平時作業題(參考)-資料下載頁

結構力學專升本網上作業題-資料下載頁

gis數據結構作業ppt課件-資料下載頁

數據結構與算法在線作業答案-資料下載頁

數據結構與算法離線作業答案-資料下載頁

面試-常考的數據結構題-資料下載頁

數據結構考研真題與答案-資料下載頁

數據結構單元題(帶答案)-資料下載頁

數據結構考研真題和答案-資料下載頁

數據結構作業題(已修改)

數據結構作業題(編輯修改稿)

數據結構作業題-wenkub.com

數據結構作業題(已改無錯字)

數據結構作業題-資料下載頁