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

核心觀念

本題分為兩部分：

• System stack：程序執行函式呼叫時，用來保存函式執行所需資訊的堆疊。
• Quick sort：採用分治法，選定基準值（pivot）後，將資料分成「小於 pivot」與「大於 pivot」兩側，再遞迴排序左右子序列。

Quick sort 的基本流程為：

1. 選定 pivot。
2. 從右側找出小於 pivot 的數字，移至左側空位。
3. 從左側找出大於 pivot 的數字，移至右側空位。
4. 左右指標相遇時，將 pivot 放入相遇位置。
5. 對 pivot 左右兩側遞迴處理。

本題採用「以子序列第一個元素為 pivot，左右交替掃描」的 partition 方法。

---

（A）System stack 的內容與運作方式

1. System stack 的定義

System stack 是作業系統與程式執行期間使用的堆疊，主要管理函式呼叫與返回。它採用 後進先出（LIFO, Last In First Out） 的原則。

當函式 $f$ 呼叫函式 $g$ 時，$g$ 的執行資訊會被放在 stack 的頂端；$g$ 執行完畢後，先移除 $g$ 的資訊，恢復 $f$ 的執行狀態。

---

2. Stack frame 的主要內容

每一次函式呼叫通常會建立一個 stack frame，也稱為 activation record，內容包括：

1. 返回位址（return address）
   函式執行完畢後，程式應回到呼叫者的哪一個指令位置。

2. 參數（parameters）
   呼叫函式時傳入的資料。

3. 區域變數（local variables）
   函式內宣告的變數。

4. 暫存資料（temporary values）
   運算過程中暫時保存的中間結果。

5. 保存的暫存器內容（saved registers）
   保存呼叫前的 CPU 暫存器狀態，使函式返回後能恢復原本的執行環境。

6. 控制連結（control link）
   指向呼叫者 stack frame 的資訊，用來返回上一層函式。

7. 返回值（return value）
   函式執行完成後傳回呼叫者的結果。

某些語言或編譯器也會保存 static link、例外處理資訊等內容。

---

3. 函式呼叫時的運作

假設函式 $A$ 呼叫函式 $B$，運作流程如下：

1. 將參數傳給 $B$。
2. 保存返回位址。
3. 建立 $B$ 的 stack frame。
4. 配置 $B$ 所需的區域變數與暫存空間。
5. 執行函式 $B$。
6. 將返回值交給 $A$。
7. 移除 $B$ 的 stack frame。
8. 根據返回位址回到 $A$ 繼續執行。

Stack pointer（SP）通常指向目前 stack 頂端；frame pointer（FP）則用來固定存取目前函式的參數與區域變數。

---

4. 遞迴函式與 System stack

Quick sort 是遞迴函式。每次遞迴呼叫都會建立新的 stack frame，保存：

• 子序列的左界與右界
• pivot 或 partition 所需的指標
• 返回位址
• 尚未完成的遞迴工作

例如：

$$\text{quickSort}(low, high)$$

呼叫左右子問題時，兩個遞迴呼叫會依序放入 system stack。最內層子問題完成後，stack frame 依 LIFO 順序移除，程式返回上一層繼續處理另一側子問題。

因此，遞迴深度會影響 system stack 使用量：

• 平衡分割時：空間約為 $O(\log n)$
• 最差分割時：空間約為 $O(n)$

---

（B）Quick sort 排序

原始數列為：

$$40,\ 78,\ 35,\ 12,\ 6,\ 28,\ 51,\ 67,\ 22,\ 89,\ 3,\ 19,\ 58$$

1. Partition 的移動條件與基準

每一輪選擇子序列第一個元素作為 pivot。

設左指標為 $i$，右指標為 $j$：

1. $j$ 從右向左尋找第一個滿足

$$A[j] < pivot$$

的數字，將它移到左側空位。

2. $i$ 從左向右尋找第一個滿足

$$A[i] > pivot$$

的數字，將它移到右側空位。

3. 當 $i$ 與 $j$ 相遇時，將 pivot 放入該位置。

本題的「移動」採用空位填入方式，因此不必每次都進行完整交換。

---

第一次 partition：pivot = 40

原序列：

$$40,\ 78,\ 35,\ 12,\ 6,\ 28,\ 51,\ 67,\ 22,\ 89,\ 3,\ 19,\ 58$$

移動過程

1. 從右側找小於 $40$ 的數字：

$$19 < 40$$

將 $19$ 移到左端空位。

2. 從左側找大於 $40$ 的數字：

$$78 > 40$$

將 $78$ 移到右側空位。

3. 繼續從右側尋找：

$$3 < 40$$

將 $3$ 移至左側空位。

4. 從左側尋找：

$$51 > 40$$

將 $51$ 移至右側空位。

5. 從右側尋找：

$$22 < 40$$

將 $22$ 移至左側空位。

6. 從左側尋找：

$$67 > 40$$

將 $67$ 移至右側空位。

7. 左右指標相遇於第 8 個位置，放入 pivot $40$。

結果為：

(A) 中序轉後序與二元運算樹

1. 二元運算樹（Expression Tree）

對中序運算式 $A*(B+C)+E*F-H/I$ 依運算子優先權與結合律建構二元樹：

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

2. 後序運算式（Postorder Statement）

對上述二元樹進行後序走訪（左子樹 $\rightarrow$ 右子樹 $\rightarrow$ 根節點）：

【答案】$A B C + * E F * + H I / -$

---

(B) 使用 Stack 實現 Infix 轉 Postfix 之演算法與追蹤過程

1. 演算法設計（Infix to Postfix Algorithm）

優先權定義：

• 內置優先權 $in\_stack\_prec('(') = 0$, $in\_stack\_prec('+','-') = 1$, $in\_stack\_prec('*','/') = 2$
• 到來優先權 $incoming\_prec('(') = 3$, $incoming\_prec('+','-') = 1$, $incoming\_prec('*','/') = 2$

演算法步驟：

1. 建立一個運算子堆疊 $S$ 與輸出佇列 $Q$。
2. 由左至右讀取中序運算式之 Token $x$：
   • 運算元（Operand）： 直接輸出至 $Q$。
   • 右括號 )： 反覆 Pop $S$ 頂端元素至 $Q$，直到 Pop 出左括號 (（( 丟棄不輸出）。
   • 運算子（Operator）或左括號 (： 若 $S$ 非空且 $in\_stack\_prec(S.top()) \ge incoming\_prec(x)$，將 $S.top()$ Pop 至 $Q$；最後將 $x$ Push 入 $S$。
3. 掃描結束後，將 $S$ 中剩餘運算子依序 Pop 至 $Q$。

核心觀念

使用單向鏈結串列實作堆疊（Stack）時，基於後進先出（LIFO）原則，將鏈結串列的頭節點（*top）作為堆疊頂端：

• push：在頭部新增節點，使新節點指向原 *top，並更新 *top 為新節點。
• pop：讀取 *top 節點的值後，將 *top 移動至下一個節點，最後釋放原頂端節點之記憶體。

---

程式碼實作

1. push 函式實作

void push (node **top, int new_value) {
    // assume top is not null
    node *new_node = (node *) malloc (sizeof (node));
    
    new_node->value = new_value; // 寫入資料
    new_node->next = *top;       // 新節點接在舊頂端之前
    *top = new_node;             // 更新頂端指標為新節點
}

2. pop 函式實作

核心觀念

本題考查以 Stack 實作迷宮走法搜尋，核心是：

1. 以二維陣列表示迷宮。
2. 每個位置最多可向八個方向移動。
3. 使用堆疊保存「目前走過的路徑」。
4. 找不到可走方向時，退回上一個位置，這就是 回溯法（backtracking）。
5. 走到出口時，Stack 內的內容即為一條完整路徑。

假設迷宮以矩陣表示：

• 0：可通行
• 1：牆壁
• S：起點
• E：出口

八個移動方向如下：

$$(-1,-1),\ (-1,0),\ (-1,1),\ (0,-1),\ (0,1),\ (1,-1),\ (1,0),\ (1,1)$$

分別代表左上、上、右上、左、右、左下、下、右下。

---

解題方法

一、Stack 儲存路徑

Stack 中每個元素代表一個走過的位置：

$$(r,c)$$

其中 $r$ 是列索引，$c$ 是行索引。

為了知道某個位置的八個方向是否都已經嘗試過，每個 Stack 元素還應保存下一個要嘗試的方向：

$$(r,c,nextDir)$$

其中：

• r, c：目前位置
• nextDir：下一個尚未嘗試的方向編號，範圍為 $0$ 到 $7$

如此一來，回溯到某個位置時，可以繼續嘗試尚未搜尋的方向，不會重複從第一個方向開始。

---

二、判斷合法移動

從目前位置 $(r,c)$ 往第 $k$ 個方向移動：

$$nr=r+dr[k]$$ $$nc=c+dc[k]$$

新位置 $(nr,nc)$ 必須同時符合：

1. 沒有超出迷宮邊界：

$$0\le nr<rows,\qquad 0\le nc<cols$$

2. 不是牆壁。
3. 尚未走訪過。

可用 visited[nr][nc] 記錄是否已經走過。走訪過的位置不可再次加入 Stack，否則在有環路的迷宮中會無限循環。

---

三、搜尋八個方向

每次查看 Stack 頂端的位置，依序測試八個方向：

• 若目前方向可以合法移動，便將目前元素的 nextDir 加一。
• 將新位置標記為已走訪。
• 將新位置 Push 至 Stack。
• 若新位置是出口，搜尋完成。
• 若該方向不合法，繼續測試下一個方向。

方向順序不影響「是否找到路徑」，但會影響找到的路徑內容。

---

四、解決死路問題

若 Stack 頂端的位置八個方向都無法移動，表示目前位置是死路。

此時執行：

1. 將該位置 Pop 出 Stack。
2. 回到上一個位置。
3. 由上一個位置的 nextDir 繼續嘗試尚未搜尋的方向。

若起點也被 Pop 掉，表示整個迷宮不存在從起點到出口的路徑。

這個過程可表示為：

$$\text{走到死路} \Rightarrow \text{Pop 當前位置} \Rightarrow \text{回到上一位置} \Rightarrow \text{嘗試下一方向}$$

---

關鍵伪程式碼

核心觀念

本題要求求出圖中所有頂點對 $(i,j)$ 的可達性（reachability）：判斷是否存在一條由頂點 $i$ 出發、最後抵達頂點 $j$ 的路徑。

可使用 Warshall 演算法計算圖的傳遞閉包（transitive closure）：

• 若 $(i,j)\in E$，則 $i$ 可直接到達 $j$。
• 若存在頂點 $k$，使得 $i$ 可到達 $k$ 且 $k$ 可到達 $j$，則 $i$ 可到達 $j$。
• 每一對頂點都必須判斷，因此結果可用 $n\times n$ 的布林矩陣表示。

令 $R[i][j]$ 表示頂點 $i$ 是否可到達頂點 $j$。

---

解題方法：Warshall 演算法

先建立矩陣 $R$：

$$R[i][j]= \begin{cases} 1, & (i,j)\in E,\\ 0, & (i,j)\notin E. \end{cases}$$

若將長度為 $0$ 的路徑也視為可達，則令：

$$R[i][i]=1,\qquad 1\le i\le n$$

接著依序允許頂點 $1,2,\ldots,n$ 作為中間頂點。

令 $R^{(k)}[i][j]$ 表示只允許頂點 $\{1,2,\ldots,k\}$ 作為中間頂點時，$i$ 是否可到達 $j$。

考慮是否加入頂點 $k$ 作為中間頂點：

• 不經過 $k$：$R^{(k-1)}[i][j]=1$。
• 經過 $k$：必須同時滿足 $R^{(k-1)}[i][k]=1$ 與 $R^{(k-1)}[k][j]=1$。

因此遞迴式為：

$$R^{(k)}[i][j] = R^{(k-1)}[i][j] \lor \left(R^{(k-1)}[i][k]\land R^{(k-1)}[k][j]\right)$$

關鍵程式碼

核心觀念

Kruskal 演算法依邊權重由小到大檢查，每次加入一條不會形成環的邊，直到生成樹包含 $|V|-1$ 條邊。本圖有 5 個頂點，因此最小生成樹需要 4 條邊。

解題方法

由圖讀出邊及權重，按權重遞增排列：

$$(a,e):5,\quad (c,d):6,\quad (b,c):7,\quad (b,d):7.5,\quad (a,d):8,\quad (d,e):9,\quad (a,c):20,\quad (b,e):20$$

依序執行 Kruskal 演算法：

檢查的邊	處理方式	原因
$(a,e)$，權重 $5$	選入	不形成環
$(c,d)$，權重 $6$	選入	不形成環

核心觀念

插入排序（Insertion Sort）將陣列分成兩部分：

• 左側：已排序區
• 右側：尚未處理區

每一回合取出尚未處理區的第一個元素，稱為 key，由右至左比較已排序區中的元素：

• 若已排序元素大於 key，便向右移動一格。
• 找到適當位置後，將 key 插入。

升冪排序的判斷條件為：

$$A[j] > key$$

每完成一回合，已排序區便增加一個元素。

---

解題方法

原始陣列為：

$$(14,10,3,8,6,4,13)$$

第一個元素 $14$ 視為已排序，接著依序插入 $10,3,8,6,4,13$。

第 1 回合：插入 10

已排序區：

$$(14)$$

取出 $key=10$。因為 $14>10$，將 $14$ 向右移動，再把 $10$ 放入前方：

$$(14,10) \rightarrow (10,14)$$

結果：

$$(10,14,3,8,6,4,13)$$

---

第 2 回合：插入 3

目前已排序區為：

$$(10,14)$$

取出 $key=3$：

• $14>3$，$14$ 右移
• $10>3$，$10$ 右移
• $3$ 插入最前方

$$(10,14,3) \rightarrow (3,10,14)$$

結果：

$$(3,10,14,8,6,4,13)$$

---

第 3 回合：插入 8

目前已排序區為：

$$(3,10,14)$$

取出 $key=8$：

• $14>8$，$14$ 右移
• $10>8$，$10$ 右移
• $3<8$，停止移動
• 將 $8$ 插入 $3$ 與 $10$ 之間

$$(3,10,14,8) \rightarrow (3,8,10,14)$$

結果：

$$(3,8,10,14,6,4,13)$$

---

第 4 回合：插入 6

目前已排序區為：

$$(3,8,10,14)$$

取出 $key=6$：

• $14>6$，$14$ 右移
• $10>6$，$10$ 右移
• $8>6$，$8$ 右移
• $3<6$，停止移動
• 將 $6$ 插入 $3$ 與 $8$ 之間

$$(3,8,10,14,6) \rightarrow (3,6,8,10,14)$$

結果：

$$(3,6,8,10,14,4,13)$$

---

核心觀念

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

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

其中：

• $a=7$：每次產生 $7$ 個子問題；
• $b=3$：每個子問題的規模為 $n/3$；
• $f(n)=n^2$：每層額外的非遞迴成本；
• $T(n)$ 在 $n<3$ 時為常數。

Master Theorem 需比較：

$$f(n)=n^2$$

與

$$n^{\log_b a}=n^{\log_3 7}$$

因為：

$$\log_3 7\approx 1.771$$

所以：

$$n^{\log_3 7}=O(n^{1.771})$$

而 $n^2$ 的成長速度較快。

解題方法

由於：

$$2>\log_3 7$$

因此 $f(n)=n^2$ 比 $n^{\log_3 7}$ 大一個多項式量級。再檢查 Master Theorem 第三種情況所需的 regularity condition：

$$af\left(\frac{n}{b}\right) = 7\left(\frac{n}{3}\right)^2 = \frac{7}{9}n^2$$

取 $c=\frac79<1$，可得：

$$af\left(\frac{n}{b}\right)\leq c f(n)$$

因此符合 Master Theorem 第三種情況：

$$T(n)=\Theta(f(n))=\Theta(n^2)$$

題目要求的是「漸近上界」，所以可寫成：