數(shù)據(jù)結(jié)構(gòu)作業(yè)題(完整版)
【正文】 i = 3 2 6 10 [ 121616*30281820 ] 6 i = 4 2 6 10 12[ 1616*18302820 ] 5 i = 5 2 6 10 1216[ 16*18203028 ] 4 i = 6 2 6 10 121616*[ 18202830 ] 3 2 6 10 121616*18202830 (4) 快速排序PivotPvtpos 0 1 2 3 4 5 6 7 8 9 排序碼比較次數(shù)pospospospos 120,1,2,3[ 12 2 1630281016*20 618 ] 9pospos 60,1[ 6 2 10 ]12 [ 281616*203018 ] 2pospospospospos 284,5,6,7,8[ 2 ] 6 [ 10 ] 12[ 281616*203018 ] 5pospospos 18 4,5,6 2 6 10 12[ 181616*20 ]28[ 30 ] 3pos 16*4 2 6 10 12[ 16*16 ]18[ 20 ] 2830 1 2 6 10 1216*[ 16 ]18202830 左子序列遞歸深度為1，右子序列遞歸深度為3。235。, …,1。235。采用線性探查法尋找下一個空位, 畫出相應(yīng)的散列表, 并計算等概率下搜索成功的平均搜索長度和搜索不成功的平均搜索長度。(A,B,D,E)(A,B,D,E)165。 5 186。 (4) 確定哪些活動是關(guān)鍵活動。例如： 76對于有n個頂點的無向圖，采用鄰接矩陣表示，如何判斷以下問題： 圖中有多少條邊？任意兩個頂點i和j之間是否有邊相連？任意一個頂點的度是多少？用鄰接矩陣表示無向圖時，因為是對稱矩陣，對矩陣的上三角部分或下三角部分檢測一遍，統(tǒng)計其中的非零元素個數(shù)，就是圖中的邊數(shù)。 編寫按層次遍歷二叉樹的算法。610 假定用于通信的電文僅由8個字母c1, c2, c3, c4, c5, c6, c7, c8組成, , , , , , , 。（3）分別求出該二叉樹的先序、中序、后序遍歷序列。若在一維數(shù)組B中從0號位置開始存放，則下三角矩陣中的任一元素aij在應(yīng)存于一維數(shù)組的什么下標(biāo)位置？給出計算公式。52假二維數(shù)組A9180。amp。 //雙棧的棧頂指針和棧底指針dsType V[m]。(2) 求最大值函數(shù)max：通過一趟遍歷在單鏈表中確定值最大的結(jié)點?！ lse i++?！ hile(in) { k=k+10*i?！ while(in)?！ (4)x=n。第三章 [m]中，棧底分別處于數(shù)組的兩端。//棧數(shù)組} DoubleStack；初始化空雙棧算法：InitdStack(DoubleStack amp。 [1]==m) return 1。3180。（2）設(shè)有一個n180。65 試分別找出滿足以下條件的所有二叉樹:(1) 二叉樹的前序序列與中序序列相同。試為這8個字母設(shè)計不等長Huffman編碼, 并給出該電文的總碼數(shù)。第7章 圖71在n個頂點的無向完全圖中，邊的條數(shù)為（n(n1)/2 ）。如果鄰接矩陣中A[i][j] 不為零，說明頂點i與頂點j之間有邊相連。畫出由所有關(guān)鍵活動構(gòu)成的圖，指出哪些活動加速可使整個工程提前完成。 6 187。165。 (2) 采用雙散列法尋找下一個空位, 再散列函數(shù)為 RH (key) = (7*key) % 10 + 1, 尋找下一個空位的公式為 Hi = (Hi1 + RH (key)) % 13, H1 = H (key)。n/2一般地，增量序列可采用235。nα(5) 直接選擇排序初始排列 0 1 2 3 4 5 6 7 8 9 排序碼比較次數(shù) i = 0[ 12 2 16 30 28 10 16* 20 618 ] 9 i = 1 2[ 12 16 30 28 10 16* 20 618 ] 8 i = 2 2 6 [ 16 30 28 10 16* 20 1218 ] 7 i = 3 2 6 10 [ 30 28 16 16* 20 1218 ] 6 i = 4 2 6 10 12[ 28 16 16* 20 3018 ] 5 i = 5 2 6 10 12 16[ 28 16* 20 3018 ] 4 i = 6 2 6 10 12 16 16*[ 28 20 3018 ] 3 i = 7 2 6 10 12 16 16* 18
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1