107 地方特考三等 資訊處理 資料結構 考古題詳解

核心觀念

本題考查計算機科學與離散數學中經典的歐幾里得演算法（輾轉相除法，Euclidean Algorithm）​之正確性與時間複雜度分析，核心涉及以下四項重要觀念與定理：

1. 除法原理（Division Algorithm）：對任意整數 $x$ 與正整數 $y$，存在唯一整數商 $q$ 與餘數 $r$，使得 $x = qy + r$，且餘數滿足 $0 \le r < y$。在程式語言中，$r = x \mathbin{\%} y$。
2. 良序原理（Well-Ordering Principle）：非負整數集合的任意非空子集必有最小元素。若一組非負整數序列嚴格遞減，則其長度必為有限，此乃證明迴圈終止性（Termination）的基本工具。
3. 餘數減半引理（Modulo Halving Lemma）：若 $X \ge Y > 0$，則 $X \mathbin{\%} Y < \frac{X}{2}$。此幾何級數縮減特性是歐幾里得演算法具備對數級時間複雜度 $\mathcal{O}(\log b)$ 的核心數學基礎。
4. 狀態遞迴與分情況討論：追蹤迴圈每回合變數的轉移，利用奇數步與偶數步的嚴格不等式，精確推導出迴圈執行的上限次數。

---

解題方法

（一）證明演算法必於有限時間內停止（不會有無窮迴圈）

切入點：定義迴圈狀態序列，證明控制變數 $y$ 為「嚴格遞減且具有下界的非負整數序列」。

1. 定義變數狀態： 設程式輸入任意正整數 $a, b > 0$。進入 while 迴圈前，初始狀態為： $x_1 = a, \quad y_1 = b$ 若迴圈執行第 $k$ 次（$k \ge 1$），設進入該次迴圈時的變數值為 $x_k$ 與 $y_k$。
2. 單步狀態轉移： 依程式第 3 行邏輯： $r_k = x_k \mathbin{\%} y_k, \quad x_{k+1} = y_k, \quad y_{k+1} = r_k$ 因為迴圈進入條件為 $y_k > 0$，根據整數除法原理，餘數 $r_k$ 必定滿足： $0 \le r_k < y_k$ 因此，下一輪的控制變數 $y_{k+1}$ 滿足： $0 \le y_{k+1} < y_k$
3. 終止性推論： 序列 $\{y_k\}$ 是一組由正整數出發的嚴格遞減非負整數序列： $b = y_1 > y_2 > y_3 > \dots \ge 0$ 由於 $y_1 = b$，且每次迭代至少減少 $1$（即 $y_{k+1} \le y_k - 1$），根據整數的良序原理，$y_k$ 不可能無限遞減，至多經過 $b$ 次迭代後必有某個整數步 $m$ 使得 $y_{m+1} = 0$。 當 $y = 0$ 時，迴圈判斷條件 y > 0 為偽（False），迴圈即刻跳出並執行 return x; 終止程式。 得證：輸入任意兩正整數，此程式必在有限步後停止，絕不會造成無窮迴圈。

---

（二）證明若 $a > b$，while 迴圈至多執行 $2\log_2 b + 1$ 次

切入點：先建立「兩次迭代後變數規模至少減半」的重要引理，再針對迴圈總執行次數的奇偶性進行分類證明。

【引理】若整數 $X \ge Y > 0$，則 $X \mathbin{\%} Y < \frac{X}{2}$。

證明： 設 $R = X \mathbin{\%} Y$。依除法原理，存在整數商 $q \ge 1$ 使得 $X = qY + R$，其中 $0 \le R < Y$。

• 狀況一：若 $Y \le \frac{X}{2}$，因 $R < Y$，故顯然有 $R < \frac{X}{2}$。
• 狀況二：若 $Y > \frac{X}{2}$，則商數 $q = \left\lfloor \frac{X}{Y} \right\rfloor = 1$（因為若 $q \ge 2$，則 $X \ge 2Y > X$，矛盾）。 此時 $X = 1 \cdot Y + R \implies R = X - Y$。 因為 $Y > \frac{X}{2}$，所以 $-Y < -\frac{X}{2}$，得： $R = X - Y < X - \frac{X}{2} = \frac{X}{2}$ 綜合以上兩種狀況，對任意整數 $X \ge Y > 0$，恆有 $X \mathbin{\%} Y < \frac{X}{2}$，引理成立。

---

【主證明】

1. 變數跨步收縮關係： 已知初始 $a > b > 0$，$x_1 = a, y_1 = b$。

• 第 1 次執行完畢後：$x_2 = y_1 = b$，$y_2 = x_1 \mathbin{\%} y_1 = a \mathbin{\%} b < b$。
• 第 2 次執行完畢後：$x_3 = y_2$，$y_3 = x_2 \mathbin{\%} y_2 = y_1 \mathbin{\%} y_2 = b \mathbin{\%} y_2$。 因為 $b > y_2 > 0$，由引理可知： $y_3 = b \mathbin{\%} y_2 < \frac{b}{2} = \frac{y_1}{2}$ 同理，對任意整數 $k \ge 1$，在第 $k+1$ 次迭代中：$x_{k+2} = y_{k+1}$ 且 $y_{k+2} = x_{k+1} \mathbin{\%} y_{k+1} = y_k \mathbin{\%} y_{k+1}$。 因為 $y_k > y_{k+1} > 0$，套用引理可得： $y_{k+2} < \frac{y_k}{2}$ 由此遞迴關係，特別觀察奇數項： $y_3 < \frac{y_1}{2} = \frac{b}{2^1}, \quad y_5 < \frac{y_3}{2} < \frac{b}{2^2}, \quad \dots, \quad y_{2k+1} < \frac{b}{2^k} \quad (\forall k \ge 0)$

核心觀念

1. 割性質（Cut Property）與最小邊：在連通圖中，對任意非空的頂點真子集 $S \subset V$，跨越割 $(S, V \setminus S)$ 且權重嚴格最小的邊，必定包含於圖的最小權重擴張樹（Minimum Spanning Tree, MST）中。對於單一頂點 $v$，以其為割 $(\{v\}, V \setminus \{v\})$，其最小事件邊 $l(v)$ 必然是該割上的最小邊，故 $l(v)$ 必定屬於 MST。
2. 波魯夫卡演算法（Borůvka's Algorithm）核心精神：本題的邊集合 $L$ 即為 Borůvka 演算法在第一輪（第一階段）所挑選的邊集合。若權重互異，所選取的邊必不包含迴圈且均屬於唯一存在的 MST。
3. 極值原理與反證法（Proof by Contradiction）：證明無迴圈時，利用迴圈中必然存在「權重嚴格最大之邊」的性質導出矛盾。
4. 全序關係建立（Tie-Breaking）：當邊的權重相同時，為避免演算法產生環路或歧義，可透過給予每條邊唯一編號（或端點座標字典序）建立嚴格全序關係（Strict Total Order）。

---

解題方法

（一）證明 $G[L]$ 沒有迴圈（Acyclic）

採用反證法（Proof by Contradiction）：

1. 假設反面成立： 假設由邊集合 $L$ 所導出的子圖 $G[L]$ 存在至少一個簡單迴圈 $C$。 設該迴圈由 $k$ 個相異頂點依序構成：$C = (v_1, v_2, \ldots, v_k, v_1)$，其中 $k \ge 3$。

2. 找出迴圈中的最大邊： 因為題設「每個邊的權重都不相同」，迴圈 $C$ 上的所有邊權重皆互異，因此在迴圈 $C$ 中必定存在唯一的「嚴格最大權重邊」。 設此邊為 $e_{\max} = (u, v) \in C$。

3. 導出矛盾：

• 根據 $L$ 的定義，$e_{\max} \in L = \bigcup_{x\in V} l(x)$，表示 $e_{\max}$ 必定是其端點 $u$ 或 $v$ 的最小事件邊（亦即 $e_{\max} = l(u)$ 或 $e_{\max} = l(v)$）。
• 不失一般性，假設 $e_{\max} = l(u)$。這意味著在所有連接至頂點 $u$ 的邊當中，$e_{\max}$ 的權重嚴格最小。
• 然而，由於頂點 $u$ 位於迴圈 $C$ 上，$u$ 在迴圈中必定還連接了另一條相鄰邊 $e' \in C$（$e' \ne e_{\max}$）。
• 根據 $e_{\max}$ 為迴圈 $C$ 中嚴格最大邊的設定，必有： $w(e') < w(e_{\max})$
• 此不等式與「$e_{\max} = l(u)$ 是以 $u$ 為端點中權重最小的邊」產生矛盾。

4. 結論： 假設不成立，故 $G[L]$ 絕不可能存在迴圈，$G[L]$ 為一個無向無環圖（即森林，Forest）。

---

（二）判斷 $G[L]$ 是否一定是 $G$ 的擴張樹，並給出論證

$G[L]$ 不一定是 $G$ 的擴張樹。

擴張樹必須滿足「連通且無迴圈」之條件。雖然由第（一）小題已知 $G[L]$ 無迴圈，但 $G[L]$ 不一定連通，其連通元件（Connected Components）數量可能大於 1，此時 $G[L]$ 僅為擴張森林（Spanning Forest），而非單一擴張樹。

• 反例說明： 考慮一包含 4 個頂點的連通圖 $G=(V,E)$，其中：

• 頂點集合：$V = \{1, 2, 3, 4\}$
• 邊集合與權重：
• $e_1 = (1, 2)$，權重 $w(e_1) = 1$
• $e_2 = (3, 4)$，權重 $w(e_2) = 2$
• $e_3 = (2, 3)$，權重 $w(e_3) = 10$
• $e_4 = (4, 1)$，權重 $w(e_4) = 20$

所有邊的權重皆互不相同，為正整數。

• 求各頂點的最小事件邊 $l(v)$：

• 對頂點 1：相鄰邊為 $(1,2)$ [權重 1] 與 $(4,1)$ [權重 20]，最小為 $l(1) = (1, 2)$。
• 對頂點 2：相鄰邊為 $(1,2)$ [權重 1] 與 $(2,3)$ [權重 10]，最小為 $l(2) = (1, 2)$。
• 對頂點 3：相鄰邊為 $(3,4)$ [權重 2] 與 $(2,3)$ [權重 10]，最小為 $l(3) = (3, 4)$。
• 對頂點 4：相鄰邊為 $(3,4)$ [權重 2] 與 $(4,1)$ [權重 20]，最小為 $l(4) = (3, 4)$。

• 分析 $L$ 與 $G[L]$： $L = l(1) \cup l(2) \cup l(3) \cup l(4) = \{(1, 2), (3, 4)\}$ $G[L]$ 中只包含 2 條邊，而 4 個頂點的擴張樹必須恰有 $4 - 1 = 3$ 條邊。在 $G[L]$ 中，頂點 $\{1, 2\}$ 與頂點 $\{3, 4\}$ 分屬兩個互不相連的連通分量，圖形並不連通，因此 $G[L]$ 不是 $G$ 的擴張樹。

---

（三）利用上述結論設計最小權重擴張樹（MST）演算法

根據割性質（Cut Property），每個頂點所挑選的最小邊 $l(v)$ 必定屬於最小權重擴張樹。由於一次挑選可能形成多個連通元件（森林），可將各連通元件視為「超頂點（Super-vertex）」，反覆套用此選邊策略進行元件縮合。這正是經典的 Borůvka 演算法（又稱 Sollin 演算法）。

演算法步驟：

1. 初始化：

• 令擴張樹邊集合 $T = \emptyset$。
• 使用互斥集合（Disjoint Set / Union-Find）資料結構，將圖中每一個頂點 $v \in V$ 各自初始化為一個獨立的連通元件。

核心觀念

1. 比較排序法與非比較排序法的時間複雜度界限：

• 一般基於「兩兩比較」的排序演算法（如 Merge Sort、Heap Sort），其時間複雜度下限為 $\Omega(n \log n)$。
• 若欲在線性時間 $O(n)$ 或 $O(n+M)$ 內完成排序，必須打破比較排序的限制，改採非比較排序法（Non-comparison Sort），如計數排序法（Counting Sort）​與基數排序法（Radix Sort）。

2. 計數排序法（Counting Sort）：

• 適用於已知輸入為介於特定範圍內的整數。若數值範圍為 $1$ 至 $M$，建立大小為 $M$ 的計數陣列統計各數值的出現頻率，並利用累加次數（前綴和）決定各元素的輸出位置。
• 時間複雜度為 $O(n + M)$，空間複雜度為 $O(n + M)$，且具有穩定性（Stability）。

3. 基數排序法（Radix Sort）：

• 依據位數由低位至高位（LSD, Least Significant Digit first）依序進行排序，每一輪位數的排序必須使用穩定的排序演算法（通常採用計數排序）。
• 若 $n$ 個鍵值的最大值為 $n^c$（$c$ 為常數），只要選擇以 $n$ 為基底（Base-$n$）進制表示，各數值的位數即為 $\lceil \log_n(n^c) \rceil = c$ 位。每位數的值域為 $0 \le \text{digit} \le n - 1$，每輪計數排序耗時 $O(n + n) = O(n)$，總時間複雜度為 $c \times O(n) = O(n)$。

---

解題方法

（一）$x_i \le M$ 的 $O(n+M)$ 排序演算法

本小題直接採用計數排序法（Counting Sort）。

演算法步驟

1. 配置計數陣列：宣告一個大小為 $M$ 的陣列 $C[1..M]$，並將所有元素初始化為 $0$。配置與原陣列大小相同的輸出陣列 $B[1..n]$。
2. 統計出現次數：走訪陣列 $A$，依元素值統計各數出現次數： $C[A[i]] \leftarrow C[A[i]] + 1 \quad (\forall i \in \{1, 2, \ldots, n\})$
3. 計算前綴累加和：將 $C$ 陣列轉換為小於或等於該數值的累積出現次數： $C[j] \leftarrow C[j] + C[j-1] \quad (\forall j \in \{2, 3, \ldots, M\})$ 此時 $C[v]$ 即代表數值 $v$ 在排序後輸出陣列中的最終存放位置（1-based）。
4. 輸出排序結果（確保穩定性）：從原陣列 $A$ 的尾端向前端反向走訪（$i = n$ 倒數至 $1$）： $B[C[A[i]]] \leftarrow A[i]$ $C[A[i]] \leftarrow C[A[i]] - 1$
5. 將 $B[1..n]$ 複製回 $A[1..n]$（或直接輸出 $B$）。

虛擬碼（Pseudocode）

Algorithm COUNTING-SORT(A, n, M)
 let C[1..M] be a new array, initialized to 0
 let B[1..n] be a new array
 
 for i = 1 to n do
 C[A[i]] = C[A[i]] + 1
 
 for j = 2 to M do
 C[j] = C[j] + C[j - 1]
 
 for i = n downto 1 do
 B[C[A[i]]] = A[i]
 C[A[i]] = C[A[i]] - 1
 
 return B

複雜度分析

• 初始化陣列 $C$：耗時 $O(M)$。
• 頻率統計：走訪長度為 $n$ 的陣列，耗時 $O(n)$。
• 累加前綴和：走訪長度為 $M$ 的陣列，耗時 $O(M)$。
• 反向輸出定位：走訪長度為 $n$ 的陣列，耗時 $O(n)$。
• 總時間複雜度：$O(n) + O(M) + O(n) + O(M) = O(n + M)$。
• 輔助空間複雜度：$O(n + M)$（用於陣列 $B$ 與 $C$）。

---

（二）$x_i \le n^2$ 的 $O(n)$ 排序演算法

此要求完全可行。演算法採用以 $n$ 為基底的基數排序法（Base-$n$ LSD Radix Sort），內部搭配計數排序法。

核心推導與數學轉換

若直接使用第（一）小題的計數排序法，因鍵值上限 $M = n^2$，時間複雜度將膨脹為 $O(n + n^2) = O(n^2)$，不符要求。因此必須將數值降維分解：

1. 原整數值域為 $x_i \in \{1, 2, \ldots, n^2\}$。為便於進位表示，先平移轉換為 0-based 數值： $y_i = x_i - 1 \quad \Longrightarrow \quad y_i \in \{0, 1, 2, \ldots, n^2 - 1\}$
2. 任意介於 $0$ 至 $n^2 - 1$ 的整數 $y_i$，均可精確以 2 個位數的 $n$ 進位制數值 $(d_{i, 1}, d_{i, 0})_n$ 表示： $y_i = d_{i, 1} \cdot n + d_{i, 0}$ 其中：

• 低位數（個位數）：$d_{i, 0} = y_i \pmod n$，其值域為 $\{0, 1, \ldots, n - 1\}$。
• 高位數（十位數）：$d_{i, 1} = \lfloor y_i / n \rfloor$，其值域為 $\{0, 1, \ldots, n - 1\}$。

3. 透過 LSD（Least Significant Digit）基數排序，僅需對低位數與高位數分別進行一次穩定的計數排序，共計 2 回合。

演算法步驟

1. 前處理：對所有 $i = 1$ 至 $n$，設定 $y_i = A[i] - 1$。
2. 第一回合（排序低位數）：

• 提取各元素的鍵值 $\text{key}_0(y_i) = y_i \pmod n$。
• 由於鍵值範圍為 $0$ 到 $n - 1$（共 $n$ 種可能），以 $\text{key}_0$ 為排序基準，對陣列執行穩定計數排序法。
• 本輪時間複雜度為 $O(n + n) = O(n)$。

3. 第二回合（排序高位數）：

• 提取上一輪排序後陣列中各元素的鍵值 $\text{key}_1(y_i) = \lfloor y_i / n \rfloor$。

核心觀念

1. 二元堆積（Binary Heap）之陣列表示法： 在以 $1$ 為起始索引的陣列 $A[1..n]$ 中，對於任意節點 $i$：

• 其左子節點為 $2i$，右子節點為 $2i+1$。
• 其父節點為 $\lfloor i/2 \rfloor$。
• 葉節點（Leaf nodes）的索引範圍為 $\lfloor n/2 \rfloor + 1$ 至 $n$；非葉節點（內部節點）的索引範圍為 $1$ 至 $\lfloor n/2 \rfloor$。
• 題目中的「堆疊（heap）」係指資料結構中的「最大堆積（Max-Heap）」，滿足父節點數值大於等於子節點數值之偏序關係：$A[i] \ge \max\{A[2i], A[2i+1]\}$。

2. 自底向上建立堆積（Bottom-Up Heap Construction / Floyd's Build-Heap）：

• 副程式 $\operatorname{sift}(A, r, n)$ 運作的前提是：以 $A[r]$ 為根的左右子樹皆已滿足堆積性質。
• 葉節點本身無子節點，自然滿足堆積性質，因此不需要進行 $\operatorname{sift}$。
• 演算法應自最後一個非葉節點 $r = \lfloor n/2 \rfloor$ 開始，依序遞減至樹根 $r = 1$，逐一呼叫 $\operatorname{sift}$，確保每次呼叫時，其左右子樹均已由先前的步驟調整為合法堆積。

3. 計算複雜度之級數求和：

• 傳統直覺常誤認為呼叫約 $n/2$ 次 $\operatorname{sift}$、每次花費 $O(\log n)$，導致估計為 $O(n \log n)$。
• 精確分析應將「節點所在的高度」與「該高度的節點數量」合併考慮。越接近底層的節點數量越多，但下沉高度極小；樹根節點下沉高度最大，但只有 $1$ 個節點。透過無窮差比級數求和，可嚴格證明其總時間為線性時間 $O(n)$。

---

解題方法

（一）線性時間建堆演算法設計

演算法說明：

1. 陣列中索引為 $\lfloor n/2 \rfloor + 1$ 至 $n$ 的元素均為葉節點，其高度為 $0$，其各自形成的單節點子樹已經符合堆積定義。
2. 我們由最後一個內部節點 $i = \lfloor n/2 \rfloor$ 遞減迴圈至樹根 $i = 1$。
3. 當處理到節點 $i$ 時，其左子節點 $2i$ 與右子節點 $2i+1$（若存在）的索引均大於 $i$。由於迴圈由大到小執行，以 $A[2i]$ 和 $A[2i+1]$ 為根的子樹已在先前的步驟中被轉化為合法堆積，完全滿足呼叫 $\operatorname{sift}(A, i, n)$ 的前置條件。
4. 當 $i = 1$ 執行完畢後，整個陣列 $A[1..n]$ 即成為合法堆積。

演算法虛擬碼（Pseudocode）：

Algorithm Build-Heap(A, n)
Input: 
 A: 儲存 n 個整數的陣列 A[1..n]
 n: 陣列的大小
Output: 
 符合堆積（Max-Heap）性質的陣列 A[1..n]

begin
 for i := floor(n / 2) down to 1 do
 sift(A, i, n);
 end for
end

---

（二）計算複雜度為 $O(n)$ 之嚴格推導

1. 節點高度與數量界限：

• 定義節點的高（height）$h$ 為從該節點往下到達任一葉節點的最長路徑長度（邊數）。
• 葉節點的高度為 $0$。
• 整個二元樹的樹高為 $H = \lfloor \log_2 n \rfloor$。
• 在一個包含 $n$ 個節點的完全二元樹中，高度為 $h$ 的節點最多有 $\left\lceil \frac{n}{2^{h+1}} \right\rceil$ 個。

2. 總計算時間之數學式： 副程式 $\operatorname{sift}(A, r, n)$ 處理高度為 $h$ 的節點時，所需時間正比於其高度，即花費 $c \cdot h$（$c$ 為某一常數）。 葉節點（$h=0$）不需要執行 $\operatorname{sift}$。總時間 $T(n)$ 為所有非葉節點執行 $\operatorname{sift}$ 所需時間的總和：

核心觀念

本題的核心考點為動態規劃（Dynamic Programming）​中的由上而下記憶化遞迴（Top-down Memoization）。

1. 重疊子問題（Overlapping Subproblems）：傳統樸素遞迴計算斐波納契數列時，相同子問題會被重複呼叫多次，時間複雜度高達 $O(2^n)$。
2. 記憶化查表（Memoization Table）：演算法配置全域陣列 $f[N]$ 作為備忘錄（Lookup Table）。

• 當 $f[k] \ge 0$ 時，代表子問題 $F(k)$ 已經被計算過，直接查表回傳數值，不再深入遞迴。
• 當 $f[k] < 0$（本題初值設為 $-1$）時，代表子問題 $F(k)$ 尚未被計算過，此時必須進入第 4 行執行計算，並將結果存入 $f[k]$。

3. 關鍵指令觸發條件：第 4 行指令 $f[n] = F(n-1) + F(n-2)$ 僅在「首次求解狀態 $f[k]$」時才會被執行。

---

解題方法

1. 程式初始狀態分析

在主程式呼叫 $\operatorname{Fib}(n)$ 時：

• 第 8 行設定基礎狀態（Base Cases）：$f[0] = 0$、$f[1] = 1$。
• 第 9～10 行迴圈將待求的未知狀態初始化： $f[2] = f[3] = \dots = f[n] = -1$
• 第 11 行呼叫 $F(n)$ 開始進行由上而下的記憶化搜尋。

2. 遞迴呼叫展開與執行流程

當呼叫 $F(n)$ 時，由於 $f[n] = -1 < 0$，第 4 行指令被觸發，開始評估右側運算式 $F(n-1) + F(n-2)$。

依 C 語言由左至右評估運算元的特性：

1. 左子樹遞迴優先展開： $F(n)$ 優先呼叫 $F(n-1)$；因為 $f[n-1] = -1$，第 4 行再次被觸發，轉而呼叫 $F(n-2)$……此過程一路沿著左分支向下遞迴，直到呼叫 $F(2)$。 在進入 $F(2)$ 時，因 $f[2] = -1$，第 4 行執行 $f[2] = F(1) + F(0)$：

• 呼叫 $F(1)$：此時 $f[1] = 1 \ge 0$，不滿足 f[n] < 0，不執行第 4 行，直接回傳 $1$。
• 呼叫 $F(0)$：此時 $f[0] = 0 \ge 0$，不滿足 f[n] < 0，不執行第 4 行，直接回傳 $0$。
• 計算完成，將 $f[2] = 1$ 寫入陣列並回傳。

2. 右子樹呼叫命中快取（Cache Hit）：

• 當 $F(2)$ 計算完畢並寫入 $f[2]$ 後，遞迴返回至 $F(3)$ 的第 4 行：$f[3] = F(2) + F(1)$。
• 此時呼叫右運算元 $F(1)$，因 $f[1] = 1 \ge 0$，直接回傳，不執行第 4 行。計算完成後寫入 $f[3] = 2$ 並回傳。
• 同理，當返回上一層 $F(4)$ 的第 4 行時，其右運算元為 $F(2)$；而 $f[2]$ 早在左子樹展開時計算完畢（$f[2] = 1 \ge 0$），因此 $F(2)$ 直接查表回傳，右子樹完全不會進入第 4 行。