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

核心觀念

1. 大 O 符號（Big-O Notation）定義： 若存在正實數常數 $c$ 與正整數 $n_0$，使得對所有 $n \ge n_0$，均滿足 $0 \le T(n) \le c \cdot g(n)$，則記為 $T(n) = O(g(n))$，表示 $g(n)$ 為 $T(n)$ 的漸近上限（Asymptotic Upper Bound）。
2. 基本函數成長速率階層（Growth Rate Hierarchy）： 當 $n \to \infty$ 時，常見函數之成長速率階層為： $O(1) \prec O(\log \log n) \prec O(\log n) \prec O(n^c) \text{ (其中 } 0 < c < 1 \text{)} \prec O(n) \prec O(n \log n) \prec O(n^2) \prec O(2^n) \prec O(n!)$
3. 多項式項之漸近支配原則（Dominance Rule）： 若函數為多個項之和，其漸近成長速率取決於成長最快的「最高次方項（支配項，Dominant Term）」，低階項與常數係數在漸近分析中皆可忽略。

解題方法

本題給定之函數包含三項相加：

• 常數項：$3$
• 根號項：$7\sqrt{n} = 7n^{0.5}$
• 對數項：$\log n$

步驟一：比較各項之成長速率

1. 比較 $\sqrt{n}$ 與常數項 $3$： $\lim_{n \to \infty} \frac{3}{\sqrt{n}} = 0$ 因此 $\sqrt{n}$ 成長速率遠大於常數項。

2. 比較 $\sqrt{n}$ 與 $\log n$： 利用羅必達法則（L'Hôpital's Rule）求極限（對分子分母分別對 $n$ 微分）： $\lim_{n \to \infty} \frac{\log n}{\sqrt{n}} = \lim_{n \to \infty} \frac{\frac{1}{n}}{\frac{1}{2\sqrt{n}}} = \lim_{n \to \infty} \frac{2}{\sqrt{n}} = 0$ 極限值為 $0$，證明 $\sqrt{n}$ 的成長速率嚴格大於 $\log n$。

步驟二：確定支配項並給出漸近上限 在各項中，$7\sqrt{n}$ 為成長最快的支配項。 當 $n \ge 16$ 時，恆有 $3 \le \sqrt{n}$ 且 $\log_2 n \le \sqrt{n}$，因此： $T(n) = 3 + 7\sqrt{n} + \log n \le \sqrt{n} + 7\sqrt{n} + \sqrt{n} = 9\sqrt{n}$ 選取常數 $c = 9$、$n_0 = 16$，滿足大 O 定義 $T(n) \le c\sqrt{n}$。

故其成長速率為 $O(\sqrt{n})$。

解題技巧

• 速判竅門：將所有含 $n$ 的項改寫為指數次方形式。$\sqrt{n} = n^{0.5}$，而任何正次方多項式 $n^\epsilon$（即使 $\epsilon = 0.001$）在 $n \to \infty$ 時均遠大於對數函數 $(\log n)^k$。因此一眼即可鎖定 $n^{0.5}$ 為支配項。
• 常見陷阱：部分考生誤以為 $\log n$ 比 $\sqrt{n}$ 大，或將兩者混淆為同階。切記「多項式勝過對數（Polynomial beats Logarithm）」。

【答案】

$O(\sqrt{n})$

第二小題：$T(n)=2T(n/2)+n$

核心觀念

1. 分治法遞迴關係式（Divide-and-Conquer Recurrence）： 形式為 $T(n) = aT(n/b) + f(n)$，其中 $a \ge 1$ 表示子問題數量，$b > 1$ 表示每次切割縮小之倍率，$f(n)$ 為分割與合併子問題的成本。

核心觀念

本題評量**二元樹（Binary Tree）**於算術運算式的應用，核心觀念包含：

1. 算術運算式的三種表示法：

• 中序運算式（Infix Expression）：運算子置於兩運算元中間，如 $(A + B)$。人類易讀，但需依賴括號與運算子優先順序。
• 前序運算式（Prefix Expression，波蘭表示法）：運算子置於兩運算元之前，如 $+ A\ B$。不需括號即可唯一確定運算順序。
• 後序運算式（Postfix Expression，逆波蘭表示法）：運算子置於兩運算元之後，如 $A\ B +$。

2. 算術運算樹（Expression Tree）的結構特性：

• 為一棵嚴格二元樹（Strict Binary Tree）。
• 葉節點（Leaf Nodes）：皆為運算元（Operands，數值）。
• 內部節點（Internal Nodes）：皆為運算子（Operators，如 $+、-、\times、/$）。

3. 樹走訪（Tree Traversal）與運算式之對應關係：

• 前序走訪（Preorder: V-L-R） $\rightarrow$ 產生前序運算式。
• 中序走訪（Inorder: L-V-R） $\rightarrow$ 產生中序運算式（配合括號還原優先權）。
• 後序走訪（Postorder: L-R-V） $\rightarrow$ 產生後序運算式，且為運算樹求值（Evaluation）的自然順序。

解題方法

題目給定之中序算術運算式為： $((6\times(5-3))-(1+2))\times(((4+2)/3)+(5\times4))$

(一) 前序運算式（Prefix Expression）推導

利用括號化法（Fully Parenthesized Method）或直接由運算子優先權進行由外而內的轉換：

1. 最外層主運算子為中央的 $\times$： $\times\ [ (6\times(5-3))-(1+2) ]\ [ ((4+2)/3)+(5\times4) ]$
2. 轉換左子運算式 $[ (6\times(5-3))-(1+2) ]$：

• 主運算子為 $-$：$-\ [ 6\times(5-3) ]\ [ 1+2 ]$
• 轉換 $6\times(5-3)$：$\times\ 6\ [ 5-3 ] \implies \times\ 6\ -\ 5\ 3$
• 轉換 $1+2$：$+\ 1\ 2$
• 左子運算式前序為：$-\ \times\ 6\ -\ 5\ 3\ +\ 1\ 2$

3. 轉換右子運算式 $[ ((4+2)/3)+(5\times4) ]$：

• 主運算子為 $+$：$+\ [ (4+2)/3 ]\ [ 5\times4 ]$
• 轉換 $(4+2)/3$：$/\ [ 4+2 ]\ 3 \implies /\ +\ 4\ 2\ 3$
• 轉換 $5\times4$：$\times\ 5\ 4$
• 右子運算式前序為：$+\ /\ +\ 4\ 2\ 3\ \times\ 5\ 4$

4. 合併全式： $\times\ -\ \times\ 6\ -\ 5\ 3\ +\ 1\ 2\ +\ /\ +\ 4\ 2\ 3\ \times\ 5\ 4$

(二) 繪製算術運算樹（Expression Tree）

依據運算式之結合順序與階層關係，自頂向下建立二元運算樹：

• 根節點為最外層乘號 $\times$。
• 左子樹代表 $((6\times(5-3))-(1+2))$。
• 右子樹代表 $(((4+2)/3)+(5\times4))$。

算術運算樹之結構圖如下：

 [ × ] (根節點)
 ／ ＼
 ／ ＼
 [ － ] [ ＋ ]
 ／ ＼ ／ ＼
 [ × ] [ ＋ ] [ ／ ] [ × ]
 ／ ＼ ／ ＼ ／ ＼ ／ ＼
 (6) [－] (1) (2)[＋] (3)(5) (4)
 ／ ＼ ／ ＼
 (5) (3) (4) (2)

節點階層關係說明：

1. 根節點為 $\times$，其左子節點為 $-$，右子節點為 $+$。
2. 左子樹節點 $-$：

• 左子節點為 $\times$（其左子節點為 $6$，右子節點為 $-$，此 $-$ 之子節點為 $5$ 與 $3$）。
• 右子節點為 $+$（其子節點為 $1$ 與 $2$）。

3. 右子樹節點 $+$：

• 左子節點為 $/$（其左子節點為 $+$，此 $+$ 之子節點為 $4$ 與 $2$；右子節點為 $3$）。
• 右子節點為 $\times$（其子節點為 $5$ 與 $4$）。

(三) 運算樹求值原理與步驟

核心觀念

本題評量多元樹（$m$-ary Tree）的基礎理論、陣列循序儲存表示法，以及自平衡多元搜尋樹的進階結構。核心涵蓋：

1. $m$ 路樹（$m$-ary Tree）的結構定義：以遞迴方式定義空樹或由根節點與最多 $m$ 棵互斥之 $m$ 路子樹所組成之有序樹（Ordered Tree）。
2. 完全 $m$ 路樹（Complete $m$-ary Tree）的陣列索引對映：利用階層順序（Level-order）循序存放於陣列中，推導「0 起始索引（0-based indexing）」下父節點與子節點之整數映射公式。
3. 多元搜尋樹（Multi-way Search Tree）與 $(2,4)$-樹（$(2,4)$-Tree）：

• 四元搜尋樹（4-ary Search Tree）的鍵值（Keys）排列與子樹區間劃分規則。
• $(2,4)$-樹（亦稱 2-3-4 樹，為階數為 4 之 B-樹）的大小性質（Size Property）與深度平衡性質（Depth Property）。

解題方法與推導

(一) $m$ 路樹的定義

$m$ 路樹（$m$-ary Tree）為一種有限節點的集合 $T$，其遞迴定義如下：

1. 基底情況（Base Case）：$T$ 可以為空集合（Empty tree）。
2. 遞迴情況（Recursive Step）：$T$ 由一個稱為根節點（Root）的節點，以及 $m$ 個互斥的子集合 $T_0, T_1, \dots, T_{m-1}$ 所組成。其中每個子集合 $T_k$（$0 \le k \le m-1$）本身亦為一棵 $m$ 路樹，稱為根節點的第 $k$ 個子樹（Subtree）。

重要性質：

• 樹中任意節點的分支度（Degree，即擁有子節點的個數）至多為 $m$（$0 \le \text{degree}(v) \le m$）。
• 各子樹之間具有嚴格的順序關係（即 Ordered Tree），不可任意對調。當 $m=2$ 時，即為二元樹（Binary Tree）。

(二) 陣列表示法之親子節點索引推導

當使用陣列以階層順序（Level-order）表示完全 $m$ 路樹（Complete $m$-ary Tree），且陣列起始索引為 $0$（根節點位於索引 $0$）時：

1. 第 $c$ 個子節點的位置推導

• 根節點（索引 $0$）之前有 $0$ 個節點，其子節點依序排列於陣列索引 $1, 2, \dots, m$。
• 若節點 $v$ 位於索引 $i$，代表在節點 $v$ 之前（包括其祖先與同一層左側節點）共有 $i$ 個節點。
• 根據完全樹的排滿規則，這 $i$ 個節點共產生 $i \times m$ 個子節點，再加上根節點本身（佔用索引 $0$），因此節點 $v$ 的第一個子節點起始位置必為： $m \cdot i + 1$
• 子節點編號 $c$ 之定義可採兩種常規慣例：
• 慣例 A（子節點編號以 $1$ 起算，即 $c \in \{1, 2, \dots, m\}$）： 節點 $v$ 的第 $c$ 個子節點索引為： $\text{Child}(i, c) = m \cdot i + c$
• 慣例 B（子節點編號以 $0$ 起算，即 $c \in \{0, 1, \dots, m-1\}$）： 節點 $v$ 的第 $c$ 個子節點索引為： $\text{Child}(i, c) = m \cdot i + c + 1$

2. 父節點（Parent）的位置推導

• 設某非根節點位於陣列索引 $i$（$i > 0$），其父節點索引為 $p$。
• 根據子節點公式，該節點必為父節點 $p$ 的某個子節點： $i = m \cdot p + k \quad (1 \le k \le m)$
• 將等式兩邊同時減去 $1$： $i - 1 = m \cdot p + (k - 1) \quad (0 \le k - 1 \le m - 1)$
• 兩邊同除以 $m$ 並取下高斯符號（Floor，即無條件捨去）： $\lfloor \frac{i - 1}{m} \rfloor = \lfloor p + \frac{k - 1}{m} \rfloor = p + 0 = p$
• 因此，對於任意非根節點 $v$（索引 $i > 0$），其父節點索引固定為： $\text{Parent}(i) = \lfloor \frac{i - 1}{m} \rfloor$

(三) $(2,4)$-樹的定義與四元搜尋樹之差異

1. 四元搜尋樹（4-ary Search Tree）的定義

四元搜尋樹為二元搜尋樹在 $m=4$ 時的推廣，滿足：

• 每個內部節點至多包含 $4$ 個子節點，以及至多 $3$ 個搜尋鍵值（Keys）。
• 若節點包含 $d$ 個子節點（$2 \le d \le 4$），則該節點包含 $d-1$ 個鍵值 $K_1 < K_2 < \dots < K_{d-1}$，將數值範圍劃分為 $d$ 個區間。

核心觀念

1. 二元堆積（Binary Heap）與最小堆積性質（Min-Heap Property）：

• 結構性（Structural Property）：二元堆積在本質上是一棵「完全二元樹（Complete Binary Tree）」，除底層外每一層皆被填滿，且底層節點由左至右緊密排列。
• 順序性（Heap-Order Property）：最小堆積規定對於任一非根節點 $v$，其父節點鍵值小於或等於該節點鍵值，即 $key(\text{parent}(v)) \le key(v)$；因此全樹之最小值必儲存於樹根（Root）。

2. 堆積排序（Heap Sort）：

• 採「由底向上建堆（Bottom-up Heapify）」與「連續萃取樹根（Extract）」兩階段進行。
• 建堆時間為 $O(N)$，每次萃取並維護堆積耗時 $O(\log N)$，排序 $N-1$ 次耗時 $O(N \log N)$，總時間複雜度為 $O(N \log N)$，且為原處排序（In-place Sorting，空間複雜度 $O(1)$）。

3. 具堆積特性之二元樹合併（Merging Heaps via Sift-Down）：

• 題目指定為具堆積特性且高度為對數級別的二元樹（非強制要求維持完全二元樹之陣列連續性）。
• 可利用「取一葉節點作為新樹根、原二樹為左右子樹」，再針對新樹根進行一次「下濾（Sift-Down / Heapify-Down）」調整，於樹高深度 $O(\text{Height}) = O(\log n + \log m)$ 內完成合併。

解題方法

(一) 最小堆積（Min-Heap）的定義與相關操作功能

1. 完整定義： 最小堆積為滿足以下兩項特性的二元樹：

• 完全二元樹（Complete Binary Tree）：設樹高為 $h$，第 $0$ 層至第 $h-1$ 層的節點數均達到最大容量；第 $h$ 層（最底層）的所有葉節點由左至右依序填入，無間隙。
• 最小堆積序性（Min-Heap Order）：除樹根外，樹中任意節點 $x$ 均滿足 $key(\text{parent}(x)) \le key(x)$。換言之，任意子樹的根節點鍵值必小於或等於其左、右子節點之鍵值，樹根保證為整棵樹的最小值。

2. 相關操作功能：

• Find-Min（查詢最小值）： 直接回傳樹根節點之鍵值。 時間複雜度：$O(1)$。
• Insert(x)（插入節點）： 將新元素放入完全二元樹最底層由左至右的第一個空位（即最後一個節點的下一個位置），隨後執行「上濾（Sift-Up / Percolate-Up）」：將新節點與其父節點比較，若新節點鍵值較小則互換，重複此步驟直至滿足堆積序性或抵達樹根。 時間複雜度：$O(\log N)$（$N$ 為節點數）。
• Extract-Min / Delete-Min（刪除最小值）： 取出樹根節點，將最底層最後一個葉節點搬移至樹根位置，隨後執行「下濾（Sift-Down / Percolate-Down）」：將該節點與其左、右子節點中鍵值較小者比較，若其鍵值較大則互換，重複向下推移直至滿足堆積序性或成為葉節點。 時間複雜度：$O(\log N)$。
• Build-Heap（建構堆積）： 給定包含 $N$ 個未排序元素的陣列，由最後一個非葉節點（索引 $\lfloor N/2 \rfloor$）由後往前至根節點，對每一節點依序呼叫下濾調整。 時間複雜度：$O(N)$。

(二) 堆積排序（Heap Sort）的方法並分析其時間複雜度

1. 方法說明（以遞增排序為例，採用最大堆積 Max-Heap）：

• 步驟一：建構堆積（Build-Heap） 將大小為 $N$ 的未排序輸入陣列視為一棵完全二元樹，由最後一個非葉節點 $\lfloor N/2 \rfloor$ 開始往第 $1$ 個節點逆序遍歷，對每一節點執行下濾（Max-Heapify），建立最大堆積（樹根為全域最大值）。
• 步驟二：排序與萃取（Sorting Phase） 重複以下動作共 $N-1$ 回合：

1. 將樹根（陣列首項，即未排序區域之最大值）與目前堆積之最後一個葉節點（未排序區域末項）交換，使最大值歸位至最終位置。

2. 將堆積有效大小減 $1$（將歸位的最大值排除於堆積之外）。

3. 對新的樹根執行下濾（Max-Heapify），重新維護其最大堆積性質。 當所有元素處理完畢，陣列即完成遞增排序。

4. 時間複雜度分析：

• 建構堆積階段： 設樹高為 $H = \lfloor \log_2 N \rfloor$。高度為 $h$ 的層級最多有 $\lceil N / 2^{h+1} \rceil$ 個節點，且高度為 $h$ 的節點下濾最多需 $O(h)$ 次比較與置換。總耗時為： $T_{\text{build}}(N) = \sum_{h=0}^{\lfloor \log_2 N \rfloor} \left\lceil \frac{N}{2^{h+1}} \right\rceil \cdot O(h) = O\left( N \sum_{h=0}^{\infty} \frac{h}{2^h} \right) = O(N)$
• 排序與萃取階段： 共進行 $N-1$ 次交換與下濾。每次下濾花費時間與當前樹高成正比，最多需 $O(\log N)$ 次比較與交換。總耗時為： $T_{\text{sort}}(N) = \sum_{i=2}^{N} O(\log i) = O(N \log N)$
• 整體時間複雜度： $T(N) = T_{\text{build}}(N) + T_{\text{sort}}(N) = O(N) + O(N \log N) = O(N \log N)$ 堆積排序在最佳、最差與平均情況下，時間複雜度均穩定為 $O(N \log N)$。此外，排序過程直接在輸入陣列上交換，額外空間複雜度為 $O(1)$。

(三) 結合兩棵具堆積特性之二元樹 $T_1$ 與 $T_2$ 之方法與複雜度分析

核心觀念

本題考查加權無向圖的相鄰矩陣、廣度優先尋訪（BFS）與最小擴張樹（MST）。

相鄰矩陣以列、欄代表頂點；若兩頂點間有邊，填入邊權重，若無邊則填入 $\infty$。BFS 不考慮權重，依指定的字母順序探索尚未拜訪的相鄰頂點。Prim 演算法則從指定起點開始，每次選擇一條連接「已納入頂點」與「尚未納入頂點」的最小權重邊。

圖中頂點為 $V=\{a,b,c,d,f,g,h,i\}$；無向邊及權重為： $ab=22,\ ah=14,\ bc=10,\ bd=41,\ bg=35,\ cd=31,\ df=4,\ fg=18,\ gh=6,\ hi=37,\ fi=29$。

（一）加權相鄰矩陣

頂點依字母順序排列為 $a,b,c,d,f,g,h,i$。主對角線填 $0$；沒有直接相連的頂點填 $\infty$。因為圖是無向圖，矩陣對稱。

（二）由 $g$ 開始的 BFS 樹

忽略邊權重，並按字母順序檢查每個頂點的相鄰點。

1. 從 $g$ 開始；其相鄰點為 $b,f,h$，依序納入佇列。
2. 處理 $b$，發現尚未拜訪的 $a,c,d$。
3. 處理 $f$，發現尚未拜訪的 $i$；$d$ 已拜訪，不再加入。
4. 處理 $h$ 時，$a,i$ 已拜訪。其餘頂點也都已發現，尋訪完成。

因此 BFS 樹的邊為 $\{gb,gf,gh,ba,bc,bd,fi\}$，可表示為：

 g
 / | \
 b f h
 / | \ \
 a c d i

（三）Prim 演算法與最小擴張樹