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

核心觀念

本題旨在考驗**演算法分析（Algorithm Analysis）中的迴圈計數（Loop Counting）與離散數學的級數求和（Summation Series）**技巧。

解題時需要掌握以下核心要素：

1. 補集計數法（Complement Counting）：在固定上限的雙重迴圈中，求 $i \neq j$ 的組合數，可利用「總組合數 $\left(x^2\right)$」扣除「$i = j$ 的組合數 $(x)$」。
2. 級數求和公式：
   • 一次方和（等差級數）：$\sum_{x=1}^{n} x = \frac{n(n+1)}{2}$
   • 平方和公式：$\sum_{x=1}^{n} x^2 = \frac{n(n+1)(2n+1)}{6}$
3. 變數累加特性：變數 $Z$ 的最終值等於「初始值」加上「敘述 Z++ 被執行的總次數」。

解題方法

步驟一：分析內層迴圈的執行次數

當最外層迴圈變數 $x$ 為定值時，$i$ 與 $j$ 的取值範圍皆為 $1 \le i, j \le x$：

• $i$ 與 $j$ 產生的所有二元對 $(i, j)$ 總數為 $x \times x = x^2$ 種。
• 其中條件 $i = j$ 的組合共有 $x$ 種（分別為 $(1,1), (2,2), \dots, (x,x)$）。
• 因此，滿足條件 if (i != j) 的二元對個數為：
  $x^2 - x = x(x-1)$

即對於給定的 $x$，敘述 Z++ 會被執行 $x^2 - x$ 次。

步驟二：累加外層迴圈獲得總增加量

最外層迴圈 $x$ 從 $1$ 迭代至 $n$，故整個演算法中 Z++ 的總執行次數為：
$\text{Total Increments} = \sum_{x=1}^{n} (x^2 - x) = \sum_{x=1}^{n} x^2 - \sum_{x=1}^{n} x$

代入標準級數求和公式：
$\text{Total Increments} = \frac{n(n+1)(2n+1)}{6} - \frac{n(n+1)}{2}$

提出公因式 $\frac{n(n+1)}{2}$ 進行通分與化簡：
$\text{Total Increments} = \frac{n(n+1)}{2} \left[ \frac{2n+1}{3} - 1 \right]$
$\text{Total Increments} = \frac{n(n+1)}{2} \left[ \frac{2n-2}{3} \right]$

核心觀念

1. 霍夫曼編碼 (Huffman Coding)：
   霍夫曼編碼是一種基於字元出現頻率（或機率）構建最佳前綴碼（Prefix Code）的貪婪演算法（Greedy Algorithm）。出現頻率越高的字元，其編碼長度越短，從而達到資料壓縮的效果。
2. 帶權路徑長度 (Weighted Path Length, WPL)：
   對於一棵擴充二元樹（Extended Binary Tree），其外部節點（葉節點）代表各字元。加權路徑長度 $WPL$ 定義為所有葉節點的權重（頻率 $f_i$）與其從根節點到該葉節點的路徑長度（深度 $d_i$）的乘積之和：
   $WPL = \sum_{i=1}^{n} (f_i \times d_i)$
   此外，根據霍夫曼樹的性質，$WPL$ 亦等於所有內部節點（Internal Nodes）權重之總和。
3. 平均字碼長度 ($L_{avg}$)：
   平均字碼長度代表傳輸每一個符號平均需要的位元數（Bits/Symbol），計算公式為總帶權路徑長度除以所有符號的總頻率：
   $L_{avg} = \frac{WPL}{\sum_{i=1}^{n} f_i} = \frac{WPL}{N}$
   其中 $N = \sum_{i=1}^{n} f_i$ 為資料源總頻率。

解題方法

第一步：構建霍夫曼樹 (Huffman Tree Construction)

將給定之符號與頻率依頻率由小到大排序並存入最小優先佇列（Min-Heap）：
$S = \{A:4, B:7, C:10, D:15, E:20, F:45\}$

每次選取頻率最小的兩個節點合併為一個新的內部節點，重複此步驟直至只剩下一個根節點：

1. 合併 $A(4)$ 與 $B(7)$：
   • 建立內部節點 $N_1 = 4 + 7 = 11$
   • 剩餘節點：$\{C:10, N_1:11, D:15, E:20, F:45\}$
2. 合併 $C(10)$ 與 $N_1(11)$：
   • 建立內部節點 $N_2 = 10 + 11 = 21$
   • 剩餘節點：$\{D:15, E:20, N_2:21, F:45\}$
3. 合併 $D(15)$ 與 $E(20)$：
   • 建立內部節點 $N_3 = 15 + 20 = 35$
   • 剩餘節點：$\{N_2:21, N_3:35, F:45\}$
4. 合併 $N_2(21)$ 與 $N_3(35)$：
   • 建立內部節點 $N_4 = 21 + 35 = 56$
   • 剩餘節點：$\{F:45, N_4:56\}$
5. 合併 $F(45)$ 與 $N_4(56)$：
   • 建立根節點 $N_5 = 45 + 56 = 101$
   • 完成霍夫曼樹構建，總頻率 $N = 101$。

(a) 計算霍夫曼樹的加權路徑長度 (WPL)

核心觀念

本題旨在評量**二元搜尋樹（Binary Search Tree, BST）的基本建構規則以及三種常見的樹的走訪（Tree Traversals）**演算法。

1. 二元搜尋樹（BST）之定義與插入規則：
   對於 BST 中的任意節點 $x$：

   • 若其左子樹存在，則左子樹中所有節點的值皆小於 $x$ 的值。
   • 若其右子樹存在，則右子樹中所有節點的值皆大於 $x$ 的值。
   • 插入新元素 $v$ 時，自根節點開始比對：若 $v < \text{node.val}$ 則往左子樹遞迴搜尋；若 $v > \text{node.val}$ 則往右子樹遞迴搜尋；直至找到適當的空位（null 處）建立新節點。

2. 樹走訪（Tree Traversals）演算法：

   • 前序走訪（Pre-order Traversal）：走訪順序為 根節點（V） $\to$ 左子樹（L） $\to$ 右子樹（R）。
   • 中序走訪（In-order Traversal）：走訪順序為 左子樹（L） $\to$ 根節點（V） $\to$ 右子樹（R）。
   • 後序走訪（Post-order Traversal）：走訪順序為 左子樹（L） $\to$ 右子樹（R） $\to$ 根節點（V）。

解題方法

(a) 逐一插入建構二元搜尋樹（BST）

給定插入序列：$[50, 30, 70, 20, 40, 60, 80]$

1. 插入 50：樹為空，直接作為根節點（Root）。
2. 插入 30：$30 < 50$，成為 $50$ 的左子節點。
3. 插入 70：$70 > 50$，成為 $50$ 的右子節點。
4. 插入 20：$20 < 50$ 往左走；$20 < 30$ 往左走，成為 $30$ 的左子節點。
5. 插入 40：$40 < 50$ 往左走；$40 > 30$ 往右走，成為 $30$ 的右子節點。
6. 插入 60：$60 > 50$ 往右走；$60 < 70$ 往左走，成為 $70$ 的左子節點。
7. 插入 80：$80 > 50$ 往右走；$80 > 70$ 往右走，成為 $70$ 的右子節點。

建構完成之二元搜尋樹如下圖所示：

          50
        /    \
      30      70
     /  \    /  \
    20  40  60  80

(b) 推導三種走訪序列（Pre-order, In-order, Post-order）

根據子樹結構進行遞迴追蹤：

1. Pre-order Traversal（前序走訪：根 $\to$ 左 $\to$ 右）：
   • 拜訪根節點 $50$。
   • 拜訪左子樹（根為 $30$）：拜訪根 $30$ $\to$ 左子節點 $20$ $\to$ 右子節點 $40$（序列：30, 20, 40）。
   • 拜訪右子樹（根為 $70$）：拜訪根 $70$ $\to$ 左子節點 $60$ $\to$ 右子節點 $80$（序列：70, 60, 80）。

核心觀念

1. 排序演算法的穩定度（Stability）

   • 定義：若待排序資料中存在鍵值（Key）相同的元素（例如 $A[i] = A[j]$ 且原順序 $i < j$），經排序過後，$A[i]$ 依然排在 $A[j]$ 前面，則稱該排序演算法為穩定（Stable）；反之，若相同鍵值元素的相對前後順序可能改變，則稱為不穩定（Unstable）。
   • 本質判斷：演算法在運作過程中是否包含「長距離／跨越式交換（Long-distance Swap）」或破壞相對位置的結構調整（如 Heap 下沉操作）。

2. 最壞時間複雜度（Worst-case Time Complexity）

   • 指演算法在最不利的輸入資料分佈下，執行步驟數量的漸進上限（Asymptotic Upper Bound），以 Big-$O$ 記號表示。

解題方法

• (a) 子題：針對題目列出的 6 種排序演算法（Bubble Sort、Selection Sort、Insertion Sort、Merge Sort、Quick Sort、Heap Sort），分析各自的元素搬移與交換機制，區分出穩定與不穩定的演算法。
• (b) 子題：將 (a) 中判定為「不穩定」的演算法取出，列出各自在最壞情況下的時間複雜度，經由漸進成長率比較，選出表現最佳者（時間複雜度最快者）。

選項分析

針對題目給定的 6 種排序演算法逐一說明穩定度與最壞時間複雜度：

1. Bubble Sort（氣泡排序）

   • 穩定度：穩定（Stable）。僅在相鄰元素滿足嚴格大於關係（$A[j] > A[j+1]$）時才進行交換，相等元素不會交換位置，相對順序不變。
   • 最壞時間複雜度：$O(n^2)$。

2. Selection Sort（選擇排序）

   • 穩定度：不穩定（Unstable）。每輪尋找未排序區間的最小值後，將其與未排序區間的第一個元素進行長距離交換。
   • 反例說明：對數列 $[5_a, 5_b, 2]$ 進行升冪排序，第一輪找到最小值 $2$，將其與第一個元素 $5_a$ 交換，數列變為 $[2, 5_b, 5_a]$。此時 $5_a$ 與 $5_b$ 的相對順序倒置。
   • 最壞時間複雜度：$O(n^2)$。

3. Insertion Sort（插入排序）

   • 穩定度：穩定（Stable）。未排序元素由後往前插入已排序區間時，若遇到相同鍵值的元素即停止搜尋並插入其右側，確保相對順序不變。
   • 最壞時間複雜度：$O(n^2)$。

4. Merge Sort（合併排序）

   • 穩定度：穩定（Stable）。在合併（Merge）兩個已排序子陣列時，若左右兩側元素鍵值相等，實作上規定優先取左側子陣列元素進入結果陣列，即可維護相對順序。
   • 最壞時間複雜度：$O(n \log n)$。

核心觀念

這題考有向加權圖的最短路徑。路徑成本是沿途邊權重總和；由於圖中邊權重皆為非負數，可用 Dijkstra 演算法逐步確定各頂點從起點 $A$ 出發的最短距離。

依原圖，會影響本題的邊包括 $A\to D$ 權重 $2$、$D\to G$ 權重 $7$、$G\to H$ 權重 $2$。圖上的方向與權重須依箭頭判讀。

解題方法

從 $A$ 開始，記錄目前已知的最短距離 $d(v)$，每次選取距離最小且尚未確定的頂點，並用它更新相鄰頂點：