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

核心觀念

線性搜尋（linear search）是從單向鏈結串列的起點開始，依序比較每個節點的 data 與目標值。單向鏈結串列只能透過 next 前往下一個節點，因此最壞情況下須走訪整個串列。

以下方法在找到目標時回傳該節點；搜尋到串列尾端仍未找到時回傳 null。若有重複值，回傳從串列起點遇到的第一個符合節點。

解題方法

假設方法接收串列起點 head 與搜尋目標 target，且 head 為 null 代表空串列。

迴圈方式

static Node linearSearchIterative(Node head, int target) {
 Node current = head;

 while (current != null) {
 if (current.data == target) {
 return current;
 }
 current = current.next;
 }

 return null;
}

current 由 head 開始逐節點向後移動。每次先檢查目前節點；相符就回傳，否則移至 current.next。當 current == null 時，表示已走到串列尾端，整串串列都沒有目標值。

遞迴方式

核心觀念

本題比較四種樹狀結構的兩項性質：

• Balance：樹高是否受到結構規則控制，使左右子樹高度大致平衡。
• Searching Tree：是否具有搜尋樹的順序性；本題採左小右大，且每個節點的子樹鍵值具有區間順序。

以下依數列順序逐筆插入建立；Heap 採一般逐筆插入並向上調整。

一、AVL tree

AVL tree 要求每個節點的平衡因子滿足：

依序插入時，主要旋轉如下：

• 插入 $30$：形成 RR，對 $0$ 左旋。
• 插入 $80$：形成 RR，對 $30$ 左旋。
• 插入 $40$：形成 RR，對 $10$ 左旋。
• 插入 $60$：形成 LL，對 $80$ 右旋。

最後的 AVL tree 為：

 50
 / \
 30 70
 / \ / \
 10 40 60 80
 / \ \
 0 20 90

AVL tree 經過旋轉維持高度平衡，因此 Balance = yes；同時符合左小右大的搜尋順序，因此 Searching Tree = yes。

二、Min heap

Min heap 必須滿足：

逐筆插入並向上調整後，陣列表示為：

其樹形如下：

 0
 / \
 10 30
 / \ / \
 20 50 80 40
 / \ /
 90 70 60

每個父節點均小於或等於子節點，符合 Min heap 定義。Heap 使用完全二元樹，因此具有結構上的平衡性，但節點並未依左小右大排列。

所以：

• Balance = yes
• Searching Tree = no

三、Max heap

Max heap 必須滿足：

逐筆插入並向上調整：

• 插入 $10$ 後，$10$ 上移。
• 插入 $30$ 後，$30$ 上移。
• 插入 $20$ 後，$20$ 上移。
• 插入 $50,80,40,90,70,60$ 時，分別依父子大小關係向上調整。

最後陣列表示為：

樹形如下：

 90
 / \
 70 80
 / \ / \
 40 60 10 50
 / \ /
 0 20 30

每個父節點均大於或等於子節點，符合 Max heap 定義。Heap 的完全二元樹結構具有平衡性，但不具左小右大的搜尋樹順序。

所以：

• Balance = yes
• Searching Tree = no

核心觀念

Huffman Tree 以「由根節點走到葉節點」的路徑作為數字編碼：

• 向左走記為 $0$
• 向右走記為 $1$
• 走到葉節點時，得到一個數字
• 依序切割編碼字串，直到全部讀完

依圖可得各數字編碼：

解題方法

將題目字串由左至右依照上述編碼切割：

$010101111101001000011$

切割結果為：

核心觀念

本題考查：

1. BFS 使用 queue，採先進先出（FIFO）。
2. DFS 使用 stack，採後進先出（LIFO）。
3. processSet 在節點加入 queue 或 stack 時立即記錄，避免同一節點重複加入。
4. 多個可走訪節點依邊的 cost 由小到大處理。
5. BFS 的走訪順序受 queue 影響；DFS 的走訪順序受 stack 的「最後 push 者先 pop」影響。

依圖可讀得主要邊如下：

• $S\to A:21$、$S\to B:11$、$S\to C:31$
• $A\to B:1$
• $B\to X:2$、$B\to Y:3$、$B\to C:4$
• $C\to Z:5$
• $X\to Y:6$、$X\to Z:7$、$X\to A:9$
• $Y\to Z:8$
• $Z\to C:10$

以下集合內容依「加入順序」表示；queue 由左至右表示出口到入口，stack 由左至右表示 stack top 到 stack bottom。

解題方法

BFS

起點 $S$ 先加入 queue 與 processSet。

• 從 $S$ 可到 $A,B,C$，cost 依序為 $11,21,31$，因此加入順序為 $B,A,C$。
• 從 $B$ 可到 $X,Y,C$，其中 $C$ 已在 processSet，故依 cost 加入 $X,Y$。
• 之後依 queue 順序逐一取出節點。

核心觀念

本題考查各排序演算法的：

• 最佳與最差時間複雜度
• In-Space：是否只使用 $O(1)$ 額外空間
• Stable：相同鍵值的相對順序是否保持
• 對指定數列進行降冪排序時的比較次數

Radix Sort 不依賴元素彼此比較，因此比較次數為 $0$。

以下採用一般教科書中的標準版本：

• Bubble Sort 使用提前結束判斷
• Merge Sort 合併時，兩邊皆有元素才進行比較
• Quick Sort 採第一個元素為 pivot，且每次 partition 對其餘元素各比較一次

解題方法

指定數列為：

此數列本身已經是降冪排列。

Bubble Sort

降冪排序時，第一輪檢查相鄰元素即可發現沒有任何交換，需比較：

最佳時間複雜度為 $O(n)$，最差為 $O(n^2)$。Bubble Sort 僅交換相鄰元素，因此為 Stable，且為 In-Space。

Insertion Sort

數列已符合降冪順序，每個新元素只需與前一元素比較一次：

最佳時間複雜度為 $O(n)$，最差為 $O(n^2)$。Insertion Sort 為 In-Space 且 Stable。

Merge Sort

依題意，奇數個元素時後半段多一個元素：

合併比較次數如下：

• 合併 $[50]$ 與 $[46]$：$1$ 次
• 合併 $[28]$ 與 $[19]$：$1$ 次
• 合併 $[37]$ 與 $[28,19]$：$2$ 次
• 最後合併 $[50,46]$ 與 $[37,28,19]$：$4$ 次

總比較次數：

Merge Sort 的最佳與最差時間複雜度皆為 $O(n\log n)$。標準 Merge Sort 需要額外陣列，因此不是 In-Space，但合併時可維持相同元素順序，故為 Stable。

Quick Sort

第一個元素作為 pivot。對降冪排序而言，$50$ 是最大值，每次都成為其中一側的極端 pivot，形成最差情況。

比較次數為：

Quick Sort 的最佳時間複雜度為 $O(n\log n)$，最差為 $O(n^2)$。標準原地 Quick Sort 為 In-Space，但交換可能改變相同鍵值的相對順序，因此不是 Stable。