114 關務特考三等 資訊處理(選試英文)科別 資料結構 考古題詳解
第 一 題25 分
給予一前序（preorder）表示式 和後序（postorder）表示式 ，試畫出所有可能的二元樹。
登入後即可作答並保存紀錄。
核心觀念
前序走訪（preorder）順序為「根、左子樹、右子樹」；後序走訪（postorder）順序為「左子樹、右子樹、根」。題目給定前序 、後序 ，要求列出所有符合兩種走訪結果的二元樹。
若未限定為滿二元樹，只有一個子節點的節點可以把該子樹放在左邊或右邊，走訪結果仍相同。因此，前序與後序通常無法唯一決定二元樹。
解題方法
前序第一個節點是根，所以根為 ；後序最後一個節點也是根，與此一致。
其餘節點在前序中的排列是 ，在後序中的排列是 。這表示每個節點的子樹走訪次序都必須沿著同一條根到葉的路徑延伸：若某節點有兩個非空子樹，前序會先走左子樹、後序也會先走左子樹，兩種順序就不會呈現完全相反的排列。因此，各節點至多只有一個子節點，整棵樹必為單枝鏈。
四個節點組成的鏈有三個父子關係： 與 、 與 、 與 。每個子節點都可選擇接在父節點左側或右側，所以共有 棵二元樹。
第 二 題25 分
假設每個運算元都是一位整數，使用堆疊方法，模擬後序式 的計算過程。
登入後即可作答並保存紀錄。
核心觀念
後序式（Postfix）把運算子放在運算元之後。使用堆疊計算時，由左至右逐一讀取：
- 遇到運算元，就推入堆疊。
- 遇到二元運算子，就依序彈出右運算元、左運算元，計算「左運算元 運算子 右運算元」，再將結果推回堆疊。
本題的運算元皆為一位整數，因此後序式中的 25、42、-6、+6 分別代表運算元 ，運算子為 。
解題方法
由左至右掃描 ，以堆疊記錄尚未完成運算的數值：
| 讀取項目 | 動作 | 堆疊（底 → 頂） |
|---|---|---|
| 推入 | ||
| 推入 | ||
| 彈出 ，計算 ，推回 | ||
| 推入 | ||
| 推入 |
第 三 題25 分
假設現有五個字母 、、、、 的頻率分別為 、、、、，請依步驟建構霍夫曼樹（Huffman Tree）。
登入後即可作答並保存紀錄。
核心觀念
霍夫曼樹（Huffman Tree）用來為不同頻率的符號建立不等長編碼，使加權路徑長度最小。建樹時反覆選取頻率最低的兩個節點，合併成一個父節點，其頻率為兩者相加；再將父節點放回集合，直到只剩一個根節點。
解題方法
依頻率由小到大排列，每一步合併目前最小的兩個節點：
| 步驟 | 合併的節點 | 父節點頻率 | 合併後的節點集合 |
|---|---|---|---|
| 1 | 、 | ||
| 2 | 、 | ||
| 3 | 、 | ||
| 4 | 、 | 根節點 |
因此，霍夫曼樹的合併順序為：
第 四 題25 分
請逐步寫出下列使用遞迴函式的呼叫與輸出過程。
#include <iostream> using namespace std; int A(int n, int c = 1) { if (n == 0) return c + 1; return A(n - 2, c * n); } int main() { cout << A(6) << endl; return 0; }
登入後即可作答並保存紀錄。
核心觀念
本題考遞迴函式的呼叫過程，以及參數的預設值。函式 A 的第二個參數 c 預設為 ，所以呼叫 A(6) 等同於呼叫 A(6, 1)。
函式每次呼叫會在 n 尚未為 時，將 n 減 ，並將目前的 n 乘上 c 後傳入下一層；當 n=0 時，回傳 。
解題方法
依序列出每次遞迴呼叫時的參數 ：
| 呼叫 | 傳入的參數 | 執行結果 |
|---|---|---|
| 第 1 次 | 呼叫 A(4, 1 × 6) | |
| 第 2 次 | 呼叫 A(2, 6 × 4) | |
| 第 3 次 | 呼叫 A(0, 24 × 2) | |
| 第 4 次 | 符合終止條件，回傳 |