資訊處理 94 年資料結構考古題

假設三維陣列 Ｘ[3:10, 4:15, 5:20] 的第一個元素在記憶體的位址是200。假設每個元 素佔4 個位元組（bytes），那麼當採用以行為主（column-major）時， X[5, 7, 10] 之 位址為何？（20 分）

寫出累堆排序法（Heap Sort）的演算法。（10 分） 針對輸入數列（53、26、41、18、35、10、55、45、9、21），寫出排序過程。（10 分）

有一遞迴函數如下： int f(int n) { if (n < 3) return n; else return f(n-3) + f(n-2) + f(n-1); } 以f(9) 叫用之，將傳回值多少？（5 分） 令函數g(n) 為計算f(n) 時需呼叫f(0) 的次數，試寫出g(n) 的遞迴關係 （recurrence relation）。（10 分） 函數g(9) 的值為何？（5 分）

假設編碼系統中有A、B、C、D、E、F 等符號，其出現機率依序為 0.43, 0.13, 0.12, 0.18, 0.08, 0.06， 請依據此畫出霍夫曼樹（Huffman tree）並設計一套霍夫曼碼（Huffman code），並依 此所設計的霍夫曼碼將011000001000111010011 進行解碼。（20 分）

如下圖以頂點0 為啟始點，找出其深度優先展開樹（Depth-first Spanning Tree）並計 算出其成本（cost）。（20 分） 0 1

5 4 3 28 16 12 18 22 25 14 24 2 10

5 9

5 9 7 5 7