108 年 國立臺灣大學資訊網路與媒體研究所《資料結構與演算法》

核心觀念

本題考的是：

• 堆疊（stack）的後進先出（LIFO）特性；
• 合法的 push／pop 操作序列；
• Catalan number（卡特蘭數）的遞迴式與封閉形式。

輸入順序固定為 $1,2,\ldots,n$。每個數字依序進入堆疊，但可以在任意時刻刪除（pop）堆疊頂端元素，因此產生不同的輸出排列。

例如 $n=3$ 時，合法排列包括：

$$123,\quad 132,\quad 213,\quad 231,\quad 321$$

但 $312$ 無法產生，因為要先輸出 $3$，必須先將 $1,2,3$ 都放入堆疊；此時 $3$ 輸出後，$2$ 必須先於 $1$ 輸出，不可能接著輸出 $1$。

---

解題方法

將堆疊操作轉換成括號序列

將「放入堆疊」視為左括號，將「刪除堆疊頂端元素」視為右括號。

由於任何時刻刪除的元素都必須是目前堆疊頂端，因此刪除次數不能超過放入次數。最後必須完成 $n$ 次放入與 $n$ 次刪除。

所以，合法操作序列正好對應於長度為 $2n$ 的合法括號序列，也就是 Dyck paths。其數量即為第 $n$ 個 Catalan number。

---

(a) 遞迴公式

令 $b_n$ 表示 $n$ 個元素可形成的合法堆疊排列數，並定義

$$b_0=1$$

考慮第一個元素與其配對的刪除操作。

在這次刪除之前，堆疊內部可能有 $i$ 個元素；刪除該元素之後，剩下的操作則包含 $n-1-i$ 個元素。這兩部分可以獨立形成合法操作，因此共有

$$b_i b_{n-1-i}$$

種方式。

對所有可能的 $i=0,1,\ldots,n-1$ 加總，得到：

$$\boxed{ b_n=\sum_{i=0}^{n-1} b_i b_{n-1-i} }$$

因此遞迴式為：

$$\boxed{ b_0=1,\qquad b_n=\sum_{i=0}^{n-1} b_i b_{n-1-i}\quad(n\ge 1) }$$

前幾項為：

$$b_0=1,\quad b_1=1,\quad b_2=2,\quad b_3=5,\quad b_4=14$$

---

(b) 解析公式

這正是 Catalan number 的標準形式，因此：

核心觀念

本題考查中序表示式（infix expression）轉後序表示式（postfix expression），也就是將運算子移到其兩個運算元之後。

各運算子的優先順序為：

$$括號 > 乘法、除法 > 加法、減法$$

同一優先順序的運算子採由左至右結合，因此：

$$x/y*z=(x/y)*z$$

後序表示式不需要括號，因為運算順序已由運算子的位置明確表示。

解題方法

原式為：

$$\frac{a}{c(b+d)}\div(e-a)\times c$$

先依括號與運算子優先順序分解。

第一步：處理括號 $(b+d)$

$$b+d$$

轉為後序形式：

$$b\ d\ +$$

第二步：處理 $c*(b+d)$

將 $c$ 與前一步結果相乘：

$$c*(b+d)$$

後序形式為：

$$c\ b\ d\ +\ *$$

第三步：處理 $a/(c*(b+d))$

將 $a$ 除以前一步結果：

$$a/[c*(b+d)]$$

後序形式為：

$$a\ c\ b\ d\ +\ *\ /$$

第四步：處理括號 $(e-a)$

$$e-a$$

後序形式為：

$$e\ a\ -$$

核心觀念

本題考查最小堆積（min-heap）的兩項性質：

1. 完全二元樹：除最後一層外，每層皆填滿，最後一層由左至右排列。
2. 最小堆積性質：每個父節點的值皆小於或等於其子節點，即

$$A[\text{parent}(i)] \leq A[i]$$

使用陣列表示時：

• 父節點：$\left\lfloor i/2 \right\rfloor$
• 左子節點：$2i$
• 右子節點：$2i+1$

插入時，元素先放在陣列末端，再向上調整（up-heap）；刪除最小值時，移除根節點，將最後元素移至根部，再向下調整（down-heap）。

---

解題方法

以下以陣列表示每一步的 min-heap。

1. insert 7

$$[7]$$

樹狀結構：

7

2. insert 4

4 先放在末端，再與父節點 7 交換：

$$[7,4] \rightarrow [4,7]$$

  4
 /
7

3. insert 3

3 放入下一個位置，與父節點 4 比較並交換：

$$[4,7,3] \rightarrow [3,7,4]$$

  3
 / \
7   4

4. insert 1

1 放在陣列末端：

$$[3,7,4,1]$$

1 小於父節點 7，因此交換：

$$[3,7,4,1] \rightarrow [3,1,4,7]$$

此時 1 已大於根節點 3，不需繼續上移。

    3
   / \
  1   4
 /
7

5. delete\ min

移除根節點 3，將最後元素 7 移至根部：

$$[3,1,4,7] \rightarrow [7,1,4]$$

7 與較小的子節點 1 交換：

$$[7,1,4] \rightarrow [1,7,4]$$

  1
 / \
7   4

6. insert 9

9 放入陣列末端，且 9 大於父節點 7：

$$[1,7,4,9]$$

    1
   / \
  7   4
 /
9

7. insert 2

2 放入陣列末端：

$$[1,7,4,9,2]$$

2 小於父節點 7，因此交換：

核心觀念

本題考查「以自底向上的方式建立 Heap」，也就是 Bottom-Up Build-Heap。

以最大堆（max heap）為例，必須滿足：

$$A[\mathrm{parent}(i)] \ge A[i]$$

陣列表示的完全二元樹中：

• 第 $i$ 個節點的父節點為 $\lfloor i/2 \rfloor$
• 左子節點為 $2i$
• 右子節點為 $2i+1$
• $i>\lfloor n/2\rfloor$ 的節點全部是葉節點

葉節點本身已經符合 Heap 條件，因此只需從最後一個內部節點開始，反向處理至根節點。

---

解題方法

建立最大堆的演算法如下：

1. 將 $n$ 個鍵值先依序放入完全二元樹。
2. 從第 $\lfloor n/2\rfloor$ 個節點開始。
3. 對每個內部節點執行 sift-down：
   • 比較該節點與兩個子節點。
   • 將較大的子節點與父節點交換。
   • 若交換後仍違反最大堆條件，繼續向下調整。
4. 處理順序為：

$$\left\lfloor\frac n2\right\rfloor, \left\lfloor\frac n2\right\rfloor-1,\ldots,2,1$$

此方法建立 Heap 的時間複雜度為：

$$O(n)$$

不可使用逐一插入的方式，因為每次插入可能需要向上調整 $O(\log n)$，總複雜度會是 $O(n\log n)$。

---

以 $n=15$ 為例

假設原始陣列為：

$$[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]$$

其完全二元樹如下：

                    1
              /           \
             2             3
          /     \       /     \
         4       5     6       7
        / \     / \   / \     / \
       8   9  10 11 12 13  14 15

因為：

$$\left\lfloor\frac{15}{2}\right\rfloor=7$$

所以從節點 $7$ 開始，依序處理節點 $7,6,5,4,3,2,1$。

處理節點 7

節點 $7$ 的子節點為 $14,15$，最大值為 $15$，交換：

節點 7：7 → 15
節點 15：15 → 7

處理節點 6

節點 $6$ 的子節點為 $12,13$，交換較大的 $13$：

節點 6：6 → 13
節點 13：13 → 6

處理節點 5

節點 $5$ 的子節點為 $10,11$，交換較大的 $11$：

節點 5：5 → 11
節點 11：11 → 5

處理節點 4

節點 $4$ 的子節點為 $8,9$，交換較大的 $9$：

參考書等級：中等（如《Introduction to Algorithms》CLRS 第7章）

(a) 判斷

1. 輸出為非遞增序列 False
   透過 PARTITION 將比基準 x 小的元素放在左側，較大的放右側，最終得到的是 遞增（由小到大）序列，非遞增（由大到小）不成立。

2. QUICKSORT 為穩定排序 False
   在 if A[j] < x 與 if A[j] > x 的交換過程中，若兩鍵相等仍會被交換，會改變相同鍵的相對次序，故不具穩定性。

3. QUICKSORT 為原地(in‑place)排序 True
   只使用常數個額外變數 i, j, p, r, q, x，無額外隨機存取陣列，故為原地演算法。

---

(b) 全部鍵相同的最壞執行時間

當所有 $n$ 個鍵相同，PARTITION 每次都只把基準 $x$ 移至最左或最右，使遞迴規模減少 1。遞迴關係：

$T(n)=T(n-1)+\Theta(n)$

解得 $T(n)=\Theta(n^{2})$，故最壞情形為 $O(n^{2})$。

---

(c) 三路切分實作

核心觀念

Open addressing 將所有資料直接存放在 hash table 中；發生碰撞時，利用 probe sequence 依序尋找下一個空槽。

一般形式為：

$$h(k,i)$$

其中：

• $k$：鍵值
• $i$：探測次數，從 $0$ 開始
• $m$：hash table 大小
• $h(k,0)$：第一次探測的位置

雙重雜湊的形式為：

$$h(k,i)=\bigl(h_1(k)+i\cdot h_2(k)\bigr)\bmod m$$

其中 $h_2(k)$ 是每次探測前進的步長。

---

（a）Linear Probing

線性探測每次向後移動一格，因此：

$$h(k,i)=\bigl(h'(k)+i\bigr)\bmod m$$

題目給定：

$$h'(k)=k\bmod m$$

代入可得：

$$\boxed{h(k,i)=\bigl((k\bmod m)+i\bigr)\bmod m}$$

由模運算性質，也可寫成：

$$\boxed{h(k,i)=(k+i)\bmod m}$$

當 $i=0$ 時，探測原始 hash 位置；若該位置被占用，則依序探測下一格。

---

（b）Double Hashing

題目給定：

$$h_1(k)=k\bmod 16$$ $$h_2(k)=1+(k\bmod 15)$$ $$h(k,i)=\bigl(h_1(k)+i\cdot h_2(k)\bigr)\bmod 16$$

依照題目順序插入各鍵值。

逐一插入

鍵值 $k$	$h_1(k)$	$h_2(k)$	探測位置	最終位置
$16$	$0$	$2$	$0$	$0$
$3$	$3$	$4$	$3$	$3$
$35$	$3$	$6$	$3,9$	$9$
$67$	$3$	$8$	$3,11$	$11$
$51$	$3$	$7$	$3,10$	$10$
$1$	$1$	$2$	$1$	$1$
$15$	$15$	$1$	$15$	$15$
$31$	$15$	$2$	$15,1,3,5$	$5$
$19$	$3$	$5$	$3,8$	$8$
$17$	$1$	$3$	$1,4$	$4$

以 $31$ 為例：

$$h_1(31)=31\bmod16=15$$ $$h_2(31)=1+(31\bmod15)=1+1=2$$

探測序列為：

$$\begin{aligned} h(31,0)&=(15+0\cdot2)\bmod16=15\\ h(31,1)&=(15+1\cdot2)\bmod16=1\\ h(31,2)&=(15+2\cdot2)\bmod16=3\\ h(31,3)&=(15+3\cdot2)\bmod16=5 \end{aligned}$$

位置 $15,1,3$ 均已占用，因此放入位置 $5$。

最終 hash table

索引	0	1	2	3	4	5	6	7
內容	16	1	空	3	17	31	空	空

核心觀念

本題考查三種最短路徑演算法的適用範圍：

• Dijkstra：解單源最短路徑，但要求所有邊權重皆非負。
• Bellman-Ford：解單源最短路徑，可處理負權重；也能偵測負環。
• Floyd-Warshall：解全點對最短路徑，可處理負權重，但不能在存在負環時定義有限的最短路徑。

若圖中存在從 $s$ 到 $t$ 的負環，沿著負環繞行次數越多，路徑成本便能無限下降：

$$\operatorname{dist}(s,t)=-\infty$$

因此「存在負環時仍能求得全點對最短路徑」通常是不成立的。

---

解題方法

逐一檢查每個演算法的：

1. 解決問題類型：單源或全點對。
2. 邊權重限制：是否允許負邊。
3. 負環影響：是否仍存在定義良好的最短路徑。

---

選項分析

(a) 錯誤

Dijkstra 的確是解單源最短路徑問題，但其正確性的關鍵條件是：

$$w(u,v)\ge 0$$

也就是所有邊權重必須非負。原因是 Dijkstra 採用貪心法，一旦選出目前距離最小的頂點，就認定其最短距離已經確定。若存在負邊，之後仍可能透過其他頂點找到更短的路徑，導致先前確定的結果錯誤。

例如有以下邊：

$$s\to u:1,\qquad s\to v:4,\qquad v\to u:-5$$

從 $s$ 出發時：

• 目前 $d(u)=1$
• 目前 $d(v)=4$

Dijkstra 會先確定 $u$ 的距離為 $1$。但實際上存在路徑

$$s\to v\to u$$

其成本為：

$$4+(-5)=-1$$

因此真正的最短距離是 $-1$，不是 $1$。此圖沒有負環，仍足以顯示 Dijkstra 不能處理一般負邊。

所以「沒有負環」並不足以保證 Dijkstra 正確，還必須要求所有邊權重非負。

---

(b) 錯誤

Bellman-Ford 解決的是單源最短路徑問題，即給定一個來源頂點 $s$，求：

$$\operatorname{dist}(s,v)$$

對所有頂點 $v$ 的最短距離。

它不能在單次執行中直接求出任意兩點 $u,v$ 之間的最短距離：

$$\operatorname{dist}(u,v)$$

核心觀念

本題考查：

• 深度優先搜尋（DFS）的三種頂點狀態。
• DFS 堆疊中「尚未完成處理」的頂點。
• 有向圖中的回邊（back edge）。
• 移除所有回邊即可消除有向環。

三種型態可解讀為：

• Type-0：尚未拜訪。
• Type-1：已拜訪但尚未完成，仍在 DFS 堆疊中。
• Type-2：已完成處理，已從 DFS 堆疊移除。

若目前處理頂點為 $v$：

• 邊 $(v,w)$ 若指向 Type-1 頂點，表示形成回邊，可能造成有向環。
• 邊 $(v,w)$ 若指向 Type-0 頂點，表示發現新頂點，必須繼續 DFS。
• 當 $v$ 沒有尚未處理的 Type-0 鄰點時，便完成 $v$，標記為 Type-2。

---

解題方法

1. 判斷 Line 8 的 Type-A

if v has a Type-A neighbor w in G
  Remove (v,w) from G

要使輸出圖為無環圖，必須移除造成循環的邊。

在 DFS 中，從目前頂點 $v$ 指向仍在搜尋路徑上的頂點 $w$，即：

$$v \to w,\qquad w\text{ 為 Type-1}$$

這種邊稱為回邊。它可能直接形成循環，因此應將其移除。

所以：

$$A=1$$

若 $A=0$，會刪除前往尚未拜訪頂點的邊，可能破壞必要的搜尋邊，卻沒有針對循環本身處理。

若 $A=2$，會刪除指向已完成頂點的邊。這類邊不代表目前 DFS 路徑上的循環，不應作為移除對象。

---

2. 判斷 Line 10 的 Type-B

else if v has a Type-B neighbor w in G
  Label w as Type-C
  S.push(w)

當 $v$ 沒有 Type-1 鄰點時，應尋找尚未拜訪的鄰點，繼續進行 DFS。

尚未拜訪的頂點是 Type-0，因此：

$$B=0$$

找到 Type-0 鄰點 $w$ 後，必須將它標記為「已發現但尚未完成」，也就是 Type-1，接著推入堆疊。

因此：

$$C=1$$

若 $C=0$，$w$ 仍會被視為未拜訪，可能重複推入堆疊。

若 $C=2$，則會錯誤地把尚未處理的頂點標記為已完成，破壞 DFS 狀態判斷。

---

3. 判斷 Line 14 的 Type-D

(a) 最大同時出航船隻數等於泊位序列與船隻序列的最長共同子序列（Longest Common Subsequence, LCS）長度。
計算 LCS：

$$\begin{aligned} \text{泊位}&= \text{DFADBDCEBEAGCF}\\ \text{船隻}&= \text{EFBEGECAEBDABD} \end{aligned}$$

核心觀念

本題的核心為一維動態規劃（1D Dynamic Programming, DP）中的字串／序列分割問題（Sequence Segmentation Problem）。

1. 最佳子結構（Optimal Substructure）：
   長度為 $i$ 的前綴序列之最小成本，取決於更短前綴序列的最佳成本加上最後一段形狀（不替換或套用某條轉換規則）的花費。
2. 重疊子問題（Overlapping Subproblems）：
   計算後續位置的最小成本時，會重複查詢相同前綴的最優解，適合建立一維陣列表記錄。

---

解題方法

1. 符號與規則整理

• 形狀原始成本（Cost Before Transformation）：

  • 正方形 $\text{☐} = 6$
  • 圓形 $\text{○} = 3$
  • 三角形 $\text{▷} = 2$

• 轉換規則（Transformation Rules）：

  • Rule #1：$(\text{☐}, \text{○})$，成本 $6 + 3 = 9 \to 7$（節省 2）
  • Rule #2：$(\text{☐}, \text{▷})$，成本 $6 + 2 = 8 \to 7$（節省 1）
  • Rule #3：$(\text{○}, \text{▷})$，成本 $3 + 2 = 5 \to 4$（節省 1）
  • Rule #4：$(\text{▷}, \text{☐})$，成本 $2 + 6 = 8 \to 6$（節省 2）
  • Rule #5：$(\text{☐}, \text{○}, \text{▷})$，成本 $6 + 3 + 2 = 11 \to 8$（節省 3）
  • Rule #6：$(\text{☐}, \text{▷}, \text{☐})$，成本 $6 + 2 + 6 = 14 \to 10$（節省 4）
  • Rule #7：$(\text{▷}, \text{☐}, \text{▷})$，成本 $2 + 6 + 2 = 10 \to 7$（節省 3）

• 待轉換序列（共 10 個圖形）：
  $S = (S_1, S_2, \dots, S_{10}) = (\text{☐}, \text{○}, \text{▷}, \text{☐}, \text{▷}, \text{☐}, \text{▷}, \text{☐}, \text{○}, \text{▷})$

  • 原始總成本 $= 6 + 3 + 2 + 6 + 2 + 6 + 2 + 6 + 3 + 2 = 38$。

---

2. 定義 DP 狀態與轉移方程式

定義 $DP[i]$ 為將前綴序列 $S[1 \dots i]$ 轉換後的最小總成本，基礎狀態 $DP[0] = 0$。

轉移方程式為：
$DP[i] = \min \begin{cases} DP[i-1] + \text{cost}(S[i]) \\ \min_{k \in \{2, 3\}} \{ DP[i-k] + \text{rule\_cost}(S[i-k+1 \dots i]) \quad \text{若存在匹配的規則}\} \end{cases}$

---

3. 逐步推導計算

• $i = 1$：$S[1] = \text{☐}$
  $DP[1] = DP[0] + 6 = 6$

• $i = 2$：$S[1 \dots 2] = (\text{☐}, \text{○})$

  • 不替換：$DP[1] + 3 = 6 + 3 = 9$
  • 套用 Rule #1 $(\text{☐}, \text{○})$：$DP[0] + 7 = 7$
    $DP[2] = \min(9, 7) = 7$

• $i = 3$：$S[1 \dots 3] = (\text{☐}, \text{○}, \text{▷})$

  • 不替換：$DP[2] + 2 = 7 + 2 = 9$
  • 套用 Rule #3 於 $S[2 \dots 3] = (\text{○}, \text{▷})$：$DP[1] + 4 = 6 + 4 = 10$
  • 套用 Rule #5 於 $S[1 \dots 3] = (\text{☐}, \text{○}, \text{▷})$：$DP[0] + 8 = 8$
    $DP[3] = \min(9, 10, 8) = 8$

• $i = 4$：$S[1 \dots 4] = (\text{☐}, \text{○}, \text{▷}, \text{☐})$

  • 不替換：$DP[3] + 6 = 8 + 6 = 14$
  • 套用 Rule #4 於 $S[3 \dots 4] = (\text{▷}, \text{☐})$：$DP[2] + 6 = 7 + 6 = 13$
    $DP[4] = \min(14, 13) = 13$

• $i = 5$：$S[1 \dots 5] = (\text{☐}, \text{○}, \text{▷}, \text{☐}, \text{▷})$

  • 不替換：$DP[4] + 2 = 13 + 2 = 15$
  • 套用 Rule #2 於 $S[4 \dots 5] = (\text{☐}, \text{▷})$：$DP[3] + 7 = 8 + 7 = 15$
  • 套用 Rule #7 於 $S[3 \dots 5] = (\text{▷}, \text{☐}, \text{▷})$：$DP[2] + 7 = 7 + 7 = 14$
    $DP[5] = \min(15, 15, 14) = 14$

• $i = 6$：$S[1 \dots 6] = (\text{☐}, \text{○}, \text{▷}, \text{☐}, \text{▷}, \text{☐})$

  • 不替換：$DP[5] + 6 = 14 + 6 = 20$
  • 套用 Rule #4 於 $S[5 \dots 6] = (\text{▷}, \text{☐})$：$DP[4] + 6 = 13 + 6 = 19$
  • 套用 Rule #6 於 $S[4 \dots 6] = (\text{☐}, \text{▷}, \text{☐})$：$DP[3] + 10 = 8 + 10 = 18$
    $DP[6] = \min(20, 19, 18) = 18$

• $i = 7$：$S[1 \dots 7] = (\text{☐}, \text{○}, \text{▷}, \text{☐}, \text{▷}, \text{☐}, \text{▷})$

  • 不替換：$DP[6] + 2 = 18 + 2 = 20$
  • 套用 Rule #2 於 $S[6 \dots 7] = (\text{☐}, \text{▷})$：$DP[5] + 7 = 14 + 7 = 21$