111 年 國立成功大學工程科學系碩士班乙組《資料結構》

解題要點

1. 以 $2$ 為底 的對數寫成 $\lg$。
2. 斯特林公式 $\displaystyle n!\sim\sqrt{2\pi n}\left(\frac{n}{e}\right)^n$ ⇒

$$\lg(n!) = n\lg n -\Theta(n),\qquad (\lg n)! \asymp (\lg n)^{\lg n}e^{-\lg n}=n^{\lg\lg n- \log_2 e}\,.$$

3. 代數恆等式：$4^{\lg n}=2^{2\lg n}=n^{2}$.
4. 觀察指數與多項式的相對成長：

$(\lg n)^{\lg n}=n^{\lg\lg n}=2^{(\lg n)(\lg\lg n)}\ll(3/2)^n=2^{c n},$

因為 $(\lg n)(\lg\lg n)=o(n)$.
5. 階乘 $n!$ 優於任何固定底數的指數 $c^{\,n}$，而 $(\lg n)!$ 的指數為 $\lg\lg n-O(1)$，仍屬於多項式級別的上界。

等價類與遞減序列

核心觀念

本題旨在考驗對**程式碼時間複雜度（Time Complexity）與大 $O$ 漸進符號（Big-Oh Notation）**的分析能力，核心在於將多重迴圈（Nested Loops）的執行次數轉換為數學級數（Summation），並找出其最高階項（Dominant Term）。

所使用到的核心數學公式與工具如下：

1. 等差級數求和公式：
   $\sum_{j=0}^{m-1} j = \frac{(m-1)m}{2} = \frac{m^2 - m}{2}$
2. 高次次方和之漸進數量級估算（利用定積分估計法）：
   對於任意正整數 $k$：
   $\sum_{i=0}^{N-1} i^k = \Theta(N^{k+1})$
   其最高次項係數可由積分求得：
   $\int_{0}^{N} x^k \, dx = \frac{N^{k+1}}{k+1}$

---

解題方法

(1) 第一小題推導

程式碼片段：

k = 0;
for (i = 0; i < N; i++)
  for (j = 0; j < N; j++)
    k++;

1. 迴圈結構分析：

   • 外層迴圈 i 自 $0$ 執行至 $N-1$，共執行 $N$ 次。
   • 內層迴圈 j 自 $0$ 執行至 $N-1$，共執行 $N$ 次。
   • 兩層迴圈之變數相互獨立，內層執行次數不隨 i 的改變而變化。

2. 數學公式推導：
   基本指令 k++ 的總執行次數 $T(N)$ 為：
   $T(N) = \sum_{i=0}^{N-1} \sum_{j=0}^{N-1} 1 = \sum_{i=0}^{N-1} N = N \times N = N^2$

3. 漸進複雜度判定：
   $T(N) = N^2 \implies O(N^2)$

---

(2) 第二小題推導

程式碼片段：

k = 0;
for (i = 0; i < N; i++)
  for (j = 0; j < i*i; j++)
    for (z = 0; z < j; z++)
      k++;

1. 迴圈結構與相依性分析：

   • 外層迴圈：$i$ 從 $0$ 到 $N-1$。
   • 中層迴圈：$j$ 從 $0$ 到 $i^2 - 1$（上限受 $i^2$ 控制）。
   • 內層迴圈：$z$ 從 $0$ 到 $j - 1$（上限受 $j$ 控制）。

2. 由內而外推導執行次數：

   • 最內層 ($z$ 迴圈)：在固定 $j$ 的情況下，z 從 $0$ 變到 $j-1$，基本指令 k++ 共執行 $j$ 次。
   • 中層 ($j$ 迴圈)：在固定 $i$ 的情況下，將最內層執行次數對 $j$ 進行累加（$j$ 由 $0$ 至 $i^2 - 1$）：
     $S(i) = \sum_{j=0}^{i^2 - 1} j = \frac{(i^2 - 1)(i^2)}{2} = \frac{i^4 - i^2}{2}$

Huffman 編碼構造步驟

步驟	合併對象 (頻率)	產生新節點頻率
1	$b\,(3)$、$f\,(5)$	$8$
2	$8$、$c\,(12)$	$20$
3	$g\,(13)$、$d\,(16)$	$29$
4	$20$、$a\,(25)$	$45$
5	$29$、$e\,(39)$	$68$
6	$45$、$68$	$113$ (根)

位元分配（左子 0、右子 1）

• 根左子 $45$ → 前綴 0，右子 $68$ → 前綴 1

【答案】

1. Binary Search Tree

        12
       /  \
      3    15
          /  \
        14    35
              / \
            21   42

核心觀念

深度優先搜尋（DFS）會沿著尚未拜訪的鄰點一路前進，走到沒有未拜訪鄰點時才回溯；廣度優先搜尋（BFS）則用佇列，依距離起點的層次逐層拜訪。兩者都在拜訪頂點時標記，避免重複拜訪。

解題方法

圖中有 $a$ 至 $i$ 共 9 個頂點，邊沒有箭頭，因此視為無向圖。依原圖讀得下列鄰接關係；遇到多個尚未拜訪的鄰點時，依題目註記選字典序最小者。

頂點	鄰點（字典序排列）
$a$	$b,h$
$b$	$a,c,h$
$c$	$b,d,f,i$
$d$	$c,e,f$
$e$	$d,f$
$f$	$c,d,e,g$
$g$	$f,h,i$
$h$	$a,b,g,i$
$i$	$c,g,h$

**(a) DFS：**從 $g$ 開始，先選 $f$，再由 $f$ 選 $c$，接著依序走到 $b$、$a$、$h$、$i$。$i$ 的鄰點都已拜訪，因此開始回溯；回到 $c$ 時，$d$ 仍未拜訪，於是由 $c$ 走到 $d$，再走到 $e$。

因此拜訪順序為

$$g\to f\to c\to b\to a\to h\to i\to d\to e$$

核心觀念

本題考查資料結構與演算法中的核心觀念：遞迴（Recursion）與阿克曼函數（Ackermann's Function）。

1. 阿克曼函數（Ackermann's Function）：
   阿克曼函數是一個極具代表性的非原始遞迴函數（Non-primitive Recursive Function）。它的成長速度極快，常用於測試電腦程式語言的遞迴處理能力、堆疊（Stack）深度上限，以及演算法的時間與空間複雜度分析。

2. 遞迴三大要素：
   解遞迴問題時必須明確定義：

   • 基本情況（Base Case）：當 $m = 0$ 時，函數直接返回 $n + 1$，不再進行遞迴呼叫。
   • 遞迴步驟（Recursive Step）：
     • 當 $m > 0$ 且 $n = 0$ 時，將參數轉化為 $A(m-1, 1)$。
     • 當 $m > 0$ 且 $n > 0$ 時，採用雙重遞迴，將內部求解 $A(m, n-1)$ 的結果作為外層 $A(m-1, \cdot)$ 的第二個參數。
   • 收斂性（Convergence）：每次遞迴呼叫時，$(m, n)$ 的字典序（Lexicographical order）均會嚴格遞減，確保最終必定能在有限步驟內到達 $m = 0$ 的基本情況。

---

解題方法

(1) 計算 $A(2, 1)$ 之值

採用「由外向內拆解、由內向外回推」的代換法（Substitution Method）進行逐步推導：

1. 展開主式 $A(2, 1)$：
   根據定義中 $m > 0, n > 0$ 的規則：
   $A(2, 1) = A(1, A(2, 0))$

2. 求解內層 $A(2, 0)$：
   根據定義中 $m > 0, n = 0$ 的規則：
   $A(2, 0) = A(1, 1)$

3. 求解 $A(1, 1)$：
   根據定義中 $m > 0, n > 0$ 的規則：
   $A(1, 1) = A(0, A(1, 0))$

4. 求解 $A(1, 0)$ 與基底代入：

   • $A(1, 0) = A(0, 1) = 1 + 1 = 2$
   • 代回 $A(1, 1)$：
     $A(1, 1) = A(0, 2) = 2 + 1 = 3$

5. 求解 $A(2, 0)$ 之結果：
   由步驟 2 與步驟 4 可得：
   $A(2, 0) = A(1, 1) = 3$

6. 求解 $A(1, 3)$：
   將 $A(2, 0) = 3$ 代回步驟 1 的 $A(2, 1) = A(1, 3)$：

   • $A(1, 3) = A(0, A(1, 2))$
   • 先求 $A(1, 2) = A(0, A(1, 1)) = A(0, 3) = 3 + 1 = 4$
   • 因此 $A(1, 3) = A(0, 4) = 4 + 1 = 5$

7. 得出最終結果：
   $A(2, 1) = 5$

---

(2) 撰寫計算 $A(m, n)$ 的遞迴程式

採用 C/C++ 語言撰寫對應阿克曼函數數學定義的遞迴函式：

核心觀念

Quicksort 的執行時間取決於每次 partition 選出的 pivot 是否能將資料分割均勻。

對含有 $n$ 個元素的陣列：

• partition 必須掃描元素一次，因此分割成本為 $\Theta(n)$。
• 分割後，pivot 本身已位於最終位置，不必再處理。
• 遞迴時間可用遞迴式分析。

一般形式為：

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

其中 $k$ 是 pivot 左側的元素數量。

---

解題方法

判斷 Quicksort 的最佳與最差情況，關鍵在於觀察每次 partition 後，左右子問題的大小：

• 子問題大小接近一半：遞迴樹高度最小，為最佳情況。
• 一側沒有元素，另一側包含幾乎全部元素：遞迴樹高度最大，為最差情況。

---

（1）Quicksort 的最佳情況

情況說明

最佳情況發生在每次選出的 pivot 都接近目前資料的中位數，使 partition 後的兩個子陣列大小盡量平均。

若 $n$ 為偶數，可近似分成：

$$\frac{n}{2} \quad\text{與}\quad \frac{n}{2}-1$$

因此遞迴式可寫成：

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

忽略常數與小數點差異即可進行漸進分析。

遞迴樹分析

第一層的 partition 成本為：

$$\Theta(n)$$

下一層共有兩個子問題，每個大小約為 $n/2$，總 partition 成本為：

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

再下一層共有四個子問題，每個大小約為 $n/4$，總成本仍為：

$$4\cdot\Theta\left(\frac{n}{4}\right)=\Theta(n)$$

每一層的總成本皆為 $\Theta(n)$。

由於每次問題大小約減半，遞迴樹高度為：

$$\log_2 n$$

所以總執行時間為：

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

因此：

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

最佳情況下，Quicksort 的時間複雜度為 $O(n\log n)$，且其漸進下界也是 $\Omega(n\log n)$。

---

（2）Quicksort 的最差情況

情況說明

最差情況發生在每次選出的 pivot 都是目前資料中的最小值或最大值，使 partition 後：

• 一側子陣列大小為 $0$；
• 另一側子陣列大小為 $n-1$。

例如 pivot 每次都是最小值，遞迴式為：

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

由於 $T(0)=\Theta(1)$，可簡化為：

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

展開遞迴式

將遞迴式逐步展開：

$$T(n)=T(n-1)+cn$$

核心觀念

本題考查 完全二元樹（Complete Binary Tree） 的定義及其在 記憶體中的表示法（Representation）。

1. 完全二元樹（Complete Binary Tree）的定義：
   若一棵二元樹的高度為 $h$，除了第 $h$ 層外，其餘第 $1$ 至 $h-1$ 層的節點數均達到最大值（即滿二元樹）；且第 $h$ 層的所有節點必須由左至右連續排列，中間不允許有任何空缺（Gap）。
2. 樹的儲存結構：
   二元樹主要有兩種實作方式：
   • 連續儲存（Sequential Representation）：使用一維陣列（Array）。
   • 鏈結儲存（Linked Representation）：使用雙向指標的鏈結串列（Linked List）。

---

解題方法

最適合實作完全二元樹的資料結構是 一維陣列（Array）。

原因說明與推導

1. 空間利用率極高（Zero Space Overhead）：
   一般的二元樹若採用陣列儲存，可能因節點分佈不均勻而需填入大量無效的空節點（NIL/Dummy Nodes），造成記憶體浪費；但完全二元樹在按層序（Level-Order）由左至右編號時，節點恰好連續填滿陣列的前 $n$ 個位置，完全不會浪費任何陣列空間。此外，陣列不需要像指標鏈結串列一樣額外為每個節點維護左右子節點指標（Pointer Overhead），節省了記憶體負擔。

2. 父子節點索引計算極快（$O(1)$ Index Arithmetic）：
   設完全二元樹共有 $n$ 個節點，並將節點按層序編號存入一維陣列。以 1-based 索引（陣列第一個元素位於 Index 1）為例：

   • 對於位於索引 $i$ 的節點：
     • 其 父節點（Parent） 位於索引：
       $\lfloor \frac{i}{2} \rfloor$
     • 其 左子節點（Left Child） 位於索引（若 $2i \le n$）：
       $2i$
     • 其 右子節點（Right Child） 位於索引（若 $2i + 1 \le n$）：
       $2i + 1$

核心觀念

本題考驗 5 階 B 樹（B-tree of order 5） 的鍵值（Key）插入與溢位分裂（Split）機制。

對於階數為 $m$ 的 B 樹（本題 $m = 5$），其必須遵循以下結構規範與操作定義：

1. 節點容量限制：
   • 鍵值上限：任一節點最多容納 $m - 1 = 4$ 個鍵值。
   • 子節點上限：任一節點最多擁有 $m = 5$ 個子樹（Child Pointers）。
   • 鍵值下限：除根節點（Root）外，其餘非葉節點與葉節點至少需包含 $\lceil m / 2 \rceil - 1 = \lceil 5 / 2 \rceil - 1 = 2$ 個鍵值。
2. 深度平衡：所有葉節點（Leaf Nodes）必須位於相同的深度（Level）。
3. 插入與分裂法則：
   • 任何新鍵值必定先搜尋並插入至對應的葉節點中。
   • 若插入後該葉節點的鍵值數量達到 $m = 5$ 個，即發生溢位（Overflow）。
   • 發生溢位時，將節點內的 5 個鍵值由小到大排序，取位於正中間（第 $\lceil m / 2 \rceil = 3$ 個）的鍵值作為**中位數（Median Key）向上提升（Promote）**至父節點；左側 2 個較小鍵值與右側 2 個較大鍵值則分別分裂為兩個全新的子節點。
   • 若父節點接收提升的鍵值後亦發生溢位，則依相同法則向上一路連鎖分裂（Cascading Split），直至樹高增加或符合規範為止。

---

解題方法

本題給定之原始 5 階 B 樹結構如下：

• 根節點：$[395, 430, 480]$
• 葉節點 1（鍵值 $< 395$）：$[380, 382]$
• 葉節點 2（鍵值介於 $395 \sim 430$）：$[406, 412]$
• 葉節點 3（鍵值介於 $430 \sim 480$）：$[451, 472]$
• 葉節點 4（鍵值 $> 480$）：$[493, 506, 511]$

依照題目要求，依序執行 $507$ 與 $520$ 之插入推導：

步驟一：插入 507

1. 尋找插入位置：由根節點開始比對，因 $507 > 480$，沿最右側指標尋找到葉節點 4：$[493, 506, 511]$。
2. 寫入鍵值：將 $507$ 插入該葉節點，保持遞增順序，節點鍵值更新為 $[493, 506, 507, 511]$。
3. 容量檢查：此時該節點包含 4 個鍵值，符合上限規範 $\le m - 1 = 4$，未發生溢位，無須進行分裂。

步驟二：插入 520

1. 尋找插入位置：同樣經由根節點比對（$520 > 480$），定位至最右側葉節點 $[493, 506, 507, 511]$。
2. 寫入鍵值：將 $520$ 插入該葉節點，鍵值更新為 $[493, 506, 507, 511, 520]$。
3. 容量檢查與分裂：
   • 節點內鍵值數量達到 5 個（$= m$），觸發溢位（Overflow）。
   • 排序後的 5 個鍵值為：$493, 506, \mathbf{507}, 511, 520$。
   • 取第 3 個鍵值 $\mathbf{507}$ 作為中位數提升至父節點（根節點）。
   • 左側鍵值 $[493, 506]$ 留在原葉節點；右側鍵值 $[511, 520]$ 拆分為獨立的新葉節點。
4. 更新父節點（根節點）：
   • 根節點接收提升的鍵值 $507$，鍵值由 $[395, 430, 480]$ 更新為 $[395, 430, 480, 507]$。

核心觀念

AOE 網路中：

• 頂點代表事件，邊代表活動。
• 活動 $(u,v)$ 的工期為 $d_{uv}$。
• 最早開始時間：

$$ES(u,v)=ve(u)$$

• 最晚開始時間：

$$LS(u,v)=vl(v)-d_{uv}$$

其中：

• $ve(v)$：事件 $v$ 的最早發生時間。
• $vl(v)$：事件 $v$ 的最晚發生時間。
• $ES=LS$ 的活動為關鍵活動，所有關鍵活動組成關鍵路徑。

---

解題方法

依照箭頭方向先做 forward pass，求出各事件的最早時間：

$$ve(v)=\max_{(u,v)}\{ve(u)+d_{uv}\}$$

再由終點反向做 backward pass，求出各事件的最晚時間：

$$vl(u)=\min_{(u,v)}\{vl(v)-d_{uv}\}$$

由圖可讀得活動如下：

活動	工期
$a\to b$	5
$a\to c$	6
$b\to d$	3
$c\to d$	6
$c\to e$	3
$d\to e$	3
$d\to f$	4
$d\to g$	4
$e\to g$	1
$e\to h$	4
$g\to i$	5
$h\to i$	2
$f\to j$	4
$i\to j$	2

1. Forward pass：事件最早時間

$$ve(a)=0$$ $$ve(b)=0+5=5$$ $$ve(c)=0+6=6$$ $$ve(d)=\max(5+3,\;6+6)=12$$ $$ve(e)=\max(6+3,\;12+3)=15$$ $$ve(f)=12+4=16$$ $$ve(g)=\max(12+4,\;15+1)=16$$ $$ve(h)=15+4=19$$ $$ve(i)=\max(16+5,\;19+2)=21$$ $$ve(j)=\max(16+4,\;21+2)=23$$

因此，專案最短工期為 $23$。

2. Backward pass：事件最晚時間

終點事件的最晚時間等於專案工期：

$$vl(j)=23$$

接著反向計算：

$$vl(i)=23-2=21$$ $$vl(f)=23-4=19$$ $$vl(h)=21-2=19$$ $$vl(g)=21-5=16$$ $$vl(e)=\min(16-1,\;19-4)=15$$ $$vl(d)=\min(15-3,\;19-4,\;16-4)=12$$ $$vl(c)=\min(12-6,\;15-3)=6$$ $$vl(b)=12-3=9$$ $$vl(a)=\min(9-5,\;6-6)=0$$

---

(a) 各活動的最早與最晚開始時間

對每個活動 $(u,v)$：

$$ES(u,v)=ve(u),\qquad LS(u,v)=vl(v)-d_{uv}$$