114年 - 114 公務升官等考試_薦任_資訊處理：資料結構#133251

(一)使用遞迴方法（Recursion）撰寫虛擬碼，計算第 n 項的費伯納西數。 （8 分）

(二)使用動態規劃方法（Dynamic Programming）撰寫虛擬碼，透過自底向 上（Bottom-up）的方式計算第 n 項的費伯納西數。（8 分）

(三)比較兩個方法的時間複雜度（Time Complexity）。（6 分）

二、已知 B⁺-tree 的階數（Order）為 m = 3。葉節點至多可存放 2 個鍵值，至 少須存放 1 個鍵值；內部節點至多可有 3 個子節點，至少須有 2 個子節 點。當節點因插入而溢位時，規定葉節點分裂時將右子節點之第一個鍵 值提升至父節點，內部節點分裂時則將中間鍵值提升至父節點。請完成 下列各題：
 (一)依序插入 17、5、12、23、7、19、3、30 等 8 個鍵值以建構 B+-tree。 請逐步說明並繪製每次插入後之樹形結構。

(二)承接(一)之結果，依序刪除 7、23 與 5 等三個鍵值。刪除過程中若需借 值時，一律自右兄弟節點借取；若無法借值，則與左兄弟節點合併。 請逐步說明並繪製每次刪除鍵值後之樹形結構。（6 分）

(三)承接(一)之結果，說明在該 B+-tree 中搜尋鍵值 19 之完整過程，並列出 查找時經過之節點及比較順序。（4 分）

(一)說明何謂穩定排序（Stable Sort），並解釋若演算法不屬於穩定排序， 在處理相同鍵值時會造成什麼影響。

(二)使用選擇排序（Selection Sort）對上述數列進行排序，並逐步描述每次 選擇與交換的過程，最後給出排序後的結果。

(三)使用合併排序（Merge Sort）對上述數列進行排序，並描述拆分與合併 的過程，最後給出排序後的結果。

(四)使用基數排序（Radix Sort）對上述數列進行排序，並描述逐位（個位 數、十位數）的桶排序（Bucket Sort）過程，最後給出排序後的結果。

 (一)依步驟建構霍夫曼樹，並寫出各字母的編碼。（10 分）

(二)比較固定長度編碼（假設每個字母以 3 位元表示）與霍夫曼編碼，並計算壓縮率（需列計算過程）。 （6 分）

 (一)畫出圖 G 的相鄰串列（Adjacency List）。

(二)畫出圖 G 的相鄰矩陣（Adjacency Matrix）。

(三)從節點 a 開始，寫出廣度優先搜尋（Breadth-First Search, BFS）的節點拜訪順序。

(四)從節點 a 開始，寫出深度優先搜尋（Depth-First Search, DFS）的節點拜訪順序。