111 高普考高考三級 資訊處理 資料結構 考古題詳解

核心觀念

本題考查資料結構中「堆疊（Stack）應用：中序運算式（Infix）轉後序運算式（Postfix）」的經典演算法追蹤（Trace）。

1. 基本轉換原理：

• 運算元（Operand）：不改變相對順序，讀取後直接輸出至後序運算式字串（postfix string）。
• 運算子（Operator）：依照優先順序（Precedence）與結合性（Associativity）暫存於堆疊（operstk）中。當新讀入運算子的優先權低於或等於堆疊頂端運算子時，堆疊頂端運算子必須先彈出（pop）輸出，以確保優先運算者先出現。

2. 括弧處理機制：

• 演算法透過自訂布林函數 precedence(op1, op2) 規範運算子間的輸出關係。
• 左括弧 (：進入堆疊後扮演「隔離邊界」角色。依題目定義 precedence('(', op) = FALSE，表示左括弧位於堆疊內時，任何後續運算子皆無法將其彈出，直接推入堆疊。
• 右括弧 )：代表該子運算式結束。依題目定義 precedence(op, ')') = TRUE（除 ( 外），會強制將堆疊中累積至左括弧為止的所有運算子依序彈出輸出；當碰觸到左括弧時（precedence('(', ')') = FALSE），迴圈中止，演算法透過 else topsymb = pop(operstk); 將對應的左括弧彈出消除，且右括弧本身不推入堆疊，達成「後序運算式不含括弧」的特性。

3. 終止處理（End of String, eos）：

• 讀取完整運算式後，將堆疊內殘留的所有運算子由頂端至底端全數彈出並輸出。

解題方法

給定中序運算式為：$(2+3)\times4$。 堆疊 operstk 初始狀態為空堆疊，以下逐步追蹤各輸入字元之執行動作：

1. 讀入 symb = '('：

• symb 為運算子。
• operstk 目前為空，不執行彈出迴圈。
• 滿足 empty(operstk) || symb != ')'，執行 push(operstk, '(')。
• 狀態：postfix string 為空；operstk 為 (。

2. 讀入 symb = '2'：

• symb 為運算元，直接加入後序字串。
• 狀態：postfix string 為 2；operstk 為 (。

3. 讀入 symb = '+'：

• symb 為運算子。
• 檢查 precedence(stacktop(operstk), '+')，即 precedence('(', '+') = FALSE，不執行彈出迴圈。
• 滿足 empty(operstk) || symb != ')'，執行 push(operstk, '+')。
• 狀態：postfix string 為 2；operstk 為 ( +（頂端為 +）。

4. 讀入 symb = '3'：

• symb 為運算元，直接加入後序字串。
• 狀態：postfix string 為 23；operstk 為 ( +。

核心觀念

1. 佇列（Queue）之操作特性： 佇列為先進先出（FIFO, First-In-First-Out）的線性資料結構。所有新增操作（Enqueue / Insert）皆在隊尾（Rear / Back）進行；刪除操作（Dequeue / Remove）則在隊首（Front）進行。
2. 鏈結串列（Linked List）指標維護： 在不具備虛擬頭節點（Dummy Head）的單向鏈結佇列中：

• front 指向佇列的第一個節點。
• rear 指向佇列的最後一個節點。
• 當佇列為空時，front == NULL 且 rear == NULL。

3. K&R C 函式宣告風格： 本題採用經典教科書（如 Tenenbaum 等所著之《Data Structures Using C》）常見的 K&R C 語法格式定義函式參數，解題時遵循題目的變數與結構定義實作函式內容即可。

解題方法

將整數 $x$ 加入佇列的程序可分為四個關鍵步驟：

1. 配置新節點並初始化欄位： 呼叫題目提供的 getnode 函式取得一塊新的節點記憶體，並令指標變數 p 指向它。

• 資料欄位賦值：p->info = x;
• 指標欄位初始化：因為新節點即將成為佇列的最後一個節點，其後續無其他節點，故必須設定 p->next = NULL;。

2. 檢查佇列加入前是否為空： 依題意需檢查串列加入前是否為空。在合法的佇列狀態下，佇列為空等價於 pq->front == NULL（或 pq->rear == NULL）。
3. 分流處理串列串接：

• 狀況一：佇列原為空（pq->front == NULL 或 pq->rear == NULL）： 此時新節點 p 不僅是隊尾，也是隊首，因此必須將 pq->front 指向 p。
• 狀況二：佇列原非空： 原佇列最後一個節點為 pq->rear，必須將原最後節點的 next 指標接上新節點，即執行 pq->rear->next = p;。

4. 更新隊尾指標： 無論原佇列是否為空，新節點加入後皆成為佇列的最後一個節點，因此最後必須將 pq->rear 更新指向新節點 p（pq->rear = p;）。

解題技巧

核心觀念

1. 二元搜尋樹（Binary Search Tree, BST）之定義： 對於樹中任意節點 $T$：

• 若其左子樹不為空，則左子樹上所有節點的值皆小於節點 $T$ 的值。
• 若其右子樹不為空，則右子樹上所有節點的值皆大於節點 $T$ 的值。
• 其左、右子樹亦分別為二元搜尋樹。

2. 走訪（Traversal）特性：

• 前序追蹤（Preorder Traversal）：走訪順序為「根節點 $\to$ 左子樹 $\to$ 右子樹」。序列之首個元素即為樹（或子樹）之根節點。
• 中序追蹤（Inorder Traversal）：走訪順序為「左子樹 $\to$ 根節點 $\to$ 右子樹」。任何二元搜尋樹經中序追蹤輸出之結果，必然為由小至大的嚴格遞增排序序列。

3. 前序序列重建 BST 之唯一性： 一般二元樹僅給前序序列無法唯一決定樹形，但 BST 具備鍵值大小之排序約束。只要依前序序列確定根節點後，序列中凡小於根節點者必屬左子樹、大於根節點者必屬右子樹，故單靠前序序列即可唯一決定樹形。

解題方法

一、建構二元搜尋樹（分治法推導）

給定前序追蹤序列：$14, 4, 3, 9, 7, 5, 15, 18, 16, 17, 20$

1. 確定樹根（Root）與左右子樹劃分：

• 序列首位為 $14$，故整棵樹之根節點為 $14$。
• 比 $14$ 小之連續數值為左子樹前序序列：$\{4, 3, 9, 7, 5\}$。
• 比 $14$ 大之連續數值為右子樹前序序列：$\{15, 18, 16, 17, 20\}$。

2. 遞迴建構左子樹（以 $14$ 之左子樹為例）：

• 前序序列 $\{4, 3, 9, 7, 5\}$ 之首位為 $4$，故 $4$ 為 $14$ 之左子節點。
• 比 $4$ 小者為左子樹：$\{3\}$，故 $3$ 為 $4$ 之左子節點（葉節點）。
• 比 $4$ 大者為右子樹前序序列：$\{9, 7, 5\}$。
• 首位為 $9$，故 $9$ 為 $4$ 之右子節點。
• 比 $9$ 小者為左子樹前序序列：$\{7, 5\}$，右子樹為空。
• 首位為 $7$，故 $7$ 為 $9$ 之左子節點。
• 比 $7$ 小者為左子樹：$\{5\}$，故 $5$ 為 $7$ 之左子節點（葉節點），右子樹為空。

3. 遞迴建構右子樹（以 $14$ 之右子樹為例）：

• 前序序列 $\{15, 18, 16, 17, 20\}$ 之首位為 $15$，故 $15$ 為 $14$ 之右子節點。
• 比 $15$ 小者無元素，故 $15$ 之左子樹為空。

核心觀念

1. 圖形之邊集合表示法（Edge Array / Coordinate List）： 本題定義結構型態 edge 包含 (col, row, weight)，以陣列 $a$ 儲存無向圖 $G=(V,E)$ 之各條邊及其權重值。無向邊連接點 col 與 row，其連接關係具對稱性，即邊 $(u, v)$ 與 $(v, u)$ 視為同一條邊。
2. 最小擴張樹（Minimum Spanning Tree, MST）： 給定一個連通且具有權重的無向圖 $G=(V, E)$，其最小擴張樹為包含圖中所有頂點 $V$ 的無環連通子圖（樹），且所有樹邊之權重總和為最小。若 $|V| = n$，則擴張樹恰有 $n - 1$ 條邊。本題頂點數 $|V|=6$，故擴張樹必由 5 條邊構成。
3. Prim 演算法（Prim's Algorithm）： 屬於貪婪演算法（Greedy Algorithm）。運作機制如下：

• 令集合 $U$ 為已加入擴張樹之頂點集合，初始時 $U = \{ \text{起點} \}$。
• 在每一步驟中，自跨越割（Cut）的邊（即一端在 $U$、另一端在 $V \setminus U$ 的候選邊）中，挑選權重最小的邊 $(u, v)$，將頂點 $v$ 納入 $U$。
• 重複上述步驟，直到所有頂點皆加入 $U$（即 $U = V$）為止。

解題方法

步驟一：繪製陣列 $a$ 所儲存之圖形 $G=(V, E)$

根據題目陣列 $a$ 的資料，整理圖形的頂點與邊：

• 頂點集合：$V = \{0, 1, 2, 3, 4, 5\}$
• 邊與權重集合（共 9 條邊）：
• $(0, 4)$ 權重 $1$
• $(0, 3)$ 權重 $2$
• $(3, 4)$ 權重 $3$
• $(1, 2)$ 權重 $7$
• $(2, 4)$ 權重 $10$
• $(2, 3)$ 權重 $15$
• $(0, 5)$ 權重 $20$
• $(1, 5)$ 權重 $24$
• $(2, 5)$ 權重 $25$

此圖形由頂點群體 $\{0, 3, 4\}$ 與 $\{1, 2, 5\}$ 構成，兩者由邊 $(0, 5)$、$(4, 2)$、$(3, 2)$ 相互連接。圖形 $G$ 結構繪製如下：

 (20)
 [0] ================================ [5]
 / \ /|
 / \ (1) (24) / |
 (2)/ \ / |
 / [4] ---------- (10) --------- [2] | (25)
 / / / | |
 / (3) / (15) / | |
 [3] ---+ / | |
 | / | |
 +----------------------------------+ |(7)
 | |
 [1]+

步驟二：執行 Prim 演算法（由節點 0 開始）

起始設定：$U = \{0\}$，$V \setminus U = \{1, 2, 3, 4, 5\}$，最小擴張樹邊集合 $E_{\text{MST}} = \emptyset$。