109 年 國立成功大學資訊工程系碩士班《程式設計》

這題主要測試對資料結構基本概念的理解，涵蓋雜湊表、圖論、最小生成樹、圖的遍歷以及拓撲排序。

(1) 靜態雜湊（Static Hashing）中的開放定址法（Open Addressing）在最壞情況下，成功搜尋的比較次數確實可能達到 $O(n)$。然而，將搜尋時間降低到 $O(\log n)$ 通常是藉由使用平衡搜尋樹（如 AVL 樹或紅黑樹）來實現，而非靜態雜湊。因此，前半句陳述是正確的，後半句將 $O(\log n)$ 的時間複雜度歸因於雜湊或平衡搜尋樹的應用，但若是在指靜態雜湊本身，則不正確。若題目意指「一般情況下」，雜湊表的搜尋可以接近 $O(1)$，但最壞情況確實是 $O(n)$。與平衡搜尋樹的 $O(\log n)$ 比較，若是指雜湊表無法透過靜態雜湊達到 $O(\log n)$，則敘述可能誤導。然而，若將 "balanced search tree" 作為一種獨立的資料結構來看，其搜尋時間為 $O(\log n)$，與雜湊表（最壞 $O(n)$）不同。此題的陳述「The number could be reduced to $O(\log n)$ by using balanced search tree」是正確的，表示存在另一種結構（平衡搜尋樹）能達成此時間複雜度，但不表示雜湊表本身能。

判斷：True

(2) 圖論中的握手定理（Handshaking Lemma）指出，一個圖中所有頂點的度數之和等於邊數的兩倍，即 $\sum_{i=1}^{n} d_i = 2e$。題目中的求和上限為 $n-1$，且沒有乘以 2，因此是錯誤的。

判斷：False
修正： 在圖 $G$ 中，所有頂點的度數之和等於邊數的兩倍，即 $e = \frac{1}{2} \sum_{i=1}^{n} d_i$。

核心觀念

本題旨在考驗資料結構中 布隆過濾器（Bloom Filter） 的運作原理及其 假陽性率（False Positive Rate，即題目所稱的 filter error probability） 之機率推導。

涉及的關鍵定義與機率原理包括：

1. 獨立均勻雜湊假設（Simple Uniform Hashing Assumption）：
   每個雜湊函式 $f_i$ 將任意鍵值（key）映射至長度為 $m$ 的位元陣列中任一位置的機率均為 $\frac{1}{m}$，且各次雜湊相互獨立。
2. 位元未被設為 1 的機率：
   單一鍵值在單一雜湊函式作用下，未選中某特定位元的機率為 $1 - \frac{1}{m}$。
3. 假陽性（False Positive）發生的充分必要條件：
   當待查詢的鍵值 $k$ 不在集合中，但其對應的 $h$ 個雜湊位置 $f_1(k), f_2(k), \dots, f_h(k)$ 恰好全部都被先前的加入操作設為 1 時，系統會錯誤回答「maybe」，此即為布隆過濾器的錯誤（filter error）。
4. 常用極限近似公式：
   當 $m$ 甚大時，利用重要極限 $\lim_{m \to \infty} \left(1 - \frac{1}{m}\right)^m = e^{-1}$，可將機率以指數形式表示。

---

解題方法

題目設定：

• 位元陣列大小為 $m$。
• 共有 $h$ 個獨立且均勻的雜湊函式。
• 經過 $u$ 次更新（新增元素操作）。
• 現對一任意鍵值進行查詢，求發生過濾器錯誤（filter error）的機率。

步驟一：單一更新事件對某特定位元的影響

考慮陣列中的任意特定位元 $b$（例如第 $j$ 個位元，其中 $1 \le j \le m$）：

• 某一次新增操作中，一個雜湊函式選中位元 $b$ 的機率為 $\frac{1}{m}$。
• 該雜湊函式「未選中」位元 $b$ 的機率為： $$1 - \frac{1}{m}$$

步驟二：經過 $u$ 次更新後，某特定位元仍為 0 的機率

每次更新使用 $h$ 個獨立的雜湊函式，因此 $u$ 次更新共執行了 $h \times u$ 次獨立的雜湊位元選取。
該特定位元 $b$ 在所有 $h \cdot u$ 次雜湊選取中皆未被選中的機率為：

$$P(\text{bit } b = 0) = \left(1 - \frac{1}{m}\right)^{hu}$$

若採用指數逼近法（當 $m$ 很大時）：

$$\left(1 - \frac{1}{m}\right)^{hu} = \left[\left(1 - \frac{1}{m}\right)^m\right]^{\frac{hu}{m}} \approx e^{-\frac{hu}{m}}$$

核心觀念

本題要求建構加權無向圖的最小生成樹（Minimum Spanning Tree, MST）。最小生成樹必須：

• 包含所有頂點；
• 不形成迴圈；
• 若有 $n$ 個頂點，必須恰有 $n-1$ 條邊；
• 所有邊權重總和最小。

本圖共有 $6$ 個頂點，因此最小生成樹應包含 $5$ 條邊。採用 Kruskal 演算法，依邊權重由小到大選邊；若加入某邊會形成迴圈，就捨棄該邊。

圖中邊與權重

依原圖頂點標記，邊如下：

$$\begin{array}{c|c} \text{邊} & \text{權重} \\ \hline (b,d) & 7\\ (b,e) & 9\\ (c,d) & 12\\ (d,e) & 13\\ (a,f) & 15\\ (c,e) & 18\\ (b,f) & 21\\ (a,b) & 24\\ (e,f) & 29 \end{array}$$

解題方法：Kruskal 演算法

依權重排序並逐邊判斷：

權重	邊	判斷	原因
7	$(b,d)$	選取	連接兩個不同頂點
9	$(b,e)$	選取	不形成迴圈
12	$(c,d)$	選取	不形成迴圈

這題主要測試對漸進符號 $O$（大 O 符號）的定義和理解，特別是對於指數函數的判斷。

核心概念：
一個函數 $f(n)$ 被稱為 $O(g(n))$（讀作 $f(n)$ 是 $O$ of $g(n)$）是指存在正常數 $c$ 和 $n_0$，使得對於所有 $n \ge n_0$，都有 $0 \le f(n) \le c \cdot g(n)$ 成立。簡單來說，就是 $f(n)$ 的成長速度不超過 $g(n)$ 的常數倍。

第一小題：Is $5^{n+1} = O(5^n)$?

我們需要判斷 $f(n) = 5^{n+1}$ 的成長速度是否不超過 $g(n) = 5^n$ 的常數倍。
根據 $O$ 的定義，我們尋找常數 $c > 0$ 和 $n_0 \ge 1$，使得對於所有 $n \ge n_0$，都有 $5^{n+1} \le c \cdot 5^n$。

我們可以這樣簡化 $5^{n+1}$：
$5^{n+1} = 5^n \cdot 5^1 = 5 \cdot 5^n$

現在我們將這個結果代入不等式：
$5 \cdot 5^n \le c \cdot 5^n$

為了使這個不等式成立，我們可以選擇 $c=5$。
那麼，不等式變為：
$5 \cdot 5^n \le 5 \cdot 5^n$
這個不等式對於所有 $n \ge 1$ 都成立。

因此，我們找到了常數 $c=5$ 和 $n_0=1$（或者任何 $n_0 \ge 1$ 都可以），使得對於所有 $n \ge n_0$，都有 $5^{n+1} \le c \cdot 5^n$。

結論： 是的，$5^{n+1} = O(5^n)$。

第二小題：Is $6^{2n} = O(6^n)$?

我們需要判斷 $f(n) = 6^{2n}$ 的成長速度是否不超過 $g(n) = 6^n$ 的常數倍。

核心觀念

本題考遞迴式的漸近界。關鍵在於把整個 $T(n)$ 除以 $n$，觀察每層遞迴工作量如何累積；遞迴參數每次開平方，直到落入基底範圍。

解題方法

令 $R(n)=T(n)/n$。將原式兩邊除以 $n$：

$$R(n) =\frac{T(n)}{n} =\frac{\sqrt n\,T(\sqrt n)}{n}+1 =\frac{T(\sqrt n)}{\sqrt n}+1 =R(\sqrt n)+1$$

每遞迴一次，$R$ 增加 $1$。若連續開平方 $k$ 次，參數變成 $n^{1/2^k}$。遞迴在此參數進入固定的基底範圍時停止，因此 $k$ 滿足：

$$n^{1/2^k}=O(1)$$

取對數可得 $2^k=\Theta(\log n)$，所以：

核心觀念

Quicksort 每次選擇一個 pivot，利用 partition 將資料分成兩部分：

• 小於 pivot 的元素
• 大於 pivot 的元素

若兩部分大小分別為 $k$ 與 $n-k-1$，則遞迴式為

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

其中 $\Theta(n)$ 是一次 partition 的成本。

Quicksort 的效率關鍵在於 pivot 是否能將資料分得平均：

• 分割接近平衡：時間複雜度為 $O(n\log n)$
• 每次都分成 $0$ 與 $n-1$：時間複雜度退化為 $O(n^2)$

因此，本題要求的是設計 pivot 選擇方式，使遞迴樹高度維持在 $O(\log n)$。

---

解題方法：每次選取中位數作為 pivot

每次 partition 前，使用線性時間的選擇演算法找出目前子陣列的真正中位數，將它作為 pivot。

若目前有 $n$ 個元素，選出的中位數會將資料分成大小約為 $n/2$ 的兩部分，因此：

$$T(n)=2T\left(\frac{n}{2}\right)+\Theta(n)$$

使用 Master Theorem：

• $a=2$
• $b=2$
• $f(n)=\Theta(n)$
• $n^{\log_b a}=n^{\log_2 2}=n$

因此屬於同階情況：

$$T(n)=\Theta(n\log n)$$

遞迴樹推導

在遞迴樹的每一層，所有子問題的元素總數仍為 $n$，所以該層 partition 的總成本為 $\Theta(n)$。

由於每次都近似平分資料，遞迴樹高度為：

$$\log_2 n$$

因此總成本為：

$$\Theta(n)\times\Theta(\log n) = \Theta(n\log n)$$

---

關鍵虛擬碼

QUICKSORT(A, low, high):
    if low >= high:
        return

    pivotValue = LINEAR_TIME_MEDIAN(A, low, high)
    p = PARTITION(A, low, high, pivotValue)

    QUICKSORT(A, low, p - 1)
    QUICKSORT(A, p + 1, high)

其中：

• PARTITION 必須在 $\Theta(n)$ 時間內完成
• LINEAR_TIME_MEDIAN 使用線性時間的中位數選擇演算法，例如 median-of-medians
• 每次選出的 pivot 都是目前子陣列的真正中位數

核心觀念

本題考的是最長共同子序列（Longest Common Subsequence, LCS）。

子序列可以刪除原序列中的部分元素，但不能改變剩餘元素的相對順序；它不要求元素連續。

令

$$X=\langle 1,0,0,1,0,1,0,1\rangle$$ $$Y=\langle 0,1,0,1,1,0,1,1,0\rangle$$

定義 $L[i][j]$ 為 $X$ 的前 $i$ 個元素與 $Y$ 的前 $j$ 個元素之 LCS 長度。

其遞迴公式為：

$$L[i][j]= \begin{cases} L[i-1][j-1]+1, & X_i=Y_j\\ \max\{L[i-1][j],L[i][j-1]\}, & X_i\ne Y_j \end{cases}$$

邊界條件為：

$$L[0][j]=0,\qquad L[i][0]=0$$

---

解題方法：動態規劃

將兩個序列逐項比較，建立以下 DP 表：

$i\backslash j$	0	1:0	2:1	3:0	4:1	5:1	6:0	7:1	8:1	9:0
0	0	0	0	0	0	0	0	0	0	0
1:1	0	0	1	1	1	1	1	1	1	1
2:0	0	1	1	2	2	2	2	2	2	2
3:0	0	1	1	2	2	2	3	3	3	3
4:1	0	1	2	2	3	3	3	4	4	4
5:0	0	1	2	3	3	3	4	4	4	5
6:1	0	1	2	3	4	4	4	5	5	5
7:0	0	1	2	3	4	4	5	5	5	6

核心觀念

本題考查演算法中利用**大師定理（Master Theorem）**求解遞迴關係式（Recurrence Relation）的時間複雜度。

大師定理適用於形式如下的遞迴式：

$$T(n) = aT\left(\frac{n}{b}\right) + f(n)$$

其中常數滿足 $a \ge 1$ 且 $b > 1$。其核心精神是比較「遞迴樹葉節點總成本」與「各層合併成本 $f(n)$」的大小關係，決定性指標為 $n^{\log_b a}$ 與 $f(n)$：

1. Case 1（葉節點成本主導）：
   若存在常數 $\epsilon > 0$，使得 $f(n) = O(n^{\log_b a - \epsilon})$，則： $$T(n) = \Theta(n^{\log_b a})$$
2. Case 2（各層成本均勻分布）：
   若存在常數 $k \ge 0$，使得 $f(n) = \Theta(n^{\log_b a} \lg^k n)$，則： $$T(n) = \Theta(n^{\log_b a} \lg^{k+1} n)$$ （當 $k = 0$ 時，$f(n) = \Theta(n^{\log_b a})$，則 $T(n) = \Theta(n^{\log_b a} \lg n)$）
3. Case 3（根節點合併成本主導）：
   若存在常數 $\epsilon > 0$，使得 $f(n) = \Omega(n^{\log_b a + \epsilon})$，且滿足平滑條件／正則條件（Regularity Condition，即存在常數 $c < 1$ 且對足夠大的 $n$ 恆滿足 $a f(n/b) \le c f(n)$），則： $$T(n) = \Theta(f(n))$$

---

解題方法

給定遞迴關係式：

$$T(n) = 27T\left(\frac{n}{3}\right) + n^3$$