112 年 國立臺灣大學電機工程研究所丙組《資料結構（B）》

核心觀念

$O$ 與 $\Omega$ 分別表示不同方向的漸近界：

• $T(n)=O(X(n))$：$T(n)$ 的成長速度至多與 $X(n)$ 同階。
• $T(n)=\Omega(X(n))$：$T(n)$ 的成長速度至少與 $X(n)$ 同階。

形式化地說，若存在常數 $c>0$ 與 $n_0$，使得對所有 $n\ge n_0$：

$$T(n)\ge cX(n),$$

則 $T(n)=\Omega(X(n))$。

但這只代表下界，並未限制 $T(n)$ 的上界，因此不能推出 $T(n)=O(X(n))$。

解題方法

直接以反例檢驗敘述是否成立。令題目所稱的指數函數為：

$$X(n)=2^n$$

再令程式實際執行時間為：

$$T(n)=4^n=(2^n)^2$$

因為對所有 $n$ 都有：

$$4^n\ge 2^n,$$

所以：

$$T(n)=\Omega(2^n)$$

然而，$T(n)$ 並不是 $O(2^n)$。若假設存在常數 $C>0$，使得：

$$4^n\le C2^n,$$

則可化為：

$$2^n\le C$$

但當 $n$ 持續增加時，$2^n$ 會無限增大，不可能永遠小於固定常數 $C$。因此：

$$4^n\notin O(2^n)$$

這表示程式可以至少是指數時間，實際上卻是更高階的指數時間。

選項分析

題目敘述為：

核心觀念

Min-heap 是一棵完全二元樹，且每個節點的鍵值不大於其子節點。因此：

• 最小元素一定位於根節點。
• 含有 $n$ 個元素時，樹高為 $O(\log n)$。
• 使用陣列儲存時，根節點位於固定位置，通常是索引 $0$。

陣列表示如下：

$$\text{parent}(i)=\left\lfloor\frac{i-1}{2}\right\rfloor,\qquad \text{left}(i)=2i+1,\qquad \text{right}(i)=2i+2$$

解題方法

逐一分析三個操作的主要步驟與最多需要移動的層數。

1. findMin()

Min-heap 的最小元素就是根節點，直接存放在陣列的第一個位置：

$$\text{findMin()}=A[0]$$

不需要搜尋其他節點，因此時間複雜度為：

$$O(1)$$

2. insert()

插入新元素時，先將元素放到陣列末端，以維持完全二元樹的形狀。接著執行上浮（percolate up）：

1. 將新元素放在最後一個葉節點。
2. 與父節點比較。
3. 若新元素小於父節點，便交換。
4. 重複上述步驟，直到滿足 min-heap 性質。

新元素最多從葉節點上浮到根節點。完全二元樹高度為 $O(\log n)$，所以交換與比較次數最多為 $O(\log n)$。

動態陣列在容量不足時需要擴充；採用倍增容量的策略時，尾端插入的攤銷成本為 $O(1)$。因此：

$$\text{insert()}=O(1)+O(\log n)=O(\log n)$$

3. deleteMin()

刪除最小元素時，刪除根節點會破壞陣列表示的完整性，因此通常採取以下步驟：

核心觀念

Deap（double-ended heap）是一種雙端優先佇列，通常以一棵完整二元樹表示：

• 左子樹符合 min-heap 性質，根節點保存最小值。
• 右子樹符合 max-heap 性質，根節點保存最大值。
• 因此可在兩端分別取得最小值與最大值。

其主要操作複雜度如下：

操作	複雜度
findMin()	$O(1)$
findMax()	$O(1)$
deleteMin()	$O(\log n)$
deleteMax()	$O(\log n)$

解題方法

判斷此敘述的關鍵，在於分辨「尋找」與「刪除」的成本。

取得最小值時，只需查看 min-heap 的根節點：

$$\text{findMin()} = O(1)$$

取得最大值時，只需查看 max-heap 的根節點：

$$\text{findMax()} = O(1)$$

刪除最小值後，必須將適當元素補至根部，再沿著 min-heap 向下調整；樹高為 $O(\log n)$，因此：

$$\text{deleteMin()} = O(\log n)$$

同理，刪除最大值需在 max-heap 中進行向下調整：

$$\text{deleteMax()} = O(\log n)$$

核心觀念

本題考查樹的 post-order traversal（後序走訪） 定義。

對於以某節點為根的樹，後序走訪順序為：

1. 依序走訪根節點的所有子樹；
2. 最後才走訪根節點本身。

若每拜訪一個節點，就依序標上遞增編號，則最後被拜訪的節點會取得最大編號。

解題方法

設樹共有 $n$ 個節點，編號依序為 $1,2,\ldots,n$。

後序走訪會先完成根節點的所有子樹，最後才拜訪根節點。因此根節點必定是第 $n$ 個被拜訪的節點，其編號為：

$$n$$

這是所有編號中的最大值，所以根節點會擁有最大的編號。

例如：

    A
   / \
  B   C

後序走訪順序為：

$$B,\ C,\ A$$

標號後為：

$$B=1,\quad C=2,\quad A=3$$

核心觀念

本題考查 B-tree 的高度與硬碟區塊存取成本。

B-tree 是高度平衡的多路搜尋樹。若 B-tree 的 order 為 $K$，可將每個節點視為一個硬碟 block，最多具有約 $K$ 個子樹。由於每次讀取一個節點就能取得一整個 block 的資料，因此每下降一層約需一次硬碟存取。

若樹高為 $h$，最多可容納的資料量約為：

$$N \approx K^h$$

因此：

$$h \approx \log_K N$$

每次硬碟存取時間為 $t$，查詢一筆資料約需存取 $h$ 個節點，所以查詢時間為：

$$T(N) \approx h \cdot t \approx \log_K N \cdot t$$

---

解題方法

B-tree 每一層都能將搜尋範圍縮小約 $K$ 倍。查詢流程如下：

1. 讀取根節點，判斷目標資料落在哪個子樹。
2. 讀取對應的下一層節點。
3. 重複此過程，直到找到目標資料。

若經過 $h$ 層後找到資料，則：

$$K^h \approx N$$

兩邊取對數：

$$h \approx \log_K N$$

每層需要一次硬碟存取，故：

$$T(N) \approx \log_K N \cdot t$$

以題目給定的 $N=10,000,000$、$K=1024$ 為例：

$$\log_{1024}(10,000,000) = \frac{\log_2(10,000,000)}{\log_2(1024)} = \frac{\log_2(10,000,000)}{10} \approx 2.33$$

因此理想化的平均估計時間約為：

$$T \approx 2.33t$$

核心觀念

本題考查紅黑樹（Red-Black Tree, RB Tree）的插入規則與插入後修復。

紅黑樹必須滿足以下性質：

1. 每個節點非紅即黑。
2. 根節點必須是黑色。
3. 所有外部葉節點 NIL 都是黑色。
4. 紅色節點的子節點必須是黑色，因此不能出現連續兩個紅色節點。
5. 從任一節點到其所有後代 NIL 葉節點的每條路徑，都包含相同數量的黑色節點，稱為 black-height。

插入新資料時，先依照一般二元搜尋樹插入，維持二元搜尋樹的順序：

$$\text{左子樹鍵值} < \text{目前節點鍵值} < \text{右子樹鍵值}$$

新插入的資料節點通常先塗成紅色，再進行修復。

---

解題方法

插入新節點 $z$ 後，將 $z$ 染成紅色的主要原因是：

• 若染成黑色，會使包含 $z$ 的路徑黑色節點數增加，可能破壞 black-height。
• 染成紅色不會立刻改變任何路徑的黑色節點數。
• 因此通常只可能造成「紅色節點的父節點也是紅色」的違規，再透過重新著色與旋轉修復。

設新節點為 $z$，其父節點為 $p$，祖父節點為 $g$，叔叔節點為 $u$。

情況一：父節點為黑色

若 $p$ 為黑色，則不會產生連續紅色節點，紅黑樹性質維持不變。

例如：

$$p=\text{Black},\qquad z=\text{Red}$$

此時不需要旋轉或重新著色。

情況二：父節點與叔叔節點皆為紅色

若 $p$ 與 $u$ 都是紅色，則將：

• $p$ 染成黑色；
• $u$ 染成黑色；
• $g$ 染成紅色。

即：

$$p,u:\text{Red}\rightarrow\text{Black}$$ $$g:\text{Black}\rightarrow\text{Red}$$

如此可維持經過 $g$ 的路徑黑色數量，但可能使 $g$ 與其父節點形成連續紅色，因此必須將 $g$ 視為新的問題節點，繼續向上修復。

情況三：叔叔節點為黑色，且形成直線型

若叔叔節點為黑色，且 $z$、$p$、$g$ 位於同一直線上，則對 $g$ 進行一次旋轉。

例如左左型：

核心觀念

題目描述的是從某個起點出發，每條邊恰好經過一次，最後回到起點。這種路徑稱為 Euler circuit（歐拉迴路）。

對於有向圖，存在 Euler 迴路的必要條件是：

1. 圖中所有具有邊的頂點屬於同一個強連通區域。
2. 對每個頂點 $v$，其入度必須等於出度：

$$\operatorname{indegree}(v)=\operatorname{outdegree}(v)$$

因此，「強連通」只保證頂點之間彼此可達，並不保證每個頂點的入度與出度相等。

---

解題方法

判斷題目敘述是否成立，必須比較：

• 強連通條件；
• Euler 迴路所需的入度／出度條件。

若只知道圖是強連通圖，仍可能有某個頂點的出度大於入度。此時每次進入與離開頂點無法完全配對，必然無法在使用所有邊後回到起點。

考慮有向圖：

• $A\to B$
• $B\to C$
• $C\to A$
• $A\to C$
• $C\to B$

此圖為強連通圖，例如：

• $A$ 可到達 $B,C$；
• $B$ 可經由 $C$ 到達 $A$；
• $C$ 可經由 $A$ 到達 $B$。

但各頂點的入度與出度如下：

頂點	入度	出度
$A$	$1$	$2$
$B$	$2$	$1$
$C$	$2$	$2$

$A$ 與 $B$ 不符合入度等於出度的條件，因此不存在 Euler 迴路。

---

題目敘述中的名詞問題

核心觀念

本題考查兩個圖論定義：

• 穩定集（stable set／independent set）：圖中的頂點集合，其中任意兩個頂點都不相鄰。
• 穩定數 $\alpha(G)$：圖 $G$ 中最大穩定集的頂點數量。
• 色數 $\chi(G)$：將圖 $G$ 正確著色所需的最少顏色數，使每條邊兩端的頂點顏色不同。

在圖著色中，同一種顏色所形成的頂點集合必定是穩定集。因此，一個使用 $\chi(G)$ 種顏色的著色方式，就是將所有頂點分割成 $\chi(G)$ 個穩定集。

解題方法

題幹的前半段敘述正確：圖著色確實可以視為將頂點集合分割成若干個穩定集。

但由「可分割成穩定集」不能推出

$$\chi(G)\leq \alpha(G).$$

原因是：

• $\chi(G)$ 表示穩定集的個數；
• $\alpha(G)$ 表示單一最大穩定集的頂點數量。

兩者衡量的對象不同，不能直接比較為上述不等式。

可用完全圖 $K_n$ 作為反例。完全圖中任意兩個不同頂點都相鄰，因此每個穩定集最多只能包含一個頂點，故

$$\alpha(K_n)=1.$$

另一方面，完全圖的每個頂點都必須使用不同顏色，因此

$$\chi(K_n)=n.$$

當 $n\geq 2$ 時，

$$\chi(K_n)=n>1=\alpha(K_n),$$

明確違反題幹所宣稱的

$$\chi(G)\leq\alpha(G).$$

正確的相關關係

核心觀念

本題考查兩種圖形的性質：

1. 平面圖（planar graph）：能在平面上繪製，使任意兩條邊只在共同端點相交，不產生邊的交叉。
2. 二分圖（bipartite graph）：頂點可以分成兩個互不相交的集合，使每條邊的兩端分屬不同集合。等價判定方式是：圖中不存在奇數長度的環。

立方體的骨架圖共有 $8$ 個頂點、$12$ 條邊、$6$ 個面。

解題方法

一、判斷是否為平面圖

將立方體的圖形畫成兩個正方形：

• 外層正方形代表立方體的一個面；
• 內層正方形代表相對的另一個面；
• 以 $4$ 條不相交的邊，將外層正方形的四個頂點分別連到內層正方形的四個頂點。

此畫法可以完整表示立方體的 $8$ 個頂點與 $12$ 條邊，且所有邊都能安排在平面上而不互相穿越，因此立方體圖是平面圖。

也可用 Euler 公式驗算。對連通平面圖而言：

$$V-E+F=2$$

立方體圖中：

$$V=8,\qquad E=12,\qquad F=6$$

因此：

$$8-12+6=2$$

符合平面嵌入的基本條件；配合上述無交叉畫法，可確認其為平面圖。

二、判斷是否為二分圖

將立方體的每個頂點以三個二進位座標表示：

核心觀念

本題考查雜湊函數的定義，以及雜湊表各項操作的時間複雜度。

1. Perfect hash function

   Perfect hash function 通常指對固定的 $n$ 個鍵值，不會發生碰撞的雜湊函數：

   $h(k_i)\ne h(k_j),\qquad k_i\ne k_j$

   「每個桶被選中的機率相同」較接近 uniform hashing（均勻雜湊）的假設，不是 perfect hashing 的完整定義。

2. find() 與 insertData()

   在雜湊分布均勻、碰撞很少時：

   • find() 直接計算 $h(k)$，平均可在 $O(1)$ 找到對應桶。
   • insertData() 直接計算 $h(k)$，平均可在 $O(1)$ 插入對應桶。

   這兩項複雜度通常是平均時間複雜度，並非無條件的最壞情況複雜度。

3. deleteMin()

   deleteMin() 要找出所有資料中的最小鍵值。普通雜湊表只依照雜湊值分桶，雜湊值與鍵值大小沒有排序關係，因此無法直接由雜湊表定位最小值。

---

解題方法

逐一檢查題目所宣稱的三項複雜度：

• find()：計算雜湊值並存取桶，平均為 $O(1)$。

• insertData()：計算雜湊值並插入桶，平均為 $O(1)$。

• deleteMin()：必須檢查 $B$ 個桶，才能確定全域最小值，時間為

  $O(B)$

  即使碰撞很少，仍然需要判斷哪些桶為空、哪些桶含有資料，並比較各桶中的最小鍵值。均勻分布只能降低碰撞，無法提供鍵值大小的排序資訊。

核心觀念

本題考樹的基本性質，以及大 $O$、大 $\Omega$ 的漸近界。

• 樹是連通且無環的圖；有 $n$ 個節點的樹恰有 $n-1$ 條邊。
• 葉節點是沒有子節點的節點；內部節點是至少有一個子節點的節點。
• 根到每個葉節點各有唯一一條路徑。
• 題目將子樹定義為：取原樹中的一部分節點，以及連接這些節點的邊所形成的樹。因此，只要取出的節點與原樹中相應的邊構成連通子樹，就計為一個子樹。

解題方法

逐一檢查選項是否對所有符合定義的樹都成立。對於數量與節點數的漸近關係，可用星狀樹或鏈狀樹等簡單結構測試；一個反例就足以否定通稱性質。

選項分析

(A) 正確。
任一有 $n$ 個節點的樹，其邊數為

$$n-1$$

因此，(Number of edges) = (Number of nodes) $-1$。

(B) 錯誤。
葉節點數等於內部節點數加 $1$，並非一般樹的性質。考慮根節點有三個子節點的樹：葉節點有 $3$ 個、內部節點有 $1$ 個，並不滿足

$$\text{葉節點數}=\text{內部節點數}+1$$

這個等式只在特定條件下成立，例如每個內部節點恰有兩個子節點的二元樹。

已確認原卷頁圖內容，第 13 題的五個選項與題目文字一致，以下為完整詳解。

---

核心觀念

本題考的是圖論（Graph Theory）基本定義與性質，涵蓋以下概念：

• 同構（Isomorphic）：兩圖 $G_1, G_2$ 同構，代表存在頂點之間的一對一映射，使得邊的連接關係完全對應。
• 團（Clique）：圖中一個頂點子集，其中任意兩頂點之間皆有邊相連。特別注意：單一頂點本身即構成一個大小為 1 的團（trivial clique）。
• 深度優先搜尋（DFS）的時間複雜度：標準 DFS 為 $O(V + E)$。
• 最長簡單路徑（Longest Simple Path）：在一般圖上求最長簡單路徑是 NP-hard 問題，且路徑長度隨圖的結構而異，無法用 $\Theta(n^2)$ 一概而論。
• 完全圖（Complete Graph）的邊數：$K_n$ 的邊數為 $\binom{n}{2} = \frac{n(n-1)}{2} = \Theta(n^2)$。

---

解題方法

逐一檢驗每個選項的敘述是否為正確的數學命題。

---

選項分析

(A) Two graphs are isomorphic if and only if both graphs contain the same number of vertices and the same number of edges.　→ ❌ 錯誤

頂點數與邊數相同只是必要條件（necessary condition），絕非充分條件。

反例：考慮 $n = 4, |E| = 3$ 的兩個圖：

• $G_1$：路徑圖 $P_4$（四個頂點排成一條鏈：$1-2-3-4$）
• $G_2$：星形圖 $K_{1,3}$（一個中心頂點連接其餘三個頂點）

兩者皆有 4 個頂點、3 條邊，但 $G_1$ 的最大度數為 2，而 $G_2$ 的最大度數為 3，因此不同構。

選項使用 "if and only if" 宣稱這是充要條件，故錯誤。

---

(B) All non-empty graphs must contain at least a clique.　→ ✅ 正確

根據 clique 的定義，任何單一頂點 $\{v\}$ 都構成一個大小為 1 的團（因為「任兩頂點間皆有邊」這一條件在只有一個頂點時是空真（vacuously true）的）。

既然圖是 non-empty（至少有一個頂點），就必然包含至少一個大小為 1 的 clique。即使圖完全沒有邊（獨立集），每個孤立頂點本身仍是一個 clique。

因此本敘述正確。

---

核心觀念

本題考的是**雜湊函數（Hash Function）與碰撞（Collision）**的概念。碰撞是指兩筆以上不同的資料經過雜湊函數後，映射到同一個桶（bucket），即 $h(s_1) = h(s_2)$ 但 $s_1 \neq s_2$。

題目定義的雜湊函數為：

$$h(s) = \left(\sum_i s[i]\right) \bmod B$$

其中 $s[i]$ 為字串第 $i$ 個字元的 ASCII 碼，$B = 5$ 為桶數。題目問的是哪些桶號發生碰撞。

---

解題方法

從原卷圖中確認：待插入的 10 筆字串為 "USA", "MIT", "Cat", "Dog", "May", "Sam", "Bob", "Low", "Phd", "See"，桶數 $B = 5$。逐一計算每筆字串的 ASCII 碼總和及其模 5 的結果。

字串	各字元 ASCII 碼	總和	$\bmod 5$	桶號
USA	U=85, S=83, A=65	233	$233 = 46 \times 5 + 3$	3
MIT	M=77, I=73, T=84	234	$234 = 46 \times 5 + 4$	4
Cat	C=67, a=97, t=116	280	$280 = 56 \times 5 + 0$	0
Dog	D=68, o=111, g=103	282	$282 = 56 \times 5 + 2$	2
May	M=77, a=97, y=121	295	$295 = 59 \times 5 + 0$	0
Sam	S=83, a=97, m=109	289	$289 = 57 \times 5 + 4$	4
Bob	B=66, o=111, b=98	275	$275 = 55 \times 5 + 0$	0