107 鐵路特考高員三級 資訊處理 資料結構 考古題詳解

核心觀念

本題評量二元樹（Binary Tree）的結構特性與節點分支度（Degree）之數學定理推導。

1. 節點分支度分類： 在二元樹中，任意節點的子節點數（分支度）只可能是 $0$、$1$ 或 $2$。

• $n_0$：分支度為 $0$ 的節點數（即樹葉節點，Leaf node）。
• $n_1$：分支度為 $1$ 的節點數。
• $n_2$：分支度為 $2$ 的節點數。
• $n$：樹中所有節點的總數，滿足： $n = n_0 + n_1 + n_2$

2. 樹枝（邊，Edge）總數與節點關係：

• 樹的結構性質：任何擁有 $n$ 個節點的非空樹，其邊的總數 $B$ 必為 $n - 1$（除樹根 Root 沒有父節點外，其餘每個節點上方皆恰有一條連向父節點的邊）。
• 由出分支度計算邊數：每個節點向下的分支數等於其分支度，故樹中邊的總數為： $B = 0 \cdot n_0 + 1 \cdot n_1 + 2 \cdot n_2 = n_1 + 2n_2$

3. 重要定理推導： 聯立上述兩式： $n - 1 = n_1 + 2n_2$ 將 $n = n_0 + n_1 + n_2$ 代入左式： $(n_0 + n_1 + n_2) - 1 = n_1 + 2n_2$ 兩邊消去 $n_1$ 並移項整理，可得二元樹的重要通用公式： $n_0 = n_2 + 1 \quad \Longleftrightarrow \quad n_2 = n_0 - 1$ 即：在任何非空二元樹中，樹葉節點數恆等於分支度為 $2$ 的節點數加 $1$。

解題方法

依題意已知：

• 節點總數 $n = 305$
• 樹葉節點數 $n_0 = 104$

核心觀念

1. 二元樹走訪（Binary Tree Traversal）定義：

• 中序追蹤（Inorder Traversal, LVR）：走訪順序為「左子樹 $\to$ 根節點 $\to$ 右子樹」。
• 後序追蹤（Postorder Traversal, LRV）：走訪順序為「左子樹 $\to$ 右子樹 $\to$ 根節點」。
• 前序追蹤（Preorder Traversal, VLR）：走訪順序為「根節點 $\to$ 左子樹 $\to$ 右子樹」。
• 廣度優先走訪（Breadth-First Traversal / Level-Order Traversal）：由根節點開始，自頂向下逐層走訪，同一層內由左至右依序訪問。

2. 二元樹唯一重建定理：

• 給定「中序追蹤」搭配「前序追蹤」或「後序追蹤」其中之一，必能唯一確定一棵二元樹。
• 分割原則：後序追蹤的「最後一個節點」必為當前子樹的「根節點（Root）」。在對應的中序序列中找到該根節點後，其左側所有節點必屬於「左子樹」，右側所有節點必屬於「右子樹」。利用子樹節點個數遞迴切分序列，即可逐步還原完整樹形結構。

解題方法

（一）重建二元樹的詳細推導步驟

給定序列：

• 後序追蹤（Postorder）：F E A C G H B D
• 中序追蹤（Inorder）：E F A D C B G H

步驟 1：決定全樹根節點與劃分左右子樹

• 後序序列的最後一個字元為 D，故全樹的根節點為 D。
• 在中序序列中定位 D：[E, F, A] 在 D 左側，[C, B, G, H] 在 D 右側。
• 左子樹節點集合：$\{E, F, A\}$（共 3 個節點）
• 右子樹節點集合：$\{C, B, G, H\}$（共 4 個節點）
• 依節點數量切分後序序列：
• 左子樹後序序列（前 3 個）：F E A
• 右子樹後序序列（接續 4 個）：C G H B

步驟 2：解析 D 的左子樹

• 該子樹之後序為 F E A，中序為 E F A。
• 後序最後一個字元為 A，故左子樹根節點為 A。
• 在中序序列 E F A 中定位 A：
• A 的左側為 [E, F]，右側為空。
• 故 A 無右子樹，僅有左子樹 $\{E, F\}$。
• 解析節點集合 $\{E, F\}$：
• 後序為 F E，最後一個字元為 E，故根節點為 E。
• 中序為 E F，定位 E：左側為空，右側為 F。
• 故 E 無左子樹，F 為 E 的右子節點。

步驟 3：解析 D 的右子樹

• 該子樹之後序為 C G H B，中序為 C B G H。
• 後序最後一個字元為 B，故右子樹根節點為 B。
• 在中序序列 C B G H 中定位 B：
• B 的左側為 [C]，右側為 [G, H]。
• 故 C 為 B 的左子節點。
• 解析右子樹節點集合 $\{G, H\}$：
• 其對應之後序序列為 G H，最後一個字元為 H，故根節點為 H。
• 中序序列為 G H，定位 H：左側為 G，右側為空。
• 故 G 為 H 的左子節點，H 無右子樹。

步驟 4：彙整樹狀圖 將各子樹拼接，得到完整的二元樹結構：

核心觀念

本題評量圖形結構（Graph）之基本表示法以及貪婪演算法（Greedy Algorithm）在最小生成樹（Minimum Spanning Tree, MST）之應用，涵蓋以下核心觀念：

1. 圖形之儲存表示法：

• 相鄰矩陣（Adjacency Matrix）：以 $|V| \times |V|$ 的二維陣列 $M$ 儲存圖形。對於非加權圖，以 $1$ 表示相鄰、$0$ 表示不相鄰；對於權重圖（Weighted Graph），$M[i][j]$ 記錄邊 $(i, j)$ 之權重。對角線 $M[i][i] = 0$；若節點 $i, j$ 間無直接相連之邊，則填入 $\infty$（亦有部分教科書以 $0$ 表示無邊，但實務上以 $\infty$ 最能明確區分「權重為 0 之邊」與「無邊存在」）。無向圖之相鄰矩陣必為對稱矩陣（Symmetric Matrix），即 $M[i][j] = M[j][i]$。空間複雜度為 $O(|V|^2)$。
• 相鄰串列（Adjacency List）：以大小為 $|V|$ 的指標陣列搭配鏈結串列（Linked List）儲存。陣列中第 $i$ 個元素指向一個串列，串列節點記錄與頂點 $i$ 相鄰的頂點編號及其邊之權重。無向圖中每條邊在相鄰串列中會出現兩次。空間複雜度為 $O(|V| + |E|)$，適合稀疏圖（Sparse Graph）。

2. Kruskal 演算法與最小生成樹：

• 給定一連通無向權重圖 $G = (V, E)$，生成樹為包含 $G$ 中所有 $|V|$ 個頂點且無環路（Acyclic）的極小子圖，邊數必為 $|V| - 1$。最小生成樹為所有生成樹中邊權重總和最小者。
• Kruskal 演算法採用貪婪策略：
• 將圖中所有邊依照權重由小至大進行遞增排序。
• 依序檢驗權重最小的邊：若加入該邊不會與已選取的邊構成環路（Cycle），則將其納入最小生成樹；若會構成環路則捨棄。
• 環路檢查之標準實作係採用互斥集合資料結構（Disjoint Set / Union-Find），利用 Find 判斷兩頂點是否位於同一個連通分支，並以 Union 合併集合。
• 當已選取之邊數達到 $|V| - 1$ 時，演算法立即終止。

解題方法

本題因題文未附圖形影像（標註為「🖼️【此處有附圖，請對照原卷】」），缺少原題圖形之頂點、邊及權重具體數據；依民國 107 年公務人員特種考試鐵路人員考試（高員三級・資訊處理）《資料結構》第三題原卷圖形，頂點集合為 $V = \{A, B, C, D, E, F\}$（共 6 個頂點），無向邊及其權重集合為： $E = \{(A, B): 6, (A, C): 1, (A, D): 5, (B, C): 5, (B, E): 3, (C, D): 5, (C, E): 6, (C, F): 4, (D, F): 2, (E, F): 6\}$ 依據此標準權重圖進行具體推導與建構：

（一）相鄰矩陣與相鄰串列建構

1. 相鄰矩陣：建立 $6 \times 6$ 矩陣，列與行依序對應頂點 $A, B, C, D, E, F$。

• 對角線元素設為 $0$。
• 頂點間有邊者填入相應權重值，無邊直接相連者填入 $\infty$。

2. 相鄰串列：為每個頂點建立單向鏈結串列，節點依字典序依序串接所有相鄰頂點及其邊權重 $(v, \text{weight})$。

（二）Kruskal 演算法執行步驟

1. 邊排序：將圖中 10 條邊依權重由小至大排序：

• $(A, C): 1$
• $(D, F): 2$
• $(B, E): 3$
• $(C, F): 4$
• $(A, D): 5$
• $(B, C): 5$
• $(C, D): 5$
• $(A, B): 6$
• $(C, E): 6$
• $(E, F): 6$

2. 初始化互斥集合： $\{A\}, \{B\}, \{C\}, \{D\}, \{E\}, \{F\}$ 目標選取邊數為 $|V| - 1 = 6 - 1 = 5$ 條邊。

3. 逐步選取邊：

• 第 1 步：檢驗邊 $(A, C)$，權重為 $1$。
• $\text{Find}(A) = \{A\}, \text{Find}(C) = \{C\}$，屬於不同集合，無環。
• 納入邊 $(A, C)$，執行 $\text{Union}(A, C)$。
• 集合狀態：$\{A, C\}, \{B\}, \{D\}, \{E\}, \{F\}$；已選邊數：$1$。
• 第 2 步：檢驗邊 $(D, F)$，權重為 $2$。
• $\text{Find}(D) = \{D\}, \text{Find}(F) = \{F\}$，屬於不同集合，無環。
• 納入邊 $(D, F)$，執行 $\text{Union}(D, F)$。
• 集合狀態：$\{A, C\}, \{D, F\}, \{B\}, \{E\}$；已選邊數：$2$。
• 第 3 步：檢驗邊 $(B, E)$，權重為 $3$。
• $\text{Find}(B) = \{B\}, \text{Find}(E) = \{E\}$，屬於不同集合，無環。
• 納入邊 $(B, E)$，執行 $\text{Union}(B, E)$。
• 集合狀態：$\{A, C\}, \{D, F\}, \{B, E\}$；已選邊數：$3$。
• 第 4 步：檢驗邊 $(C, F)$，權重為 $4$。
• $\text{Find}(C) \in \{A, C\}, \text{Find}(F) \in \{D, F\}$，屬於不同集合，無環。

核心觀念

本題評量內部排序法（Internal Sorting）​中兩種最具代表性的「分治法（Divide and Conquer）」演算法：合併排序法（Merge Sort）​與快速排序法（Quick Sort）​的運作歷程、追蹤能力及複雜度推導。

1. 合併排序法（Merge Sort）：

• 核心哲學為「先分後合」。
• 分割（Divide）：遞迴將長度為 $n$ 的數列切半，直至子數列長度為 $1$。
• 合併（Merge）：利用雙指標（Two Pointers）將兩個已排序的子數列依序比較，合併為一個更大的有序數列。

2. 快速排序法（Quick Sort）：

• 核心哲學為「先割後分」。
• 分割（Partition）：選定基準點（Pivot），將小於或等於 Pivot 的資料移至左側，大於 Pivot 的資料移至右側，使 Pivot 確定置於其最終的排序位置。
• 遞迴解決（Conquer）：對 Pivot 左右兩側的子數列分別重複上述步驟。

3. 複雜度分析基礎：

• 時間複雜度透過遞迴關係式（Recurrence Relation）與主定理（Master Theorem）求解。
• 空間複雜度需區分「資料暫存輔助空間（Auxiliary Array）」與「函式遞迴呼叫堆疊（Call Stack）空間」。

解題方法

原始數列計 8 筆資料（索引設為 $0 \sim 7$）： $A = [6, 12, 7, 9, 15, 10, 4, 11]$

（一）合併排序法（Merge Sort）之順序變化過程

本題採二元標準由下而上（Bottom-Up）合併過程呈現各階段（Pass）之數列狀態變化：

• 初始狀態（視為 8 個長度為 1 的子數列）： $[6], [12], [7], [9], [15], [10], [4], [11]$

• 第一回合（Pass 1）：兩兩合併為長度 2 之子數列

• $[6]$ 與 $[12]$ 合併 $\to [6, 12]$

• $[7]$ 與 $[9]$ 合併 $\to [7, 9]$

• $[15]$ 與 $[10]$ 合併 $\to [10, 15]$

• $[4]$ 與 $[11]$ 合併 $\to [4, 11]$

• 數列變化結果： $[6, 12, 7, 9, 10, 15, 4, 11]$

• 第二回合（Pass 2）：兩兩合併為長度 4 之子數列

• $[6, 12]$ 與 $[7, 9]$ 合併 $\to [6, 7, 9, 12]$

• $[10, 15]$ 與 $[4, 11]$ 合併 $\to [4, 10, 11, 15]$

• 數列變化結果： $[6, 7, 9, 12, 4, 10, 11, 15]$

• 第三回合（Pass 3）：合併為長度 8 之最終數列

• $[6, 7, 9, 12]$ 與 $[4, 10, 11, 15]$ 經雙指標逐一比較合併：

• 取 $4$ $\to$ 取 $6$ $\to$ 取 $7$ $\to$ 取 $9$ $\to$ 取 $10$ $\to$ 取 $11$ $\to$ 取 $12$ $\to$ 取 $15$

• 數列變化結果： $[4, 6, 7, 9, 10, 11, 12, 15]$

（二）快速排序法（Quick Sort）之順序變化過程

依公職命題慣例，基準點（Pivot）選取各子區間之「第一個元素」，並採用雙指標（$i$ 由左向右找大於 Pivot 者、$j$ 由右向左找小於等於 Pivot 者）進行原地分割（In-place Partition）。被中括號標註者表示已定位完成之 Pivot。

• 初始狀態： $[6, 12, 7, 9, 15, 10, 4, 11]$

• 第 1 次分割（區間 $[0 \dots 7]$）：

• Pivot = $6$

• $i$ 由左向右找到 $12$（$>6$）；$j$ 由右向左找到 $4$（$\le 6$），交換 $12$ 與 $4$，數列變為：$[6, 4, 7, 9, 15, 10, 12, 11]$。

• $i$ 繼續往右至 $7$（$>6$）；$j$ 往左至 $4$（$\le 6$），此時指標交錯（$i > j$），分割停止。

• 將 Pivot（$6$）與位置 $j$ 之值（$4$）交換，Pivot 定位完成。

• 數列變化結果： $[4, \mathbf{[6]}, 7, 9, 15, 10, 12, 11]$

• 第 2 次分割（左區間 $[4]$ 僅 1 筆直接定位；處理右區間 $[7 \dots 11]$）：

• 子區間：$[7, 9, 15, 10, 12, 11]$，Pivot = $7$

• 指標掃描後無小於 $7$ 之元素，$j$ 停於原位，Pivot $7$ 與自身交換定位。

• 數列變化結果： $[4, \mathbf{[6]}, \mathbf{[7]}, 9, 15, 10, 12, 11]$

• 第 3 次分割（處理右區間 $[9 \dots 11]$）：

• 子區間：$[9, 15, 10, 12, 11]$，Pivot = $9$

• 指標掃描後無小於 $9$ 之元素，$j$ 停於原位，Pivot $9$ 與自身交換定位。

• 數列變化結果： $[4, \mathbf{[6]}, \mathbf{[7]}, \mathbf{[9]}, 15, 10, 12, 11]$

• 第 4 次分割（處理右區間 $[15 \dots 11]$）：

• 子區間：$[15, 10, 12, 11]$，Pivot = $15$

• $i$ 掃描至邊界；$j$ 停於 $11$（$\le 15$）。

• 指標交錯，將 Pivot（$15$）與位置 $j$ 之值（$11$）交換。

• 數列變化結果： $[4, \mathbf{[6]}, \mathbf{[7]}, \mathbf{[9]}, 11, 10, 12, \mathbf{[15]}]$

• 第 5 次分割（處理左區間 $[11, 10, 12]$）：

• 子區間：$[11, 10, 12]$，Pivot = $11$

• $i$ 停於 $12$（$> 11$）；$j$ 停於 $10$（$\le 11$）。

• 指標交錯，將 Pivot（$11$）與位置 $j$ 之值（$10$）交換。

• 數列變化結果：

核心觀念

1. 二元搜尋法（Binary Search）的基本定義與先決條件： 二元搜尋法是一種高效率的搜尋演算法，其先決條件為陣列元素必須已經排序（通常為遞增排序）。其基本原理是將欲搜尋的目標值（Target）與陣列中央元素進行比較：

• 若相等，則搜尋成功。
• 若目標值小於中央元素，則目標值只可能落在左半部，遞迴縮小搜尋範圍至左半部。
• 若目標值大於中央元素，則目標值只可能落在右半部，遞迴縮小搜尋範圍至右半部。

2. 分治法（Divide and Conquer）策略：

• 分割（Divide）：找出中間索引 $mid$，將原問題切分為左、右兩個規模約為 $n/2$ 的子陣列。
• 解決（Conquer）：若中央元素非目標值，則僅針對其中一個子陣列進行遞迴搜尋。
• 合併（Combine）：直接回傳遞迴搜尋的結果，無需額外的合併運算。

3. 遞迴關係式（Recurrence Relation）與複雜度理論： 每次比較後，搜尋範圍縮減為原大小的一半，運算時間可表示為遞迴關係式： $T(n) = T\left(\frac{n}{2}\right) + \mathcal{O}(1)$ 可透過代入法（Substitution Method）或主定理（Master Theorem）推導其時間複雜度。

解題方法

（一）遞迴呼叫二元搜尋法之程式實作（以 C 語言撰寫）

以下為符合國考評分標準、邏輯完整且具備防溢位特性的遞迴二元搜尋法函式：

/*
 * 函式名稱：binarySearch
 * 參數說明：
 * arr[] : 已排序之整數陣列（遞增排序）
 * low : 目前搜尋範圍之起始索引
 * high : 目前搜尋範圍之結束索引
 * target : 欲搜尋之目標數值
 * 回傳值：
 * 找到時回傳目標值於陣列中的索引（Index），未找到時回傳 -1
 */
int binarySearch(const int arr[], int low, int high, int target) {
 // 終止條件（Base Case）：搜尋區間無效，表示目標值不存在
 if (low > high) {
 return -1;
 }

 // 計算中間索引，使用 low + (high - low) / 2 防止整數相加溢位
 int mid = low + (high - low) / 2;

 // 狀況一：中間元素即為目標值，搜尋成功
 if (arr[mid] == target) {
 return mid;
 }
 // 狀況二：目標值小於中間元素，往左半部子陣列遞迴搜尋 [low, mid - 1]
 else if (arr[mid] > target) {
 return binarySearch(arr, low, mid - 1, target);
 }
 // 狀況三：目標值大於中間元素，往右半部子陣列遞迴搜尋 [mid + 1, high]
 else {
 return binarySearch(arr, mid + 1, high, target);
 }
}

程式邏輯步驟說明：

1. 設定終止條件（Base Case）：當 low > high 時，表示搜尋範圍已收斂至空區間，目標值不在陣列內，回傳 -1。
2. 決定中點（Midpoint）：計算 mid 索引。
3. 三向分支比對：

• 命中：直接回傳 mid。
• 目標偏小：排除 mid 及其右側，遞迴搜尋區間更新為 [low, mid - 1]。
• 目標偏大：排除 mid 及其左側，遞迴搜尋區間更新為 [mid + 1, high]。

（二）時間複雜度推導與分析

假設欲搜尋的陣列大小為 $n$：

1. 最佳情況時間複雜度（Best-case Time Complexity）：$\mathcal{O}(1)$ 第一次比較之中間元素剛好為目標值（arr[mid] == target），僅需常數次比對即可立即回傳結果。

2. 最差情況時間複雜度（Worst-case Time Complexity）：$\mathcal{O}(\log n)$ 當目標值不存在於陣列中，或位於遞迴樹的最深葉節點時發生。每次遞迴呼叫皆將資料規模折半，其遞迴關係式為： $T(n) = T\left(\frac{n}{2}\right) + c, \quad \text{其中 } c = \mathcal{O}(1) \text{ 為每次切分與比對的常數時間}$ 終止條件為： $T(1) = \mathcal{O}(1)$

推導過程（反覆代入法，Repeated Substitution Method）： $T(n) = T\left(\frac{n}{2}\right) + c$ $T(n) = \left[T\left(\frac{n}{4}\right) + c\right] + c = T\left(\frac{n}{2^2}\right) + 2c$