114 年 國立臺灣聯合大學系統（清華、政治、陽明交通、中央四校聯招）研究所電機類《資料結構》

核心觀念

本題考查迴圈執行次數與時間複雜度的估算。迴圈條件為：

for (int i = 0; i*i < n; i++) {
    statement...
}

每次迭代中，變數 $i$ 增加 $1$；迴圈持續至 $i^2 \ge n$。因此關鍵在於找出 $i$ 的最大成長範圍。

解題方法

迴圈執行條件為：

$$i^2<n$$

因為 $i\ge 0$，兩邊開平方可得：

$$i<\sqrt n$$

因此，$i$ 大約會從 $0$ 執行到 $\sqrt n-1$，迴圈執行次數約為：

$$\sqrt n$$

若每次執行的 statement 為常數時間，則總時間複雜度為：

$$T(n)=\Theta(\sqrt n)=\Theta(n^{1/2})$$

所以在選項中應選擇 $O(n^{1/2})$。

選項分析

• (A) $O(1)$：錯誤。
  當 $n$ 增加時，迴圈次數約為 $\sqrt n$，並非固定次數，因此不是常數時間。

核心觀念

本題考查資料結構中資料進出順序的定義。

• Stack（堆疊）：採用後進先出（Last-In, First-Out, LIFO），也可說是先進後出。最後放入的資料會最先取出。
• Queue（佇列）：採用先進先出（First-In, First-Out, FIFO）。最早放入的資料會最先取出。

題目所述的 first-in, last-out，表示「第一個放入的資料最後才取出」，等同於 先進後出（FILO），其概念與 LIFO 相同。

解題方法

將資料依序放入資料結構：

$$A \rightarrow B \rightarrow C$$

若資料結構遵循 first-in, last-out：

1. 最先放入的 $A$ 必須最後取出。
2. 因此後放入的 $C$ 會先取出。
3. 取出順序為：

$$C \rightarrow B \rightarrow A$$

這正是堆疊的運作方式。堆疊通常只允許在同一端進行資料的插入與刪除，該端稱為頂端（top）。

選項分析

核心觀念

本題考查中序表示式（infix expression）轉後序表示式（postfix expression，逆波蘭表示法）。

後序表示式的規則是：運算元先輸出，運算子在其所屬運算元之後輸出。例如：

$$A+B \rightarrow AB+$$

原式為：

$$A*(B+C)-D$$

運算優先順序為：

$$括號 > 乘法 > 減法$$

解題方法

先處理括號內的加法：

$$B+C \rightarrow BC+$$

再將 $A$ 與括號結果相乘：

$$A*(B+C) \rightarrow A(BC+)*$$

移除括號後得到：

$$ABC+*$$

最後將結果與 $D$ 做減法：

$$A*(B+C)-D \rightarrow ABC+*D-$$

因此正確的後序表示式為：

$$\boxed{ABC+*D-}$$

選項分析

• (A) A(BC+)-D：錯誤。*
  此表示式仍保留中序表示法的結構，乘號與減號沒有依後序表示法移到所有運算元之後，因此不是正確的 postfix expression。

核心觀念

本題考查各種排序演算法的平均時間複雜度。常見排序法的比較如下：

排序法	平均時間複雜度	最壞時間複雜度
Bubble sort	$O(n^2)$	$O(n^2)$
Selection sort	$O(n^2)$	$O(n^2)$
Heap sort	$O(n\log n)$	$O(n\log n)$
Insertion sort	$O(n^2)$	$O(n^2)$

其中，$n$ 表示待排序元素的數量。

解題方法

逐一判斷各排序演算法的主要操作次數：

• 若演算法需要反覆進行約 $n$ 輪，每輪又處理約 $n$ 個元素，時間複雜度通常為 $O(n^2)$。
• 若演算法能將問題規模以樹狀結構處理，每次操作成本為 $O(\log n)$，且總共進行 $n$ 次，則複雜度為 $O(n\log n)$。

Heap sort 使用堆積（heap）維護元素順序：

1. 建立堆積的時間複雜度為 $O(n)$。
2. 每次取出最大值或最小值後，需重新調整堆積，成本為 $O(\log n)$。
3. 共取出 $n$ 個元素，因此調整堆積的總成本為

$$n \times O(\log n)=O(n\log n)$$

加上建立堆積的成本：

$$O(n)+O(n\log n)=O(n\log n)$$

因此，Heap sort 的平均時間複雜度為 $O(n\log n)$。

選項分析

(A) Bubble sort

Bubble sort 反覆比較相鄰元素，並將較大的元素逐步往後移動。

平均情況下，需要進行約 $n$ 輪掃描，第 $i$ 輪約需比較 $n-i$ 次，因此比較次數約為

$$(n-1)+(n-2)+\cdots+1 =\frac{n(n-1)}{2} =O(n^2)$$

核心觀念

本題考查排序演算法的 in-place（原地排序） 定義。

若排序過程主要直接在原陣列內交換、移動元素，且額外使用的輔助空間為 $O(1)$，通常稱為原地排序。遞迴堆疊所需空間在一般考試分類中通常不列為主要資料儲存空間，但仍可補充其實際成本。

三種排序法的典型空間需求如下：

排序法	額外輔助空間	是否屬於典型原地排序
Quick sort	分割區通常為 $O(1)$，另有遞迴堆疊	是
Merge sort	合併通常需要 $O(n)$ 暫存陣列	否
Heap sort	$O(1)$	是

因此，本題採用一般資料結構與演算法教科書的標準定義判斷。

解題方法

判斷每個排序演算法在陣列排序過程中，是否需要額外配置與輸入規模同階的儲存空間：

• 額外空間為 $O(1)$：屬於原地排序。
• 額外空間為 $O(n)$：不屬於典型原地排序。

Merge sort 的合併階段通常將左右兩個已排序子陣列合併到一個暫存陣列中，必須配置最多 $O(n)$ 的額外空間，因此不是典型的 in-place sorting algorithm。

選項分析

(A) Quick sort

Quick sort 透過 pivot 將陣列分割成兩部分，分割時可直接在原陣列中交換元素。例如使用雙指標進行 partition，分割階段只需常數個指標與暫存變數，因此額外空間為 $O(1)$。

Quick sort 的遞迴堆疊：

• 平衡分割時約為 $O(\log n)$。
• 最差情況可能達到 $O(n)$。

在一般排序法分類中，Quick sort 仍視為原地排序。因此此選項錯誤。

(B) Merge sort

核心觀念

本題考察「使用 heap 維護前 $k$ 大元素」的方法。

若要在掃描 $n$ 個數字的過程中，隨時保留目前看過的前 $k$ 大元素，應使用 min-heap：

• heap 中恰好保存目前的 $k$ 大元素。
• min-heap 的根節點是這 $k$ 個元素中的最小值，也就是目前第 $k$ 大的數字。
• 新數字只需與根節點比較，即可判斷是否應進入前 $k$。

解題方法

假設題目所稱的 top-$k$ 是指「$k$ 大」：

1. 先將前 $k$ 個數字放入 min-heap。
2. 掃描後續每個數字 $x$：
   • 若 $x \leq$ heap 根節點，則 $x$ 不可能進入前 $k$ 大，忽略。
   • 若 $x >$ heap 根節點，則刪除根節點，並將 $x$ 插入 heap。
3. 掃描結束後，heap 內即為全體數字中的前 $k$ 大元素。

例如目前 min-heap 內容為：

$[3, 8, 12]$

這代表目前保留的前 $3$ 大元素為 $3,8,12$，其中根節點 $3$ 是第 $3$ 大元素。若遇到新數字 $10$，因為 $10>3$，便移除 $3$ 並加入 $10$；若遇到 $2$，則直接忽略。

每次插入或刪除的時間複雜度為 $O(\log k)$，掃描 $n$ 個數字的總時間複雜度為：

$O(n\log k)$

heap 所需的額外空間為：

$O(k)$

選項分析

(A) min-heap

正確。

核心觀念

本題考查使用大小為 $k$ 的 heap，掃描 $n$ 個數字以維持前 $k$ 大元素時的時間複雜度。

若要維持前 $k$ 大元素，通常使用 min-heap：

• Heap 中存放目前看到的前 $k$ 大元素。
• Heap 的根節點是這 $k$ 個元素中最小者，也就是目前第 $k$ 大的元素。
• 新元素若大於根節點，便取代根節點，再進行 heapify。
• Heap 大小固定為 $k$，因此每次調整的成本為 $O(\log k)$。

解題方法

掃描每個元素時：

1. 前 $k$ 個元素先建立大小為 $k$ 的 heap。
2. 對其餘元素逐一處理：
   • 取出 heap 根節點，成本為 $O(1)$。
   • 若新元素不大於根節點，直接忽略。
   • 若新元素大於根節點，替換根節點並重新調整 heap，成本為 $O(\log k)$。

最多需要對 $n$ 個元素進行上述檢查，因此總時間複雜度為：

$$O(n) + O(n\log k)=O(n\log k)$$

其中建立初始 heap 的成本可視為 $O(k)$；即使逐一插入而為 $O(k\log k)$，在整體掃描成本中仍不改變主要答案。所需額外空間為：

$$O(k)$$

選項分析

核心觀念

本題考查：

1. **Max binary heap（最大二元堆積）**的插入操作。
2. 插入新元素時，必須先放在完全二元樹的下一個空位置，再向上調整。
3. 最大堆積的性質為：每個父節點的值皆大於或等於其子節點。
4. 樹高定義為「根節點到最深葉節點的邊數」。

共有 $8$ 個元素，形成高度為 $3$ 的完全二元樹。

解題方法

依序插入各元素，若新節點大於父節點，就持續向上交換。

插入 $3$

$$[3]$$

插入 $41$

$41>3$，與父節點交換：

$$[41,3]$$

插入 $52$

先放入陣列尾端：

$$[41,3,52]$$

$52>41$，向上交換：

$$[52,3,41]$$

插入 $26$

先放入最後位置：

$$[52,3,41,26]$$

$26>3$，交換：

$$[52,26,41,3]$$

插入 $38$

$$[52,26,41,3,38]$$

$38>26$，交換：

$$[52,38,41,3,26]$$

插入 $57$

先放入最後位置：

$$[52,38,41,3,26,57]$$

$57>41$，交換：

$$[52,38,57,3,26,41]$$

接著 $57>52$，再與根節點交換：

$$[57,38,52,3,26,41]$$

插入 $9$

$$[57,38,52,3,26,41,9]$$

$9<52$，不需交換。

插入 $49$

$$[57,38,52,3,26,41,9,49]$$

$49>3$，向上交換：

核心觀念

二元搜尋樹（Binary Search Tree, BST）遵守：

• 左子樹所有鍵值小於根節點。
• 右子樹所有鍵值大於根節點。
• 依序插入資料時，每個新節點都由根節點開始比較，直到找到適當的空位置。
• 樹高（height）通常定義為「根節點到最深葉節點的最長邊數」；單一根節點的樹高為 $0$。

解題方法

依序插入：

1. 插入 $3$：成為根節點。
2. 插入 $41$：$41>3$，放在 $3$ 的右側。
3. 插入 $52$：$52>3$、$52>41$，放在 $41$ 的右側。
4. 插入 $26$：$26>3$、$26<41$，放在 $41$ 的左側。
5. 插入 $38$：$38>3$、$38<41$、$38>26$，放在 $26$ 的右側。
6. 插入 $57$：$57>3$、$57>41$、$57>52$，放在 $52$ 的右側。
7. 插入 $9$：$9>3$、$9<41$、$9<26$，放在 $26$ 的左側。
8. 插入 $49$：$49>3$、$49>41$、$49<52$，放在 $52$ 的左側。

形成的 BST 為：

核心觀念

最大二元堆積（max binary heap）必須同時符合：

1. 完全二元樹結構：以陣列儲存時，節點依層序排列。
2. 最大堆積性質：每個父節點值都不小於其子節點：

$$\text{parent} \geq \text{left child}, \qquad \text{parent} \geq \text{right child}$$

若陣列採用 $0$ 起始索引，索引為 $i$ 的節點，其父節點索引為：

$$\operatorname{parent}(i)=\left\lfloor \frac{i-1}{2}\right\rfloor$$

本題各陣列皆有 $9$ 個元素，直接依陣列順序形成完全二元樹，因此只需檢查父子節點的大小關係。

解題方法

每個陣列的樹形結構如下：

$$\begin{array}{c} a_0\\ /\quad \backslash\\ a_1\quad a_2\\ /\ \backslash\quad /\ \backslash\\ a_3\ a_4\ a_5\ a_6\\ /\ \backslash\ /\ \backslash a_7\ a_8 \end{array}$$

逐一檢查所有父節點即可。只要找到一組「父節點小於子節點」，該陣列就不是最大二元堆積。

選項分析

(A) $\{16,14,9,4,8,12,5,3,2\}$

其父子關係包括：

在二元搜尋樹 (BST) 中搜尋 101 時，從根節點開始必須同時維持一個 下限 (low) 與 上限 (high)：

• 若目前節點 $v$ 大於 101，須往左子樹走，更新 high = v；
• 若 $v$ 小於 101，須往右子樹走，更新 low = v；
• 任一次左移的節點必須滿足 low < v < high，右移亦同。

依此檢查四個選項：

序列	判斷結果
A 20 → 252 → 41 → 49 → 130 → 120 → 131 → 101	在從 120 左移到 131 時 high 已被設定為 120，131 > 120，違反 high 上限，不可能

關鍵條件

1. $A$ 必須與 $C$ 相鄰。
2. $D$ 與 $E$ 不能相鄰。

驗證各選項是否能成為第 3 位

• $B$ 為第 3 位
  • 剩餘位置：$1,2,4,5$。
  • 為使 $A$、$C$ 相鄰，只能放在 $(1,2)$ 或 $(4,5)$。
  • 任一情況下，$D$、$E$ 只能佔剩下的兩個相鄰位置，違反「$D$、$E$ 不相鄰」。
  • 因此 $B$ 不可能 站在第 3 位。

核心觀念

本題考查 Fibonacci 數列的遞迴定義：

$$F(0)=0,\qquad F(1)=1$$

且對於 $i\ge 0$：

$$F(i+2)=F(i)+F(i+1)$$

也就是每一項等於前兩項的和。

解題方法

依序計算 $F(5)$、$F(6)$ 與 $F(7)$：

$$F(5)=F(3)+F(4)=2+3=5$$ $$F(6)=F(4)+F(5)=3+5=8$$ $$F(7)=F(5)+F(6)=5+8=13$$

因此：

$$\boxed{F(7)=13}$$

選項分析

核心觀念

本題考察單向鏈結串列的「環（loop／cycle）偵測」，以及 Floyd 的「龜兔賽跑演算法（Tortoise and Hare Algorithm）」。

程式中設定兩個指標：

• slow：每次前進一個節點。
• fast：每次前進兩個節點。

slow = slow->next;
fast = fast->next->next;

若鏈結串列沒有環，fast 最終會走到 NULL；若鏈結串列存在環，兩個指標會在環內相遇，因此可藉由判斷：

if (slow == fast)
    return 1;

來確認是否存在環。

需注意，slow == fast 比較的是兩個指標是否指向「同一個節點」，不是比較節點中的 data 是否相同。

解題方法

程式的迴圈條件為：

while (slow && fast && fast->next)

這表示只要 slow、fast 以及 fast->next 都不是 NULL，就持續移動兩個指標。

每一輪的移動方式如下：

slow = slow->next;          // 前進 1 步
fast = fast->next->next;    // 前進 2 步

沒有環的情況

例如：

A → B → C → D → NULL

fast 的移動速度較快，會先抵達 NULL。此時迴圈結束，函式執行：

return 0;

代表鏈結串列沒有環。

有環的情況

例如：

A → B → C → D
        ↑     ↓
        └─────┘

當兩個指標進入環之後，fast 每輪比 slow 多前進一個節點。設環長度為 $k$，兩個指標之間的距離每輪會改變 $1$（以模 $k$ 計算），因此經過有限輪後必定相遇。

相遇時：

slow == fast

函式立即回傳：

return 1;

因此，funcA() 的功能是判斷鏈結串列是否包含環。

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$

核心觀念

時間複雜度必須根據 funcA() 的實際程式碼判定，不能僅由函式名稱或選項推論。分析時需觀察：

• 迴圈執行次數是否隨 $n$ 增加。
• 是否有巢狀迴圈。
• 每次迭代中變數如何變化，例如 $i \leftarrow i+1$ 或 $i \leftarrow 2i$。
• 遞迴函式的遞迴次數與每層工作量。

常見複雜度判定如下：

$$\text{固定次數操作}=O(1)$$ $$\text{單層執行 }n\text{ 次的迴圈}=O(n)$$ $$\text{兩層各執行 }n\text{ 次的巢狀迴圈}=O(n^2)$$ $$\text{每次將問題規模減半，且每層工作量為 }O(n)=O(n\log n)$$

解題方法

本題題幹只有函式名稱 funcA()，未提供函式內容，因此無法計算其基本操作的執行次數，也無法建立時間複雜度函數 $T(n)$。

判定流程應為：

1. 找出輸入規模 $n$。
2. 計算迴圈或遞迴的執行層數。
3. 求出總基本操作次數 $T(n)$。
4. 忽略常數與低階項，取其漸近表示法。

例如：

核心觀念

「Auxiliary memory space」是指演算法執行過程中，除了儲存原始輸入資料之外，額外使用的記憶體空間。分析時須觀察：

• 區域變數數量是否固定；
• 是否配置與 $n$ 有關的陣列或資料結構；
• 是否使用遞迴，並計算遞迴呼叫堆疊深度；
• 是否建立暫存陣列、複製資料或其他額外結構。

題目未提供 funcA() 的函式內容，因此無法由目前資訊判定其輔助空間複雜度。

解題方法

必須先取得 funcA() 的完整程式碼，再依下列方式分析：

• 若只使用固定數量的變數，且沒有遞迴或隨 $n$ 增長的配置，則為 $O(1)$。
• 若配置長度與 $n$ 成正比的陣列，或遞迴深度為 $n$，則為 $O(n)$。
• 若配置 $n \times n$ 的矩陣，則為 $O(n^2)$。
• 若遞迴深度或額外儲存結構的規模為 $O(n\log n)$，則為 $O(n\log n)$。

核心觀念

本題考查堆疊（Stack）的應用與經典演算法問題——最長有效括號子字串（Longest Valid Parentheses）。

1. 堆疊儲存索引（Index）而非字元：
   • 透過儲存字元的索引位置，當遇到右括號 ')' 匹配成功時，可直接利用當前索引 $i$ 與堆疊頂端元素 $\text{st.top()}$ 的差值計算出當前有效括號子字串的長度：
     $\text{長度} = i - \text{st.top()}$
2. 哨兵節點／基準點（Sentinel Index -1）：
   • 程式初始時執行 st.push(-1)，目的是作為長度計算的基準邊界，使得從字串開頭（索引 $0$）就成立的有效括號可以正確算出長度（例如 $i - (-1) = i + 1$）。
   • 當右括號過多導致堆疊清空時，將該右括號的索引 st.push(i) 作為新的「未匹配基準點」。

---

解題方法

給定輸入字串 $s = \text{"()"}$，字串長度 $s.\text{length}() = 2$。

1. 變數初始狀態

• 堆疊 st：放入底標 -1，即 $\text{st} = [-1]$（頂端為 $-1$）。
• maxLen = 0。

2. 迴圈追蹤（Trace）

步驟 ($i$)	當前字元 $s[i]$	條件分支與操作	堆疊內容（底 $\to$ 頂）	$\text{maxLen}$ 計算與更新
初始	—	st.push(-1)	[-1]	$0$
$i = 0$	'('	符合 s[i] == '('，執行 st.push(0)	[-1, 0]	不變（$0$）

核心觀念

這題涉及括號字串的「平衡值」計算。常見定義是：

• 遇到左括號 (，平衡值加 $1$；
• 遇到右括號 )，平衡值減 $1$；
• funcB(s) 回傳掃描完整個字串後的最終平衡值。

題目未附上 funcB 的函式定義；以下依資料結構中最常見的括號平衡計算定義作答。

解題方法

令初始平衡值為 $0$，逐字元掃描：

字元	計算	平衡值
(	$0+1$	$1$
)	$1-1$	$0$
(	$0+1$	$1$
(	$1+1$	$2$
)	$2-1$	$1$
)	$1-1$	$0$

因此：

核心觀念

本題考查利用「堆疊（stack）」判斷括號是否配對正確。

掃描字串 $s$ 時，採用以下規則：

• 遇到開括號 (：將其索引（index）推入堆疊。
• 遇到閉括號 )：應與最近尚未配對的 ( 配對，因此從堆疊頂端取出一個索引。
• 若遇到 ) 時堆疊原本就是空的，表示沒有可配對的開括號，這個 ) 即為未配對的閉括號。
• 掃描結束後，若堆疊仍不為空，表示有未配對的開括號。

因此，判斷未配對閉括號的時機，是「執行 pop 之前檢查堆疊是否為空」。

解題方法

設目前掃描到的字元為 )：

1. 先檢查 stack 是否為空。
2. 若 stack 為空，表示沒有任何尚未配對的 (，因此目前的 ) 無法配對，屬於 unmatched closing parenthesis。
3. 若 stack 不為空，才執行 pop，將最近的 ( 配對掉。

例如字串：

$$s = "()"$$

掃描過程如下：

字元	動作	堆疊狀態
(	push	$[0]$
)	pop	$[]$

此時 pop 之後堆疊變空，只代表目前所有開括號都已配對完成，並不代表遇到了未配對的閉括號。

再看字串：

$$s = ")("$$

掃描第一個字元 ) 時，stack 一開始就是空的，因此該 ) 才是未配對的閉括號。

選項分析

(A) For every opening parenthesis, (, we push its index onto the stack

正確。

每遇到一個開括號 (，便將它的位置索引推入 stack，記錄尚未配對的開括號。例如掃描到索引 $i$ 的 (，執行：

核心觀念

本題考查「有效括號（valid parentheses）」與堆疊的應用。

若一段括號字串中的每個左括號 ( 都能依照正確順序與右括號 ) 配對，且配對過程中任一前綴的左括號數量不少於右括號數量，則稱該段括號為有效括號。

例如：

• ()：有效
• (())：有效
• ()()：有效
• )(：無效
• (()：無效

題目中的 funcB() 應是透過堆疊或索引記錄，判斷括號配對位置，並計算「最長有效括號子字串」的長度。這與單純判斷整個字串是否平衡不同。

---

解題方法

處理括號字串時，常見方法是使用堆疊記錄尚未配對的左括號位置，並搭配索引計算有效區段長度。

以字串：

$$()(()())$$

為例，程式會依序掃描每個字元：

1. 遇到 (：記錄其位置。
2. 遇到 )：嘗試與最近的 ( 配對。
3. 配對成功後，根據目前位置與有效區段起點，更新最長長度。
4. 若某個 ) 無法配對，表示有效括號區段被切斷，必須更新新的起點。

若程式的目的只是判斷括號是否平衡，通常只需在最後檢查堆疊是否為空；但題目選項中特別指出「maximum length」，表示函式還需要計算有效括號的最長長度，因此功能不只是平衡檢查。

例如輸入：

$$())()$$

其中最長有效括號子字串為 ()，長度為：

$$2$$

整個字串並非完全平衡，但仍然存在長度為 $2$ 的有效括號區段。因此，函式若能回傳這個最大長度，其功能就是尋找最長有效括號長度。

---

選項分析

(A) Find the length of the input string

錯誤。
若函式只要取得輸入字串長度，直接使用字串長度函式即可，不需要進行括號配對，也不需要使用堆疊或追蹤括號位置。

---

核心觀念

本題考查 QuickSort 的：

1. 分割（partition）方向
2. Pivot 的選取方式
3. 是否穩定（stable）
4. 是否原地排序（in-place）

程式中：

• pivot = v[left]，每次都選取目前子陣列最左側元素作為 pivot。
• i 從左向右尋找第一個 $\geq pivot$ 的元素。
• j 從右向左尋找第一個 $\leq pivot$ 的元素。
• 若 $i<j$，交換 v[i] 與 v[j]。
• 最後將 pivot 與 v[j] 交換，使 pivot 左側元素不大於它，右側元素不小於它。

因此，此版本 QuickSort 會將資料排序成**非遞減（由小到大）**順序。

---

解題方法：追蹤 Pivot

原始陣列為：

$$[12,2,16,30,8,28,4,10,20,6]$$

第一次呼叫：quicksort(V,0,9)

選取：

$$pivot=12$$

經過分割與交換後：

$$[8,2,6,10,12,4,28,30,20,16]$$

此時 pivot $12$ 位於索引 $4$，接著處理兩個子陣列：

• 左側：索引 $0\sim3$

$$[8,2,6,10]$$

• 右側：索引 $5\sim9$

$$[4,28,30,20,16]$$

---

左側子陣列：[8,2,6,10]

目前最左側元素為 $8$，因此：

$$pivot=8$$

所以 8 確實被當作 pivot 使用。

分割後可得到：

$$[6,2,8,10]$$

之後再遞迴處理左右子陣列。

---

右側子陣列：[4,28,30,20,16]

目前最左側元素為 $4$，因此先選：

$$pivot=4$$

分割後，右側剩下：

$$[28,30,20,16]$$

處理此子陣列時，最左側元素為 $28$，因此：

$$pivot=28$$

所以 28 也確實被當作 pivot 使用。

---

選項分析

(A) The quicksort() function sorts the given array in a non-increasing order.

錯誤。

程式中：

do i++; while (v[i] < pivot);
do j--; while (v[j] > pivot);

左側尋找大於等於 pivot 的元素，右側尋找小於等於 pivot 的元素，並將較小元素交換到左側、較大元素交換到右側。

因此排序結果是由小到大，即非遞減順序，不是由大到小的非遞增順序。

---

核心觀念

本題考查二元搜尋樹（BST）的大小關係，以及 AVL 樹的平衡條件。

節點高度是從該節點到最遠葉節點的邊數；葉節點高度為 $0$，空子節點高度為 $-1$。節點平衡值定義為：

$$\text{平衡值}=\text{左子樹高度}-\text{右子樹高度}$$

若每個節點的平衡值都在 $-1、0、1$ 之中，該樹符合高度平衡條件；若同時也是 BST，便是 AVL 樹。BST 則要求每個節點的左子樹鍵值都小於該節點，右子樹鍵值都大於該節點。

解題方法

依照原卷圖形，從葉節點往上逐層計算高度和平衡值。再分別檢查兩棵樹是否符合 BST 的大小關係。

Tree A

節點	高度	平衡值
$1,4,6,8,12$	$0$	$0$
$2$	$1$	$1$
$3$	$2$	$1$
$9$	$1$	$1$
$7$	$2$	$-1$
$11$	$1$	$-1$
$10$	$3$	$1$
$5$	$4$	$-1$

例如，節點 $7$ 的左子節點 $6$ 高度為 $0$，右子節點 $9$ 高度為 $1$，所以平衡值為 $0-1=-1$。Tree A 的所有節點平衡值皆為 $-1、0、1$。

Tree A 也符合 BST 順序：每個節點的左側鍵值都比該節點小，右側鍵值都比該節點大。因此 Tree A 是 AVL 樹。

Tree B

圖形結構
$V=\{V_0,V_1,V_2,V_3,V_4,V_5,V_6\}$
$E=\{V_0\!\to\!V_1,\;V_0\!\to\!V_3,\;V_1\!\to\!V_3,\;V_1\!\to\!V_4,\;V_2\!\to\!V_0,\;V_2\!\to\!V_3,\;V_2\!\to\!V_5,\;V_3\!\to\!V_2,\;V_3\!\to\!V_4,\;V_3\!\to\!V_5,\;V_3\!\to\!V_6,\;V_4\!\to\!V_6,\;V_5\!\to\!V_6,\;V_6\!\to\!V_4,\;V_6\!\to\!V_5\}$

---

(A) G 為有向無環圖 (DAG)

存在有向迴路，例如
$V_2\!\to\!V_0\!\to\!V_3\!\to\!V_2$ 以及 $V_4\!\to\!V_6\!\to\!V_4$。
因此 不為 DAG → 錯誤。

(B) BFS 從 $V_0$ 的訪問序列 $V_0,V_1,V_2,V_3,V_4,V_5,V_6$

從 $V_0$ 可直接到達的僅有 $V_1,V_3$。$V_2$ 必須在走訪完 $V_3$ 後才被發現。

本題考查開放定址法 (Open Addressing) 的雜湊表 (Hash Table) 操作，特別是二次探測法 (Quadratic Probing) 的碰撞解決。

雜湊表大小 $m = 9$。
雜湊函數 $h(k, i) = ((k \pmod m) + i^2) \pmod m$。
插入的鍵值序列：18, 16, 10, 7, 26。

我們逐步模擬插入過程：

1. 插入 18:

• $k = 18$。
• $i = 0$: $h(18, 0) = ((18 \pmod 9) + 0^2) \pmod 9 = (0 + 0) \pmod 9 = 0$。
• 位置 [0] 空，插入 18。
• Hash Table: [18, _, _, _, _, _, _, _, _]

2. 插入 16:

• $k = 16$。
• $i = 0$: $h(16, 0) = ((16 \pmod 9) + 0^2) \pmod 9 = (7 + 0) \pmod 9 = 7$。
• 位置 [7] 空，插入 16。
• Hash Table: [18, _, _, _, _, _, _, 16, _]

3. 插入 10:

• $k = 10$。
• $i = 0$: $h(10, 0) = ((10 \pmod 9) + 0^2) \pmod 9 = (1 + 0) \pmod 9 = 1$。
• 位置 [1] 空，插入 10。
• Hash Table: [18, 10, _, _, _, _, _, 16, _]

4. 插入 7:

• $k = 7$。
• $i = 0$: $h(7, 0) = ((7 \pmod 9) + 0^2) \pmod 9 = (7 + 0) \pmod 9 = 7$。
• 位置 [7] 已被 16 佔用。發生碰撞。
• $i = 1$: $h(7, 1) = ((7 \pmod 9) + 1^2) \pmod 9 = (7 + 1) \pmod 9 = 8$。
• 位置 [8] 空，插入 7。

核心觀念

本題考查遞迴函式的時間複雜度，關鍵在於：

• 每次呼叫會產生 兩個規模約為 $n/2$ 的子問題。
• 每次遞迴呼叫之外，還會執行一次加法與加上 $n$ 的運算，視為常數時間 $\Theta(1)$。
• 可利用遞迴式與 Master Theorem 分析。

令 $T(n)$ 表示 mystery(n) 的執行時間。

---

解題方法

當 $n \leq 1$ 時，函式直接回傳 $1$，因此：

$$T(n)=\Theta(1)$$

當 $n>1$ 時，函式執行兩次 mystery(n/2)，並進行常數次算術運算，因此：

$$T(n)=2T\left(\frac{n}{2}\right)+\Theta(1)$$

套用 Master Theorem 標準形式：

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

其中：

$$a=2,\qquad b=2,\qquad f(n)=\Theta(1)$$

計算比較基準：

$$n^{\log_b a} = n^{\log_2 2} = n$$

因此：

$$f(n)=\Theta(1)=O(n^{1-\varepsilon})$$

可視為 Master Theorem 的第一種情況，所以：

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

---

遞迴樹驗證

第 $0$ 層有 $1$ 個函式呼叫。

第 $1$ 層有 $2$ 個函式呼叫。

第 $2$ 層有 $2^2$ 個函式呼叫。

第 $k$ 層有：

$$2^k$$

個函式呼叫。

每次輸入規模減半，因此遞迴深度約為：

$$\log_2 n$$

最底層的函式呼叫數量約為：

$$2^{\log_2 n}=n$$

核心觀念

本題考查如何將有向加權圖的 adjacency list（鄰接串列）轉成圖形。每筆資料 $(v,w)$ 表示：由該列的節點出發，沿有向邊前往目標節點 $v$，邊權重為 $w$。

解題方法

原卷表格列出：$0$ 的鄰點為 $(1,4)$、$(2,1)$；$1$ 的鄰點為 $(3,1)$；$2$ 的鄰點為 $(1,2)$、$(3,5)$；$3$ 沒有鄰點。因此，圖中的邊依序為 $0\to1$（權重 $4$）、$0\to2$（權重 $1$）、$1\to3$（權重 $1$）、$2\to1$（權重 $2$）及 $2\to3$（權重 $5$）。

核心觀念

本題考加權有向圖的單源最短路徑。Dijkstra 演算法適用於邊權重皆為非負數的圖：每次從尚未確定的節點中，選出目前暫定距離最小者，確定其最短距離，再沿著該節點的出邊進行「鬆弛」，也就是檢查經過該節點能否縮短鄰點的距離。

解題方法

依原卷表格，圖中有向邊為 $0\to1$ 權重 $4$、$0\to2$ 權重 $1$、$1\to3$ 權重 $1$、$2\to1$ 權重 $2$、$2\to3$ 權重 $5$；節點 $3$ 沒有出邊。

以節點 $0$ 為起點，初始化 $d(0)=0$，其餘節點距離為 $\infty$。依序選取暫定距離最小的未確定節點並鬆弛其出邊：

步驟	確定節點	鬆弛結果	暫定距離 $(d(0),d(1),d(2),d(3))$
初始化	—	—	$(0,\infty,\infty,\infty)$
1	$0$	$d(1)=4,\ d(2)=1$	$(0,4,1,\infty)$
2	$2$	經 $2\to1$ 得 $1+2=3<4$，更新 $d(1)=3$；經 $2\to3$ 得 $1+5=6$，更新 $d(3)=6$	$(0,3,1,6)$
3	$1$	經 $1\to3$ 得 $3+1=4<6$，更新 $d(3)=4$	$(0,3,1,4)$