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

核心觀念

本題考查資料結構中的「刪除順序」。

若一個集合採用「後進先出」（Last In, First Out, LIFO）的規則，則最後插入的元素會最先被刪除。符合此定義的資料結構是 Stack（堆疊）。

堆疊的基本操作如下：

• push：將元素插入堆疊頂端。
• pop：刪除並取出堆疊頂端元素。

因此，若依序插入 $a、b、c$：

$$\text{push}(a),\ \text{push}(b),\ \text{push}(c)$$

堆疊內容由底部到頂部為：

$$[a,b,c]$$

第一次執行 pop 時，刪除的是最晚插入的元素 $c$。

解題方法

題幹關鍵描述為：

the elements deleted from the set is the one most recently inserted

意思是「被刪除的元素，是最近插入的元素」。

將此敘述對應到常見資料結構的刪除規則：

• 最近插入者優先刪除：後進先出（LIFO）
• 最早插入者優先刪除：先進先出（FIFO）
• 依優先權刪除：Priority Queue 或 Heap

後進先出是堆疊的定義，因此正確選項為 Stack。

選項分析

A. Queue

Queue（佇列）遵循先進先出（First In, First Out，FIFO）。

若依序插入 $a、b、c$，刪除順序為：

$$a \rightarrow b \rightarrow c$$

核心觀念

Hash table 以雜湊函數將 key 映射到表格位置，使資料能直接定位。若雜湊函數分布均勻，且負載因子

$$\alpha=\frac{n}{m}$$

維持常數，其中 $n$ 為資料筆數、$m$ 為槽位數，則一次搜尋平均只需檢查常數個位置或鏈結串列節點。

因此，Hash table 的平均搜尋時間為

$$\Theta(1)$$

也就是平均常數時間。

需要注意的是，$\Theta(1)$ 表示「緊確的常數時間界線」；它同時也屬於 $O(1)$，但 $O(1)$ 只表示上界，資訊較不精確。

解題方法

本題問的是 Hash table 在平均情況下執行 search 的時間複雜度。

在理想雜湊條件下：

1. 雜湊函數能將 key 均勻分布。
2. 負載因子 $\alpha$ 維持常數。
3. 每次碰撞所需處理的項目數量平均為常數。

因此：

• 開放定址法平均只需探查常數個槽位。
• Separate chaining 平均只需搜尋長度為常數的鏈結串列。

故平均搜尋時間為

$$T_{\text{average}}=\Theta(1)$$

最壞情況若所有 key 都碰撞到同一位置，則可能退化為

$$T_{\text{worst}}=\Theta(n)$$

但題目問的是平均情況，因此不採用最壞情況答案。

選項分析

A. $\Theta(1)$

正確。

在雜湊函數分布良好、負載因子為常數的前提下，搜尋平均只需處理固定數量的元素，因此平均時間為

$$\Theta(1)$$

核心觀念

本題考的是圖論中的「最小生成樹」（Minimum Spanning Tree, MST）。

若將每棟房屋視為一個頂點，兩棟房屋間可鋪設的電纜視為一條邊，邊的權重代表電纜長度，則問題可表示為：

• 所有房屋都必須互相連通；
• 總電纜長度必須最小；
• 不需要形成迴路，因為迴路只會增加電纜用量。

對一個具有 $V$ 個頂點的連通圖，生成樹恰有：

$$V-1$$

條邊。所有生成樹中，總邊權重最小者稱為最小生成樹。

因此，「以最少電纜連接所有房屋」正是最小生成樹所要解決的問題。

解題方法

將房屋與電纜配置抽象成加權圖：

1. 房屋對應圖中的頂點。
2. 可鋪設的電纜對應圖中的邊。
3. 電纜長度對應邊的權重。
4. 從所有能連接全部房屋的生成樹中，選擇總權重最小者。

常用的求解方法包括：

• Prim’s algorithm
• Kruskal’s algorithm

這些演算法都能找出最小生成樹，達成總電纜長度最小的目標。

選項分析

A. AVL tree

AVL tree 是一種高度平衡的二元搜尋樹，主要用來維持搜尋、插入與刪除操作的效率。

它的重點是樹的平衡性，與「在加權圖中以最小總邊權重連接所有頂點」無關，因此不能直接解決房屋最省電纜配置問題。

此選項錯誤。

B. 2-3 tree

核心觀念

Quicksort 的核心流程是：

1. 選擇一個 pivot。
2. 將資料分割成小於與大於 pivot 的兩部分。
3. 對兩部分遞迴排序。
4. 合併步驟僅需線性掃描，因此每層分割成本為 $O(N)$。

若每次分割較為均勻，遞迴關係可表示為：

$$T(N)=2T\left(\frac{N}{2}\right)+O(N)$$

由主定理：

$$T(N)=O(N\log N)$$

因此，Quicksort 的平均執行時間為 $O(N\log N)$。

解題方法

Quicksort 每一層遞迴都會處理總共約 $N$ 個元素，分割成本為 $O(N)$。

若 pivot 平均能將資料分成大小相近的兩部分，遞迴深度約為：

$$\log_2 N$$

所以總平均成本為：

$$\text{每層成本}\times\text{層數} =O(N)\times O(\log N) =O(N\log N)$$

因此正確選項為 D。

需要注意的是，Quicksort 的最壞情況發生在每次 pivot 都選到最小值或最大值，使分割極度不平衡：

$$T(N)=T(N-1)+O(N)=O(N^2)$$

核心觀念

貪婪演算法（Greedy Algorithm）的基本思想是：

每一步都選擇當下看起來最好的方案，並且通常不回溯，希望藉此得到整體最佳解。

常見的貪婪演算法具有以下特徵：

1. 將問題拆成多個選擇步驟。
2. 每一步選擇目前最有利的元素。
3. 已做出的選擇通常不再修改。
4. 問題必須具備適合貪婪策略的結構，例如貪婪選擇性與最佳子結構。

本題要判斷各選項是否屬於貪婪演算法，或是否為貪婪演算法常使用的實作工具。

---

解題方法

逐一判斷各選項：

• 是否本身是一種貪婪演算法？
• 若不是演算法，是否是貪婪演算法常用的資料結構？
• 是否只是一般資料結構，與貪婪策略沒有直接關係？

Dijkstra's algorithm 與 Huffman codes 都是典型貪婪演算法；priority queue 則常用來支援貪婪選擇。Linked list 只是一般性的線性資料結構，不具備貪婪決策流程。

---

選項分析

A. Dijkstra's algorithm

Dijkstra 演算法用來求解單一來源點到其他各點的最短路徑。

每一步都從尚未確定最短距離的頂點中，選出目前暫定距離最小的頂點，將其視為已確定，接著更新鄰接頂點的距離：

$$dist[v] = \min\left(dist[v],\ dist[u] + w(u,v)\right)$$

其中 $u$ 是目前選出的頂點，$w(u,v)$ 是邊的權重。

這種「每次選擇目前距離最小者」的策略就是貪婪策略，因此 Dijkstra's algorithm 屬於貪婪演算法。

補充：Dijkstra 演算法要求邊權重不可為負數。

---

B. priority queue

Priority queue（優先佇列）本身是一種資料結構，不是完整的演算法；但它經常被用來實作貪婪演算法中的「選出目前最佳元素」操作。

核心觀念

本題考查**循環佇列（circular queue）**的陣列操作。

佇列遵守 FIFO（First In, First Out，先進先出）：

• ENQUEUE：從佇列尾端加入元素。
• DEQUEUE：從佇列頭端移除元素。
• 陣列範圍為 $Q[1..12]$，尾端到達 $Q[12]$ 後，下一格會循環回到 $Q[1]$。

初始佇列內容依序為：

$$15,\ 6,\ 9,\ 8,\ 4$$

其中：

• Head 位於 $Q[7]$，元素為 $15$
• Tail 位於 $Q[11]$，元素為 $4$

解題方法

依序執行三次 ENQUEUE：

1. ENQUEUE(Q,17)

目前尾端在 $Q[11]$，下一個位置為 $Q[12]$：

$$Q[12] = 17$$

佇列變為：

$$15,\ 6,\ 9,\ 8,\ 4,\ 17$$

2. ENQUEUE(Q,3)

尾端已位於 $Q[12]$，循環回到陣列第一格：

$$Q[1] = 3$$

佇列變為：

$$15,\ 6,\ 9,\ 8,\ 4,\ 17,\ 3$$

3. ENQUEUE(Q,5)

下一個位置為 $Q[2]$：

$$Q[2] = 5$$

此時佇列的邏輯順序為：

$$15,\ 6,\ 9,\ 8,\ 4,\ 17,\ 3,\ 5$$

4. DEQUEUE(Q)

核心觀念

Heap（堆）是一棵符合堆序性質的完全二元樹：

• 除最後一層外，其餘各層皆填滿。
• 最後一層的節點由左至右排列。
• 高度 $h$ 通常定義為「根節點到最深葉節點的邊數」，因此根節點高度為 $0$。

本題詢問高度為 $h$ 的 heap，其元素個數下限。堆序性質只影響父子節點的大小關係，不影響節點數量；因此只需分析完全二元樹的結構。

解題方法

高度為 $h$ 表示至少有一個節點位於第 $h$ 層（根為第 $0$ 層）。

為使元素數量最少：

1. 第 $0$ 層至第 $h-1$ 層必須全部填滿。
2. 第 $h$ 層只需放置最左側的一個節點。

前 $h$ 層的節點數為：

$$1+2+2^2+\cdots+2^{h-1} =\sum_{i=0}^{h-1}2^i =2^h-1$$

再加上第 $h$ 層至少需要的 $1$ 個節點：

$$(2^h-1)+1=2^h$$

因此，高度為 $h$ 的 heap 至少有 $2^h$ 個元素。

選項分析

核心觀念

本題考查記憶體碎片化（fragmentation）與自動垃圾回收（automatic garbage collection）。

當程式反覆配置與釋放記憶體時，空閒空間可能被分散在不同位置，形成碎片。即使所有空閒區塊加總後足以配置某個物件，也可能因為沒有一段連續空間而配置失敗。

若垃圾回收器能將仍在使用中的物件全部搬移，使其集中存放於連續區域，便可將剩餘空間合併成一大段連續空間，這種技術稱為：

• Compaction（壓縮）
• Compacting garbage collection（壓縮式垃圾回收）

因此，題目所描述「將所有已配置物件移到連續儲存空間」的機制，正是具備壓縮功能的自動垃圾回收。

解題方法

判斷關鍵在於題幹中的兩個描述：

1. 找出不再使用的物件並回收空間
2. 搬移仍在使用的物件，使其連續排列

第一項是一般垃圾回收的基本功能；第二項則是壓縮式垃圾回收的特徵。

物件搬移後，記憶體可呈現如下形式：

$$\text{已配置物件}_1 \mid \text{已配置物件}_2 \mid \cdots \mid \text{連續空閒空間}$$

原本分散的空閒區域被合併，因此可以消除外部碎片（external fragmentation）。所以正確選項為 A。

選項分析

A. Automatic garbage collection

正確。

Automatic garbage collection 能自動找出不再被程式使用的物件並回收其記憶體。若垃圾回收器進一步將所有仍在使用的物件搬移至連續儲存區域，便能執行 compaction，消除記憶體中的外部碎片。

核心觀念

本題考查紅黑樹（Red-Black Tree）的高度上界。紅黑樹具有下列重要性質：

1. 每個節點不是紅色就是黑色。
2. 根節點為黑色。
3. 紅色節點的子節點必為黑色，因此不會出現連續兩個紅色節點。
4. 從任一節點到其後代 NIL 葉節點的每條路徑，都包含相同數量的黑色節點。

紅黑樹透過限制紅色節點不能連續出現，使得樹高至多是理想平衡樹高度的兩倍。因此，含有 $n$ 個內部節點的紅黑樹，其高度滿足：

$$h \leq 2\log_2(n+1)$$

---

解題方法與推導

令 $bh$ 表示根節點的 black-height，即從根到 NIL 葉節點路徑上的黑色節點數量。

由於紅色節點不能連續出現，所以在任一路徑上，紅色節點數量不會多於黑色節點數量。因此：

$$h \leq 2bh$$

另一方面，black-height 為 $bh$ 的紅黑樹，至少包含如完全二元樹般的節點數量，因此：

$$n \geq 2^{bh}-1$$

移項可得：

$$n+1 \geq 2^{bh}$$

兩邊取以 $2$ 為底的對數：

$$bh \leq \log_2(n+1)$$

配合 $h\leq 2bh$，得到：

$$h\leq 2\log_2(n+1)$$

所以正確選項為 B。

---

選項分析

核心觀念

本題考查 linked list（鏈結串列）中的 sentinel（哨兵節點）。

Sentinel 是一個不代表實際資料的 dummy object（虛擬物件），通常放在鏈結串列的開頭、結尾，或同時放在兩端，用來統一處理特殊情況，例如：

• 空串列；
• 插入第一個節點；
• 刪除第一個節點；
• 插入或刪除最後一個節點；
• 遍歷至串列邊界。

加入 sentinel 後，許多節點操作不必特別判斷「目前是否位於串列第一個節點」，因此可以簡化邊界條件。

例如，原本刪除第一個節點時，可能需要更新 head；若使用 dummy head 作為 sentinel，則只需統一修改前驅節點的連結：

$$\text{prev.next} \leftarrow \text{prev.next.next}$$

其中 prev 可以是 sentinel，不必為第一個實際資料節點。

解題方法

題幹中的關鍵描述是：

a dummy object that is widely used in linked list in order to simplify boundary conditions

其中：

• dummy object 指不儲存實際資料、專門協助操作的虛擬物件；
• simplify boundary conditions 指簡化串列開頭、結尾與空串列等特殊情況。

符合這個定義的術語就是 Sentinel。

因此正確選項為 A。

選項分析

A. Sentinel

正確。

核心觀念

本題考查最大堆積（Max-Heap）的插入操作。

最大堆積必須同時符合：

1. 完全二元樹：新元素必須先放在下一個可用位置，也就是陣列最後。
2. 最大堆積性質：每個父節點的值皆大於或等於其子節點。

若採用 1-based index，節點索引關係為：

$$\text{Parent}(i)=\left\lfloor \frac{i}{2}\right\rfloor$$

插入新元素後，若新元素大於父節點，就持續向上交換，此過程稱為 Max-Heapify-Up 或 Bubble-Up。

---

解題方法

原本的最大堆積為：

$$A=\langle 15,13,9,5,12,8,7,4,0,6,2,1\rangle$$

其索引如下：

索引	1	2	3	4	5	6	7	8	9	10	11	12
值	15	13	9	5	12	8	7	4	0	6	2	1

步驟一：將 10 放到陣列最後

為維持完全二元樹結構，先將 10 放在索引 13：

$$A=\langle 15,13,9,5,12,8,7,4,0,6,2,1,10\rangle$$

此時 10 的父節點索引為：

$$\left\lfloor \frac{13}{2}\right\rfloor=6$$

父節點為 $A[6]=8$。

由於：

$$10>8$$

因此交換索引 13 與索引 6：

$$A=\langle 15,13,9,5,12,10,7,4,0,6,2,1,8\rangle$$

---

步驟二：繼續向上比較

10 現在位於索引 6，其父節點索引為：

核心觀念

本題考查樹或圖形的走訪順序：

• Pre-order traversal（前序走訪）：先訪問目前節點，再依序走訪子樹。
• Post-order traversal（後序走訪）：先依序走訪所有子樹，最後訪問目前節點。
• Depth-first order traversal（深度優先走訪）：沿著一條分支深入到底，再回溯走訪其他分支；若為樹，通常可用堆疊實作。

若圖形為一般圖，還必須指定起始節點，以及相鄰節點的訪問順序；否則走訪結果不唯一。

解題方法

依照 Fig. 1 的根節點或起始節點，逐步記錄：

1. 前序：節點第一次被抵達時立即記錄。
2. 後序：該節點的所有子節點都完成走訪後才記錄。
3. 深度優先：使用 DFS，沿目前分支持續深入；遇到已訪問節點不得重複走訪。

例如樹結構為：

    A
   / \
  B   C

則：

核心觀念

本題比較四種雜湊碰撞處理方法。雜湊表大小取 $10$，索引為 $0$ 至 $9$，主雜湊函數為：

$$h(x)=x\bmod 10$$

各資料的初始雜湊位置如下：

$x$	$h(x)$
89	9
18	8
49	9
58	8
69	9

當不同資料映射到同一索引時，就會發生碰撞。

---

A：Separate Chaining

Separate chaining 將每個索引設為一條鏈結串列；碰撞資料放在同一個 bucket 中，不需要尋找其他空位。

依照輸入順序插入：

• $89$：放入索引 $9$
• $18$：放入索引 $8$
• $49$：映射至 $9$，與 $89$ 碰撞，接在索引 $9$ 的鏈上
• $58$：映射至 $8$，與 $18$ 碰撞，接在索引 $8$ 的鏈上
• $69$：映射至 $9$，接在索引 $9$ 的鏈上

雜湊表為：

索引	鏈結內容
0	—
1	—
2	—
3	—
4	—
5	—
6	—
7	—
8	$18\rightarrow58$
9	$89\rightarrow49\rightarrow69$

---

B：Linear Probing

Linear probing 發生碰撞時，依序檢查下一個位置：

$$h_i(x)=(h(x)+i)\bmod 10,\qquad i=0,1,2,\ldots$$

依照輸入順序：

1. $89$：$h(89)=9$，索引 $9$ 空，放入 $9$。
2. $18$：$h(18)=8$，索引 $8$ 空，放入 $8$。
3. $49$：初始位置 $9$ 已被 $89$ 佔用，檢查索引 $0$，放入 $0$。
4. $58$：初始位置 $8$ 被佔用，依序檢查 $9$、$0$，皆被佔用；索引 $1$ 空，放入 $1$。
5. $69$：初始位置 $9$ 被佔用，依序檢查 $0$、$1$；索引 $2$ 空，放入 $2$。

雜湊表為：

索引	內容
0	49
1	58
2	69
3	—
4	—
5	—
6	—
7	—
8	18
9	89

---

C：Quadratic Probing

quadratic probing 以平方數作為探查間隔：

$$h_i(x)=(h(x)+i^2)\bmod 10,\qquad i=0,1,2,\ldots$$

依照輸入順序：

1. $89$：探查 $9$，放入索引 $9$。
2. $18$：探查 $8$，放入索引 $8$。
3. $49$：
   • $i=0$：$(9+0^2)\bmod10=9$，已被佔用。
   • $i=1$：$(9+1^2)\bmod10=0$，空，放入索引 $0$。
4. $58$：
   • $i=0$：$8$，已被 $18$ 佔用。
   • $i=1$：$9$，已被 $89$ 佔用。
   • $i=2$：$(8+2^2)\bmod10=2$，空，放入索引 $2$。
5. $69$：
   • $i=0$：$9$，已被佔用。
   • $i=1$：$0$，已被 $49$ 佔用。
   • $i=2$：$(9+2^2)\bmod10=3$，空，放入索引 $3$。

雜湊表為：

索引	內容
0	49
1	—
2	58
3	69
4	—
5	—
6	—
7	—
8	18
9	89

---

D：Double Hashing

第二雜湊函數為：

$$h_2(x)=7-(x\bmod 7)$$

核心觀念

本題考查 Huffman coding。Huffman coding 是一種依照字元出現頻率建立變動長度前綴碼的方法：

• 出現頻率越高的字元，通常配置越短的編碼。
• 出現頻率越低的字元，通常配置越長的編碼。
• 每個字元的編碼皆不可成為另一個字元編碼的前綴，因此可直接解碼。
• 建樹時反覆取出頻率最小的兩個節點合併，合併後再放回節點集合，直到只剩根節點。

本題各字元頻率如下：

字元	頻率
newline	1
s	3
t	4
a	10
i	12
space	13
e	15

---

解題方法

每次選取目前頻率最小的兩個節點合併。合併時，左分支標記為 $0$，右分支標記為 $1$。

第一步：合併 newline 與 s

$$1+3=4$$

形成節點：

$$N_1=(newline,s),\qquad f(N_1)=4$$

目前頻率為：

$$4,\ 4,\ 10,\ 12,\ 13,\ 15$$

其中兩個頻率為 $4$ 的節點分別是 $t$ 與 $N_1$。

第二步：合併 t 與 $N_1$

$$4+4=8$$

形成：

$$N_2=(t,N_1),\qquad f(N_2)=8$$

目前頻率為：

$$8,\ 10,\ 12,\ 13,\ 15$$

第三步：合併 a 與 $N_2$

$$10+8=18$$

形成：

$$N_3=(a,N_2),\qquad f(N_3)=18$$

目前頻率為：

$$12,\ 13,\ 15,\ 18$$

第四步：合併 i 與 space

$$12+13=25$$

形成：

$$N_4=(i,space),\qquad f(N_4)=25$$

目前頻率為：

$$15,\ 18,\ 25$$

第五步：合併 e 與 $N_3$

$$15+18=33$$

形成：

$$N_5=(e,N_3),\qquad f(N_5)=33$$

目前頻率為：

$$25,\ 33$$

第六步：合併 $N_4$ 與 $N_5$

$$25+33=58$$

形成 Huffman tree 的根節點。

---

Huffman 樹

以下採用左分支為 $0$、右分支為 $1$：

                         (58)
                       /      \
                    0 /        \ 1
                    (25)       (33)
                   /   \       /   \
                0 /     \ 1 0 /     \ 1
                 i       space e     (18)
                                        / \
                                     0 /   \ 1
                                      a     (8)
                                           / \
                                        0 /   \ 1
                                         t     (4)
                                               / \
                                            0 /   \ 1
                                             newline s

各節點的權重為：

• 根節點：$58$
• $i+space=12+13=25$
• $e+(a+(t+(newline+s)))=15+18=33$
• $a+(t+(newline+s))=10+8=18$
• $t+(newline+s)=4+4=8$
• $newline+s=1+3=4$

---