111 年 國立中央大學資訊工程學系碩士班《資料結構與演算法》

核心觀念

本題考驗運算式表示法轉換（Infix to Postfix Conversion）與堆疊（Stack）資料結構應用，核心觀念包含：

1. Shunting-yard 演算法：利用堆疊暫存運算子（Operators）與括號（Parentheses）進行中序（Infix）轉後序（Postfix）的處理過程。
2. 運算子優先權與結合律（Precedence & Associativity）：
   • 括號 ()：當讀取到左括號 ( 時，優先權最高，直接壓入堆疊；但在堆疊內部，( 的優先權視為最低，不會被後續的一般運算子彈出。
   • 乘除 *, /：優先權高於加減，同階採左至右結合（Left-to-Right）。
   • 加減 +, -：優先權低於乘除，同階採左至右結合（Left-to-Right）。
3. 堆疊最大深度分析：追蹤轉換過程中，堆疊內同時存在的 Token（運算子與括號）數量的上限。
4. 後序轉中序（Postfix to Infix Conversion）：利用運算元堆疊，由左至右讀取後序運算式，遇到運算子即彈出頂端兩個運算元結合並加括號，還原為標準中序運算式。

解題方法

1. 中序轉後序堆疊運作規則

• 運算元（Operand）：直接輸出至後序運算式。
• 左括號 (：直接推入（Push）運算子堆疊。
• 運算子（Operator）：若堆疊頂端運算子的優先權大於或等於當前讀入運算子（同優先權依左結合律處理），則將堆疊頂端運算子彈出（Pop）並輸出；重複此檢查直到堆疊頂端優先權較低或為 (，最後將當前運算子推入堆疊。
• 右括號 )：不斷彈出堆疊頂端運算子並輸出，直到遇到 ( 為止，並將 ( 彈出丟棄。

2. 後序轉中序堆疊運作規則

• 由左至右掃描後序運算式：
  • 遇到運算元：推入運算元堆疊。
  • 遇到二元運算子 $op$：從堆疊先後彈出 $y$（右運算元）與 $x$（左運算元），組合成 $(x \ op \ y)$ 後推回堆疊。

選項分析

(A) 正確

分析中序運算式 $a*(b+c/d)*(e-f)+g$ 轉後序的堆疊狀態變化：

核心觀念
本題考驗演算法設計典範（Algorithm Design Paradigms）的核心定義與運作機制，主要涵蓋以下四項重點：

1. 動態規劃（Dynamic Programming, DP）：利用「記憶化（Memoization）」或「填表法（Tabulation）」儲存子問題的解，避免重複計算導致的遞迴爆炸（Recursive Explosion）。
2. 重疊子問題（Overlapping Subproblems）：若遞迴樹中存在大量重複計算的子問題且未加適當處理，時間複雜度常呈指數級暴增。
3. 貪婪演算法（Greedy Algorithm）：具備「貪婪選擇性質（Greedy-choice Property）」，在每一步驟中皆做出當下看起來最佳的局部最佳選擇（Locally Optimal Decision）。
4. 分治法（Divide and Conquer）：標準架構涵蓋 Divide（分）、Conquer（治）、Combine（合）。其中真正進行「遞迴求解」的是 Conquer（治） 階段。

解題方法
本題屬於經典觀念判斷題，解題切入點在於對各演算法概念的標準定義進行比對與驗證：

1. 檢視動態規劃是否能將重複子問題的時間複雜度從指數級降低至多項式級，藉此避免遞迴爆炸。
2. 評估未經記憶化處理的重疊遞迴呼叫對時間複雜度的影響。
3. 確認貪婪演算法的決策模式。
4. 剖析分治法三個階段各自對應的演算法行為，釐清遞迴執行的時間點。

選項分析

• (A) 正確
  動態規劃（Dynamic Programming） 的核心精神在於解決具有「重疊子問題（Overlapping Subproblems）」的遞迴問題。若採用傳統遞迴，相同子問題會被重複計算多次，造成計算量隨問題規模呈指數型暴增（即 Recursive Explosion）。DP 透過儲存子問題的解答（備忘錄法或填表法），使每個子問題僅需計算一次，成功避免了遞迴爆炸。

核心觀念

本題評測考生對 AVL Tree（高度平衡二元搜尋樹） 之核心性質與推導的理解，涵蓋三大要點：

1. 平衡條件（Balance Property）：任意節點之左右子樹高度差絕對值不可超過 1，即平衡因子（Balance Factor）$BF = h_L - h_R \in \{-1, 0, 1\}$。
2. 重平衡旋轉時間複雜度（Rebalancing Complexity）：
   • 插入（Insertion）：至多進行 1 次單旋轉或雙旋轉，時間複雜度為 $O(1)$。
   • 刪除（Deletion）：可能引發向根節點傳遞的連鎖旋轉（Cascading Rotations），最多需 $O(\log n)$ 次旋轉，時間複雜度為 $O(\log n)$。
3. 樹高與最少節點數關係（Fibonacci Tree 結構）：高度為 $h$ 的 AVL 樹，其最少節點數符合費氏數列（Fibonacci Sequence）遞迴關係，構成節點數的 下界（Lower Bound）。

解題方法

本題要求找出 錯誤（false） 的選項。解題切入點如下：

1. 複雜度分析：區分「插入」與「刪除」元素後恢復平衡所需的旋轉次數與連鎖效應（Cascading Effect）。
2. 數學公式證明：推導高度為 $h$ 的最疏鬆 AVL 樹（Fibonacci Tree）之最小節點數遞迴式 $N(h) = N(h-1) + N(h-2) + 1$，檢驗節點數 $n$ 與費氏數列 $F_{h+2}$ 的不等式方向。
3. 邏輯與邊界檢查：對照 AVL 樹平衡因子的精準數學定義，檢驗不等式符號與邊界值（如 $BF = 1$）。

選項分析

• (A) 正確（非本題所求之錯誤選項）

  • 原文：The time complexity of rebalancing rotation after deleting an element is O(log n).
  • 解析：在 AVL 樹中刪除一個節點後，執行旋轉重平衡可能會使該子樹的高度減少 1，進而打破父節點或更上層祖先節點的平衡。最壞情況下，此不平衡會一路向上傳遞至根節點（稱為 Cascading Rotations），最多需要進行 $O(\log n)$ 次旋轉。由於每次旋轉僅需 $O(1)$ 時間，故刪除後旋轉重平衡的總時間複雜度為 $O(\log n)$。故本敘述正確（True）。

• (B) 錯誤（為本題答案）

  • 原文：The time complexity of rebalancing rotation after insertion is O(log n).
  • 解析：在 AVL 樹中插入一個節點後，至多只需要進行 1 次旋轉（單旋轉或雙旋轉），即可將該子樹的高度恢復至插入前的高度，不會將不平衡繼續向上傳遞。因此，插入後進行旋轉重平衡的時間複雜度應為 $O(1)$。將其標示為 $O(\log n)$ 未能反映 $O(1)$ 的精準旋轉次數特性（考題常以此對比插入 $O(1)$ 與刪除 $O(\log n)$ 之差異）。故本敘述錯誤（False）。

核心觀念

本題考驗**高度偏向左傾樹（Height-Biased Leftist Tree, HBLT）**的定義、結構性質以及核心操作的時間複雜度。

1. $s(x)$ 的定義（Shortest distance / 最右路徑長度）：
   對於樹中的任意節點 $x$，定義 $s(x)$ 為從節點 $x$ 下降至外部節點（external node，即空指標 null）的最短路徑長度。

   • 若 $x$ 為外部節點，則 $s(\text{null}) = 0$。
   • 若 $x$ 為內部節點（internal node），則：
     $s(x) = \min(s(\text{left}(x)), s(\text{right}(x))) + 1$

2. HBLT 的結構性質：
   對於 HBLT 中的每一個內部節點 $x$，皆滿足左子樹的最短距離不小於右子樹的最短距離：
   $s(\text{left}(x)) \ge s(\text{right}(x))$
   由此可導出：
   $s(x) = s(\text{right}(x)) + 1$
   這意味著從根節點 $x$ 出發到達外部節點的最短路徑，必然沿著**最右路徑（rightmost path）**延伸。

3. 最右路徑長度的上界定理：
   若以 $x$ 為根節點的子樹包含 $w(x)$ 個內部節點，則該子樹至少包含 $2^{s(x)} - 1$ 個內部節點：
   $w(x) \ge 2^{s(x)} - 1 \implies 2^{s(x)} \le w(x) + 1 \implies s(x) \le \log_2(w(x) + 1)$
   注意：此定理僅保證「最右路徑長度（即 $s(x)$）」不超過 $\log_2(w(x)+1)$，並不保證最左路徑或樹的高度滿足對數限制。

解題方法

本題要求找出**敘述錯誤（false）**的選項。切入點如下：

1. 分析結構性質（選項 A、B）：
   檢查對數限制 $\log_2(w(x)+1)$ 適用於何種路徑。HBLT 僅限制「最右路徑」的長度為 $O(\log w(x))$；對於「最左路徑」與「樹高（Height）」，完全沒有對數上界的約束。極端情況下（如完全左偏樹），最左路徑長度與樹高均可達 $O(w(x))$。
2. 分析操作複雜度（選項 C、D）：
   • Melding（合併）：HBLT 的合併過程僅沿著兩棵樹的「最右路徑」進行比對與重組。因為最右路徑長度至多為 $O(\log n)$，故合併兩棵大小為 $n$ 的 HBLT 所需時間為 $O(\log n)$。
   • Remove Min（刪除最小值）：刪除根節點後，將左右兩棵子樹進行 Melding 操作。時間複雜度由 Melding 決定，亦為 $O(\log n)$。

選項分析

核心觀念

本題考驗**遞迴函式（Recursive Functions）**的追蹤、收斂性（Terminability）分析，以及基本數論與演算法觀念。具體包含以下三大重點：

1. 遞迴終止性與不變量（Parity Invariant）分析：判斷遞迴呼叫是否具備正確的基底條件（Base Case）以及參數傳遞能否在有限步內收斂至終止條件。
2. 歐幾里得演算法（Euclidean Algorithm / 輾轉相除法）與程式語法細節：理解最大公因數（GCD）遞迴求法，並注意虛擬碼或 C 語言中逗號運算子（Comma Operator）與遞迴呼叫的差異。
3. 遞迴樹追蹤與動態規劃思想：利用樹狀展開或自底向上（Bottom-up）的表格繪製，精確計算遞迴函式的數值輸出。

解題方法

1. 函式 $F1(x)$ 之終止性推導

給定遞迴函式：

int F1(int x) {
    if (x % 2 == 0)
        return x / 2;
    else
        return F1(F1(3 * x + 2));
}

• 分析輸入 $x$ 為奇數的情況：
  若 $x$ 為正奇數，可將 $x$ 表示為 $x = 2k + 1$（其中 $k \ge 0$ 為整數）。
  代入內層表達式 $3x + 2$：
  $3x + 2 = 3(2k + 1) + 2 = 6k + 5 = 2(3k + 2) + 1$
  因為 $3k + 2$ 為整數，故 $3x + 2$ 必定亦為奇數。
• 無窮遞迴展開：
  當 $x$ 為奇數時，$F1(x)$ 會優先評估內層呼叫 $F1(3x + 2)$。由於 $3x + 2$ 仍為奇數，評估 $F1(3x + 2)$ 又會再度觸發更內層的呼叫 $F1(3(3x + 2) + 2)$。此過程中傳入內層函式的參數永遠維持為奇數，永遠無法到達 x is even（傳入偶數）的終止條件。因此對於任何正奇數 $x$，內層遞迴呼叫皆無法終止，導致程式進入無窮遞迴（Infinite Recursion）與堆疊溢位（Stack Overflow）。

2. 函式 $F2(x, y)$ 之數值追蹤

給定函式：

int F2(int x, int y) {
    if (y == 0)
        return x;
    else
        return (y, x % y);
}

• 情況 A：依字面 C/C++ 逗號運算子語法
  在 C 語言中，(y, x % y) 屬於逗號運算子（Comma Operator），會先評估左側 $y$，再評估右側 $x \bmod y$，最終返回右側表達式的值。
  當 $x = 21, y = 12$ 時，因 $y \neq 0$，執行 return (12, 21 % 12)。
  $21 \bmod 12 = 9$，故函式直接回傳 $9$。
• 情況 B：若為印製印漏函式名之輾轉相除法 return F2(y, x % y);
  若補回遞迴呼叫 $F2$，此即經典求最大公因數 $\gcd(x, y)$ 的歐幾里得演算法：
  1. $F2(21, 12) \rightarrow F2(12, 21 \bmod 12) = F2(12, 9)$
  2. $F2(12, 9) \rightarrow F2(9, 12 \bmod 9) = F2(9, 3)$
  3. $F2(9, 3) \rightarrow F2(3, 9 \bmod 3) = F2(3, 0)$

核心觀念

本題考驗 C / C++ 語言中二維陣列（2D Array）與指標（Pointer）的轉換語法與指標運算（Pointer Arithmetic）。

在 C / C++ 規範中，二維陣列 int arr[M][N] 在記憶體中是以**列為主順序（Row-Major Order）**連續存放。陣列名稱、指標與下標運算子 [] 之間存在以下基本轉換公式：

1. 下標運算子與指標解參考（Dereference）等價公式：
   $E1[E2] \equiv *(E1 + E2)$
   因此，對於二維陣列元素 arr[i][j]，標準指標展開式為：
   $arr[i][j] \equiv *(*(arr + i) + j)$

2. 一維記憶體連續定址（Flattening）公式：
   陣列名稱 arr 降級（Decay）後的 *arr 代表指向第一個元素 arr[0][0] 的指標（型態為 int*）。
   第 $i$ 列第 $j$ 行的元素 arr[i][j] 在連續記憶體中的一維偏移量（Offset）為 $i \times N + j$ 個元素空間，其等價指標表示法為：
   $arr[i][j] \equiv *(*arr + i \times N + j)$

解題方法

已知二維陣列宣告為 int arr[5][5]（列數 $M = 5$，行數 $N = 5$），目標為找出與 arr[2][3] 等價的表達式（即列索引 $i = 2$、行索引 $j = 3$）。

1. 套用二維指標標準展開：
   將 $i = 2, j = 3$ 代入二維指標公式 $arr[i][j] \equiv *(*(arr + i) + j)$：
   $arr[2][3] \equiv *(*(arr + 2) + 3)$

2. 套用一維記憶體偏移量計算：
   陣列每列長度 $N = 5$。計算 $i = 2, j = 3$ 的一維連續記憶體偏移量：
   $\text{Offset} = 2 \times 5 + 3 = 13$
   將偏移量代入一維指標公式 $arr[i][j] \equiv *(*arr + \text{Offset})$：
   $arr[2][3] \equiv *(*arr + 13)$

選項分析

• (A) *(*arr+13)：正確。
  • arr 型態為 int[5][5]，在表達式中降級為指向列陣列的指標（型態為 int (*)[5]）。
  • *arr 解參考得到第一列開頭，進一步降級為指向第一個整數 arr[0][0] 的指標（型態為 int*）。

核心觀念

本題考驗常見抽象資料型態（Abstract Data Types, ADT）的運作特性及其輸出序列的可行性分析，涵蓋以下核心概念：

1. 佇列（Queue）：遵循「先進先出」（First-In, First-Out, FIFO）原則。若元素入隊順序為 $m_1, m_2, m_3, m_4, m_5$，其出隊順序必然為 $m_1, m_2, m_3, m_4, m_5$。
2. 堆疊（Stack）：遵循「後進先出」（Last-In, First-Out, LIFO）原則。透過交錯執行進棧（Push）與出棧（Pop）操作，可產生多種有效的堆疊排列（Stack Permutation）。
3. 最大堆積（Max Heap）：屬於優先佇列（Priority Queue）的一種實現方式，每次取出的元素皆為目前堆積中優先權（鍵值 Key）最大者。若適當設定元素的鍵值，並配合交錯的插入（Insert）與取出最大值（Extract-Max）操作，可靈活調整輸出順序。

解題方法

裝置 A 依序傳送訊息 $m_1, m_2, m_3, m_4, m_5$ 至黑盒子中。要判斷黑盒子是否可能為特定資料結構，需檢查是否存在一組合法的操作序列（包含進步時機與取出時機），使得裝置 B 接收到的輸出順序成立。

1. 佇列輸出判斷：純佇列在無優先權參與的情況下，僅能產生唯一的 FIFO 序列 $m_1, m_2, m_3, m_4, m_5$。但若輸出序列為 FIFO，黑盒子並不「必然」為佇列，因為其他結構（如堆疊）在特定操作下亦能產生相同的輸出。
2. 堆疊輸出判斷：針對目標輸出序列，驗證是否符合 Stack 操作規範（元素入棧順序固定的前提下，已 Push 的元素若未 Pop，其相對順序必須滿足 LIFO 限制）。
3. 最大堆積輸出判斷：為各訊息賦予合適的鍵值 $k_1, k_2, k_3, k_4, k_5$，驗證每次取出元素時，該元素是否為當時堆積內鍵值最高者。

選項分析

• (A) 錯誤（為本題應選答案）
  當裝置 B 依序收到 $m_1, m_2, m_3, m_4, m_5$ 時，黑盒子不一定必須是佇列（Queue）。
  若黑盒子為堆疊（Stack），只需對每個訊息採取「進棧後立即出棧」的操作流程：
  $\text{Push}(m_1) \rightarrow \text{Pop}() \rightarrow m_1$
  $\text{Push}(m_2) \rightarrow \text{Pop}() \rightarrow m_2$
  $\text{Push}(m_3) \rightarrow \text{Pop}() \rightarrow m_3$
  $\text{Push}(m_4) \rightarrow \text{Pop}() \rightarrow m_4$
  $\text{Push}(m_5) \rightarrow \text{Pop}() \rightarrow m_5$
  此時堆疊同樣能輸出 $m_1, m_2, m_3, m_4, m_5$ 序列。因此敘述中稱「黑盒子**必然（must）**為佇列」係屬錯誤。

• (B) 正確
  當裝置 B 依序收到 $m_3, m_2, m_1, m_4, m_5$ 時，黑盒子可以是一個堆疊（Stack）。
  具體操作順序如下：

核心觀念

1. 雜湊表與開放定址法（Open Addressing - Linear Probing）：

   • 當發生碰撞（Collision）時，線性探測（Linear Probing）依照探測函數 $h(k, i) = (h(k) + i) \bmod m$ 依次向後尋找下一個空槽位放置。
   • 本題未特別指明主雜湊函數（Primary Hash Function）時，預設使用標準的餘數法：$h(k) = k \bmod 17$。

2. 線性探測的刪除機制（Deletion with Shift / Rehashing）：

   • 當從雜湊表中刪除鍵值 $k$ 且不採用墓碑（Tombstone / Lazy Deletion）標記時，該槽位會留下一道「空隙（Gap）」。
   • 為維護後續搜尋路徑的正確性，必須對後續連續的同集區（Cluster）元素進行位移重置。
   • 對於空隙後的每一個元素，若該空隙部位落於該元素的探測路徑（即主雜湊值 $h(k)$ 至當前槽位）上，該元素即可向前移入空隙，並將釋出的新空隙繼續交由後續元素檢視，直到遇見原本即為空的槽位為止。

解題方法與推導步驟

步驟一：建構初始雜湊表

雜湊表大小 $m = 17$，槽位索引為 $0 \sim 16$。
依序將集合 $\{23, 12, 34, 46, 28, 11, 6, 7, 0, 33, 13, 45\}$ 插入雜湊表：

1. $k = 23$：$h(23) = 23 \bmod 17 = 6$。槽位 6 為空，放入 23。
2. $k = 12$：$h(12) = 12 \bmod 17 = 12$。槽位 12 為空，放入 12。
3. $k = 34$：$h(34) = 34 \bmod 17 = 0$。槽位 0 為空，放入 34。
4. $k = 46$：$h(46) = 46 \bmod 17 = 12$（與 12 碰撞）。
   • $i=1 \Rightarrow (12+1) \bmod 17 = 13$。槽位 13 為空，放入 46。
5. $k = 28$：$h(28) = 28 \bmod 17 = 11$。槽位 11 為空，放入 28。
6. $k = 11$：$h(11) = 11 \bmod 17 = 11$（與 28 碰撞）。
   • $i=1 \Rightarrow 12$（佔用）；$i=2 \Rightarrow 13$（佔用）；$i=3 \Rightarrow 14$（空）。放入 11 於槽位 14。
7. $k = 6$：$h(6) = 6 \bmod 17 = 6$（與 23 碰撞）。
   • $i=1 \Rightarrow 7$。槽位 7 為空，放入 6。
8. $k = 7$：$h(7) = 7 \bmod 17 = 7$（與 6 碰撞）。
   • $i=1 \Rightarrow 8$。槽位 8 為空，放入 7。
9. $k = 0$：$h(0) = 0 \bmod 17 = 0$（與 34 碰撞）。
   • $i=1 \Rightarrow 1$。槽位 1 為空，放入 0。
10. $k = 33$：$h(33) = 33 \bmod 17 = 16$。槽位 16 為空，放入 33。
11. $k = 13$：$h(13) = 13 \bmod 17 = 13$（與 46 碰撞）。
    • $i=1 \Rightarrow 14$（佔用）；$i=2 \Rightarrow 15$（空）。放入 13 於槽位 15。
12. $k = 45$：$h(45) = 45 \bmod 17 = 11$（與 28 碰撞）。
    • 探測路徑：$11 \rightarrow 12 \rightarrow 13 \rightarrow 14 \rightarrow 15 \rightarrow 16 \rightarrow 0 \rightarrow 1 \rightarrow 2$（空）。放入 45 於槽位 2。

核心觀念

本題考查單向鏈結串列（Singly Linked List）的迭代反轉演算法（Iterative Reversal Algorithm），屬於經典的三指標追蹤法（Three-Pointer Approach）。

演算法主要維護三個關鍵指標變數：

1. P（Previous）：指向當前處理節點的前一個節點，初始值為 NULL。
2. C（Current）：指向當前正在處理的節點，初始值為 *Href（即原串列的頭指標 head）。
3. N（Next）：用於暫存當前節點的原下一個節點，防止指標轉向後遺失後續串列的位址，初始值為 NULL。

此外，參數 NPtr* Href 為指向頭指標的雙重指標（Pointer to Pointer），允許函式在結束前直接修改主程式中的 head 指標值。

解題方法

要實現單向鏈結串列的原地反轉（In-place Reversal），需要在走訪串列的過程中逐一將節點的 next 指向其前一個節點。

完整推導步驟如下：

1. 確定迴圈終止條件——空格 (1)：
   迴圈需持續執行至走訪完所有節點為止。當 C 尚未抵達串列末端（即 C != NULL）時繼續執行；當 C == NULL 時表示所有節點的指標皆已完成轉向。
   因此，空格 (1) 應填入：C != NULL

2. 進行指標反轉——空格 (2)：
   在將 N 暫存為 C->next 後，需將當前節點 C 的 next 指標改指向前一個節點 P，即執行 C->next = P;。
   因此，空格 (2) 應填入：P

3. 推進指標進行下一次疊代：

   • P = C;：將 P 移動到當前節點 C 的位置，作為下一個節點的前置節點。
   • C = N;：將 C 移動到剛才暫存的下一個節點 N。

4. 更新頭指標——空格 (3)：
   當 while 迴圈結束時，C 的值為 NULL，而 P 正好指向原串列的最後一個節點（即反轉後新串列的頭節點）。因此，必須將新頭節點位址賦值給 *Href，即 *Href = P;。
   因此，空格 (3) 應填入：*Href = P;

完整 C 語言實作程式碼

核心觀念

AOE 網路以頂點表示事件、以有向邊表示活動，邊上的數字是活動所需時間。count 欄位表示該頂點的直接前驅數，也就是入度；關鍵路徑則是起點到終點之間總工期最長的路徑。

事件最早發生時間以所有前驅路徑中的最大值計算；事件最晚發生時間則由終點往回，以所有後續活動允許時間中的最小值計算：

其中 $d(u,v)$ 是活動 $(u,v)$ 的時間。

解題方法

由圖可讀出起點為頂點 $0$、終點為頂點 $8$，各頂點的鄰接資料（「相鄰頂點，活動時間」）為：

• $0\to1(5),\ 0\to2(4),\ 0\to3(5)$
• $1\to4(1)$
• $2\to4(3)$
• $3\to5(2)$
• $4\to6(9),\ 4\to7(7)$
• $5\to7(5)$
• $6\to8(2)$
• $7\to8(5)$

逐一計算各頂點的直接前驅數，得到 count 序列：

例如，頂點 $4$ 有頂點 $1、2$ 兩個前驅；頂點 $5$ 只有頂點 $3$ 一個前驅。

由起點往後計算最早發生時間：

核心觀念

本題考查經典**比較排序演算法（Comparison-based Sorting Algorithms）**的時間複雜度（最佳、平均、最壞狀況）與額外空間複雜度（Space Complexity / Auxiliary Space）。考生的核心任務為精確掌握以下五種排序演算法的性能指標：

1. 插入排序法（Insertion Sort）
2. 合併排序法（Merge Sort）
3. 快速排序法（Quick Sort）
4. 堆積排序法（Heap Sort）
5. 氣泡排序法（Bubble Sort）

解題方法

比較排序演算法的各項複雜度與特性整理如下表：

根據此對照表即可精準分析各選項。

選項分析

• (A) 正確

  • 時間複雜度分析：
    • 最佳狀況（Best Case）：當輸入陣列已呈升冪排序時，每次插入新元素只需比較 $1$ 次即可確認位置，總比較次數為 $n-1$ 次，時間複雜度為 $O(n)$。
    • 最壞狀況（Worst Case）：當輸入陣列呈降冪（逆序）排序時，第 $i$ 個元素需與前方 $i-1$ 個元素逐一比較並後移，總比較次數為 $\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}$，時間複雜度為 $O(n^2)$。
    • 平均狀況（Average Case）：平均而言，第 $i$ 個元素需向前移動 $\frac{i}{2}$ 次，總時間複雜度為 $O(n^2)$。
  • 故本選項敘述完全正確。

• (B) 正確

  • 時間複雜度分析：
    • Merge Sort 採用分治法（Divide and Conquer），其遞迴關係式為 $T(n) = 2T(n/2) + \Theta(n)$。

核心觀念

本題考查計算複雜度理論（Complexity Theory）中關於 $P$、$NP$、$NP\text{-hard}$ 與 $NP\text{-Complete}$（NPC） 的經典定義、多項式時間規約（Polynomial-time Reduction）的傳遞性，以及經典未解問題 $P \text{ vs } NP$ 的概念。

1. $P$ 類別（Polynomial Time）：可由「確定性演算法」（Deterministic Algorithm）在最壞情況下以多項式時間 $O(n^k)$ 求解的判定問題集合。
2. $NP$ 類別（Nondeterministic Polynomial Time）：可由「非確定性演算法」（Non-deterministic Algorithm）在最壞情況下以多項式時間 $O(n^k)$ 求解（或可在多項式時間內驗證其解）的判定問題集合。
3. $NP\text{-hard}$ 類別：若對所有 $Y \in NP$，均滿足 $Y \le_p X$（$Y$ 可多項式時間規約至 $X$），則稱問題 $X$ 為 $NP\text{-hard}$。注意 $NP\text{-hard}$ 問題本身不一定要屬於 $NP$。
4. $NP\text{-Complete}$ (NPC) 類別：問題 $X$ 若同時滿足以下兩個條件，則定義為 NPC 問題：
   • (1) $X \in NP$
   • (2) $X \in NP\text{-hard}$
5. 多項式時間規約（$\le_p$）之傳遞性：若 $A \le_p B$ 且 $B \le_p C$，則 $A \le_p C$。

解題方法

依據複雜度類別的嚴格數學定義與計算理論公式進行判斷：

1. 未解問題的判定：目前學界尚未證明 $P \neq NP$ 或 $P = NP$，凡聲稱「已證明（proved）」無多項式時間確定性演算法可解 NPC 問題的敘述皆不成立。
2. 規約方向與歸屬判定：
   • 欲證明 $X$ 為 $NP\text{-hard}$，必須將「已知為 $NP\text{-hard}$ 的問題 $A$」規約至 $X$（即 $A \le_p X$）。
   • 欲證明 $X$ 為 $NPC$，必須同時滿足 $X \in NP$ 與 $X \in NP\text{-hard}$。
3. $NP$ 的基本定義：直接根據非確定性演算法於多項式時間內可求解進行歸屬認定。

選項分析

• (A) 錯誤。
  至今計算機科學界尚未證明是否存在確定性多項式時間演算法可以解決 NPC 問題（即著名的 $P \text{ vs } NP$ 開放問題）。雖然理論學界普遍猜測 $P \neq NP$，但該結論至今尚未被數學證明。

核心觀念

本題考查兩種最小生成樹（Minimum Spanning Tree, MST）演算法：

• Prim 演算法：從一個頂點開始，逐步加入連接目前頂點集合與外部頂點集合的最小權重邊。
• Kruskal 演算法：按照邊的權重由小到大考慮，若加入該邊不會形成環，就將其加入生成樹。

設圖中：

• $n=|V|$：頂點數
• $m=|E|$：邊數

生成樹必須滿足：

Kruskal 演算法的核心判斷是：

若邊 $(u,v)$ 的兩端點目前位於不同連通元件，加入此邊不會形成環；若兩端點位於同一連通元件，加入此邊會形成環。

此判斷通常使用 Disjoint Set Union（DSU，互斥集合）完成，並搭配 find 與 union 操作。

解題方法

Kruskal 演算法先將所有邊依權重遞增排序，再依序處理每一條邊：

1. 初始時每個頂點各自形成一棵樹。
2. 每次選擇尚未處理且權重最小的邊 $(u,v)$。
3. 若 $u$、$v$ 屬於不同的樹，加入該邊並合併兩棵樹。
4. 若 $u$、$v$ 已在同一棵樹，捨棄該邊，以避免形成環。
5. 當選出的邊數達到 $n-1$ 時停止。

這與 Prim 演算法的輸出格式一致，皆以 $T$ 儲存答案，最後輸出 $M=(V,T)$。

Kruskal's MST Algorithm

Algorithm: Kruskal's MST algorithm

Input:
    A weighted connected undirected graph G=(V, E),
    where |V|=n

Output:
    The MST M=(V, T) with the minimal total weight,
    where |T|=n-1

1:  T ← φ
2:  F ← {{v} | v∈V}
3:  sort all edges in E in nondecreasing order of weight
4:  while |T| < n-1 do
5:      select an edge (u, v)∈E with the minimal weight
        among the unselected edges
        such that u and v belong to different trees in F
6:      T ← T∪{(u, v)}
7:      merge the two trees containing u and v in F
8:  return M=(V, T)

其中第 5 行可使用 DSU 實作：

if find(u) ≠ find(v) then
    T ← T∪{(u, v)}
    union(u, v)

核心觀念

本題屬於經典的**動態規劃（Dynamic Programming, DP）**問題，源自 Introduction to Algorithms (CLRS) 演算法經典範例。

解答本題需要掌握以下核心觀念與定義：

1. 最佳子結構（Optimal Substructure）：若到達第 $j$ 個旅館的最佳路線是在第 $i$ 個旅館停靠（其中 $0 \le i < j$），則從起點到第 $i$ 個旅館的路線也必定是到達第 $i$ 個旅館的最佳路線。
2. 重疊子問題（Overlapping Subproblems）：計算到達後續旅館的最佳代價時，會重複用到先前已計算好的較小規模子問題的解答（即到達前幾個旅館的最小懲罰值）。
3. 路徑重建（Path Reconstruction）：題目除了要求計算最小懲罰值外，還要求輸出最佳旅館停靠序列（optimal sequence of hotels），因此必須維護一個追蹤陣列（parent 或 prev），以便完成 DP 表格後進行回溯（Backtracking）。

解題方法

1. 符號定義 (Notations)

• 令 $a_0 = 0$ 表示出發起點（公里數為 $0$）。
• 令 $a_1, a_2, \dots, a_n$ 表示沿途 $n$ 間旅館的位置（單位：公里），滿足 $0 < a_1 < a_2 < \dots < a_n$。
• $DP[j]$：表示從起點 $a_0$ 出發，並以第 $j$ 間旅館作為當天住宿點時，到達第 $j$ 間旅館所產生的最小總懲罰值（Minimum Total Penalty）。
• $parent[j]$：記錄使得 $DP[j]$ 達到最小值的上一個停靠點索引 $i$（用於追蹤並重建最佳停靠序列）。

2. 遞迴式 (Recursive Formula)

到達第 $j$ 間旅館的上一站可以是起點 $a_0$ 或先前的任意旅館 $a_i$（其中 $0 \le i < j$）。當天天行進距離為 $x = a_j - a_i$ 公里，當天懲罰值為 $(20 - (a_j - a_i))^2$。

因此，狀態轉移方程式如下：

$DP[j] = \min_{0 \le i < j} \left\{ DP[i] + (20 - (a_j - a_i))^2 \right\} \quad \text{for } 1 \le j \le n$

同時，對應的最佳前驅結點記錄為：

$parent[j] = \arg\min_{0 \le i < j} \left\{ DP[i] + (20 - (a_j - a_i))^2 \right\}$

3. 初始值設定 (Initial Values)

• $DP[0] = 0$：位於起點 $a_0 = 0$ 時，累積懲罰值為 $0$。
• $DP[j] = \infty \quad (\forall 1 \le j \le n)$：將其餘狀態初始化為無窮大。
• $parent[j] = -1 \quad (\forall 0 \le j \le n)$：前驅站索引初始化為 $-1$。

4. 演算法邏輯與虛擬碼 (Algorithm & Pseudocode)

核心觀念

本題考查的核心觀念為**等價關係（Equivalence Relation）與互斥集資料結構（Disjoint-Set Union / Union-Find）**的應用。

1. 等價關係與遞移性：
   等號 Constraints（$x_i = x_j$）滿足自反性、對稱性與遞移性（Transitivity）。因此，一連串的等式約束會將變數集合劃分為數個互不相交的「等價類（Equivalence Classes）」或「連通分量（Connected Components）」。在同一個等價類中的所有變數，其賦值必須完全相同。
2. 矛盾判斷邏輯：
   對於任意不等式 Constraints（$x_i \neq x_j$），若變數 $x_i$ 與 $x_j$ 在等式遞移推導後屬於「同一個等價類」，則產生無法滿足的邏輯矛盾；反之，若所有不等式約束所涉及的兩變數均屬於「不同等價類」，則必定能找到一組實數（或整數）賦值滿足所有條件。
3. 互斥集資料結構（Disjoint-Set / Union-Find）：
   為了高效動態維護這些變數的等價類關係，需使用 Union-Find 資料結構，並搭配**路徑壓縮（Path Compression）與按秩合併（Union by Rank / Size）**兩大優化技術，以達到近乎線性的執行時間。

解題方法

1. 資料結構設計

採用 Disjoint-Set (Union-Find) 維護 $n$ 個變數的連通狀態：

• parent[1..n]：整數陣列，parent[i] 記錄變數 $x_i$ 所屬樹狀結構中的父節點。若 parent[i] == i，代表 $x_i$ 為該集合的根節點（代表元素）。
• rank[1..n]：整數陣列，記錄以 $x_i$ 為根的樹高上限（或子集大小），用於合併時維持樹平衡。

支援以下核心操作：

• Make-Set(i)：初始化變數 $x_i$，令 parent[i] = i 且 rank[i] = 0。
• Find-Set(i)：尋找 $x_i$ 所屬集合的根節點，並在搜尋過程中執行路徑壓縮（將沿途經過的節點直接指向根節點）。
• Union(i, j)：將 $x_i$ 與 $x_j$ 所在的集合合併。使用按秩合併，將秩（Rank）較小的樹掛載至秩較大的樹之下。

2. 演算法步驟與邏輯

本演算法採用兩階段處理原則（Two-Pass Approach）：

• 階段一：合併所有等式（Equality Constraints）

  1. 初始化包含 $n$ 個變數的 Union-Find 資料結構。
  2. 遍歷所有形式為 "$x_i = x_j$" 的等式 constraints。
  3. 對於每一組等式，呼叫 Union(i, j)，將變數 $x_i$ 與 $x_j$ 歸納至同一個等價類中。

• 階段二：檢查所有不等式（Disequality Constraints）

  1. 遍歷所有形式為 "$x_i \neq x_j$" 的不等式 constraints。
  2. 對於每一組不等式，查詢 Find-Set(i) 與 Find-Set(j)：
     • 若 Find-Set(i) == Find-Set(j)：表示 $x_i$ 與 $x_j$ 已被等式約束推導為必須相等，但此處又要求兩者不相等，發生矛盾，演算法立即回傳 False（不可滿足）。
  3. 若遍歷完所有不等式皆未發現矛盾，則回傳 True（可滿足）。

3. 關鍵虛擬碼（Pseudocode）