113 年 國立臺北大學資訊工程研究所《資料結構與演算法》

核心觀念

本題考查最小生成樹（Minimum Spanning Tree, MST）與 Prim 演算法。對連通且帶權重的無向圖，最小生成樹必須：

• 包含所有頂點；
• 不形成迴圈；
• 具有 $|V|-1$ 條邊；
• 總權重最小。

Prim 演算法從指定起點 $s$ 開始，每次選擇「一端已在樹中、另一端尚未加入，且權重最小」的邊，逐步擴張生成樹。

解題方法

本題要求初始頂點為 $s$，正確作法如下：

1. 初始時令
   $T=\{s\}.$

2. 從所有連接 $s$ 與其他頂點的邊中，選擇權重最小者 $(s,v_1)$，加入生成樹。

3. 此時樹中已有 $\{s,v_1\}$，從所有「一端在樹中、另一端不在樹中」的邊中，選擇權重最小者並加入。

4. 重複上述步驟，直到所有頂點都加入。若圖有 $n$ 個頂點，最後得到 $n-1$ 條邊。

每一步可整理為：

核心觀念

本題考查 Huffman coding。Huffman 編碼是一種不定長度、前綴碼（prefix code）：

• 出現頻率越高的符號，通常配置越短的編碼。
• 出現頻率越低的符號，通常配置越長的編碼。
• 任一符號的編碼不能是另一符號編碼的前綴，以確保能唯一解碼。
• Huffman 演算法每次選取頻率最小的兩個節點合併，重複此步驟即可得到最小加權路徑長度。

檔案所需的最小 bit 數為：

$$\text{總位元數} = \sum_{i} f_i \ell_i$$

其中 $f_i$ 是符號頻率，$\ell_i$ 是該符號的編碼長度。

---

解題方法

將所有符號依頻率由小到大排列：

符號	f	e	a	d	g	b	c
頻率	5	9	12	13	15	26	43

每次取出頻率最小的兩個節點合併：

1. 合併 $f$ 與 $e$：

$$5+9=14$$

2. 合併 $a$ 與 $d$：

$$12+13=25$$

3. 合併頻率 $14$ 與 $g$：

$$14+15=29$$

4. 合併頻率 $25$ 與 $b$：

$$25+26=51$$

5. 合併頻率 $29$ 與 $c$：

$$29+43=72$$

6. 最後合併 $51$ 與 $72$：

$$51+72=123$$

Huffman 樹可表示如下：

                 123
                /   \
              51     72
             /  \   /  \
            b   25 c   29
               / \     / \
              a   d   g   14
                         / \
                        f   e

令左分支為 $0$、右分支為 $1$，可得到一組合法的 Huffman 編碼：

核心觀念

本題考查遞迴式的漸近分析，可使用 Master Theorem：

$$T(n)=aT\left(\frac{n}{b}\right)+f(n)$$

其中：

• $a=5$：每次分成 $5$ 個子問題
• $b=4$：每個子問題的規模為 $n/4$
• $f(n)=n$：每層額外花費的非遞迴成本

Master Theorem 需比較：

$$f(n)=n$$

與

$$n^{\log_b a}=n^{\log_4 5}$$

因為 $5>4$，所以：

$$\log_4 5>1$$

因此：

$$n^{\log_4 5}$$

的成長速度高於 $n$。

---

解題方法：使用 Master Theorem

Master Theorem 的第一種情況為：

$$f(n)=O\left(n^{\log_b a-\varepsilon}\right)$$

其中 $\varepsilon>0$，則：

$$T(n)=\Theta\left(n^{\log_b a}\right)$$

本題中：

$$a=5,\qquad b=4,\qquad f(n)=n$$

且：

$$n=n^1$$

由於：

$$\log_4 5>1$$

可取某個 $\varepsilon>0$，使得：

$$1=\log_4 5-\varepsilon$$

因此符合 Master Theorem 第一種情況，得到：

$$T(n)=\Theta\left(n^{\log_4 5}\right)$$

題目要求的是漸近上界，因此可寫成：

$$\boxed{T(n)=O\left(n^{\log_4 5}\right)}$$

數值上：

$$\log_4 5=\frac{\log 5}{\log 4}\approx 1.161$$

所以也可表示為：

$$T(n)=O(n^{1.161})$$

---

遞迴樹直觀驗算

核心觀念

題目要求判斷是否存在兩個不同元素 $a,b\in S$，使得

$$ab=x.$$

關鍵是將乘法條件改寫為查找問題：

$$b=\frac{x}{a}.$$

因此，依序取出每個元素 $a$，只要檢查：

1. $a$ 是否為 $0$；
2. $x/a$ 是否為整數；
3. $x/a$ 是否存在於 $S$；
4. $x/a\ne a$，確保使用的是兩個不同元素。

使用雜湊表儲存集合元素，即可在期望 $O(1)$ 時間完成存在性查詢。

---

解題方法

先將所有元素存入雜湊表 $H$。

特別處理 $x=0$：

• 乘積為 $0$ 必須至少有一個元素為 $0$；
• 因為題目要求兩個不同元素，所以還必須有另一個元素；
• 對集合 $S$ 而言，只要 $0\in S$ 且 $k\ge 2$，就一定存在符合條件的兩個元素。

當 $x\ne 0$ 時，集合中符合條件的兩個元素都不會是 $0$。逐一檢查每個 $a\in S$，計算

$$b=\frac{x}{a}.$$

若 $b$ 為整數、$b\in S$ 且 $b\ne a$，則找到兩個元素 $a,b$，回傳成功；全部檢查完仍未找到，則回傳失敗。

關鍵偽程式碼

TwoProduct(S, x):
    H ← 建立空的雜湊表

    for each a in S:
        H.insert(a)

    if x = 0:
        if 0 ∈ H and |S| ≥ 2:
            return TRUE
        else:
            return FALSE

    for each a in S:
        if a = 0:
            continue

        if x mod a = 0:
            b ← x / a

            if b ≠ a and H.contains(b):
                return TRUE

    return FALSE

例如 $S=\{2,3,5,10\}$、$x=30$：

核心觀念

本題涵蓋三個重點：

1. Quick sort

   • 採用分割（partition）將資料分成「小於基準」與「大於基準」兩側。
   • 每次選定一個 pivot，完成後 pivot 位於排序後的正確位置。
   • 平均時間複雜度為 $O(n\log n)$，最壞情況為 $O(n^2)$。

2. Inorder 與 Postorder

   • Inorder：左子樹 $\rightarrow$ 根 $\rightarrow$ 右子樹。
   • Postorder：左子樹 $\rightarrow$ 右子樹 $\rightarrow$ 根。
   • 運算子優先權為：
     $*/ \;>\; +-\!$
   • 同一優先權的運算子採左結合。

3. Stack 轉換運算式

   • 運算元直接輸出。
   • 運算子暫存於 stack。
   • 遇到括號時，左括號作為區隔，右括號則將運算子彈出至左括號為止。

題目中的數列疑似因排版遺失空格，以下依合理格式解讀為
$60,\ 80,\ 45,\ 2,\ 36,\ 98,\ 11,\ 47,\ 52,\ 89,\ 75,\ 63,\ 7$。

---

(A) 使用 Quick Sort 排序

分割規則

採用以下升冪排序規則：

• 每個子數列的第一個元素作為 pivot。
• 左指標 $i$ 從左向右尋找第一個大於 pivot 的數字。
• 右指標 $j$ 從右向左尋找第一個小於 pivot 的數字。
• 當 $i<j$ 時，交換 $A[i]$ 與 $A[j]$。
• 當 $i\geq j$ 時，交換 pivot $A[L]$ 與 $A[j]$，pivot 即完成定位。

第一次分割：pivot = 60

原數列：

$$60,\ 80,\ 45,\ 2,\ 36,\ 98,\ 11,\ 47,\ 52,\ 89,\ 75,\ 63,\ 7$$

1. $i$ 遇到 $80>60$ 停止；$j$ 從右側找到 $7<60$：

$$60,\ \underline{80},45,2,36,98,11,47,52,89,75,63,\underline{7}$$

交換 $80$ 與 $7$：

$$60,\ 7,45,2,36,98,11,47,52,89,75,63,80$$

2. $i$ 找到 $98>60$；$j$ 從右側找到 $52<60$：

交換後：

$$60,\ 7,45,2,36,52,11,47,98,89,75,63,80$$

3. 此時左指標與右指標交會，$j$ 停在 $47$。將 pivot $60$ 與 $47$ 交換：

$$47,\ 7,\ 45,\ 2,\ 36,\ 52,\ 11,\ 60,\ 98,\ 89,\ 75,\ 63,\ 80$$

因此：

$$[47,7,45,2,36,52,11]\quad 60\quad [98,89,75,63,80]$$

左半部繼續分割

以 $47$ 為 pivot：

$$[47,7,45,2,36,52,11] \rightarrow [11,7,45,2,36]\quad 47\quad [52]$$

以 $11$ 為 pivot：

$$[11,7,45,2,36] \rightarrow [2,7]\quad 11\quad [45,36]$$

繼續處理：

$$[2,7]\rightarrow [2]\quad 7$$ $$[45,36]\rightarrow [36]\quad 45$$

因此左半部排序為：

$$2,\ 7,\ 11,\ 36,\ 45,\ 47,\ 52$$

右半部繼續分割

以 $98$ 為 pivot：

$$[98,89,75,63,80] \rightarrow [80,89,75,63]\quad 98$$

以 $80$ 為 pivot：

$$[80,89,75,63] \rightarrow [75,63]\quad 80\quad [89]$$

繼續處理：

$$[75,63]\rightarrow [63]\quad 75$$

因此右半部排序為：

$$63,\ 75,\ 80,\ 89,\ 98$$

排序結果

合併左右兩側：

$$\boxed{2,\ 7,\ 11,\ 36,\ 45,\ 47,\ 52,\ 60,\ 63,\ 75,\ 80,\ 89,\ 98}$$

---

(B) Inorder 轉為 Postorder 並畫出二元樹

原式：

$$A*(B+C)+E*F-H/I$$

運算優先順序

先處理括號，再處理乘除，最後處理加減。因此完整結構為：

$$\bigl(A*(B+C)+E*F\bigr)-\bigl(H/I\bigr)$$

其二元樹如下：

                 -
               /   \
              +     /
             / \   / \
            *   * H   I
           / \ / \
          A  + E  F
            / \
           B   C

轉換過程

各子運算式的 Postorder：

• $B+C$：

  $B\ C\ +$

• $A*(B+C)$：

  $A\ B\ C\ +\ *$

• $E*F$：

核心觀念

本題考查以單向 linked list 實作 stack，以及指標與動態記憶體的操作。

Stack 遵守 LIFO（Last In, First Out，後進先出）：

• push：將新元素放到 stack 頂端。
• pop：取出並刪除 stack 頂端元素。
• top：指向目前 stack 的第一個節點。
• 空 stack 時，top == NULL。

由於 linked list 的頭端就是 stack 頂端，因此兩種操作都只需修改頭端指標，時間複雜度皆為 $O(1)$。

題目中的結構宣告依標準 C 語法應寫成：

typedef struct node {
    int value;
    struct node *next;
} node;

解題方法

push 的操作順序

新節點加入 stack 頂端時，必須依序完成：

1. 將資料存入新節點的 value。
2. 讓新節點指向原本的 stack 頂端。
3. 將 top 更新為新節點。

假設原本的 stack 如下：

top
 ↓
[A] → [B] → NULL

加入新節點 C 後：

top
 ↓
[C] → [A] → [B] → NULL

因此程式為：

void push(node **top, int new_value) {
    node *new_node = (node *) malloc(sizeof(node));

    new_node->value = new_value;
    new_node->next = *top;
    *top = new_node;
}

top 的型別是 node **，因為 push 必須修改呼叫端的 stack 頂端指標。若只傳入 node *top，修改的只是函式內部副本，無法更新真正的 stack 頂端。

pop 的操作順序

刪除 stack 頂端時，必須依序完成：

1. 以 deleting_node 暫存目前頂端節點。
2. 先讀出該節點的資料。
3. 將 top 往下一個節點移動。
4. 釋放原本的頂端節點。
5. 回傳取出的資料。

假設原本為：

top
 ↓
[A] → [B] → NULL

執行 pop 後：

top
 ↓
[B] → NULL

程式為：

int pop(node **top) {
    int value;
    node *deleting_node = *top;

    value = deleting_node->value;
    *top = deleting_node->next;

    free(deleting_node);
    return value;
}

完整實作如下：

核心觀念

本題考查：

• 以 stack 實作深度優先搜尋（Depth-First Search, DFS）。
• 使用 回溯法（backtracking） 解迷宮。
• 以 mark[row][col] 記錄已走過的位置，避免重複搜尋。
• 每個 stack 元素記錄：

$$(\text{row},\text{col},\text{dir})$$

其中 dir 表示目前位置下一個尚未嘗試的方向。

move[8] 儲存八個移動方向：

typedef struct {
    int v;    // row 的變化量
    int h;    // col 的變化量
} offsets;

由目前位置與方向計算下一格：

$$\text{next\_row}=\text{row}+\text{move[dir].v}$$ $$\text{next\_col}=\text{col}+\text{move[dir].h}$$

---

解題方法

假設：

• 起點為 (1,1)。
• 出口為 (exit_row, exit_col)。
• maze[r][c] == 0 表示可通行。
• maze[r][c] == 1 表示牆壁。
• 迷宮外圍已設為牆壁，因此不必另外處理陣列越界。
• mark[r][c] == 1 表示該位置已走過。

當目前位置有合法方向時：

1. 將目前位置尚未嘗試的方向取出。
2. 計算下一個位置。
3. 若下一位置是出口，表示找到路徑。
4. 若下一位置是合法且未走過的位置：
   • 將目前位置更新為「下一次從哪個方向繼續嘗試」。
   • 將下一位置 push 入 stack。
5. 若八個方向都無法前進，表示此位置走不通，將它 pop，回到上一格繼續嘗試。

---

關鍵程式碼