112 公務人員升官等薦任 資訊處理 資料結構 考古題詳解

核心觀念

二維陣列的元素位址，取決於陣列在記憶體中的儲存順序。本題依一般程式語言的 row-major（列優先） 方式計算：同一列的元素依欄索引連續存放，再依列索引排列。

每個元素占 $4$ Bytes，陣列有 $18$ 列、每列 $10$ 個元素，因此：

其中 $\operatorname{Base}$ 是 $A[0][0]$ 的位址。若已知其他元素的位址，也可先求出兩元素間的索引差，再換算成位元組差。

解題方法

（一）計算陣列所占空間

陣列共有 $18\times 10=180$ 個元素，每個元素占 $4$ Bytes：

（二）由 $A[0][0]$ 求 $A[5][3]$ 的位址

從 $A[0][0]$ 到 $A[5][3]$，跨過 $5$ 列，每列 $10$ 個元素，再往右移 $3$ 個元素，因此索引差為：

位移量為：

核心觀念

• 前序、中序、後序是運算式的三種表示法：運算子分別置於運算元之前、中間或之後。後序式不需括號即可依運算順序計算。
• 中序轉後序時，依運算子優先順序安排輸出；括號內先處理，指數運算優先於乘除，乘除優先於加減。
• 後序轉中序時，從左至右掃描：運算元推入堆疊；遇到二元運算子，依序取出右運算式與左運算式，組成「（左運算式 運算子 右運算式）」後推回堆疊。

（一）中序轉後序

原式為：

依括號與運算子優先順序分段轉換：

1. $(A+B)$ 轉為 $AB+$。
2. $(D-E)$ 轉為 $DE-$；再與 $C$ 組成 $C^{(D-E)}$，其後序式為 CDE-^。
3. $C^{(D-E)}+F$ 轉為 $CDE-^F+$。
4. 將前述兩個括號相乘，得到 $AB+CDE-^F+*$。
5. 最後減去 $G$，在式尾加入 $G-$。

因此，後序式為：

（二）後序轉中序

將原式逐段依後序運算規則組合。每遇到運算子，就把堆疊頂端的兩個運算式取出，先取出的作為右運算式，後取出的作為左運算式。

核心觀念

二元搜尋樹（Binary Search Tree, BST）符合以下規則：每個節點的左子樹鍵值都小於該節點，右子樹鍵值都大於該節點。

刪除只有一個或沒有子節點的節點時，可以直接接回其子樹；刪除有兩個子節點的節點時，為了維持 BST，通常以其中序前驅或中序後繼取代：

• 中序前驅：左子樹中的最大值。
• 中序後繼：右子樹中的最小值。

題目要求「維持最小變動」，因此取代 48 後，只需再刪除該前驅或後繼原本的位置。

解題方法

原樹中，48 的左子樹最大值為 45，右子樹最小值為 55，所以有兩種取代方式。

方法一：以中序前驅 45 取代 48

45 原本是 41 的右子節點，刪除 45 後，將 45 放到根節點位置；其餘節點連結維持不變。

 45
 / \
 37 77
 \ /
 41 66
 / / \
 38 55 70
 \
 40

核心觀念

二元樹可用兩種方式表示：

• 陣列表示法：採用根節點索引為 $1$ 的慣例。索引為 $i$ 的節點，其左子節點位於 $2i$，右子節點位於 $2i+1$。
• 鏈結串列表示法：每個節點包含資料欄位，以及指向左子節點、右子節點的指標；沒有子節點時，指標為 NULL。

解題方法

由圖可讀出：$1$ 是根節點；$1$ 的左、右子節點分別為 $2$、$3$；$2$ 的左子節點為 $4$；$4$ 的左子節點為 $6$；$3$ 的右子節點為 $5$。

依陣列表示法逐層定位：

• 節點 $1$ 在索引 $1$。
• 節點 $2$、$3$ 分別在索引 $2$、$3$。
• 節點 $4$ 是節點 $2$ 的左子節點，位於索引 $2 \times 2=4$。
• 節點 $6$ 是節點 $4$ 的左子節點，位於索引 $2 \times 4=8$。
• 節點 $5$ 是節點 $3$ 的右子節點，位於索引 $2 \times 3+1=7$。

陣列表示法

核心觀念

Prim 演算法從指定起點逐步擴張生成樹。每一步都從「已納入生成樹的節點」連到「尚未納入的節點」的邊中，選擇權重最小者；如此直到所有節點都納入。若圖有 $n$ 個節點，最小生成樹會有 $n-1$ 條邊。

解題方法

從起點 $a$ 開始，每一步列出連接樹內與樹外節點的候選邊，選取權重最小者：

核心觀念

合併排序（Merge Sort）採用「分而治之」：

1. 將序列反覆切成左右兩半，直到每個子序列只剩一個元素。
2. 單一元素視為已排序。
3. 逐層合併相鄰的已排序子序列；每次比較兩邊目前最前面的元素，將較小者放入結果序列，直到合併完成。

本題共有 $16$ 個元素，可連續對半切分為 $8、4、2、1$ 個元素的區段，再逐層合併回完整序列。

解題方法

一、分割序列

原始序列：

第一層分成左右兩半：

第二層各自再分成兩半：

第三層繼續分割，直到每組只剩兩個元素：

二、由小組開始合併

先將每組兩個元素排成遞增順序：

合併相鄰兩組。例如，合併 $[3,12]$ 與 $[11,13]$：依序比較兩組最前端元素，取出 $3、11、12、13$，得到 $[3,11,12,13]$。其餘各組同理：