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

核心觀念

本題考驗雜湊表（Hash Table）中**衝突與溢位處理解法（Collision / Overflow Handling Schemes）**的分類與定義。

雜湊表的溢位處理主要分為以下範式：

1. 開放定址法（Open Addressing）：
   所有鍵值（Keys）與資料皆直接儲存於雜湊表本體的陣列 Slot 中（不使用外部鏈結結構）。當雜湊函數計算出的位置 $h(k)$ 發生衝突時，會在同一個雜湊表陣列內部，依照特定的**探測序列（Probing Sequence）**尋找下一個未被佔用的空位。其探測函數一般表示為：
   $h(k, i) = (h'(k) + f(i)) \bmod m$
   常見的開放定址探測策略包含：

   • 線性探測（Linear Probing）：$f(i) = i$
   • 二次探測（Quadratic Probing）：$f(i) = c_1 i + c_2 i^2$
   • 雙重雜湊（Double Hashing）：$f(i) = i \cdot h_2(k)$
   • 再雜湊（Rehashing）：當衝突發生時，依序套用不同的雜湊函數 $h_1(k), h_2(k), \dots$ 探測表內空位。

2. 鏈結法 / 封閉定址法（Chaining / Closed Addressing）：
   雜湊表每個 Slot 僅指向一個外部資料結構（如單向鏈結串列 Linked List 或樹狀結構 Tree），衝突的資料直接接續在該 Slot 的鏈結串列後方。

3. 動態雜湊（Dynamic Hashing）：
   當資料量隨著時間動態大幅增減時，傳統固定表格大小（Static Table Size）的雜湊結構會面臨負載因子（Load Factor）過高或過低的問題。動態雜湊（如 Extendible Hashing、Linear Hashing）透過動態擴展雜湊表結構或分裂儲存桶（Bucket Splitting）來處理溢位與擴充，非屬在靜態表格陣列內進行探測的開放定址法。

---

解題方法

題幹詢問：「下列何者不屬於開放定址法（Open Addressing）的溢位處理解法？」

切入點為檢視各選項的運作原理是否符合開放定址法的核心特徵：

• 特徵 1：資料是否完全儲存在固定大小的雜湊表陣列內部。
• 特徵 2：衝突發生時，是否透過探測序列在表內尋找空 Slot。

只要選項屬於外部資料結構、或是涉及表格動態重構與擴充的技術，即不屬於開放定址法。

---

選項分析

核心觀念

本題考查**快速排序法（Quick Sort）**的核心機制——分割階段（Partition Phase）。

在快速排序法中，第一階段（First Phase）會選定一個基準值（Pivot），並透過雙指標由兩端向中間掃描，將數列調整為：
$\text{左半部元素} \le \text{Pivot} \le \text{右半部元素}$

在國內資工／AI 研究所考試中，若未特別指定分割演算法，預設採用經典的 Horowitz-Sahni 分割演算法（出自《Fundamentals of Data Structures》）。其處理機制如下：

1. 設定雙指標：左指標 $i$ 與右指標 $j$。
2. 指標移動：
   • 指標 $i$ 由左向右移動，尋找大於或等於 Pivot 的元素。
   • 指標 $j$ 由右向左移動，尋找小於或等於 Pivot 的元素。
3. 交換元素：當 $i < j$ 時，將 $A[i]$ 與 $A[j]$ 對調，然後繼續移動指標。
4. 定位 Pivot：當 $i \ge j$ 時停止掃描，最後將 Pivot 元素與 $A[j]$ 交換，完成第一階段分割。

---

解題方法

給定初始數列：$A = [9, 7, 24, 6, 11, 4, 2, 19]$，索引範圍為 $0 \sim 7$。

狀況一：選擇第一個元素作為 Pivot（Pivot = 9）

• 初始狀態：Pivot $= A[0] = 9$，$i = 1$，$j = 7$。
• 第一輪掃描與交換：
  • 指標 $i$ 從 1 開始向右尋找 $\ge 9$ 的元素：$A[1]=7 < 9$，$A[2]=24 \ge 9$，故 $i$ 停在索引 2。
  • 指標 $j$ 從 7 開始向左尋找 $\le 9$ 的元素：$A[7]=19 > 9$，$A[6]=2 \le 9$，故 $j$ 停在索引 6。
  • 因 $i (2) < j (6)$，交換 $A[2]$ (24) 與 $A[6]$ (2)。
  • 數列變為：$[9, 7, \mathbf{2}, 6, 11, 4, \mathbf{24}, 19]$
• 第二輪掃描與交換：
  • 指標 $i$ 繼續向右：$A[3]=6 < 9$，$A[4]=11 \ge 9$，故 $i$ 停在索引 4。
  • 指標 $j$ 繼續向左：$A[5]=4 \le 9$，故 $j$ 停在索引 5。
  • 因 $i (4) < j (5)$，交換 $A[4]$ (11) 與 $A[5]$ (4)。
  • 數列變為：$[9, 7, 2, 6, \mathbf{4}, \mathbf{11}, 24, 19]$
• 第三輪掃描與結束條件：
  • 指標 $i$ 繼續向右：$A[5]=11 \ge 9$，停在索引 5。
  • 指標 $j$ 繼續向左：$A[4]=4 \le 9$，停在索引 4。
  • 此時 $i (5) \ge j (4)$，掃描結束。
• 最後放置 Pivot：
  • 將 Pivot $A[0]$ (9) 與 $A[j]$ ($A[4]=4$) 交換。
  • 最終結果數列為：$[4, 7, 2, 6, 9, 11, 24, 19]$（對應選項 (A)）。

---

狀況二：選擇第二個元素作為 Pivot（Pivot = 7）

核心觀念

1. 左傾樹（Leftist Tree / Leftist Heap）的定義與性質：

   • Min Tree 性質：任意節點的值皆小於或等於其子節點的值（根節點包含最小值）。
   • 最短路徑長度 $dist(i)$：定義 $dist(i)$ 為節點 $i$ 至其子樹中「外部節點（Null 節點）」的最短路徑邊數。若無子節點（即 Null 節點），則 $dist(\text{Null}) = 0$。
   • 左傾性質（Leftist Property）：對樹中任意節點 $i$，皆滿足 $dist(\text{RChild}(i)) \le dist(\text{LChild}(i))$。因此可推出 $dist(i) = dist(\text{RChild}(i)) + 1$。

2. 最右邊路徑（Rightmost Path）的節點數上限：

   • 因為每個節點皆維持「右子樹的 $dist$ 不大於左子樹的 $dist$」，從根節點一路向右延伸至 Null 的路徑（即最右邊路徑），代表了整棵樹通往外部節點的最短路徑。
   • 若一棵左傾樹的最右邊路徑包含 $r$ 個節點，則該樹至少包含 $2^r - 1$ 個節點（當整棵樹為高度 $r$ 的滿二元樹 Full Binary Tree 時節點數最少）。
   • 設樹共有 $n$ 個節點，由 $n \ge 2^r - 1$ 可推得最右邊路徑的節點數 $r \le \log_2(n+1)$，故最右邊路徑長度為 $O(\log n)$。

3. 基本操作與時間複雜度：

   • Merge（合併）：合併兩棵左傾樹時，演算法沿著兩棵樹的「最右邊路徑」進行遞迴合併，合併後若違反左傾性質則交換左右子樹。時間複雜度為 $O(\log n)$。
   • Delete-Min（刪除最小值）：移除根節點後，將分離出的左子樹與右子樹進行 Merge 操作，時間複雜度為 $O(\log n)$。

---

解題方法

本題旨在檢驗左傾樹的結構屬性與核心操作邏輯，切入點如下：

1. 分析最右邊路徑長度：利用最右邊路徑節點數 $r$ 與總節點數 $n$ 的關係式 $n \ge 2^r - 1$，推導 $r$ 的漸近複雜度。
2. 分析 Merge 操作機制：檢視左傾樹合併演算法的遞迴步驟（比較根節點大小，將較大根節點的樹與較小根節點樹的右子樹進行合併）。
3. 分析 Delete-Min 複雜度：將 Delete-Min 拆解為「取出根節點」與「合併左右子樹」，由 Merge 的複雜度求得結果。
4. 驗證最左邊路徑與節點數下限：構建極端特例（如退化為僅含左子樹的單鏈結構）測試最左邊路徑節點數與總節點數的關係。

---

選項分析

• (A) 正確。
  在包含 $n$ 個節點的左傾樹中，由於左傾性質 $dist(\text{RChild}(i)) \le dist(\text{LChild}(i))$，從根節點沿右子樹一路向右延伸的最右邊路徑，即為通往外部節點的最短路徑。若最右邊路徑有 $r$ 個節點，樹的總節點數滿足：
  $n \ge 2^r - 1 \implies 2^r \le n + 1 \implies r \le \log_2(n+1)$
  因此，通往最右側葉節點的路徑長度為 $O(\log n)$。

核心觀念

本題考查**最低有效位基數排序法（LSD Radix Sort）**的基本定義、運作流程與穩定性應用。

1. 非比較排序法（Non-comparison Sort）：基數排序不透過元素之間的兩兩比較（如 $\le$ 或 $>$），而是依據 key 的位元值（Digit）將資料分配至相應的桶子（Buckets/Queues）中，屬於非比較排序法。
2. 穩定性（Stability）：LSD Radix Sort 在各個 Pass 中必須維持排序的穩定性（Stable）。當多個元素的當前位數值相同時，必須維持前一階段排序後的相對順序。
3. 排序階段與位元順序：
   • 輸入資料的最大位數為 $d = 3$（最高到百位數）。
   • Pass 1：針對個位數（Least Significant Digit, $d_1$）進行穩定分配與收集。
   • Pass 2：針對十位數（$d_2$）進行穩定分配與收集。
   • Pass 3：針對百位數（Most Significant Digit, $d_3$）進行穩定分配與收集。

---

解題方法

給定輸入串列 $L = [28, 203, 16, 30, 123, 521, 63, 528, 210, 216, 941, 45]$，將所有數字補齊為三位數表示：
$L = [028, 203, 016, 030, 123, 521, 063, 528, 210, 216, 941, 045]$

以基底 $R = 10$（桶子 $0 \sim 9$）推導三次 Pass 的詳細過程：

Pass 1：依個位數（Units Digit）分配與收集

各元素的個位數分別為：

• $028 \to 8, \; 203 \to 3, \; 016 \to 6, \; 030 \to 0, \; 123 \to 3, \; 521 \to 1$
• $063 \to 3, \; 528 \to 8, \; 210 \to 0, \; 216 \to 6, \; 941 \to 1, \; 045 \to 5$

將元素依序放入對應桶子（保持先進先出 FIFO 順序）：

• 桶子 0: $[030, 210]$
• 桶子 1: $[521, 941]$
• 桶子 2: $[\;]$
• 桶子 3: $[203, 123, 063]$
• 桶子 4: $[\;]$
• 桶子 5: $[045]$
• 桶子 6: $[016, 216]$
• 桶子 7: $[\;]$
• 桶子 8: $[028, 528]$
• 桶子 9: $[\;]$

由桶子 $0 \to 9$ 依序收集，Pass 1 結束後的串列為：
$L_1 = [30, 210, 521, 941, 203, 123, 63, 45, 16, 216, 28, 528]$

• 第 5 個元素為 $203$
• 第 6 個元素為 123
• 第 7 個元素為 $63$

Pass 2：依十位數（Tens Digit）分配與收集

基於 $L_1$ 的順序，各元素的十位數分別為：

• $30(030) \to 3, \; 210 \to 1, \; 521 \to 2, \; 941 \to 4, \; 203 \to 0, \; 123 \to 2$
• $63(063) \to 6, \; 45(045) \to 4, \; 16(016) \to 1, \; 216 \to 1, \; 28(028) \to 2, \; 528 \to 2$

將元素依序放入對應桶子：

• 桶子 0: $[203]$
• 桶子 1: $[210, 16, 216]$
• 桶子 2: $[521, 123, 28, 528]$
• 桶子 3: $[30]$

核心觀念

本題旨在考驗考生對**二元堆積（Binary Heap）**的基本性質、操作時間複雜度（Time Complexity）以及動態建構（Heap Building）過程的掌握程度。主要涵蓋以下核心觀念與定義：

1. 堆積性質（Heap Property）：

   • 最小堆積（Min-Heap）：若樹高為 $h$，為一棵完全二元樹（Complete Binary Tree），且任意節點之鍵值皆小於或等於其子節點鍵值（$A[\text{parent}(i)] \le A[i]$），根節點為全樹最小值。
   • 最大堆積（Max-Heap）：任意節點之鍵值皆大於或等於其子節點鍵值（$A[\text{parent}(i)] \ge A[i]$），根節點為全樹最大值。

2. 堆積基本操作的時間複雜度：

   • 插入（Insert）：將新元素放於完全二元樹末端後執行「上浮」（Sift-Up / Percolate-Up）調整。樹高為 $h = \lfloor \log_2 n \rfloor$，最壞時間複雜度為 $O(\log n)$。
   • 刪除極值（Delete-Min / Delete-Max）：將根節點與末端元素交換後刪除末端元素，並對新根節點執行「下沉」（Sift-Down / Percolate-Down）調整。最壞時間複雜度為 $O(\log n)$。
   • 搜尋任意元素（Search）：堆積僅維護父子節點之間的半偏序關係（Partial Order），左右子樹之間無固定大小順序，搜尋特定元素無法進行二元搜尋，最壞情況需走訪全樹，時間複雜度為 $O(n)$。

3. 逐一插入建構堆積（Build Heap via Sequential Insertion）：

   • 依序將數列元素逐一插入堆積中，每插入一個元素即即時修復堆積性質。陣列索引 $i$（採用 1-based index）之父節點索引為 $\lfloor i / 2 \rfloor$，左子節點為 $2i$，右子節點為 $2i + 1$。
   • 階層走訪（Level Order Traversal）順序即對應陣列索引 $1$ 到 $n$ 的元素順序。

---

解題方法

1. 複雜度分析切入點：

   • 檢驗操作的最緊確上界（Tight Upper Bound）。對於 Heap 的插入與刪除最小值操作，其最壞時間複雜度皆與樹高成正比，即 $O(\log n)$；搜尋任意元素因無全序資訊，時間複雜度為 $O(n)$。

2. 逐一插入建構 Min-Heap 的推導過程（針對選項 (C)）：

   • 給定插入序列：$\{42, 9, 23, 37, 4, 34, 2\}$
   • 採用 1-based 陣列表示法，詳細步驟如下：
     • 插入 $42$：陣列為 $[42]$。
     • 插入 $9$：放於索引 2，與父節點 $42$（索引 1）比較，$9 < 42$，進行交換。陣列變為 $[9, 42]$。
     • 插入 $23$：放於索引 3，與父節點 $9$（索引 1）比較，$23 > 9$，無需交換。陣列變為 $[9, 42, 23]$。
     • 插入 $37$：放於索引 4，與父節點 $42$（索引 2）比較，$37 < 42$，進行交換。陣列變為 $[9, 37, 23, 42]$。
     • 插入 $4$：放於索引 5，與父節點 $37$（索引 2）比較，$4 < 37$，進行交換；

核心觀念

本題考查堆疊（Stack）的後進先出（LIFO, Last-In-First-Out）特性以及**堆疊置換（Stack Permutation）**的判斷。

1. 堆疊基本操作：

   • $X$：壓入（Push）操作，將輸入序列中的下一個元素放入堆疊頂端。
   • $Y$：彈出（Pop）操作，將堆疊頂端的元素取出並輸出。

2. 合法操作序列條件：

   • 總共進行 $4$ 次 Push（$X$）與 $4$ 次 Pop（$Y$），總操作長度為 $8$。
   • 在任意前綴序列中，Push 的次數 $N(X)$ 必須大於等於 Pop 的次數 $N(Y)$（即 $N(X) \ge N(Y)$），否則會發生下溢（Underflow）。
   • 輸入長度為 $n$ 時，可產生的合法堆疊置換總數為卡塔蘭數（Catalan Number）：
     $C_n = \frac{1}{n+1}\binom{2n}{n}$
     當 $n=4$ 時，共有 $C_4 = \frac{1}{5}\binom{8}{4} = 14$ 種合法的輸出序列。

3. 堆疊置換禁忌模式（Forbidden Pattern）：
   一個排列為合法的堆疊輸出，當且僅當該排列不包含 $231$ 禁忌模式。
   具體定義：對於輸入順序為 $1, 2, \dots, n$ 的元素，若輸出序列中存在三個元素 $i, j, k$ 滿足相對大小 $i < j < k$，且在輸出序列中的相對位置為 $k$ 出現在 $i$ 之前、 $i$ 出現在 $j$ 之前（即 $k \dots i \dots j$ 模式），則該序列絕不可能由單一堆疊產生。因為當較大值 $k$ 被 Push 後再 Pop 出來時，$i$ 與 $j$（$i < j$）已在堆疊中，受 LIFO 限制，較晚進入堆疊的 $j$ 必然先於 $i$ 被彈出。

---

解題方法

驗證一個序列是否為合法的堆疊輸出，有以下兩種方法：

1. 操作模擬法：
   依據目標輸出序列，推導對應的 $X$（Push）與 $Y$（Pop）操作序列。若能成功構建出滿足條件的 $4$ 次 $X$ 與 $4$ 次 $Y$ 操作，則該序列合法。
2. 禁忌模式檢驗法：
   檢查輸出序列中是否存在 $i < j < k$ 但輸出順序呈現 $k \dots i \dots j$ 的結構。若存在，則直接判定為非法輸出。

以下對各選項進行逐一驗證。

---

選項分析

• (A) 1243：正確
  • 推導步驟：
    1. Push 1 ($X$)，Pop 1 ($Y$) $\rightarrow$ 輸出：1，堆疊內部：[]
    2. Push 2 ($X$)，Pop 2 ($Y$) $\rightarrow$ 輸出：1 2，堆疊內部：[]
    3. Push 3 ($X$)，Push 4 ($X$) $\rightarrow$ 堆疊內部（由底至頂）：[3, 4]
    4. Pop 4 ($Y$) $\rightarrow$ 輸出：1 2 4，堆疊內部：[3]
    5. Pop 3 ($Y$) $\rightarrow$ 輸出：1 2 4 3，堆疊內部：[]
  • 對應操作序列：XYXYXXYY（共 4 個 $X$、4 個 $Y$）。
  • 因此 (A) 為可行的輸出序列。

核心觀念

本題考驗圖論（Graph Theory）中資料結構的表示法及其時間與空間複雜度分析，核心觀念包含：

1. 圖的資料結構表示法與空間複雜度：
   • 鄰接矩陣（Adjacency Matrix）：以 $n \times n$ 的二維陣列儲存頂點間邊的關係。無論邊數 $m$ 為何，空間複雜度均為 $\Theta(n^2)$。
   • 鄰接串列（Adjacency List）：由長度為 $n$ 的頭指標陣列與邊節點鏈結串列組成。在無向圖中，每條邊 $(u, v)$ 會在 $u$ 與 $v$ 的串列中各出現一次（共 $2m$ 個邊節點）。總空間複雜度為 $\Theta(n + m)$。
   • 鄰接多重表（Adjacency Multilist）：專門為無向圖設計的結構，包含長度為 $n$ 的表頭陣列與 $m$ 個邊節點（每條邊僅用一個邊節點表示）。總空間複雜度為 $\Theta(n + m)$。
2. 題目特殊條件 $m \gg n$ 的漸進分析：
   當邊數 $m$ 遠大於頂點數 $n$ 時，頂點數 $n$ 在漸進分析中屬於低階項（$n = o(m)$），故空間複雜度 $\Theta(n + m)$ 可簡化為 $\Theta(m)$。
3. 連通性檢測（Connectivity Determination）的時間複雜度：
   判斷無向圖是否連通需透過圖的走訪（BFS 或 DFS）：
   • 使用鄰接矩陣走訪時，尋找每個頂點的所有鄰居均需掃描整列（長度 $n$），總時間複雜度為 $\Theta(n^2)$。
   • 使用鄰接串列走訪時，時間複雜度為 $\Theta(n + m)$。

---

解題方法

本題切入點分為「空間複雜度推導」與「連通性走訪時間複雜度推導」兩部分：

1. 空間複雜度推導：

   • 鄰接矩陣：需配置 $n \times n$ 空間，佔用記憶體大小為 $\Theta(n^2)$，自然落於 $O(n^2)$ 之漸進上界內。
   • 鄰接串列：空間由「頂點頭指標陣列」與「鏈結串列邊節點」組成，分別為 $\Theta(n)$ 與 $\Theta(2m) = \Theta(m)$。總空間為 $\Theta(n + m)$。套用題目給定條件 $m \gg n$，可得 $\Theta(n + m) = \Theta(m)$。
   • 鄰接多重表：空間由「頂點頭指標陣列」與「$m$ 個邊節點」組成，總空間為 $\Theta(n + m)$。套用題目給定條件 $m \gg n$，同樣簡化為 $\Theta(m)$。

2. 時間複雜度推導：

   • 檢測圖是否連通，必須從某一頂點出發進行走訪（BFS/DFS），確認走訪到的頂點總數是否等於 $n$。

核心觀念

本題考查圖形理論（Graph Theory）中的最短路徑演算法（Shortest Path Algorithms）及其時間複雜度分析。

1. 單源最短路徑（Single-Source Shortest Path, SSSP）：

   • 給定圖形 $G = (V, E)$，其中頂點數 $|V| = n$，邊數 $|E| = m$。
   • 單源單目的地（Single-Source Single-Destination）與單源多目的地／全目的地（Single-Source All-Destinations）：在一般圖形的最壞情況漸進分析中，求單一對的最短路徑與求單一起點到所有終點的最短路徑，目前尚無漸進階數更低的普遍演算法。
   • 使用經典的戴克斯特拉演算法（Dijkstra's Algorithm，採用陣列／鄰接矩陣實作），時間複雜度為 $O(n^2)$。若使用斐波那契堆積（Fibonacci Heap）實作，時間複雜度為 $O(m + n \log n)$。在稠密圖（Dense Graph, $m = O(n^2)$）下亦為 $O(n^2)$。

2. 全對最短路徑（All-Pairs Shortest Path, APSP）：

   • 求解圖中任意兩點間的最短路徑距離。
   • 經典動態規劃演算法為弗洛伊德-瓦希爾演算法（Floyd-Warshall Algorithm），時間複雜度為 $O(n^3)$。
   • 若對 $n$ 個頂點分別執行 $n$ 次 Dijkstra 演算法（陣列實作），總時間複雜度亦為 $n \times O(n^2) = O(n^3)$。

---

解題方法

針對包含 $n$ 個頂點的無向圖 $G$：

1. 單源最短路徑推導：

   • Dijkstra 演算法在每輪疊代中尋求未造訪頂點中距離最小者，需要 $O(n)$ 時間；共進行 $n$ 輪疊代，並對鄰接邊進行鬆弛（Relaxation）操作。
   • 採用最基礎的陣列實作時，時間複雜度為：
     $T(n) = O(n^2)$
   • 因此，無論是求解單一目的地或多個目的地，其時間複雜度均為 $O(n^2)$。

2. 全對最短路徑推導：

   • 使用 Floyd-Warshall 演算法，需透過三重虛擬頂點迴圈更新所有頂點對之間的最短距離，狀態轉移方程為 $d_{ik}^{(j)} = \min(d_{ik}^{(j-1)}, d_{ij}^{(j-1)} + d_{jk}^{(j-1)})$。
   • 三重迴圈的計算複雜度為：

核心觀念

本題旨在考驗對基本資料結構（一維陣列、單向鏈結串列、環狀單向鏈結串列）在執行新增（Insertion）與刪除（Deletion）操作時之時間複雜度（Time Complexity）與記憶體配置特性的比較。

主要評估的關鍵機制包括：

1. 陣列的連續記憶體配置與位移開銷（Shift Cost）：陣列具備隨機存取（Random Access）特性，但插入與刪除特定元素時，需移動後續元素以維護資料連續性。
2. 鏈結串列的動態記憶體配置與走訪開銷（Traversal Cost）：鏈結串列插入/刪除節點本身僅需修改指標 $O(1)$，但若未掌握目標位置前驅節點（Predecessor）的指標，則需從頭進行走訪（Traversal）。

---

解題方法

分析各種資料結構在長度為 $n$ 的情況下，特定操作所需的時間複雜度：

1. 一維陣列（1D Array）：

   • 前端插入（Index 0）：需將現有的 $n$ 個元素全部向後移動一位，操作次數為 $n$，時間複雜度為 $O(n)$。
   • 任意位置刪除（例如第 3 個元素，Index 2）：存取第 3 個元素為 $O(1)$，但刪除後需將第 4 至第 $n$ 個元素（共 $n-3$ 個元素）向前移動一位，時間複雜度為 $O(n-3) = O(n)$。

2. 單向鏈結串列（Singly Linked List）：

   • 前端插入：只需建立新節點，將新節點的 next 指向原 head，並更新 head 指向新節點，無需走訪，時間複雜度為 $O(1)$。
   • 尾端插入：在未額外維護尾指標（tail pointer）的標準單向鏈結串列中，必須從 head 走訪 $n$ 個節點找到目前的尾節點，時間複雜度為 $O(n)$。

3. 環狀單向鏈結串列（Circular Singly Linked List）：

   • 在經典資料結構設計中，環狀單向鏈結串列通常使用一個指向尾節點的指標 tail 來代表整個串列。
   • 在此結構下，頭節點即為 tail->next。

核心觀念

本題考查《資料結構》中**算術運算式（Arithmetic Expressions）**的表示法轉換及其語法規則，涵蓋以下核心觀念：

1. 運算式表示法定義：
   • 中序表示法（Infix Notation）：運算子位於兩運算元之間（如 $A + B$）。計算時需依賴運算子優先權（Precedence）、結合性（Associativity）及括號來決定執行順序。
   • 後序表示法（Postfix / Reverse Polish Notation, RPN）：運算子位於兩運算元之後（如 $A B +$）。無需括號及優先權規則即可無歧義表達運算順序。
   • 前序表示法（Prefix / Polish Notation）：運算子位於兩運算元之前（如 $+ A B$）。同樣無需括號即可表達算序。
2. 二元運算式的合法性定理：
   對於僅含二元運算子（Binary Operators）的有效前序或後序運算式，若包含 $N$ 個運算元（Operands），則必須恰好包含 $N - 1$ 個運算子。
3. 堆疊（Stack）應用：
   後序與前序運算式的求值與轉換，底層皆可透過堆疊結構以 $O(n)$ 時間複雜度完成。

---

解題方法

轉換運算式主要採用以下兩種方法：

1. 堆疊演算法（Stack-based Algorithm）：
   • 後序轉前序：由左至右掃描後序運算式。遇到運算元時壓入堆疊；遇到二元運算子時，自堆疊彈出兩個元素，分別作為右運算元 $op_2$ 與左運算元 $op_1$，將其組合為新前序字串 [運算子] [op1] [op2] 後重新壓回堆疊。
2. 完全加括號法（Full Parenthesization Method）：
   依照優先權與結合性將中序運算式加上完整括號，再將運算子搬移至該層括號的最右側（轉後序）或最左側（轉前序），最後抹去所有括號即可得到目標運算式。

---

選項分析

(A) 錯誤

• 題目敘述：The postfix of infix expression $b+a*c/d$ is $bac+d/*$.
• 推導步驟：
  在中序運算式 $b + a * c / d$ 中，運算子優先權為 * 與 /（同級且左結合）高於 +。
  1. 先處理 $a * c$，轉為後序：$a c *$
  2. 再處理與 $d$ 的除法 $(a * c) / d$，轉為後序：$a c * d /$
  3. 最後處理與 $b$ 的加法 $b + ((a * c) / d)$，轉為後序：$b a c * d / +$
• 結論：正確的後序應為 $b a c * d / +$。選項中的 bac+d/* 反推回中序代表 $b * (a + c) / d$，與原式不符。

(B) 錯誤

• 題目敘述：The postfix of $(a+b)/(c-d)*e$ is $ab+cd-*/$.
• 推導步驟：
  在中序運算式 $(a+b)/(c-d)*e$ 中，括號優先執行，同級的 / 與 * 依左結合律自左向右處理。
  1. 處理括號 $(a+b)$ 與 $(c-d)$，分別得到 $a b +$ 與 $c d -$
  2. 處理除法 $(a+b) / (c-d)$，得到 $a b + c d - /$
  3. 最後處理與 $e$ 的乘法 $((a+b)/(c-d)) * e$，得到正確後序：$a b + c d - / e *$

核心觀念

1. Source Vertex（源點）的定義：在有向圖 $G = (V, E)$ 中，若從頂點 $s$ 出發，存在到達圖中所有頂點的導向路徑（Directed Path），則稱 $s$ 為 Source Vertex。意即對於所有 $x \in V$，頂點 $x$ 皆可由 $s$ 到達（Reachable）。
2. 圖形走訪（Graph Traversal）：要驗證指定頂點 $v$ 是否為 Source Vertex，只需從 $v$ 出發進行一次單源圖形走訪（如廣度優先搜尋 BFS 或深度優先搜尋 DFS）。若走訪過程中拜訪到的相異頂點總數恰好等於頂點總數 $|V|$，則表示從 $v$ 可到達圖中所有頂點，$v$ 即為 Source Vertex。

---

解題方法

1. 切入點分析

題目已明確給定「特定頂點 $v$」，並要求判斷 $v$ 是否為 Source Vertex。因此不需要採用較複雜的全圖 Source 尋找演算法（如利用 DFS 結束時間或強連通元件 SCC），直接從頂點 $v$ 出發執行一次走訪即可。

2. 資料結構設計（Data Structures Used）

• 鄰接串列（Adjacency List）：用於儲存有向圖 $G = (V, E)$。每一個頂點 $u \in V$ 附帶一個鏈結串列，記錄其所有出邊（Outgoing Edges）對應的相鄰頂點。採用鄰接串列可在 $O(\text{deg}^+(u))$ 時間內存取頂點 $u$ 的所有鄰居，保證走訪時間達到 $O(|V| + |E|)$。
• 拜訪標記陣列（visited Array）：大小為 $|V|$ 的布林陣列（Boolean Array），初值皆為 false。用以記錄各頂點是否已被拜訪，避免重複走訪與無窮迴圈。
• 佇列（Queue）：用於廣度優先搜尋（BFS），維護待處理頂點的先進先出（FIFO）順序。

3. 演算法步驟

1. 初始化拜訪頂點計數器 reached_count = 0。
2. 建立大小為 $|V|$ 的布林陣列 visited，將所有位置設為 false。
3. 建立一個空佇列 $Q$。
4. 將起始頂點 $v$ 標記為 visited[v] = true，推入佇列 $Q$，並將 reached_count 加 1。
5. 當佇列 $Q$ 不為空時：
   • 從 $Q$ 佇列前端取出頂點 $u$。
   • 遍歷頂點 $u$ 在鄰接串列中的所有出邊相鄰頂點 $w$（即 $(u, w) \in E$）：
     • 若 visited[w] 為 false：
       • 設定 visited[w] = true。
       • 將 reached_count 加 1。
       • 將頂點 $w$ 推入佇列 $Q$。
6. 當走訪結束（$Q$ 為空）時，檢查 reached_count == |V|：
   • 若相等，傳回 true（$v$ 為 Source Vertex）。
   • 否則，傳回 false（$v$ 不是 Source Vertex）。

4. 關鍵程式碼（C++ / Pseudocode）

核心觀念

本題的核心在於利用 DAG（有向無環圖） 的結構特性，判定圖中是否存在 源點（Source Vertex）。

1. 源點（Source Vertex）的定義：在有向圖 $G=(V, E)$ 中，若存在一頂點 $u \in V$，使得對任意頂點 $v \in V$ 都存在一條從 $u$ 到 $v$ 的有向路徑（即 $u$ 可到達圖中的所有頂點），則稱 $u$ 為圖 $G$ 的源點。
2. DAG 的入度（In-degree）結構定理：
   • 在任何有限且非空的 DAG 中，必定存在 至少一個 入度為 $0$ 的頂點。
   • 若一個 DAG 存在源點 $u$，則 $u$ 的入度必定為 $0$（因為若 $u$ 的入度大於 $0$，且圖無環，則無法從小於 $u$ 的前序頂點回推到達 $u$）。
   • 定理：一個 DAG 存在源點的 充要條件（當且僅當） 為 該圖中恰好存在一個入度為 $0$ 的頂點。
3. 複雜度優化思維：
   子問題 (a) 針對單一頂點執行可達性檢查（如 DFS/BFS）需時 $O(|V| + |E|)$。若對每個頂點皆執行一次，總時間複雜度為 $O(|V|(|V|+|E|)) = O(|V|^2 + |V||E|)$。利用 DAG 的入度特性，僅需走訪一次圖的點與邊計算入度，即可將時間複雜度降至 $O(|V| + |E|)$。

---

解題方法

1. 演算法邏輯與步驟

1. 建立一個長度為 $|V|$ 的陣列 in_degree，初始值全設為 $0$。
2. 走訪圖中所有的有向邊 $(u, v) \in E$，將目標頂點的入度累加：in_degree[v] += 1。
3. 掃描 in_degree 陣列，找出所有入度為 $0$ 的頂點，並統計其數量 $k$。
4. 判定結果：
   • 若 $k = 1$：回傳 True（唯一入度為 $0$ 的頂點即為源點）。
   • 若 $k > 1$ 或 $k = 0$：回傳 False（圖中不存在源點）。

2. 定理數學推導與證明

• 充分性 ($\Leftarrow$)：假設 DAG 中恰好有一個頂點 $u$ 的入度為 $0$。
  對任意頂點 $v \in V$，從 $v$ 開始沿著有向邊逆向（向後）走訪。因為 $G$ 為有限且無環的圖（DAG），逆向走訪不可能形成迴圈，亦不可能無限延伸，故必定會終止於某個入度為 $0$ 的頂點。由於圖中唯一的入度 $0$ 頂點為 $u$，因此從任意頂點 $v$ 逆向走訪最終都會到達 $u$。這代表從 $u$ 順向走訪必定存在到達 $v$ 的有向路徑。故 $u$ 可到達所有頂點，$u$ 即為源點。

• 必要性 ($\Rightarrow$)：假設 DAG 中存在源點 $s$。
  若圖中存在另一個頂點 $w \neq s$ 且 $w$ 的入度也為 $0$，則意味著沒有任何頂點有邊連向 $w$，因此源點 $s$ 無法到達 $w$，這與 $s$ 為源點的定義矛盾。故入度為 $0$ 的頂點至多只能有 $1$ 個。又因有限 DAG 至少存在 $1$ 個入度為 $0$ 的頂點，因此入度為 $0$ 的頂點恰好有 $1$ 個（即 $s$）。

3. 虛擬碼（Pseudocode）

核心觀念

1. 源頭頂點（Source Vertex / Universal Source）定義
   在有向圖 $G = (V, E)$ 中，若存在一個頂點 $s \in V$，使得從 $s$ 出發可以到達圖中所有其他頂點 $v \in V$（即對所有 $v \in V$，均存在一條從 $s$ 到 $v$ 的有向路徑），則稱 $s$ 為該有向圖的源頭頂點。

2. 強連通元件（Strongly Connected Component, SCC）與縮圖（Condensation Graph）
   將有向圖 $G$ 中的每個強連通元件縮為單一頂點後，可得到一個無環的有向無環圖（DAG），稱為縮圖 $G^{SCC}$。若 $G$ 中存在源頭頂點，則在縮圖 $G^{SCC}$ 中，該源頭頂點所在的元件入度（In-degree）必須為 0，且整個 $G^{SCC}$ 只能恰好存在一個入度為 0 的元件。

3. DFS 結束時間（Finishing Time）性質
   對有向圖 $G$ 進行深度優先搜尋（DFS）時，最後一個完成走訪（即擁有最大結束時間 $finish$）的頂點 $u$，必定屬於縮圖 $G^{SCC}$ 中入度為 0 的強連通元件。因此，若 $G$ 中存在任何源頭頂點，$u$ 必為源頭頂點之一。

---

解題方法

1. 演算法切入點與原理推導

暴力解法會對每一個頂點執行一次 DFS 或 BFS（每次需 $O(|V| + |E|)$ 時間），總時間複雜度為 $O(|V|^2 + |V||E|)$，不符合題目對更高效演算法的要求。

為了將時間複雜度優化至線性時間 $O(|V| + |E|)$，我們利用 DFS 結束時間 的關鍵幾何性質：

• 性質 1：全圖 DFS 中結束時間最晚的頂點 $u$，必定屬於縮圖 $G^{SCC}$ 中入度為 0 的元件。
• 性質 2：若圖 $G$ 存在源頭頂點，則該源頭頂點必須能夠到達圖中所有頂點，這意味著縮圖 $G^{SCC}$ 有且僅有一個入度為 0 的元件。若存在多個入度為 0 的元件，則各元件間彼此互不可達，圖中絕無源頭頂點。
• 結論：全圖 DFS 結束時間最晚的頂點 $u$ 是唯一可能的源頭頂點候選人。只需針對頂點 $u$ 進行第二次 DFS/BFS 走訪驗證，即可確定全圖是否存在源頭頂點。

2. 演算法步驟

1. 第一次 DFS 遍歷：
   對圖 $G=(V, E)$ 執行標準 DFS 走訪，記錄所有頂點的結束時間。找出結束時間最晚（最大）的頂點，記為 $u$。
2. 第二次 DFS/BFS 驗證：
   從頂點 $u$ 出發執行一次 DFS 或 BFS，並統計所能走訪到的頂點總數 $count$。
3. 結果判斷：
   若 $count = |V|$，代表從 $u$ 可到達全圖所有頂點，則 $u$ 為源頭頂點，傳回 true；否則傳回 false（表示 $G$ 不含源頭頂點）。

3. 關鍵虛擬碼（Pseudocode）

核心觀念

1. 非確定性演算法（Non-Deterministic Algorithm, ND Algorithm）：
   ND 演算法由兩個階段構成：

   • 選擇階段（Choosing Phase）：利用非確定性選擇動作 choice()，在多項式時間內猜測（Guess）一組候選解。
   • 檢查階段（Checking Phase）：為一確定性演算法（Deterministic Algorithm），於多項式時間內驗證（Verify）該候選解是否為原問題的合法解。若符合則回傳 SUCCESS，否則回傳 FAILURE。
   • 假設 ND 演算法具備神奇的選擇能力：若存在可導出 SUCCESS 的選擇組合，演算法必定會選到該組合。

2. NP 問題（Non-deterministic Polynomial Time Problem）之定義：
   若一個決策問題存在一個多項式時間複雜度的 ND 演算法能將其求解，則該問題屬於 NP 問題類別。

3. 精確覆蓋決策問題（Exact Cover Decision Problem, ECDP）：

   • 輸入：一個包含 $n$ 個元素的宇集 $U = \{u_1, u_2, \dots, u_n\}$，以及一個包含 $m$ 個子集的集合 $S = \{S_1, S_2, \dots, S_m\}$，其中每個 $S_j \subseteq U$。
   • 目標：判定是否存在一個子集合 $S^* \subseteq S$，使得 $U$ 中的每一個元素 $u_i$ 都恰好出現於 $S^*$ 中的某一個子集中（即 $S^*$ 形成宇集 $U$ 的一個分割）。

---

解題方法

依據題目指定的 ND 演算法定義與 ND-SAT 的標準格式，設計解答 ECDP 的多項式時間演算法 ND-ECDP 並進行複雜度分析。

1. 演算法設計（Algorithm Design）

Algorithm: ND-ECDP
Input: A universe set $U = \{u_1, u_2, \dots, u_n\}$ of $n$ elements, and a collection $S = \{S_1, S_2, \dots, S_m\}$ of $m$ subsets of $U$.
Output: SUCCESS if $S$ contains an exact cover for $U$; FAILURE, otherwise.

核心觀念

1. 非確定性演算法（Non-Deterministic Algorithm, ND Algorithm）：
   在計算複雜度理論（Complexity Theory）中，判定問題（Decision Problem）屬於 $\text{NP}$ 類別的定義為「存在一個能在非確定性多項式時間內解決該問題的非確定性演算法」。非確定性演算法包含兩個關鍵階段：

   • 猜測階段（Guessing Phase）：非確定性地選擇或猜測一個候選解（Candidate Solution / Certificate）。
   • 驗證階段（Verification Phase）：以確定性演算法（Deterministic Algorithm）檢查該候選解是否為合法的正確解。

2. 精確覆蓋判定問題（Exact Cover Decision Problem, ECDP）：

   • 輸入：萬有集合 $U = \{u_1, u_2, \dots, u_m\}$（共 $m$ 個元素），以及由 $n$ 個子集組成的集合族 $S = \{S_1, S_2, \dots, S_n\}$，其中 $S_i \subseteq U$。
   • 目標：判定是否存在子集合族 $S^* \subseteq S$，滿足：
     1. 完全覆蓋：$\bigcup_{S_i \in S^*} S_i = U$（$U$ 中每個元素至少出現一次）。
     2. 互斥性：對於任意 $S_i, S_j \in S^*$ 且 $i \neq j$，$S_i \cap S_j = \emptyset$（$U$ 中每個元素至多出現一次）。
        兩者結合即為：$U$ 中的每個元素 $u \in U$ 恰好只在 $S^*$ 的某一個集合中出現一次。

---

解題方法

要證明 ECDP 的非確定性演算法（ND Algorithm）具有多項式時間複雜度（Polynomial Time Complexity），需完整列出演算法步驟，並依序分析「猜測階段」與「驗證階段」的時間複雜度。

1. 非確定性演算法（ND Algorithm）設計

ND_ECDP(U, S):
    // 步驟 1：猜測階段 (Guessing Phase)
    S* = empty set
    For i = 1 to n:
        nondeterministically choose x_i in {0, 1}
        If x_i == 1:
            Add S_i to S*

    // 步驟 2：驗證階段 (Verification Phase)
    Initialize count array C[1...m] = 0 for all elements in U
    
    For each S_i in S*:
        For each element u in S_i:
            C[u] = C[u] + 1
            
    For each element u in U (from 1 to m):
        If C[u] != 1:
            Return FAILURE
            
    Return SUCCESS

2. 時間複雜度分析（Big-O Notation）

設輸入大小由兩個參數決定：萬有集合元素個數 $|U| = m$，集合族個數 $|S| = n$。

1. 猜測階段時間複雜度 $T_{\text{guess}}(m, n)$：

   • 非確定性機器針對 $S$ 中的每個集合 $S_i$ ($1 \le i \le n$) 做出一項非確定性選擇（是否加入 $S^*$）。
   • 產生長度為 $n$ 的二進位決策向量包（$x \in \{0, 1\}^n$）需要 $n$ 步選擇。
   • 因此，猜測階段時間複雜度為：
     $T_{\text{guess}}(m, n) = O(n)$

2. 驗證階段時間複雜度 $T_{\text{verify}}(m, n)$：

   • 計數陣列初始化：初始化長度為 $m$ 的計數陣列 $C[1\dots m]$ 為 0，耗時 $O(m)$。
   • 元素出現次數統計：走訪 $S^*$ 中所有選定集合的每一個元素。