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

核心觀念

1. 反向（Inversion）的定義與數學性質： 在 $1$ 到 $n$ 的排列中，對於任一對元素 $(i, j)$，若 $i < j$ 且較大的數字 $j$ 出現在較小的數字 $i$ 前面，即稱此對為一個「反向」。由 $n$ 個相異元素構成的排列中，兩兩配對的總對數為組合數 $\binom{n}{2} = \frac{n(n-1)}{2}$。
2. 排列映射 $P$ 的意義： 題目的 $P$ 定義為「數值到出現位置」的映射。若 $x$ 出現在排列的第 $k$ 個位置，則 $P(x) = k$。因此，「較大數字 $j$ 出現在較小數字 $i$ 左邊」在數學上等價於 $P(j) < P(i)$。
3. 線性遞迴（Linear Recursion）： 線性遞迴是指函式在每次執行時，至多只呼叫一次自身（單一遞迴分支），使遞迴呼叫鏈呈一條線性鏈狀結構（問題規模由 $n$ 降至 $n-1$）。這與分治法（Divide-and-Conquer，如合併排序法計算反向數採用的二元分支遞迴 $2T(n/2)$）在結構上截然不同。

解題方法

（一）最大反向數與對應排列推導

1. 排列總對數： 集合 $\{1, 2, \dots, n\}$ 中，滿足 $1 \le i < j \le n$ 的數對 $(i, j)$ 共有： $\binom{n}{2} = \frac{n(n-1)}{2}$
2. 最大反向條件： 當且僅當排列中的「每一對」數字 $(i, j)$（$i < j$）皆滿足 $P(j) < P(i)$（即較大的數恆出現在較小的數之前）時，反向數達到最大值。
3. 對應排列型式： 所有較大數字必須排在所有較小數字的前方，因此該排列必為嚴格由大到小的降冪排列（完全逆序排列）： $n,\ n-1,\ n-2,\ \dots,\ 2,\ 1$ 以題目所定義的位置映射 $P$ 表示為： $P(k) = n - k + 1 \quad (\forall k \in \{1, 2, \dots, n\})$ 其最大反向數即為所有數對的總數：$\frac{n(n-1)}{2}$。

（二）線性遞迴演算法設計與複雜度分析

1. 遞迴切入點與數學推導

設排列中所有反向數對的集合為： $I_n = \{(i, j) \mid 1 \le i < j \le n \land P(j) < P(i)\}$

我們將全體反向對依據「是否包含最大數字 $n$」分割為兩互斥子集：

1. 包含最大數字 $n$ 的反向對：即所有形如 $(i, n)$ 且滿足 $1 \le i < n$ 與 $P(n) < P(i)$ 的數對。我們只需走訪 $i = 1$ 到 $n-1$，統計滿足 $P(n) < P(i)$ 的個數。
2. 不包含數字 $n$ 的反向對：即由數字集合 $\{1, 2, \dots, n-1\}$ 彼此之間構成的反向對。因為移除數字 $n$ 並不會改變剩餘任意兩數 $i, j < n$ 在排列中的相對先後順序（$P(j) < P(i)$ 的真假值完全不變），此子集的大小恰好為規模為 $n-1$ 的子問題反向數。

由此可建立線性遞迴關係式： $\text{CountInversions}(P, n) = \begin{cases} 0, & \text{if } n \le 1 \\ \text{CountInversions}(P, n-1) + \sum_{i=1}^{n-1} [P(n) < P(i)], & \text{if } n > 1 \end{cases}$ 其中 $[P(n) < P(i)]$ 為指示函數，條件成立時計為 $1$，否則計為 $0$。

2. 虛擬碼（Pseudo-code）

假設 $P$ 為一維陣列（索引 $1$ 到 $n$），$P[x]$ 存放數值 $x$ 在排列中的位置（1-based）：

核心觀念

本題評量重點涵蓋「優先佇列（Priority Queue, PQ）抽象資料型態」與「內部實作結構（陣列 vs. 二元堆積）」之間的對應關係，具體核心包含：

1. 優先佇列排序架構（PQ Sort）：利用連續「加入（Insert）」與「擷取（Delete_Min）」完成排序。不同的內部實作（未排序陣列、已排序陣列、堆積）會對應到不同的經典排序演算法（選擇排序、插入排序、堆積排序）。
2. 未排序陣列實作之複雜度權衡（Trade-off）：尾端插入為常數時間 $O(1)$，但尋找並刪除最小值需循序走訪，花費線性時間 $O(n)$。
3. 完全二元樹（Complete Binary Tree, CBT）之循序表示法：利用 1-based 陣列索引對應樹狀結構，節點 $i$ 的父節點為 $\lfloor i/2 \rfloor$，左子節點為 $2i$，右子節點為 $2i + 1$。
4. 最小堆積特性（Min-Heap Property）與堆積化（Heapify）：任意非根節點的鍵值必大於或等於其父節點鍵值。由最後一個非葉節點 $\lfloor n/2 \rfloor$ 起算，由下而上（Bottom-up）對各子樹執行下沉（Sift-Down / Percolate-Down），以 $O(n)$ 時間建構最小堆積。

解題方法

（一）利用優先佇列對 $n$ 個鍵值進行排序

利用優先佇列進行排序的程序統稱為 PQ-Sort，分為兩大階段：

1. 建立階段（Construction Phase）：

• 建立一個空的優先佇列 $PQ$。
• 將待排序的 $n$ 個鍵值依序透過 Insert 操作加入 $PQ$ 中。

2. 擷取輸出階段（Extraction Phase）：

• 連續執行 $n$ 次 Delete_Min 操作。
• 由於每次 Delete_Min 都會取出當前 $PQ$ 中鍵值最小的元素，因此將取出的元素依序填入輸出陣列的第 $1$ 到第 $n$ 個位置，即完成由小到大的遞增排序。

（二）使用未排序陣列（Unsorted Array）實現優先佇列

1. 操作之時間複雜度分析

以長度為 $n$ 的未排序陣列實作：

• Insert（加入）： 直接將新元素置於陣列末端（索引 $n+1$ 處），並將元素計數器加 1。
• 時間複雜度：$O(1)$。
• Delete_Min（擷取最小者）： 由於陣列無序，必須從頭到尾掃描所有元素以找出最小值所在的索引位置，需比較 $n-1$ 次；找到後，將最小值取出，並將陣列最後一個元素移至該空缺處（或將後續元素往前遞移）以維持緊湊性。
• 時間複雜度：$O(n)$。

2. 排序原理判斷

該敘述為非（錯誤），其對應之排序原理應為選擇排序（Selection Sort）。

（三）二元堆積（最小堆積）之結構與操作

1. 陣列對應之完全二元樹

陣列大小 $n = 10$，利用 1-based 索引規則：

• 根節點：Index 1（鍵值 35）
• Index 1 的子節點：左子為 Index 2（鍵值 18）、右子為 Index 3（鍵值 42）
• Index 2 的子節點：左子為 Index 4（鍵值 24）、右子為 Index 5（鍵值 7）
• Index 3 的子節點：左子為 Index 6（鍵值 14）、右子為 Index 7（鍵值 25）
• Index 4 的子節點：左子為 Index 8（鍵值 12）、右子為 Index 9（鍵值 38）
• Index 5 的子節點：左子為 Index 10（鍵值 21）

樹狀結構表示如下：

 35 (1)
 / \
 18 (2) 42 (3)
 / \ / \
 24 (4) 7(5) 14(6) 25(7)
 / \ /
 12(8) 38(9) 21(10)

2. 堆積特性（Heap Property）

在二元堆積中，堆積特性指的是樹中節點鍵值與其子節點鍵值之間的偏序關係：

• 最小堆積特性（Min-Heap Property）：對於樹中除根節點以外的任意節點 $i$，其鍵值恆大於或等於其父節點（Parent）的鍵值，即： $Key(Parent(i)) \le Key(i)$ 換言之，任一子樹的根節點鍵值，皆為該子樹所有節點中的最小值。

3. 堆積化（Heapify）過程與結果

節點總數 $n = 10$，最後一個非葉節點索引為 $\lfloor 10 / 2 \rfloor = 5$。自底向上依序對 Index $5, 4, 3, 2, 1$ 進行下沉（Sift-Down）調整：

1. 調整 Index 5（鍵值 7）：

• 子節點為 Index 10（鍵值 21）。
• 比較 $7 \le 21$，符合最小堆積特性，不需調整。

2. 調整 Index 4（鍵值 24）：

• 子節點為 Index 8（鍵值 12）與 Index 9（鍵值 38）。
• 較小的子節點為 Index 8（鍵值 12）。
• 因 $24 > 12$，將 Index 4 與 Index 8 交換。
• 交換後陣列：[-, 35, 18, 42, 12, 7, 14, 25, 24, 38, 21]。

3. 調整 Index 3（鍵值 42）：

• 子節點為 Index 6（鍵值 14）與 Index 7（鍵值 25）。
• 較小的子節點為 Index 6（鍵值 14）。
• 因 $42 > 14$，將 Index 3 與 Index 6 交換。
• 交換後陣列：[-, 35, 18, 14, 12, 7, 42, 25, 24, 38, 21]。

4. 調整 Index 2（鍵值 18）：

• 子節點為 Index 4（鍵值 12）與 Index 5（鍵值 7）。

核心觀念

1. AVL 樹之定義與平衡特性：AVL 樹為一種高度平衡的二元搜尋樹（Height-Balanced Binary Search Tree）。對樹中任一節點 $x$，其左子樹高度 $h_L$ 與右子樹高度 $h_R$ 滿足平衡因子（Balance Factor, $BF$）條件： $BF(x) = h_L - h_R \in \{-1, 0, 1\}$
2. 二元搜尋樹與中序走訪的排序等價性：二元搜尋樹（BST）的中序走訪（In-order Traversal）依「左子樹 $\to$ 根節點 $\to$ 右子樹」順序輸出，其鍵值必然呈現嚴格遞增排序。
3. 由下而上（Bottom-Up）走訪與剪枝：檢驗樹結構特性時，自頂向下（Top-Down）重複計算樹高會導致 $O(n^2)$ 的最差時間複雜度；改採後序走訪（Post-order Traversal）由葉節點向根節點計算高度並同步驗證平衡因子，可在每個節點僅造訪常數次的前提下，於 $O(n)$ 線性時間內完成驗證。
4. 插入操作的高度不變性（Height Invariant）：AVL 樹插入新節點引發失衡時，透過單旋轉（Single Rotation: LL, RR）或雙旋轉（Double Rotation: LR, RL，亦即 Trinode Restructuring）修正最深失衡節點後，該子樹的高度會精準回復至「插入前」的原高度，因此不平衡狀態不會向更高層的祖先節點傳遞。

解題方法

（一）利用 AVL 樹進行排序之可行性、方法與時間複雜度

可以利用 AVL 樹對鍵值進行排序。此演算法即為樹排序（Tree Sort）的平衡樹優化版本。

• 排序方法：

1. 建樹階段：初始化一棵空的 AVL 樹。將欲排序的 $n$ 個鍵值依序呼叫插入操作（Insert）加入 AVL 樹中。由於 AVL 樹具備自我平衡機制，每次插入均維持平衡。
2. 輸出階段：當 $n$ 個鍵值全數插入後，對此 AVL 樹執行中序走訪（In-order Traversal），將走訪到的鍵值依序輸出，即得到由小到大排列之有序數列。

• 時間複雜度推導：

• 建樹時間：一棵包含 $k$ 個節點的 AVL 樹，其樹高嚴格受限於 $O(\log k)$。因此，插入第 $k$ 個元素的成本為 $O(\log k)$。插入 $n$ 個元素的總建樹時間為： $\sum_{k=1}^{n} O(\log k) = O(\log(n!)) = O(n \log n)$
• 走訪時間：中序走訪每個節點恰好造訪一次，時間複雜度為 $O(n)$。
• 總時間複雜度：建樹時間加上走訪時間，總時間複雜度為： $O(n \log n) + O(n) = O(n \log n)$
• （空間複雜度為儲存樹節點所需之 $O(n)$ 空間）。

（二）線性時間判斷二元搜尋樹是否為 AVL 樹之演算法

題目已知該樹已具備二元搜尋樹（BST）之特性（鍵值滿足 $Left < Root < Right$），故判斷重點在於驗證整棵樹是否滿足 AVL 樹的「平衡因子限制（任一節點 $|h_L - h_R| \le 1$）」。

• 演算法切入點： 若由根節點自頂向下對每個節點呼叫求高度函式，會造成大量重複計算，使時間複雜度退化至 $O(n^2)$。必須採用後序走訪（Post-order Traversal）的由下而上（Bottom-Up）遞迴：

1. 遞迴計算左子樹與右子樹的高度。
2. 若任何子樹失衡，立即回傳特定哨兵值（如 $-1$）提早剪枝終止。
3. 若左右子樹皆平衡，檢查當前節點平衡因子 $|h_L - h_R|$ 是否大於 $1$；若大於 $1$ 則回傳 $-1$，否則回傳當前子樹的真實高度 $\max(h_L, h_R) + 1$。

• 演算法虛擬碼（C/C++ 風格）：

核心觀念

• 無向圖的相鄰矩陣中，若頂點 $u$ 與 $v$ 相鄰，則 $M[u][v]=1$；否則為 $0$。無向圖的矩陣必須對稱，沒有自迴圈時主對角線為 $0$。
• DFS 依指定的鄰點順序，先沿著尚未拜訪的鄰點深入；無向圖中，首次發現頂點時所走的邊構成深度優先樹（DF-tree）。
• 有向無迴圈圖（DAG）的拓樸排序，必須讓每一條有向邊 $u\to v$ 的起點 $u$ 排在終點 $v$ 前面。

（一）無向圖

1. 相鄰矩陣

依字母順序排列頂點為 $a,b,c,d,e,f,g,h$。由圖一可讀出邊為：

因此相鄰矩陣為：

矩陣對稱，且主對角線皆為 $0$，符合此圖是無自迴圈無向圖的性質。

2. 由 $a$ 開始的 DFS 深度優先樹

每次都按字母順序檢查鄰點。由矩陣可得各頂點的鄰點順序，例如 $a$ 的鄰點依序是 $b,d,e,g,h$，$b$ 的鄰點依序是 $a,c,e,f,g$。

搜尋過程的拜訪順序為：

$f$ 沒有尚未拜訪的鄰點後，回到 $c$，再拜訪 $g$；回到 $b$ 後，再依序拜訪 $e$；回到 $a$ 後，再拜訪 $d$，並由 $d$ 拜訪 $h$。完整拜訪順序為：

DF-tree 的樹邊為：

（二）相鄰矩陣上的 DFS 時間複雜度

使用相鄰矩陣時，DFS 每拜訪一個頂點，都要掃描該頂點所在的一整列，檢查是否有通往其他頂點的邊。每列有 $n$ 個位置，共有 $n$ 個頂點，因此：