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

核心觀念

BFS（Breadth-First Search，廣度優先搜尋）使用佇列（Queue），從根節點 $s$ 開始，依照「距離起點由近到遠」的順序拜訪節點。

BFS 的規則如下：

1. 將起點 $s$ 標記為已拜訪並放入佇列。
2. 反覆取出佇列前端節點。
3. 依序檢查其鄰接節點；尚未拜訪者標記為已拜訪、設定其父節點，並加入佇列。
4. 每個節點第一次被發現時，便加入 BFS 樹，其父子邊即為樹邊。

題目圖形為無向圖，邊集合為

$$(a,s),(b,s),(c,s),(c,b),(d,s),(d,e).$$

因此各節點的鄰接關係為：

• $s$：$a,b,c,d$
• $a$：$s$
• $b$：$s,c$
• $c$：$s,b$
• $d$：$s,e$
• $e$：$d$

以下依題目列出的鄰接順序處理。

解題方法：逐步執行 BFS

初始狀態：

• 已拜訪集合：$\{s\}$
• 佇列：$[s]$
• BFS 樹：根節點為 $s$

步驟	取出節點	新發現節點	佇列狀態	新增樹邊
1	$s$	$a,b,c,d$	$[a,b,c,d]$	$(s,a),(s,b),(s,c),(s,d)$
2	$a$	無	$[b,c,d]$	無
3	$b$	無；$c$ 已發現	$[c,d]$	無
4	$c$	無；$b$ 已發現	$[d]$	無
5	$d$	$e$	$[e]$	$(d,e)$
6	$e$	無；$d$ 已發現	$[]$	無

其中：

核心觀念

Merge Sort（合併排序）採用「分割與征服」策略：

1. 將陣列遞迴分割成單一元素。
2. 將相鄰且已排序的子陣列兩兩合併。
3. 合併時依序比較兩邊最前面的元素，較小者先放入結果。

時間複雜度為 $O(n\log n)$，額外空間複雜度為 $O(n)$。

題目文字要求排序陣列 $(5,1,8,3,6,4,7,2)$；附圖內容為無向圖，與本題 Merge Sort 無關，因此排序過程依題目文字中的陣列作答。

解題方法：分割階段

原始陣列：

$$(5,1,8,3,6,4,7,2)$$

第一次分割：

$$(5,1,8,3)\quad (6,4,7,2)$$

第二次分割：

$$(5,1)\quad (8,3)\quad (6,4)\quad (7,2)$$

分割至單一元素：

$$(5)\ (1)\ (8)\ (3)\ (6)\ (4)\ (7)\ (2)$$

解題方法：合併階段

先合併相鄰的單一元素：

$$(5)+(1)\rightarrow(1,5)$$ $$(8)+(3)\rightarrow(3,8)$$ $$(6)+(4)\rightarrow(4,6)$$ $$(7)+(2)\rightarrow(2,7)$$

此時陣列分成四個已排序子陣列：

$$(1,5)\quad(3,8)\quad(4,6)\quad(2,7)$$

接著合併兩兩子陣列：

合併 $(1,5)$ 與 $(3,8)$：

核心觀念

本題考遞迴式的漸進複雜度，可使用 Master Theorem：

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

其中：

• $a=3$
• $b=4$
• $f(n)=n^2$

先計算：

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

因為 $\log_4 3<1$，所以：

$$n^{\log_4 3}=O(n^{0.793})$$

而 $f(n)=n^2$ 的成長速度明顯較快。

解題方法

比較 $f(n)$ 與 $n^{\log_4 3}$：

$$n^2=\Omega\left(n^{\log_4 3+\varepsilon}\right)$$

取適當的 $\varepsilon>0$ 即可成立，因此符合 Master Theorem 的第三種情況。若正規性條件成立：

$$a f\left(\frac{n}{b}\right) =3\left(\frac{n}{4}\right)^2 =\frac{3}{16}n^2 \leq cn^2$$

其中 $c=\frac{3}{16}<1$，故：

核心觀念

本題考的是 區間排程（Interval Scheduling） 與 貪心演算法（Greedy Algorithm）。

對兩個開區間 $(a_i,b_i)$ 與 $(a_j,b_j)$，若要互不相交，排序後可檢查：

$$a_j \ge b_i$$

由於題目使用的是「開區間」，當 $a_j=b_i$ 時，兩區間不包含端點，仍然互不相交。

---

解題方法

採用「每次選擇結束時間最早的區間」：

1. 將所有區間依右端點 $b_i$ 遞增排序。

2. 依序掃描排序後的區間。

3. 若目前區間的左端點滿足

   $a_i \ge \text{lastEnd}$

   就選取該區間，並令

   $\text{lastEnd}=b_i$

4. 掃描結束後，所選區間即為最大互不相交子集合。

初始時令 $\text{lastEnd}=-\infty$。

偽程式碼：

GreedyIntervalSchedule(S):
    將 S 依 b_i 遞增排序
    selected = []
    lastEnd = -∞

    for each interval (a_i, b_i) in S:
        if a_i >= lastEnd:
            將 (a_i, b_i) 加入 selected
            lastEnd = b_i

    return selected

---

正確性說明

（A）int list[5] 與 int *plist[5] 的差異

核心觀念

• int list[5]：宣告一個含有 5 個 int 的陣列。
• int *plist[5]：宣告一個含有 5 個「指向 int 的指標」之陣列。

兩者的記憶體配置不同：

int list[5];

可視為：

list[0], list[1], list[2], list[3], list[4]

每個元素直接儲存一個整數。

int *plist[5];

則是：

plist[0], plist[1], ..., plist[4]

每個元素儲存一個位址，因此每一列可以指向不同長度的整數陣列，形成不規則的二維陣列。

解題方法：逐列配置二維陣列

假設要建立 $5 \times n$ 的二維陣列：

#include <stdlib.h>

int rows = 5;
int cols = n;

int *plist[5];

for (int i = 0; i < rows; i++) {
    plist[i] = malloc(cols * sizeof(int));
}

之後即可使用二維陣列的方式存取：

plist[i][j] = 10;
printf("%d", plist[i][j]);

使用完畢後必須逐列釋放：

for (int i = 0; i < rows; i++) {
    free(plist[i]);
}

若希望使用一整塊連續記憶體，也可以寫成：

int *data = malloc(rows * cols * sizeof(int));
int *plist[5];

for (int i = 0; i < rows; i++) {
    plist[i] = data + i * cols;
}

此時 plist[i][j] 等價於：

data[i * cols + j]

複雜度與技巧

• 配置時間：$O(rows)$；若包含初始化全部元素，則為 $O(rows \times cols)$。
• 額外指標空間：$O(rows)$。
• int *plist[5] 的每一列可獨立配置，因此適合建立不規則二維陣列。
• 常見錯誤是把 int *plist[5] 誤認為真正連續的二維陣列；它本質上是「指標陣列」。

---

（B）Inorder 轉 Postorder 與二元樹

核心觀念

原式為：

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

運算優先順序為：

$$括號 > *、/ > +、-$$

同一層級的 *、/、+、- 皆採由左至右結合，因此原式可分組為：

$$(A*B)+\frac{C*(D-E)}{F+H}$$

二元樹

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

Postorder 結果

Postorder 的走訪順序為：

$$左子樹 \rightarrow 右子樹 \rightarrow 根節點$$

因此：