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

核心觀念

題目考漸近符號 $\Theta$：若演算法的執行步數 $T(n)$ 同時具有上、下界，且兩者相差常數倍，則 $T(n)=\Theta(f(n))$。分析迴圈時，可計算最內層敘述執行次數，再保留最高次的成長項。

解題方法

（一）

外層變數 $i$ 依序取 $0,2,4,\ldots$，小於 $n$。每次外層迴圈執行時，內層迴圈跑 $i$ 次，因此總執行次數為

此式的最高次項與 $n^2$ 成正比，因此

（二）

while 迴圈令 $i$ 依序取 $0,1,\ldots,n-1$。當 $i$ 固定時，內層 $j$ 從 $i$ 執行到 $n$（含 $n$），共執行 $n-i+1$ 次。因此

核心觀念

Complete Binary Tree（完全二元樹）是指：除最底層外，其餘各層都填滿；最底層的節點由左至右連續排列，不留空缺。樹高以層數計算，因此單一節點的樹高為 $1$。

本題要證明節點數 $n$ 與樹高 $h$ 的上下界：

解題方法

下界：$n\ge 2^{h-1}$

樹高為 $h$，表示第 $h$ 層至少有一個節點。完全二元樹中，最底層節點由左至右排列；只要第 $h$ 層有節點，前面各層就必須填滿。

因此前 $h-1$ 層共有

個節點，且第 $h$ 層至少有 $1$ 個節點，故

上界：$n\le 2^h-1$

高度為 $h$ 的二元樹，第 $i$ 層最多有 $2^{i-1}$ 個節點。因此全樹最多有

核心觀念

本題考查無向圖的兩種儲存方式：

1. Adjacency matrix（鄰接矩陣）：以二維陣列表示任兩個節點是否相鄰。
2. Adjacency multilist（鄰接多重串列）：每一條無向邊只建立一個 edge node，再透過兩組鏈結欄位，分別串接至該邊兩端節點的邊串列。

圖中節點與邊如下：

這是一個無向圖，共有 $n=8$ 個節點、$e=6$ 條邊。

（一）Adjacency matrix 儲存方式

1. 鄰接矩陣

令矩陣 $A[i][j]$ 表示節點 $i$ 與節點 $j$ 是否相鄰：

由於本題為無向圖，因此：

依節點順序 $1,2,3,4,5,6,7,8$，鄰接矩陣為：

其中：

• 第 $2$ 列與第 $3$ 列中的 $1$，表示邊 $(2,3)$。
• 第 $6$ 列與第 $7$ 列中的 $1$，表示邊 $(6,7)$。
• 對角線皆為 $0$，表示圖中沒有 self-loop。

程式上可宣告：

若插入無向邊 $(u,v)$，必須同時設定：

Adjacency multilist 儲存方式

1. 資料結構

Adjacency multilist 通常包含兩種節點。

Vertex node

每個節點至少包含：

其中 firstedge 指向該節點所連接的第一條邊。

Edge node

每條無向邊只建立一個 edge node：

欄位意義如下：

• ivex：邊的一端節點。
• jvex：邊的另一端節點。
• ilink：同一端點 ivex 的下一條相關邊。
• jlink：同一端點 jvex 的下一條相關邊。

可表示為：

EdgeNode {
 ivex;
 jvex;
 ilink;
 jlink;
}

2. 本題的 edge nodes

令六條邊分別為：

e12 = (1, 2)
e23 = (2, 3)
e34 = (3, 4)
e45 = (4, 5)
e67 = (6, 7)
e78 = (7, 8)

各 vertex node 的串列如下：

1 : e12 → NULL
2 : e12 → e23 → NULL
3 : e23 → e34 → NULL
4 : e34 → e45 → NULL
5 : e45 → NULL

6 : e67 → NULL
7 : e67 → e78 → NULL
8 : e78 → NULL

亦可繪成：

1 ─ e12 ─ 2 ─ e23 ─ 3 ─ e34 ─ 4 ─ e45 ─ 5

6 ─ e67 ─ 7 ─ e78 ─ 8

但在 adjacency multilist 中，e12、e23 等 edge node 各只建立一次，並同時被兩個端點的串列所共用。

例如：

e12 = {
 ivex = 1,
 jvex = 2,
 ilink = NULL,
 jlink = e23
}

因此：

• 從節點 $1$ 出發，沿著 ilink 或依端點判斷後可找到 $e12$。
• 從節點 $2$ 出發，可依序找到 $e12$、$e23$。
• 同一個 e12 不需複製成兩份。

計算某節點的 degree 時，從該 vertex node 的 firstedge 開始，沿著對應的 link 欄位逐一走訪即可。

（二）計算所有節點 Degree 的時間複雜度

1. Adjacency matrix

在鄰接矩陣中，節點 $i$ 的 degree 等於第 $i$ 列中所有元素的總和：

核心觀念

本題考查二元搜尋樹（Binary Search Tree, BST）依序插入的結果、紅黑樹（Red-Black Tree, RBT）的插入平衡規則，以及兩種樹在搜尋、插入、刪除操作上的時間複雜度。

BST 的每個節點都符合：左子樹的鍵值小於該節點，右子樹的鍵值大於該節點。依序插入遞增數字 $1$ 至 $8$ 時，每個新節點都成為目前最右側節點，因此 BST 退化成單向鏈結。

紅黑樹除了符合 BST 的鍵值順序，還需維持下列性質：

1. 每個節點為紅色或黑色。
2. 根節點為黑色。
3. 所有 NIL 葉節點（空子節點）為黑色。
4. 紅色節點的子節點必為黑色。
5. 從任一節點到其後代 NIL 葉節點的每條路徑，黑色節點數相同。

複雜度分析以樹高 $h$ 為基礎。BST 的操作通常需 $O(h)$；紅黑樹的高度受平衡性質限制為 $O(\log n)$。

（一）建立 Binary Search Tree

按 $1,2,3,4,5,6,7,8$ 順序插入。每次插入的數字都大於目前樹中的所有節點，故沿右子樹一路向下，成為最右端的新節點。

1
 \
 2
 \
 3
 \
 4
 \
 5
 \
 6
 \
 7
 \
 8

此樹的高度為 $\Theta(n)$，已退化為鏈結結構。

（二）建立 Red-Black Tree

以下採用標準紅黑樹插入規則：新插入節點先染紅，再依父、叔、祖父節點的顏色與形狀進行重新著色或旋轉；最後確保根節點為黑色。圖中 ○ 表示黑色節點，◉ 表示紅色節點；未畫出的 NIL 子節點皆為黑色。

依序插入與調整如下：

1. 插入 $1$：新節點成為根，染黑。
2. 插入 $2$：成為 $1$ 的右子節點，為紅色，不違反性質。
3. 插入 $3$：形成右右型；對 $1$ 左旋，並將原祖父 $1$ 染紅、新根 $2$ 染黑。
4. 插入 $4$：新節點為 $3$ 的右子節點，父節點 $3$ 紅、叔節點 $1$ 紅；將 $1$、$3$ 染黑，祖父 $2$ 染紅，再將根 $2$ 染黑。
5. 插入 $5$：形成右右型；對 $3$ 左旋，並將原祖父 $3$ 染紅、節點 $4$ 染黑。
6. 插入 $6$：父節點 $5$ 紅、叔節點 $3$ 紅；將 $3$、$5$ 染黑，祖父 $4$ 染紅。
7. 插入 $7$：形成右右型；對 $5$ 左旋，並將原祖父 $5$ 染紅、節點 $6$ 染黑。
8. 插入 $8$：父節點 $7$ 紅、叔節點 $5$ 紅；將 $5$、$7$ 染黑，祖父 $6$ 染紅。