111 年 國立中正大學資訊工程學系碩士班甲組《軟體設計》

這題考驗對二元搜尋法 (Binary Search) 時間複雜度與最大比較次數的理解。

二元搜尋法是一種在有序陣列中搜尋目標值的演算法。它的基本原理是：

1. 檢查陣列中間的元素。
2. 如果中間元素正好是目標值，搜尋就成功了。
3. 如果目標值小於中間元素，則在陣列的左半部繼續搜尋。
4. 如果目標值大於中間元素，則在陣列的右半部繼續搜尋。
5. 不斷重複這個過程，直到找到目標值或陣列的搜尋範圍縮小到空。

對於一個包含 $n$ 個元素的有序陣列，二元搜尋法最多需要進行 $\lfloor \log_2 n \rfloor + 1$ 次比較才能找到目標值（或確定目標值不存在）。這是因為每次比較，搜尋範圍都會縮小一半。

題目中給定的陣列大小是 $n = 2000$。
我們需要計算 $\lfloor \log_2 2000 \rfloor + 1$。

核心觀念

題目考查 C 語言中陣列名稱與 sizeof 運算子的意義。

若 r 是一個真正的整數陣列：

int r[] = {10, 20, 30, 40};

則：

• sizeof(r)：整個陣列所占的記憶體大小
• sizeof(int)：單一 int 元素所占的記憶體大小
• 陣列元素個數：

$$\text{元素個數}=\frac{\text{陣列總大小}}{\text{單一元素大小}} =\frac{\texttt{sizeof(r)}}{\texttt{sizeof(int)}}$$

因此正確形式為：

sizeof(r) / sizeof(int)

解題方法

設陣列 r 中共有 $n$ 個 int 元素，且每個 int 占用 $s$ bytes，則：

$$\texttt{sizeof(r)}=n \times s$$

又因為：

$$\texttt{sizeof(int)}=s$$

所以：

$$\frac{\texttt{sizeof(r)}}{\texttt{sizeof(int)}} = \frac{n\times s}{s} = n$$

這正好得到陣列元素個數，因此選項 (c) 正確。

選項分析

(a) sizeof(r)

此運算式得到的是整個陣列的總位元組數，不是元素個數。

例如：

int r[5];

若 sizeof(int) = 4，則：

$$\texttt{sizeof(r)}=5\times4=20$$

結果是 20，不是元素個數 5，因此錯誤。

(b) sizeof(*r)

陣列名稱 r 在此處可視為指向第一個元素的指標，*r 表示第一個元素，其型別為 int。

因此：

核心觀念

本題考查 C 語言的「陣列名稱與指標運算」：

若 bPtr 指向陣列 b 的第一個元素，則有

$$bPtr = b = \&b[0]$$

C 語言中，陣列下標運算可改寫為指標運算：

$$b[i] \equiv *(b+i)$$

因此：

$$b[3] \equiv *(b+3)$$

由於 bPtr 與 b 都指向 b[0]，所以：

$$b[3] = *(bPtr+3)$$

---

解題方法

直接套用陣列下標與指標的等價關係：

$$b[i] = *(b+i)$$

令 $i=3$，且以 bPtr 取代指向陣列開頭的 b：

$$b[3] = *(bPtr+3)$$

指標加法的單位是「元素」，因此 bPtr + 3 會指向第三個索引位置，也就是 b[3] 的位址；再以 * 取值，即得到 b[3]。

---

選項分析

（a）*(bPtr + 3)

正確。

bPtr 指向 b[0]，因此：

• bPtr + 3 指向 b[3]
• *(bPtr + 3) 取出該位置的元素值

所以：

$$*(bPtr+3)=b[3]$$

---

（b）b[ bPtr + 3 ]

錯誤。

陣列下標運算的形式是：

$$b[\text{整數索引}]$$

核心觀念

本題考察整數的位元移位運算：

• x <<= 1 等同於 x = x << 1：所有位元向左移一格，最右側補入 0，最左側溢出的位元捨棄。
• x >>= 1 等同於 x = x >> 1：所有位元向右移一格。對本題常見的 32 位元二補數模型而言，若移位後的最左位為 $0$，右移時最左側補入 $0$。

四-byte int 具有 $32$ 個位元，設原始位元為：

$$x=b_{31}b_{30}b_{29}\cdots b_1b_0$$

其中 $b_{31}$ 是最左側位元，$b_0$ 是最右側位元。

解題方法

先分析左移：

$$x \ll 1 = b_{30}b_{29}\cdots b_1b_0 0$$

原本的最左側位元 $b_{31}$ 被移出並捨棄，而最右側補入 $0$。

接著再右移一位：

$$(x \ll 1)\gg 1 = 0b_{30}b_{29}\cdots b_1 0$$

因此最後結果具有兩個特徵：

1. 最左側位元必為 $0$。
2. 最右側位元必為 $0$。

換句話說，原本的 $b_{31}$ 與 $b_0$ 都不會保留；中間的位元 $b_{30}$ 到 $b_1$ 則保留下來。

選項分析

這題考驗對遞迴函數的理解與計算。

函數 mystery 是一個遞迴函數，它根據輸入參數 number 的值來計算結果。
基本情況 (base case) 是當 number <= 1 時，函數返回 1。
遞迴步驟 (recursive step) 是當 number > 1 時，函數返回 number 乘以 mystery(number - 1) 的結果。

我們需要計算 mystery(4) 的值。

讓我們一步步展開計算：

1. 呼叫 mystery(4)：
   number 是 4，大於 1。
   所以，執行遞迴步驟：return 4 * mystery(4 - 1);
   即 return 4 * mystery(3);

2. 計算 mystery(3)：
   number 是 3，大於 1。
   所以，執行遞迴步驟：return 3 * mystery(3 - 1);
   即 return 3 * mystery(2);

3. 計算 mystery(2)：
   number 是 2，大於 1。
   所以，執行遞迴步驟：return 2 * mystery(2 - 1);
   即 return 2 * mystery(1);

核心觀念

本題考查：

1. 整數除法與取餘數

   • 個位數：x % 10
   • 去除個位數：x /= 10

2. 十進位數字反轉
   若目前已反轉結果為 rev，下一個數字為 digit，則：

   $rev_{\text{new}} = rev \times 10 + digit$

3. 32 位元有號整數範圍

   $\text{INT\_MIN}=-2^{31}=-2147483648$

   $\text{INT\_MAX}=2^{31}-1=2147483647$

   反轉過程若超出此範圍，必須回傳 0。

---

解題方法

每次取出原數字的個位數，接到反轉結果的末尾：

• digit = x % 10：取出目前個位數
• x /= 10：刪除目前個位數
• rev = rev * 10 + digit：將數字加入反轉結果

以 $x=123$ 為例：

當前 x	digit = x % 10	rev
123	3	3
12	2	32
1	1	321
0	—	321

因此結果為 $321$。

以 $x=120$ 為例：

$120 \rightarrow 12 \rightarrow 1 \rightarrow 0$

取出的數字依序為 $0,2,1$，形成 021。整數不保留前導零，因此結果為 $21$。

---

溢位判斷

不能先執行：

rev = rev * 10 + digit;

因為 rev * 10 可能已經造成 C 語言有號整數溢位。必須在運算前判斷。

正數溢位

若：

rev > INT_MAX / 10

代表乘以 $10$ 後一定超過上限。

若：

rev == INT_MAX / 10

則最後一位不能大於 INT_MAX 的個位數 $7$：

digit > 7

負數溢位

若：

rev < INT_MIN / 10

代表乘以 $10$ 後一定小於下限。

若：

rev == INT_MIN / 10

則最後一位不能小於 INT_MIN 的個位數 $-8$：

digit < -8

完整判斷式為：

if (rev > INT_MAX / 10 ||
    (rev == INT_MAX / 10 && digit > INT_MAX % 10))
    return 0;

if (rev < INT_MIN / 10 ||
    (rev == INT_MIN / 10 && digit < INT_MIN % 10))
    return 0;

在一般 C 編譯環境中：

核心觀念

本題考查物件導向程式設計中，類別成員、存取權限，以及建構子、解構子和遞迴函式的基本定義。

• 資料成員是類別中宣告的變數。
• 成員函式是類別中定義的函式。
• 建構子在類別物件建立時呼叫；解構子在物件生命週期結束、被銷毀時呼叫。
• public 成員可由任何程式碼存取；private 成員只能由該類別內的程式碼存取。
• 遞迴函式會呼叫自己。

解題方法

先根據各描述中的關鍵詞辨認定義，再將符合的描述編號填入各術語：

術語	判斷依據	對應編號
constructor（建構子）	物件建立時呼叫	6
destructor（解構子）	物件結束存在時呼叫	5
data member（資料成員）	類別中的變數	4
member function（成員函式）	類別中的函式	0
private（私有）	只有該類別內的程式碼可存取	8
public（公有）	任何程式碼都可存取	7
recursive（遞迴）	函式呼叫自己	1

核心觀念

C++ 範本（template）讓程式設計者撰寫可參數化的通用程式碼，再依不同的資料型別產生對應的函式或類別。例如，同一個函式範本可以用於整數或浮點數，而不必各寫一份幾乎相同的函式。

解題方法

依原卷圖，第 9 題問的是 C++ templates 的用途，選項 A 至 E 分別談到不同變數／引數、不同資料型別、散布程式碼骨架、改寫程式碼，以及以上皆非。判斷關鍵是看範本參數化的是什麼；C++ 範本主要用來讓同一份通用程式碼適用於不同資料型別。

選項分析

已讀取兩張原卷頁圖。由 原卷頁圖（第 3 頁）確認第 10 題的完整內容：

• 插入順序：$51, 26, 11, 6, 8, 4, 7$
• 選項：
  • (a) $(51,26,11,6,4,8,7)$
  • (b) $(26,11,51,6,4,8,7)$
  • (c) $(8,6,26,4,7,11,51)$
  • (d) $(26,8,51,6,11,4,7)$
  • (e) None of the above

---

核心觀念

本題考兩個觀念的結合：

1. AVL 樹（平衡二元搜尋樹）：每次插入後，若任一節點的左右子樹高度差超過 1，就必須透過旋轉（LL、RR、LR、RL）使樹重新平衡。
2. 二元樹的陣列表示法（array representation）：根節點存於 index 0（或 1），對於 index $i$ 的節點，其左子節點在 $2i+1$、右子節點在 $2i+2$（若以 0 為起始）。按 level-order（層序） 的順序將節點依序填入陣列。

---

解題方法

依插入順序逐一建構 AVL 樹，遇到不平衡時執行對應旋轉，最後將最終的 AVL 樹以 level-order 寫成陣列。

逐步插入與旋轉

插入 51：

  51

插入 26：

    51
   /
  26

平衡因子皆 ≤ 1，無需旋轉。

插入 11：

      51    ← BF = 2（不平衡）
     /
    26
   /
  11

節點 51 的左子樹高度 2、右子樹高度 0，BF = 2。這是 LL 型，對 51 做右旋轉：

    26
   /  \
  11    51

插入 6：

      26
     /  \
    11    51
   /
  6

平衡，無需旋轉。

插入 8：

      26
     /  \
    11    51
   /
  6
   \
    8

節點 11 的 BF = 2（左子樹高度 2、右子樹高度 0），且失衡路徑為「左子 6 → 右子 8」，屬 LR 型。先對 6 左旋、再對 11 右旋：

• 左旋 6：

    11
   /
  8
 /
6

• 右旋 11：

      26
     /  \
    8     51
   / \
  6   11

插入 4：

        26
       /  \
      8     51
     / \
    6   11
   /
  4

檢查各節點平衡因子：節點 8 的 BF = 2 − 1 = 1，節點 26 的 BF = 3 − 1 = 2（不平衡）。節點 26 是 LL 型（沿左-左方向失衡），對 26 做右旋轉：

        8
       / \
      6    26
     /    /  \
    4    11    51

插入 7：

核心觀念

二元樹的後序走訪順序為「左子樹、右子樹、根節點」，前序走訪順序為「根節點、左子樹、右子樹」。若節點只有一個子節點，題目未指定它是左子節點或右子節點，因此可能有不同的二元樹；但這個位置差異不會改變該節點的前序或後序輸出。

解題方法

依原卷可讀到後序序列為 $E,D,A,C,G,F,B,H$；表格列出的子節點數依序是 $A:1、B:2、C:0、D:1、E:0、F:1、G:0、H:2$。

後序序列最後一個節點 $H$ 是根。往前依各節點的子節點數分組：$E$ 是葉節點，$D$ 有一個子節點 $E$，$A$ 有一個子節點 $D$；接著 $C$ 是葉節點，$F$ 有一個子節點 $G$。$B$ 的兩個子樹依序為 $C$ 與 $F(G)$，而 $H$ 的兩個子樹依序為 $A(D(E))$ 與 $B(C,F(G))$。

因此，前序走訪依序是先訪問 $H$，再走訪 $A$ 子樹，最後走訪 $B$ 子樹：

$$H,A,D,E,B,C,F,G$$

這棵樹不唯一：$A、D、F$ 都只有一個子節點，各自可將唯一的子節點放在左側或右側，形成不同的二元樹。不過，單一子節點的左右位置不會改變前序輸出。

核心觀念

最大堆（max-heap）是一種完全二元樹，每個節點的值都大於或等於其子節點。以陣列表示時，索引 $i$ 的左右子節點分別位於 $2i+1$ 與 $2i+2$。

堆積排序先建立最大堆，再連續取出堆頂的最大值。取出堆頂後，將目前堆的最後一個元素移到根節點，並向下調整，使剩餘元素仍符合最大堆性質。

解題方法

圖中原始陣列為 $45, 83, 7, 61, 12, 99, 44, 77, 14, 29$；題目要求輸出前兩個最大值後，列出剩下的陣列。以下採用堆積排序常見的自底向上建堆法。

從最後一個非葉節點開始向上調整，初始最大堆為：

$$[99, 83, 45, 77, 29, 7, 44, 61, 14, 12]$$

第一次取出堆頂 $99$，將最後一個元素 $12$ 移至根節點並向下調整，得到：

$$[83, 77, 45, 61, 29, 7, 44, 12, 14]$$

第二次取出堆頂 $83$，將目前堆尾的 $14$ 移至根節點並向下調整，得到：

$$[77, 61, 45, 14, 29, 7, 44, 12]$$

因此，取出的前兩大值依序為 $99$、$83$，剩餘陣列為 $[77,61,45,14,29,7,44,12]$。

核心觀念

除法雜湊法以鍵值除以表格大小的餘數作為初始位置：

$$h(k)=k\bmod 11$$

若該位置已被占用，線性探測就依序檢查下一格，直到找到空格；探測到表尾時會回到索引 $0$。

解題方法

原卷列出的插入值依序為 $25,42,96,101,102,162,197,201$，表格大小為 $11$。依序計算餘數，遇到碰撞便向後探測：

• $25\bmod 11=3$：放入索引 $3$。
• $42\bmod 11=9$：放入索引 $9$。
• $96\bmod 11=8$：放入索引 $8$。
• $101\bmod 11=2$：放入索引 $2$。
• $102\bmod 11=3$：索引 $3$ 已有 $25$，放入索引 $4$。
• $162\bmod 11=8$：索引 $8$、$9$ 已占用，放入索引 $10$。
• $197\bmod 11=10$：索引 $10$ 已占用，往後回到索引 $0$，放入索引 $0$。
• $201\bmod 11=3$：索引 $3$、$4$ 已占用，放入索引 $5$。

因此索引 $0$ 至 $10$ 的表格為：

核心觀念

本題考查一般樹轉換為二元樹，以及二元樹的後序走訪。

一般樹常用「左子女－右兄弟」表示法轉成二元樹：

• 左指標指向該節點的第一個子女。
• 右指標指向該節點的下一個兄弟。
• 二元樹後序走訪依序為「左子樹、右子樹、根節點」。

因此，轉換後的二元樹後序走訪不一定等同一般樹的後序走訪。

解題方法

原卷圖中的樹結構與題目表示式一致：$A$ 的子女為 $B,C,D$；$B$ 的子女為 $E,F$；$E$ 的子女為 $K,L$；$C$ 的子女為 $G$；$D$ 的子女為 $H,I,J$；而 $H$ 的子女為 $M$。

原樹可畫成：

A
├─ B
│  ├─ E
│  │  ├─ K
│  │  └─ L
│  └─ F
├─ C
│  └─ G
└─ D
   ├─ H
   │  └─ M
   ├─ I
   └─ J

依「左子女－右兄弟」表示法，轉換後各節點的左、右子節點如下：

節點	左子節點（第一個子女）	右子節點（下一個兄弟）
A	B	無
B	E	C
C	G	D
D	H	無
E	K	F
F	無	無
G	無	無
H	M	I
I	無	J
J	無	無
K	無	L
L	無	無
M	無	無

接著依二元樹後序規則逐段走訪：

核心觀念

前序式（prefix form）把每個運算子放在其運算元之前。例如 $X-Y$ 寫成 $-\,X\,Y$。轉換時先依括號與運算子優先順序建立運算結構，再依序輸出「運算子、左運算元、右運算元」。

乘法與除法優先於加法與減法；同一優先級的運算由左至右計算。因此，$F/A-A*D/F$ 會解析為 $F/A-(A*D)/F$，而 $E*C*D$ 會解析為 $(E*C)*D$。

解題方法

依原卷圖，題目表達式為

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

加減同級且由左至右，因此整體結構是

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

逐部分轉成前序式：

• $F/A$：$/\,F\,A$
• $(A*D)/F$：$/\,*\,A\,D\,F$
• $F/A-(A*D)/F$：$-\,/\,F\,A\,/\,*\,A\,D\,F$
• $E/(F/A-(A*D)/F)$：$/\,E\,-\,/\,F\,A\,/\,*\,A\,D\,F$
• $B-E/(F/A-(A*D)/F)$：$-\,B\,/\,E\,-\,/\,F\,A\,/\,*\,A\,D\,F$
• $(E*C)*D$：$*\,*\,E\,C\,D$
• $(A+B)*E$：$*\, +\, A\,B\,E$

核心觀念

本題考查排序演算法的漸近時間複雜度，以及比較式排序的下界。對 $n$ 個互異鍵值進行比較式排序，必須能分辨 $n!$ 種可能的輸入排列。以決策樹表示比較過程時，樹至少需要 $n!$ 個葉節點，因此最壞情況比較次數至少為

$$\left\lceil \log_2(n!) \right\rceil = \Theta(n\log n).$$

因此，若某比較式排序演算法在最壞情況下達到 $\Theta(n\log n)$，便是漸近最優。

解題方法

分別檢查快速排序與合併排序的最壞情況複雜度，再和比較式排序的 $\Omega(n\log n)$ 下界比較。快速排序的結果須區分最壞情況與平均情況，因為分割是否平衡會影響遞迴深度。

選項分析

(a) Quicksort

每次分割需 $\Theta(n)$ 時間。

• 最壞情況： 若每次選到的樞紐都是最大值或最小值，分割大小為 $0$ 與 $n-1$，遞迴式為

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

  累加後得到 $T(n)=\Theta(n^2)$。這高於比較式排序的 $\Theta(n\log n)$ 最優界，因此快速排序在最壞情況下不是漸近最優。

核心觀念

本題考查 Dijkstra 演算法的適用條件、Johnson 重加權，以及 Floyd–Warshall 演算法的全點對最短路徑計算。Dijkstra 要求邊權非負；Johnson 透過頂點勢能重加權，把沒有負權環的圖轉成非負權圖；Floyd–Warshall 則逐一允許頂點作為中繼點，更新所有點對的距離。

解題方法

依原圖讀得頂點順序為 $a,b,c,d$，有向邊為 $a\to b$ 權重 $6$、$a\to c$ 權重 $3$、$b\to d$ 權重 $2$、$c\to d$ 權重 $5$、$d\to c$ 權重 $-3$，以及斜邊 $d\to a$ 權重 $-7$。以下 (a) 以 $a$ 為起點；(b) 使用 Johnson 重加權；(c) 的前驅矩陣以「第 $i$ 列、第 $j$ 欄記錄從 $i$ 到 $j$ 最短路徑上，緊鄰 $j$ 的前一個頂點」為定義。

(a) Dijkstra 的輸出

Dijkstra 的正確性保證要求所有邊權非負；本圖有負權邊 $d\to a=-7$、$d\to c=-3$，因此一般情況下不能保證 Dijkstra 算出正確的最短路徑。

若指定 $a$ 為起點，標準 Dijkstra 依序選取：

1. 選 $a$，得到 $d(b)=6,\ d(c)=3$。
2. 選 $c$，經 $c\to d$ 得到 $d(d)=3+5=8$。
3. 選 $b$，經 $b\to d$ 得到候選距離 $6+2=8$，與目前的 $8$ 相同。
4. 選 $d$。負權邊 $d\to a$、$d\to c$ 會產生候選值 $1$、$5$，但 $a,c$ 已被確定。

所以標準 Dijkstra 的輸出距離為

$$(d(a),d(b),d(c),d(d))=(0,6,3,8).$$

這次結果恰好是正確的最短距離，但只是此起點與此圖上的巧合；負權邊仍使 Dijkstra 不具備一般正確性保證。

(b) 重加權圖

Johnson 演算法先加入超級起點 $q$，並令 $q$ 到每個頂點的邊權皆為 $0$。以 Bellman–Ford 求得勢能：

$$h(a)=-7,\qquad h(b)=-1,\qquad h(c)=-4,\qquad h(d)=0.$$

例如，$d\to a$ 權重 $-7$，所以可得 $h(a)=-7$；再由 $a\to b$、$a\to c$ 得 $h(b)=-1$、$h(c)=-4$。對每條邊套用

$$w'(u,v)=w(u,v)+h(u)-h(v).$$

逐邊計算：

原邊	重加權計算	新權重
$a\to b$	$6+(-7)-(-1)$	$0$
$a\to c$	$3+(-7)-(-4)$	$0$
$b\to d$	$2+(-1)-0$	$1$
$c\to d$	$5+(-4)-0$	$1$
$d\to c$	$-3+0-(-4)$	$1$
$d\to a$	$-7+0-(-7)$	$0$

重加權後所有邊權皆非負，因此可對重加權圖執行 Dijkstra。驗算可見每條新邊權都不小於 $0$，而原圖中任一點對的路徑長度與重加權後的路徑長度只差端點勢能，故最短路徑不變。

(c) Floyd–Warshall 距離與前驅矩陣

初始化時，對角線距離設為 $0$，直接邊填入其權重，其餘距離為 $\infty$：

$$D^{(0)}= \begin{pmatrix} 0&6&3&\infty\\ \infty&0&\infty&2\\ \infty&\infty&0&5\\ -7&\infty&-3&0 \end{pmatrix}.$$

令 $D^{(k)}[i,j]$ 表示只允許前 $k$ 個頂點作為中繼點時，從 $i$ 到 $j$ 的最短距離。使用遞迴式

$$D^{(k)}[i,j] = \min\left(D^{(k-1)}[i,j],\ D^{(k-1)}[i,k]+D^{(k-1)}[k,j]\right).$$

核心觀念

三元 Huffman 編碼是以前綴碼表示符號，並讓平均碼長最小的方法。每一步選取機率最小的三個節點合併成一個父節點，其權重為三者機率之和；重複合併直到只剩根節點。樹枝標記為 $0,1,2$，從根到葉節點的路徑即為該符號的碼字。

三元 Huffman 樹若每個內部節點都有三個子節點，葉節點數須符合 $n\equiv 1\pmod 2$。本題有 $7$ 個符號，符合條件，不需補入虛擬符號。

解題方法

原卷表格列出七個符號及機率：$\alpha,\beta,\gamma,\delta,\varepsilon,\theta,\eta$ 的機率依序為 $0.25,0.20,0.15,0.14,0.13,0.08,0.05$。依機率由小到大，先合併最小的三個節點：

$$0.05+0.08+0.13=0.26$$

這個父節點代表 $\eta,\theta,\varepsilon$。接著在剩餘節點中，合併機率最小的三個：

$$0.14+0.15+0.20=0.49$$

這個父節點代表 $\delta,\gamma,\beta$。最後剩下 $\alpha$、權重 $0.26$ 的父節點，以及權重 $0.49$ 的父節點，將三者連到根節點。

依序為根節點的三個子節點及各群組內的子節點標上 $0,1,2$，可得到一組最適碼：

核心觀念

深度優先搜尋（DFS）從指定起點出發，每次依字母順序走訪尚未拜訪的相鄰頂點。第一次沿著某條邊抵達新頂點時，該邊就是 DFS 生成樹的樹邊；若邊連接的頂點已拜訪，該邊不列入生成樹。

解題方法

圖中的頂點為 $A$ 至 $H$；由圖可讀出無向邊：$(A,B),(A,C),(B,C),(B,D),(B,E),(D,E),(D,F),(E,F),(F,G),(F,H),(G,H)$。從 $B$ 開始，並在每個頂點依字母順序選擇尚未拜訪的鄰點。

1. 從 $B$ 出發，先走到字母最小的鄰點 $A$，加入樹邊 $(A,B)$。
2. 在 $A$，未拜訪鄰點中先走到 $C$，加入 $(A,C)$。$C$ 的鄰點皆已拜訪，回溯至 $B$。
3. $B$ 尚未拜訪的鄰點依序為 $D、E$，先走到 $D$，加入 $(B,D)$。
4. 在 $D$，依字母順序先走到 $E$，加入 $(D,E)$。
5. 在 $E$，走到尚未拜訪的 $F$，加入 $(E,F)$。
6. 在 $F$，依序走到 $G$，加入 $(F,G)$；再從 $G$ 走到 $H$，加入 $(G,H)$。

核心觀念

本題考深度優先搜尋（DFS）中的 $\operatorname{low}(v)$。令 $\operatorname{dfn}(v)$ 為頂點 $v$ 首次被拜訪的編號；$\operatorname{low}(v)$ 是從 $v$ 出發，沿 DFS 樹向下，再至多經一條非樹邊，所能到達的最小 DFS 編號。計算時取以下數值的最小值：$v$ 自己的編號、通往已拜訪祖先的非樹邊所到達的編號，以及 DFS 子節點的 $\operatorname{low}$ 值。

解題方法

圖中的邊為 $A\!-\!B$、$A\!-\!C$、$B\!-\!C$、$B\!-\!D$、$B\!-\!E$、$D\!-\!E$、$D\!-\!F$、$E\!-\!F$、$F\!-\!G$、$F\!-\!H$、$G\!-\!H$。依題意從 $B$ 開始，鄰點按字母順序優先拜訪。

DFS 先走 $B\to A\to C$，回到 $B$ 後走 $B\to D\to E\to F\to G\to H$。因此 DFS 編號為：

$$\operatorname{dfn}(B)=1,\quad \operatorname{dfn}(A)=2,\quad \operatorname{dfn}(C)=3,\quad \operatorname{dfn}(D)=4,\quad \operatorname{dfn}(E)=5,\quad \operatorname{dfn}(F)=6,\quad \operatorname{dfn}(G)=7,\quad \operatorname{dfn}(H)=8.$$

DFS 樹邊為 $B\!-\!A$、$A\!-\!C$、$B\!-\!D$、$D\!-\!E$、$E\!-\!F$、$F\!-\!G$、$G\!-\!H$。非樹邊 $C\!-\!B$ 讓 $C$ 能回到編號 $1$ 的祖先；$F\!-\!D$ 讓 $F$ 能回到編號 $4$ 的祖先；$H\!-\!F$ 讓 $H$ 能回到編號 $6$ 的祖先。

由葉節點往上計算：

• $C$ 經非樹邊 $C\!-\!B$ 到達編號 $1$，所以 $\operatorname{low}(C)=1$；$A$ 的子節點 $C$ 也使 $\operatorname{low}(A)=1$。
• $B$ 是 DFS 根，編號為 $1$，所以 $\operatorname{low}(B)=1$。
• $H$ 經非樹邊 $H\!-\!F$ 回到編號 $6$，故 $\operatorname{low}(H)=6$；$G$ 的子節點 $H$ 使 $\operatorname{low}(G)=6$。

核心觀念

此題考「活動箭線圖」的要徑。每條有向邊代表一項活動，邊上的數字是所需時間；要徑是從起點到終點的總工期最長路徑。可由起點逐點計算最早事件時間：

$$E(v)=\max_{u\to v}\bigl(E(u)+t(u,v)\bigr)$$

解題方法

圖中的活動與時間為：$1\to2$：5、$1\to3$：6、$2\to4$：3、$3\to4$：6、$3\to5$：3、$4\to5$：3、$4\to6$：4、$4\to7$：5、$5\to7$：1、$5\to8$：4、$7\to9$：5、$8\to9$：2、$6\to10$：4、$9\to10$：2。

依照箭線方向逐點計算最早事件時間：

• $E(1)=0$，所以 $E(2)=5$、$E(3)=6$。
• $E(4)=\max(5+3,\ 6+6)=12$。
• $E(5)=\max(6+3,\ 12+3)=15$；$E(6)=12+4=16$。
• $E(7)=\max(12+5,\ 15+1)=17$；$E(8)=15+4=19$。
• $E(9)=\max(17+5,\ 19+2)=22$。

核心觀念

Dijkstra 演算法用來求非負權重圖中，起點到各頂點的最短距離。每一步從尚未選取的頂點中，挑選目前暫定距離最小者定案，再用它更新相鄰頂點的距離。

解題方法

圖中的有向邊與權重為：$1\to2$ 權重 $5$、$1\to3$ 權重 $6$；$2\to4$ 權重 $3$；$3\to4$ 權重 $6$、$3\to5$ 權重 $3$；$4\to5$ 權重 $3$、$4\to6$ 權重 $4$、$4\to7$ 權重 $5$；$5\to7$ 權重 $1$、$5\to8$ 權重 $4$；$7\to9$ 權重 $5$；$8\to9$ 權重 $2$；$6\to10$ 權重 $4$；$9\to10$ 權重 $2$。

從頂點 $1$ 開始，依序選取目前暫定距離最小的頂點：

選取頂點	起點至該點的暫定最短距離	更新重點
$1$	$0$	$d(2)=5,\ d(3)=6$
$2$	$5$	經 $2$ 到 $4$，得 $d(4)=8$
$3$	$6$	經 $3$ 到 $5$，得 $d(5)=9$；到 $4$ 的距離為 $12$，不更新
$4$	$8$	到 $5$ 得 $11$，不更新；$d(6)=12,\ d(7)=13$
$5$	$9$	更新 $d(7)=10,\ d(8)=13$
$7$	$10$	更新 $d(9)=15$
$6$	$12$	更新 $d(10)=16$