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

核心觀念

本題考查漸近緊確界 $\Theta$ 的定義、不同成長率的比較，以及插入排序的執行時間如何受輸入排列影響。

解題方法

1. $\Theta(f(n))$ 的數學定義

若存在正常數 $c_1,c_2$ 與正整數 $n_0$，使得所有 $n\ge n_0$ 都滿足

$$0 \le c_1 f(n) \le T(n) \le c_2 f(n),$$

則稱 $T(n)=\Theta(f(n))$。

也就是說，當 $n$ 充分大時，$T(n)$ 同時有 $f(n)$ 的漸近下界與上界，兩者只差正常數倍。

2. 比較演算法 B 與 C

依照考卷原圖，演算法 B 的時間複雜度為 $\Theta(\log^2 n)$，演算法 C 為 $\Theta((\log\log n)!)$。

令 $m=\log\log n$。此時 $\log^2 n$ 可寫成 $e^{\Theta(m)}$。由 Stirling 公式，

$$\log(m!)=m\log m-m+O(\log m).$$

當 $m$ 趨近無窮大時，$m\log m-m$ 的成長速度高於任何固定常數倍的 $m$，因此 $(\log\log n)!$ 最終會比 $\log^2 n$ 成長得快。

題目以執行時間較低作為較好的判斷標準，所以應選漸近成長較慢的演算法 B。

3. 判斷插入排序是否為 $\Theta(n^2)$

核心觀念

前序走訪順序為「根 → 左子樹 → 右子樹」，中序走訪順序為「左子樹 → 根 → 右子樹」，後序走訪順序為「左子樹 → 右子樹 → 根」。

重建二元樹時，先用前序序列的第一個節點找出根，再從中序序列定位根。根左側是左子樹，根右側是右子樹；依此分割前序序列後，對左右子樹遞迴處理。

解題方法

1. 前序序列第一個節點是根，因此根為 $A$。在中序序列 $G\to D\to B\to E\to A\to C\to F$ 中，$A$ 左側的 $G,D,B,E$ 屬於左子樹，右側的 $C,F$ 屬於右子樹。
2. 左子樹的前序序列為 $B\to D\to G\to E$。其根為 $B$；在左子樹的中序序列 $G\to D\to B\to E$ 中，$B$ 左側是 $G,D$，右側是 $E$。因此 $B$ 的左子樹由 $D,G$ 組成，右子節點為 $E$。
3. $B$ 的左子樹前序序列為 $D\to G$，故根為 $D$；

核心觀念

Heap sort（堆積排序）將序列視為完全二元樹，並利用堆積的性質排序。

以第 $1$ 格為根節點時：

$$\text{左子節點}=2i,\qquad \text{右子節點}=2i+1,\qquad \text{父節點}=\left\lfloor\frac{i}{2}\right\rfloor$$

最大堆積（max heap）的定義為：每個父節點皆不小於其子節點。因此，根節點必定是目前堆積中的最大值。

題目要求由小到大排序，採用最大堆積。每一輪將根節點的最大值與未排序區最後一個元素交換，該最大值即固定在序列尾端，再對剩餘部分向下調整。

---

解題方法

原始序列為：

$$[16,\;30,\;8,\;79,\;24,\;51]$$

其完全二元樹如下：

              16
            /    \
          30      8
         /  \    /
       79   24  51

一、建立最大堆積

最後一個非葉節點為：

$$\left\lfloor\frac{6}{2}\right\rfloor=3$$

因此從第 $3$ 格、第 $2$ 格、第 $1$ 格依序向上調整。

步驟 1：調整第 3 格

第 3 格為 $8$，其子節點為第 6 格的 $51$，交換：

$$[16,\;30,\;8,\;79,\;24,\;51] \longrightarrow [16,\;30,\;51,\;79,\;24,\;8]$$

步驟 2：調整第 2 格

第 2 格為 $30$，子節點為 $79,24$，與較大的子節點 $79$ 交換：

$$[16,\;30,\;51,\;79,\;24,\;8] \longrightarrow [16,\;79,\;51,\;30,\;24,\;8]$$

步驟 3：調整第 1 格

第 1 格為 $16$，子節點為 $79,51$，先與較大的 $79$ 交換：

$$[16,\;79,\;51,\;30,\;24,\;8] \longrightarrow [79,\;16,\;51,\;30,\;24,\;8]$$

此時 $16$ 下移至第 2 格，其子節點為 $30,24$，再與較大的 $30$ 交換：

$$[79,\;16,\;51,\;30,\;24,\;8] \longrightarrow [79,\;30,\;51,\;16,\;24,\;8]$$

最大堆積建立完成：

              79
            /    \
          30      51
         /  \    /
       16   24  8

---

二、反覆取出最大值

記號

$$[\text{尚未排序的堆積}\mid\text{已排序部分}]$$

豎線左側才參與後續堆積調整。

第 1 輪：堆積大小由 6 變為 5

將根節點 $79$ 與第 6 格的 $8$ 交換：

核心觀念

本題考查 AVL tree 的兩項操作：

1. 插入節點後，利用平衡因子判斷是否失衡，並進行旋轉。
2. 刪除節點後，重新計算各祖先節點的平衡因子，必要時進行旋轉。

平衡因子定義為：

$$BF(v)=高度(左子樹)-高度(右子樹)$$

AVL tree 必須滿足：

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

題目資訊不足

目前附上的圖片是「控制系統」考題第 2 頁，圖中沒有本題所需的「圖 2 AVL tree」。因此無法得知原始 AVL tree 的節點配置，也就無法唯一確定插入 $73$ 及刪除 $28$ 後的兩棵樹。

解題方法

① 插入 $73$

依照二元搜尋樹規則，從根節點開始比較：

• $73$ 大於目前節點，往右子樹走。
• $73$ 小於目前節點，往左子樹走。
• 找到空位置後插入葉節點 $73$。

接著由插入位置向根節點回溯，更新高度並計算每個祖先的平衡因子。

核心觀念

雙向環狀串列的每個節點都有 prev 與 next 指標。若串列非空，首尾相接：head->prev 指向 tail，tail->next 指向 head。刪除頭節點時，要更新新頭節點、尾節點的環狀連結，並釋放舊頭節點的記憶體。

解題方法

圖 3 中節點依序為 31 → 25 → 79 → 64，head 指向 31，tail 指向 64；環狀連結為 64.next = 31、31.prev = 64。刪除 head 時，分別處理空串列、只有一個節點，以及至少兩個節點的情況。