109 年 國立成功大學電腦與通信工程研究所丁組《資料結構》

核心觀念

本題綜合考查：

• AVL tree、B-tree、heap 的基本定義。
• Binary search 對資料儲存結構的要求。
• Postfix expression 的求值方式。
• Big-O 漸近成長率比較。

題目指出有三個錯誤，因此須逐一判斷六個選項。

選項分析

(A) An AVL tree is a binary search tree.

正確。

AVL tree 是一種自我平衡的 binary search tree。除了符合二元搜尋樹的順序性質外，每個節點還必須滿足平衡條件：

$$\left|h_{\text{left}}-h_{\text{right}}\right|\leq 1$$

因此 AVL tree 必定是 binary search tree。

---

(B) A B-tree of order 5 is a 2-3-4-5 tree.

正確。

依本題採用的命名方式，order 5 的 B-tree 每個內部節點可擁有 $2$ 至 $5$ 個子樹，因此稱為 2-3-4-5 tree。

若一個節點有 $k$ 個子節點，通常具有 $k-1$ 個排序後的鍵值。例如：

• 2-node：2 個子節點、1 個鍵值
• 3-node：3 個子節點、2 個鍵值
• 4-node：4 個子節點、3 個鍵值
• 5-node：5 個子節點、4 個鍵值

所以 B 選項符合本題的定義。

---

(C) To use binary search, sorted data must not be stored in a link list.

錯誤。

Binary search 的必要條件是資料已排序，並不代表資料絕對不能存放在 linked list 中。

不過，binary search 每次都要直接存取中間元素。陣列可透過索引在 $O(1)$ 時間取得中間元素；linked list 沒有隨機存取能力，必須從頭走訪才能找到中間節點。

因此在 linked list 上執行 binary search 時，每次尋找中間節點可能需要線性走訪，總時間複雜度為：

$$T(n)=T\left(\frac n2\right)+O(n)=O(n)$$

所以較精確的說法是：

Binary search 可以作用於已排序的 linked list，但因為缺乏隨機存取能力，無法達到陣列中 $O(\log n)$ 的效率。

---

(D) A max heap is a complete binary tree.

正確。

Max heap 必須同時滿足：

1. Shape property：是一棵 complete binary tree。
2. Heap-order property：每個父節點的值不小於其子節點：

核心觀念

題目要求將完整二元樹調整成最小堆積（min heap）。

最小堆積必須符合：

$$A[\text{parent}] \leq A[\text{child}]$$

以陣列表示完整二元樹時，採用 1-based index：

• 左子節點：$2i$
• 右子節點：$2i+1$
• 父節點：$\left\lfloor i/2 \right\rfloor$
• 最後一個非葉節點：$\left\lfloor n/2 \right\rfloor$

本題 $n=10$，因此最後一個非葉節點為：

$$\left\lfloor \frac{10}{2} \right\rfloor=5$$

採用自底向上的 Build-Min-Heap，依序處理節點 $5,4,3,2,1$。

---

解題方法與逐步調整

原始陣列為：

$$[10,\ 66,\ 30,\ 52,\ 61,\ 21,\ 3,\ 27,\ 55,\ 11]$$

第 1 步：調整節點 5

節點 5 的值為 $61$，其子節點為節點 10：

$$61 > 11$$

交換 $61$ 與 $11$：

$$[10,\ 66,\ 30,\ 52,\ 11,\ 21,\ 3,\ 27,\ 55,\ 61]$$

---

第 2 步：調整節點 4

節點 4 的值為 $52$，子節點為 $27$ 與 $55$。

最小子節點為 $27$，但：

$$52 > 27$$

交換後：

$$[10,\ 66,\ 30,\ 27,\ 11,\ 21,\ 3,\ 52,\ 55,\ 61]$$

---

第 3 步：調整節點 3

節點 3 的值為 $30$，子節點為 $21$ 與 $3$。

最小子節點為 $3$，因此交換：

$$[10,\ 66,\ 3,\ 52,\ 11,\ 21,\ 30,\ 27,\ 55,\ 61]$$

節點 7 為葉節點，調整完成。

---

第 4 步：調整節點 2

節點 2 的值為 $66$，子節點為 $52$ 與 $11$。

最小子節點為 $11$，交換：

$$[10,\ 11,\ 3,\ 52,\ 66,\ 21,\ 30,\ 27,\ 55,\ 61]$$

交換後，$66$ 移至節點 5。節點 5 的子節點為 $61$，因此繼續向下調整：

$$66 > 61$$

交換 $66$ 與 $61$：

$$[10,\ 11,\ 3,\ 52,\ 61,\ 21,\ 30,\ 27,\ 55,\ 66]$$

---

第 5 步：調整節點 1

節點 1 的值為 $10$，子節點為 $11$ 與 $3$。

最小子節點為 $3$，交換：

$$[3,\ 11,\ 10,\ 52,\ 61,\ 21,\ 30,\ 27,\ 55,\ 66]$$

此時節點 3 的值為 $10$，其子節點為 $21$ 與 $30$：

核心觀念

二元樹的兩種走訪定義如下：

• Preorder（前序）：根節點 → 左子樹 → 右子樹
• Inorder（中序）：左子樹 → 根節點 → 右子樹

當節點值皆不重複時：

1. 前序序列的第一個節點必定是整棵樹的根。
2. 根在中序序列中的位置，會將其餘節點分成左子樹與右子樹。
3. 再依照相同規則遞迴處理左右子樹。

因此，不重複節點的 preorder 與 inorder 序列可以唯一決定一棵二元樹。

---

解題方法

已知：

• Preorder：A B C D E F G H I
• Inorder：B C A E D G H F I

第一步：決定根節點

前序的第一個節點為 A，所以根節點是 A。

在中序序列中：

B C | A | E D G H F I

因此：

• 左子樹包含 B、C
• 右子樹包含 E、D、G、H、F、I

前序中扣除根 A 後，前兩個節點屬於左子樹：

左子樹 preorder：B C
右子樹 preorder：D E F G H I

---

第二步：建立左子樹

左子樹的序列為：

• Preorder：B C
• Inorder：B C

前序第一個節點 B 是左子樹根。

中序中：

B | C

B 沒有左子樹，C 位於右側，因此 C 是 B 的右子節點。

左子樹為：

B
 \
  C

---

第三步：建立右子樹

右子樹的序列為：

• Preorder：D E F G H I
• Inorder：E D G H F I

前序第一個節點 D 是右子樹根。

在中序中：

E | D | G H F I

因此：

• D 的左子樹包含 E
• D 的右子樹包含 G、H、F、I

對應的前序分割為：

• 左子樹 preorder：E
• 右子樹 preorder：F G H I

所以 D 的左子節點為 E。

---

第四步：建立節點 $D$ 的右子樹

此子樹的序列為：

• Preorder：F G H I
• Inorder：G H F I

前序第一個節點 F 是根。

在中序中：

G H | F | I

因此：

• F 的左子樹包含 G、H
• F 的右子樹包含 I

右子樹的前序為：

G H

其中 G 是根；中序為：

G H

核心觀念

本題考查 Quick Sort 與 Merge Sort、Heap Sort 的：

• 最佳、平均、最壞時間複雜度
• 排序穩定性（stability）
• 內部排序與外部排序的適用性
• Pivot 選擇對 Quick Sort 效能的影響

Quick Sort 每一輪以 Pivot 將資料分割成左右兩部分。若左右子問題大小分別為 $k$ 與 $n-k-1$，其遞迴式為

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

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

不同分割情況如下：

• 分割均勻：

$$T(n)=2T(n/2)+\Theta(n)=\Theta(n\log n)$$

• 每次都極度不均勻：

$$T(n)=T(n-1)+\Theta(n)=\Theta(n^2)$$

因此 Quick Sort 的複雜度取決於 Pivot 是否能將資料分割得均勻。

---

解題方法

逐一判斷每個敘述是否符合排序演算法的基本性質，並特別注意：

1. 「平均情況」與「最壞情況」不可混淆。
2. 穩定性與時間複雜度是不同概念。
3. 已排序資料是否為最佳情況，取決於 Pivot 的選擇方式。

---

選項分析

(a) The average-case time complexity of this algorithm is the same as that of the merge sort algorithm.

正確。

Quick Sort 在 Pivot 能平均產生相對均衡分割時，平均時間複雜度為

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

Merge Sort 無論輸入資料排列如何，時間複雜度皆為

$$\Theta(n\log n)$$

因此兩者的平均時間複雜度相同，都是

$$\boxed{\Theta(n\log n)}$$

但「時間複雜度相同」不代表兩者的實際效能與額外空間需求完全相同。Quick Sort 通常具有較佳的快取區域性，且可採用原地排序；Merge Sort 通常需要 $\Theta(n)$ 的額外陣列空間。

---

(b) It is stable.

錯誤。

穩定排序要求：若兩筆資料的鍵值相同，排序後仍維持原本的先後順序。

Quick Sort 的 partition 通常會交換距離很遠的元素。例如：

$$(2_A,\ 1,\ 2_B)$$

若以第一個元素 $2_A$ 作為 Pivot，partition 過程中的交換可能使 $2_B$ 移到 $2_A$ 前面，形成：

$$(2_B,\ 2_A,\ 1)$$

相同鍵值 $2_A$ 與 $2_B$ 的相對順序改變，因此一般的 Quick Sort 不是穩定排序法。

必須注意，透過特殊設計可以建立穩定版本的 Quick Sort，但標準 Quick Sort 的一般結論是：

$$\boxed{\text{不穩定}}$$

---

(c) The worst-case time complexity of this algorithm is the same as that of the heap sort algorithm.

錯誤。

Quick Sort 的最壞情況發生在每次 Pivot 都選到最小值或最大值，使分割結果為 $0$ 與 $n-1$：

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

展開可得：

$$T(n)=\Theta(n+(n-1)+\cdots+1)=\Theta(n^2)$$

因此 Quick Sort 的最壞時間複雜度為

$$\boxed{\Theta(n^2)}$$

核心觀念

本題考查有向加權圖的單源最短路徑。從起點 $A$ 出發，找出到其他各頂點的最小路徑長度。邊的方向必須符合箭頭方向，路徑長度則為沿途邊權重的總和。

可使用 Dijkstra 演算法：每次從尚未確定最短距離的頂點中，選出目前暫定距離最小者，並用它更新相鄰頂點的距離。此圖的邊權重皆為非負數，適用 Dijkstra 演算法。

解題方法

依圖中的箭頭，從 $A$ 可直接到達 $B$，權重為 $2$；也可直接到達 $C$，權重為 $15$。其餘相關有向邊為：

• $B\to E$：$10$；$B\to F$：$30$
• $C\to B$：$3$；$C\to E$：$1$；$C\to F$：$10$
• $E\to D$：$15$
• $F\to E$：$10$；$F\to D$：$4$

從 $A$ 開始，初始暫定距離為 $d(B)=2$、$d(C)=15$，其他頂點尚不可達。

1. 確定 $B$，距離為 $2$。
   經 $B$ 更新：
   $d(E)=2+10=12,\qquad d(F)=2+30=32$

2. 確定 $E$，距離為 $12$。
   經 $E$ 更新：
   $d(D)=12+15=27$

3. 確定 $C$，距離為 $15$。
   經 $C$ 到 $B$ 的距離為 $15+3=18$，大於已知的 $2$，不更新。

核心觀念

AVL 樹是一種具備高度平衡條件的二元搜尋樹。對任一節點 $v$，定義平衡因子：

$$BF(v)=h(\text{left}(v))-h(\text{right}(v))$$

其中 $h$ 表示子樹高度。AVL 樹必須滿足：

$$BF(v)\in\{-1,0,1\}$$

插入新鍵值時，先依二元搜尋樹規則插入，再由插入位置向上檢查。若某節點的平衡因子變成 $2$ 或 $-2$，就必須透過旋轉恢復平衡。

四種失衡型態如下：

• LL：以失衡節點為中心右旋。
• RR：以失衡節點為中心左旋。
• LR：先對子節點左旋，再對失衡節點右旋。
• RL：先對子節點右旋，再對失衡節點左旋。

---

解題方法

依序插入：

$$4,\ 7,\ 12,\ 15,\ 3,\ 5,\ 14,\ 18$$

每次按照二元搜尋樹規則插入，再檢查祖先節點的平衡因子。

---

逐步插入與旋轉

1. 插入 $4$

空樹插入 $4$：

4

此時樹高平衡，不需旋轉。

---

2. 插入 $7$

$7>4$，插入 $4$ 的右子樹：

4
 \
  7

節點 $4$ 的平衡因子為：

$$BF(4)=0-1=-1$$

仍然平衡，不需旋轉。

---

3. 插入 $12$

依二元搜尋樹規則：

• $12>4$，往右。
• $12>7$，插入 $7$ 的右子樹。

插入後：

4
 \
  7
   \
    12

節點 $4$ 的平衡因子為：

$$BF(4)=0-2=-2$$

這是 RR 型失衡，因此對節點 $4$ 做一次左旋：

    4                 7
     \               / \
      7      →      4   12
       \
        12

旋轉後：

  7
 / \
4  12

---

4. 插入 $15$

$15>7$，往右；$15>12$，插入 $12$ 的右子樹：

  7
 / \
4  12
      \
       15

各節點仍符合 AVL 平衡條件：

$$BF(12)=0-1=-1$$ $$BF(7)=1-2=-1$$

不需旋轉。

---

5. 插入 $3$

$3<7$，往左；$3<4$，插入 $4$ 的左子樹：

    7
   / \
  4   12
 /      \
3        15

節點 $4$ 與 $7$ 仍然平衡，不需旋轉。

---

6. 插入 $5$

$5<7$，往左；$5>4$，插入 $4$ 的右子樹：

    7
   / \
  4   12
 / \    \
3   5    15

此時：

$$BF(4)=1-1=0$$ $$BF(7)=2-2=0$$

不需旋轉。

---

7. 插入 $14$

依搜尋路徑：

• $14>7$，往右。
• $14>12$，往右。
• $14<15$，插入 $15$ 的左子樹。

插入後：