114 公務人員升官等薦任 資訊處理 資料結構 考古題詳解

核心觀念

本題考查費伯納西數列的遞迴定義，以及遞迴與動態規劃的實作方式和時間複雜度。

數列定義為：

直接遞迴會重複計算許多相同的子問題；自底向上的動態規劃則依序計算並保存已求出的數值，避免重複計算。

（一）遞迴方法

遇到 $n=0$ 或 $n=1$ 時，直接回傳定義的基底值；其他情況依定義將前兩項相加。

FibonacciRecursive(n)
 if n = 0
 return 0
 if n = 1
 return 1
 return FibonacciRecursive(n - 1)
 + FibonacciRecursive(n - 2)

以 $n=5$ 為例：

此方法直接呈現數列的數學定義，但會在遞迴展開時重複計算，例如 $F(3)$ 在計算 $F(5)$ 時會被求出不只一次。

（二）自底向上的動態規劃

從已知的基底值 $F(0)$、$F(1)$ 開始，依序計算 $F(2)$ 至 $F(n)$，並將每一項保存下來。

FibonacciBottomUp(n)
 if n = 0
 return 0

 建立陣列 F[0..n]
 F[0] ← 0
 F[1] ← 1

 for i ← 2 to n
 F[i] ← F[i - 1] + F[i - 2]

 return F[n]

例如計算 $F(5)$：

核心觀念

本題考查 B+-tree 的插入、溢位分裂、刪除後的再平衡，以及依分隔鍵逐層搜尋。

• 葉節點最多存放 $2$ 個鍵值，至少存放 $1$ 個鍵值。葉節點溢位時，將鍵值由小到大分成左右兩個葉節點，並把右葉節點的第一個鍵值複製到父節點作為分隔鍵；該鍵值仍保留在葉節點。
• 內部節點最多有 $3$ 個子節點、至少有 $2$ 個子節點。內部節點溢位時，將中間鍵值提升至父節點；左右兩側的鍵值與子節點分別留在分裂後的左右節點。
• B+-tree 的資料鍵值都存放於葉節點；內部節點的鍵值用來指引搜尋。
• 刪除後，若節點低於最低容量，先依題目規定自右兄弟借值；右兄弟不能提供時，與左兄弟合併，並同步更新父節點分隔鍵。

以下以方括號表示葉節點，以圓括號表示內部節點；例如 $[5,12]$ 是葉節點，$(12)$ 是含有分隔鍵 $12$ 的內部節點。

（一）依序插入 8 個鍵值

插入 17

根節點同時也是葉節點：

[17]

插入 5

[5,17]

插入 12

排序後成為 $[5,12,17]$，超過葉節點容量 $2$。分成 $[5]$ 與 $[12,17]$，將右葉節點第一個鍵值 $12$ 複製到父節點，形成新根：

 (12)
 / \
 [5] [12,17]

插入 23

$23 \ge 12$，進入右葉節點，該葉節點成為 $[12,17,23]$，再分成 $[12]$ 與 $[17,23]$；將 $17$ 複製至父節點：

 (12,17)
 / | \
 [5] [12] [17,23]

插入 7

$7 < 12$，插入最左葉節點：

 (12,17)
 / | \
 [5,7] [12] [17,23]

插入 19

$19 \ge 17$，插入最右葉節點。該葉節點成為 $[17,19,23]$，分裂為 $[17]$ 與 $[19,23]$，將 $19$ 複製到父節點。父節點原有兩個鍵值，加入後成為 $(12,17,19)$，有四個子節點，超過內部節點最多 $3$ 個子節點的限制。

內部節點分裂時提升中間鍵值 $17$，左右兩側分別保留分隔鍵 $12$ 與 $19$：

 (17)
 / \
 (12) (19)
 / \ / \
 [5,7] [12] [17] [19,23]

插入 3

$3 < 17$，再依左側內部節點的分隔鍵 $12$ 導向 $[5,7]$。插入後成為 $[3,5,7]$，分裂為 $[3]$ 與 $[5,7]$，將右葉節點第一個鍵值 $5$ 複製至父節點：

 (17)
 / \
 (5,12) (19)
 / | \ / \
 [3] [5,7] [12] [17] [19,23]

插入 30

$30 \ge 17$，導向右側內部節點 $(19)$，再進入右葉節點 $[19,23]$。插入後成為 $[19,23,30]$，分裂為 $[19]$ 與 $[23,30]$，將 $23$ 複製至父節點：

 (17)
 / \
 (5,12) (19,23)
 / | \ / | \
 [3] [5,7] [12][17] [19] [23,30]

這是第（一）小題完成後的 B+-tree。

核心觀念

本題考查穩定排序的定義，以及選擇排序、合併排序、基數排序的操作方式。排序鍵值相同時，以底線標示的 $36$ 記為 $\underline{36}$，未標示者記為 $36$，藉此追蹤兩者的相對次序。

穩定排序（Stable Sort）：若兩筆資料的鍵值相同，排序後仍保留它們在原始數列中的先後次序。本題原始次序是 $36$ 在 $\underline{36}$ 之前；穩定排序後也必須維持此順序。若排序演算法不穩定，相同鍵值的資料可能交換相對位置；當資料還帶有其他欄位時，即使主鍵相同，這些欄位的先後關係也可能改變。

解題方法

（一）穩定性說明（6 分）

穩定性只比較鍵值相同的資料：若排序前 $A$ 在 $B$ 之前，且兩者鍵值相同，排序後仍讓 $A$ 在 $B$ 之前，則此排序為穩定排序。

本題可用兩個 $36$ 驗證：穩定排序須保留 $36,\ \underline{36}$ 的次序；若排序後變成 $\underline{36},\ 36$，即表示相對次序改變，該次排序不穩定。

（二）選擇排序（6 分）

每一趟從尚未排序的部分找出最小值，與該部分的第一個元素交換。以下採用標準的「交換式選擇排序」。

初始數列：

第 2 趟把位置 2 的 $45$ 與位置 8 的 $36$ 交換，原本位於 $45$ 後方的 $\underline{36}$ 因此移到未標示的 $36$ 前面。這說明標準選擇排序不具穩定性。

（三）合併排序（6 分）

合併排序先遞迴拆分，再將已排序的小數列合併。合併時遇到相同鍵值，若優先取左半部的元素，便能保留原始相同鍵值元素的先後次序。

拆分：

核心觀念

霍夫曼編碼（Huffman Coding）是依符號出現頻率建立最佳前綴碼的方法。建樹時反覆取出權重最小的兩個節點合併，新節點的權重為兩者相加，直到只剩一個根節點。將每個節點的左分支標為 $0$、右分支標為 $1$，從根走到葉節點的位元序列就是該字母的編碼。

本題指定權重相同時依字母順序決定先後，因此也需為合併後的內部節點指定排序標籤：以該子樹所含字母中排序最前者作為標籤。

解題方法

先將字母按權重由小到大排列：

$N(5)、G(5)、I(6)、R(6)、U(7)、T(15)$

依規則每次合併最小的兩個節點：

第 1 步的 $G$、$N$ 權重相同，按字母順序先取 $G$；第 2 步的 $I$、$R$ 同理先取 $I$。之後每一步都是取當下權重最小的兩個節點。

依合併順序建立樹，左右分支由左至右分別標記 $0$、$1$：

 (44)
 / \
 (17) (27)
 / \ / \
 U(7) (10) (12) T(15)
 / \ / \
 G(5) N(5) I(6) R(6)

由根節點往下讀取分支標記，可得：

核心觀念

有向圖的相鄰串列記錄每個頂點沿箭頭方向可到達的頂點；相鄰矩陣以列表示起點、欄表示終點，若有邊則記為 $1$，沒有則記為 $0$。

BFS 使用佇列，依層次拜訪；DFS 沿著尚未拜訪的鄰點繼續深入，再回溯。題目沒有指定同一頂點的鄰點處理順序，因此以下採頂點字母順序處理，亦即 $a,b,c,d,e,f$。

解題方法

依圖中箭頭可整理出邊：

（一）相鄰串列

按字母順序列出各頂點的出邊：

• $a:\ b,d,f$
• $b:\ a,c,d$
• $c:\ e,f$
• $d:\ c,e$
• $e:\ \varnothing$
• $f:\ e$

（二）相鄰矩陣

列為起點、欄為終點，頂點順序皆為 $a,b,c,d,e,f$：