109 地方特考三等 資訊處理 資料結構 考古題詳解

核心觀念

本題評量二元樹（Binary Tree）的動態走訪與深層複製（Deep Copy）演算法設計。

1. 深層複製（Deep Copy） vs. 淺層複製（Shallow Copy）：

• 淺層複製僅複製根節點的指標位址，會使新舊指標指向同一塊記憶體位址，造成別名效應（Aliasing）與重複釋放（Double Free）風險。
• 複製整棵二元樹必須進行「深層複製」，為新樹的每個節點獨立配置記憶體空間（Dynamic Memory Allocation），並遞迴複製原樹各節點的數值與結構鏈結。

2. 走訪策略（Tree Traversal）：

• 樹狀結構具備高度自相似性（Self-similarity），天然適合採用**分治法（Divide and Conquer）與遞迴（Recursion）**實現。
• 複製二元樹通常採用**前序走訪（Preorder Traversal）或後序走訪（Postorder Traversal）**概念：先配置新節點並複製資料，再遞迴複製左、右子樹；或先複製完左右子樹後，再連結至新建立的根節點。

解題方法

1. 資料結構定義

在實作演算法前，先定義標準的二元樹鏈結串列結構（以 C 語言為例）：

typedef struct TreeNode {
 int data; // 節點儲存資料
 struct TreeNode *left; // 指向左子樹的指標
 struct TreeNode *right; // 指向右子樹的指標
} TreeNode;

2. 演算法邏輯推導

設函式為 CopyTree(root)，輸入為原二元樹的根節點指標 root，回傳值為新複製二元樹的根節點指標：

• 基本終止條件（Base Case）：若輸入節點為空（root == NULL），表示當前子樹為空，直接回傳 NULL。
• 遞迴步驟（Recursive Step）：

1. 使用動態記憶體配置（如 malloc）產生一個新的節點空間 newNode。
2. 複製資料：將原節點的資料複製給新節點（newNode->data = root->data）。
3. 複製左子樹：遞迴呼叫 CopyTree(root->left)，並將回傳之新左子樹根指標賦予 newNode->left。
4. 複製右子樹：遞迴呼叫 CopyTree(root->right)，並將回傳之新右子樹根指標賦予 newNode->right。
5. 回傳當前新建立的節點指標 newNode。

3. 演算法程式碼（C 語言實作）

核心觀念

本題考查高階樹狀資料結構中 B-tree（B-樹，平衡多元搜尋樹） 的基本定義與極值推導。核心考點包含：

1. 階數（Order $m$）的意義：決定了節點最多可擁有的子樹（分支）數目與鍵值（Key）數目上限。
2. 分支數與鍵值數的關係：若一個節點擁有 $k$ 個分支，則該節點內部必恰好包含 $k - 1$ 個鍵值。
3. 內部節點與根節點（Root）的下限限制：

• 令 $d = \lceil m/2 \rceil$。
• 非根節點之分支數至少為 $d$，即鍵值數至少為 $d - 1$。
• 根節點為特例：當樹高 $h \ge 2$ 時，根節點之分支數最少僅需為 $2$，即鍵值數最少為 $1$。

4. 樹高（Height $h$）與層數（Level）的約定： 本題採國內資訊處理類科公職考試及權威教本（如 Horowitz 等）最主流之標準定義——根節點位於第 $1$ 層，整棵樹共有 $h$ 層節點，葉節點位於第 $h$ 層進行推導。

解題方法

（一）Order 為 $m$ 的 B-tree 之特性（6 分）

一棵 order 為 $m$ 的 B-tree，必須嚴格滿足以下五項結構與排序特性：

1. 子節點數上限：樹中任一節點最多擁有 $m$ 個子節點（即最多包含 $m - 1$ 個鍵值）。
2. 根節點特例：若根節點不是葉節點，則根節點至少擁有 $2$ 個子節點（至少包含 $1$ 個鍵值）。若整棵樹只有根節點（$h = 1$），則至少包含 $1$ 個鍵值。
3. 非根節點的子節點數下限：除根節點外，所有非葉節點至少擁有 $\lceil m/2 \rceil$ 個子節點（即至少包含 $\lceil m/2 \rceil - 1$ 個鍵值）。
4. 葉節點等高平衡性：所有外部葉節點（Leaf nodes）皆位於同一深度（同一層），保證樹結構具備完美的平衡性。
5. 多元搜尋排序性：節點內的鍵值依序由小到大排列；若一節點具有 $k$ 個子節點，則該節點包含 $k - 1$ 個鍵值 $K_1 < K_2 < \dots < K_{k-1}$，並將子樹範圍劃分為 $k$ 個有序區間，使得介於 $K_i$ 與 $K_{i+1}$ 之間的分支子樹所有鍵值皆落在此開區間內。

（二）Order 為 $m$、高度為 $h$ 的極值推導

令 $d = \lceil m/2 \rceil$。

1. 最多有幾個節點？最多有幾個 Key？（6 分）

• 推導切入點： 若要使節點數與鍵值數達到最大值，則每個節點的分支數皆必須取上限 $m$，且每個節點的鍵值數皆必須取上限 $m - 1$。

• 最多節點數（$N_{\max}$）推導： 各層節點數呈公比為 $m$ 的等比數列：

• 第 $1$ 層（根節點）：$m^0 = 1$ 個節點

• 第 $2$ 層：$m^1$ 個節點

• 第 $3$ 層：$m^2$ 個節點

• $\dots$

• 第 $i$ 層：$m^{i-1}$ 個節點

• 第 $h$ 層：$m^{h-1}$ 個節點

總節點數為各層總和（等比級數求和）： $N_{\max} = \sum_{i=1}^{h} m^{i-1} = \frac{m^h - 1}{m - 1}$

• 最多鍵值數（$K_{\max}$）推導： 由於每個節點皆填滿 $m - 1$ 個鍵值，總鍵值數為節點總數乘上 $(m - 1)$： $K_{\max} = (m - 1) \times N_{\max} = (m - 1) \times \frac{m^h - 1}{m - 1} = m^h - 1$

2. 最少有幾個節點？最少有幾個 Key？（8 分）

• 推導切入點： 若要使節點數與鍵值數達到最小值，則各節點的分支數與鍵值數皆必須取下限：

• 根節點的分支數取下限 $2$，鍵值數取下限 $1$。

• 其餘各層內部節點的分支數皆取下限 $d = \lceil m/2 \rceil$，鍵值數皆取下限 $d - 1$。

• 最少節點數（$N_{\min}$）推導：

• 當 $h = 1$ 時：整棵樹僅有根節點，$N_{\min} = 1$。

• 當 $h \ge 2$ 時，分析各層節點數：

• 第 $1$ 層（根節點）：$1$ 個節點

• 第 $2$ 層：根節點僅有 $2$ 個分支 $\Rightarrow 2$ 個節點

• 第 $3$ 層：第 $2$ 層的每個節點各有 $d$ 個分支 $\Rightarrow 2 \times d$ 個節點

• $\dots$

• 第 $i$ 層（$2 \le i \le h$）：$2 \times d^{i-2}$ 個節點

核心觀念

Double Hashing（雙重雜湊）處理碰撞時，使用第二個雜湊函數決定每次探查的步長。第 $i$ 次探查的位置為：

其中 $i$ 從 $0$ 開始；若 $i=0$，就是先檢查初始位置 $h_1(k)$。依題目給定的 key 順序逐一插入，遇到已占用的位置就依探查序列繼續尋找空格。

解題方法

依序計算每個 key 的初始位置與步長：

• $24$：$h_1=24\bmod13=11$，$h_2=1+(24\bmod11)=3$。索引 $11$ 空，放入 $24$。
• $53$：$h_1=1$，$h_2=10$。索引 $1$ 空，放入 $53$。
• $17$：$h_1=4$，$h_2=7$。索引 $4$ 空，放入 $17$。
• $46$：$h_1=7$，$h_2=3$。索引 $7$ 空，放入 $46$。
• $14$：$h_1=1$，$h_2=4$。索引 $1$ 已有 $53$；下一個位置為 $(1+4)\bmod13=5$，放入索引 $5$。

核心觀念

AVL tree 是每個節點左右子樹高度差不超過 $1$ 的二元搜尋樹。題目以 root 高度為 $0$，因此空子樹高度為 $-1$、葉節點高度為 $0$。

高度固定為 $h$ 時：

• 節點數最多：左右子樹都填滿，$N_{\max}(h)=2^{h+1}-1$。
• 節點數最少：左右子樹高度取 $h-1$ 與 $h-2$，所以 $N_{\min}(h)=1+N_{\min}(h-1)+N_{\min}(h-2),$ 其中 $N_{\min}(0)=1$、$N_{\min}(1)=2$。

插入節點時，先依二元搜尋樹規則放到葉節點，再由下往上檢查平衡；失衡時依插入方向採用 LL、RR、LR 或 RL 旋轉。

（一）解題方法與計算

1. 高度為 $6$ 的 AVL tree：

最多節點數為 $N_{\max}(6)=2^{7}-1=127.$

最少節點數依遞迴式計算：

因此，高度為 $6$ 時最多有 $127$ 個節點，最少有 $33$ 個節點。

2. 樹共有 $45$ 個節點：

要讓高度最高，找出仍能容納 $45$ 個節點的最大高度。由遞迴式得 $N_{\min}(6)=33$、$N_{\min}(7)=54$，因此高度 $6$ 可容納 $45$ 個節點，高度 $7$ 至少需要 $54$ 個節點。最高高度為 $6$。

要讓高度最矮，找出最大節點數首次達到 $45$ 的高度： $N_{\max}(4)=2^5-1=31<45,\qquad N_{\max}(5)=2^6-1=63\ge45.$ 最矮高度為 $5$。

（二）逐步插入與平衡

以下以 $x(L,R)$ 表示節點 $x$，其左、右子樹分別為 $L$、$R$；$\varnothing$ 表示空子樹。原樹為：

$14\bigl(8(4,\varnothing),\ 28(20(16,\varnothing),52)\bigr).$

核心觀念

將圖 2 的二元樹依「由上到下、由左到右」轉成陣列，再用由下而上的堆積化建立 Min Heap。Min Heap 的定義是：每個父節點的值都小於或等於其子節點，因此根節點是目前最小值。

建立 Min Heap 後，每次取出根節點，將最後一個元素移到根部，再向下調整堆積。依序取出的值便是由小到大的排列。

解題方法

圖中的層序陣列為：

$[22,14,20,12,16,18,17,5,8]$

採用 0 起始索引，從最後一個非葉節點開始向前堆積化。陣列長度為 9，最後一個非葉節點索引為 $\lfloor 9/2 \rfloor-1=3$。

核心觀念

KMP 的失敗函數記錄：對 pattern 的每個位置 $i$，子字串 $P[0..i]$ 中，最長的「真前綴」同時也是「真後綴」的長度。此處採用長度表示法，因此 $F[0]=0$。

當比對到位置 $j$ 失敗時，利用已比對部分的失敗函數值，保留可重用的前綴比對結果，避免 string 指標回頭。

解題方法

題目的 pattern 長度為 $18$，位置 $0$ 到 $17$ 的字元依序為：

例如：

• $i=6$ 時，$P[0..6]=\text{abcdabc}$，最長相同真前綴與真後綴為 $\text{abc}$，故 $F[6]=3$。
• $i=13$ 時，$P[0..13]=\text{abcdabcabcdabc}$，最長相同真前綴與真後綴為 $\text{abcdabc}$，故 $F[13]=7$。