數(shù)據(jù)結(jié)構(gòu)作業(yè)題(編輯修改稿)
2025-04-21 03:01 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 76對(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ù)。如果鄰接矩陣中A[i][j] 不為零，說(shuō)明頂點(diǎn)i與頂點(diǎn)j之間有邊相連。此外統(tǒng)計(jì)矩陣第i行或第i列的非零元素個(gè)數(shù)，就可得到頂點(diǎn)i的度數(shù)。④①②③⑤77對(duì)于如右圖所示的有向圖，試寫(xiě)出： (1) 從頂點(diǎn)①出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹(shù)； (2) 從頂點(diǎn)②出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹(shù)； 1) 從頂點(diǎn)①出發(fā)進(jìn)行深度優(yōu)先遍歷不唯一，得到的深度優(yōu)先生成樹(shù)； ①①例如: 12345 或13425等……③②②⑤③ ⑤④④①(2) 從頂點(diǎn)②出發(fā)進(jìn)行廣度優(yōu)先遍歷，12345，所得到的廣度優(yōu)先生成樹(shù)③②⑤④78利用普里姆（prim和克魯斯卡爾(Kruskal)算法，求下圖的最小生成樹(shù)。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 試對(duì)右圖所示的AOE網(wǎng)絡(luò)，解答下列問(wèn)題。 (1) 這個(gè)工程最早可能在什么時(shí)間結(jié)束。(2) 求每個(gè)事件的最早開(kāi)始時(shí)間Ve[i]和最遲開(kāi)始時(shí)間Vl[i]。(3) 求每個(gè)活動(dòng)的最早開(kāi)始時(shí)間e(i)和最遲開(kāi)始時(shí)間l(i)。 (4) 確定哪些活動(dòng)是關(guān)鍵活動(dòng)。畫(huà)出由所有關(guān)鍵活動(dòng)構(gòu)成的圖，指出哪些活動(dòng)加速可使整個(gè)工程提前完成。按拓?fù)溆行虻捻樞蛴?jì)算各個(gè)頂點(diǎn)的最早可能開(kāi)始時(shí)間Ve和最遲允許開(kāi)始時(shí)間Vl。然后再計(jì)算各個(gè)活動(dòng)的最早可能開(kāi)始時(shí)間e和最遲允許開(kāi)始時(shí)間l，根據(jù)l e = 0? 來(lái)確定關(guān)鍵活動(dòng)，從而確定關(guān)鍵路徑。 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 此工程最早完成時(shí)間為43。關(guān)鍵路徑為1, 33, 22, 55, 6710以右圖為例，按Dijkstra算法計(jì)算得到的從頂點(diǎn)①(A)到其它各個(gè)頂點(diǎn)的最短路徑和最短路徑長(zhǎng)度。2185522ABCDE2102源點(diǎn)終點(diǎn)最短路徑最短路徑長(zhǎng)度 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第八章 查找表習(xí)題81 設(shè)有序順序表中的元素依次為017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。試畫(huà)出對(duì)其進(jìn)行折半查找時(shí)的二叉判定樹(shù), 并計(jì)算查找成功的平均查找長(zhǎng)度和查找不成功的平均搜索長(zhǎng)度。82 設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 { 46, 25, 78, 62, 12, 37, 70, 29 }, 試畫(huà)出從空樹(shù)起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉排序樹(shù)。83將關(guān)鍵碼DEC, FEB, NOV, OCT, JUL, SEP, AUG, APR, MAR, MAY, JUN, JAN 依次插入到一棵初始為空的AVL樹(shù)（平衡二叉樹(shù)）中，畫(huà)出每插入一個(gè)關(guān)鍵碼后的AVL樹(shù)，并標(biāo)明平衡旋轉(zhuǎn)的類型。84設(shè)散列表為HT[13], 散列函數(shù)為 H (key) = key %13。用閉散列法解決沖突, 對(duì)下列關(guān)鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。采用線性探查法尋找下一個(gè)空位, 畫(huà)出相應(yīng)的散列表, 并計(jì)算等概率下搜索成功的平均搜索長(zhǎng)度和搜索不成功的平均搜索長(zhǎng)度。 (2) 采用雙散列法尋找下一個(gè)空位, 再散列函數(shù)為 RH (key) = (7*key) % 10 + 1, 尋找下一個(gè)空位的公式為 Hi = (Hi1 + RH (key)) % 13, H1 = H (key)。畫(huà)出相應(yīng)的散列表, 并計(jì)算等概率下搜索成功的平均搜索長(zhǎng)度。第九章 作業(yè)設(shè)待排序的排序碼序列為{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 試分別寫(xiě)出使用以下排序方法每趟排序后的結(jié)果。并說(shuō)明做了多少次排序碼比較。 (1) 直接插入排序 (2) 希爾排序(增量為5,2,1) (3) 起泡排序 (4) 快速排序 (5) 直接選擇排序 (6) 基數(shù)排序 (7) 堆排序 (8) 二路歸并排序 【解答】(1) 直接插入排序 初始排列 0 1 2 3 4 5 6 7 8 9 排序碼比較次數(shù) i = 1[ 12 ] 21630281016*20 618 1 i = 2[ 212 ]16302
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1