113 年 國立陽明交通大學資訊工程學系碩士班《資料結構與演算法》

核心觀念

以單向鏈結串列實作佇列時，head 指向隊首，tail 指向隊尾。執行 push 後必須維持：

• 空佇列時，新節點同時是 head 與 tail。
• 非空佇列時，原隊尾的 next 指向新節點，然後更新 tail 指向新節點。

解題方法

依序檢查空佇列與非空佇列兩種情況。

選項 A 填入後，程式相當於：

if (!head) head = node;
if (tail) tail->next = node;
tail = node;

空佇列時，head 原本為 NULL，因此設為新節點；tail 原本為 NULL，不執行第二個 if；最後將 tail 設為新節點。此時 head 與 tail 都指向新節點。

非空佇列時，head 已有節點，不執行第一個 if；接著將原隊尾的 next 設為新節點，最後更新 tail。兩種情況都符合佇列操作。

選項分析

• (A) 正確。 head = node 處理空佇列；tail->next = node 將新節點接在原隊尾後；tail = node 更新隊尾。

核心觀念

佇列採先進先出（FIFO），head 指向隊首，也就是下一個要移除的節點；tail 指向隊尾。pop 必須先保存隊首節點，再將 head 往後移一格，最後刪除原隊首節點。

解題方法

正確的操作順序是：

1. 令 node 指向目前的 head。
2. 將 head 更新為原隊首的下一個節點。
3. 刪除原隊首節點。
4. 若刪除後 head 為空，代表佇列已空，將 tail 設為 NULL。

因此，應填入 ④: head、⑤: head、⑥: head->next，也就是選項 D。

選項分析

• (A) 錯誤。 node 指向 tail，而 tail->next = tail 會讓尾節點指向自己；接著刪除 node，使 tail 成為懸空指標，佇列鏈結遭到破壞。
• **(B) 錯誤。

核心觀念

單向鏈結串列佇列遵守先進先出（FIFO）：

• head 指向隊首，也就是下一個要被 pop() 移除的節點。
• tail 指向隊尾，也就是最近加入的節點。
• push(n) 將新節點接到隊尾；若佇列為空，head 與 tail 都指向新節點。
• pop() 移除隊首，令 head 指向原隊首的下一個節點；若移除後佇列為空，tail 設為 NULL。

解題方法

依序追蹤節點順序，以及 head、tail 所指的位置：

操作	佇列由隊首至隊尾	head	tail
初始狀態	空	—	—
L.pop()	空	—	—
L.push(10)	10	10	10
L.push(5)	10 → 5	10	5
L.push(3)	10 → 5 → 3	10	3
L.pop()	5 → 3	5	3

核心觀念

C 語言陣列採用 0 起始索引。含有 10 個元素的陣列 m，有效索引為 $0$ 到 $9$。

FSort(a, left, right) 的 left、right 表示要排序區間的左右端點，且兩端都包含在內。程式以 a[left] 作為樞紐，並從 right + 1 設定右側掃描索引，因此呼叫時必須傳入有效的陣列索引範圍。

解題方法

陣列共有 10 個元素：

$$\texttt{m[0]},\ \texttt{m[1]},\ \ldots,\ \texttt{m[9]}$$

要排序整個陣列，左端點是第一個索引 $0$，右端點是最後一個索引 $9$，所以呼叫為：

FSort(m, 0, 9)

程式使用快速排序的分割方式，完成樞紐分割後，再遞迴排序樞紐左右兩側。static int c 只用來累計並印出分割次數，不影響陣列索引或排序範圍。

選項分析

核心觀念

這段程式是快速排序（Quick Sort），以 a[left] 作為樞紐值 d，先將樞紐放到分割後的位置 j，再遞迴處理樞紐左右兩側。

c 是函式內的 static 變數，只初始化一次，所有遞迴呼叫共用同一個計數器。每次執行 left < right 的呼叫完成分割後，程式就會輸出一次並將 c 加一。

解題方法

每次分割會讓一個樞紐元素到達最終位置，之後的遞迴不再處理該位置。若陣列有 $n$ 個元素，當所有區段都縮小到零個或一個元素時，共有 $n-1$ 次非平凡分割，因此輸出中的最大 c 為 $n-1$。

題幹提到的陣列 $m$ 未附在訊息中；依本題標準答案所對應的情況，取 $m$ 有 $7$ 個元素：

$$c_{\max}=7-1=6$$

選項分析

核心觀念

FSort 是以第一個元素 a[left] 為樞紐的快速排序。每次分割後，樞紐會放到最終位置，再分別遞迴處理左右子陣列：

d = a[left]
...
a[left] = a[j]
FSort(a, left, j - 1)
FSort(a, j + 1, right)

遞迴深度取決於每次分割的平衡程度。若樞紐每次都是子陣列的最小值或最大值，便會分成大小為 $0$ 與 $n-1$ 的兩側，形成最差情況，遞迴深度為 $O(n)$。

解題方法

觀察樞紐 d 的選法：每次都取目前子陣列最左側的元素。選項 (D) 是遞增排列，因此每次的樞紐都是目前子陣列的最小值。

以 (D) 為例，第一次分割以 $0$ 為樞紐，分割大小為 $0$ 與 $9$；接著右側子陣列以 $1$ 為樞紐，再分成 $0$ 與 $8$。這種情形一路持續：

$$10 \to 0+9 \to 0+8 \to \cdots \to 0+1$$

因此快速排序形成最長的遞迴鏈，最多需要 $n-1=9$ 次分割，時間複雜度為 $O(n^2)$，遞迴堆疊空間為 $O(n)$。

選項分析

核心觀念

開放定址的雙重雜湊法以第二個雜湊函數決定每次碰撞後的探查步長。鍵值 $k$ 的第 $i$ 次探查位置為

$$h(k,i)=(h_1(k)+i\cdot h_2(k))\bmod 13,\qquad i=0,1,2,\ldots$$

其中 $i=0$ 是初始位置；若該位置已被占用，就依序探查後續位置，直到找到空格。

解題方法

依題目給定的鍵值順序，先插入 $30$ 之前的鍵值：

• $80$：$h_1(80)=2$，放在索引 $2$。
• $69$：$h_1(69)=4$，放在索引 $4$。
• $99$：$h_1(99)=8$，放在索引 $8$。
• $16$：$h_1(16)=3$，放在索引 $3$。
• $73$：初始位置為 $h_1(73)=8$，與 $99$ 碰撞。步長為 $h_2(73)=1+(73\bmod 11)=8$。接著探查 $$(8+8)\bmod 13=3$$ 索引 $3$ 已被 $16$ 占用；再探查 $$(8+2\cdot 8)\bmod 13=11$$ 索引 $11$ 空著，因此 $73$ 放在索引 $11$。

插入 $30$ 時，初始位置為

核心觀念

雙重雜湊的第一個雜湊函數 $h_1(k)$ 會給出每個鍵值的初始位置。若該位置在插入當下已被先前插入的鍵值占用，就會發生碰撞，再依 $h_2(k)$ 尋找其他位置。

因此，判斷本題各選項時，要依照題目給定的插入順序，確認每個鍵值的初始位置在輪到它插入時是否已被占用。

解題方法

依序計算各鍵值的初始位置：

$$\begin{aligned} h_1(80)&=2, & h_1(69)&=4, & h_1(99)&=8,\\ h_1(16)&=3, & h_1(73)&=8, & h_1(30)&=4,\\ h_1(41)&=2. \end{aligned}$$

依照 $80,69,99,16,73,30,41$ 的順序插入：

• $80$ 插入位置 $2$；$69$ 插入位置 $4$；$99$ 插入位置 $8$。
• $16$ 的初始位置是 $3$，當時為空，因此沒有碰撞。
• $73$ 的初始位置是 $8$，已被 $99$ 占用，因此發生碰撞。
• $30$ 的初始位置是 $4$，已被 $69$ 占用，因此發生碰撞。

核心觀念

雙重雜湊使用開放定址法處理碰撞。對鍵值 $k$，第 $i$ 次探查的位置為

$$h(k,i)=(h_1(k)+i\cdot h_2(k))\bmod 13,\qquad i=0,1,2,\ldots$$

其中 $h_1(k)=k\bmod 13$ 是起始位置，$h_2(k)=1+(k\bmod 11)$ 是每次碰撞後的探查步長。若位置已被占用，就依序增加 $i$，直到找到空格。

解題方法

依題目給定順序插入各鍵值。每次先算起始位置與步長，若起始位置已占用，再依探查序列尋找下一個空格：

鍵值 $k$	$h_1(k)$	$h_2(k)$	探查位置	插入位置
80	2	4	2	2
69	4	4	4	4
99	8	1	8	8
16	3	6	3	3
73	8	8	8、3、11	11
30	4	9	4、0	0
41	2	9	2、11、7	7

核心觀念

Kruskal 演算法依邊權重由小到大檢查，每次加入一條「不會形成環」的邊，直到涵蓋全部頂點。含有 $|V|$ 個頂點的生成樹恰有 $|V|-1$ 條邊；本題有 7 個頂點，因此 MST 有 6 條邊。

解題方法

將邊依權重由小到大排列，並逐條檢查是否會形成環：

權重	邊	處理結果
5	A-D	加入
5	C-E	加入
6	D-F	加入
7	A-B	加入
7	B-E	加入，連接兩個不同的連通分量
8	B-C	拒絕，B、C 已連通，加入會形成環
8	E-F	拒絕，E、F 已連通，加入會形成環
9	B-D	拒絕，B、D 已連通，加入會形成環
9	E-G	加入，將 G 接入生成樹

核心觀念

Kruskal 演算法將所有邊依權重由小到大排序，逐一考慮：若加入某邊不會形成環，就將它納入最小生成樹；若會形成環，就略過。含有 $n$ 個頂點的生成樹恰有 $n-1$ 條邊，因此本題 7 個頂點的最小生成樹需要 6 條邊。

解題方法

依權重由小到大考慮各邊：

權重	邊	判斷
5	$A-D$	納入，連接 $A$、$D$
5	$C-E$	納入，連接 $C$、$E$
6	$D-F$	納入，$F$ 尚未連通
7	$A-B$	納入，$B$ 尚未連通
7	$B-E$	納入，連接目前的兩個連通分量
8	$B-C$	略過；$B$ 與 $C$ 已經連通，加入會形成環
8	$E-F$	略過；$E$ 與 $F$ 已經連通，加入會形成環
9	$B-D$	略過；

核心觀念

Kruskal 演算法依邊權重由小到大選邊；若加入某邊會形成環，就略過。含 $n$ 個節點的最小生成樹（MST）有 $n-1$ 條邊，且移除樹中的任一邊都會使樹分成兩個連通部分。

解題方法

依權重排序並套用 Kruskal 演算法：

權重	邊	處理結果
5	A–D	加入
5	C–E	加入
6	D–F	加入
7	A–B	加入
7	B–E	加入
8	B–C	略過；加入會形成環
8	E–F	略過；加入會形成環
9	E–G	加入，所有節點連通

因此 MST 邊為 A–D、C–E、D–F、A–B、B–E、E–G，共 $6$ 條。MST 中最低權重為 $5$，對應兩條邊：A–D 與 C–E。

核心觀念

**$s$-$t$ 割（cut）**是頂點集合的一個分割 $(S,V-S)$，其中 $s\in S$、$t\notin S$。割的容量是所有從 $S$ 指向 $V-S$ 的邊容量總和：

$$c(S,V-S)=\sum_{\substack{(u,v)\in E\\u\in S,\ v\notin S}} c(u,v)$$

可行流 $f$ 必須滿足兩項條件：

1. 容量限制：每條邊的流量不能為負，也不能超過容量，即 $0\le f(u,v)\le c(u,v)$。
2. 流量守恆：除 $s,t$ 以外，每個頂點的流入量等於流出量。

流值 $\operatorname{Val}(f)$ 是從 $s$ 送出的淨流量。最大流最小割定理指出，最大流值等於最小 $s$-$t$ 割的容量；因此任何可行流值都不會大於任何可行割的容量。

解題方法

逐項檢查選項所述是否符合割的定義、可行流的容量與守恆條件，以及最大流演算法的性質。

選項分析

(A) 正確。
若 $(S,V-S)$ 和 $(S',V-S')$ 都是有效的 $s$-$t$ 割，則 $s\in S$、$s\in S'$，且 $t\notin S$、$t\notin S'$。所以 $s\in S\cup S'$，而 $t\notin S\cup S'$。因此 $(S\cup S',V-(S\cup S'))$ 仍符合 $s$-$t$ 割的定義。

核心觀念

殘餘網路中，標示 $f/c$ 的邊表示目前流量為 $f$、容量為 $c$。沿原方向可再送的流量是 $c-f$，沿反方向可退回的流量是 $f$。增廣路徑的增廣量，等於路徑上各殘餘容量的最小值。

有向 $S$-$T$ 割的權重，是從 $S$ 側指向 $T$ 側的邊容量總和；由 $T$ 側指回 $S$ 側的邊不計入。最大流最小割定理指出，最大流值等於最小割權重。

解題方法

圖中可讀到的方向與容量包括：$S\to A$ 為 $7/12$、$S\to D$ 為 $7/11$、$D\to A$ 為 $2/5$、$A\to C$ 為 $9/10$、$C\to D$ 為 $2/5$、$D\to B$ 為 $7/8$、$C\to B$ 為 $11/12$、$B\to C$ 為 $6/7$、$C\to T$ 為 $2/3$、$B\to T$ 為 $12/20$。先由流量與容量求增廣路徑的殘餘容量，再依邊的方向計算割權重。

選項分析

(A) 正確。 路徑 $S\to A\to C\to B\to T$ 上的殘餘容量依序為 $5、1、1、8$，因此增廣量為

$$\min(5,1,1,8)=1.$$

核心觀念

sum(n) 計算 $n$ 的十進位數字和。foo 每次在數字和大於 target 時，將 $n$ 更新為 $\lfloor n/10\rfloor+1$，並讓 $y$ 乘以 $10$。最後回傳 $ny-x$，其中 $x$ 保存原始輸入值。

解題方法

依序追蹤每次迴圈的 $n$ 與 $y$：

次數	$n$	sum(n)	$y$
初始	$12321$	$9$	$1$
第 1 次更新後	$1232+1=1233$	$9$	$10$
第 2 次更新後	$123+1=124$	$7$	$100$

當 $n=124$ 時，sum(n)=7，不再大於 target，迴圈停止。因此

$$z=124\times 100-12321=79$$

核心觀念

sum(n) 計算整數 $n$ 的各位數字總和。foo 則反覆把數字向較高位進位，直到目前候選數的數字總和不超過 target，再回傳候選數與原數的差。

解題方法

令原數為 $x$。程式以 n 記錄進位後的數字，以 y 記錄位值；每次迴圈執行：

• n = n / 10 + 1：捨去個位數後加一，表示向前一位進位。
• y *= 10：把位值提高十倍。

因此，迴圈中的候選數是 $n \times y$。當 sum(n) <= target 時，n * y 就是符合條件的數，回傳值為：

$$n \times y - x$$

也就是從原數 $x$ 起，至少要增加的數量。

例如 $x=987$、target = 10：

• 初始數字總和為 $24$，不符合條件；進位後 n = 98 + 1 = 99、y = 10。
• $99$ 的數字總和為 $18$，仍不符合；再進位後 n = 9 + 1 = 10、y = 100。
• $10$ 的數字總和為 $1$，符合條件。

候選數為 $10 \times 100 = 1000$，所以最少須增加 $1000-987=13$。

每次進位都跳過了較低位數字尚未進位的數值；那些數字只會增加數字總和，無法比進位後的候選數更早達到目標。因此，程式回傳的是符合條件的最小增加量。

核心觀念

題目把向量 $a=(a_0,\ldots,a_{k-1})$ 視為有限體 $\mathbb{Z}_p$ 上的多項式

$$f(x)=\sum_{i=0}^{k-1}a_i x^i$$

並令 $b_j=f(j)$，其中 $j\in\mathbb{Z}_p$。因此，$b$ 是一個次數至多 $k-1$ 的多項式在 $\mathbb{Z}_p$ 所有元素上的取值。

解題關鍵有兩點：用 Horner 法計算多項式值；以及利用「非零多項式的根數不超過其次數」判斷映射是否為一對一。

解題方法

對固定的 $j$，可用 Horner 法改寫：

$$b_j = (\cdots((a_{k-1}j+a_{k-2})j+a_{k-3})j+\cdots+a_1)j+a_0 \pmod p.$$

這需要 $O(k)$ 次模乘法與模加法。因此逐一計算 $p$ 個分量，總時間為 $O(kp)$。

若兩個向量 $a$ 和 $a'$ 對應到相同的 $b$，令

$$g(x)=\sum_{i=0}^{k-1}(a_i-a_i')x^i.$$

則 $g(j)=0$ 對所有 $j\in\mathbb{Z}_p$ 都成立。因為 $p>k$，而 $g$ 的次數至多為 $k-1<p$，它若有 $p$ 個根，只能是零多項式。因此 $a_i=a_i'$ 對所有 $i$ 都成立，映射是一對一。

選項分析

核心觀念

這個映射把係數向量 $a=(a_0,\ldots,a_{k-1})$ 視為多項式

$$f(x)=\sum_{i=0}^{k-1}a_i x^i$$

並將它在 $\mathbb{Z}_p$ 的每個元素 $j$ 上求值，因此 $b_j=f(j)\bmod p$。由於 $p$ 是質數，$\mathbb{Z}_p$ 是有限域；非零多項式在域上的根數不會超過它的次數。

解題方法

比較兩個不同向量 $a$ 與 $a'$，可將它們對應的多項式相減。若兩向量不同，差多項式不是零多項式，且次數至多為 $k-1$。它在某個 $j$ 的值為零，恰好代表兩個映射結果在該位置相同。根數定理因此能判斷相同位置的數量上限。

此外，多項式求值具有線性；而多項式次數小於 $k$ 時，只要知道它在 $k$ 個不同點上的值，就能用插值唯一還原其係數。

選項分析

• (A) 正確。 設 $f(x)$ 與 $g(x)$ 分別對應 $a$ 與 $a'$。因 $a\ne a'$，差多項式 $h(x)=f(x)-g(x)$ 非零，且次數至多為 $k-1$。它在 $\mathbb{Z}_p$ 中最多有 $k-1$ 個根，所以不可能在所有 $p$ 個位置都為零；因此 $b\ne b'$。

核心觀念

凸多邊形的凸性表示：任取 $Q$ 中兩點，連接它們的線段都包含在 $Q$ 內。邊界點與內部點的幾何性質不同；判斷選項時，要留意「內部」是否包含邊界，以及射線的起點位置。

解題方法

圖中顯示凸多邊形的頂點依順時針排列，並以向量 $\vec{\ell}$ 的投影比較點的位置；圖 (a) 標出 $p_1=p_6$ 為最大點、$p_4$ 為最小點，圖 (b) 示意 $p_4\prec_{\vec{\ell}}p_5$。本小題判斷的是凸多邊形的幾何性質，逐項檢查邊界、內部與凸性的定義即可。

選項分析

• (A) 錯。 取一個邊的中點 $q$，令 $\vec{u}$ 沿著該邊方向。當 $\epsilon$ 夠小時，$q+\epsilon\vec{u}$ 與 $q-\epsilon\vec{u}$ 都仍在該邊上。若「inside」指多邊形內部，兩點都不在內部；若包含邊界，則兩點都在 $Q$ 中。因此都不符合「恰有一個」。
• **(B) 對。

核心觀念

將各頂點在 $\vec{\ell}$ 方向上的投影值記為

$$h_i=p_i\cdot\frac{\vec{\ell}}{\|\vec{\ell}\|}.$$

則 $p_i\prec_{\vec{\ell}}p_j$ 等價於 $h_i<h_j$；最大點與最小點分別對應全域最大、最小投影值。

沿凸多邊形邊界繞行一圈，投影值由最小值沿一側上升至最大值，再沿另一側下降至最小值。這個單調結構是循環的，不能直接把任意索引區間視為單調區間；此外，區間 $[a,b]$ 包含兩個端點。

解題方法

原圖的 $\vec{\ell}$ 指向上方，因此位置越高，投影值越大。圖 (a) 中 $p_1=p_6$ 為最高點，$p_4$ 為最低點；圖 (b) 則顯示 $p_4\prec_{\vec{\ell}}p_5$，與投影高度的判讀一致。

判斷各選項時，將比較關係轉成投影值的上升、下降或相等，再以原圖或合法的凸多邊形反例檢查。

選項分析

(A) 錯誤：區間起點仍可能是最大點。

直接使用圖 (a)，取 $a=1$、$b=4$。圖中有

$$p_2\prec_{\vec{\ell}}p_1, \qquad p_4\prec_{\vec{\ell}}p_5,$$

符合選項的兩個條件，但 $[1,4]$ 包含最大點 $p_1$。

因此，即使區間起始處下降、結束後上升，也不能排除區間端點是最大點。

(B) 錯誤：兩端皆上升，區間仍可跨過最大點與最小點。

取一個正六邊形，依順時針排列頂點，令 $\vec{\ell}$ 向上，其頂點投影值依序為

$$(h_1,h_2,h_3,h_4,h_5,h_6) = \left(\frac12,1,\frac12,-\frac12,-1,-\frac12\right), \qquad p_7=p_1.$$

這可由單位圓上角度依序為 $150^\circ,90^\circ,30^\circ,-30^\circ,-90^\circ,-150^\circ$ 的頂點構成，確實是凸正六邊形。

取 $a=1$、$b=6$、$n=7$，則

$$h_1=\frac12<h_2=1, \qquad h_6=-\frac12<h_7=\frac12.$$

兩個條件皆成立，但 $[1,6]$ 包含最大點 $p_2$，所以敘述不成立。

(C) 正確：包含最小點的區間，仍可能延伸到下降段。

核心觀念

令頂點在方向 $\vec{\ell}$ 上的投影值為

$$f_i=p_i\cdot\vec{\ell}.$$

投影時除以 $\|\vec{\ell}\|$ 不影響大小關係，因此最大點就是使 $f_i$ 最大的頂點。

凸多邊形的關鍵性質是：沿邊界循環走一圈，投影值由最小值上升至最大值，再下降至最小值；若有邊垂直於 $\vec{\ell}$，極值處可以出現相同投影值的相鄰頂點。這種循環單峰性，使區間是否含有最大點能由端點附近的資訊判定。

解題方法

原卷印出的更新規則為 $c=\lfloor(a+b)/2\rfloor$，再依 $[a,c]$ 是否包含最大點，令 $b=c$ 或 $a=c$；最後先檢查 $a$，否則輸出 $b$。其中 $0$ 是搜尋範圍 $[1,n-1]$ 的左邊界哨兵，$[0,c]$ 的有效頂點解讀為 $p_1,\ldots,p_c$；$p_n=p_1$ 則是重複的邊界頂點。

1. 正確性：維持「候選區間內存在最大點」

初始搜尋範圍包含全部不同頂點，因此至少包含一個最大點。每次更新：

• 若 $[a,c]$ 含有最大點，令 $b=c$，保留下來的區間仍含最大點。
• 若 $[a,c]$ 不含最大點，原區間中的最大點必在右側；令 $a=c$，仍保留至少一個最大點。

終止時 $b-a=1$，候選頂點只剩端點 $a,b$。若 $a$ 是最大點就輸出 $a$；否則依上述不變量，$b$ 必為最大點。

2. 終止性：區間長度嚴格縮小

令 $d=b-a$。只要迴圈條件成立，就有 $d\geq2$，因此

$$a<\left\lfloor\frac{a+b}{2}\right\rfloor<b.$$

不論更新哪一端，新區間長度都滿足

$$1\leq d_{\text{新}}\leq\left\lceil\frac d2\right\rceil<d.$$

正整數長度持續縮小，必定終止；迴圈次數為 $O(\log n)$。

3. 如何直接在 $O(1)$ 時間判定 $[a,c]$ 是否含最大點

只需讀取端點及其相鄰頂點，不必先找出最大點的位置。 以下給出包含投影值相等情況的完整判定。

先檢查端點是否為最大點。 對頂點 $p_i$，以循環索引定義

$$u_i=f_i-f_{i-1},\qquad v_i=f_{i+1}-f_i.$$

若 $u_i\geq0$、$v_i\leq0$，且至少一個不等式嚴格成立，凸性保證 $p_i$ 是全域最大點。

若 $u_i=v_i=0$，須區分最大值與最小值的平坦邊。由於頂點按順時針排列，邊的外側在左方，因此此時

$$\det(p_{i+1}-p_i,\vec{\ell})>0$$

表示 $\vec{\ell}$ 指向該邊的外側，$p_i$ 位於最大值的平坦邊；行列式小於零則位於最小值的平坦邊。以上均只需常數次運算。

核心觀念

trv1 使用佇列，依序取出較早加入的節點，因此是由左至右的層序走訪。

trv2 使用堆疊，先將右子節點、再將左子節點推入；左子節點會先被取出，因此走訪順序是根、左子樹、右子樹，也就是先序走訪。

解題方法

層序序列為 OPMRTECUS，所以根節點是 O，其左、右子節點依序為 P、M。

先序序列為 OPRTCSUME。根節點 O 之後先走訪左子樹，再走訪右子樹；因此 P 所在左子樹的節點依序是 P、R、T、C、S、U，右子樹則是 M、E。

安排左子樹時，令 P 的左右子節點為 R、T。R 沒有子節點；T 的左右子節點為 C、U，且 C 的左子節點為 S。如此先序走訪會是 P、R、T、C、S、U。再令 M 的左子節點為 E。

建構結果與驗算

核心觀念

二元搜尋樹（BST）插入節點時，若新字元小於目前節點，就往左子樹走；若大於目前節點，就往右子樹走，直到遇到空位置才插入。本題字元彼此相異，因此不需處理重複值。

前序走訪的順序是「根、左、右」：先記錄目前節點，再走訪左子樹，最後走訪右子樹。

解題方法

依序插入 COMPUTERS。以英文字母順序比較，每次從根節點開始，沿著 BST 規則找到新字元應插入的位置：

字元	插入位置
C	根節點
O	大於 C，插在 C 的右側
M	大於 C、小於 O，插在 O 的左側
P	大於 C、O，插在 O 的右側
U	大於 C、O、P，插在 P 的右側
T	大於 C、O、P，小於 U，插在 U 的左側
E	大於 C、小於 O、M，插在 M 的左側
R	大於 C、O、P，小於 U、T，插在 T 的左側
S	大於 C、O、P，小於 U、T，又大於 R，插在 R 的右側

核心觀念

二元搜尋樹（BST）要求：每個節點左子樹的鍵值小於該節點，右子樹的鍵值大於該節點。本題採一般考題慣例，假設鍵值互異。

要判斷某種走訪能否唯一決定 BST，關鍵在於走訪序列能否確定根節點，以及每個節點的左右子樹所包含的鍵值。

解題方法

對前序、後序走訪而言，序列直接指出根節點；BST 的大小關係再將其餘鍵值分到左、右子樹，之後對兩側遞迴重建。

以鍵值集合 $\{1,2,3\}$ 為例：

• 前序序列 $[2,1,3]$：第一個鍵值 $2$ 是根，$1<2$ 屬於左子樹，$3>2$ 屬於右子樹。
• 後序序列 $[1,3,2]$：最後一個鍵值 $2$ 是根；其餘序列中小於 $2$ 的部分屬於左子樹，大於 $2$ 的部分屬於右子樹。

層序走訪也能唯一決定 BST。依層序序列逐一將鍵值插入空 BST，即可重建原樹：每個節點的祖先都在該節點之前出現，因此插入時會先建立它所在搜尋路徑上的祖先。

選項分析

核心觀念

B 樹節點中的鍵值必須依遞增順序排列，子樹則依照相鄰鍵值所形成的區間分配。這項規則讓查詢時可以根據鍵值大小，判斷要往哪個子樹搜尋。

解題方法

令節點中的鍵值依序為 $key[0], key[1], \ldots, key[M-1]$，且

$$key[0] < key[1] < \cdots < key[M-1]$$

依序檢查 $M+1$ 個子樹：

• child[0] 中的所有鍵值都小於 key[0]。
• 對 $1 \le i \le M-1$，child[i] 中的所有鍵值都大於 key[i-1] 且小於 key[i]。
• child[M] 中的所有鍵值都大於 key[M-1]。

因此，各子樹所含鍵值的範圍可表示為：

核心觀念

依前一小題 1-(D) 的定義，一個節點最多 $M$ 個鍵值、$M+1$ 個子節點指標（也就是 order $=M+1$ 的 B-tree）。注意這和「$M$ 為最多子節點數」的寫法差 1，代公式前要先對清楚。

B-tree 的最低占用率來自分裂：節點已有 $M$ 個鍵時再插入一個，變成 $M+1$ 個鍵，取中位數上移到父節點，其餘 $M$ 個鍵分給左右兩個新節點：

$$\text{左}=\left\lfloor\frac{M}{2}\right\rfloor,\qquad \text{右}=\left\lceil\frac{M}{2}\right\rceil$$

分裂出來的節點至少有 $\lfloor M/2\rfloor$ 個鍵，所以這就是可以要求每個非根節點維持的下限；要求更多，分裂後的節點就會違反規定。

解題方法