109 年 國立清華大學奈米工程與微系統研究所《基礎計算機科學》

核心觀念

本題的核心觀念為述詞邏輯（Predicate Logic）中的量詞否定法則（Negation of Quantifiers），以及形式語言中 Pumping Lemma（泵躍引理）敘述的邏輯結構。

1. 量詞否定法則（De Morgan's Laws for Quantifiers）：
   • 存在量詞與全稱量詞的相互轉換：
     $\neg (\exists x \ P(x)) \iff \forall x \ \neg P(x)$
     $\neg (\forall x \ P(x)) \iff \exists x \ \neg P(x)$
   • 帶有範圍限制條件的蘊含式否定：
     $\neg (\forall x \in S, \ P(x) \implies Q(x)) \iff \exists x \in S, \ P(x) \land \neg Q(x)$
     在敘述形式語言引理時，$\forall w \in L, |w| \geq m \ (\dots)$ 常簡寫條件句，其否定即為存在一個屬於 $L$ 且長度滿足 $|w| \geq m$ 的字串，使得後續條件不成立。
2. 隸屬關係（Membership）的否定：
   $\neg (u \in L) \iff u \notin L$

---

解題方法

題目給定的原命題為：
$S = \exists \text{ integer } m \ (\forall \text{ string } w \in L,\ |w| \geq m \ (\exists x y z = w \ (\forall n \ (x y^n z \in L))))$

對命題 $S$ 進行否定操作 $\neg S$，依由外而內的順序逐層將否定符號 $\neg$ 推入各量詞範圍中：

1. 第一層（最外層量詞）：
   原式為 $\exists \text{ integer } m$。
   否定後，存在量詞 $\exists$ 轉為全稱量詞 $\forall$：
   $\neg S = \forall \text{ integer } m \ (\neg (\forall \text{ string } w \in L,\ |w| \geq m \ (\dots)))$

2. 第二層（第二個量詞）：
   內部為「對所有 $w \in L$ 且 $|w| \geq m$」。
   否定後，轉為存在量詞 $\exists$：
   $\exists \text{ string } w \in L,\ |w| \geq m \ (\neg (\exists x y z = w \ (\dots)))$
   （此部分題目 Hint 已給出提示）

3. 第三層（第三個量詞）：
   內部為「$\exists x y z = w$（存在字串拆解 $x, y, z$ 滿足 $x y z = w$）」。
   否定後，存在量詞 $\exists$ 轉為全稱量詞 $\forall$：
   $\forall x y z = w \ (\neg (\forall n \ (\dots)))$

4. 第四層（第四個量詞）：
   內部為「$\forall n$（對所有非負整數 $n$）」。
   否定後，全稱量詞 $\forall$ 轉為存在量詞 $\exists$：
   $\exists n \ (\neg (x y^n z \in L))$

核心觀念

生成樹（spanning tree）是連通無向圖的一個子圖，必須包含原圖的所有頂點，且本身是一棵樹。樹的特性是連通且沒有環路。

若原圖有 $n$ 個頂點，生成樹恰有 $n-1$ 條邊。它保留了連接所有頂點所需的結構，並且不含多餘的環路。

解題方法

判斷一個子圖是否為生成樹，檢查兩項條件：

1. 子圖包含原圖的每一個頂點。
2. 子圖連通且無環。

核心觀念

最小生成樹（MST）是包含圖中所有頂點、沒有迴圈且總邊權重最小的生成樹。若圖有 $n$ 個頂點，生成樹恰有 $n-1$ 條邊；本題有 7 個頂點，因此 MST 要選 6 條邊。

解題方法

使用 Kruskal 演算法：將邊依權重由小到大排列，逐一加入；若加入某邊會形成迴圈，就略過。

依權重檢查本題的邊：

1. $A-D=5$：加入。
2. $C-E=5$：加入。
3. $D-F=6$：加入。
4. $A-B=7$：加入，將 $B$ 接入目前的連通部分。
5. $B-E=7$：加入，連接兩個連通部分。

核心觀念

Kruskal 演算法依邊權重由小到大檢查，每次加入一條不會形成環的邊。對含有 $|V|$ 個頂點的連通圖，最小生成樹（MST）恰有 $|V|-1$ 條邊；本題有 $7$ 個頂點，因此要選 $6$ 條邊。

解題方法

將邊依權重排序：

$$AD(5),\ CE(5),\ DF(6),\ AB(7),\ BE(7),\ BC(8),\ EF(8),\ BD(9),\ EG(9),\ FG(11),\ DE(15)$$

由小到大加入不會形成環的邊：

核心觀念

本題評量離散數學／基礎計算機科學中數論基礎的歐幾里得演算法（Euclidean Algorithm，俗稱輾轉相除法）。

1. 除法定理（Division Algorithm）：
   對於任意整數 $a$ 與正整數 $b$，存在唯一的整數商 $q$ 與餘數 $r$，滿足： $$a = b \times q + r \quad (0 \le r < b)$$
2. 歐幾里得定理（Euclidean Property）：
   兩正整數的最大公因數等於「較小數」與「兩數相除之餘數」的最大公因數： $$\gcd(a, b) = \gcd(b, r) \quad \text{其中 } r = a \bmod b$$ 透過反覆進行除法替換，餘數數列嚴格遞減（$b > r_1 > r_2 > \cdots > r_k = 0$），當最後一步餘數為 $0$ 時，最後一個非零餘數即為兩數的最大公因數 $\gcd(a, b)$。
3. 時間複雜度：
   依據拉梅定理（Lamé's Theorem），歐幾里得演算法執行除法的總次數不超過較小數十進位位數的 5 倍，時間複雜度為 $O(\log(\min(a, b)))$，在大數求最大公因數時遠比質因數分解有效率。

---

解題方法

題目指定使用 Euclidean algorithm 求 $\gcd(167076, 1928737)$。設較大數為 $a = 1{,}928{,}737$，較小數為 $b = 167{,}076$。

依序執行帶餘除法運算如下：

1. 第 1 步：

   $$1{,}928{,}737 = 167{,}076 \times 11 + 90{,}901$$

   餘數為 $90{,}901$。

2. 第 2 步：

   $$167{,}076 = 90{,}901 \times 1 + 76{,}175$$

   餘數為 $76{,}175$。

3. 第 3 步：

   $$90{,}901 = 76{,}175 \times 1 + 14{,}726$$

   餘數為 $14{,}726$。

4. 第 4 步：

   $$76{,}175 = 14{,}726 \times 5 + 2{,}545$$

   餘數為 $2{,}545$（因為 $14{,}726 \times 5 = 73{,}630$）。

5. 第 5 步：

   $$14{,}726 = 2{,}545 \times 5 + 2{,}001$$

   餘數為 $2{,}001$（因為 $2{,}545 \times 5 = 12{,}725$）。

6. 第 6 步：

   $$2{,}545 = 2{,}001 \times 1 + 544$$

   餘數為 $544$。

7. 第 7 步：

   $$2{,}001 = 544 \times 3 + 369$$

   餘數為 $369$（因為 $544 \times 3 = 1{,}632$）。

核心觀念

本題考查離散數學（組合數學）中的環狀排列（Circular Permutations）。

在一般的直線排列中，$n$ 個相異物體排成一列的方法數為：

$$n!$$

而在環狀排列中，由於圓桌或環狀座位具有旋轉對稱性，任何一個排列只要透過旋轉能與另一種排列完全重合，兩者即視為同一種相對排法。每個由 $n$ 個人形成的環狀排列，沿同一個方向旋轉 $n$ 次會對應到 $n$ 種不同的直線排列（即每種環狀排列在直線上有 $n$ 種重複計數）。

因此，$n$ 個相異物體排成一圈的相異環狀排列數公式為：

$$\frac{n!}{n} = (n - 1)!$$

---

解題方法

本題共有 5 位相異的人（$n = 5$）要分配到圍成一圈的 5 個座位中。標準切入點有以下兩種方式，均能迅速求出正解：

方法一：相對固定法（最推薦的直觀思維）

1. 為了破除圓形的「旋轉對稱性」，先讓第 1 個人隨意入座。
2. 由於在空圓桌上，任何座位相對於其他人都沒有差異（純由旋轉即可重合），因此第 1 個人入座僅有 $1$ 種實質排法（用來作為基準點，定義出其他座位的相對位置：如左手邊第 1 位、對面等）。
3. 當第 1 個人固定後，其餘剩下的 $5 - 1 = 4$ 個座位便轉變為具有特定相對方位（相異）的直線排列問題。
4. 剩下的 4 個人依序入座，方法數為：

核心觀念

本題考查圖論（Graph Theory）中的基本計數定理：握手引理（Handshaking Lemma）。

1. 頂點個數與邊數：
   設 $G = (V, E)$ 是一個無向圖，其中 $V$ 為頂點集合（Vertices），$E$ 為邊集合（Edges）。其頂點數記為 $|V|$，邊數記為 $|E|$。
2. 握手引理（Handshaking Lemma）：
   在任意無向圖中，所有頂點的分支度（Degree，亦稱度數）之總和等於邊數的兩倍： $$\sum_{v \in V} \deg(v) = 2|E|$$ 此定理的直觀意義在於：每條邊連接著兩個頂點，因此每增加一條邊，圖中所有頂點的度數總和便增加 2。

---

解題方法

1. 列出題目已知條件：
   • 頂點總數 $|V| = 12$。
   • 其中有 4 個頂點的分支度各為 3，即： $$\deg(v) = 3 \quad (\text{共 } 4 \text{ 個頂點})$$
   • 其餘剩餘頂點數為 $12 - 4 = 8$ 個，其分支度各為 5，即： $$\deg(v) = 5 \quad (\text{共 } 8 \text{ 個頂點})$$

核心觀念：圖論中的完全圖與漢米爾頓環分解（Hamiltonian Cycle Decomposition）

本題源自離散數學（Discrete Mathematics）與圖論（Graph Theory）中的經典排程與圓桌會議問題，其數學模型為完全圖的邊不相交漢米爾頓環分解（Edge-Disjoint Hamiltonian Cycle Decomposition）：

1. 圖論模型對應：

   • 將全班 $n = 19$ 位學生視為無向圖中的 $n$ 個頂點（Vertices）。
   • 任意兩位學生之間相鄰就坐，視為兩頂點之間連有一條邊（Edge）。
   • 由於任何學生都可能與其他任何學生相鄰，這 $n$ 位學生所有可能的相鄰關係構成了完全圖 $K_n$（Complete Graph）。
   • 每一天的圓桌座位安排，等價於在圖中尋找一個包含所有 19 個頂點且不重複的環，即漢米爾頓環（Hamiltonian Cycle）。

2. 限制條件分析：

   • 題目要求「每位學生每天都要坐在兩位不同的同學身旁」（each student to sit next to two different classmates each day），表示任何兩位同學在所有天數中最多只能相鄰一次，即任何一條邊在所有天數中不得重複使用。
   • 因此，天數的最大值等價於「完全圖 $K_{19}$ 最多能分解出幾個彼此邊不相交（edge-disjoint）的漢米爾頓環」。

3. 瓦萊基定理（Walecki's Theorem）：

   • 對於奇數個頂點的完全圖 $K_n$（$n$ 為奇數），其所有邊可以被完全分解為 $\frac{n - 1}{2}$ 個邊不相交的漢米爾頓環。

---

解題方法

步驟一：計算總邊數與每日所需邊數

在完全圖 $K_{19}$ 中：

• 頂點數 $n = 19$。
• 完全圖 $K_{19}$ 的總邊數為：

$$|E(K_{19})| = \binom{19}{2} = \frac{19 \times 18}{2} = 171$$

• 每天 19 位學生圍坐成一個圓圈，形成一個長度為 19 的環（Cycle $C_{19}$），每天剛好消耗 19 條相鄰的邊。

步驟二：推導天數的理論上限

因為任何兩位學生不能再次相鄰，每天所使用的 19 條邊彼此互斥（邊不相交）。天數 $D$ 的理論最大值受限於圖的總邊數：

核心觀念

本題評量遞迴關係式（Recurrence Relation）之漸近複雜度分析與漸近記號（Asymptotic Notation）之定義證明。

1. 遞迴展開法（Substitution Method / Iteration Method）：適用於可逐層化簡的線性遞迴關係，展開後觀察其規律，並轉化為有限級數求和。
2. 算術級數公式（Arithmetic Series）： $$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$
3. 漸近緊密上界（Tight Upper Bound / Big-O Notation）的正式定義：
   若存在正實數常數 $c > 0$ 與正整數 $n_0$，使得對所有 $n \ge n_0$，不等式 $0 \le T(n) \le c \cdot g(n)$ 皆成立，則 $T(n) = O(g(n))$。在此要求「tight」代表求出階數最緊的 $O$ 記號上界（即本質上的 $\Theta(n^2)$ 緊密界）。

---

解題方法

步驟一：展開遞迴關係式（Iteration Method）

題目未顯式給定基本情況（base condition），一般計算機演算法中假設基本情況為常數時間，設 $T(0) = c_0$（或 $T(1) = c_1$），其中 $c_0$ 為常數。

將遞迴式連續展開：

$$\begin{aligned} T(n) &= T(n-1) + 2n \\ &= [T(n-2) + 2(n-1)] + 2n \\ &= [T(n-3) + 2(n-2)] + 2(n-1) + 2n \\ &\;\;\vdots \\ &= T(0) + \sum_{i=1}^n 2i \end{aligned}$$

步驟二：閉式解（Closed Form）推導

利用等差級數公式化簡總和：

核心觀念

1. 遞迴關係式求解（Solving Recurrence Relations）：
   本題之遞迴形式為 $T(n) = c \cdot T(n-1) + f(n)$，此類每次規模僅減少固定常數（減 1）而非依比例縮小的遞迴，不適用 Master Theorem（主定理），通常採用**反覆展開法（Iteration / Unrolling Method）**進行展開推導。
2. 差比數列求和（Sum of Arithmetico-Geometric Sequence）：
   在展開後的非齊次項加總過程中，會形成「等差乘等比」的級數 $\sum_{i=0}^{k} i \cdot 2^{i}$，需利用差比級數求和公式或求和技巧推導出閉合形式（Closed-form）。
3. 緊密漸近上界（Tight Asymptotic Upper Bound）：
   題目要求以 Big-$O$ 表示之緊密上界（即漸近緊密界線 $\Theta$ 所對應的最小上界 $O$）。假設基本情況（Base Case）為常數時間，即存在常數 $c_0$ 使得 $T(1) = \Theta(1)$。

---

解題方法

本題採用**反覆展開法（Unrolling / Iteration Method）**逐步展開遞迴式，歸納通式後計算級數和。

步驟一：逐步反覆展開

已知遞迴式：

$$T(n) = 2T(n-1) + n$$

將 $T(n-1) = 2T(n-2) + (n-1)$ 代入：

$$T(n) = 2\left[2T(n-2) + (n-1)\right] + n = 2^2 T(n-2) + 2(n-1) + n$$

將 $T(n-2) = 2T(n-3) + (n-2)$ 代入：

$$T(n) = 2^2\left[2T(n-3) + (n-2)\right] + 2(n-1) + n = 2^3 T(n-3) + 2^2(n-2) + 2(n-1) + n$$

依此規律展開 $k$ 次後，可歸納出通式：

$$T(n) = 2^k T(n-k) + \sum_{i=0}^{k-1} 2^i (n-i)$$

步驟二：代入終止條件（Base Case）

令 $n - k = 1$，即 $k = n - 1$，且設 $T(1) = c$（常數）：

$$T(n) = 2^{n-1} T(1) + \sum_{i=0}^{n-2} 2^i (n-i)$$

將後方求和項拆解為兩部分：

$$\sum_{i=0}^{n-2} 2^i (n-i) = n \sum_{i=0}^{n-2} 2^i - \sum_{i=0}^{n-2} i \cdot 2^i$$

步驟三：計算各項級數和

1. 等比級數項：

$$\sum_{i=0}^{n-2} 2^i = \frac{2^{n-1} - 1}{2 - 1} = 2^{n-1} - 1$$

因此：

$$n \sum_{i=0}^{n-2} 2^i = n(2^{n-1} - 1) = n \cdot 2^{n-1} - n$$

2. 差比級數項 $S = \sum_{i=0}^{n-2} i \cdot 2^i$：

核心觀念

本題考查經典演算法題目：最長遞增子序列問題（Longest Increasing Subsequence, LIS）。
要求使用**動態規劃（Dynamic Programming, DP）**技巧，設計並證明一個時間複雜度為 $O(n^2)$ 的演算法。

在動態規劃的設計中，最關鍵的兩個要素為：

1. 最佳子結構（Optimal Substructure）：問題的最佳解包含其子問題的最佳解。若一個以 $a_i$ 結尾的遞增子序列是最長的，則去掉 $a_i$ 後的前綴子序列，必然也是以其前一個元素 $a_j$（滿足 $j < i$ 且 $a_j < a_i$）結尾的最長遞增子序列。
2. 重疊子問題（Overlapping Subproblems）：計算不同位置結尾的 LIS 時，會重複使用到前面較短前綴的 LIS 長度與結果。

---

解題方法

1. 狀態定義（State Definition）

令陣列 $A = (a_1, a_2, \ldots, a_n)$。
定義 DP 狀態陣列 $L[1 \ldots n]$：

• $L[i]$：代表以 $a_i$ 作為最後一個元素（結尾）的最長遞增子序列（LIS）的長度。
• 若需要重建出具體的子序列，可額外維護一個前驅指標陣列 $P[1 \ldots n]$，其中 $P[i]$ 記錄在最長遞增子序列中，$a_i$ 的前一個元素索引（若 $a_i$ 為起點則設為 $0$ 或 $-1$）。

2. 轉移方程式（Recurrence Relation）

對於每一個位置 $i$（從 $1$ 到 $n$）：

• 基礎情況（Base Case）：任何元素自己本身都可以構成長度為 $1$ 的遞增子序列，故初始值 $L[i] = 1$。
• 狀態轉移：檢查所有位於 $a_i$ 前方的元素 $a_j$（即 $1 \le j < i$）。若滿足嚴格遞增條件 $a_j < a_i$，則 $a_i$ 可以接在以 $a_j$ 結尾的子序列之後，長度變為 $L[j] + 1$。因此取所有可能中的最大值：

$$L[i] = 1 + \max \big(\{0\} \cup \{ L[j] \mid 1 \le j < i \text{ 且 } a_j < a_i \}\big)$$

若同時要記錄路徑：

• 當找到使 $L[j] + 1 > L[i]$ 的 $j$ 時，更新 $L[i] = L[j] + 1$，並令 $P[i] = j$。

3. 最終結果（Final Answer）

整個序列 $A$ 的 LIS 長度即為所有 $L[i]$ 的最大值：

$$\text{LIS Length} = \max_{1 \le i \le n} L[i]$$

令最大值發生的索引為 $k$（即 $L[k] = \max L[i]$），透過前驅陣列 $P$，從 $k$ 開始沿著 $P[k], P[P[k]], \ldots$ 往前回溯，再將收集到的元素反轉，即可重構出完整的 LIS 序列。

---

演算法虛擬碼（Algorithm & Pseudocode）

核心觀念

本題的核心觀念為**計算複雜度理論（Computational Complexity Theory）**中的 NP-Complete（NPC，NP 完全）證明。

要證明一個判定問題（Decision Problem）$L$ 屬於 NP-Complete，必須滿足兩個基本條件：

1. $L \in \text{NP}$：存在一個非確定性多項式時間演算法，或給定一個候選解（Certificate / Witness），能在確定性多項式時間（Polynomial Time）內驗證其正確性。
2. $L$ 是 NP-Hard：選定一個已知的 NP-Complete 問題 $L'$，證明存在多項式時間歸約（Polynomial-Time Reduction），記作：

$$L' \le_P L$$

即任何 $L'$ 的輸入實例（Instance），皆可在多項式時間內轉換為 $L$ 的實例，且兩者的「YES / NO」答案具備充分必要關係。

本題已知 2-Partition 問題（將集合劃分為 2 個總和相等的子集）為 NP-Complete，欲證明 3-Partition 問題（將集合劃分為 3 個總和相等的子集）亦為 NP-Complete。

---

解題方法

證明分為兩大部分：證明 3-Partition $\in$ NP，以及證明 2-Partition $\le_P$ 3-Partition。

第一部分：證明 3-Partition $\in$ NP

1. 候選解（Certificate）：
   給定集合 $S$，提供一個由 3 個子集組成的劃分 $(S_1, S_2, S_3)$。
2. 多項式時間驗證器（Polynomial-Time Verifier）：
   • 檢查 $S_1 \cup S_2 \cup S_3 = S$ 且 $S_1, S_2, S_3$ 兩兩互斥（$S_i \cap S_j = \emptyset, \forall i \ne j$）。此步驟需時 $O(n)$。
   • 計算各子集元素之總和：$\sum_{x \in S_1} x$、$\sum_{x \in S_2} x$ 與 $\sum_{x \in S_3} x$。此步驟需時 $O(n)$。
   • 驗證三者是否相等：$\sum_{x \in S_1} x = \sum_{x \in S_2} x = \sum_{x \in S_3} x$。此步驟需時 $O(1)$。

以上驗證程序可在 $O(n)$ 多項式時間內完成，故 3-Partition $\in$ NP。

---

第二部分：證明 2-Partition $\le_P$ 3-Partition（NP-Hardness）

令 2-Partition 問題的給定實例為正數集合：

$$A = \{a_1, a_2, \dots, a_n\}$$

其全體元素總和記為：

$$W = \sum_{i=1}^n a_i$$

2-Partition 問題即是詢問：是否存在劃分 $(A_1, A_2)$ 使得：

$$\sum_{a \in A_1} a = \sum_{a \in A_2} a = \frac{W}{2}$$

1. 構造轉換（Reduction Construction）

我們在多項式時間內建構一個 3-Partition 的實例集合 $S$：

• 將 $A$ 中所有元素放大 2 倍，並額外加入一個新元素 $W$：

$$S = \{2a_1, 2a_2, \dots, 2a_n, W\}$$

此時集合 $S$ 共有 $n+1$ 個元素。

計算集合 $S$ 的全體元素總和 $\text{Sum}(S)$：

$$\text{Sum}(S) = \sum_{i=1}^n 2a_i + W = 2W + W = 3W$$

若 $S$ 可以被等和劃分為 3 個子集 $S_1, S_2, S_3$，則每個子集的目標總和必須剛好為：

$$\frac{\text{Sum}(S)}{3} = \frac{3W}{3} = W$$

此構造過程僅需對 $n$ 個數字乘 2 並求和，可在 $O(n)$ 多項式時間內完成。

2. 正確性證明（雙向等價性）

核心觀念

本題評量演算法複雜度分析中 Big-$O$ 漸近符號（Asymptotic Notation）的嚴格數學定義與基本性質。

依據 Big-$O$ 定義：
若 $f(n) = O(g(n))$，代表存在兩個正實數常數 $c > 0$ 與 $n_0 \geq 1$，使得對所有 $n \geq n_0$，皆滿足：

$$0 \leq f(n) \leq c \cdot g(n)$$

關鍵概念包含兩點：

1. 常數倍數關係（Constant Factor）：定義中為 $f(n) \leq c \cdot g(n)$，而非單純的 $f(n) \leq g(n)$。只要存在某個常數倍數 $c$，即使 $g(n) < f(n)$ 依然成立。
2. 漸近閾值（Threshold $n_0$）：不等式僅要求在「足夠大」的 $n \geq n_0$ 時成立，不要求在任意特定的固定下界（如本題要求的 $n > 1$）立即成立。

---

解題方法

要判定全稱命題（對所有符合 $f(n) = O(g(n))$ 的函數，在 $n > 1$ 時皆滿足 $g(n) \geq f(n)$）是否正確，最直接且嚴謹的方法是提出反例（Counterexample）。

只需構造出一組函數 $f(n)$ 與 $g(n)$，使其滿足 $f(n) = O(g(n))$，但在 $n > 1$ 時存在 $g(n) < f(n)$，即可證明該命題為 False。

反例構造推導：
令 $f(n) = 2n$ 且 $g(n) = n$。

1. 驗證 $f(n) = O(g(n))$：
   選取常數 $c = 2$ 及 $n_0 = 1$。
   對所有 $n \geq 1$，皆滿足： $$f(n) = 2n \leq 2 \cdot n = c \cdot g(n)$$ 因此根據定義，$2n = O(n)$ 完全成立。
2. 檢驗題設結論 $g(n) \geq f(n)$ 對 $n > 1$ 是否成立：
   當 $n > 1$（例如 $n = 2$）時： $$g(2) = 2$$ $$f(2) = 4$$ 明顯可得 $g(2) < f(2)$，亦即 $g(n) < f(n)$ 對所有 $n > 1$ 恆成立。

核心觀念

本題評量對經典排序演算法（Sorting Algorithms）的適用情境與實際效能特性之理解，特別是 合併排序法（Merge Sort） 與 插入排序法（Insertion Sort） 的優缺點對比：

1. 大 $O$ 漸近時間複雜度與常數常數項（Constant Factors）：
   • 漸近複雜度衡量的是資料量 $n \to \infty$ 時的成長趨勢。
   • 實務執行時間為 $c_1 \cdot n \log n$ 與 $c_2 \cdot n^2$。當資料量 $n$ 極小時，由於 Insertion Sort 的常數項 $c_2$ 遠小於 Merge Sort 的常數項 $c_1$（Merge Sort 涉及遞迴呼叫與額外陣列複製的開銷），Insertion Sort 的實際執行速度反而更快。
2. 資料的原始排序狀態（Nearly Sorted Data）：
   • Insertion Sort 在「幾乎已排序（nearly sorted）」的情境下具備最佳時間複雜度 $O(n)$。
   • Merge Sort 不論輸入資料的初始順序為何，其時間複雜度皆固定為 $O(n \log n)$。
3. 混合排序演算法（Hybrid Sort）的工程實踐：
   • 現代標準函式庫常見的排序演算法（如 Timsort、Introsort）在子問題規模小於特定閾值（例如 $n \le 16 \sim 64$）時，皆會切換至 Insertion Sort。

---

解題方法

切入點在於識別題目結論中的絕對字眼：「always use Merge Sort for better efficiency（若空間允許，我們總是應該使用 Merge Sort 以獲得更佳效率）」。

反駁此命題時，只需指出存在「空間完全充裕，但使用 Insertion Sort 效率反而顯著高於 Merge Sort」的具體合理情境：

1. 小規模資料集（Small $n$）：
   當資料筆數 $n$ 很小時，Insertion Sort 程式邏輯極為精簡，指令週期短、無遞迴額外負載（overhead）、具備優秀的快取局部性（Cache Locality），執行效率高於 Merge Sort。
2. 幾乎已排序資料（Nearly Sorted Data）：
   當資料序列已經或接近完全排序時，Insertion Sort 僅需進行相鄰比較，耗時為 $O(n)$，表現遠優於 Merge Sort 的 $O(n \log n)$。

因此，「無論何種情況都應使用 Merge Sort」在計算機科學實務與理論上皆不成立。

---

選項分析

• 題幹陳述：

  "Merge Sort has worst-case time complexity $O(n \log n)$, while the worst-case time complexity of Insertion Sort is $O(n^2)$. One weakness of Merge Sort is that

核心觀念

1. 二元搜尋樹（Binary Search Tree, BST）的定義與搜尋特性：
   • 設樹中節點數為 $n$、樹高為 $h$。
   • 在 BST 中搜尋一個特定的鍵值（key），每一層最多只會比對一個節點，因此走訪的路徑長度至多為樹高 $h$。
   • 搜尋操作的時間複雜度取決於樹的高度，即 $O(h)$。
2. 樹高 $h$ 與節點數 $n$ 的關係：
   • 最佳情況 / 平均情況（Best / Average Case）：當樹呈現平衡狀態（Balanced）時，樹高 $h = \Theta(\log n)$，搜尋時間為 $O(\log n)$。
   • 最差情況（Worst Case）：若輸入資料為已排序序列（如依序插入 $1, 2, \dots, n$），BST 會退化成一條單向鏈結串列（Skewed Tree / Degenerate Tree），此時樹高 $h = \Theta(n)$，搜尋時間為 $O(n)$。
3. 大 $O$ 符號（Big-O Notation）的嚴謹性：
   • 題目敘述宣稱「在二元搜尋樹中搜尋耗時 $O(\log n)$」，若未特別指明情況，在演算法分析中預設指最差情況（Worst-case upper bound），或涵蓋該資料結構所有可能構型的通則。由於最差情況為 $O(n)$，不符合 $O(\log n)$ 的上界，因此敘述為非。

---

解題方法

本題為是非題（若為 False 需附上理由）。切入點在於舉出反例（Counterexample），說明一般二元搜尋樹在未保證平衡的情況下，搜尋時間可能退化至線性時間：

1. 指出搜尋時間複雜度本質上是 $O(h)$，其中 $h$ 為樹高。
2. 指出當 BST 退化成傾斜樹（Skewed Tree）時，$h = O(n)$。
3. 結論：最差情況下的搜尋時間為 $O(n)$，而非 $O(\log n)$。唯有在自平衡二元搜尋樹（如 AVL Tree、Red-Black Tree）中，搜尋時間才保證為 $O(\log n)$。

---

選項分析

• 題目敘述：「Searching a specific key in a binary search tree takes $O(\log n)$ time, where $n$ is the number of keys in the binary sea

核心觀念

前序走訪（pre-order）依序記錄「根、左子樹、右子樹」；層序走訪（level-order）則從根開始，逐層由左至右記錄節點。若兩種走訪序列能唯一決定二元樹，任何符合相同序列的樹都必須具有相同結構。

解題方法

以三個節點 $A、B、C$ 構造兩棵結構不同的二元樹，並比較它們的走訪序列：

樹一：          樹二：

    A              A
   /              / \
  B              B   C
 / \
C

核心觀念

AVL 樹在每次插入後，都要檢查受影響節點的平衡因子。採用

$$BF(v)=h(\text{左子樹})-h(\text{右子樹})$$

當 $|BF(v)|>1$ 時，必須旋轉調整。若失衡節點的新增方向是「右子樹的左側」，屬於右左（RL）型，需先對右子節點右旋，再對失衡節點左旋。

解題方法

原圖中的樹為：根節點 $15$，左子節點 $4$、右子節點 $20$；節點 $4$ 的右子節點是 $12$，節點 $20$ 的右子節點是 $25$。依序插入 $17、19、18$，每次都先依二元搜尋樹規則找插入位置，再檢查平衡因子。

1. 插入 $17$： $17>15$ 且 $17<20$，所以插入為 $20$ 的左子節點。此時各節點的平衡因子仍在 $-1$ 到 $1$ 之間，不需旋轉。

2. 插入 $19$： $19>15$、$19<20$ 且 $19>17$，所以插入為 $17$ 的右子節點。節點 $20$ 的左子樹較高一層，仍符合 AVL 平衡條件。

核心觀念

AVL 樹除了符合二元搜尋樹的大小順序外，每個節點的平衡因子都必須介於 $-1$ 與 $1$。平衡因子定義為

$$BF(v)=h(\text{左子樹})-h(\text{右子樹})$$

空子樹高度取 $0$，葉節點高度取 $1$。刪除節點後若出現 $|BF|=2$，便依失衡節點與較高子樹的方向選擇旋轉；左右型（RL）須先對右子節點右旋，再對失衡節點左旋。

解題方法

依原圖讀取初始樹：根節點為 $15$；左子節點 $4$ 的右子節點為 $12$；右子節點 $20$ 的右子節點為 $25$。接著承接 (a) 依序插入 $17,19,18$，再依題意依序刪除 $25,17$。

以下以 $v(L,R)$ 表示節點 $v$ 的左、右子樹；「$\varnothing$」代表空子樹。

1. 插入 $17$，成為 $20$ 的左子節點；再插入 $19$，成為 $17$ 的右子節點。接著插入 $18$，成為 $19$ 的左子節點。此時節點 $17$ 的平衡因子為 $-2$，其右子節點 $19$ 的平衡因子為 $+1$，因此對 $17$ 做 RL 旋轉。完成 (a) 後的樹為

   $$15\bigl(4(\varnothing,12),\ 20(18(17,19),25)\bigr)$$

核心觀念

圖的中心是頂點中偏心度最小者。偏心度 $\epsilon(v)$ 是頂點 $v$ 到其他所有頂點的最短路徑距離中的最大值；若多個頂點同時達到最小偏心度，它們都可以是中心。

解題方法

使用題目附圖中的加權圖：$a$–$b$ 權重為 $4$、$a$–$c$ 為 $6$、$b$–$d$ 為 $5$、$c$–$d$ 為 $4$。先求各頂點到其他頂點的最短距離，再取最大值：

頂點	到其他頂點的最短距離	偏心度
$a$	$d(a,b)=4,\ d(a,c)=6,\ d(a,d)=9$	$\epsilon(a)=9$
$b$	$d(b,a)=4,\ d(b,c)=9,\ d(b,d)=5$	$\epsilon(b)=9$

核心觀念

絕對中心可以位於頂點，也可以位於邊的內部。要證明「多個絕對中心都在頂點上」是可能的，只要找出一個圖，使多個頂點達到最小最大距離，而每條邊的內部點都比這個最小值差。

解題方法

取一個三角形圖 $K_3$，三個頂點為 $A,B,C$，每條邊的權重都設為 $2$。

在任一頂點，例如 $A$，到另外兩個頂點的最短距離都是 $2$，因此

$$\epsilon(A)=\epsilon(B)=\epsilon(C)=2.$$

再看邊 $AB$ 上距離 $A$ 為 $x$ 的內部點 $P$，其中 $0<x<2$。到第三個頂點 $C$ 的最短距離為

核心觀念

頂點的中心性以離它最遠頂點的最短路徑距離衡量；絕對中心則允許位置落在邊的內部。令圖上任意點 $p$ 的半徑為 $R(p)=\max_{y\in V}d(p,y)$，題目要找一個例子，使某個頂點與某個邊內點同時達到最小半徑。

解題方法

原頁圖中的示意圖有邊長 $ab=4$、$ac=6$、$cd=4$、$bd=5$；圖上 $x$ 位於 $bd$ 的中點，至 $b$、$d$ 各為 $2.5$。以下另建一個圖，讓一個頂點和一個邊內點的半徑相同，並用一對相距最遠的頂點證明此半徑已是最小值。

構造頂點 $t,v,u,w,z$，只設以下邊：

• $tv=2$、$vu=2$、$uw=2$
• $vz=1$、$uz=1$

令 $x$ 為邊 $vu$ 的中點，因此 $x$ 到 $v$、$u$ 各為 $1$。圖中所有邊長都是正整數。

距離與半徑驗算

由上述邊長得到各頂點間的最短距離：

$d(\cdot,\cdot)$	$t$	$v$	$u$	$w$	$z$
$t$	0	2	4	6	3
$v$	2	0	2	4	1
$u$	4	2	0	2	1