數(shù)據(jù)結(jié)構(gòu)作業(yè)題(文件)
【正文】 已知一棵二叉樹的前序遍歷的結(jié)果是ABECDFGHIJ, 中序遍歷的結(jié)果是EBCDAFHIGJ, 試畫出這棵二叉樹。試為這8個字母設(shè)計不等長Huffman編碼, 并給出該電文的總碼數(shù)。若等長C1至C8編碼分別為000~111，平均長度為3。第7章 圖71在n個頂點的無向完全圖中，邊的條數(shù)為（n(n1)/2 ）。矩陣中非零元素的個數(shù)與邊的條數(shù)有關(guān)（無向圖非零元素的個數(shù)是邊數(shù)的2倍；有向圖非零元素的個數(shù)等于邊數(shù)）。如果鄰接矩陣中A[i][j] 不為零，說明頂點i與頂點j之間有邊相連。 (1) 這個工程最早可能在什么時間結(jié)束。畫出由所有關(guān)鍵活動構(gòu)成的圖，指出哪些活動加速可使整個工程提前完成。 2 184。 6 187。(A,B,D)(A,B,D)(A,B,D)165。165。83將關(guān)鍵碼DEC, FEB, NOV, OCT, JUL, SEP, AUG, APR, MAR, MAY, JUN, JAN 依次插入到一棵初始為空的AVL樹（平衡二叉樹）中，畫出每插入一個關(guān)鍵碼后的AVL樹，并標明平衡旋轉(zhuǎn)的類型。 (2) 采用雙散列法尋找下一個空位, 再散列函數(shù)為 RH (key) = (7*key) % 10 + 1, 尋找下一個空位的公式為 Hi = (Hi1 + RH (key)) % 13, H1 = H (key)。 (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 ]1630281016*20 618 1 i = 3[ 212 16 ]30281016*20 618 1 i = 4[ 212 16 30 ]281016*20 618 2 i = 5[ 212 16 2830 ]1016*20 618 5 i = 6[ 21012162830 ]16*20 618 3 i = 7[ 210121616*2830 ]20 618 3 i = 8[ 210121616*202830 ] 618 3 i = 9[ 2 610121616*202830 ]18 8[ 2 610121616*18202830 ](2) 希爾排序(增量為5,2,1)初始排列 0 1 2 3 4 5 6 7 8 9排序碼比較次數(shù) 12 21630281016*20 618 1+1+1+1+1 = 5 d = 5 10 216 6181216*203028 (1+1+2+1) + (1+1 d = 2+1+1) = 9 10 216 616*1218203028 1+1+3+1+3+1+1 d = 1+1+2 = 14 2 6 10 121616*18202830 希爾(shell)本人采取的增量序列為 235。n/2n/2一般地，增量序列可采用235。nα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[ 20 3028 ] 2 i = 8 2 6 10 12 16 16* 16 20[ 3028 ] 1
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1