112 年 國立臺灣大學資料科學碩士學位學程《資料結構與演算法》

第 1 題 詳解

---

核心觀念

本題考察各排序演算法在不同應用場景下的時間複雜度與行為特性，需掌握：

• Merge Sort：穩定排序，worst-case $O(n \log n)$，需 $O(n)$ 額外空間。
• Bubble Sort：最佳情況（已排序）可達 $O(n)$，worst-case $O(n^2)$。
• Quick Sort：平均 $O(n \log n)$，worst-case $O(n^2)$（例如 pivot 每次選到最大／最小值）。
• Selection Sort：無論輸入為何，交換次數最多 $O(n)$ 次（每輪至多一次 swap），比較次數永遠 $O(n^2)$。
• Radix Sort：非比較排序，time complexity 需由 digit 數與 radix 決定。

---

解題方法

逐一驗證每個選項所述的「場景」與「排序演算法特性」是否相符。關鍵是將場景條件（最壞情況 / 已排序輸入 / 隨機輸入 / 交換昂貴 / 整數範圍）對應到各演算法真正的行為，而非只背誦「平均複雜度」。

---

選項分析

---

(A) ✅ 正確

若最壞情況執行時間最重要，Merge Sort 是好選擇，worst-case $O(n \log n)$。

Merge Sort 的時間複雜度在任何輸入下均為 $O(n \log n)$，無論輸入已排序、逆序或隨機，遞迴分割與合併的步驟數不受輸入分佈影響。其遞迴關係為：

$T(n) = 2T\!\left(\frac{n}{2}\right) + O(n) \implies T(n) = O(n \log n)$

相較之下，Quick Sort 的 worst-case 為 $O(n^2)$，Heap Sort 雖然 worst-case 同為 $O(n \log n)$，但 Merge Sort 仍是「保證 $O(n \log n)$」的典型代表之一。(A) 敘述正確。

---

(B) ✅ 正確

若輸入已是排序狀態，Bubble Sort 是好選擇，best-case $O(n)$。

標準的 Bubble Sort（附有「若本輪無交換則提前結束」的最佳化旗標）在輸入已排序時，只需掃描一次 $n-1$ 對相鄰元素，確認無需交換即結束，時間複雜度為 $O(n)$。

此條件限定「輸入恰好已排序」，Bubble Sort 在此特例下確實表現最優。(B) 敘述正確。

---

(C) ✅ 正確

若輸入隨機且平均排序時間最重要，Quick Sort 是好選擇，average-case $O(n \log n)$。

Quick Sort 的平均時間複雜度分析：假設 pivot 每次將資料分成大致相等的兩半（在隨機輸入下此假設成立），遞迴關係同樣為：

$T(n) = 2T\!\left(\frac{n}{2}\right) + O(n) \implies T(n) = O(n \log n)$

更嚴格的平均分析（對所有 $n!$ 種排列取期望）可得平均比較次數約為 $2n \ln n \approx 1.39 n \log_2 n$。Quick Sort 的常數因子小（cache-friendly、in-place），在隨機輸入下實務效能往往優於 Merge Sort 與 Heap Sort。(C) 敘述正確。

---

(D) ✅ 正確

核心觀念

B+ 樹的內部節點只存放分隔鍵，實際資料存於葉節點。判斷圖中的違規，須同時檢查兩項規則：

1. 節點的最低容量：內部節點有 $k$ 個鍵，就有 $k+1$ 個子節點。本題每個節點最多有 $4$ 個鍵，因此內部節點最多有 $5$ 個子節點；非根內部節點至少須有

   $$\left\lceil\frac{5}{2}\right\rceil=3$$

   個子節點，也就是至少 $2$ 個鍵。根節點可例外，因此圖中的根只有一個鍵 $20$，仍屬合法。

2. 分隔鍵的範圍限制：題目明定，分隔鍵左側的資料必須嚴格小於該鍵，右側則大於或等於該鍵。此限制適用於整個子樹，而且必須同時遵守所有祖先節點給定的範圍。

解題方法

原圖的根節點為 $20$，左子節點為 $10$，右子節點為 $30,40$；虛線框標示的五個選項依序是 (A) $10$、(B) $13,20$、(C) $20,21$、(D) $22,23$、(E) $30,31$。以下以原圖標示作答。

先由根節點往下傳遞範圍：

• 根的左子樹：所有資料必須小於 $20$。
• 根的右子樹：所有資料必須大於或等於 $20$。
• 右側節點 $30,40$ 的三個子樹，範圍依序為 $[20,30)$、$[30,40)$、$[40,\infty)$。

再逐一檢查虛線框中的節點是否符合容量與範圍限制。

選項分析

(A) $10$：違規，應選。

這是非根內部節點，卻只有一個鍵 $10$、兩個子節點，低於「至少兩個鍵、三個子節點」的要求。即使其分隔作用符合局部大小關係，仍因容量不足而違規。

(B) $13,20$：違規，應選。

核心觀念

霍夫曼編碼每次選取目前權重最小的兩個節點合併，直到形成一棵二元樹。符號的碼字長度，就是從根節點走到該符號葉節點所經過的邊數；機率越小的符號通常會有越長的碼字。

解題方法

依機率由小到大，逐次合併兩個最小權重：

1. 合併 $G(0.03)$ 與 $B(0.06)$，得到權重 $0.09$。
2. 合併 $E(0.09)$ 與 $(G,B)(0.09)$，得到權重 $0.18$。
3. 合併 $A(0.15)$ 與權重 $0.18$ 的節點，得到權重 $0.33$。
4. 合併 $D(0.21)$ 與 $F(0.21)$，得到權重 $0.42$。
5. 合併 $C(0.24)$ 與權重 $0.33$ 的節點，得到權重 $0.57$。
6. 最後合併權重 $0.42$ 與 $0.57$，形成根節點。

由合併結構可得各符號的碼字長度：

核心觀念

本題考查 DFS（深度優先搜尋） 與 BFS（廣度優先搜尋） 在遍歷二元樹時的最差情況空間複雜度（worst-case space complexity），以及平衡二元樹（balanced binary tree） 與一般二元樹（general binary tree） 在結構上的本質差異。

關鍵定義與事實：

• DFS 的空間來源：遞迴呼叫堆疊（call stack），其深度等於樹的高度 $h$。空間複雜度為 $O(h)$。
• BFS 的空間來源：輔助佇列（queue），其最大容量等於樹在某一層的最大節點數（即最大寬度 $w$）。空間複雜度為 $O(w)$。
• 平衡二元樹的高度：$h = O(\log N)$，因此最大寬度 $w = O(N)$（最底層可達 $\lceil N/2 \rceil$ 個節點）。
• 一般二元樹的高度：最差情況為退化成鏈狀（linked list），$h = O(N)$，此時每層只有一個節點，寬度 $w = O(1)$。

---

解題方法

對每個敘述，分別套用「DFS → 分析高度 $h$」或「BFS → 分析最大寬度 $w$」的框架，再依據樹的類型（平衡 vs. 一般）代入對應的上界。

---

選項分析

敘述一：Using DFS to traverse a balanced binary tree takes $O(N)$

DFS 的空間 $= O(h)$。平衡二元樹的高度 $h = O(\log N)$，因此空間複雜度為 $O(\log N)$，不是 $O(N)$。

→ 此敘述為「FALSE」。

---

敘述二：Using DFS to traverse a binary tree (一般二元樹) takes $O(N)$

DFS 的空間 $= O(h)$。一般二元樹在最差情況下退化為一條鏈（每個節點只有一個子節點），高度 $h = N - 1 = O(N)$，呼叫堆疊最深達 $O(N)$。因此最差情況空間複雜度確實為 $O(N)$。

→ 此敘述為「TRUE」。

---

敘述三：Using BFS to traverse a balanced binary tree takes $O(N)$

BFS 的空間 $= O(w)$，$w$ 為最大層寬度。對於平衡二元樹，最底層（第 $h$ 層）的節點數最多，約為 $\lceil N/2 \rceil$ 個節點，因此：

核心觀念

本題考查的核心概念有兩個：

1. N-way merge 的演算法設計：如何將 $N$ 個已排序陣列合併為一個排序陣列，並選擇正確的資料結構。
2. Min-Heap（最小堆積）的操作複雜度：Min-Heap 是實作 N-way merge 的標準工具，其 insert 與 extract-min 均為 $O(\log N)$，build-heap 為 $O(N)$。

關鍵事實整理：

操作	時間複雜度
Build-heap（對大小為 $N$ 的堆積）	$O(N)$
Extract-min	$O(\log N)$
Insert	$O(\log N)$

---

解題方法

問題規模確認

• $N$：陣列個數
• $M$：每個陣列中的整數個數
• 總元素數：$N \times M$

標準演算法：Min-Heap 輔助的 N-way Merge

步驟一：初始化 Min-Heap

從每個陣列各取出第一個元素（共 $N$ 個元素），連同「來自哪個陣列、目前指向哪個位置」的指標資訊，一起放入 Min-Heap。

$\text{Build-Heap}(\text{大小為 } N) \Rightarrow O(N)$

步驟二：反覆執行 Extract-min + Insert

每一輪執行：

1. 從 Min-Heap 取出最小元素，輸出至結果陣列。（$O(\log N)$）
2. 從該元素所在的原始陣列，取出下一個元素，插入 Min-Heap。（$O(\log N)$）

此步驟重複執行，直到所有元素都被取出為止。

步驟三：計算總次數

• 總輸出元素數 $= N \times M$
• 每次輸出皆需一次 Extract-min 與（最多）一次 Insert，各耗 $O(\log N)$

$T(N, M) = O(N) + N \cdot M \cdot O(\log N) = O(NM \log N)$

其中 $O(N)$ 的 Build-Heap 被 $O(NM \log N)$ 吸收，不影響漸近複雜度。

---

選項分析

(A) $O(N \log M)$

錯誤。 此式完全忽略了每個陣列內的元素數 $M$ 對「總輸出次數」的影響。若 $M$ 極大，此式將嚴重低估複雜度。正確答案中 $NM$ 項（總元素數）是不可或缺的。

(B) $O(NM \log M)$

核心觀念

二元樹中節點的中序後繼，是中序走訪序列中緊接在該節點之後的節點。若節點有右子樹，後繼是右子樹中最左側的節點。

判斷 AVL 的高度平衡條件時，每個節點都必須滿足：

$$\left|h(\text{左子樹})-h(\text{右子樹})\right|\leq 1$$

本題說明字母是節點名稱，因此不以字母順序判斷鍵值大小；以下依圖檢查高度平衡。

解題方法

依圖中的左右子樹做中序走訪，順序為：

$$D,\ H,\ B,\ E,\ I,\ A,\ J,\ F,\ C,\ K,\ G,\ L,\ M$$

因此，$B$ 的中序後繼是 $E$；$A$ 的中序後繼是 $J$。

接著由葉節點往上計算高度。刪除前，$D$、$E$、$F$、$L$ 的高度各為 $2$，$B$ 的高度為 $3$，$G$ 的高度為 $3$，$C$ 的高度為 $4$，根節點 $A$ 的高度為 $5$。各節點左右子樹高度差皆不超過 $1$。

核心觀念

中序走訪的順序是「左子樹、根節點、右子樹」。將走訪得到的 0、1 序列視為二進位數，先轉成十進位，再對雜湊表長度 $11$ 取餘數：

$$f(t)=g(h(t))\bmod 11$$

線性探測遇到已占用位置時，依序檢查下一格，直到找到空位。

解題方法

依圖中各樹的中序走訪結果計算起始位置：

樹	中序二進位序列 $h(t)$	十進位值	起始位置
$t_1$	$0010110$	$22$	$0$
$t_2$	$0000100$	$4$	$4$
$t_3$	$0001111$	$15$	$4$
$t_4$	$0011100$	$28$	$6$
$t_5$	$0010001$	$17$	$6$
$t_6$	$1011000$	$88$	$0$
$t_7$	$0111100$	$60$	$5$

依 $t_1$ 到 $t_7$ 的順序插入：

第 8 題｜Postfix notation 的優點（複選題）

---

核心觀念

本題考查三種數學運算式表示法（Notation）的基本性質與比較：

表示法	說明	範例（$a + b \times c$）
Infix（中序）	運算子在兩運算元之間	$a + b \times c$
Prefix（前序／波蘭表示法）	運算子在運算元之前	$+ \ a \ \times \ b \ c$
Postfix（後序／逆波蘭表示法，RPN）	運算子在運算元之後	$a \ b \ c \ \times \ +$

Postfix 的核心特性源自以下事實：運算子的「作用對象」已由其在字串中的相對位置完全決定，不需要任何額外的優先順序規則或括號，就能唯一地還原出運算樹（expression tree）。

---

解題方法

對於「優點比較」類型的選擇題，切入點是對每個選項進行反例法或原理驗證：

• 若能找到一個「使用 postfix 反而不符合該描述」的例子，則該選項錯誤。
• 若能從 postfix 的結構原理出發，說明該描述必然成立，則該選項正確。

Postfix 最關鍵的結構原理：運算子的計算順序由左到右、遇到運算子就取前兩個運算元計算，整個過程僅需一個 stack，不需回頭查詢優先順序，也不需括號。

---

選項分析

(A) No need to use parentheses ✅ 正確

Infix 在表達非預設優先順序的運算時必須使用括號。例如：

$a \times (b + c) \quad \text{（infix，括號不可省）}$

轉為 postfix 後：

$a \ b \ c \ + \ \times$

括號資訊已被隱含於運算子的位置順序中，完全不需要括號符號。此特性是 postfix（及 prefix）相對於 infix 的最顯著優勢。

---

(B) No need to consider precedence of operators ✅ 正確

在 infix 表示法中，電腦（或人）讀到 $a + b \times c$ 時，必須先查詢「$\times$ 優先於 $+$」才能決定先計算 $b \times c$。

Postfix 將這個優先順序資訊在轉換階段一次性編碼進字串順序（例如 Dijkstra 的 shunting-yard 演算法），之後執行時只需：

1. 從左到右掃描。
2. 遇到運算元 → push 進 stack。
3. 遇到運算子 → pop 兩個運算元計算，結果 push 回 stack。

整個執行迴圈無需任何優先順序表，因為順序已固定在字串本身。

---

(C) Easier for human to read ❌ 錯誤

人類從小學習 infix 表示法（$3 + 4 \times 2$），對中序的閱讀是直覺的。

Postfix 對多數人而言反直覺，例如：

$8 \ 2 \ 3 \ + \ \times \quad \Rightarrow \quad 8 \times (2 + 3) = 40$

核心觀念

本題考查兩個層面：

1. 八皇后問題（Eight-Queen Problem）的本質：在 $8 \times 8$ 棋盤上放置 8 個皇后，使任意兩個皇后都不互相攻擊（不同行、不同列、不同對角線）。這是一個典型的約束滿足問題（Constraint Satisfaction Problem, CSP），通常以**回溯法（Backtracking）**搭配搜尋樹求解。

2. DFS 與 BFS 的特性比較：兩者皆可對搜尋樹進行遍歷，但空間複雜度、到達葉節點的速度，以及與回溯法的相容性截然不同。

搜尋樹的結構：每一層對應棋盤的一行（row），每個節點的子節點對應在該行可放置皇后的各欄（column）。深度為 8 的葉節點即為候選解，必須進一步驗證是否合法。

---

解題方法

對八皇后問題而言，我們關心的是「找到一個可行解（feasible solution）」，不需要找出所有解，也不需要找最短路徑。分別從記憶體用量、到達終止狀態的速度、實作方式三個角度分析 DFS 與 BFS 的差異：

記憶體比較

設搜尋樹的分支因子（branching factor）為 $b$，最大深度為 $d$。

演算法	記憶體用量
BFS	$O(b^d)$（需儲存當前層所有節點）
DFS	$O(b \cdot d)$（每層只需儲存一條路徑上的節點及其兄弟節點）

八皇后問題中 $b \approx 8$，$d = 8$，BFS 最壞需儲存 $8^8 = 16{,}777{,}216$ 個節點，DFS 只需儲存 $O(8 \times 8) = O(64)$ 個節點。

到達終止狀態的速度

DFS 一路向下推進，能迅速抵達深度為 $d$ 的葉節點（終止狀態），並立即判斷是 "good"（可行解）或 "bad"（違反約束）。BFS 則必須展開整層所有節點後才能推進到下一層，到達葉節點前需處理大量中間節點。

與回溯法的相容性

八皇后的標準解法是 DFS + 回溯（Backtracking）：發現某條路徑違反約束時，立即剪枝並退回上一層，大幅降低搜尋空間。BFS 的逐層展開策略與回溯法天然不相容，無法直接利用此剪枝機制。

---

選項分析

(A) DFS is more memory efficient. ✅ 正確

DFS 使用**堆疊（Stack）儲存當前路徑，空間複雜度為 $O(b \cdot d)$；BFS 使用佇列（Queue）**儲存當前層所有節點，空間複雜度為 $O(b^d)$。在樹深度固定的情況下，$b \cdot d \ll b^d$，DFS 的記憶體效率遠優於 BFS。此為選擇 DFS 的重要理由，選項正確。

---

(B) DFS can be implemented using a stack. ❌ 不構成選擇 DFS 的理由

第 10 題　Heap 的應用場景

---

核心觀念

本題考察堆積（Heap）資料結構在各類實際問題中的適用性。需要掌握以下前提知識：

• Heap 的基本性質：完全二元樹，支援 $O(\log n)$ 的插入（insert）與刪除最大／最小值（extract-max / extract-min）；peek 最大／最小值為 $O(1)$。
• Min-Heap / Max-Heap：分別讓根節點維持最小值或最大值。
• 判斷題目核心：「這個問題是否需要反覆找第 $k$ 大／小的元素？」或「是否需要維護一個動態有序的優先序列？」若是，Heap 幾乎必然能大幅改善時間複雜度。

---

解題方法

對每個選項，先問自己兩個問題：

1. 這個問題的瓶頸操作是什麼？
2. Heap 能否把該操作從 $O(n)$ 或更差降至 $O(\log n)$？

若答案是肯定的，該選項即為正確答案。

---

選項分析

---

(A) 從數字串流中找出前 $k$ 大的數 ✅

演算法設計：

維護一個大小為 $k$ 的 Min-Heap。對每個新進來的數字 $x$：

• 若 Heap 元素數 $< k$，直接插入。
• 若 $x >$ Heap 的最小值（即根節點），彈出根節點，插入 $x$。
• 否則捨棄 $x$。

處理完所有串流後，Heap 中剩下的 $k$ 個元素即為前 $k$ 大。

時間複雜度分析：

方法	每個元素的處理成本	總時間複雜度
暴力排序	$O(n \log n)$（排完再取）	$O(n \log n)$
Min-Heap（大小 $k$）	$O(\log k)$	$O(n \log k)$

當 $k \ll n$ 時，$O(n \log k)$ 顯著優於 $O(n \log n)$。Heap 有效提升效率，本選項正確。

---

(B) 動態計算數字串流的中位數 ✅

演算法設計：

使用雙堆法（Two-Heap Method）：

• Max-Heap（下半部）：存放較小的一半元素，堆頂為下半部最大值。
• Min-Heap（上半部）：存放較大的一半元素，堆頂為上半部最小值。

維護不變量（invariant）：兩個 Heap 的大小差 $\leq 1$，且 Max-Heap 的堆頂 $\leq$ Min-Heap 的堆頂。

每次插入新元素後，透過至多 2 次的 push/pop 操作恢復不變量；查詢中位數時：

$$\text{median} = \begin{cases} \text{Max-Heap.top()} & \text{若元素總數為奇數} \\ \dfrac{\text{Max-Heap.top()} + \text{Min-Heap.top()}}{2} & \text{若元素總數為偶數} \end{cases}$$

時間複雜度：每次插入 $O(\log n)$，每次查詢 $O(1)$。若用陣列排序則插入 $O(n)$，Heap 顯著更優。本選項正確。

---

(C) 計算一組網頁的 PageRank ❌

解析

• (A) 並非所有 DP 可化為最短/最優路徑問題；如 0/1 背包、序列比對等不直接是路徑找尋。 → 錯
• (B) DP 在求解最終目標時會自底而上或自頂而下計算所有子問題的最優解，子問題因此已被解出。 → 對

核心觀念
本題測驗的是 最短路徑問題的概念與常用演算法的適用條件，包括 Dijkstra、Floyd‑Warshall 兩個演算法的前提、資料結構的使用，以及圖的權重變化對最短路徑的影響。要判斷每個敘述是否正確，需要回顧以下事實：

1. Dijkstra 演算法在 沒有負權重的有向圖（或無負環）上才能正確工作。
2. Dijkstra 內部常以 優先佇列（heap / binary heap、Fibonacci heap） 來取得目前未確定的最近節點。
3. Floyd‑Warshall 演算法是 動態規劃（DP）解法，適用於 任意有向圖，只要 沒有負環（即使有負權重亦可）。
4. 若在圖的每條邊上同時增加同一常數 $c$，所有路徑的長度皆增加 $c\cdot(\text{邊數})$，最短路徑結構不會改變；但若增量僅加在 每條邊上相同的常數，最短路徑仍保持不變。

---

(a) (A) Dijkstra's algorithm can be applied to any directed graph with no negative cycle.

說明
Dijkstra 演算法的正確性依賴於「已確定的最短路徑長度永遠不會因為後續的松弛而變小」這一性質。若圖中存在 負權重邊（即使沒有負環），從起點到某些節點的暫時距離可能在之後被更短的路徑抵消，導致已確定的距離被錯誤地固定。因此 Dijkstra 只能在 所有邊重量皆非負 的圖上保證正確；僅保證「沒有負環」不足以排除負權重邊的情況。

結論
此敘述 錯誤。

---

(b) (B) The heap data structure is likely to be used in Dijkstra's algorithm.

說明
Dijkstra 需要在每一步從「尚未確定的節點集合」中挑選距離最小的節點。最直接的實作是使用 最小堆（min‑heap） 作為優先佇列，使得 extract‑min 與 decrease‑key 操作皆可在 $O(\log V)$（或 $O(1)$、$O(\log V)$ 於 Fibonacci heap）時間內完成。實務上，大多數教科書與程式庫皆採用二元堆或二叉堆實作此資料結構。

結論
此敘述 正確。

---

(c) (C) Floyd-Warshall algorithm can be applied to any directed graph with negative weights.

核心觀念

本題考察最小生成樹（Minimum Spanning Tree, MST）的三大核心性質：

• Cycle Property（循環性質）：對任意非樹邊 $e$，將 $e$ 加入 MST $T$ 後形成唯一環 $C$，則 $e$ 是 $C$ 中權重最大的邊。
• Cut Property（割集性質）：對圖 $G$ 的任意割（partition），橫跨該割的最輕邊必屬於某棵 MST。
• Kruskal 貪心策略：依邊權由小到大排序，凡不形成環者一律加入。

---

解題方法

逐一對每個選項套用上述定理，輔以反例檢驗，確認各選項的真假。

---

選項分析

(A) ✅ 正確

陳述：對 $G$ 中非樹邊 $e$，將 $e$ 加入 $T$ 後形成環 $C$，則 $e$ 是 $C$ 中權重最大的邊。

理由（反證法）：設 $e = (u, v)$，$T$ 中 $u \to v$ 的唯一路徑與 $e$ 共同構成環 $C$。假設路徑上存在某邊 $e' \in C \cap T$ 使得 $w(e') > w(e)$，則令

$T' = T - \{e'\} + \{e\}$

$T'$ 仍是生成樹，且 $w(T') = w(T) - w(e') + w(e) < w(T)$，與 $T$ 是 MST 矛盾。

故對所有 $e' \in C \cap T$，皆有 $w(e') \leq w(e)$，即 $e$ 是 $C$ 中權重最大（含並列）的邊。(A) 正確。

---

(B) ✅ 正確

陳述：對 $G$ 的任意割（partition into $S$ and $V \setminus S$），橫跨該割的最輕邊 $e$ 屬於某棵 MST。

理由（置換論證）：設 $e = (u, v)$ 為最輕橫跨邊，但假設某棵 MST $T$ 不含 $e$。由於 $T$ 是生成樹，$T$ 中存在一條 $u \to v$ 的路徑，該路徑必然經過割，故其中存在某邊 $e'$ 橫跨該割。令

$T' = T - \{e'\} + \{e\}$

$T'$ 仍是生成樹，且因 $w(e) \leq w(e')$，有 $w(T') \leq w(T)$。若 $w(e) < w(e')$，$T$ 不是 MST，矛盾；若 $w(e) = w(e')$，則 $T'$ 也是 MST 且包含 $e$。

兩種情況下，$e$ 皆屬於某棵 MST。(B) 正確。

---

(C) ✅ 正確

陳述：$G$ 中權重最小的邊必屬於某棵 MST。

理由：設全域最輕邊為 $e^* = (s, t)$。以 $\{s\}$ 與 $V \setminus \{s\}$ 作割，$e^*$ 是橫跨此割的所有邊中權重最輕者（因為 $e^*$ 是全圖最小邊）。由 (B) 的 Cut Property，$e^*$ 屬於某棵 MST。(C) 正確。

---

(D) ✅ 正確

陳述：$G$ 中權重第二小的邊必屬於某棵 MST。

第 14 題　Prefix、Infix、Postfix 表示式與二元樹

---

核心觀念

本題同時測驗兩大主題：

1. 堆疊（Stack）在表示式轉換中的應用：Infix → Postfix、Postfix → Infix 的演算法。
2. 二元樹（Binary Tree）的唯一重建條件：給定不同組合的走訪序列（preorder、inorder、postorder），能否唯一確定一棵二元樹。

關鍵定理如下：

定理：給定一棵二元樹，若已知其 inorder（中序） 走訪序列，再搭配 preorder（前序） 或 postorder（後序） 其中之一，即可唯一重建該樹。
反之，僅知 preorder 與 postorder，無法唯一重建（一般二元樹的情況下）。

---

解題方法

逐一驗證五個選項即可。以下先整理兩大主題的演算法原理，再套用於各選項。

---

【主題一：表示式轉換與 Stack】

（Infix → Postfix）
標準的 Shunting-yard 演算法使用一個 Stack 存放運算子，依優先序（precedence）與結合性（associativity）決定何時將運算子從 Stack 彈出並輸出，最後將 Stack 中剩餘運算子全部彈出。全程只需一個 Stack，即可完成轉換。

輸入：a + b * c - d
Stack: []   Output: []

掃到 a → Output: [a]
掃到 + → Stack: [+]
掃到 b → Output: [a, b]
掃到 * → * > +，push。Stack: [+, *]
掃到 c → Output: [a, b, c]
掃到 - → - <= *，pop *；- <= +，pop +；push -。Stack: [-]   Output: [a, b, c, *, +]
掃到 d → Output: [a, b, c, *, +, d]
結束，pop -。Output: [a, b, c, *, +, d, -]

結果為 a b c * + d -，正確。可以用 Stack 完成。

---

（Postfix → Infix）
掃描 Postfix 表示式，遇到運算元（operand）就 push 字串至 Stack；遇到運算子（operator）就 pop 兩個字串，組合成帶括號的 Infix 字串，再 push 回去。

輸入（Postfix）：a b c * + d -

掃到 a → Stack: ["a"]
掃到 b → Stack: ["a", "b"]
掃到 c → Stack: ["a", "b", "c"]
掃到 * → pop c, b → push "(b*c)" → Stack: ["a", "(b*c)"]
掃到 + → pop (b*c), a → push "(a+(b*c))" → Stack: ["(a+(b*c))"]
掃到 d → Stack: ["(a+(b*c))", "d"]
掃到 - → pop d, (a+(b*c)) → push "((a+(b*c))-d)"
結果："((a+(b*c))-d)"

全程使用一個 Stack 即可完成 Postfix → Infix 的轉換。可以用 Stack 完成。

---

【主題二：給定走訪序列重建二元樹】

（Infix + Preorder）
Preorder 的第一個節點必定是根（root）。找到根之後，在 Inorder 序列中定位根，左側為左子樹、右側為右子樹，遞迴處理即可唯一重建。可以唯一重建。

（Infix + Postorder）
Postorder 的最後一個節點必定是根。同樣在 Inorder 中定位根並切割左右子樹，遞迴重建。可以唯一重建。

核心觀念

題目比較三種合併 $k$ 條已排序鏈結串列的方法。每條串列有 $n$ 個節點，因此總節點數為 $kn$。

分析時分別計算：

• 每個節點被處理幾次。
• 每次尋找或維護最小值需要多少時間。
• 分治合併在每一層需要處理多少資料。

解題方法與各演算法分析

Student A：每次掃描所有串列的表頭

每輪查看 $k$ 條串列的表頭，找出最小節點，再將該節點移到結果串列尾端。找最小值需要 $O(k)$ 時間；移除表頭並接到結果串列尾端，使用表頭與尾端指標時各需 $O(1)$ 時間。

總共有 $kn$ 個節點要移動，因此總時間為：

$$O(kn)\times O(k)=O(k^2n)$$

Student B：使用最小堆積

先將每條串列的表頭放入最小堆積。之後每次取出最小節點，並從該節點所屬的串列補入下一個節點。

核心觀念

本題考查 KMP 演算法中「前綴函數（Prefix Function）計算」的執行細節。

前綴函數定義：對於長度為 $m$ 的模式字串 $P$，前綴函數 $\pi[q]$ 定義為：

$\pi[q] = \max\{ k \mid k < q,\; P[1..k] = P[q-k+1..q] \}$

即 $P_q$（$P$ 的前 $q$ 個字元）的「最長真前綴＝真後綴」的長度。

Line 7 的語意：k = π[k] 是在「目前已配對長度 $k$ 的下一個字元仍然不匹配」時，向後退回（fall-back）到次長的可能配對長度。每執行一次 Line 7，代表發生一次「失敗跳轉」。

---

解題方法

完整逐步追蹤

模式字串 $P = \texttt{ABACABACABACABAD}$，長度 $m = 16$，以 1-indexed 標記：

位置 $q$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
$P[q]$	A	B	A	C	A	B	A	C	A	B	A	C	A	B	A	D

初始化：$\pi[1] = 0$，$k = 0$。

$q = 2$，$P[2] = \texttt{B}$

• while：$k = 0$，不進入，Line 7 執行 0 次
• $P[1] = \texttt{A} \ne \texttt{B}$，$k$ 不增
• $\pi[2] = 0$

$q = 3$，$P[3] = \texttt{A}$

• while：$k = 0$，不進入，Line 7 執行 0 次
• $P[1] = \texttt{A} = \texttt{A}$，$k = 1$
• $\pi[3] = 1$

$q = 4$，$P[4] = \texttt{C}$，此時 $k = 1$

• while：$k = 1 > 0$，$P[k+1] = P[2] = \texttt{B} \ne \texttt{C}$ → 執行 Line 7：$k = \pi[1] = 0$，第 1 次
• while：$k = 0$，退出
• $P[1] = \texttt{A} \ne \texttt{C}$，$k$ 不增
• $\pi[4] = 0$

$q = 5$，$P[5] = \texttt{A}$

• while：$k = 0$，不進入，Line 7 執行 0 次
• $P[1] = \texttt{A} = \texttt{A}$，$k = 1$
• $\pi[5] = 1$

$q = 6$，$P[6] = \texttt{B}$，此時 $k = 1$

• while：$P[2] = \texttt{B} = \texttt{B}$，條件為假，不進入，Line 7 執行 0 次
• $P[2] = \texttt{B} = \texttt{B}$，$k = 2$
• $\pi[6] = 2$

$q = 7$，$P[7] = \texttt{A}$，此時 $k = 2$

• while：$P[3] = \texttt{A} = \texttt{A}$，不進入，Line 7 執行 0 次
• $k = 3$，$\pi[7] = 3$

$q = 8$，$P[8] = \texttt{C}$，此時 $k = 3$

• while：$P[4] = \texttt{C} = \texttt{C}$，不進入，Line 7 執行 0 次
• $k = 4$，$\pi[8] = 4$

$q = 9$，$P[9] = \texttt{A}$，此時 $k = 4$

• while：$P[5] = \texttt{A} = \texttt{A}$，不進入，Line 7 執行 0 次
• $k = 5$，$\pi[9] = 5$

$q = 10$，$P[10] = \texttt{B}$，此時 $k = 5$

• while：$P[6] = \texttt{B} = \texttt{B}$，不進入，Line 7 執行 0 次
• $k = 6$，$\pi[10] = 6$