113 關務特考三等 資訊處理(選試英文) 資料結構 考古題詳解

核心觀念

二元樹的三種深度優先走訪順序如下：

• 中序（inorder）：左子樹 → 根節點 → 右子樹。
• 後序（postorder）：左子樹 → 右子樹 → 根節點。
• 後序運算式求值：由左至右讀取運算子與運算元；遇到數值便推入堆疊，遇到二元運算子則彈出兩個數值，先彈出者是右運算元、後彈出者是左運算元，計算後將結果推回堆疊。

本題第一部分以後序序列最後一個節點作為根，再利用中序序列切分左右子樹；第二部分依後序表示式的堆疊規則逐步計算。

解題方法一：由中序與後序還原二元樹

中序表示式為 FBACEIGHJ，後序表示式為 BCAFIHJGE。

後序序列最後一個節點 E 是整棵樹的根。中序序列中，E 左側為左子樹，右側為右子樹：

• 左子樹中序：FBAC
• 右子樹中序：IGHJ

從後序序列移除根 E 後，依左右子樹節點數切分：

• 左子樹後序：BCAF
• 右子樹後序：IHJG

**還原左子樹：**後序 BCAF 的最後一個節點 F 是左子樹的根。中序 FBAC 中，F 左側沒有節點，右側為 BAC，因此 F 沒有左子樹，右子樹由 BAC 組成。

後序 BAC 的根為 A；中序 BAC 中，A 左側是 B、右側是 C，故 A 的左子節點為 B，右子節點為 C。

**還原右子樹：**後序 IHJG 的最後一個節點 G 是右子樹的根。中序 IGHJ 中，G 左側為 I，右側為 HJ，所以 G 的左子節點為 I，右子樹由 HJ 組成。

後序 HJ 的根為 J；中序 HJ 中，J 左側為 H，右側沒有節點，因此 J 的左子節點為 H。

對應二元樹

 E
 / \
 F G
 \ / \
 A I J
 / \ /
 B C H

解題方法二：以堆疊計算後序表示式

運算式為：

核心觀念

快速排序（Quick Sort）以樞紐（pivot）將資料分成兩組：小於樞紐的資料放在左側，大於樞紐的資料放在右側，再對左右兩組遞迴排序。

本題指定每次以該子序列的第一個數值為樞紐。以下採用雙向掃描分割法：左側指標尋找大於樞紐的值，右側指標尋找小於樞紐的值，兩者找到後交換；指標交錯時，將樞紐放到交錯位置，完成該次分割。

解題方法與比較過程

原始資料為：

$48,\ 55,\ 10,\ 88,\ 26,\ 80,\ 35,\ 40$

第一次分割：樞紐為 $48$

由左向右比較，$55>48$，左側指標停在 $55$；由右向左比較，$40<48$，右側指標停在 $40$。交換兩者：

$48,\ 40,\ 10,\ 88,\ 26,\ 80,\ 35,\ 55$

繼續掃描：左側遇到 $88>48$ 停下；右側遇到 $35<48$ 停下。交換 $88$ 與 $35$：

$48,\ 40,\ 10,\ 35,\ 26,\ 80,\ 88,\ 55$

繼續掃描：左側的 $26<48$，指標往右；接著遇到 $80>48$。右側向左掃描時也遇到 $80>48$，指標往左，兩指標交錯。將樞紐 $48$ 與交錯位置的 $26$ 交換：

$26,\ 40,\ 10,\ 35,\ 48,\ 80,\ 88,\ 55$

核心觀念

AVL 樹是符合二元搜尋樹順序，且每個節點的左右子樹高度差至多為 $1$ 的二元樹。以下採用平衡因子定義：

因此，$\mathrm{BF}=+2$ 表示左側過高，$\mathrm{BF}=-2$ 表示右側過高；空子樹高度為 $0$，葉節點高度為 $1$。

解題方法

依序插入或刪除節點，沿著受影響的路徑往根節點檢查平衡因子。若有節點的平衡因子超出 $[-1,1]$，依失衡方向進行旋轉。本題初始樹為：

 25
 / \
 15 60
 / \
 30 80

一、加入 90

依二元搜尋樹規則，$90>25$、$90>60$、$90>80$，故插入為 $80$ 的右子節點：

 25
 / \
 15 60
 / \
 30 80
 \
 90

從插入點往上檢查，節點 $80$ 的平衡因子為 $-1$，節點 $60$ 的平衡因子為 $-1$，均仍平衡；節點 $25$ 的左子樹高度為 $1$、右子樹高度為 $3$，所以 $\mathrm{BF}(25)=-2$。新節點位於失衡節點右子樹的右側，屬於 RR 型，對 $25$ 做一次左旋：

 60
 / \
 25 80
 / \ \
 15 30 90

二、再加入 85

核心觀念

本題考二元樹以一維陣列表示時，節點與子節點索引的對應關係。採用根節點放在索引 1 的表示法時，索引為 $k$ 的節點，其：

• 父節點索引為 $\left\lfloor \frac{k}{2}\right\rfloor$
• 左子節點索引為 $2k$
• 右子節點索引為 $2k+1$

這些公式以完全二元樹的層序位置配置為基礎；樹中即使缺少某些節點，其位置仍依照這套索引規則保留。

解題方法

已知節點 $i$ 位於索引 $1024$：

因此，節點 $i$ 的父節點存於陣列索引 512。

若節點 $i$ 有右子節點 $j$，依右子節點公式：

因此，節點 $j$ 存於陣列索引 2049。

最浪費陣列空間的二元樹

核心觀念

這題考無向加權圖的讀取，以及 Kruskal’s 演算法求最小生成樹。

• 無向圖的相鄰矩陣以對稱位置表示同一條邊，因此只列一次即可。
• 矩陣中的 $\infty$ 代表兩頂點之間沒有邊。
• 生成樹須連接所有頂點，且不含環；若圖有 $n$ 個頂點，生成樹恰有 $n-1$ 條邊。
• Kruskal’s 演算法依權重由小到大考慮邊，只加入不會形成環的邊，直到選出 $n-1$ 條。

解題方法

先從相鄰矩陣上、下三角區擇一讀取所有有限權重，再按權重由小到大排列。逐一檢查每條邊的兩端是否已在同一連通分量；若已連通，加入該邊會形成環，故予以略過。

對應的無向加權圖

由相鄰矩陣讀得以下 10 條邊：

圖形可表示如下；每條線上的數字為該邊權重：

graph LR
 a ---|13| b
 a ---|9| c
 a ---|10| d
 b ---|16| d
 c ---|12| d
 c ---|2| e
 c ---|3| f
 e ---|4| f
 f ---|6| g
 d ---|18| g

Kruskal’s 演算法形成過程

將邊依權重由小到大排列：

依序檢查：