113 年 國立中山大學資訊管理學系碩士班乙組《資料結構》

核心觀念

最小生成樹（Minimum Spanning Tree, MST）是在連通加權無向圖中，連結所有頂點且不形成循環、總邊權重最小的生成樹。

Prim's algorithm 採用貪心法：

1. 先選定一個起始頂點，形成目前的樹集合 $S$。
2. 每次從連接 $S$ 與 $V-S$ 的候選邊中，選擇權重最小者。
3. 將該邊及其尚未加入的頂點納入樹中。
4. 重複上述步驟，直到所有頂點都加入。

關鍵操作是「快速找出目前候選邊中的最小權重」，因此適合使用以權重為鍵值的最小優先佇列（min-priority queue）。

解題方法

Prim's algorithm 每一步都必須處理跨越切割 $(S,V-S)$ 的候選邊，並執行：

$$\text{extract-min}$$

也就是取出權重最小的候選邊。

使用最小優先佇列後：

• 插入候選邊或更新鍵值：通常為 $O(\log V)$。
• 取出最小權重元素：通常為 $O(\log V)$。
• 使用二元堆實作時，整體複雜度常為：

$$O((V+E)\log V)$$

相較於每次在線性資料結構中搜尋最小邊，優先佇列能有效降低搜尋成本。因此正確選項是 priority queue。

選項分析

• A. set

  set 可用來記錄哪些頂點已經加入目前的生成樹，避免重複加入頂點或形成錯誤連結。然而，單純的集合主要提供成員資格判斷，無法直接有效率地找出權重最小的候選邊，因此不是本題所問的主要效率工具。

概念快速檢核

• Heap vs. BST：Heap 只保證父節點鍵 $\ge$（或 $\le$）其子節點，與二元搜尋樹的左<根<右 完全不同，亦非自平衡樹。
• Max‑heap 方向：父鍵 不小於 子鍵；若父鍵較小則違反定義。
• d‑ary heap 刪除最大：將最後一個葉節點搬至根，再向下「heapify」。每層需在 $d$ 個子中找最大，費 $O(d)$；

核心觀念

本題考查遞迴關係式的展開，以及幾何級數的漸近分析。

每次遞迴：

• 問題規模由 $n$ 降為 $n/2$；
• 當層額外花費為 $n$；
• 遞迴終止條件為 $T(1)=1$。

遞迴深度為 $\log_2 n$，但每層的工作量會依序減半，因此總成本不能只用「層數 $\times$ 每層成本」估算。

解題方法：逐層展開

假設 $n=2^k$，因此 $k=\log_2 n$。

$$\begin{aligned} T(n) &=T(n/2)+n\\ &=T(n/4)+\frac n2+n\\ &=T(n/8)+\frac n4+\frac n2+n\\ &=\cdots\\ &=T(1)+n+\frac n2+\frac n4+\cdots+\frac{n}{2^{k-1}}. \end{aligned}$$

這是一個首項為 $n$、公比為 $1/2$ 的幾何級數：

$$\begin{aligned} T(n) &=1+\sum_{i=0}^{k-1}\frac{n}{2^i}\\ &=1+n\cdot\frac{1-(1/2)^k}{1-1/2}. \end{aligned}$$

由於 $n=2^k$，所以 $(1/2)^k=1/n$：

$$\begin{aligned} T(n) &=1+2n\left(1-\frac1n\right)\\ &=2n-1. \end{aligned}$$

因此：

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

其最緊確上界為 $O(n)$。

選項分析

Hoare partition（基於 pivot = 7）流程

1. 初始指標：i = -1、j = 10（陣列長度 10）。
2. 重複以下直到 i ≥ j：
   • i ← i+1　直到 A[i] ≥ 7。
   • j ← j-1　直到 A[j] ≤ 7。
   • 若 i < j，交換 A[i] 與 A[j]。

迭代	i 變化	j 變化	交換元素	交換後陣列
1	i=0 (7 ≥7)	j=9 (6 ≤7)	7 ↔ 6	6 5 10 11 3 9 2 4 8 7

核心觀念

本題考查演算法設計策略中的「貪婪法（Greedy Method）」。

貪婪法的特徵是：在每一步都選擇當下看來最有利的可行選擇，且通常不回溯；若該問題具有貪婪選擇性質，這些局部最佳選擇能組合成全域最佳解。

最小生成樹問題具有「割集合定理（Cut Property）」：

對圖中任意一個割集合，跨越該割集合的最小權重邊，必定是某棵最小生成樹中的安全邊。

Prim's algorithm 正是反覆利用此性質選擇邊，因此具有貪婪特徵。

解題方法

判斷各選項所屬的主要演算法策略：

• Binary search：分治式搜尋
• Merge sort：分治法
• Quicksort：分治法
• Floyd-Warshall：動態規劃
• Prim's algorithm：貪婪法

Prim's algorithm 的流程如下：

1. 先選定一個起點，令已加入樹的頂點集合為 $S$。
2. 從所有一端在 $S$、另一端在 $V-S$ 的邊中，選擇權重最小者。
3. 將該邊及其新頂點加入目前的生成樹。
4. 重複上述步驟，直到所有頂點都被加入。

每一步都選擇「目前跨越割集合 $(S,V-S)$ 的最小權重邊」，這正是局部最佳選擇。根據割集合定理，此邊是安全的，能保證最終形成最小生成樹。

選項分析

A. Binary search

錯誤。

Binary search 用於已排序的資料。每次檢查中間元素，依比較結果捨棄左半部或右半部，使搜尋範圍縮小為原來的一半。

其核心是利用排序性質進行分治搜尋，時間複雜度為

$$T(n)=T(n/2)+O(1)=O(\log n)$$

中間元素並不是根據「目前解中最有利的選擇」來建構最佳解，因此 Binary search 不屬於貪婪法。

B. Merge sort

錯誤。

Merge sort 先將資料遞迴切成兩半，分別排序後，再將兩個已排序的子序列合併。

其遞迴式為

$$T(n)=2T(n/2)+O(n)$$

因此時間複雜度為

$$O(n\log n)$$

它的核心是分割問題、解決子問題，再合併結果，屬於分治法，不是貪婪法。

核心觀念

Binary search（二分搜尋）適用於已排序的資料。每次取目前搜尋範圍的中間元素，將其與目標值比較：

• 相等：搜尋成功。
• 目標值較小：只搜尋左半部。
• 目標值較大：只搜尋右半部。

每次比較都會使搜尋範圍約縮小為原來的一半，因此時間複雜度為：

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

以陣列的迭代式實作而言，額外空間複雜度為 $O(1)$；若使用遞迴，則遞迴堆疊為 $O(\log n)$。

解題方法

判斷各選項是否符合二分搜尋的三個特徵：

1. 資料必須先排序。
2. 每次比較中間位置的元素。
3. 每次排除約一半的搜尋範圍。

符合「資料必須排序」的選項即為正確答案。

選項分析

A. Binary search has a time complexity of O(n).

錯誤。

二分搜尋每次將搜尋範圍縮小一半，最多需要約 $\log_2 n$ 次比較，因此時間複雜度為：

$$O(\log n)$$

$O(n)$ 是線性搜尋在最壞情況下的時間複雜度，不是二分搜尋的典型複雜度。二分搜尋在目標值恰好位於第一次檢查的中間位置時，最佳情況為 $O(1)$。

B. Binary search has a space complexity of O(n).

錯誤。

以陣列進行迭代式二分搜尋時，只需維護搜尋邊界，例如 left、right 與 mid，所以額外空間複雜度為：

$$O(1)$$

核心觀念

Breadth First Search（BFS，廣度優先搜尋）是按照「距離起點的層數」逐層拜訪圖中的頂點：

1. 先拜訪起點。
2. 再拜訪起點的所有鄰接頂點。
3. 接著拜訪距離起點兩條邊的頂點。
4. 依此類推。

為了維持「先發現的頂點先處理」的順序，BFS 使用 Queue（佇列）。佇列遵循 FIFO（First In, First Out，先進先出）原則，正好符合廣度優先的拜訪順序。

解題方法

BFS 的基本流程如下：

BFS(G, s):
    建立空佇列 Q
    將起點 s 標記為已拜訪
    enqueue(Q, s)

    while Q 不為空:
        u = dequeue(Q)
        for each u 的鄰接頂點 v:
            if v 尚未拜訪:
                將 v 標記為已拜訪
                enqueue(Q, v)

假設起點為 $s$，且 $s$ 的鄰接頂點依序為 $a,b$：

• 初始佇列：$[s]$
• 移除 $s$，加入 $a,b$：$[a,b]$
• 移除 $a$，加入 $a$ 尚未拜訪的鄰點：$[b,\ldots]$
• 移除 $b$，再處理 $b$ 的鄰點

由於 $a$ 比後來發現的頂點更早進入佇列，因此會先被處理，這能確保 BFS 逐層搜尋。

若使用鄰接串列表示圖，BFS 的時間複雜度為：

核心觀念

本題考查雜湊表（hash table）的線性探測法（linear probing）。

表格大小為 $7$，因此索引位置為 $0$ 到 $6$。雜湊函數為：

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

若計算出的槽位已被占用，線性探測會依序檢查下一格：

$$h(k),\ h(k)+1,\ h(k)+2,\ldots$$

索引超過 $6$ 時須從 $0$ 繼續循環。

解題方法

依照題目給定的插入順序，逐一計算雜湊位置並處理碰撞。

插入鍵值	雜湊值	探測過程	最終位置
$5$	$5\bmod 7=5$	位置 $5$ 為空	$5$
$9$	$9\bmod 7=2$	位置 $2$ 為空	$2$
$2$	$2\bmod 7=2$	位置 $2$ 已有 $9$，探測位置 $3$	$3$
$0$	$0\bmod 7=0$	位置 $0$ 為空	$0$
$21$	$21\bmod 7=0$	位置 $0$ 已有 $0$，探測位置 $1$	$1$
$14$	$14\bmod 7=0$	位置 $0,1,2,3$ 均已占用，位置 $4$ 為空	$4$

因此最後的雜湊表為：

核心觀念

完全二元樹（complete binary tree）的定義是：

• 除了最底層之外，其餘各層都必須填滿。
• 最底層的節點必須由左至右連續排列。

本題採用根節點為第 $1$ 層的高度定義。若高度為 $h$，則節點數滿足：

$$2^{h-1}\le n\le 2^h-1$$

因此：

$$h=\lfloor\log_2 n\rfloor+1$$

選項中的 $\log n+1$ 是省略取整數符號後的常用寫法，其中 $\log$ 以 $2$ 為底。

解題方法

利用完全二元樹的層數與節點數關係判斷：

• 高度為 $h$ 時，前 $h-1$ 層已經完全填滿，因此至少有 $2^{h-1}$ 個節點。
• 高度為 $h$ 時，最多有 $2^h-1$ 個節點。
• 解得高度為 $\lfloor\log_2 n\rfloor+1$，符合選項 A。

例如 $n=10$ 時：

核心觀念

無向圖是二分圖，表示頂點可以分成兩組，使每條邊的兩端都分屬不同組。等價地，無向圖是二分圖若且唯若不含奇數長度的環。

圖中有三角形 $B-C-D-B$，也有環 $B-C-F-E-B$。刪除邊後，必須確認所有奇數環都已消失。

解題方法

逐一檢查選項是否能消除圖中的奇數環：

• 刪除三角形中的一條邊，只能破壞三角形；還要確認是否留下其他奇數環。
• 若刪除 $B-D$，頂點可分成兩組：$\{B,D,F\}$ 與 $\{A,C,E\}$。圖上的每條邊都連接兩組，因此刪除後是二分圖。

選項分析

核心觀念

二元樹的葉節點數可由「根節點是否為葉節點」與「左右子樹的葉節點數」組成：

$$L(T)=L(T.Left)+L(T.Right)+Leaf(T)$$

其中：

• 若 $T$ 為葉節點，則 $Leaf(T)=1$。
• 若 $T$ 不是葉節點，則 $Leaf(T)=0$。
• 空子樹的葉節點數定義為 $L(NULL)=0$。

因此，當根節點是葉節點時，左右子樹皆為空：

$$L(T)=0+0+1=1$$

當根節點不是葉節點時：

$$L(T)=L(T.Left)+L(T.Right)+0$$

正好等於左右子樹葉節點數的總和。

解題方法

採用「根節點分類」判斷遞迴式：

1. 若根節點 $T$ 是葉節點，答案必須為 $1$。
2. 若根節點 $T$ 不是葉節點，答案應為左右子樹葉節點數之和。
3. 將兩種情況合併，便是在左右子樹遞迴結果之外，加上 $Leaf(T)$。

所以正確遞迴定義為：

$$L(T)= \begin{cases} 0, & T=NULL\\ L(T.Left)+L(T.Right)+Leaf(T), & T\neq NULL \end{cases}$$

選項分析

• A. $L(T):=L(T.Left)+L(T.Right)+Leaf(T)$

  正確。根節點為葉節點時，$Leaf(T)=1$；根節點為內部節點時，$Leaf(T)=0$，完整涵蓋兩種情況。

核心觀念

本題考查「鏈結串列適合使用哪一種排序法」以及比較排序的時間複雜度下限。

設鏈結串列共有 $n$ 個節點，且資料排列為隨機、未排序狀態。對於比較排序而言，必須區分至少 $n!$ 種可能的排列，因此決策樹高度至少為：

$$\log_2(n!)=\Theta(n\log n)$$

所以比較排序在一般情況下的最佳漸進時間複雜度為：

$$\Omega(n\log n)$$

能穩定達到此下限的排序法，才可視為具有最佳時間複雜度。

鏈結串列不支援陣列的隨機存取，無法在 $O(1)$ 時間內取得第 $i$ 個元素。因此，適合鏈結串列的排序法應盡量避免大量的索引存取與元素搬移。

解題方法

Merge Sort 的流程如下：

1. 將鏈結串列分割成兩半。
2. 分別遞迴排序左右兩個子串列。
3. 將兩個已排序的鏈結串列合併。

對鏈結串列而言，可以使用慢指標與快指標找出中點，並以重新連接節點指標的方式完成分割。每一層分割總共需要掃描 $O(n)$ 個節點。

合併兩個已排序鏈結串列時，只需比較兩個串列目前的首節點，將較小者接到結果串列尾端。每個節點只會被處理一次，因此合併成本為 $O(n)$。

其遞迴式為：

$$T(n)=2T\left(\frac n2\right)+O(n)$$

由主定理可得：

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

此複雜度達到比較排序的理論下限，且不需要對鏈結串列進行大量隨機存取，因此 Merge Sort 是本題最佳選擇。

選項分析

A. Insertion Sort

Insertion Sort 依序取出元素，插入前面已排序的部分。

隨機排列平均具有 $\Theta(n^2)$ 個數量級的逆序關係。即使鏈結串列在找到插入位置後只需調整指標，尋找插入位置仍可能需要逐節點掃描，因此平均與最壞時間複雜度皆為：

$$\Theta(n^2)$$

已排序輸入的最佳情況可達 $O(n)$，但題目指定的是隨機、未排序的鏈結串列，因此不是最佳答案。

B. Quick Sort

Quick Sort 每次選擇樞紐值進行分割。

若每次分割都接近左右各半，遞迴式為：

$$T(n)=2T\left(\frac n2\right)+O(n)$$

此時可達到 $\Theta(n\log n)$。然而，若樞紐值經常落在最小值或最大值附近，遞迴式會變成：

核心觀念

本題考查加權圖的全點對最短路徑問題（All-Pairs Shortest Paths, APSP）：計算任意頂點 $i$ 到任意頂點 $j$ 的最短距離，共有 $n^2$ 組距離需要求得。

對一般加權圖，最經典且穩定的解法是 Floyd–Warshall 演算法。令

• $D^{(k)}[i][j]$：只允許頂點 $1,2,\ldots,k$ 作為中繼點時，$i$ 到 $j$ 的最短距離。
• 初始狀態：

$$D^{(0)}[i][j]= \begin{cases} 0, & i=j\\ w(i,j), & i,j\text{ 之間有邊}\\ \infty, & \text{沒有直接邊} \end{cases}$$

加入第 $k$ 個中繼點時，最短路徑只有兩種情況：

1. 不經過 $k$；
2. 經過 $k$，分成 $i\to k$ 與 $k\to j$ 兩段。

因此遞迴式為

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

解題方法

Floyd–Warshall 需要枚舉：

• 中繼點 $k$：$n$ 種；
• 起點 $i$：$n$ 種；
• 終點 $j$：$n$ 種。

每次只進行常數時間的加法與比較，因此總時間複雜度為

$$O(n)\times O(n)\times O(n)=O(n^3)$$

其核心程式結構如下：

for k = 1 to n:
    for i = 1 to n:
        for j = 1 to n:
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

核心觀念

本題考查隨機圖中三角形（長度為 3 的無向環）之期望值。

在 8 個頂點的無向圖中，每 3 個頂點若其間的 3 條邊全部存在，就形成一個三角形。由於題目強調是 unordered cycles，同一組 3 個頂點只計算一次。

使用期望值的線性性：

$$E[X]=\sum E[I_i]$$

其中 $I_i$ 表示某一組頂點是否形成三角形。

解題方法

先選出形成三角形的 3 個頂點：

$$\binom{8}{3}=56$$

固定任意 3 個頂點後，三者之間共有 3 條可能的邊。要形成三角形，這 3 條邊必須全部存在；每條邊存在的機率為 $0.5$，因此：

$$P(\text{固定三點形成三角形}) =(0.5)^3 =\frac{1}{8}$$

故三角形數量的期望值為：

$$E[X] =\binom{8}{3}(0.5)^3 =56\cdot\frac{1}{8} =7$$

因此正確選項為 D。

選項分析

• A. $\frac{1}{8}$：錯誤。
  $\frac{1}{8}$ 是固定一組 3 個頂點形成三角形的機率，不是整張圖中三角形數量的期望值。

核心觀念

本題考查最大堆積（max-heap）的結構與插入操作。

1. 最大堆積必須符合：每個父節點的值皆大於或等於其子節點。
2. 完整二元樹以陣列儲存時，level-order traversal 就是陣列順序。
3. 採用 $1$ 起始索引時：

$$\text{parent}(i)=\left\lfloor \frac{i}{2}\right\rfloor$$

新紀錄必須先放在下一個可用位置，再沿著父節點向上比較；若新值大於父節點，就交換，此過程稱為上浮（percolate up）。

---

解題方法

原始堆積的陣列為：

$$[10,8,5,3,2]$$

其結構為：

        10
       /  \
      8    5
     / \  \
    3   2

第一次插入 $1$

新節點放在第 $6$ 個位置，也就是節點 $5$ 的左子節點：

$$[10,8,5,3,2,1]$$

因為：

$$1<5$$

不需上浮，堆積維持不變。

第二次插入 $7$

新節點放在第 $7$ 個位置，也就是節點 $5$ 的右子節點：

$$[10,8,5,3,2,1,7]$$

比較 $7$ 與父節點 $5$：

$$7>5$$

因此交換兩者：

$$[10,8,7,3,2,1,5]$$

接著比較 $7$ 與其新父節點 $10$：

$$7<10$$

停止上浮。因此最後的 level-order traversal 為：

$$10,8,7,3,2,1,5$$

---

選項分析

核心觀念

本題考查：

• Adjacency list（鄰接串列）表示法
• 無向圖中每條邊會在兩個端點的鄰接串列各出現一次
• 握手定理（Handshaking Lemma）：

$$\sum_{v\in V}\deg(v)=2|E|$$

其中 $\deg(v)$ 是頂點 $v$ 的度數，$|E|$ 是邊數。

---

解題方法

對每個頂點 $x$，內層迴圈會逐一走訪其鄰接串列中的所有頂點 $y$：

for (auto x : edges) {
    for (auto y : x) {
        count += 1;
    }
}

因此：

$$\texttt{count} = \sum_{v\in V}\deg(v)$$

對無向圖而言，每條邊會被計數兩次。例如邊 $(u,v)$ 會在 $u$ 的鄰接串列出現一次，也會在 $v$ 的鄰接串列出現一次，所以：

$$\texttt{count}=2|E|$$

最後輸出：

cout << count / 2 << endl;

得到：

$$\frac{\texttt{count}}{2} = \frac{2|E|}{2} = |E|$$

所以此程序計算的是無向圖的邊數。

例如，若圖有兩條邊：

0: 1, 2
1: 0
2: 0

所有鄰接串列共有 $4$ 個項目，count = 4，輸出 $4/2=2$，正好是邊數。

---

選項分析

• A. Calculate the number of edges in an undirected graph.

  正確。無向圖中每條邊在鄰接串列出現兩次，count / 2 即為邊數。

核心觀念

本題考查無權圖的廣度優先搜尋（Breadth-First Search, BFS）與最短路徑距離。

在無權圖中，每條邊的成本皆為 $1$，因此從起點 $r$ 到頂點 $x$ 的最短距離 $d(r,x)$，就是最短路徑所包含的邊數。

BFS 會依照距離分層搜尋：

$$L_k=\{x\mid d(r,x)=k\}$$

搜尋順序必定是先處理 $L_0$，再處理 $L_1$、$L_2$，依此類推。同一層中的頂點，先後順序則取決於鄰接串列順序。

因此，BFS 的重要性質為：

$$u\text{ 在 }v\text{ 之前被訪問}\quad\Longrightarrow\quad d(r,u)\le d(r,v)$$

解題方法

BFS 使用先進先出（FIFO）的佇列：

1. 先訪問起點 $r$，其距離為 $0$。
2. 訪問 $r$ 的所有未訪問鄰居，這些頂點距離為 $1$。
3. 再依序訪問距離為 $1$ 的頂點，找出距離為 $2$ 的頂點。
4. 持續按照距離由小到大的順序處理。

所以，若 $u$ 在 $v$ 之前被訪問，$u$ 不可能比 $v$ 距離起點更遠，只能是：

• $d(r,u)<d(r,v)$：$u$ 比 $v$ 更接近 $r$；
• $d(r,u)=d(r,v)$：$u$ 與 $v$ 位於同一層。

綜合可得：

$$d(r,u)\le d(r,v)$$

先將頻率由小至大排列：$Q5,\;T10,\;S12,\;R13,\;P20$

1. 合併最小的兩個：$Q5+T10=15$ → 節點 $A$
2. 再合併次小的兩個：$S12+R13=25$ → 節點 $B$
3. 合併 $A15$ 與 $P20$：$15+20=35$ → 節點 $C$
4. 最後合併 $B25$ 與 $C35$ 成根節點，總頻率 $60$

從根開始計算葉節點深度（即編碼長度）：

• 根的左子樹 $B$，其子節點 $S,R$ 深度 $2$ → 編碼長度 $2$。
• 根的右子樹 $C$，其子節點 $P$ 深度 $2$ → 編碼長度 $2$。

核心觀念

本題考查單向鏈結串列（singly linked list）的指標操作與時間複雜度。

已知條件：

• 只有 head 指標，沒有 tail 指標。
• 每個節點只能沿著 next 往後走，不能由後往前走。
• 串列未排序，因此尋找最小值不能提早結束。
• 正式的 Big-O 表示「最多為此成長階」，所以 $O(1)$ 也屬於 $O(n)$，因為：

$$O(1)\subseteq O(n)$$

因此，題目問「能否實作成 $O(n)$」，時間為 $O(1)$ 的操作也符合條件。

解題方法

逐一判斷每個操作需要：

1. 是否必須走訪節點；
2. 最多走訪幾個節點；
3. 是否只需修改固定數量的指標。

只走訪固定數量節點是 $O(1)$；最多走訪整條串列一次是 $O(n)$。

選項分析

A. Deleting the first node：正確

刪除第一個節點只需將 head 移到下一個節點：

$$\text{head} \leftarrow \text{head.next}$$

只需執行固定數量的指標操作，因此實際複雜度為：

$$O(1)$$

而 $O(1)$ 屬於 $O(n)$，所以本選項符合題意。

B. Deleting the last node：正確

單向鏈結串列要刪除最後一個節點，必須找到倒數第二個節點，將其 next 設為 null。

例如：

previous.next = null

但只有 head 指標，且無法向前移動，因此必須從串列開頭逐節點走訪，直到找到最後一個節點及其前驅節點。最多需要走訪 $n$ 個節點：

$$T(n)=O(n)$$

所以本選項正確。

C. Inserting an item at the front：正確

在串列前端插入新節點，只需：

核心觀念

Merge sort（合併排序）採用分治法（divide and conquer）：

1. Divide：將資料分成兩半。
2. Conquer：遞迴地將左右兩半排序。
3. Combine：將兩個已排序的子序列合併。

其時間複雜度可由遞迴式表示：

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

其中 $\Theta(n)$ 是合併兩個子序列所需的時間。依主定理可得：

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

因此，標準 merge sort 的最佳、平均與最壞情況時間複雜度皆為 $\Theta(n\log n)$。

解題方法

逐一依照 merge sort 的核心特性判斷：

• 是否使用分治策略？
• 是否需要額外記憶體？
• 最佳情況是否仍需處理各層合併？
• 是否屬於 in-place sorting？
• $O(n\log n)$ 是否適合大型資料集？

選項分析

A. It uses a divide-and-conquer strategy to sort the elements.

正確。Merge sort 先將序列不斷分割成較小的子序列，再遞迴排序，最後逐層合併，因此是典型的分治演算法。

B. It has a space complexity of O(1).

錯誤。標準陣列版 merge sort 在合併時通常需要額外的暫存陣列，儲存量為 $O(n)$；遞迴呼叫堆疊另需 $O(\log n)$。

因此總額外空間複雜度為：

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

先以先序與中序建立二元樹。
先序：$10\;1\;5\;2\;7\;19\;12\;15\;20$
中序：$1\;2\;5\;7\;10\;12\;15\;19\;20$

1. 根節點 $10$（先序第一個）。
   • 左子樹的中序為 $1\;2\;5\;7$，對應先序 $1\;5\;2\;7$。
     • 根 $1$，右子樹中序 $2\;5\;7$、先序 $5\;2\;7$。
       • 根 $5$，左子 $2$，右子 $7$。
   • 右子樹的中序為 $12\;15\;19\;20$，對應先序 $19\;12\;15\;20$。
     • 根 $19$，左子樹中序 $12\;15$、先序 $12\;15$ → 根 $12$，右子 $15$。
     • 右子 $20$。

得到的樹如圖（省略圖形），最高路徑為
$10 \rightarrow 1 \rightarrow 5 \rightarrow 2$（或

核心觀念

本題比較三種常見演算法設計方法與遞迴的關係，並考察拓撲排序的時間複雜度。

• Backtracking（回溯法）：逐步建立解答，遇到不符合條件時撤銷選擇，通常以遞迴搜尋狀態樹。
• Divide and conquer（分治法）：將問題分割成較小的同類型子問題，遞迴解決後再合併結果。
• Dynamic programming（動態規劃）：利用最佳子結構與重疊子問題，儲存已計算結果以避免重複計算；可採遞迴，也可採迭代。
• Topological sort（拓撲排序）：對有向無環圖排序，使每條邊 $u\to v$ 中，$u$ 都排在 $v$ 之前。

解題方法

判斷前面三個選項時，關鍵是辨認「遞迴是否為該方法的核心典型特徵」，以及該敘述是否宣稱「必然」使用遞迴。

判斷拓撲排序時，直接計算其標準演算法的時間複雜度。使用鄰接串列時，頂點與邊各只需處理有限次，因此可達到

$$O(|V|+|E|)$$

這就是相對於輸入大小的線性時間。

選項分析

A. Backtracking invokes recursion.

正確。

回溯法通常以遞迴實作。每一層遞迴代表做出一個選擇，遞迴深入下一個狀態；若該選擇導致無解，便撤銷選擇並嘗試其他分支。

例如排列問題的概念流程如下：

1. 選擇一個尚未使用的元素。
2. 遞迴處理下一個位置。
3. 遞迴返回後取消該元素的使用狀態。

因此，回溯法的搜尋結構本質上是一棵狀態樹，遞迴是其標準實作方式。即使實際程式改用明確的堆疊模擬，仍然是在模擬遞迴搜尋。

B. Divide and conquer invokes recursion.

正確。

分治法的標準流程是：

1. 將原問題分割為較小的同類型子問題。
2. 遞迴解決各子問題。
3. 合併子問題的解答。

例如合併排序的時間複雜度滿足

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

其中 $2T(n/2)$ 表示遞迴處理兩個子陣列，$O(n)$ 表示合併成本，因此

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

分治法可用非遞迴程式碼模擬，但其設計概念是透過遞迴逐層分割問題，所以本選項正確。

概念

• 連通簡單圖（無迴路、無重邊）之最少邊數為生成樹的邊數：
  $e_{\min}=v-1$
• 最大邊數為完全圖：
  $e_{\max}= \frac{v(v-1)}{2}$

判斷

A. $e\le 1$
 不一定；若 $v\ge3$ 必須至少 $e=v-1\ge2$。✗

B. $e\ge v-1$
 由生成樹的下界直接得出。✅

圖形資訊
頂點 $V=\{v_0,\dots ,v_6\}$，有向邊與權重

邊	權重
$(v_0,v_2)$	4
$(v_1,v_0)$	2
$(v_1,v_3)$	3
$(v_3,v_0)$	1
$(v_3,v_2)$	2
$(v_3,v_5)$	8
$(v_3,v_6)$	4
$(v_4,v_1)$	10
$(v_4,v_3)$	2
$(v_4,v_6)$	7
$(v_5,v_2)$	2
$(v_6,v_5)$	1

---

A. 從 $v_4$ 到 $v_5$ 的最短加權路徑長度為 7

可能的路徑

• $v_4\!\to\!v_3\!\to\!v_6\!\to\!v_5$：$2+4+1=7$
• $v_4\!\to\!v_6\!\to\!v_5$：$7+1=8$
• $v_4\!\to\!v_3\!\to\!v_5$：$2+8=10$

最小為 $7$，故 A 為真。

---

B. 以標準 Dijkstra 演算法（從 $v_4$）最後被「確定」的頂點是 $v_1$

Dijkstra 步驟（距離 $d$）：

取出	更新後 $d$
$v_4\;(0)$	$d(v_1)=10,\;d(v_3)=2,\;d(v_6)=7$

核心觀念

本題考查二元樹的三種走訪方式，以及樹高的定義。

樹的結構如下：

        A
       / \
      B   C
     / \
    D   E

三種走訪規則：

• Level order（層序走訪）：由上到下、由左到右，通常使用佇列。
• Preorder（前序走訪）：根 → 左子樹 → 右子樹。
• Inorder（中序走訪）：左子樹 → 根 → 右子樹。

本題採常見考試定義：根節點位於第 1 層，樹高等於最深層數，也就是最長根葉路徑上的節點數。

解題方法

先依樹的層次列出節點：

• 第 1 層：$A$
• 第 2 層：$B, C$
• 第 3 層：$D, E$

因此可直接推得層序走訪。

再依照根、左子樹、右子樹的順序，分別進行前序與中序走訪：

前序：

$$A \rightarrow B \rightarrow D \rightarrow E \rightarrow C$$

所以結果為：

$$\text{ABDEC}$$

中序時，先走訪 $B$ 的左子樹 $D$，再訪問 $B$，接著訪問 $B$ 的右子樹 $E$；完成左子樹後訪問根 $A$，最後訪問右子樹 $C$：

$$D \rightarrow B \rightarrow E \rightarrow A \rightarrow C$$

所以結果為：

$$\text{DBEAC}$$

選項分析

A. The level order traversal of the tree is ABCDE

正確。

層序走訪依照「由上到下、同層由左到右」的順序：

$$A \rightarrow B \rightarrow C \rightarrow D \rightarrow E$$

因此層序走訪為 ABCDE。

B. The inorder traversal of the tree is DBEAC

正確。