111 年 國立臺灣大學生物機電系碩士班丙組《資料結構（C）》

核心觀念

本題的核心為區間合併問題（Merge Intervals）與貪婪演算法（Greedy Algorithm）配合排序（Sorting）。

1. 區間重疊判定：
   設兩已依起始點排序之區間為 $A = [s_1, e_1]$ 與 $B = [s_2, e_2]$，其中 $s_1 \le s_2$。
   • 一般數學定義中閉區間重疊條件為 $s_2 \le e_1$。
   • 本題特殊定義：由題目所附之範例 2 可知，$a[0] = (1,3)$ 與 $a[1] = (3,5)$ 輸出為 (1,3), (3,5)，並未合併。這代表端點相交（$s_2 = e_1$）視為不重疊（Non-overlapping），即本題定義的重疊條件為嚴格重疊：
     $s_2 < e_1$
2. 區間合併規則：
   當兩區間重疊（$s_2 < e_1$）時，合併後的新區間起始點為 $s_1$，終點延伸至兩者較大者：
   $\text{Merged Interval} = (s_1, \max(e_1, e_2))$

---

解題方法

1. 邊界檢查：
   若陣列為空或長度 $n \le 0$，直接返回。
2. 依起點遞增排序：
   將所有區間依起點（start）由小到大排序；若起點相同，則可依終點（end）排序。此步驟確保我們只需依序由左向右掃描，每次僅需比較當前合併中的區間與下一個區間。
3. 線性掃描與合併（One-pass Scan）：
   • 設定暫存變數 curr 為排序後的第一個區間 $a[0]$。
   • 從索引 $i = 1$ 遍歷至 $n - 1$：
     • 若重疊（$a[i].\text{start} < \text{curr}.\text{end}$）：
       更新當前區間終點：$\text{curr}.\text{end} = \max(\text{curr}.\text{end}, a[i].\text{end})$。
     • 若不重疊（$a[i].\text{start} \ge \text{curr}.\text{end}$）：
       印出 curr，並將 curr 更新為 $a[i]$。
4. 輸出最後一個區間：
   迴圈結束後，印出最後保留在 curr 中的區間。

---

選項分析

本題為演算法設計與虛擬碼（Pseudocode）撰寫題，無選項。針對題幹給定的兩組測試資料分析如下：

• 範例 1 分析：$a[0] = (1,3), a[1] = (2,4)$
  • 起點已排序，比較 $a[1].\text{start} = 2$ 與 $a[0].\text{end} = 3$。
  • 因 $2 < 3$，兩者重疊，合併為 $(1, \max(3, 4)) = (1, 4)$。
  • 正確輸出：'(1,4)'。
• 範例 2 分析：$a[0] = (1,3), a[1] = (3,5)$
  • 比較 $a[1].\text{start} = 3$ 與 $a[0].\text{end} = 3$。
  • 因 $3 \not< 3$（$a[1].\text{start} \ge a[0].\text{end}$），依題意不予合併，各自獨立輸出。
  • 正確輸出：'(1,3), (3,5)'。

---

解題技巧與常見陷阱

核心觀念

1. 圖著色問題（Graph Coloring Problem / Vertex Coloring）：
   • 給定無向圖 $G = (V, E)$，替每一個頂點 $v \in V$ 分配一個顏色（常以正整數 $1, 2, \dots, k$ 表示），滿足若 $(u, v) \in E$，則 $\text{color}[u] \neq \text{color}[v]$。
   • 使圖中相鄰頂點皆不同色所需的最少顏色數，稱為該圖的色數（Chromatic Number），記為 $\chi(G)$。
2. 計算複雜度（NP-hard）：
   • 題目明確要求「最小化所使用的顏色總數（minimizing the total number of colors used）」，這屬於最佳化問題（Optimization Problem），已被證明為 NP-hard。
   • 貪婪著色演算法（Greedy Coloring）只能找到近似解，不保證使用最少顏色數；若要取得嚴格最小值，必須使用**回溯法（Backtracking）或分支定界法（Branch and Bound）**進行狀態空間樹搜尋，從小到大嘗試顏色數 $m = 1, 2, \dots, |V|$，第一個成功著色的 $m$ 即為 $\chi(G)$。

---

解題方法

本題要求寫出求得「最小顏色數」的虛擬碼，解題切入點如下：

1. 外層疊代（Iterative Deepening Search）：
   • 顏色數 $m$ 從 $1$ 開始遞增到 $|V|$。
   • 只要能在 $m$ 種顏色下成功替圖中所有頂點合法著色，該 $m$ 即為最小顏色數 $\chi(G)$，立即結束並回傳結果。
2. 內層回溯（Backtracking）：
   • 定義輔助函式 isSafe(v, c, color, graph)：檢查頂點 $v$ 著色為 $c$ 時，是否與所有已著色且與其相鄰的頂點衝突。
   • 定義遞迴函式 colorUtil(v, m, color, graph)：
     • 若 $v = |V|$（所有頂點皆已著色），回傳 true。
     • 否則對頂點 $v$ 嘗試所有可用顏色 $c \in \{1, 2, \dots, m\}$：
       • 若 isSafe(v, c, color, graph) 為真，設定 $\text{color}[v] = c$。
       • 遞迴呼叫 colorUtil(v + 1, m, color, graph)。若回傳 true，則成功。
       • 若無法走通，則回溯復原 $\text{color}[v] = 0$。
     • 若 $1 \sim m$ 皆不可行，回傳 false。

---

關鍵程式碼（Pseudocode）

核心觀念

本題考核經典演算法問題：最長迴文子序列（Longest Palindromic Subsequence, 簡稱 LPS）。

1. 子序列（Subsequence）與子字串（Substring）之差異：
   • 子字串（Substring）必須是原字串中連續的字元區段。
   • 子序列（Subsequence）只需保持原字串中的相對先後順序，不要求連續。
2. 最佳子結構（Optimal Substructure）與重疊子問題（Overlapping Subproblems）：
   • 設字串為 $S$，長度為 $n$，索引從 $0$ 到 $n-1$。令 $DP[i][j]$ 表示子字串 $S[i \dots j]$ 中最長迴文子序列的長度。
   • 若首尾字元相同（即 $S[i] = S[j]$）： $$DP[i][j] = DP[i+1][j-1] + 2 \quad (\text{當 } i < j)$$
   • 若首尾字元不同（即 $S[i] \ne S[j]$）： $$DP[i][j] = \max(DP[i+1][j], DP[i][j-1])$$
   • 基本邊界條件（Base Cases）：
     • 單一字元必為長度 1 的迴文：對所有 $i$，有 $DP[i][i] = 1$。
     • 當 $i > j$ 時，$DP[i][j] = 0$。
3. 回溯重構解（Backtracking Reconstruction）：
   • 題目要求找出該最長迴文子序列（即輸出字串本身，而不只是求長度）。
   • 填完動態規劃表格後，從區間 $[0, n-1]$ 出發進行回溯（Backtracking），依據 DP 表格的轉移邏輯向內縮小範圍，即可重構出完整的迴文子序列。

---

解題方法

本題採用動態規劃（Dynamic Programming, DP）結合雙指標回溯法：

1. 第一階段：計算 DP 表格

   • 建立一個大小為 $n \times n$ 的二維陣列 $DP$，初始化所有元素為 0。
   • 依子字串長度 $L$ 從 $1$ 遞增至 $n$（由短區間擴展至長區間），確保計算 $DP[i][j]$ 時所需的子問題 $DP[i+1][j-1]$、$DP[i+1][j]$ 與 $DP[i][j-1]$ 均已計算完成。

2. 第二階段：回溯建構字串

   • 設兩指標 $i = 0, j = n - 1$，最長迴文長度為 $m = DP[0][n-1]$。
   • 建立長度為 $m$ 的字元陣列（或字串）$res$，設定寫入指標 $left = 0, right = m - 1$：
     • 若 $S[i] == S[j]$：此字元為迴文兩端，令 $res[left] = res[right] = S[i]$，隨後 $i \leftarrow i + 1$，$j \leftarrow j - 1$，$left \leftarrow left + 1$，$right \leftarrow right - 1$。
     • 若 $S[i] \ne S[j]$：判斷來自哪一個轉移方向。若 $DP[i+1][j] \ge DP[i][j-1]$，代表較佳解落在區間 $[i+1, j]$，故令 $i \leftarrow i + 1$；否則令 $j \leftarrow j - 1$。
     • 重複此過程直到 $left > right$。

---

演算法虛擬碼（Pseudocode）

核心觀念

本題旨在證明**樹（Tree）**的等價定義之一：若一個連通圖中的每一條邊都是「橋（Bridge / Cut-edge）」，則該圖為一棵樹（即無環且邊數恰為 $N-1$）。
考點涵蓋以下圖論核心定義與性質：

1. 連通圖（Connected Graph）：任兩頂點之間皆存在路徑。
2. 環（Cycle）：起點與終點相同且不重複走過任何邊的簡單閉合路徑。
3. 橋（Bridge / Cut-edge）：圖中一條邊移除後會使連通分量（Connected Components）數量增加的邊。定理指出：一條邊是橋，若且唯若它不包含在任何環中。
4. 樹的特性（Properties of a Tree）：一個具有 $N$ 個頂點的無向連通無環圖，其邊數必定為 $N - 1$。

---

解題方法

本題需證明兩個結論：

1. 該圖沒有環（No cycles）。
2. 該圖的邊數為 $N - 1$（$N - 1$ edges）。

最佳切入策略是：

• 先以**反證法（Proof by Contradiction）**證明「圖中不存在任何環」。
• 再利用「連通且無環圖即為樹」的性質，藉由**數學歸納法（Mathematical Induction）**推導出邊數必為 $N - 1$。

---

證明推導

設 $G = (V, E)$ 是一個具有 $N$ 個節點的連通圖（$|V| = N$），且滿足性質：移除任意邊 $e \in E$ 後，所得圖 $G - e$ 均不連通（即每條邊皆為橋）。

第一部分：證明圖中無環（No cycles）

採用反證法：

1. 假設 $G$ 中存在至少一個環 $C = (v_1, v_2, \dots, v_k, v_1)$，其中 $k \ge 3$。
2. 考慮該環上的任一條邊 $e = (v_1, v_2) \in E$。
3. 當我們從 $G$ 中移除邊 $e$ 得到子圖 $G' = G - e$：
   • 由於原圖 $G$ 是連通的，對任意兩點 $u, w \in V$，在 $G$ 中必定存在一條連接 $u$ 與 $w$ 的路徑 $P$。
   • 若路徑 $P$ 未使用到邊 $e$，則 $P$ 在 $G'$ 中依然完整存在。
   • 若路徑 $P$ 包含邊 $e = (v_1, v_2)$，我們可將經過邊 $(v_1, v_2)$ 的這一步驟，替換為環 $C$ 中的另一側路徑：
     $v_1 - v_k - v_{k-1} - \dots - v_2$
     此替代路徑不經過邊 $e$，因此在 $G'$ 中依然連通。
4. 這表示移除邊 $e$ 後，$G'$ 中的任兩頂點之間仍然存在路徑，即 $G'$ 依然是連通圖。
5. 此結論與題目給定的條件「移除任意邊皆會使圖不連通」產生矛盾。
6. 因此，假設不成立，$G$ 必定不存在任何環。

---

核心觀念

1. 2-3 樹（2-3 Tree）定義：

   • 2-3 樹是一種自平衡搜尋樹（Self-balancing Search Tree），為 B-Tree 的特例（即 order 為 3 的 B-tree）。
   • 節點類型分為兩種：
     • 2-node：包含 1 個資料鍵值（Key）及 2 個子節點指標（Child pointers）。
     • 3-node：包含 2 個資料鍵值及 3 個子節點指標。
   • 完全平衡性（Perfect Balance）：所有葉節點（Leaf nodes）均位於同一深度（即「從根節點到任一空鏈結（null link / leaf）的路徑長度皆相等」）。

2. 核心機制：由下而上生長（Bottom-up Growth）：

   • 與一般二元搜尋樹（BST）「直接在最底層新增葉節點向下生長」不同，2-3 樹的新增與刪除操作透過**節點分裂（Split）與節點合併（Merge / Borrow）**來維持高度平衡。
   • 樹的高度只有在根節點分裂時才會加 1，因此所有葉節點的深度同步增加，永遠保持在同一層。

---

解題方法

要完整解釋 2-3 樹如何達成「從 root 到 null link 路徑等長」的性質，需從**插入（Insertion）與刪除（Deletion）**的結構維護機制來說明：

1. 插入運作（Insertion）與向上分裂（Bottom-up Splitting）

當插入新鍵值時，一律先找到最底層的葉節點進行插入：

• 情境一：插入至 2-node
  • 2-node 尚有容納空間，直接將鍵值加入，使該節點吸收成為 3-node。
  • 高度變化：整棵樹的結構高度未變，所有葉節點深度保持不變。
• 情境二：插入至 3-node（產生暫時的 4-node）
  • 3-node 原已有 2 個鍵值，加入新鍵值後暫時成為擁有 3 個鍵值（設為 $k_{\min} < k_{\text{mid}} < k_{\max}$）的 4-node。
  • 節點分裂（Split）：將中間值 $k_{\text{mid}}$ 往上推至父節點（Parent），$k_{\min}$ 與 $k_{\max}$ 分裂為兩個獨立的 2-node。
  • 向上傳播（Upward Propagation）：若父節點亦為 3-node，則持續向上分裂傳遞；此過程不向下增加葉節點深度。
  • 根節點分裂（Root Splitting）：若分裂一路傳播至根節點（Root），此時根節點分裂為兩個節點，並由推上去的中間值建立新的根節點。
  • 高度變化：此時樹高整齊增加 1，因為新的根節點成為整棵樹唯一的頂端，所有舊的葉節點距離新根節點的路徑同步加 1，路徑長度依舊處處相等。

核心觀念

1. 二元樹高度（Height）的定義：

   • 樹的高度通常有兩種主流定義：
     • 以「節點數（Number of Nodes）」定義（常見於多數教科書如 Horowitz 與一般 C 語言實作）：
       • 空樹（Empty tree）的高度為 $0$。
       • 只有單一根節點的樹，高度為 $1$。
       • 遞迴關係式為： $$\text{Height}(T) = 1 + \max(\text{Height}(T\to\text{left}), \text{Height}(T\to\text{right}))$$
     • 以「邊數（Number of Edges）」定義（常見於 CLRS 等演算法聖經）：
       • 空樹的高度定義為 $-1$。
       • 單一根節點的高度為 $0$。
   • 考試若無特別指明，以**節點數定義（空樹高度為 $0$，單一節點為 $1$）**最為直覺且為學界經典實作；本解亦針對邊數定義提供備註說明。

2. 後序走訪與分治法（Post-order Traversal & Divide-and-Conquer）：

   • 計算樹高的過程本質上是後序走訪（Post-order Traversal）：必須先分別算出左子樹與右子樹的高度，再取兩者最大值加 $1$ 回傳給母節點。

---

解題方法

採用**遞迴（Recursion）**方式實作：

1. 基底情況（Base Case）：
   • 若輸入的節點為空指標（node == NULL），表示這是一棵空樹，終止遞迴並回傳 0。
2. 遞迴步驟（Recursive Step）：
   • 遞迴呼叫計算左子樹的高度：left_height = getHeight(node->left)。
   • 遞迴呼叫計算右子樹的高度：right_height = getHeight(node->right)。
   • 找出兩者中的較大值，加上當前節點本身貢獻的 $1$，作為本樹的高度回傳： $$\text{Height} = 1 + \max(\text{left\_height}, \text{right\_height})$$

---

關鍵程式碼實作（C 語言）

假設二元樹節點的結構定義如下：

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

計算高度的遞迴函式：