108 高普考高考三級 資訊處理 資料結構 考古題詳解

核心觀念

1. 二元樹（Binary Tree）的遞迴定義： 二元樹是一種遞迴結構，其定義為：樹要麼為空集合（$\text{tree} = \text{NULL}$），要麼由一個根節點（Root）以及兩棵互不相交的左子樹（Left Subtree）與右子樹（Right Subtree）所組成。
2. 分治法（Divide and Conquer）與後序走訪概念： 處理樹狀結構的統計問題，標準做法是將大問題拆解為獨立的左右子問題，先分別求得子樹的解，再匯總為整棵樹的解：

• 計算節點總數：若樹為空，節點數為 $0$；否則節點總數等於「左子樹節點數 $+$ 右子樹節點數 $+ 1$（根節點本身）」。 $N(T) = \begin{cases} 0, & \text{若 } T = \text{NULL} \\ 1 + N(T\to \text{left}) + N(T\to \text{right}), & \text{若 } T \neq \text{NULL} \end{cases}$
• 計算葉節點個數：葉節點（Leaf Node）定義為分歧度（Degree）為 $0$ 的節點，即其左右指標皆為空（$T\to \text{left} = \text{NULL}$ 且 $T\to \text{right} = \text{NULL}$）。 $L(T) = \begin{cases} 0, & \text{若 } T = \text{NULL} \\ 1, & \text{若 } T\to \text{left} = \text{NULL} \text{ 且 } T\to \text{right} = \text{NULL} \\ L(T\to \text{left}) + L(T\to \text{right}), & \text{其他} \end{cases}$

---

解題方法

本題要求以 C 語言遞迴函式計算「節點總數」與「葉節點個數」，解題切入點在於設計精準的基準終止條件（Base Cases）​與遞迴關係式（Recursive Steps）：

1. 計算節點總數 (countTree)：

• 終止條件：傳入指標為空（tree == NULL），代表空樹或走訪至葉節點下方，回傳 $0$。
• 遞迴步驟：非空節點時，對左子樹與右子樹分別呼叫 countTree，並將兩者回傳值加上 $1$（計入當前節點）後回傳。

2. 計算葉節點個數 (countLeaves)：

• 終止條件一（空樹）：若 tree == NULL，空樹不含任何葉節點，回傳 $0$。
• 終止條件二（葉節點）：若當前節點滿足 tree->left == NULL && tree->right == NULL，代表該節點為葉節點，回傳 $1$。
• 遞迴步驟：若當前節點非葉節點（至少有一個子節點），則整棵樹的葉節點數即為「左子樹的葉節點數 $+$ 右子樹的葉節點數」，回傳 countLeaves(tree->left) + countLeaves(tree->right)。

---

選項分析

本題為申論程式實作題（非選擇題），針對題目給定的程式碼骨架、介面設計與邊界條件進行分析：

1. 函式回傳型態之修正考量（void 轉換為 int）： 題幹給定之骨架為 void countTree(NODEPTR tree) 與 void countLeaves(NODEPTR tree)。由於參數列只有樹的指標，且要求「計算（Count）」個數，若回傳型態設為 void，遞迴呼叫時各層節點將無法向上回傳計數結果，呼叫端亦無法取得數值。依據歷年公職資料結構閱卷標準，題幹此處為典型的骨架型態疏漏，最正規且學理嚴謹的解法是將回傳型態改為 int，實作無副作用的純粹分治遞迴。
2. 空指標先驗（tree == NULL）的必要性： 任何指標存取運算子（->）執行前，必須保證指標不為 NULL。

核心觀念

本題評量二元樹（Binary Tree）的走訪、遞迴設計（Recursion）​以及指標運算（Pointer Manipulation）。

1. 二元樹鏡像反轉（Mirror / Invert Binary Tree）：

• 題目要求將「每一節點」的左、右子節點互換，意味著整體二元樹將轉換為原樹的鏡像（Mirror Image）。
• 對於樹中每一個非空節點，其指標成員 left 與 right 必須彼此對調，且其左右子樹也必須依同樣規則徹底翻轉。

2. 遞迴的兩大基本要素：

• 終止條件（Base Case）：當輸入指標為空（tree == NULL）時，表示已達空樹或葉節點下方，不需處理，直接返回（return）。
• 遞迴步驟（Recursive Step）：
• 交換當前節點的 left 與 right 指標。
• 遞迴呼叫函式自身，分別處理其左子樹與右子樹。

3. 走訪架構（Traversal Order）：

• 本題可採前序走訪（Pre-order）​或後序走訪（Post-order）​實作。若採前序走訪，則先交換當前節點的左右子樹指標，再遞迴深入兩側；若採後序走訪，則先將兩側子樹各自鏡像完成後，再將當前節點的左右指標對調。兩者皆能在時間複雜度 $O(n)$ 內完成。

---

解題方法

本解法採用前序走訪（Pre-order）​邏輯進行遞迴交換，步驟明確且不易出錯：

步驟 1：定義遞迴終止條件

遞迴必須有明確邊界。當傳入的指標 tree 為空指標 NULL 時，無節點需要交換，直接結束本次函式呼叫：

if (tree == NULL) {
 return;
}

步驟 2：交換當前節點的左右指標

宣告一個型態為 NODEPTR 的暫存指標變數 temp，暫存當前節點的左子節點位址，再將右子節點位址賦予左指標，最後將 temp 賦予右指標，完成互換：

NODEPTR temp = tree->left;
tree->left = tree->right;
tree->right = temp;

步驟 3：遞迴處理左右子樹

當前層級交換完成後，對兩邊子樹遞迴呼叫 swapTree：

swapTree(tree->left);
swapTree(tree->right);

核心觀念

本題出自經典排序演算法——快速排序法（Quick Sort）​的分割程序（Partition / Divide Step），原始程式碼架構源自 Tenenbaum 所著《Data Structures Using C》之分割函式實作。

核心機制與運作原理如下：

1. 基準點（Pivot）選定：選取子陣列第 1 個元素作為基準值，即 $a = x[lb]$。
2. 雙向指標掃描：

• 指標 down 從左端（$lb$）向右推進，尋找「大於基準值 $a$」的元素（欲置換至右側）。
• 指標 up 從右端（$ub$）向左推進，尋找「小於或等於基準值 $a$」的元素（欲置換至左側）。
• 若兩指標尚未交錯（$down < up$），則互換 $x[down]$ 與 $x[up]$，使小值在左、大值在右。

3. 基準點歸位（Pivot Placement）：

• 當兩指標交錯（$down \ge up$）時跳出外層迴圈。
• 將位於 $x[lb]$ 的基準點與 $x[up]$ 互換，此時基準值即座落於其排序後的最終正確位置，左側所有元素均 $\le a$，右側所有元素均 $> a$。最後將該分割點索引存入 *pj 回傳。

---

解題方法

題目給定初始陣列 $x[] = [30, 75, 53, 47, 21, 94, 88, 39]$，範圍 $lb = 0$、$ub = 7$。

1. 變數初始值

• 基準值 $a = x[0] = 30$
• $down = lb = 0$
• $up = ub = 7$

各元素與初始索引對應如下：

$$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline \text{索引} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline x[\text{索引}] & 30 & 75 & 53 & 47 & 21 & 94 & 88 & 39 \\ \hline \end{array}$$

---

2. 迴圈追蹤（Trace）

• 第 1 輪外層迴圈（此時 $down = 0 < up = 7$）：

• 移動 down：條件為 x[down] <= 30 && down < 7
• $down = 0$：$x[0] = 30 \le 30 \implies down$ 累加為 $1$
• $down = 1$：$x[1] = 75 > 30$（條件不符，停止）
• $\implies down$ 停在 $1$（對應元素 $75$）
• 移動 up：條件為 x[up] > 30
• $up = 7$：$x[7] = 39 > 30 \implies up$ 遞減為 $6$
• $up = 6$：$x[6] = 88 > 30 \implies up$ 遞減為 $5$
• $up = 5$：$x[5] = 94 > 30 \implies up$ 遞減為 $4$
• $up = 4$：$x[4] = 21 \le 30$（條件不符，停止）
• $\implies up$ 停在 $4$（對應元素 $21$）
• 判斷與交換：
• 檢查條件 $down < up$（$1 < 4$，成立）。
• 交換 $x[1]$ 與 $x[4]$（即 $75$ 與 $21$ 對調）。
• 此時陣列狀態為： $x[] = [30, \mathbf{21}, 53, 47, \mathbf{75}, 94, 88, 39]$

---

• 第 2 輪外層迴圈（此時 $down = 1 < up = 4$）：

• 移動 down：條件為 x[down] <= 30 && down < 7
• $down = 1$：$x[1] = 21 \le 30 \implies down$ 累加為 $2$
• $down = 2$：$x[2] = 53 > 30$（條件不符，停止）

核心觀念

1. 最小擴張樹（Minimum Spanning Tree, MST）： 在一個具有 $|V|$ 個節點的連通無向圖形 $G=(V,E)$ 中，擴張樹為包含圖中所有節點且不含任何環路（Cycle）的子圖，其邊數恰好為 $|V|-1$ 條。若該擴張樹的所有邊權重總和為所有可能擴張樹中最小者，即稱為最小擴張樹。
2. Kruskal 演算法： 採用貪婪策略（Greedy Strategy）以邊為導向（Edge-based）建構 MST：

• 將圖中所有邊依權重大小由小至大遞增排序。
• 依序檢視各邊：若加入該邊不會與已選取的邊形成環路（Cycle），則將該邊納入擴張樹；若形成環路則予以捨棄。實作上常搭配互斥集合（Disjoint Set / Union-Find）判定是否成環。
• 重複上述步驟，直到選滿 $|V|-1$ 條邊為止，演算法終止。

---

解題方法

步驟一：確認節點數與目標邊數

圖形頂點集合為 $V = \{0, 1, 2, 3, 4, 5, 6\}$，共有 $|V| = 7$ 個頂點。 因此，最小擴張樹所需的邊數為： $|E_{\text{MST}}| = |V| - 1 = 7 - 1 = 6 \text{ 條邊}$

步驟二：將所有邊按權重由小至大排序

給定邊集合 $E$ 排序後的結果如下：

1. $(0, 5)$，權重 $= 9$
2. $(2, 3)$，權重 $= 11$
3. $(1, 6)$，權重 $= 13$
4. $(1, 2)$，權重 $= 15$
5. $(3, 6)$，權重 $= 17$
6. $(3, 4)$，權重 $= 21$
7. $(4, 6)$，權重 $= 23$
8. $(4, 5)$，權重 $= 24$
9. $(0, 1)$，權重 $= 27$

步驟三：依序檢驗邊並加入樹中（檢查是否成環）

處理順序	候選邊 $(u, v)$	權重	檢查是否成環（連通分量變化）	決策	目前已選邊數
1	$(0, 5)$	$9$	節點 $0, 5$ 尚未連通，無環路。合併為 $\{0, 5\}$	納入	1
2	$(2, 3)$	$11$	節點 $2, 3$ 尚未連通，無環路。合併為 $\{2, 3\}$	納入	2
3	$(1, 6)$	$13$	節點 $1, 6$ 尚未連通，無環路。合併為 $\{1, 6\}$	納入	3
4	$(1, 2)$	$15$	集合 $\{1, 6\}$ 與 $\{2, 3\}$ 連通，合併為 $\{1, 2, 3, 6\}$	納入	4