115 年 國立臺北大學資訊工程研究所《資料結構與演算法》

核心觀念

本題考查：

• 中序表示法（infix notation）
• 後序表示法（postfix notation）
• 運算子優先順序與結合性
• 二元運算式樹（binary expression tree）

原式為：

$$(A+B)\times C+(D-E)\times(F+G)$$

括號先計算，乘法優先於加法，因此實際結構為：

$$\bigl((A+B)\times C\bigr)+\bigl((D-E)\times(F+G)\bigr)$$

後序表示法的規則是：

1. 先處理左子運算式。
2. 再處理右子運算式。
3. 最後輸出目前運算子的符號。

因此，二元運算式樹的後序走訪結果就是 postfix notation。

解題方法

左半部

左半部為：

$$(A+B)\times C$$

其中：

$$(A+B)\Rightarrow A\ B\ +$$

再將結果與 $C$ 進行乘法：

$$(A+B)\times C\Rightarrow A\ B\ +\ C\ \times$$

右半部

右半部為：

$$(D-E)\times(F+G)$$

先處理兩個括號：

$$(D-E)\Rightarrow D\ E\ -$$ $$(F+G)\Rightarrow F\ G\ +$$

再進行乘法：

$$(D-E)\times(F+G) \Rightarrow D\ E\ -\ F\ G\ +\ \times$$

合併左右子運算式

整個式子的最外層運算子是加法，因此最後輸出 $+$：

$$(A+B)\times C+(D-E)\times(F+G)$$

轉換為：

$$A\ B\ +\ C\ \times\ D\ E\ -\ F\ G\ +\ \times\ +$$

核心觀念

BST（Binary Search Tree，二元搜尋樹）滿足：

• 任一節點左子樹的鍵值皆小於該節點。
• 任一節點右子樹的鍵值皆大於該節點。
• Postorder traversal（後序走訪）順序為：

$$\text{Left} \rightarrow \text{Right} \rightarrow \text{Root}$$

因此，後序序列的最後一個元素必為整棵 BST 的根節點。假設所有鍵值皆不重複，BST 可由後序序列唯一決定。

解題方法

給定後序序列：

$$B \rightarrow A \rightarrow D \rightarrow C \rightarrow H \rightarrow G \rightarrow F \rightarrow E$$

1. 決定根節點

最後一個元素為 $E$，所以根節點是 $E$。

將其餘元素依照大小分成左右子樹：

• 小於 $E$：$B,A,D,C$，屬於左子樹
• 大於 $E$：$H,G,F$，屬於右子樹

因此：

$$\text{Left of }E: B,A,D,C$$ $$\text{Right of }E: H,G,F$$

2. 建立左子樹

左子樹的後序序列為：

$$B \rightarrow A \rightarrow D \rightarrow C$$

最後一個元素為 $C$，所以左子樹根節點為 $C$。

依照 $C$ 分割：

• 小於 $C$：$B,A$
• 大於 $C$：$D$

所以 $C$ 的左子樹後序序列為 $B \rightarrow A$，右子樹為 $D$。

對 $B \rightarrow A$ 而言，最後一個元素 $A$ 為根節點；$B<A$，因此 $B$ 為 $A$ 的左子節點。

核心觀念

在快速排序（Quicksort）完成第一次分割（Partition）後，若某元素 $A[i]$ 為該次採用的樞紐（Pivot），則該元素必須滿足以下兩項條件：

1. 不小於左側所有元素：$\max_{0 \le j < i} A[j] \le A[i]$
2. 不大於右側所有元素：$A[i] \le \min_{i < k < n} A[k]$

即該 Pivot 已經被安置於陣列最終排序完成後的正確位置上。

---

關鍵推導

給定陣列 $A = [8, 4, 13, 11, 16, 20, 19, 24, 18, 29]$（共 10 個元素），逐一檢驗各位置是否符合 Pivot 條件：

| 索引 $i$ | 元素 $A[i]$ | 左側最大值 $\max(A[0..i-1])$ | 右側最小值 $\min(A[i+1..9])$ | 是否可為 Pivot | 理由 |

核心觀念

本題考查最大堆積（max-heap）的插入與刪除最大值操作。

最大堆積必須同時符合：

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

$$\text{parent} \geq \text{child}$$

最大堆積通常以陣列儲存：

• 插入：將新元素放在陣列最後，再向上調整（bubble up）。
• Extract-Max：移除根節點，將最後一個元素移至根，再向下調整（heapify down）。

---

解題方法

依序執行 8 個操作，並以陣列表示當下的最大堆積。

1. Insert 8

插入後：

$$[8]$$

樹狀結構：

8

---

2. Insert 4

先將 4 放在最後，再與父節點 8 比較。因為 $4 < 8$，不需調整。

$$[8,4]$$

  8
 /
4

---

3. Insert 9

先放在陣列最後：

$$[8,4,9]$$

9 的父節點為 8，因為 $9 > 8$，交換：

$$[9,4,8]$$

  9
 / \
4   8

---

4. Insert 6

先放在最後：

$$[9,4,8,6]$$

6 的父節點為 4，因為 $6 > 4$，交換：

$$[9,6,8,4]$$

    9
   / \
  6   8
 /
4

---

5. Extract-Max

移除根節點 9，將最後一個元素 4 移至根：

$$[4,6,8]$$

此時 4 的子節點為 6 與 8，最大子節點為 8。因為 $4 < 8$，交換：

$$[8,6,4]$$

    8
   / \
  6   4

---

6. Insert 13

先放在最後：

$$[8,6,4,13]$$

13 的父節點為 6，交換後：

核心觀念

AVL 樹要求每個節點的左右子樹高度差至多為 $1$。定義平衡因子為

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

插入後若某節點的平衡因子變成 $2$ 或 $-2$，就要依插入方向判斷旋轉類型。本題會依序用到 LL 單旋與 LR 雙旋。

解題方法

原始樹為：

       15
      /  \
    10    25
   /
  5

插入鍵值 2

依二元搜尋樹規則，$2<15$、$2<10$、$2<5$，因此插入為 $5$ 的左子節點：

       15
      /  \
    10    25
   /
  5
 /
2

節點 $10$ 的左子樹比右子樹高 $2$，而新節點位於左子節點的左側，屬於 LL 型。以 $10$ 為軸向右旋轉，得到：

       15
      /  \
     5    25
    / \
   2  10

插入鍵值 8

從目前的樹搜尋：$8<15$、$8>5$、$8<10$，因此插入為 $10$ 的左子節點：

核心觀念

Dijkstra 演算法用來求非負權重圖中，起點到各節點的最短距離。每一步從尚未確定的節點中，選取目前暫定距離最小者，將其距離確定，再用它更新相鄰節點：

$$d(v)\leftarrow\min\bigl(d(v),\,d(u)+w(u,v)\bigr)$$

其中 $d(v)$ 是起點 $S$ 到節點 $v$ 的暫定距離，$w(u,v)$ 是邊 $(u,v)$ 的權重。

解題方法

初始化 $d(S)=0$，其餘節點距離為 $\infty$。從 $S$ 出發，暫定距離為 $5$ 的 $A、B、M$ 同距；同距時處理順序可以不同，不影響最短距離。

確定節點	距離	更新後的暫定距離
$S$	$0$	$E=1,\ A=5,\ B=5,\ M=5$
$E$	$1$	$F=8$；經 $E$ 到 $A$ 為 $7$，不優於 $5$
$A$	$5$	$C=10,\ K=11$
$M$	$5$	$L=7$；經 $M$ 到 $B$ 為 $9$，不優於 $5$
$B$	$5$	經 $B$ 到 $L=8、G=9、F=9$，皆不優於現有距離

核心觀念

最小生成樹（MST）必須連接圖中的所有頂點、不可形成迴圈，且總權重最小。這張圖有 8 個頂點，因此任何生成樹都恰有 $8-1=7$ 條邊。

• Kruskal 演算法：依權重由小到大檢查邊；若加入該邊不會形成迴圈，就選取。
• Prim 演算法：從一個頂點開始，每次選擇連接「已加入樹中的頂點」與「樹外頂點」的最小權重邊。

Kruskal 演算法

將邊依權重遞增排列，逐一檢查：

權重	邊	處理結果
2	$(E,H)$	選取
14	$(D,I)$	選取
15	$(C,E)$	選取
16	$(A,F)$	選取
19	$(A,I)$	選取
20	$(C,D)$	選取
21	$(C,I)$	略過；會形成迴圈
23	$(A,C)$	略過；會形成迴圈
24	$(D,E)$	略過；會形成迴圈
25	$(E,F)$	略過；會形成迴圈
26	$(C,F)$	略過；會形成迴圈
30	$(A,B)$	選取，連入頂點 $B$

選取 $(A,B)$ 後，8 個頂點已全部連通，且共選了 7 條邊，因此演算法完成。前 6 條選取的邊將 $A,C,D,E,F,H,I$ 連成一個連通分量；$(A,B)$ 再將 $B$ 加入。

最小生成樹總權重為：

$$2+14+15+16+19+20+30=116$$

Prim 演算法

核心觀念

本題考查編輯距離（Edit Distance），又稱 Levenshtein Distance。給定兩字串，允許使用三種編輯操作：

• 插入（Insertion）：插入一個字元，成本為 $1$。
• 刪除（Deletion）：刪除一個字元，成本為 $1$。
• 替換（Substitution）：將一個字元替換成另一個字元，成本為 $1$。
• 若兩字元相同，直接保留，成本為 $0$。

令 $D(i,j)$ 表示將 str1 的前 $i$ 個字元轉換成 str2 的前 $j$ 個字元所需的最少操作次數。

---

解題方法：動態規劃遞迴公式

設 str1[i] 與 str2[j] 分別為目前考慮的最後一個字元，定義：

$$cost(i,j)= \begin{cases} 0, & \text{若 } str1[i]=str2[j] \\ 1, & \text{若 } str1[i]\ne str2[j] \end{cases}$$

邊界條件

若其中一個字串為空字串：

$$D(0,j)=j$$

表示需要插入 $j$ 個字元。

$$D(i,0)=i$$

表示需要刪除 $i$ 個字元。

遞迴公式

當 $i>0$ 且 $j>0$ 時，最後一步有三種可能：

1. 刪除 str1 的最後一個字元：$D(i-1,j)+1$
2. 插入 str2 的最後一個字元：$D(i,j-1)+1$
3. 保留或替換最後一個字元：$D(i-1,j-1)+cost(i,j)$

因此：

$$D(i,j)=\min \begin{cases} D(i-1,j)+1 \\ D(i,j-1)+1 \\ D(i-1,j-1)+cost(i,j) \end{cases}$$

若兩字元相同，第三項就是不做任何編輯；若不同，第三項代表替換。

---

計算 INTENTION 到 EXECUTION

令：

• str1 = INTENTION
• str2 = EXECUTION

兩字串長度皆為 $9$。

使用上述遞迴公式建立動態規劃表。列表示 INTENTION 的前綴，欄表示 EXECUTION 的前綴：

$D(i,j)$	空字串	E	X	E	C	U	T	I	O	N
空字串	0	1	2	3	4	5	6	7	8	9
I	1	1	2	2	3	4	5	6	7	8
N	2	2	2	3	4	5	6	7	8	7

核心觀念

Huffman 編碼（Huffman Coding） 是一種貪婪演算法（Greedy Algorithm）。建樹時每次選擇權重（頻率）最小的兩個節點合併，直到形成單一樹根。慣例設定左分支編碼為 0、右分支編碼為 1。

---

建樹步驟（Step-by-Step）

初始節點集合：$\{A:5, B:12, D:19, C:33, E:40, F:41\}$

1. 合併最小兩節點 $A(5)$ 與 $B(12)$：

   • 建立內部節點 $n_1 = 5 + 12 = 17$（左子樹 $A$，右子樹 $B$）。
   • 剩餘集合：$\{n_1:17, D:19, C:33, E:40, F:41\}$

2. 合併最小兩節點 $n_1(17)$ 與 $D(19)$：

   • 建立內部節點 $n_2 = 17 + 19 = 36$（左子樹 $n_1$，右子樹 $D$）。
   • 剩餘集合：$\{C:33, n_2:36, E:40, F:41\}$

3. 合併最小兩節點 $C(33)$ 與 $n_2(36)$：

   • 建立內部節點 $n_3 = 33 + 36 = 69$（左子樹 $C$，右子樹 $n_2$）。
   • 剩餘集合：$\{E:40, F:41, n_3:69\}$

4. 合併最小兩節點 $E(40)$ 與 $F(41)$：

   • 建立內部節點 $n_4 = 40 + 41 = 81$（左子樹 $E$，右子樹 $F$）。