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

核心觀念

本題考查二元樹的三種走訪順序，以及利用「鏈結節點表示法」與「堆疊（stack）」實作非遞迴中序走訪。

• 前序：根 $\rightarrow$ 左子樹 $\rightarrow$ 右子樹
• 中序：左子樹 $\rightarrow$ 根 $\rightarrow$ 右子樹
• 後序：左子樹 $\rightarrow$ 右子樹 $\rightarrow$ 根

依考卷圖形判讀，$H$ 是 $D$ 的右子節點，$K$ 是 $G$ 的左子節點。

（一）三種走訪結果

樹的結構為：

• $A$ 的左、右子節點為 $B$、$C$
• $B$ 的左、右子節點為 $D$、$E$
• $D$ 的右子節點為 $H$
• $C$ 的左、右子節點為 $F$、$G$
• $G$ 的左子節點為 $K$

1. 前序走訪：根、左、右

2. 中序走訪：左、根、右

3. 後序走訪：左、右、根

（二）二元樹資料結構與非遞迴中序走訪

資料結構設計

因節點數無法預先確定，使用動態配置記憶體的鏈結二元樹：

typedef struct Node {
 char data;
 struct Node *left;
 struct Node *right;
} Node;

每個節點包含：

• data：儲存節點資料
• left：指向左子樹
• right：指向右子樹

另外使用堆疊儲存尚未處理的節點。

非遞迴中序走訪虛擬碼

Inorder(root):
 建立空堆疊 S
 current ← root

 while current ≠ NULL 或 S 不為空:
 while current ≠ NULL:
 Push(S, current)
 current ← current.left

 current ← Pop(S)
 輸出 current.data

 current ← current.right

執行方法

核心觀念

本題考查「特殊矩陣的壓縮儲存」。矩陣 $A$ 只有三條對角線上的元素可能不為零：

• 下對角線：$a_{i,i-1}$，共有 $n-1$ 個。
• 主對角線：$a_{i,i}$，共有 $n$ 個。
• 上對角線：$a_{i,i+1}$，共有 $n-1$ 個。

因此需要儲存的元素總數為

符合題目限制。

解題方法

採用一維陣列 $B$，依序儲存「下對角線、主對角線、上對角線」。

陣列配置

具體定義如下：

以題目中的 $5\times5$ 矩陣為例：

陣列索引如下：

由 $B$ 取得 $a_{ij}$

給定 $0\le i,j\le n-1$，分三種情況判斷：

1. 位於下對角線

當

表示 $a_{ij}$ 位於下對角線，因此

2. 位於主對角線

當

表示 $a_{ij}$ 位於主對角線，因此

3. 位於上對角線

當

核心觀念

本題考察無向圖的兩種表示法：

1. 相鄰串列（adjacency list）：每個頂點保存一條串列，記錄與該頂點直接相連的所有頂點。
2. 鏈結串列與循序串列的差異：

• 鏈結串列適合資料數量變動、插入與刪除頻繁的情況。
• 一維陣列適合資料結構固定、需要連續記憶體與快速索引的情況。

由圖可辨識的邊為：

因為是無向圖，每條邊必須在兩個端點的相鄰串列中各記錄一次。

（一）以鏈結串列表示相鄰串列

各頂點的相鄰頂點如下：

• 頂點 $0$：連接 $1,2,3$
• 頂點 $1$：連接 $0$
• 頂點 $2$：連接 $0,3$
• 頂點 $3$：連接 $0,2,4$
• 頂點 $4$：連接 $3$

可表示為：

0 ─→ 1 ─→ 2 ─→ 3 ─→ NULL
1 ─→ 0 ─→ NULL
2 ─→ 0 ─→ 3 ─→ NULL
3 ─→ 0 ─→ 2 ─→ 4 ─→ NULL
4 ─→ 3 ─→ NULL

每條無向邊均出現兩次，例如邊 $(0,3)$ 同時記錄於頂點 $0$ 與頂點 $3$ 的串列中。

相鄰頂點的排列順序不影響圖形所代表的內容，因此上述順序只要正確記錄所有相鄰頂點即可。

（二）以一維陣列表示相鄰串列

資料結構設計

設一維陣列為 $B$，採用下列格式：

• $B[0]$：記錄目前使用的陣列元素數量，不包含 $B[0]$ 本身。
• $B[1]$ 至 $B[5]$：分別記錄頂點 $0$ 至頂點 $4$ 的相鄰資料起始位置。
• $B[6]$ 以後：依序存放各頂點的相鄰頂點。
• 頂點 $i$ 的相鄰資料範圍為：
• 起點：$B[i+1]$
• 終點：下一個頂點的起始位置減 $1$
• 最後一個頂點的終點為 $B[0]$

此設計不使用其他資料結構，所有索引、頂點與數量資訊均存放於同一個一維陣列中。

陣列內容

依序將相鄰頂點存放如下：

• 頂點 $0$：$1,2,3$
• 頂點 $1$：$0$
• 頂點 $2$：$0,3$
• 頂點 $3$：$0,2,4$
• 頂點 $4$：$3$

因此：

其中：

核心觀念

區間堆積（interval heap）是雙端優先佇列（double-ended priority queue），每個節點儲存一個區間 $[L,R]$，並滿足：

1. 節點內部：$L\le R$。
2. 所有左端點形成最小堆積（min-heap）：

$L_{\text{parent}}\le L_{\text{child}}$

3. 所有右端點形成最大堆積（max-heap）：

$R_{\text{parent}}\ge R_{\text{child}}$

因此，根節點的左端點是全體元素的最小值，右端點是全體元素的最大值。

本題不是選擇題，無選項分析。

（一）依序插入元素並畫出最後區間堆積

解題方法

插入時遵循以下原則：

• 若目前最後一個節點只有一個元素，先將新元素放入同一節點，形成區間。
• 若新元素小於父節點左端點，沿左端點最小堆積向上調整。
• 若新元素大於父節點右端點，沿右端點最大堆積向上調整。
• 每次調整後，都必須維持節點內 $L\le R$。

依序處理如下。

插入 $40$

$[40,40]$

插入 $30$

放入根節點並排序：

$[30,40]$

插入 $60$

新增節點 $[60,60]$。因為 $60>40$，沿右端點向上調整：

插入 $15$

放入最後節點，形成 $[15,40]$。因為 $15<30$，與根節點左端點交換：

插入 $14$

新增節點 $[14,14]$。因為 $14<15$，向上調整：

插入 $19$

放入最後節點 $[15,15]$，形成：

$[15,19]$

此時仍符合堆積條件。

插入 $80$

新增節點 $[80,80]$。因為 $80>40$，先與父節點右端點交換，再與根節點右端點交換：

插入 $12$

放入最後節點 $[40,40]$，形成 $[12,40]$。

因為 $12<30$，先與父節點左端點交換，成為 $[12,60]$；再因為 $12<14$，與根節點左端點交換：

插入 $90$

新增節點 $[90,90]$。因為 $90>60$，先與父節點右端點交換，再與根節點右端點交換：

最後區間堆積

驗算：

• 左端點：$12,14,15,30,60$，符合最小堆積。
• 右端點：$90,80,19,40,60$，符合最大堆積。
• 每個節點均滿足左端點 $\le$ 右端點。

（二）刪除元素 $12$

解題方法

$12$ 是根節點的最小元素。刪除根節點左端點後，以最後一個節點的元素 $60$ 補入根節點，再沿左端點最小堆積向下調整。

原結構：

刪除 $12$，以 $60$ 補至根節點：

根節點左端點 $60$ 應與子節點中較小的左端點 $14$ 交換：

此時 $60$ 位於節點 $[60,80]$，仍大於其子節點 $[30,40]$ 的左端點 $30$，因此繼續向下調整。交換後並維持節點內部順序：

（三）以一維陣列儲存區間堆積

核心設計