109 年 國立政治大學資訊管理學系碩士班科技組《資料結構》

核心觀念

本題考查最長共同子序列（Longest Common Subsequence, LCS）與動態規劃。

• 「子序列」可以刪除字元，但不能改變原有順序。
• 共同子序列必須同時出現在 $X$ 與 $Y$ 中。
• $L[i,j]$ 表示 $X[0..i]$ 與 $Y[0..j]$ 的一個最長共同子序列。
• 通常同時記錄其長度 $|L[i,j]|$，以便進行比較。

本題字串為：

$$X=\text{BAACBBSCHAA}$$ $$Y=\text{ABABCSCAH}$$

索引如下：

$$\begin{array}{c|ccccccccccc} i&0&1&2&3&4&5&6&7&8&9&10\\ \hline X[i]&B&A&A&C&B&B&S&C&H&A&A \end{array}$$ $$\begin{array}{c|ccccccccc} j&0&1&2&3&4&5&6&7&8\\ \hline Y[j]&A&B&A&B&C&S&C&A&H \end{array}$$

---

1.1 遞迴關係與基本情況

基本情況

若其中一個字串為空字串，便不存在非空共同子序列：

$$L[i,-1]=\varepsilon \qquad (i\geq -1)$$ $$L[-1,j]=\varepsilon \qquad (j\geq -1)$$

其中 $\varepsilon$ 表示空字串，因此：

$$|L[i,-1]|=|L[-1,j]|=0$$

當最後一個字元相同

若 $X[i]=Y[j]$，則此字元可以接在前一個子問題的解後面：

$$L[i,j]=L[i-1,j-1]\cdot X[i]$$

因此長度關係為：

$$|L[i,j]|=|L[i-1,j-1]|+1$$

原因是 $X[i]$ 與 $Y[j]$ 相同，將它納入共同子序列必能使長度增加 $1$。

當最後一個字元不同

若 $X[i]\neq Y[j]$，則 $X[i]$ 與 $Y[j]$ 不可能同時作為共同子序列的最後一個字元，因此必須捨去其中一個：

$$|L[i,j]|= \max\left(|L[i-1,j]|,\ |L[i,j-1]|\right)$$

若兩者長度相同，任取其中一個即可；若要保留所有不同的 LCS，則需同時保留兩個方向的結果。

---

1.2 動態規劃演算法

令 $C[i,j]=|L[i,j]|$，先建立大小為 $(m+1)\times(n+1)$ 的表格。

長度計算

for i = 0 to m:
    C[i][-1] = 0

for j = 0 to n:
    C[-1][j] = 0

for i = 0 to m:
    for j = 0 to n:
        if X[i] == Y[j]:
            C[i][j] = C[i-1][j-1] + 1
        else:
            C[i][j] = max(C[i-1][j], C[i][j-1])

回溯取得實際 LCS

從 $C[m,n]$ 開始回溯：

1. 若 $X[i]=Y[j]$，將此字元加入答案，移至 $(i-1,j-1)$。
2. 若 $X[i]\neq Y[j]$：
   • 若 $C[i-1,j]>C[i,j-1]$，移至 $(i-1,j)$。
   • 若 $C[i,j-1]>C[i-1,j]$，移至 $(i,j-1)$。
   • 若兩者相等，任選一個方向；不同選擇可能得到不同但同樣最長的 LCS。

2.1 建立 AVL 樹

插入序列依次平衡後得到的最終樹形如下（以「父節點 → 左子、右子」表示）

11 → 6 , 28
6  → 5 , 7
5  → 2 , ∅
2  → ∅ , ∅
7  → ∅ , ∅
28 → 18 , 35
18 → 13 , 20
13 → 12 , 16
12 → ∅ , ∅
16 → ∅ , ∅
20 → ∅ , 22
22 → ∅ , ∅
35 → 29 , 58
29 → ∅ , ∅
58 → ∅ , ∅

各節點的平衡因子皆在 $[-1,1]$，符合 AVL 定義。

【答案】上述樹即為插入全部 16 個鍵後的 AVL 二元搜尋樹。

---

2.2 刪除鍵 22 後的 AVL 樹

22 為葉節點，直接移除後重新計算平衡因子，仍無需旋轉，得到：

核心觀念

本題考查雜湊表（Hash Table）處理碰撞（collision）的三種方法：

1. Separate Chaining（分離鏈結）
   每個索引位置存放一條鏈結串列，發生碰撞時，將資料接在同一個串列中。

2. Linear Probing（線性探測）
   發生碰撞時，依序檢查下一個位置：
   $h_i(k)=(h(k)+i)\bmod N,\quad i=0,1,2,\ldots$

3. Double Hashing（雙重雜湊）
   使用第二個雜湊函數決定每次探測的位移量：
   $h_i(k)=(h(k)+i\cdot d(k))\bmod N$

本題中：

$N=17,\qquad h(k)=k\bmod 17$

雙重雜湊的位移函數為：

$d(k)=11-(k\bmod 11)$

插入順序依題目所列：

$98,77,19,29,41,82,12,108,53,25,54,42$

---

3.1 Separate Chaining

先計算每個 key 的雜湊位置：

Key	$h(k)=k\bmod 17$
98	13
77	9
19	2
29	12
41	7
82	14
12	12
108	6
53	2
25	8
54	3
42	8

相同索引的 key 放在同一條鏈結串列中，因此：

索引	鏈結串列
0	空
1	空
2	$19\rightarrow53$
3	$54$
4	空
5	空
6	$108$
7	$41$
8	$25\rightarrow42$
9	$77$
10	空
11	空
12	$29\rightarrow12$
13	$98$
14	$82$
15	空
16	空

鏈結串列中的先後順序依照題目插入順序排列。

---

3.2 Linear Probing

線性探測的規則是：若原始位置已被占用，就依序檢查下一格，超過索引 $16$ 時回到索引 $0$。

逐一插入：

• $98$：$h(98)=13$，放入 13。
• $77$：$h(77)=9$，放入 9。
• $19$：$h(19)=2$，放入 2。
• $29$：$h(29)=12$，放入 12。
• $41$：$h(41)=7$，放入 7。
• $82$：$h(82)=14$，放入 14。
• $12$：原位置 12 已有 $29$，依序檢查 13、14，皆已占用，故放入 15。
• $108$：$h(108)=6$，放入 6。
• $53$：原位置 2 已有 $19$，下一格 3 為空，故放入 3。
• $25$：$h(25)=8$，放入 8。
• $54$：原位置 3 已有 $53$，下一格 4 為空，故放入 4。
• $42$：原位置 8 已有 $25$，索引 9 已有 $77$，索引 10 為空，故放入 10。

最後的線性探測結果：

索引	內容
0	空
1	空
2	19
3	53
4	54
5	空
6	108
7	41
8	25
9	77
10	42
11	空
12	29
13	98
14	82
15	12
16	空

---

3.3 Double Hashing

雙重雜湊的探測公式為：

$h_i(k)=\bigl(h(k)+i\cdot d(k)\bigr)\bmod 17$

其中：

$d(k)=11-(k\bmod 11)$

逐一計算如下：

核心觀念

本題考查三項圖論基本操作：

1. 加權無向圖：每條道路連接兩個地點，且具有成本。
2. Edge-list／鄰接串列表示法：每個節點保存地點名稱與其相鄰邊；無向邊需在兩端節點各記錄一次。
3. 圖形走訪：
   • DFS（Depth-First Search）：使用遞迴或堆疊，先深入到底再回溯。
   • BFS（Breadth-First Search）：使用佇列，按照距離起點的層次逐層拜訪。

以下假設同一節點的鄰接邊，依照題目給出的順序處理。每個節點第一次被發現時，將其標記為已拜訪，以避免無向圖中的循環造成重複走訪。

---

4.1 Edge-list 結構

每個節點可表示為：

$$\text{Vertex}=(\text{name},\text{firstEdge})$$

每條邊可表示為：

$$\text{Edge}=(\text{neighbor},\text{cost},\text{nextEdge})$$

由於本題是無向圖，因此例如 Taipei 與 Taidong 之間的道路，必須同時出現在 Taipei 的邊串列與 Taidong 的邊串列中。

鄰接串列表示

節點	相鄰邊（目的地，成本）
Taipei	Taidong，750；Hualian，500；Taichung，400
Taidong	Taipei，750；Hualian，350；Kaoshiung，450；GreenIsland，800；Kenting，550
Hualian	Taipei，500；Taidong，350；GreenIsland，1650；Nanto，700
GreenIsland	Hualian，1650；Taidong，800
Kaoshiung	Taidong，450；Kenting，400
Kenting	Kaoshiung，400；Taidong，550
Taichung	Taipei，400；Nanto，200
Nanto	Taichung，200；Hualian，700

例如 Taipei 的結構可寫成：

$$\text{Taipei} \rightarrow (\text{Taidong},750) \rightarrow (\text{Hualian},500) \rightarrow (\text{Taichung},400)$$

其中每個邊節點還會有 nextEdge 指標，指向下一條相鄰邊。

---

4.2 DFS

演算法

DFS(v):
    visited[v] = true
    輸出 v

    for each edge (v, u) in adjacency list of v:
        if visited[u] == false:
            輸出邊 (v, u)
            DFS(u)

若圖不保證連通，則需對所有節點再加上外層迴圈：

for each vertex v:
    if visited[v] == false:
        DFS(v)

從 Taipei 開始走訪

依照鄰接邊順序：

1. 拜訪 Taipei。
2. 沿 Taipei → Taidong 深入。
3. 沿 Taidong → Hualian 深入。
4. 沿 Hualian → GreenIsland 深入。
5. GreenIsland 的相鄰節點皆已拜訪，回溯至 Hualian。
6. 沿 Hualian → Nanto 深入。
7. 沿 Nanto → Taichung 深入。
8. Taichung 的相鄰節點皆已拜訪，回溯。
9. 回到 Taidong，沿 Taidong → Kaoshiung 深入。
10. 沿 Kaoshiung → Kenting 深入，完成走訪。

節點拜訪順序

$$\boxed{ \text{Taipei} \rightarrow \text{Taidong} \rightarrow \text{Hualian} \rightarrow \text{GreenIsland} \rightarrow \text{Nanto} \rightarrow \text{Taichung} \rightarrow \text{Kaoshiung} \rightarrow \text{Kenting} }$$

DFS 發現的樹邊

每條邊表示「第一次發現新節點」時所使用的邊：

1. Taipei — Taidong，750
2. Taidong — Hualian，350
3. Hualian — GreenIsland，1650
4. Hualian — Nanto，700
5. Nanto — Taichung，200
6. Taidong — Kaoshiung，450
7. Kaoshiung — Kenting，400

因此 DFS 形成的走訪樹為：

Taipei
└── Taidong
    ├── Hualian
    │   ├── GreenIsland
    │   └── Nanto
    │       └── Taichung
    └── Kaoshiung
        └── Kenting

其中 Taidong — GreenIsland 雖然是圖中的邊，但 GreenIsland 已由 Hualian 發現，因此它不是 DFS 樹邊，只會被檢查為已拜訪節點。

複雜度

若使用鄰接串列：

$$O(|V|+|E|)$$

其中 $|V|$ 是節點數，$|E|$ 是邊數。額外空間為：

$$O(|V|)$$

主要用於 visited 陣列與遞迴堆疊。

---