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

核心觀念

本題考遞迴關係式、遞迴次數的分析，以及遞迴演算法的時間複雜度。分析時要區分：

• 計算結果：依遞迴定義展開後，找出 $Q(n)$ 的數學意義。
• 乘法運算次數：只計算程式實際執行的乘法，不把加法或遞迴呼叫算成乘法。
• 執行時間：每層遞迴所做的工作，加上子問題的執行時間。

解題方法

（一）遞迴關係式與計算結果

依虛擬碼可直接寫出：

逐層展開：

因此，$Q(n)$ 是前 $n$ 個正奇數的總和。由等差級數求和可得：

所以此演算法計算的是 $n$ 的平方。

（二）乘法運算次數

每次遞迴呼叫計算 $2n-1$，其中包含一次乘法 $2\times n$。當 $n=1$ 時直接回傳，不執行這次乘法。

令 $M(n)$ 表示乘法運算次數，則：

展開後：

核心觀念

算術運算樹以運算子作為內部節點、運算元作為葉節點。二元運算子有左、右子樹，分別表示左運算元與右運算元；因此樹的形狀保留了原式的運算次序，不必依靠括號再判斷優先順序。

本題也考查滿二元樹的定義：每個節點恰有 $0$ 個或 $2$ 個子節點。算術運算樹若只使用二元運算子，運算子節點各有兩個子節點，運算元節點則是葉節點，故符合此定義。

（一）建立算術運算樹

原式為：

最外層運算是除法，因此根節點為 $\div$；左子樹表示分子，右子樹表示分母。依照原式中各運算的括號與結構，得到：

 ÷
 / \
 − ÷
 / \ / \
 × + + 7
 / \ / \ / \
 + 3 7 2 × 5
 / \ / \
 5 1 2 8

左子樹的分子為 $((5+1)\times3)-(7+2)$；右子樹的分母為 $((2\times8)+5)\div7$。樹中每個運算子的左右子樹順序，均對應原式運算子的左右運算元。

（二）是否為滿二元樹

敘述正確。

本題的算術運算樹只包含二元運算子 $+$、$-$、$\times$、$\div$，每個運算子節點都恰有兩個子節點；數字節點則沒有子節點。因此，每個節點的子節點數都是 $0$ 或 $2$，符合滿二元樹（Full Binary Tree，又稱 Proper Binary Tree）的定義。

（三）運算表示式種類與前序表示式

原式是中序表示式（Infix Expression）：運算子寫在運算元之間，例如 $5+1$。題目中的括號用來明確指定運算順序。

將樹轉為前序表示式（Preorder Expression），採用「根、左子樹、右子樹」的走訪順序：

核心觀念

優先佇列（Priority Queue）依物件的優先權決定處理順序。此題以鍵值代表優先權，且鍵值愈小，優先權愈高，因此適合用最小堆積管理。

最小二元堆積是完全二元樹，並滿足「父節點鍵值不大於子節點鍵值」的堆積性質。因此，節點的鍵值若大於 $k$，其子樹中的所有鍵值也都大於 $k$，可以直接略過整棵子樹。

（一）優先佇列的 ADT 定義

優先佇列是一種抽象資料型態，其元素各自帶有優先權；操作依優先權選取元素，而不是依照元素加入的先後順序。以本題的鍵值規則而言，鍵值最小者優先。

常見操作如下：

• Create：建立空的優先佇列。
• Insert(x)：將物件 $x$ 加入佇列。
• FindMin：回傳優先權最高的物件，也就是鍵值最小者，但不移除它。
• DeleteMin：回傳並移除鍵值最小者。
• IsEmpty：檢查佇列是否為空。
• Size：回傳佇列中的物件數量。

若允許鍵值相同，FindMin 或 DeleteMin 可回傳其中任一個最小鍵值物件；除非 ADT 另行規定，通常不保證相同鍵值物件的先後順序。

（二）找出所有鍵值不大於 $k$ 的物件

解題方法

從堆積根節點開始，以遞迴或堆疊走訪節點：

1. 若目前節點鍵值大於 $k$，停止走訪該節點的子樹。
2. 若目前節點鍵值小於或等於 $k$，輸出該物件，並繼續檢查其子節點。
3. 空節點不需處理。

偽碼如下：

核心觀念

本題考查：

1. 紅黑樹的結構限制與平衡條件。
2. $(2,4)$-樹的節點與紅黑樹節點的對應關係。
3. 將紅色節點與其黑色父節點合併，形成 $(2,4)$-樹中的多鍵節點。
4. 利用紅黑樹的黑高度與「紅節點不能相鄰」證明高度為 $O(\log n)$。

（一）紅黑樹與 $(2,4)$-樹的定義

1. 紅黑樹

紅黑樹是一種具有下列條件的二元搜尋樹：

1. 每個節點均為紅色或黑色。
2. 根節點為黑色。
3. 所有外部葉節點（通常以 $NIL$ 表示）均為黑色。
4. 紅色節點的子節點必須為黑色，因此不能有連續兩個紅色節點。
5. 從任一節點到其所有後代 $NIL$ 葉節點的每條路徑，都包含相同數量的黑色節點，此數量稱為該節點的黑高度（black-height）。
6. 節點鍵值仍須符合二元搜尋樹的順序：

2. $(2,4)$-樹

$(2,4)$-樹是一種平衡的多路搜尋樹，具有下列特性：

1. 每個內部節點包含 $1$ 至 $3$ 個排序後的鍵值。
2. 每個內部節點具有 $2$ 至 $4$ 個子樹；子樹數量等於鍵值數量加 $1$。
3. 節點內的鍵值與子樹符合多路搜尋樹的順序關係。
4. 所有葉節點位於相同深度，因此整棵樹保持平衡。
5. 一個鍵值的節點稱為 $2$-node，兩個鍵值的節點稱為 $3$-node，三個鍵值的節點稱為 $4$-node。

紅黑樹與 $(2,4)$-樹的對應方式為：

• 黑色節點本身對應一個 $(2,4)$-樹節點中的鍵值。
• 黑色節點的紅色子節點，與該黑色父節點合併成同一個多鍵節點。
• 黑色節點最多有兩個紅色子節點，因此合併後最多有三個鍵值，正好形成 $(2,4)$-樹的 $2$-、$3$-、$4$-node。

（二）紅黑樹轉換為 $(2,4)$-樹

解題方法

將每個黑色節點視為一個 $(2,4)$-樹節點，並把它的紅色子節點併入同一個節點。合併後的鍵值仍依照由小到大的順序排列。

依照圖中的紅黑樹：

• 根節點 $r$ 為黑色，紅色子節點為 $a$、$b$。
• 節點 $e$ 為黑色，其紅色子節點為 $l$。
• 其他黑色節點沒有紅色子節點。

因此：

• $a,r,b$ 合併為一個三鍵值節點 $[a\mid r\mid b]$。
• $e,l$ 合併為一個二鍵值節點 $[e\mid l]$。
• $c,d,f$ 各自形成一鍵值節點。

轉換後的 $(2,4)$-樹如下：

 [ a | r | b ]
 / | | \
 [ c ] [ d ] [ e | l ] [ f ]
 / \ / \ / | \ / \
 [ g ] [ h ][ i ][ j ][ k ][ o ][ p ][ m ][ n ]

更精確地表示各節點的子樹關係：

• $[a\mid r\mid b]$ 的四個子樹依序為：

• $[c]$ 的子樹為 $[g]$、$[h]$。
• $[d]$ 的子樹為 $[i]$、$[j]$。
• $[e\mid l]$ 的三個子樹依序為 $[k]$、$[o]$、$[p]$。
• $[f]$ 的子樹為 $[m]$、$[n]$。

核心觀念

本題考查：

1. 無向圖的相鄰矩陣判讀。
2. 相鄰矩陣與邊集合的對應關係。
3. BFS 的佇列（Queue）概念。
4. 當同一層有多個相鄰節點時，依字母順序拜訪。

由於是無向圖，矩陣必須滿足：

且矩陣中 $M_{ij}=1$ 表示節點 $i$ 與節點 $j$ 之間有一條無向邊。

解題方法

（一）畫出無向圖 $G$

只需讀取相鄰矩陣的上三角部分，避免同一條無向邊重複計算。

矩陣中值為 $1$ 的位置所代表的邊如下：

因此共有 $11$ 條邊。

各節點的相鄰節點為：

可依下列方式繪圖：

 e
 / \
 a---b
 /|\ /|\
 d | f | 
 \|/ \|
 g---c
 \ /
 f

較精確的作圖依據為邊集合：

其中每一條邊均為無向邊。

（二）建立 BFS 樹

BFS 從節點 $a$ 開始，並以字母順序處理相鄰節點。

第 1 層：拜訪 $a$

$a$ 的相鄰節點依字母順序為：

因此將 $b,d,e,f$ 加入 BFS 樹。

目前樹邊：