114 年 國立中山大學電機工程學系碩士班丙組《資料結構》

核心觀念

AVL 樹是二元搜尋樹，且每個節點的左右子樹高度差最多為 $1$。平衡因子定義為：

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

刪除節點或插入節點後，若有節點的平衡因子超出 $-1$ 到 $1$，就須以旋轉恢復平衡。

題目未指定刪除有兩個子節點的節點時，要採用中序前驅或中序後繼。以下採常用的中序後繼規則：以右子樹中最小的鍵值取代被刪除的鍵值。

解題方法

① 刪除根節點 $49$：

$49$ 有兩個子節點，其中序後繼是右子樹中最小的鍵值 $57$。以 $57$ 取代 $49$，再從原位置刪除 $57$。此時節點 $66$ 的左子樹為空，右子樹為 $69$（其右子節點為 $72$），所以：

$$\text{BF}(66)=0-2=-2$$

這是右右型失衡，在 $66$ 處做一次左旋，得到以 $69$ 為根、左右子節點分別為 $66$ 與 $72$ 的子樹。旋轉後，節點 $74$ 與根節點 $57$ 都符合 AVL 平衡條件。

刪除後的 AVL 樹：

核心觀念

本題考查「遞迴」與「線性搜尋」：

• 陣列最大值的定義：
  $\max(A[0],A[1],\ldots,A[n-1])$
• 將問題縮小為：
  1. 找出 $A[1]$ 至 $A[n-1]$ 的最大值。
  2. 再將它與 $A[0]$ 比較。
• 必須設定基底條件，避免遞迴無限進行。
• 每個元素只被比較有限次，因此時間複雜度可達 $O(n)$。

題目給定 $n$ 個元素，假設 $n\geq 1$。

解題方法

令 find_max(A, n) 表示找出陣列中前 $n$ 個元素的最大值。

當 $n=1$ 時，陣列只有 $A[0]$，最大值就是 $A[0]$：

$$\text{find\_max}(A,1)=A[0]$$

當 $n>1$ 時，先遞迴找出 $A[1]$ 至 $A[n-1]$ 的最大值，再與 $A[0]$ 比較：

$$M=\text{find\_max}(A+1,n-1)$$

因此：

$$\text{find\_max}(A,n)= \begin{cases} A[0], & A[0]>M\\ M, & A[0]<M \end{cases}$$

因為題目說所有元素互不相同，所以不會發生相等情況；即使允許重複元素，使用 $\geq$ 或 $>$ 也都能正確找出最大值。

關鍵程式碼

以下以 C 語言風格表示：

int find_max(int A[], int n) {
    if (n == 1) {
        return A[0];
    }

    int max_of_rest = find_max(A + 1, n - 1);

    if (A[0] > max_of_rest) {
        return A[0];
    } else {
        return max_of_rest;
    }
}

呼叫方式：

int answer = find_max(A, n);

【答案】使用 heap sort（以最大堆方式）最合適。

分析

1. Selection sort

   • 只做 $k$ 次選擇，每次遍歷整個陣列。
   • 時間 $T_{\text{sel}} = O(nk)$。
   • $k\ll n$ 時仍為線性倍增，對大 $n$ 不具優勢。

2. Heap sort（建最大堆）

   • 建堆：$O(n)$。
   • 抽出最大值 $k$ 次，每次 $O(\log n)$。

推導過程

使用堆疊法，由左至右讀取 postfix，遇到運算元直接壓入堆疊，遇到運算子彈出兩個最近的元素，組成 prefix 子式再壓回。

讀入	堆疊內容（從底至頂）
D	D
B	D B
+	+ D B
F	+ D B F
A	+ D B F A
C	+ D B F A C

**先講答案：**應使用 adjacency lists（鄰接串列），其 BFS 的時間複雜度較小。

核心觀念

設圖 $G$ 有：

• $n$ 個 vertices
• $m$ 條 edges
• maximum degree 為 $d$

BFS 的主要工作包含：

1. 每個 vertex 至多被拜訪、加入佇列一次，成本為 $\Theta(n)$。
2. 對每個 vertex 掃描其所有鄰居，成本取決於圖的儲存方式。

對 undirected graph，由握手定理：

$$\sum_{v\in V}\deg(v)=2m$$

又因為每個 vertex 的 degree 不超過 $d$：

$$2m\le nd \quad\Longrightarrow\quad m\le \frac{nd}{2}$$

---

解題方法與複雜度分析

一、使用 adjacency matrix

Adjacency matrix 是 $n\times n$ 的矩陣。當 BFS 拜訪某個 vertex $v$ 時，必須掃描矩陣中對應的整列，逐一確認 $v$ 是否與其他 vertex 相鄰。

每個 vertex 都要掃描 $n$ 個位置，而共有 $n$ 個 vertices：

$$T_{\text{matrix}}=\Theta(n\cdot n)=\Theta(n^2)$$

即使某個 vertex 的實際 degree 很小，仍然必須掃完整列，因此 maximum degree 很小也無法降低此方法的主要成本。

---

二、使用 adjacency lists

Adjacency lists 直接儲存每個 vertex 的鄰居。BFS 拜訪 vertex $v$ 時，只需掃描 $v$ 的 adjacency list，不必檢查不存在的 edges。

所有 adjacency lists 的總長度為：

$$\sum_{v\in V}\deg(v)=2m$$

因此，所有鄰居總共只會被掃描 $2m$ 次，常數 $2$ 不影響漸近複雜度：

$$T_{\text{list}}=\Theta(n+m)$$

答案先講

在一般允許使用雜湊的前提下，應將資料儲存在**雜湊表（hash table）**中，使用分布均勻的雜湊函數，並控制負載因子，使平均搜尋時間達到 $\Theta(1)$。這是漸近意義下的最佳結果。若 key 值域很小且連續，則可使用直接定址表（direct-address table），搜尋時間甚至可達到 $O(1)$ 的最壞情況。

核心觀念

這題考的是字典（dictionary）的搜尋效率，以及下列資料結構的時間複雜度：

• 未排序陣列或鏈結串列：平均 $\Theta(n)$。
• 已排序陣列搭配二分搜尋：平均 $\Theta(\log n)$。
• 平衡二元搜尋樹：平均 $\Theta(\log n)$。
• 雜湊表：在雜湊函數良好、碰撞受控制時，平均 $\Theta(1)$。

雜湊表使用雜湊函數 $h(k)$ 將 key $k$ 轉換成表格索引：

$$h(k)\in\{0,1,\ldots,m-1\},$$

其中 $m$ 是雜湊表的槽位數。若不同 key 對應到相同槽位，就會發生碰撞（collision）。

令負載因子為

$$\alpha=\frac{n}{m}.$$

只要維持 $\alpha=O(1)$，每個槽位平均只需處理常數數量的資料。

解題方法與推導

採用分離鏈結（separate chaining）處理碰撞。每個槽位存放一條鏈結串列，將所有具有相同雜湊值的資料放在同一串列中。

在簡單均勻雜湊（simple uniform hashing）的假設下：

• 不成功搜尋時，預期需要檢查的資料筆數約為

$$E[T_{\text{unsuccessful}}]=\alpha.$$

• 成功搜尋時，若每筆資料被搜尋的機率相同，平均檢查筆數約為