111 司法特考三等 檢察事務官電子資訊組 程式語言 考古題詳解

核心觀念

1. 剖析樹（Parse Tree / Concrete Syntax Tree）之定義： 在形式語言與編譯器理論中，剖析樹是依據上下文無關文法（Context-Free Grammar, CFG / BNF）之產生規則（Production Rules），以樹狀階層結構視覺化呈現字串語法推導過程的圖形表示法。

• 樹根節點（Root）：文法的起始符號（Start Symbol），本題為 $\langle assign\rangle$。
• 內部節點（Internal Nodes）：代表非終端符號（Non-terminal Symbols），如 $\langle assign\rangle$、$\langle id\rangle$、$\langle expr\rangle$。
• 葉節點（Leaf Nodes）：由左至右排列，代表終端符號（Terminal Symbols），包含變數名稱（$A, B, C$）與運算子／標點符號（$:=, +, *$），其由左至右的走訪結果即為輸入語句（稱為此樹的產出，Yield）。
• 分支（Subtrees/Edges）：代表某個產生規則的套用（例如父節點為 $\langle expr\rangle$，子節點為 $\langle expr\rangle$、$+$、$\langle expr\rangle$）。

2. 文法之二義性（Ambiguity）： 若一組 BNF 文法中，存在至少一個語句可以建構出兩棵或兩棵以上不同結構的剖析樹（或對應兩種不同的最左推導／最右推導），則稱該文法具有二義性（Ambiguous Grammar）。 題給文法未規範加法 $+$ 與乘法 $*$ 的「運算子優先權（Precedence）」與「結合性（Associativity）」，故針對包含複合運算的語句 $A:=B+C*A$ 會產生歧義。

解題方法

本題解題切入點分為兩大部分：

1. 說明剖析樹：條列定義、節點性質（樹根、內部節點、葉節點）以及剖析樹與產生規則推導之對應關係。
2. 建構兩種剖析樹：

• 觀察待剖析語句 $A:=B+C*A$：
• 最外層均必須先展開指派規則：$\langle assign\rangle \rightarrow \langle id\rangle := \langle expr\rangle$，左側 $\langle id\rangle \rightarrow A$。
• 等號右側的運算式 $\langle expr\rangle$ 需導出 $B+C*A$。
• 歧義來源在於右側運算式中「加法」與「乘法」的階層高低：
• 剖析樹一（乘法優先，先乘後加）：外層展開為 $\langle expr\rangle + \langle expr\rangle$，右側子樹再展開為 $\langle expr\rangle * \langle expr\rangle$。此結構對應之語意為 $A := B + (C * A)$。
• 剖析樹二（加法優先，先加後乘）：外層展開為 $\langle expr\rangle * \langle expr\rangle$，左側子樹再展開為 $\langle expr\rangle + \langle expr\rangle$。此結構對應之語意為 $A := (B + C) * A$。

選項分析

本題為申論與作圖題，無選擇題選項。此處針對本題文法二義性所衍生的兩種推導路徑進行語意結構對比分析：

1. 路徑一（語意：$B+(C*A)$）： 乘法節點 $*$ 處於剖析樹較深之子樹，加法節點 $+$ 處於較淺之階層。

核心觀念

1. 氣泡排序法（Bubble Sort）基本原理： 屬於比較排序法（Comparison Sort）。其核心機制為「相鄰元素兩兩比較」，若順序不符目標（如前項大於後項），則立即對調（Swap）。每一輪掃描（Pass）會將未排序區間中的最大值如同氣泡浮出水面般，逐步推進至該區間的最右端。
2. 演算法複雜度與性質：

• 時間複雜度：
• 最差狀況（反序）：$O(n^2)$
• 平均狀況：$O(n^2)$
• 最佳狀況（已排序且加入旗標最佳化）：$O(n)$
• 空間複雜度：$O(1)$，屬於原地排序（In-place Sort），僅需常數個額外輔助變數。
• 穩定性（Stability）：屬於穩定排序（Stable Sort），因為兩相鄰元素若鍵值相等，則不進行對調，保有原本之相對順序。

解題方法

本題要求將包含 $6$ 個元素之陣列 $A = [5, 3, 8, 6, 7, 2]$ 由小而大（遞增）排序。

1. 演算法架構設計：

• 外層迴圈（變數 $i$）：控制進行的回合數。長度為 $n$ 的陣列最多需執行 $n - 1$ 回合（$i$ 從 $0$ 到 $n - 2$）。
• 內層迴圈（變數 $j$）：負責相鄰兩元素的比較與交換。由於每完成一個回合，該回合的最大值便已固定在陣列末端，故第 $i$ 回合只需比較至未排序區間邊界，即 $j$ 從 $0$ 到 $n - 2 - i$。
• 元素交換（Swap）：以暫存變數 temp 進行三步驟數值交換。

2. 追蹤推導過程（Trace Process）： 初始狀態：$[5, 3, 8, 6, 7, 2]$，長度 $n = 6$。

• 第 1 回合（Pass 1）：比較範圍索引 $0 \le j \le 4$

• $j=0$：$5 > 3$ $\rightarrow$ 交換 $\rightarrow$ $[3, 5, 8, 6, 7, 2]$

• $j=1$：$5 \le 8$ $\rightarrow$ 不換 $\rightarrow$ $[3, 5, 8, 6, 7, 2]$

• $j=2$：$8 > 6$ $\rightarrow$ 交換 $\rightarrow$ $[3, 5, 6, 8, 7, 2]$

• $j=3$：$8 > 7$ $\rightarrow$ 交換 $\rightarrow$ $[3, 5, 6, 7, 8, 2]$

• $j=4$：$8 > 2$ $\rightarrow$ 交換 $\rightarrow$ $[3, 5, 6, 7, 2, 8]$

• 本回合完成，數值 $8$ 已定位於索引 $5$。

• 第 2 回合（Pass 2）：比較範圍索引 $0 \le j \le 3$

• $j=0$：$3 \le 5$ $\rightarrow$ 不換

• $j=1$：$5 \le 6$ $\rightarrow$ 不換

• $j=2$：$6 \le 7$ $\rightarrow$ 不換

• $j=3$：$7 > 2$ $\rightarrow$ 交換 $\rightarrow$ $[3, 5, 6, 2, 7, 8]$

• 本回合完成，數值 $7$ 已定位於索引 $4$。

• 第 3 回合（Pass 3）：比較範圍索引 $0 \le j \le 2$

• $j=0$：$3 \le 5$ $\rightarrow$ 不換

• $j=1$：$5 \le 6$ $\rightarrow$ 不換

• $j=2$：$6 > 2$ $\rightarrow$ 交換 $\rightarrow$ $[3, 5, 2, 6, 7, 8]$

• 本回合完成，數值 $6$ 已定位於索引 $3$。

• 第 4 回合（Pass 4）：比較範圍索引 $0 \le j \le 1$

• $j=0$：$3 \le 5$ $\rightarrow$ 不換

• $j=1$：$5 > 2$ $\rightarrow$ 交換 $\rightarrow$ $[3, 2, 5, 6, 7, 8]$

• 本回合完成，數值 $5$ 已定位於索引 $2$。

• 第 5 回合（Pass 5）：比較範圍索引 $0 \le j \le 0$

• $j=0$：$3 > 2$ $\rightarrow$ 交換 $\rightarrow$ $[2, 3, 5, 6, 7, 8]$

• 本回合完成，所有元素已全數就位。

最終排序結果為：$[2, 3, 5, 6, 7, 8]$。

選項分析

核心觀念

本題考查遞迴演算法（Recursive Algorithm）之追蹤分析與函數呼叫次數（Function Invocations / Call Tree）之計算：

1. 費氏數列（Fibonacci Sequence）定義： $FIB(0) = 0,\quad FIB(1) = 1,\quad FIB(n) = FIB(n-1) + FIB(n-2) \quad (n \ge 2)$
2. 遞迴呼叫次數之遞迴關係式（Recurrence Relation）： 計算 $FIB(n)$ 時，若包含自身呼叫，其總呼叫次數 $C(n)$ 滿足： $C(0) = 1,\quad C(1) = 1,\quad C(n) = 1 + C(n-1) + C(n-2) \quad (n \ge 2)$
3. 遞迴呼叫樹（Recursion Tree）：遞迴執行的軌跡可視為一棵樹狀結構，樹中的節點總數即為函數被呼叫的總次數。

解題方法

一、計算 $FIB(4)$ 之值

依題意給定之定義，自底向上（Bottom-up）依序推導：

• $FIB(0) = 0$
• $FIB(1) = 1$
• $FIB(2) = FIB(1) + FIB(0) = 1 + 0 = 1$
• $FIB(3) = FIB(2) + FIB(1) = 1 + 1 = 2$
• $FIB(4) = FIB(3) + FIB(2) = 2 + 1 = 3$

故 $FIB(4)$ 之值為 $3$。

二、計算呼叫 $FIB(n)$ 之次數

可透過「遞迴呼叫樹」或「遞迴關係式」兩種方式求解：

方法一：繪製遞迴呼叫樹（Recursion Tree）展開分析

將呼叫 $FIB(4)$ 的展開過程表示為樹狀結構：

 FIB(4)
 / \
 FIB(3) FIB(2)
 / \ / \
 FIB(2) FIB(1) FIB(1) FIB(0)
 / \
 FIB(1) FIB(0)

統計樹中各層之呼叫次數：

• 第 0 層（根節點）：$FIB(4)$，共 $1$ 次。
• 第 1 層：$FIB(3), FIB(2)$，共 $2$ 次。
• 第 2 層：
• 來自 $FIB(3)$：$FIB(2), FIB(1)$
• 來自 $FIB(2)$：$FIB(1), FIB(0)$
• 共 $4$ 次。
• 第 3 層：
• 來自第 2 層之 $FIB(2)$：$FIB(1), FIB(0)$
• 共 $2$ 次。

各函數呼叫次數明細：

• 呼叫 $FIB(4)$：$1$ 次
• 呼叫 $FIB(3)$：$1$ 次
• 呼叫 $FIB(2)$：$2$ 次
• 呼叫 $FIB(1)$：$3$ 次
• 呼叫 $FIB(0)$：$2$ 次

總呼叫次數 $= 1 + 1 + 2 + 3 + 2 = 9$ 次。

核心觀念

本題測驗二維陣列（Two-Dimensional Array）於一維實體記憶體空間中的位址對映公式（Address Mapping Function）。常見的儲存順序有兩種：

1. 以列為主（Row-Major Order）：元素依列順序由左至右、由上而下連續存放（C、C++、Java 等語言採用）。
2. 以行為主（Column-Major Order）：元素依行順序由上而下、由左至右連續存放（Fortran、MATLAB 等語言採用）。

定址公式： 設二維陣列宣告為 $A[L_1..U_1, L_2..U_2]$，其中：

• 列數（Row count）$R = U_1 - L_1 + 1$
• 行數（Column count）$C = U_2 - L_2 + 1$
• 基準位址（Base Address）為 $\text{Loc}(A[L_1, L_2])$
• 每個陣列元素佔用的記憶體大小為 $d$（單位：Bytes 或 Words）

對於任意元素 $A[i, j]$ 之位址公式：

• 以列為主（Row-Major）： $\text{Loc}(A[i, j]) = \text{Loc}(A[L_1, L_2]) + [(i - L_1) \times C + (j - L_2)] \times d$
• 以行為主（Column-Major）： $\text{Loc}(A[i, j]) = \text{Loc}(A[L_1, L_2]) + [(j - L_2) \times R + (i - L_1)] \times d$

解題方法

1. 整理題目已知條件

• 陣列宣告：$A[1..3, 1..5]$
• 第一維（列）：下界 $L_1 = 1$，上界 $U_1 = 3$，總列數 $R = 3 - 1 + 1 = 3$
• 第二維（行）：下界 $L_2 = 1$，上界 $U_2 = 5$，總行數 $C = 5 - 1 + 1 = 5$
• 起始位址：$\text{Loc}(A[1, 1]) = 100$
• 目標元素：$A[2, 4]$，即列索引 $i = 2$、行索引 $j = 4$
• 題目未特別指定元素所佔空間大小，依國家考試慣例假設每個元素佔用 $1$ 個記憶體單位（即 $d = 1$）。

2. 以列為主（Row-Major Order）推導與計算

• 推導步驟： 至目標元素 $A[2, 4]$ 前，需先依序跨過：

1. 完整的第 $1$ 列（共跨過 $i - L_1 = 2 - 1 = 1$ 列），每列有 $C = 5$ 個元素，共跨過 $1 \times 5 = 5$ 個元素。
2. 第 $2$ 列中目標元素前方的元素（即 $A[2, 1], A[2, 2], A[2, 3]$，共 $j - L_2 = 4 - 1 = 3$ 個元素）。

• 累積跨過的元素個數（Offset）：