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

（一）後序運算式的計算

核心觀念： 後序運算式將運算子放在運算元之後，例如 3 4 + 表示 $3+4$。計算時由左至右掃描，遇到運算元就推入堆疊；遇到運算子，就彈出所需數目的運算元，計算後再將結果推回堆疊。

解題方法： 堆疊遵循後進先出（LIFO），能保留運算所需的最近運算元，因此適合進行後序運算式計算。佇列遵循先進先出（FIFO），無法依運算子需要的順序取出運算元。

選項分析： 堆疊適合；佇列不適合。

解題技巧： 記住「後序運算式由左至右掃描、以堆疊計算」。

（二）二元搜尋樹的走訪

核心觀念： 二元搜尋樹（BST）符合左子樹鍵值小於根節點、右子樹鍵值大於根節點的性質。

解題方法： 中序走訪依序進行「左子樹、根節點、右子樹」，因此會先輸出較小鍵值，再輸出根節點，最後輸出較大鍵值，得到遞增順序。

選項分析：

• 前序（Preorder）：根、左、右；不保證遞增。
• 中序（Inorder）：左、根、右；可得到遞增鍵值。
• 後序（Postorder）：左、右、根；不保證遞增。
• 層序（Level-order）：逐層由上而下走訪；不保證遞增。

解題技巧： BST 題目問「由小到大列出鍵值」，直接選中序走訪。

（三）鏈結串列處理碰撞的搜尋複雜度

核心觀念： 使用鏈結串列（chaining）處理碰撞時，雜湊表每個位置對應一條鏈結串列。搜尋先計算雜湊值，再沿著該位置的串列尋找資料。

解題方法： 在雜湊函數分布均勻、負載因子維持在適當範圍的假設下，每個位置平均只需檢查常數筆資料，因此平均搜尋時間為 $O(1)$。若大量資料集中在同一條串列，最壞情況則可達 $O(n)$。

選項分析：

• $O(1)$：平均搜尋時間，正確。
• $O(\log n)$：不是鏈結串列 chaining 在一般均勻雜湊假設下的平均複雜度。
• $O(n)$：可描述最壞情況，不是題目所問的平均情況。
• $O(\sqrt{n})$：不是此方法的標準平均搜尋複雜度。

核心觀念

優先佇列（Priority Queue）依元素的優先權決定取出順序。本題採取最大優先權優先，也就是每次取出目前的最大值。

三種實作方式的時間複雜度，取決於「維持順序」或「尋找最大值」的工作分別落在哪個操作上：

• 排序好的陣列：最大值可直接取得，但插入時要維持排序。
• 未排序陣列：插入可直接放入，但取最大值時要搜尋整個陣列。
• 最大堆積：根節點為最大值，插入與刪除根節點都透過沿樹調整完成。

以下以 $n$ 表示目前元素個數。

解題方法

（一）排序好的陣列

將元素依遞增順序排列，最大值放在陣列末端：

• 插入：找到新元素應放的位置，並移動其後元素以維持排序，最壞需移動 $n$ 個元素，為 $O(n)$。
• 取最大值：直接取陣列末端元素，為 $O(1)$。

因此，插入為 $O(n)$，取最大值為 $O(1)$。

（二）未排序陣列

• 插入：直接放到陣列末端，不必維持排序，為 $O(1)$。
• 取最大值：必須逐一比較元素，找出最大值，最多檢查 $n$ 個元素，為 $O(n)$。

因此，插入為 $O(1)$，取最大值為 $O(n)$。

（三）最大堆積

最大堆積是一種完全二元樹，且每個父節點的鍵值不小於其子節點，因此最大值位於根節點。

• 插入：先將新元素放在完全二元樹的下一個空位，再向上調整（上浮）。堆積高度為 $O(\log n)$，所以插入為 $O(\log n)$。
• 取最大值：最大值在根節點。移除根節點後，將最後一個節點移到根部，再向下調整（下沉），最多經過樹高，故為 $O(\log n)$。

因此，插入為 $O(\log n)$，取最大值為 $O(\log n)$。若只讀取最大值而不移除，則可直接查看根節點，時間為 $O(1)$；本題的「取出最大數」包含移除操作。

（四）逐步建立最大堆積

以下以陣列層序表示堆積，並在每一步列出對應樹形。插入時上浮；取出最大值時，以最後一個節點補到根部，再下沉。

1. 加入 10

陣列：$[10]$

10

2. 加入 30

30 放在 10 的子節點，因 $30>10$，上浮。

陣列：$[30,10]$

 30
 /
10

3. 加入 50

50 放在下一個空位，因 $50>30$，上浮至根。

陣列：$[50,10,30]$

核心觀念

二元搜尋樹（binary search tree, BST）遵守以下次序：每個節點左子樹的鍵值小於該節點，右子樹的鍵值大於該節點。插入時，從根節點開始比較，直到找到空位置；刪除時，則依被刪節點的子節點數分情況處理：

• 沒有子節點：直接刪除。
• 只有一個子節點：以該子節點取代被刪節點。
• 有兩個子節點：以左子樹最大值（中序前驅）或右子樹最小值（中序後繼）取代，再刪除該前驅或後繼原所在節點。

以陣列表示二元樹時，採用 1 起始索引：節點 $A(i)$ 的左子節點在 $A(2i)$，右子節點在 $A(2i+1)$。

解題方法

（一）依序插入，再刪除 50

依插入順序逐一比較，插入後的樹如下。每一步以粗體標出新插入的節點。

插入 50：

50

插入 30：

 50
 /
30

插入 70：

 50
 / \
30 70

插入 20：

 50
 / \
 30 70
 /
20

插入 40：

 50
 / \
 30 70
 / \
20 40

插入 60：

 50
 / \
 30 70
 / \ /
20 40 60

插入 80：

 50
 / \
 30 70
 / \ / \
20 40 60 80

刪除 50 時，它有兩個子節點。採用右子樹最小值作為中序後繼：右子樹中的最小值是 60。以 60 取代根節點的 50，再刪除原本位於 70 左側的 60：

 60
 / \
 30 70
 / \ \
20 40 80

（二）刪除 40

依陣列索引還原相關樹形：

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

節點 40 有兩個子節點。其右子樹最小值為 50，因此以 50 取代 40；再刪除原本在 $A(6)$ 的 50。該位置原有一個右子節點 60，故以 60 接替。

變化後的樹為：

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

依 $A(2i)$、$A(2i+1)$ 的索引規則，更新後陣列為：

$i$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
$A(i)$	50	30	70	10	--	60	90	--	20	--	--	--	--	80	--	--	--

（三）刪除 30

節點 30 只有一個子節點 10，因此以 10 取代 30。原本 10 的右子節點 20 隨之保留：

核心觀念

每個機器人只比較輸送帶上相鄰的兩顆球，並把較大的放前面、較小的放後面。若把整組機器人視為一趟由左至右的相鄰比較交換，這就是冒泡排序（Bubble Sort）的一趟。

用球的大小表示其排序名次，目標是由大到小。一次由左至右的掃描中，每顆球至多向左移動一格；因此，若某顆球左側有 $d$ 顆比它大的球，它至少需要 $d$ 趟才能到達正確位置。所需趟數的最大值，就是完成排序所需的趟數。

解題方法

（一）4 個機器人是否足夠

依序進行由左至右的相鄰比較交換：

機器人	比較後的球序
初始	$3,2,5,6,1,4$
第 1 個	$3,5,2,6,1,4$
第 2 個	$3,5,6,2,1,4$
第 3 個	$3,5,6,2,4,1$
第 4 個	$5,3,6,2,4,1$

通過 4 個機器人後，球序仍不是由大到小，因此 4 個機器人不夠。

（二）求最少機器人數

輸入序列為：

$$11,12,20,16,3,1,7,15,2,18,10,5,14,6,8,13,19,4,9,17$$

計算每顆球左側有幾顆比它大的球，找出最大值：

球	左側比它大的球數
11	0
12	0
20	0
16	1
3	4
1	5
7	4
15	3
2	7
18	4
10	6
5	8
14	6
6	10
8	9
13	6
19	3
4	13
9	11
17	3