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

核心觀念

本題考驗**快速排序法（Quicksort）**的各項核心理論特性，包含：

1. 時間複雜度（Time Complexity）：最壞情況（Worst-case）與隨機化下的期望值（Expected time）。
2. 樞紐碼選擇策略（Pivot Selection Strategy）：中位數（Median）選擇對遞迴時間複雜度的保證。
3. 排序穩定度（Stability）：原地（In-place）Partition 運算對相同鍵值元素相對順序的影響。
4. 空間複雜度（Space Complexity）：遞迴呼叫堆疊（Recursion Stack）空間的消耗。

解題方法

分析 Quicksort 時，可將演算法分為 Partition（分割） 與 Recursive Calls（遞迴呼叫） 兩部分：

1. 遞迴關係式（Recurrence Relation）：
   設輸入資料量為 $n$，分割後兩側子陣列的大小分別為 $k$ 與 $n - 1 - k$（其中 $0 \le k \le n - 1$），則執行時間滿足：
   $T(n) = T(k) + T(n - 1 - k) + \Theta(n)$

2. 最壞情況分析：
   當分割極度不均勻（如 $k = 0$ 或 $k = n - 1$）時：
   $T(n) = T(n - 1) + \Theta(n) = \Theta(n^2)$

3. 最佳與理想分割分析：
   若每次分割均能平分陣列（$k \approx \frac{n}{2}$）：
   $T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)$
   根據主定理（Master Theorem），此式解得 $T(n) = \Theta(n \log n)$。

4. 空間複雜度分析：
   Quicksort 雖然是在原陣列進行交換（In-place），但系統必須維持遞迴呼叫堆疊（Recursion Stack）。堆疊深度取決於遞迴樹的高度。

選項分析

• (A) 正確
  在最壞情況下（例如：輸入資料已排序或逆序，且每次皆選擇最邊緣元素作為 Pivot），分割結果為 $0$ 與 $n - 1$ 個元素。遞迴關係式為 $T(n) = T(n - 1) + O(n)$，展開後得 $T(n) = O(n^2)$。

核心觀念

攤還分析（Amortized Analysis）為演算法分析中的核心技術，主要用於分析資料結構在一連串操作（Sequence of operations）下的平均成本。

關鍵觀念與定義包含：

1. 與平均情況分析（Average-Case Analysis）的本質差異：
   • 攤還分析不假設任何輸入資料的機率分佈（Probability Distribution），保證的是在**最壞狀況的操作序列（Worst-case sequence of operations）**下，每個操作的平均成本上界。
   • 平均情況分析則高度依賴輸入資料的機率分佈，求取隨機輸入下的期望成本（Expected Cost）。
2. 單一操作與序列成本：
   • 攤還成本（Amortized Cost）為 $O(1)$ 並不代表每一個單一操作的實際執行時間（Actual Cost）皆為 $O(1)$。序列中允許存在少數極為昂貴（如 $O(n)$）的操作，只要其成本能被其他操作預先存納的成本所抵銷即可。
3. 三大分析方法：
   • 聚合分析（Aggregate Method）：計算 $n$ 個操作的總實際成本 $T(n)$，則每個操作的攤還成本為 $\frac{T(n)}{n}$。
   • 記帳法（Accounting Method）：為不同的操作設定「攤還費用（Amortized Cost）」。當操作的攤還費用高於實際成本時，多出的部分轉為信用（Credit）存入資料結構中，用以支付未來實際成本大於攤還費用的高昂操作。
   • 位能法（Potential Method）：定義位能函數（Potential Function）$\Phi(D_i)$ 將資料結構狀態 $D_i$ 映射至實數。第 $i$ 個操作的攤還成本 $c_i'$ 定義為：
     $c_i' = c_i + \Phi(D_i) - \Phi(D_{i-1})$
     其中 $c_i$ 為實際成本。若位能增加（$\Phi(D_i) - \Phi(D_{i-1}) > 0$），代表將能量／費用預存於資料結構中，用以補貼未來高耗時操作。

解題方法

本題為觀念型複選題，切入點為精準掌握攤還分析的三大分析技術（Aggregate, Accounting, Potential methods）之定義，以及攤還分析與平均情況分析的本質差別。

解法為依據 CLRS《Introduction to Algorithms》經典教科書之嚴謹定義，逐一驗證選項 (A) 至 (E) 的敘述正確性。

選項分析

• (A) 正確：
  攤還分析（Amortized Analysis）旨在評估任意操作序列（Any sequence of operations）下平均每個操作成本的上界（Upper bo

核心觀念

本題考核**動態規劃（Dynamic Programming, DP）在最長共同子序列（Longest Common Subsequence, LCS）**問題中的應用，包含遞迴關係式（狀態轉移方程式）推導、時間複雜度分析以及空間複雜度最佳化（空間壓縮）。

1. LCS 狀態定義：
   設 $dp[i][j]$ 表示字串 $X[1..i]$（前 $i$ 個字元）與字串 $Y[1..j]$（前 $j$ 個字元）的 LCS 長度。

2. 遞迴關係式（Recurrence Relation）：

3. 空間最佳化原理（Rolling Array）：
   計算第 $i$ 列 $dp[i][j]$ 時，僅需參考當前列 $dp[i][\cdot]$ 與前一列 $dp[i-1][\cdot]$ 的值。因此可使用大小僅為 $2 \times (n+1)$ 的表格進行輪替更新，完成答案計算。

解題方法

1. 字元匹配狀況推導 ($X[i] == Y[j]$)

當末尾字元 $X[i]$ 與 $Y[j]$ 相同，此字元必包含於 $X[1..i]$ 與 $Y[1..j]$ 的最長共同子序列中。因此，最佳解等於「排除該字元後的前綴子串 $X[1..i-1]$ 與 $Y[1..j-1]$ 之 LCS 長度」加上 $1$：
$dp[i][j] = dp[i-1][j-1] + 1$

2. 字元不匹配狀況推導 ($X[i] \neq Y[j]$)

當末尾字元不同，兩字元無法同時作為 LCS 的末尾字元。此時有兩種互斥的選擇情境：

• 排除 $X[i]$：考慮 $X[1..i-1]$ 與 $Y[1..j]$，長度為 $dp[i-1][j]$。
• 排除 $Y[j]$：考慮 $X[1..i]$ 與 $Y[1..j-1]$，長度為 $dp[i][j-1]$。

取兩者最大值即可確保覆蓋最佳解：
$dp[i][j] = \max(dp[i-1][j], dp[i][j-1])$

針對選項 (I) 的數學等價性推導：
因為子字串包含關係，$dp$ 表格具單調非遞減特性，即：
$dp[i-1][j-1] \le dp[i-1][j] \quad \text{且} \quad dp[i-1][j-1] \le dp[i][j-1]$
將 $dp[i-1][j-1]$ 併入 $\max$ 計算中，結果依然不變：
$\max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) = \max(dp[i-1][j], dp[i][j-1])$
因此選項 (I) 在邏輯與數值結果上皆完全正確。

核心觀念

本題旨在考驗對**貪婪演算法（Greedy Algorithm）基本性質、適用條件、經典應用及其與動態規劃（Dynamic Programming, DP）**之間關係的理解。

1. 貪婪演算法的兩大核心要素：
   • 貪婪選擇性質（Greedy-Choice Property）：可透過做出局部最佳選擇（Local Optimal Choice）來導出全域最佳解（Global Optimal Solution），且先前的選擇不會因後續決策而改變。
   • 最佳子結構（Optimal Substructure）：原問題的最佳解包含其子問題的最佳解。
2. 背包問題（Knapsack Problems）之差異：
   • 分數背包問題（Fractional Knapsack Problem）：物品可任意分割，滿足貪婪選擇性質。
   • 0/1 背包問題（0/1 Knapsack Problem）：物品不可分割，不滿足貪婪選擇性質，必須採用動態規劃求解。
3. 單源最短路徑演算法之限制：
   • Dijkstra 演算法基於貪婪選擇，前提假設為所有邊的權重皆為非負值（Non-negative Edge Weights）。若含有負權邊，已選定的最短距離頂點可能會被後續鬆弛（Relaxation）操作更新，導致貪婪策略失效。
4. 貪婪演算法與動態規劃之包含關係：
   • 貪婪演算法可視為動態規劃的特例。能用貪婪演算法求解的問題必定能用動態規劃求解，但反之不成立（DP 適用範圍大於 Greedy）。
5. 最小生成樹（Minimum Spanning Tree, MST）演算法：
   • Prim 演算法與 Kruskal 演算法皆基於切割定理（Cut Property），每次選擇當前最佳的「輕邊（Light Edge）」，屬於典型的貪婪演算法。

解題方法

判定貪婪演算法相關敘述的正確性時，可依循以下邏輯切入：

1. 驗證正確性條件：欲證明一個貪婪演算法永遠能得到最佳解，必須同時證明該問題具備「貪婪選擇性質」與「最佳子結構」。兩者缺一不可。
2. 比較 Greedy 與 DP 的適用界線：
   • 檢查決策過程是否需要「回溯」或「列舉所有子問題結果」。若局部最佳選擇可能導致後續空間浪費或無效狀態（如 0/1 背包），則無法使用貪婪演算法。
3. 檢視演算法的邊界假設：
   • 檢視演算法在執行貪婪步驟時的基礎假設。例如 Dijkstra 演算法假設「離開未存取集合的頂點，其距離必為最終最短距離」，當存在負邊時此假設被打破。
4. 確認經典演算法範疇：
   • 熟記常見演算法的設計範式（Greedy, DP, Divide-and-Conquer 等）。Prim 與 Kruskal 演算法在每一步均選取最小權重的邊，符合貪婪演算法定義。

選項分析

• (A) 正確
  分析：一個貪婪演算法能夠保證求得全域最佳解的充要條件是該問題必須同時滿足貪婪選擇性質（Greedy-Choice Property）與最佳子結構（Optimal Substructure）。若缺乏貪婪選擇性質，局部最佳選擇可能會錯失全域最佳解；若缺乏最佳子結構，則子問題的最佳解無法遞迴組合出原問題的最佳解。因此本敘述正確。

• (B) 正確
  分析：

  • 在分數背包問題中，物品可以分割，採用貪婪策略依單位重量價值比值 $r_i = \frac{v_i}{w_i}$ 由大到小排序並優先填入背包，

各選項詳細解析

(A) 正確
最佳化版本為求出最佳值 $O^*$，決策版本為判定是否存在解滿足目標值 $\le k$（或 $\ge k$）。若最佳化版本存在多項式時間演算法求得 $O^*$，只需將 $O^*$ 與門檻值 $k$ 進行 $O(1)$ 時間比對，即可完成決策版本的求解。因此最佳化版本可在多項式時間求解，必然蘊涵決策版本亦可於多項式時間求解。

(B) 正確（註：題幹 $L \in \text{eONP}$ 為 $L \in \text{coNP}$ 之誤植）
若 $L \in \text{NP-hard}$，根據定義，對任意語言 $A \in \text{NP}$ 皆滿足 $A \le_p L$。又已知 $L \in \text{coNP}$，且複雜度類別 $\text{coNP}$ 在多項式時間歸約下具有封閉性（Closed under $\le_p$），故 $A \in \text{coNP}$，推得 $\text{NP} \subseteq \text{coNP}$。兩邊取補集得 $\text{coNP} \subseteq \text{NP}$，綜上可得 $\text{NP} = \text{coNP}$。

(C) 錯誤
設 $A \in \text{NPC}$，其補集 $\bar{A}$ 必為 $\text{coNP}$-complete。

核心觀念

本題旨在考驗漸近記號（Asymptotic Notation）的基本定義、代數性質（如對稱性與遞移性）以及函數成長速率的比較。解答本題需掌握以下標準定義：

1. $O$ 記號（Big-O Notation，漸近上界）：
   $f(n) = O(g(n))$ 表示存在正常數 $c > 0$ 與 $n_0 > 0$，使得對於所有 $n \ge n_0$，恆成立：
   $0 \le f(n) \le c \cdot g(n)$

2. $\Omega$ 記號（Big-Omega Notation，漸近下界）：
   $f(n) = \Omega(g(n))$ 表示存在正常數 $c > 0$ 與 $n_0 > 0$，使得對於所有 $n \ge n_0$，恆成立：
   $0 \le c \cdot g(n) \le f(n)$

3. $\Theta$ 記號（Big-Theta Notation，漸近緊確界）：
   $f(n) = \Theta(g(n))$ 當且僅當 $f(n) = O(g(n))$ 且 $f(n) = \Omega(g(n))$。

4. 漸近符號的轉置對稱性（Transpose Symmetry）：
   $f(n) = O(g(n)) \iff g(n) = \Omega(f(n))$

解題方法

本題為複選題，應採用「定義直接推導」結合「極限檢驗與反例驗證」的策略：

1. 依據定義證明正命題：將選項給予的前提條件帶入 Big-O 與 Big-Theta 的數學定義，利用不等式的運算推導出結論。
2. 構造反例反駁假命題：若命題不成立，只需找出一個滿足前提條件但違反結論的具體函數組合 $f(n)$ 與 $g(n)$ 即可。
3. 最高次項主導原則：評估多項式函數的漸近階數時，當 $n \to \infty$，僅最高次項決定成長速率，低次項與任意有限常數係數均可忽略。

選項分析

• (A) 錯誤

  • 說明：Big-O 表示「漸近上界」（成長速率小於等於），不具備對稱律（Symmetry）。若 $f(n) = O(g(n))$，代表 $f(n)$ 的成長速率不超過 $g(n)$，但不代表 $g(n)$ 的成長速率不超過 $f(n)$。
  • 反例：設 $f(n) = n$，$g(n) = n^2$。當 $n \ge 1$ 時，$n \le 1 \cdot n^2$，故 $n = O(n^2)$ 成立；但不存在正常數 $c$ 使得對所有足夠大的 $n$ 恆有 $n^2 \le c \cdot n$，因此 $n^2 \ne O(n)$。

• (B) 正確

  • 說明：依據 $\Theta$ 記號的定義，$f(n) = \Theta(g(n))$ 充要條件為 $f(n) = O(g(n))$ 且 $f(n) = \Omega(g(n))$。

核心觀念

本題考驗計算複雜度理論中的比較模型下界（Lower Bounds in Comparison-Based Model）、決策樹模型（Decision-Tree Model）、**資訊理論論證（Information-Theoretic Argument）以及計算模型（Computational Model）**對演算法複雜度下界的約束與定義。

1. 比較排序模型與下界：比較型排序演算法僅能透過「比較兩元素大小（如 $a_i \le a_j$）」來確定元素之間的相對順序。在此模型下，排序 $n$ 個相異元素的最壞情況時間複雜度下界為 $\Omega(n \log n)$。
2. 決策樹模型（Decision-Tree Model）：用於描述比較型演算法操作流程的嚴謹模型。輸入規模為 $n$ 的比較排序演算法可對應至一棵二元決策樹：
   • 樹的內部節點（Internal Nodes）代表一次比較操作。
   • 樹的葉節點（Leaves）代表一種可能的輸出排列（Permutation）。
   • 樹的高度（Height $h$）代表最壞情況下的比較次數。
3. 資訊理論論證（Information-Theoretic Argument）：$n$ 個相異元素共有 $n!$ 種可能的全排列組合。每次比較結果為二元選擇（Yes / No），最多僅能提供 1 bit 的資訊。要從 $n!$ 種可能性中確定唯一的正確排列，至少需要 $\log_2(n!)$ 次比較。根據 Stirling 近似公式，$\log_2(n!) = \Omega(n \log n)$。
4. 計算模型限制：演算法的時間複雜度下界嚴格依附於所採用的計算模型與允許的基本操作。若超越比較模型（例如採用 Counting Sort, Radix Sort 等基於鍵值直接索引的非比較型排序），則不受 $\Omega(n \log n)$ 下界的限制。

解題方法

透過決策樹模型與資訊理論推導比較排序演算法的下界步驟如下：

1. 葉節點數與可能排列數：
   處理 $n$ 個相異元素時，共有 $n!$ 種可能的排序結果。為保證演算法對任何輸入皆能正確排序，決策樹的葉節點數量 $L$ 必須涵蓋所有可能排列：
   $L \ge n!$

2. 樹高與最壞情況比較次數：
   高度為 $h$ 的二元決策樹，其最多擁有 $2^h$ 個葉節點，故：
   $2^h \ge L \ge n!$
   兩邊取以 2 為底的對數得到樹高 $h$ 的下界：
   $h \ge \log_2(n!)$

3. Stirling 近似推導：
   利用對數性質與 Stirling 公式展開：
   $\log_2(n!) = \sum_{i=1}^{n} \log_2 i \ge \sum_{i=\lfloor n/2 \rfloor}^{n} \log_2 i \ge \left( \frac{n}{2} \right) \log_2 \left( \frac{n}{2} \right) = \Omega(n \log n)$

核心觀念

本題考查圖論（Graph Theory）中「單源最短路徑」（Single-Source Shortest Path, SSSP）與「全對最短路徑」（All-Pairs Shortest Path, APSP）的核心演算法、負權邊（Negative-weight edges）與負權環（Negative-weight cycles）對路徑長度定義及演算法正確性的影響，以及各最短路徑演算法的時間複雜度與負環偵測機制。

涉及的重點理論與定理包含：

1. Dijkstra 演算法：採用貪婪策略（Greedy Strategy）。若圖中包含負權邊，已選定為最短距離的頂點可能會被後續的負權邊鬆弛（Relax），破壞貪婪選擇性質（Greedy Choice Property），導致演算法失效。
2. Bellman-Ford 演算法：採用動態規劃思想，對所有邊進行 $V-1$ 輪鬆弛操作。若在第 $V$ 輪鬆弛時仍有邊可被更新，即代表圖中存在從源點可達的負權環。
3. 負權環（Negative-weight cycle）對最短路徑的影響：若源點可達某負權環，且該負權環可達目標頂點，則繞行該環無限次可使路徑總權重趨近於 $-\infty$，導致最短路徑長度無下界，即「未妥善定義」（Not well-defined）。
4. Floyd-Warshall 演算法：採用動態規劃解 APSP 問題，時間複雜度為 $O(V^3)$。演算法結束後，若對角線元素滿足 $d[i][i] < 0$，表示頂點 $i$ 位於某負權環上或可達負權環，可用於偵測負權環。
5. 全對最短路徑的時間複雜度：常見演算法的時間複雜度包含 Floyd-Warshall 的 $O(V^3)$、重複執行 $V$ 次 Bellman-Ford 的 $O(V^2 E)$，以及 Johnson 演算法的 $O(V^2 \log V + VE)$。

解題方法

依據單源與全對最短路徑演算法的設計前提、鬆弛機制、負環判定定理與時間複雜度理論，對各選項進行邏輯推導與正確性判定。

選項分析

• (A) 正確。Dijkstra 演算法的貪婪策略建立在「所有邊權重非負」（$w(u, v) \ge 0$）的假設上。在此假設下，當一個頂點從未造訪集合中被挑出並加入確定集合時，其當前估計值即為最終最短距離。若圖中存在負權邊，已確定最短距離的頂點可能透過後續延伸出的負權邊獲得更短的路徑，導致 Dijkstra 演算法計算出錯誤的結果。
• (B) 正確。

選項解析

• (A) 正確：分支限界法（Branch-and-Bound）建立搜尋樹進行系統化探索，並藉由計算各節點的邊界值（bound）實施剪枝（pruning），剔除不可能包含最佳解的枝葉以縮小搜尋範圍。
• (B) 正確：A* 演算法採用評估函數 $f(n) = g(n) + h(n)$ 作為搜尋優先權。當啟發式函數 $h(n)$ 具備可採納性（admissible）時，即代表剩餘成本的下界估計，故 A* 可被視為最佳優先分支限界法（Best-First Branch-and-Bound）的一種特例。

核心觀念

本題考查**中位數之中位數演算法（Median-of-Medians Algorithm，亦稱 Select 演算法）與減治法（Prune-and-Search / Divide-and-Conquer）**的分析。重點包含：

1. 中位數選取與剪枝下界推導：透過將陣列劃分為固定大小的子組（如每 5 個一組），利用各組中位數的中位數 $m$ 作為樞軸（Pivot），保證每次剪枝至少能排除固定比例的元素（約 $3n/10$）。
2. 遞迴關係式（Recurrence Relation）與時間複雜度：評估遞迴式的解是否滿足最壞情況線性時間 $O(n)$。
3. 分組大小對複雜度的影響：分析為何每組大小選擇 5 能保證 $O(n)$，而選擇 3 則無法。
4. 演算法正確性（Correctness）與執行效率（Efficiency）的區別：區分 Pivot 的品質是影響時間複雜度還是演算法答案的正確性。

解題方法

1. 剪枝比例與下界推導

設陣列元素個數為 $n$，將其劃分為 $g = \lceil n/5 \rceil$ 個組別（每組 5 個元素）。
取得每組的中位數後，遞迴求出這些中位數的中位數 $m$：

• 在 $g$ 個組中位數中，至少有包含 $m$ 在內的 $\lceil g/2 \rceil \approx n/10$ 個組別的中位數大於等於 $m$。
• 對於每一個中位數大於等於 $m$ 的組別，該組內包含中位數本身以及比中位數大的 2 個元素，共計 3 個元素皆大於等於 $m$。
• 因此，整個陣列中保證大於等於 $m$ 的元素個數至少為：
  $3 \times \left( \left\lceil \frac{1}{2} \left\lceil \frac{n}{5} \right\rceil \right\rceil - 2 \right) \ge \frac{3n}{10} - 6 \approx \frac{3n}{10}$
• 同理，保證小於等於 $m$ 的元素個數亦至少為 $3n/10$。
• 剪枝後進入下一次遞迴的最大子陣列大小至多為 $n - \frac{3n}{10} = \frac{7n}{10}$。

2. 時間複雜度遞迴式推導

Algorithm Select 的最壞情況執行時間 $T(n)$ 可拆解為三個部分：

1. 找出各組中位數與 Partition 劃分：$O(n)$。
2. 遞迴尋找中位數之中位數 $m$：$T(n/5)$。
3. 剪枝後對剩餘子陣列遞迴尋找：至多 $T(7n/10)$。

整理得到遞迴關係式：
$T(n) = T(n/5) + T(7n/10) + O(n)$

使用代入法（Substitution Method）驗證是否存在常數 $c > 0$ 使得 $T(n) \le c n$：
$T(n) \le c \left(\frac{n}{5}\right) + c \left(\frac{7n}{10}\right) + d n = c \cdot \frac{9n}{10} + d n$
若要使 $c \cdot \frac{9n}{10} + d n \le c n$，只需取 $c \ge 10d$ 即可成立。
因為 $\frac{1}{5} + \frac{7}{10} = \frac{9}{10} < 1$，遞迴樹每層的總工作量呈等比級數遞減，故 $T(n) = O(n)$。

選項分析

• (A) 正確
  根據上述推導，在每 5 個元素一組的設定下，共有約 $n/5$ 個小組。其中至少有一半（約 $n/10$ 個小組）的中位數大於等於 $m$。

核心觀念

拓樸排序要求每條有向邊 $u \to v$ 的起點 $u$ 都排在終點 $v$ 前面。判斷選項時，逐條檢查圖中的先後限制即可。

AOE 網路的活動位於邊上，關鍵路徑則是從起點到終點、總工期最長的路徑。若每條邊代表的活動都需一天，路徑工期就是邊數。

解題方法

由圖可讀出邊的方向：

檢查拓樸排序時，確認每條邊的起點都排在終點之前；比較關鍵路徑時，則列出起點 $A$ 到終點 $F$ 的路徑並比較工期。

選項分析

(A) 錯誤。 排序 ACEGFBD 中，$C$ 排在 $B$ 前面，違反邊 $B \to C$；$G$ 也排在 $D$ 前面，違反邊 $D \to G$。因此不是合法的拓樸排序。

核心觀念

雜湊函數為

發生碰撞時：

• 線性探測（linear probing）：依序檢查下一個 bucket。
• 二次探測（quadratic probing）：第 $i$ 次探測位置為

依考卷圖片，最後的雜湊表為：

各鍵值的雜湊位置為：

解題方法

依各選項給定的輸入順序逐一插入，最後比較是否得到考卷中的表格。

以序列

為例。

採用線性探測：

1. $27$ 放入 bucket $5$。
2. $37$ 放入 bucket $4$。
3. $16$ 原本要放 bucket $5$，碰撞後放入 bucket $6$。
4. $17$ 原本要放 bucket $6$，碰撞後放入 bucket $7$。
5. $15$ 原本要放 bucket $4$，依序檢查 $5,6,7$，放入 bucket $8$。
6. $38$ 原本要放 bucket $5$，依序檢查 $6,7,8$，放入 bucket $9$。
7. $57$ 放入 bucket $2$。
8. $24$ 原本要放 bucket $2$，碰撞後放入 bucket $3$。

所得結果正好是：

採用二次探測時：

核心觀念

最小生成樹（MST）是連通所有頂點且總權重最小的樹，因此若圖有 $7$ 個頂點，MST 恰有 $6$ 條邊。

• Kruskal 演算法：依邊權重由小到大檢查，只加入不會形成環的邊。
• Prim 演算法：從指定頂點出發，每次加入一條連接「已加入頂點」與「尚未加入頂點」的最小權重邊。
• 二元樹：根節點選定後，每個節點至多有兩個子節點。

解題方法

Kruskal 演算法

將邊依權重排序：

依序加入不形成環的邊：

此時已加入 $6$ 條邊，所有頂點都連通，得到 MST。

Prim 演算法，從 $C$ 出發

每步加入的邊依序為：

所以 $(E,G)$ 是第 $5$ 條加入 MST 的邊。

Prim 演算法，從 $D$ 出發

每步加入的邊依序為：

核心觀念

1. 快速排序法（Quick Sort）與分割演算法（Partition Algorithm）：

   • Quick Sort 採用分治法（Divide and Conquer）。第一階段（First Phase / Partition）選定一個 Pivot（樞紐碼）後，將小於等於 Pivot 的元素置於左區塊，大於 Pivot 的元素置於右區塊，最後將 Pivot 放回兩區塊之間的正確位置。
   • 國內資訊研究所考試預設採用經典的 Horowitz Partitioning Algorithm（Ellis Horowitz《Fundamentals of Data Structures》標準）：
     • 設定指標 $i$ 從左端往右掃描（尋找 $> \text{Pivot}$ 者）。
     • 設定指標 $j$ 從右端往左掃描（尋找 $\le \text{Pivot}$ 者）。
     • 當 $i$ 與 $j$ 皆停止時交換 $A[i]$ 與 $A[j]$，重複此過程直到 $i \ge j$，最後將 Pivot 與 $A[j]$ 交換。

2. 最低有效位數基數排序法（LSD Radix Sort）：

   • LSD（Least Significant Digit）Radix Sort 由最低位數（個位數）開始，向最高位數依次進行穩定排序（Stable Sort），通常搭配 10 個 Bucket（0～9）進行收集與搬移。
   • 給定資料的最大值為 $119$（共 3 位數），因此總共需執行 3 個回合（Passes）：
     • Pass 1：依個位數（$x \pmod{10}$）分桶排序。
     • Pass 2：依十位數（$\lfloor x / 10 \rfloor \pmod{10}$）分桶排序。
     • Pass 3：依百位數（$\lfloor x / 100 \rfloor \pmod{10}$）分桶排序。

解題方法

給定原始陣列 $A = [9, 7, 15, 6, 11, 4, 22, 119]$（共 8 個元素）。

1. Quick Sort 第一階段 Partition 推導

• Pivot 選擇第一個元素 $9$：

  • 初始陣列：$[9, 7, 15, 6, 11, 4, 22, 119]$，Pivot $p = 9$。
  • 指標 $i$ 從 $A[1]$ 開始右移，指標 $j$ 從 $A[8]$ 開始左移：
    • $i$ 往右尋找 $> 9$ 的元素：$A[1]=9 \le 9$, $A[2]=7 \le 9$, 停在 $A[3]=15 > 9$（$i=3$）。
    • $j$ 往左尋找 $\le 9$ 的元素：$A[8]=119 > 9$, $A[7]=22 > 9$, 停在 $A[6]=4 \le 9$（$j=6$）。
    • 交換 $A[3]$ 與 $A[6]$ $\Rightarrow$ 陣列變為 $[9, 7, 4, 6, 11, 15, 22, 119]$。
  • 繼續掃描：
    • $i$ 繼續右移：$A[3]=4 \le 9$, $A[4]=6 \le 9$, 停在 $A[5]=11 > 9$（$i=5$）。
    • $j$ 繼續左移：$A[6]=15 > 9$, $A[5]=11 > 9$, 停在 $A[4]=6 \le 9$（$j=4$）。
  • 此時 $i = 5 \ge j = 4$，迴圈結束。
  • 將 Pivot $A[1]$ ($9$) 與 $A[j]$ ($A[4]=6$) 交換 $\Rightarrow$ 最終序列為 $[6, 7, 4, 9, 11, 15, 22, 119]$。

• Pivot 選擇第二個元素 $7$：

  • 將 Pivot ($7$) 交換至首位 $\Rightarrow$ 初始陣列變為 $[7, 9, 15, 6, 11, 4, 22, 119]$，Pivot $p = 7$。
  • $i$ 掃描停在 $A[2]=9 > 7$ ($i=2$)；$j$ 掃描停在 $A[6]=4 \le 7$ ($j=6$)。
  • 交換 $A[2]$ 與 $A[6]$ $\Rightarrow [7, 4, 15, 6, 11, 9, 22, 119]$。
  • $i$ 繼續掃描停在 $A[3]=15 > 7$ ($i=3$)；$j$ 繼續掃描停在 $A[4]=6 \le 7$ ($j=4$)。
  • 交換 $A[3]$ 與 $A[4]$ $\Rightarrow [7, 4, 6, 15, 11, 9, 22, 119]$。

1. 初始紅黑樹狀態推導

依 Level Order Traversal $52, 33, 80, 100$ 建構二元搜尋樹結構：

• $52$ 為根節點，依紅黑樹性質必為黑色。
• 檢視各葉節點（$\text{NIL}$）至根節點的路徑黑高度（Black-Height）：
  • 若 $80$ 為紅色，則 $100$ 必為黑色（不可有連續紅節點），導致右子樹長路徑之黑高度大於短路徑，違反紅黑樹性質；故 $80$ 必為黑色，$100$ 必為紅色。
  • 為使左子樹（$33$ 方向）黑高度與右子樹一致，$33$ 必為黑色。
• 初始節點顏色：$52(\text{黑})$、$33(\text{黑})$、$80(\text{黑})$、$100(\text{紅})$。
• (A) 錯誤：節點 $33$ 為黑色。

2. 依序插入節點之動態調整

Step 1：插入 $65$

$65$ 為 $80$ 之左子節點，預設顏色為紅色。

• 父節點 $80$ 為黑色，無連續紅節點違規，無需調整。

Step 2：插入 $55$（驗證選項 B）

$55$ 為 $65$ 之左子節點，預設顏色為紅色。

• 出現 Double Red 違規：新節點 $55(\text{紅})$、父節點 $P=65(\text{紅})$、叔節點 $U=100(\text{紅})$、祖父節點 $G=80(\text{黑})$。
• Case 1 處理（叔節點為紅）：
  1. 將父節點 $P(65)$ 與叔節點 $U(100)$ 改塗為黑色。
  2. 將祖父節點 $G(80)$ 改塗為紅色。
• 調整後節點 $100$ 之顏色變為黑色。

核心觀念

本題考驗中序（Infix）、後序（Postfix）與前序（Prefix）算術運算式的相互轉換，以及運算樹（Expression Tree）與堆疊（Stack）的應用。

1. 中序運算式（Infix）：運算子位於兩個運算元中間，例如 $A + B$。計算時需依循括號優先權與運算子優先順序（如乘除優先於加減）。
2. 後序運算式（Postfix）：運算子位於兩個運算元之後，例如 $A B +$。不需括號即可明確表示計算順序，適合利用堆疊進行求值。
3. 前序運算式（Prefix）：運算子位於兩個運算元之前，例如 $+ A B$。同樣不需括號即可表達正確的計算順序。
4. 運算樹（Expression Tree）：運算式可表示為二元樹結構，其中內部節點（Internal Nodes）為運算子，葉節點（Leaves）為運算元。對運算樹進行中序追蹤（In-order Traversal）、後序追蹤（Post-order Traversal）與前序追蹤（Pre-order Traversal），可分別得到相應的中序、後序與前序運算式。

解題方法

1. 括號法（Infix 轉 Postfix / Prefix）：

   • 步驟一：依據運算子優先順序與結合律，將整體運算式補齊所有括號。
   • 步驟二（轉後序）：將每個運算子移動到對應右括號的外側，最後將所有括號刪除。
   • 步驟三（轉前序）：將每個運算子移動到對應左括號的外側，最後將所有括號刪除。

2. 堆疊建置法（Postfix 轉 Infix / Prefix）：

   • 由左至右依次掃描後序運算式：
     • 若遇到運算元：推入（Push）堆疊。
     • 若遇到運算子：自堆疊頂端彈出（Pop）兩個元素，先彈出者為右運算元 $Op_2$，後彈出者為左運算元 $Op_1$。將其組合成對應的中序式 $(Op_1 \text{ 運算子 } Op_2)$ 或前序式 $(\text{運算子 } Op_1 \ Op_2)$ 後推回堆疊。
   • 掃描完畢後，堆疊頂端的元素即為最終轉換結果。

選項分析

• (A) 錯誤
  • 已知中序運算式：$(A+(B/(C-D)))$
  • 推導步驟：
    1. 處理最內層括號：$(C-D) \rightarrow CD-$
    2. 處理除法運算：$(B / (CD-)) \rightarrow B CD- /$
    3. 處理加法運算：$(A + (B CD- /)) \rightarrow A B CD- / +$
  • 正確結果：正確後序表示法應為 $ABCD-/+$。

核心觀念

本題比較四種容器的操作規則：

• Stack（堆疊）：後進先出，push 從頂端加入，pop 移除頂端。
• Queue（佇列）：先進先出，push 從 rear 加入，pop 從 front 移除。
• Min heap（最小堆積）：每次 pop 移除最小值。
• Max heap（最大堆積）：每次 pop 移除最大值。

依考卷圖中的實際程式碼，最後三個操作為：

container.push('C');
container.push('U');
container.pop();

並非 push('D')。

解題方法

先依序執行程式：

push T, pop
push L, push O, push V, pop
push E, push N, pop
push C, push U, pop

第一組 T 立即被移除，之後分別依各容器規則模擬。

選項分析

(A) Standard stack

堆疊內容變化如下，左側為 bottom、右側為 top：

push L → L
push O → L O
push V → L O V
pop    → L O
push E → L O E
push N → L O E N
pop    → L O E
push C → L O E C
push U → L O E C U
pop    → L O E C

最後由 top 到 bottom 應為：

C, E, O, L

不是 L, O, E, C，故 (A) 錯誤。

(B) Standard queue

佇列由 front 到 rear：

根據中序走訪（Inorder: I L O V E N C U）與後序走訪（Postorder: L I V N U C E O）重建二元樹：

1. 二元樹重建步驟

1. 確定樹根（Root）：
   後序走訪最後一個節點為 $O$，故全樹的根節點為 $O$。
2. 劃分左右子樹：
   在中序走訪中，$O$ 左側為左子樹 I L，右側為右子樹 V E N C U。
   • 左子樹：
     • 中序：I L，後序：L I。
     • 後序最後節點為 $I$，故 $I$ 為 $O$ 的左子節點；中序顯示 $L$ 在 $I$ 右側，故 $L$ 為 $I$ 的右子節點。
   • 右子樹：
     • 中序：V E N C U，後序：V N U C E。
     • 後序最後節點為 $E$，故 $E$ 為 $O$ 的右子節點。
     • 中序中 $E$ 左側為 $V$，右側為 N C U：
       • $V$ 為 $E$ 的左子節點。

核心觀念

本題考二元樹的結構計數。左右子樹的位置有區別，因此左子樹和右子樹互換時，視為不同結構。這類結構數由卡特蘭數（Catalan number）計算。

令 $C_n$ 表示含 $n$ 個節點的結構不同二元樹數量，空樹有 $C_0=1$ 種。根節點固定後，若左子樹有 $i$ 個節點，右子樹便有 $n-1-i$ 個節點，因此：