107 高普考高考三級 資訊處理 資料結構 考古題詳解

核心觀念

本題評量公職考試「資料結構」中最經典的核心主題：連續儲存結構（陣列）與動態鏈結結構（樹狀結構）在檢索、動態維護與走訪上的權衡（Trade-off）。

1. 二分搜尋（Binary Search）：

• 先決條件：必須建立在支援常數時間隨機存取（Random Access）的循序連續記憶體（如陣列 Array），且資料必須已事先由小到大（或由大到小）排序。
• 搜尋原理：分治法（Divide and Conquer）。每次透過中間索引比對，將搜尋區間折半。

2. 一般二元搜尋樹（Binary Search Tree, BST）：

• 性質：若其左子樹不為空，則左子樹上所有節點的鍵值均小於根節點鍵值；若其右子樹不為空，則右子樹上所有節點的鍵值均大於根節點鍵值；且其左、右子樹亦各自為二元搜尋樹。
• 樹高瓶頸：BST 的搜尋與操作效率高度依賴於樹高 $h$。在最差情況下（輸入序列已排序），BST 會退化為單向斜曲樹（Skewed Tree），樹高達 $h = O(n)$。

3. AVL 樹（AVL Tree, 高度平衡二元搜尋樹）：

• 定義：對任一節點而言，其左子樹與右子樹的高度差（平衡因子 Balance Factor, $BF = h_L - h_R$）絕對值不超過 1（即 $BF \in \{-1, 0, 1\}$）。
• 樹高保證：具有 $n$ 個節點的 AVL 樹，其樹高嚴格受限於 $h \le 1.44 \log_2(n+2) = O(\log n)$。因此所有依賴樹高的操作（搜尋、插入、刪除）在最差情況下皆保證為 $O(\log n)$。

4. 陣列（Array）vs. 平衡樹（Balanced Tree）的運算代價：

• 陣列具備常數時間隨機存取（第 $j$ 個元素可直接透過索引 array[j-1] 以 $O(1)$ 取得），但插入與刪除必須搬移元素（Shifting），耗時 $O(n)$。
• 樹狀結構支援動態指標修改，插入與刪除節點不需搬移其餘節點，代價取決於路徑尋找與再平衡（Rotation）成本。

---

解題方法

(一) 二分搜尋 vs. 一般二元搜尋樹（BST）之建置與搜尋比較

針對 $n$ 個鍵值，兩者在建置程序與搜尋程序上的運作方式與效能推導如下：

1. 建置程序（Construction）

• 二分搜尋（以陣列為基礎）：
• 作法：二分搜尋無法在未排序的陣列上運作。建置程序包含兩步：先將 $n$ 筆資料置入大小為 $n$ 的連續陣列中，再使用最佳效率之比較排序演算法（如合併排序 Merge Sort 或堆積排序 Heap Sort）對陣列進行排序。
• 效能：
• 時間複雜度：最差、平均與最佳皆為 $O(n \log n)$（若使用快速排序 Quick Sort，最差為 $O(n^2)$，但標準建置多採 $O(n \log n)$ 演算法）。
• 空間複雜度：除儲存 $n$ 個鍵值外，排序額外輔助空間為 $O(1) \sim O(n)$。不需指標開銷。
• 一般二元搜尋樹（BST）：
• 作法：以動態節點構成（各節點含資料欄位及左、右子指標）。從空樹開始，逐一讀入鍵值，透過 BST 插入規則（小於當前節點走左邊、大於當前節點走右邊，直至遇空指標掛上新節點），共執行 $n$ 次插入操作。
• 效能：
• 時間複雜度：
• 最佳 / 平均情況（輸入資料隨機排列）：樹結構大致平衡，樹高 $h = O(\log n)$，建置時間為 $\sum_{i=1}^{n} O(\log i) = O(n \log n)$。
• 最差情況（輸入資料原先就已依序由小到大或由大到小排列）：樹退化為「斜曲樹」（Skewed Tree），樹高達 $h = O(n)$。每次插入需比對目前所有節點，建置時間為 $1 + 2 + \dots + n = O(n^2)$。
• 空間複雜度：除儲存 $n$ 個鍵值外，每個節點需額外儲存 2 個指標（left_child, right_child），空間複雜度為 $O(n)$，但實體記憶體常數較大。

2. 搜尋程序（Search）

• 二分搜尋：
• 作法：維護左右邊界指標 low 與 high。每次計算中點 mid = (low + high) / 2，以陣列索引直接讀取中點鍵值並與目標鍵值比較。若命中則結束；若目標鍵值較小則移至左半區間 high = mid - 1；較大則移至右半區間 low = mid + 1。
• 效能：
• 時間複雜度：每次比對均將搜尋空間折半，故最差與平均時間複雜度皆嚴格保證為 $O(\log n)$；最佳情況（首次中點即命中）為 $O(1)$。
• 一般二元搜尋樹（BST）：
• 作法：從根節點（root）開始比對。若命中則結束；若目標鍵值較小則遞迴走入左子樹；較大則走入右子樹，直到命中或指針為 NULL（代表鍵值不存在）。
• 效能：
• 時間複雜度：
• 最佳情況（目標鍵值位於根節點）：$O(1)$。
• 平均情況（樹形平衡）：$O(\log n)$。
• 最差情況（樹退化為斜曲樹）：等同於在單向鏈結串列（Linked List）中循序搜尋，時間複雜度退化為 $O(n)$。

【綜合對比表】

比較項目	二分搜尋（已排序陣列）	一般二元搜尋樹（BST）
資料結構型態	靜態、連續記憶體（Array）	動態、節點鏈結結構（Linked Tree）
建置作法	陣列收集資料後，進行整批排序	由空樹開始，依序將 $n$ 筆資料插入節點
建置時間（平均）	$O(n \log n)$	$O(n \log n)$
建置時間（最差）	$O(n \log n)$（以 Merge/Heap Sort 排序）	$O(n^2)$（輸入已排序時退化為斜曲樹）
搜尋時間（平均）	$O(\log n)$	$O(\log n)$
搜尋時間（最差）	$O(\log n)$	$O(n)$
空間開銷	僅鍵值本身，$O(n)$，無額外指標負擔	每個節點需額外負擔 2 個子節點指標

---

(二) 策略甲（排序陣列）vs. 策略乙（AVL 樹）六種功能 Big-O 比較

以下針對含有 $n$ 個鍵值的「策略甲：已由小到大排序的陣列」與「策略乙：AVL 樹」獨立運作進行分析：

1. 尋找特定鍵值 $k$

• 策略甲（排序陣列）：利用二分搜尋法，搜尋範圍每次折半，時間複雜度為 $O(\log n)$。
• 策略乙（AVL 樹）：AVL 樹為高度平衡樹，樹高保證為 $h = O(\log n)$。自根節點向下尋找，最差比對次數等於樹高，時間複雜度為 $O(\log n)$。
• 效能比較：兩者效能相近（皆為 $O(\log n)$）。

2. 尋找排序為 $j$ 的鍵值

• 策略甲（排序陣列）：陣列支援常數時間隨機存取，排序為 $j$（第 $j$ 小）的元素其索引即為 array[j-1]，直接存取時間複雜度為 $O(1)$。
• 策略乙（AVL 樹）：
• 在標準 AVL 樹定義中，節點僅記錄平衡因子（或樹高）與鍵值。欲取得第 $j$ 小元素，必須透過中序走訪（Inorder Traversal）依序拜訪節點並計數，最差需走訪 $j$ 個節點，時間複雜度為 $O(j) \le O(n)$。

核心觀念

本題為二元樹（Binary Tree）計數性質的經典定理證明題，主要考查以下定義與結構性質：

1. 節點的分支度（Degree of a node）：一個節點所擁有的子樹（子節點）個數。二元樹中任意節點的分支度僅可能為 $0$、$1$ 或 $2$。

• 分支度為 $0$：即葉節點（Leaf Node），個數記為 $n_0$。
• 分支度為 $1$：具有單一子節點的節點，個數記為 $n_1$。
• 分支度為 $2$：具有兩個子節點的節點，個數記為 $n_2$。

2. 樹的邊數與節點總數關係：在任一非空樹狀結構中，除了根節點（Root）沒有任何父節點指向它之外，其餘每個節點皆恰好由一條指向它的分支（邊）所連結。若節點總數為 $n$、分支總數為 $B$，則 $B = n - 1$（即 $n = B + 1$）。
3. 分支總數與分支度關係：所有分支皆是由節點向下指出，故總分支數 $B$ 等於所有節點的分支度總和。

---

解題方法

採用「雙重計數法」（Double Counting），分別從「節點分支度分類」與「分支（邊）總數」兩個角度建立方程式聯立推導。

步驟一：依分支度計算節點總數 $n$

設該非空二元樹之節點總數為 $n$。 樹中每個節點的分支度必為 $0$、$1$ 或 $2$ 之一，故節點總數可表示為： $n = n_0 + n_1 + n_2 \quad \text{--- (式 1)}$

步驟二：依分支（邊）總數推導節點總數 $n$

設樹中的總分支數為 $B$。 每個分支度為 $0$ 的節點向下引出 $0$ 條邊；分支度為 $1$ 的節點引出 $1$ 條邊；分支度為 $2$ 的節點引出 $2$ 條邊。因此總分支數為： $B = 0 \cdot n_0 + 1 \cdot n_1 + 2 \cdot n_2 = n_1 + 2n_2$

因樹為非空，除根節點無指向它的分支外，其餘 $n - 1$ 個節點皆恰好對應一條由父節點指入的分支，因此樹的總節點數與分支數具備以下關係： $B = n - 1 \implies n = B + 1$

將 $B = n_1 + 2n_2$ 代入上式，可得節點總數的第二種表示式： $n = n_1 + 2n_2 + 1 \quad \text{--- (式 2)}$

核心觀念

1. 接合點（Articulation Point，亦稱割頂 Cut-vertex）： 在連通的無向圖 $G=(V, E)$ 中，若移除某節點 $v$ 及其所有相連的邊後，所形成的子圖不再連通（即連通元件的數量增加），則節點 $v$ 稱為圖 $G$ 的接合點。
2. 雙連通圖（Biconnected Graph）： 若一個連通無向圖不包含任何接合點，且節點數至少為 2，則稱此圖為雙連通圖。雙連通圖中任意兩相異節點之間，至少存在兩條內部節點互斥（internally vertex-disjoint）的路徑。
3. 雙連通元件（Biconnected Component，簡稱 BCC，亦稱雙連通分量）： 雙連通元件為圖 $G$ 的「極大雙連通子圖（Maximal Biconnected Subgraph）」。

• 邊的分割性：原圖 $G$ 的邊集合 $E$ 會被分割成數個互斥的雙連通元件，即圖中的每一條邊「恰好屬於一個」雙連通元件。兩條邊屬於同一個雙連通元件，若且唯若它們位於同一個簡單環（simple cycle）上，或者它們為同一條邊。
• 節點的分屬：非接合點只會屬於一個雙連通元件；接合點則必然同時出現在兩個或兩個以上的雙連通元件中。單一條「橋（Bridge）」本身即構成一個包含 2 個節點與 1 條邊的雙連通元件。

---

解題方法

步驟一：分析圖之拓撲結構與各節點分支度（Degree）

由題意給定之邊集合： $G(E)=\{(0,1),(1,2),(1,3),(2,4),(3,4),(3,5),(5,6),(5,7),(6,7),(7,8),(7,9)\}$ 可梳理出各區塊之幾何關聯：

• 節點 $0$ 僅連接節點 $1$（分支度為 1）。
• 節點群 $\{1, 2, 3, 4\}$ 藉由邊 $(1,2), (2,4), (4,3), (3,1)$ 構成一個長度為 4 的簡單環。
• 邊 $(3,5)$ 為連接子圖 $\{0, 1, 2, 3, 4\}$ 與子圖 $\{5, 6, 7, 8, 9\}$ 的唯一橋樑。
• 節點群 $\{5, 6, 7\}$ 藉由邊 $(5,6), (6,7), (5,7)$ 構成一個三角形（長度為 3 的簡單環）。
• 節點 $8$ 與 $9$ 分別藉由邊 $(7,8)$ 與 $(7,9)$ 懸掛於節點 $7$（分支度皆為 1）。

步驟二：判定接合點（Articulation Points）

依據接合點定義，逐一檢驗各節點移除後的連通狀況：

1. 節點 0、8、9：分支度均為 1（端點 / 樹葉節點），移除任一點僅減少該點，其餘節點依然連通，故非接合點。
2. 節點 2、4：位於環 $1-2-4-3-1$ 上。若移除節點 2，節點 4 仍可經由路徑 $4-3-1$ 與其餘部分連通；若移除節點 4，節點 2 仍可經由路徑 $2-1$ 連通，故非接合點。
3. 節點 6：位於環 $5-6-7-5$ 上。若移除節點 6，節點 5 與 7 之間仍有邊 $(5,7)$ 直接相連，故非接合點。
4. 節點 1：移除節點 1 後，邊 $(0,1)$ 斷開，節點 $0$ 形成孤立元件，圖被分割為 $\{0\}$ 與其餘部分，故 $1$ 為接合點。
5. 節點 3：移除節點 3 後，路徑中斷，圖被分割為 $\{0, 1, 2, 4\}$ 與 $\{5, 6, 7, 8, 9\}$ 兩個互不相連的子圖，故 $3$ 為接合點。
6. 節點 5：移除節點 5 後，圖被分割為 $\{0, 1, 2, 3, 4\}$ 與 $\{6, 7, 8, 9\}$ 兩個互不相連的子圖，故 $5$ 為接合點。
7. 節點 7：移除節點 7 後，邊 $(7,8)$ 與 $(7,9)$ 斷開，節點 $8$、節點 $9$ 分別成為孤立元件，故 $7$ 為接合點。

綜上所述，接合點集合為：$\{1, 3, 5, 7\}$。

步驟三：劃分並求出所有雙連通元件（Biconnected Components）

根據接合點將圖的邊集合分解為極大雙連通子圖，共可劃分為 6 個雙連通元件：

核心觀念

1. 對稱式最小－最大堆積（Symmetric Min-Max Heap，簡稱 SMMH）之定義與特性：

• 結構特性：SMMH 為一棵「完全二元樹」（Complete Binary Tree）。其根節點（Root）為空（Dummy），不儲存任何鍵值。
• 兄弟節點特性（Sibling Property）：對任意擁有右兄弟節點 $y$ 的節點 $x$，恆滿足 $\text{key}(x) \le \text{key}(y)$（左兄弟鍵值不大於右兄弟鍵值）。
• 祖父節點之子節點範圍特性（Grandparent Properties）：若節點 $x$ 擁有祖父節點 $gp$：
• 若 $gp$ 有左子節點 $gl$，則 $\text{key}(gl) \le \text{key}(x)$。
• 若 $gp$ 有右子節點 $gr$，則 $\text{key}(x) \le \text{key}(gr)$。
• 即 $gp$ 之子樹中所有深度差大於等於 2 的後代節點 $x$，其鍵值皆落在區間 $[\text{key}(gl), \text{key}(gr)]$ 之內。

2. 雙端優先佇列（Double-Ended Priority Queue, DEPQ）：

• 一般傳統堆積（如 Min-Heap 或 Max-Heap）為「單端優先佇列」（SEPQ），僅能以 $O(1)$ 查找與 $O(\log n)$ 刪除單一極值（最小或最大），查找／刪除另一極端則需 $O(n)$。
• SMMH 是一種 DEPQ，能以 $O(1)$ 時間取得最小值（根節點之左子節點）與最大值（根節點之右子節點），並以 $O(\log n)$ 時間完成插入（Insert）、刪除最小值（Delete Min）與刪除最大值（Delete Max）。

3. 完全二元樹之一維陣列索引運算（0-based Indexing）：

• 樹根置於索引 $0$。
• 對於節點索引 $x$：左子節點為 $2x+1$、右子節點為 $2x+2$、父節點為 $\lfloor \frac{x-1}{2} \rfloor$、祖父節點為 $\lfloor \frac{x-3}{4} \rfloor$、兄弟節點為 $x \pm 1$（左子為 $x+1$、右子為 $x-1$）。

---

解題方法

(一) SMMH 特性說明、功能比較與逐步插入過程

1. SMMH 特性

• 樹狀結構：SMMH 為完全二元樹，根節點為空（不存資料）。
• 左小右大兄弟性質：若節點 $x$ 存在右兄弟 $y$，則 $\text{key}(x) \le \text{key}(y)$。
• 祖父邊界限制：設節點 $x$ 的祖父節點為 $gp$，$gp$ 的左子節點為 $gl$、右子節點為 $gr$，則恆滿足： $\text{key}(gl) \le \text{key}(x) \le \text{key}(gr)$

2. 與一般堆積的功能差異

• 一般堆積（Min-Heap 或 Max-Heap）：屬於單端優先佇列。Min-Heap 僅支援以 $O(1)$ 查找最小值、以 $O(\log n)$ 刪除最小值，但查找或刪除最大值需 $O(n)$；Max-Heap 則僅支援以 $O(1)$ 查找最大值、以 $O(\log n)$ 刪除最大值，查找或刪除最小值需 $O(n)$。
• SMMH：屬於雙端優先佇列。最小值恆存於根節點的左子節點（索引 1），最大值恆存於根節點的右子節點（索引 2）。因此 SMMH 同時支援以 $O(1)$ 查找最小值與最大值，且插入、刪除最小值、刪除最大值皆可在 $O(\log n)$ 時間內完成。

3. 依序插入 $30, 20, 50, 5, 4, 9, 70, 2, 80$ 之逐步推導

（以陣列索引 0 為根節點空位，元素從索引 1 開始放置）：

1. 插入 $30$：

• 放入索引 1（根之左子節點）。無祖父與兄弟節點，直接定位。

2. 插入 $20$：

• 放入索引 2（根之右子節點）。其左兄弟為索引 1（值 30）。
• 違反兄弟特性（$20 < 30$），交換兩者：索引 1 置 $20$、索引 2 置 $30$。

3. 插入 $50$：

• 放入索引 3（索引 1 之左子節點）。祖父為根節點，其左、右子節點分別為索引 1（值 20）與索引 2（值 30）。
• $50 > 30$，違反祖父右子邊界，故 $50$ 與索引 2 之 $30$ 交換：索引 2 變為 $50$，索引 3 置入 $30$。目前滿足 $20 \le 30 \le 50$。

4. 插入 $5$：

• 放入索引 4（索引 1 之右子節點）。左兄弟為索引 3（值 30）。
• 違反兄弟特性（$5 < 30$），$30$ 移至索引 4，候選位置轉至索引 3。
• 檢查索引 3 的祖父左子節點（索引 1，值 20）：$5 < 20$，違反邊界，故 $20$ 下移至索引 3，$5$ 移入索引 1。

5. 插入 $4$：

• 放入索引 5（索引 2 之左子節點）。
• 檢查祖父左子節點（索引 1，值 5）：$4 < 5$，違反邊界，故 $5$ 下移至索引 5，$4$ 移入索引 1。

6. 插入 $9$：

• 放入索引 6（索引 2 之右子節點）。左兄弟為索引 5（值 5）。
• 滿足兄弟特性（$5 \le 9$），且檢查祖父右子節點（索引 2，值 50）：$9 \le 50$，直接定位。

7. 插入 $70$：

• 放入索引 7（索引 3 之左子節點）。祖父為索引 1，其右子節點為索引 4（值 30）。
• $70 > 30$，違反祖父右子邊界，$30$ 下移至索引 7。再往上比對：索引 4 之祖父右子節點為索引 2（值 50），$70 > 50$，$50$ 下移至索引 4，$70$ 移入索引 2。

8. 插入 $2$：

• 放入索引 8（索引 3 之右子節點）。左兄弟為索引 7（值 30）。
• 違反兄弟特性（$2 < 30$），$30$ 移至索引 8，候選位置轉至索引 7。
• 檢查祖父左子節點（索引 3，值 20）：$2 < 20$，$20$ 下移至索引 7。
• 再檢查上一層祖父左子節點（索引 1，值 4）：$2 < 4$，$4$ 下移至索引 3，$2$ 移入索引 1。

9. 插入 $80$：

• 放入索引 9（索引 4 之左子節點）。祖父為索引 1，其右子節點為索引 4（值 50）。
• $80 > 50$，$50$ 下移至索引 9。再往上比對：索引 4 之祖父右子節點為索引 2（值 70），$80 > 70$，$70$ 下移至索引 4，$80$ 移入索引 2。

建構完成後各節點值（1 至 9）：

• 索引 1: $2$、索引 2: $80$
• 索引 3: $4$、索引 4: $70$、索引 5: $5$、索引 6: $9$
• 索引 7: $20$、索引 8: $30$、索引 9: $50$

樹狀結構圖：

 [Root] (空)
 / \
 (2) (80)
 / \ / \
 (4) (70) (5) (9)
 / \ /
 (20) (30)(50)

---

(二) 刪除數字 $2$ 後的 SMMH 樹狀結構圖

1. 取出最小值並縮小樹規模：

• 最小值 $2$ 位於索引 1，將其移除產生空缺（Hole）。
• 取出完全二元樹的最後一個元素（位於索引 9 的 $50$），樹的大小減 1（剩餘 8 個節點）。待安置元素為 $X = 50$。