109 年 國立成功大學會計學研究所乙組《資料結構》

核心觀念

Priority queue（優先佇列）是一種抽象資料型態，每個元素具有優先權，刪除操作不是依照先進先出，而是優先移除優先權最高或最低的元素。

以最大優先佇列為例，主要操作如下：

• insert：加入元素
• find-max：找出最高優先權元素
• delete-max：移除最高優先權元素

Binary heap（二元堆積）必須滿足：

1. 完整二元樹：除最後一層外，其餘各層皆填滿，最後一層由左至右排列。
2. 堆積順序性：最大堆中，父節點值不小於子節點；最小堆中，父節點值不大於子節點。

因此，最高或最低優先權元素會固定位於根節點，能有效支援優先佇列操作。

---

解題方法

判斷資料結構是否適合實作優先佇列，重點在於比較「插入」與「刪除最高優先權元素」的時間複雜度。

使用 binary heap 時：

• 最高優先權元素位於根節點，查看最高優先權為 $O(1)$。
• 插入元素時，先放在樹的末端，再逐層向上調整，時間為 $O(\log n)$。
• 刪除根節點時，以最後一個節點補至根部，再逐層向下調整，時間為 $O(\log n)$。

整理如下：

操作	Binary heap 時間複雜度
查看最高優先權	$O(1)$
插入	$O(\log n)$
刪除最高優先權	$O(\log n)$

這是優先佇列常見且高效率的實作方式，因此正確答案為 Heap。

---

選項分析

(a) Array：錯誤

陣列可以實作優先佇列，但效率取決於元素是否排序。

• 未排序陣列：插入可為 $O(1)$，但刪除最高優先權元素必須搜尋全陣列，為 $O(n)$。
• 已排序陣列：刪除最高優先權元素可為 $O(1)$，但插入時須維持排序，最差為 $O(n)$。

核心觀念

題目中的 priority query 依選項語境是指「優先佇列（priority queue）」的應用。

優先佇列中的每筆資料都具有優先權，刪除或處理資料時，優先處理優先權最高者。其核心操作為：

• insert：加入具有優先權的資料。
• delete-min：取出優先權最小者。
• delete-max：取出優先權最大者。

常見實作方式是 heap。優先佇列常用於資料壓縮、作業系統、排程、圖形演算法與垃圾郵件過濾等情境。相關課程教材亦將 Huffman codes、interrupt handling 與 Bayesian spam filter 列為優先佇列應用。

解題方法

逐一判斷各選項是否需要「依優先權選出下一筆要處理的資料」：

• 若是依優先權取出資料，屬於優先佇列應用。
• 若是依照最後加入、最先取出的後進先出（LIFO）原則，則屬於 stack 應用，而非優先佇列。

選項分析

(a) Huffman codes：正確，屬於優先佇列應用

Huffman coding 每次選出頻率最低的兩個節點合併，形成新的樹節點，再將新節點放回集合中。

若以節點頻率作為優先權，流程為：

1. 取出頻率最小的兩個節點。
2. 合併成頻率總和的新節點。
3. 將新節點重新插入優先佇列。
4. 重複上述步驟，直到只剩一個根節點。

因此可使用 min-heap 有效率地實作。

(b) Interrupt handling in operating system：正確，屬於優先佇列應用

核心觀念

ArrayIndexOutOfBoundsException 是 Java 在存取陣列時，索引值超出合法範圍所拋出的例外。

若陣列長度為 $n$，合法索引範圍為：

$$0 \leq \text{index} < n$$

當程式執行期間使用小於 $0$ 或大於等於 $n$ 的索引存取陣列，就會發生 ArrayIndexOutOfBoundsException。

例如：

int[] a = {10, 20, 30};
System.out.println(a[3]);

陣列 a 的長度為 $3$，合法索引只有 $0、1、2$；索引 $3$ 超出範圍，因此執行時會拋出例外。

此例外屬於：

ArrayIndexOutOfBoundsException
    └── IndexOutOfBoundsException
        └── RuntimeException

因此它是執行時例外（run-time exception），也是 unchecked exception。

解題方法

判斷此題的關鍵在於：Java 陣列索引是否超出範圍，通常必須等程式實際執行到該敘述時，才能根據當時的索引值與陣列長度判斷。

例如：

int i = getIndex();
int[] a = new int[5];
System.out.println(a[i]);

核心觀念

本題考查陣列的兩項重要特性：

1. 連續記憶體配置：陣列元素通常連續存放。
2. 索引直接存取：透過索引可在 $O(1)$ 時間取得元素。

這些特性使陣列特別適合：

• 建立高速快取（cache）。
• 利用空間區域性（spatial locality）提升記憶體存取效率。

其中，空間區域性是指：程式存取某個記憶體位置後，近期很可能會存取其附近的位置。陣列因元素連續排列，天然適合展現此特性。

解題方法

判斷各選項是否「大量使用陣列」，可觀察該概念是否依賴：

• 連續記憶體配置；
• 索引存取；
• 頻繁存取相鄰資料；
• 以固定位置快速查找資料。

符合上述條件者，通常與陣列關係密切。

選項分析

a) Binary trees（二元樹）

二元樹通常以節點與指標表示，每個節點包含資料、左子節點指標與右子節點指標：

$$\text{Node} = (\text{data}, \text{left}, \text{right})$$

若二元樹為一般形狀，使用陣列儲存可能造成大量空間浪費。陣列表示法最適合完全二元樹，例如 heap，此時可使用下列索引關係：

• 若父節點索引為 $i$，左子節點為 $2i$；
• 右子節點為 $2i+1$；
• 父節點為 $\lfloor i/2 \rfloor$。

但一般二元樹並不大量依賴陣列，故此選項錯誤。

b) Scheduling of processes（程序排程）

程序排程常使用佇列、優先佇列、堆積等資料結構。例如：

核心觀念

AVL tree 是一種自我平衡的二元搜尋樹（Self-Balancing Binary Search Tree），名稱來自 Adelson-Velsky 與 Landis。

其核心定義是：對樹中的每一個節點，其左、右子樹高度差的絕對值不得超過 $1$。設節點 $v$ 的平衡因子為：

$$BF(v)=h(\text{左子樹})-h(\text{右子樹})$$

則 AVL tree 必須滿足：

$$|BF(v)|\leq 1$$

因此，AVL tree 同時具備：

1. 二元搜尋樹的性質：左子樹鍵值小於節點，右子樹鍵值大於節點。
2. 高度平衡的性質：每個節點的左右子樹高度差最多為 $1$。

藉由旋轉操作維持平衡後，AVL tree 的搜尋、插入與刪除時間複雜度皆可維持為 $O(\log n)$。

解題方法

本題直接辨認 AVL tree 的定義即可。判斷關鍵在於「balanced」與「height balanced」：

• AVL tree 是一種平衡樹。
• 更精確地說，AVL tree 是一種高度平衡二元搜尋樹。
• 高度平衡的判定條件為每個節點皆滿足 $|BF|\leq 1$。

因此，符合 AVL tree 定義的是選項 a。

選項分析

(a) a tree which is balanced and is a height balanced tree

核心觀念

Max-heap（最大堆積）是一種符合以下條件的完全二元樹：

對每一個非根節點，其父節點的鍵值都不小於子節點：

$$\text{key(parent)} \geq \text{key(child)}$$

因此，根節點的鍵值會大於或等於整棵樹中所有其他節點的鍵值。換言之，最大堆積的最大元素一定位於根節點。

解題方法

由最大堆積的定義，從根節點往下的每一條路徑，鍵值都不會增加。若某個子孫節點的鍵值大於根節點，便會違反最大堆積的條件。

所以：

$$\text{最大鍵值} = \text{根節點的鍵值}$$

因此正確答案為選項 c。

選項分析

a) Leaf node

錯誤。Leaf node（葉節點）沒有子節點，但最大元素不必位於葉節點。最大堆積的最大元素必定在根節點；葉節點可能包含較小的鍵值。

核心觀念

本題考查「建立 Heap 的時間複雜度」。建立 Heap 常見有兩種方法：

1. 將 $n$ 個元素逐一插入空 Heap。
2. 先將元素放入陣列，再採用 Bottom-up Heap Construction，自最後一個非葉節點向下調整。

題目選項中沒有 $O(n)$，因此依選項設計，採用「逐一插入元素」的建立方式。

對大小為 $k$ 的 Heap 插入一個元素時，最壞情況須向上調整，Heap 高度為 $O(\log k)$，故單次插入時間為 $O(\log k)$。

---

解題方法

逐一插入 $n$ 個元素時，第 $k$ 個元素的插入成本為：

$$O(\log k)$$

因此總時間複雜度為：

$$\sum_{k=1}^{n} O(\log k) = O(\log 1+\log 2+\cdots+\log n)$$

由於每一項最多為 $\log n$，共有 $n$ 項，因此：

$$\sum_{k=1}^{n} O(\log k) = O(n\log n)$$

所以，按照選項所對應的逐一插入建立法，建立 Heap 的時間複雜度為：

$$O(n\log n)$$

---

選項分析

• a) $O(n*n*\log n)$

  錯誤。建立 Heap 並不需要對每個元素再進行 $O(n\log n)$ 的完整處理，因此不會達到 $O(n^2\log n)$。

• b) $O(n\log n)$

核心觀念

本題考查「外部記憶體資料結構」與不同平衡搜尋樹的適用情境。

外部記憶體（external memory）是指磁碟、SSD 等儲存裝置。相較於主記憶體，外部記憶體的存取速度較慢，因此設計資料結構時，重點不只在於比較鍵值的次數，也要盡量減少磁碟區塊（block）的讀寫次數。

外部記憶體資料結構通常具備以下特性：

• 一個節點可儲存大量鍵值與子樹指標。
• 節點大小通常配合磁碟區塊大小。
• 樹的高度較低，可減少磁碟存取次數。
• 每次讀取一個節點時，能取得大量相關資料。

$B$-tree 正是為外部記憶體設計的多路平衡搜尋樹。若每個節點最多有 $m$ 個子節點，且樹高為 $h$，搜尋成本大致與 $h$ 次磁碟區塊存取有關。由於每個節點可容納許多鍵值，$B$-tree 的高度通常遠低於二元搜尋樹。

---

解題方法

判斷某種樹是否適合外部記憶體，主要觀察兩點：

1. 節點是否能儲存大量資料。
2. 是否能以較低樹高完成搜尋，降低磁碟 I/O 次數。

$AVL$ tree 與 red-black tree 都是二元搜尋樹，每個節點最多只有兩個子樹。因此，即使它們能維持平衡，樹高仍大致為 $O(\log_2 n)$。

$B$-tree 則是多路搜尋樹。一個節點可有許多子節點，若分支數為 $m$，樹高約為：

$$O(\log_m n)$$

由於 $m$ 通常很大，$\log_m n$ 明顯小於 $\log_2 n$。此外，一個 $B$-tree 節點可直接對應一個磁碟區塊，讀取一個節點便能取得大量鍵值與指標，因此能有效降低外部記憶體存取次數。

所以，最適合且最廣泛使用於外部記憶體的資料結構是 $B$-tree$。

---

選項分析

a) AVL tree

錯誤。

$AVL$ tree 是高度平衡的二元搜尋樹，對每個節點都要求左右子樹高度差最多為 $1$。它能保證搜尋、插入與刪除的時間複雜度為：

$$O(\log_2 n)$$

$AVL

核心觀念

本題考查 B+ tree 的存取特性。

B+ tree 是多路平衡搜尋樹，具有以下特徵：

• 內部節點只儲存索引鍵與子樹指標。
• 所有實際資料紀錄都儲存在葉節點。
• 葉節點通常依鍵值排序，並以指標串接成 linked list。
• 從根節點到任一葉節點的高度相同，因此樹高維持平衡。

因此，B+ tree 同時適合：

1. 依索引快速尋找特定資料，也就是隨機存取。
2. 依鍵值順序讀取連續資料，也就是循序存取。

---

解題方法

1. 判斷隨機存取能力

若要尋找特定鍵值，從根節點開始，依索引逐層往下走到葉節點。

由於 B+ tree 為平衡樹，搜尋特定資料的時間複雜度約為：

$$O(\log_B N)$$

其中：

• $N$ 為資料筆數；
• $B$ 為每個節點可容納的分支數。

由於每個節點可存放大量索引，B+ tree 的高度通常很低，適合磁碟或資料庫索引的快速查找。

2. 判斷循序存取能力

B+ tree 的葉節點按照鍵值排序，且相鄰葉節點之間通常有鏈結指標。

搜尋到第一筆資料後，可以沿著葉節點的鏈結指標依序讀取後續資料，不必反覆從根節點開始搜尋。因此，讀取連續 $k$ 筆資料的成本約為：

$$O(\log_B N + k)$$

其中 $O(\log_B N)$ 是先找到起始位置的成本，$O(k)$ 是依序讀取後續資料的成本。

這表示 B+ tree 不只支援快速隨機存取，也支援快速循序存取。

---

選項分析

a) B+ tree allows only the rapid random access

錯誤。

核心觀念

漢諾塔（Tower of Hanoi）具有遞迴結構。若有 $n$ 個盤子，將其由起點柱移到目標柱，必須：

1. 先將上方 $n-1$ 個盤子移到輔助柱。
2. 將最大的第 $n$ 個盤子移到目標柱。
3. 再將 $n-1$ 個盤子由輔助柱移到目標柱。

其遞迴關係為：

$$T(n)=2T(n-1)+1$$

且 $T(0)=0$，因此總移動次數為：

$$T(n)=2^n-1$$

每一次遞迴呼叫都必須記錄目前的盤子數量、來源柱、輔助柱與目標柱。遞迴函式執行時，這些尚未完成的工作會依照「後進先出」（Last In, First Out, LIFO）順序保存，正好符合堆疊（Stack）的特性。

---

解題方法

漢諾塔通常以遞迴方式求解，例如：

Hanoi(n, source, auxiliary, target):
    if n == 1:
        將盤子由 source 移到 target
    else:
        Hanoi(n-1, source, target, auxiliary)
        將第 n 個盤子由 source 移到 target
        Hanoi(n-1, auxiliary, source, target)

當執行 Hanoi(n-1, ...) 時，原本的 Hanoi(n, ...) 尚未完成，必須暫停並保存其執行資訊。等較內層的遞迴完成後，才回到上一層繼續執行。

這種執行順序如下：

• 最後被暫停的遞迴呼叫最先恢復。
• 最先被暫停的遞迴呼叫最後恢復。

核心觀念

本題分別考查四個重要概念：

1. 以「鍵值」存取資料的抽象資料型態。
2. 不損失原始資訊的資料壓縮方法。
3. 描述正規語言的形式化工具。
4. 將物品配置到容量有限容器中的最佳化問題。

---

a) Associative array（關聯陣列）

定義與核心觀念

Associative array 是一種以「鍵（key）」對應「值（value）」的資料結構，也稱為：

• Map
• Dictionary
• Symbol table

一般陣列通常以整數索引存取資料：

$$A[3] = \text{某個值}$$

關聯陣列則可以使用字串或其他可比較的鍵：

$$D[\text{"Alice"}] = 85$$

其中 "Alice" 是鍵，$85$ 是對應的值。一個鍵通常對應一個值，且鍵具有唯一性。

基本操作

關聯陣列通常支援下列操作：

• insert(key, value)：新增鍵值配對。
• search(key) 或 get(key)：依鍵查詢值。
• delete(key)：刪除指定鍵。
• update(key, value)：修改指定鍵的值。
• contains(key)：判斷某鍵是否存在。

例如：

$$D[\text{"CSIE"}] = 90$$

查詢 D["CSIE"] 即可得到 $90$。

常見實作方式

1. 雜湊表（Hash Table）

使用雜湊函數將鍵轉換成陣列索引：

$$index = h(key)$$

平均情況下，搜尋、新增、刪除的時間複雜度為：

$$O(1)$$

若發生大量碰撞，最壞情況可能退化為：

$$O(n)$$

2. 二元搜尋樹

若以平衡二元搜尋樹實作，搜尋、新增、刪除通常為：

$$O(\log n)$$

此方法能維持鍵的排序順序，適合需要範圍查詢或依序列印資料的情況。

解題技巧與常見陷阱

關聯陣列的重點不是「連續整數索引」，而是「透過任意鍵取得對應值」。因此：

• array[5] 不一定是關聯陣列。
• student["姓名"]、phoneBook["王小明"] 都是典型關聯陣列。
• 關聯陣列主要描述的是抽象功能，實作方式可以是雜湊表、平衡樹或其他結構。

---

b) Lossless compression（無失真壓縮）

定義與核心觀念

Lossless compression 是指壓縮後的資料，經過解壓縮可以完全還原成原始資料：

$$\text{Decompress}(\text{Compress}(x)) = x$$

壓縮過程不會遺失任何資訊，因此適合用於：

• 文字檔
• 程式原始碼
• 資料庫
• 執行檔
• 需要逐位元正確還原的文件

與之相對的是 Lossy compression（失真壓縮），例如 JPEG、MP3，會捨棄部分資訊以換取較高壓縮率。

基本方法

無失真壓縮通常利用資料中的重複性或統計規律。

1. Run-Length Encoding（RLE）

連續出現相同符號時，以「符號＋重複次數」表示。

原始資料：

$$AAAAABBBCC$$

可表示為：

$$A5B3C2$$

解碼後仍可完整得到原始資料。

2. Huffman Coding

Huffman Coding 根據符號出現頻率建立變動長度編碼：

• 出現頻率高的符號使用較短編碼。
• 出現頻率低的符號使用較長編碼。
• 編碼具有 prefix-free 特性，任何符號的編碼都不是另一符號編碼的前綴，因此可以唯一解碼。

Huffman Tree 通常以頻率最低的兩個節點反覆合併建立。

3. Dictionary-based compression

以字典記錄重複出現的字串，常見方法包括：

• LZ77
• LZ78
• LZW

若資料中有大量重複片段，便可用字典索引取代原本較長的內容。

壓縮率

常用壓縮率表示為：

$$\text{Compression Ratio} = \frac{\text{壓縮後大小}}{\text{壓縮前大小}}$$

此比例越小，代表壓縮效果越好。也可使用節省比例：

$$\text{Saving} = 1- \frac{\text{壓縮後大小}}{\text{壓縮前大小}}$$

解題技巧與常見陷阱

判斷是否為無失真壓縮，關鍵在於「能否完全還原」：

• ZIP、GZIP、Huffman、LZW：屬於無失真壓縮。
• JPEG、MP3、MPEG：通常屬於失真壓縮。
• 無失真壓縮不代表檔案一定變小。若資料本身缺乏規律，加入編碼資訊後大小甚至可能增加。
• 「還原相近」不等於無失真；必須逐位元或逐字元完全一致。

---

c) Regular expression（正規表示式）

定義與核心觀念

Regular expression 是用來描述一組字串規則的表示法，所描述的語言稱為正規語言（regular language）。

正規表示式可用於：

• 搜尋文字
• 驗證輸入格式
• 字串擷取
• 編譯器詞法分析
• 表單資料檢查

例如，表示只包含數字的字串：

$$[0-9]^+$$

其中 $+$ 表示前面的模式至少出現一次。

基本運算子

1. 串接（Concatenation）

若：

$$R = ab$$

表示字串必須先出現 a，再出現 b。

2. 聯集（Union）

以 | 表示：

$$a|b$$

表示字串可以符合 a 或 b。

3. Kleene Star

以 * 表示前一個模式出現零次以上：

$$a^*$$

可接受：

$$\epsilon,\ a,\ aa,\ aaa,\ldots$$

其中 $\epsilon$ 是空字串。

4. Kleene Plus

以 + 表示前一個模式出現一次以上：

$$a^+$$

核心觀念

本題考查二元搜尋樹（Binary Search Tree, BST）的建立。

對任一節點，BST 必須符合：

• 左子樹所有鍵值小於節點鍵值；
• 右子樹所有鍵值大於節點鍵值。

插入新數值時，從根節點開始比較：

• 若新值較小，往左子樹走；
• 若新值較大，往右子樹走；
• 抵達空位置後，將新節點插入該處。

題目含有重複值 $10$，以下採用常見規則：重複值一律插入右子樹。

---

解題方法與插入過程

依題目順序逐一插入：

插入值	插入位置
$13$	作為根節點
$3$	$13$ 的左子節點
$4$	$3$ 的右子節點
$12$	$4$ 的右子節點
$14$	$13$ 的右子節點
$10$	$12$ 的左子節點
$5$	$10$ 的左子節點
$1$	$3$ 的左子節點
$8$	$5$ 的右子節點
$2$	$1$ 的右子節點
$7$	$8$ 的左子節點
$9$	$8$ 的右子節點
$11$	$第一個\ 10$ 的右子樹中，成為重複 $10$ 的右子節點
$6$	$7$ 的左子節點
$18$	$14$ 的右子節點

以幾個關鍵節點為例：

插入 $10$ 時：

$$13\rightarrow 3\rightarrow 4\rightarrow 12$$

因為 $10<12$，所以插入 $12$ 的左側。

插入 $5$ 時：

$$13\rightarrow 3\rightarrow 4\rightarrow 12\rightarrow 10$$

因為 $5<10$，所以插入第一個 $10$ 的左側。

插入第二個 $10$ 時，遇到原本的 $10$，依重複值放右側的規則，繼續往右；而右側尚無節點，因此成為原本 $10$ 的右子節點。

---

最後形成的二元搜尋樹

核心觀念

Dijkstra 演算法適用於邊權重皆為非負數的有向圖。每一步從尚未確定最短距離的節點中，選出目前暫定距離最小者，將其距離定案，再用它更新相鄰節點的暫定距離。

若目前已知從來源到節點 $u$ 的距離為 $d(u)$，而邊 $u\to v$ 的權重為 $w(u,v)$，則更新公式為：

$$d(v)\leftarrow \min\bigl(d(v),\ d(u)+w(u,v)\bigr)$$

本題由圖可讀得有向邊：$1\to2$（1）、$1\to3$（12）、$2\to3$（9）、$2\to4$（3）、$4\to3$（4）、$3\to5$（5）、$4\to5$（13）、$4\to6$（15）、$5\to6$（4）。

解題方法與步驟

以節點 1 為來源。表中「暫定距離」依序記為 $(d_1,d_2,d_3,d_4,d_5,d_6)$；$\infty$ 表示目前尚無已知路徑。

步驟	定案節點	更新內容	更新後暫定距離
初始化	—	$d_1=0$，其餘設為 $\infty$	$(0,\infty,\infty,\infty,\infty,\infty)$
1	1	$1\to2$：$0+1=1$；$1\to3$：$0+12=12$	$(0,1,12,\infty,\infty,\infty)$
2	2	$2\to3$：$1+9=10$，比 12 小；