112 關務特考三等 資訊處理 資料結構 考古題詳解

核心觀念

本題考查運算式的運算子優先順序與結合律，以及二元運算式樹的三種走訪方式。

• *、/ 的優先順序高於 +、-。
• 同一優先順序的二元運算子依左至右結合。
• 運算式樹的葉節點是運算元，本題為 $A,B,C,D,E$；內部節點是運算子。
• 前序走訪：根、左子樹、右子樹。
• 後序走訪：左子樹、右子樹、根。

解題方法

先依優先順序與左至右結合規則，將中序運算式加上括號：

$$A/B-C+D*E-A*C = ((A/B)-C)+(D*E)-(A*C)$$

再依運算式的結構建立二元樹。整體運算的最外層是由左至右結合的減法，因此根節點是最後一個 -；它的左子樹表示 $((A/B)-C)+(D*E)$，右子樹表示 $A*C$。

 -
 / \
 + *
 / \ / \
 - * A C
 / \ / \
 / C D E
 / \
 A B

樹中最左側的 / 子樹表示 $A/B$；其結果再與 $C$ 相減，接著加上 $D*E$，最後減去 $A*C$。

核心觀念

本題考無向加權圖的相鄰矩陣、相鄰串列，以及以 Prim 演算法求最小成本擴張樹（Minimum Cost Spanning Tree, MST）。

無向圖的邊 $(u,v)$ 表示 $u$ 與 $v$ 互相相鄰；在相鄰矩陣中，矩陣對稱，頂點到自身的對角線值為 $0$，沒有邊的頂點對以 $\infty$ 表示。相鄰串列則逐一列出每個頂點相鄰的頂點及邊權重。

Prim 演算法從指定起點開始，每一步選擇一條「一端在已加入頂點集合內、另一端在集合外」且權重最小的邊，直到所有頂點都加入。對 $|V|=5$ 的連通圖，擴張樹包含 $|V|-1=4$ 條邊。

解題方法

依題目邊的列舉順序，權重對應如下：

邊	權重
$(T,W)$	$2$
$(T,Y)$	$1$
$(T,Z)$	$7$
$(W,X)$	$4$
$(W,Z)$	$3$
$(X,Z)$	$6$

相鄰矩陣

頂點順序採 $T,W,X,Y,Z$。矩陣中的權重依序填入；未直接相連的頂點對以 $\infty$ 表示。

$$\begin{array}{c|ccccc} & T & W & X & Y & Z\\ \hline T & 0 & 2 & \infty & 1 & 7\\ W & 2 & 0 & 4 & \infty & 3\\ X & \infty & 4 & 0 & \infty & 6\\ Y & 1 & \infty & \infty & 0 & \infty\\ Z & 7 & 3 & 6 & \infty & 0 \end{array}$$

相鄰串列

每條無向邊在兩端頂點的串列中各列一次：

核心觀念

2-3 樹是階序為 3 的 B 樹。每個節點可存 1 或 2 個遞增的鍵值，分別稱為 2-節點與 3-節點；除根節點外，每個內部節點有 2 或 3 個子節點。所有葉節點位於同一層，因此樹保持平衡。

插入時，先將新鍵值放入適當葉節點。若節點暫時有 3 個鍵，便將中間鍵提升至父節點，左右兩鍵分別形成子節點；若父節點也滿載，則繼續向上分裂。刪除時，若刪除內部節點中的鍵，先以其前驅或後繼鍵替換，再從葉節點刪除；若因此產生空節點，則向兄弟借鍵或與兄弟合併，維持 2-3 樹的節點容量與葉深度。

解題方法：依序插入

以下以方括號表示節點中的鍵值；同一括號內的鍵值屬於同一節點。

1. 插入 $60$、$70$：兩個鍵可放在根節點。

$[60,70]$

2. 插入 $50$：根節點暫時有三個鍵 $[50,60,70]$，將中間鍵 $60$ 提升為新根。

$[60]([50]\mid[70])$

3. 插入 $10$：$10<60$，放入左葉節點。

$[60]([10,50]\mid[70])$

4. 插入 $20$：左葉節點暫時成為 $[10,20,50]$，提升中間鍵 $20$ 至根。根成為 $[20,60]$，兩側葉節點分別為 $[10]$ 與 $[50]$。

$[20,60]([10]\mid[50]\mid[70])$

5. 插入 $80$：$80>60$，放入最右葉節點。

$[20,60]([10]\mid[50]\mid[70,80])$

6. 插入 $95$：最右葉節點暫時成為 $[70,80,95]$，提升中間鍵 $80$ 至根。根暫時成為 $[20,60,80]$，再分裂並提升中間鍵 $60$ 為新根。

$[60]([20]([10]\mid[50])\mid[80]([70]\mid[95]))$

7. 插入 $90$：$90>60$ 且 $90>80$，放入最右葉節點。

$[60]([20]([10]\mid[50])\mid[80]([70]\mid[90,95]))$

因此，依序插入全部資料後的 2-3 樹如上。

解題方法：依序刪除

刪除 $50$

核心觀念

選擇排序每一趟都在尚未排好的部分中找出最大值，並將它放到該部分的最右端。外迴圈令 $i$ 從 $n-1$ 遞減至 $1$，表示本趟要把最大值放到索引 $i$；內迴圈則逐一比較索引 $0$ 到 $i$ 的元素，記錄最大值的位置。

解題方法

index 記錄目前最大值的索引，large 暫存最大值。每趟先假設索引 $0$ 的元素最大，再由索引 $1$ 掃描至 $i$；遇到更大的元素時更新 large 和 index。掃描結束後，將最大值與索引 $i$ 的元素交換。

Selectsort(x, n)

int x[], n;

{
 int i, index, j, large;

 for (i = n-1; i > 0; i--) {
 index = 0;
 large = x[0];

 for (j = 1; j <= i; j++) {
 if (x[j] > large) {
 large = x[j];
 index = j;
 }
 }

 x[index] = x[i];
 x[i] = large;
 }
}

以題目陣列為例：

• 第 1 趟掃描索引 $0$ 至 $7$，最大值 $92$ 在索引 $5$，與索引 $7$ 的 $33$ 交換：[25,57,48,37,12,33,86,92]