108 高普考高考三級 資訊處理 程式語言 考古題詳解

核心觀念

1. 馬克勞林級數（Maclaurin Series）逼近指數函數 $e^x$： 指數函數 $e^x$ 在 $x=0$ 處的泰勒展開式（即馬克勞林級數）定義為： $e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!} = 1 + \frac{x^1}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots$ 當電腦進行數值逼近計算時，通常截取有限項進行累加。

2. 迴圈狀態追蹤（Loop Invariant & Tracing）： 追蹤迴圈內部變數的更新規律：

• 累加變數：$e$
• 次方累乘：$\text{exponent} = x^k$
• 階乘累乘：$\text{factorial} = k!$
• 控制變數：$\text{number}$ 自 $1$ 遞增至 $\text{accuracy}-1$

3. 遞迴程式設計（Recursion）的兩大要素：

• 終止條件（Base Case）：當 $\text{accuracy} \le 1$ 時停止遞迴，回傳第 $0$ 項的值 $1.0$。
• 遞迴關係式（Recursive Step）：將求「前 $\text{accuracy}$ 項和」轉化為「前 $\text{accuracy}-1$ 項和」加上「第 $\text{accuracy}-1$ 項之值」，滿足數學歸納法的推導邏輯。

---

解題方法

一、推導變數 $e$ 的數學式與運算意義

1. 變數初始狀態：

• $e = 1.0$（即級數的第 $0$ 項：$\frac{x^0}{0!} = 1$）
• $\text{exponent} = 1.0$
• $\text{factorial} = 1$
• $\text{number} = 1$

2. 迴圈執行過程追蹤： 迴圈條件為 while (number < accuracy)：

• 第 1 次迭代（$\text{number} = 1$）：
• $\text{exponent} = 1.0 \times x = x^1$
• $\text{factorial} = 1 \times 1 = 1!$
• $e = 1.0 + \frac{x^1}{1!}$
• $\text{number}$ 遞增為 $2$
• 第 2 次迭代（$\text{number} = 2$）：
• $\text{exponent} = x^1 \times x = x^2$
• $\text{factorial} = 1! \times 2 = 2!$
• $e = 1.0 + \frac{x^1}{1!} + \frac{x^2}{2!}$
• $\text{number}$ 遞增為 $3$
• 第 $k$ 次迭代（$\text{number} = k$）：
• 累加項為 $\frac{x^k}{k!}$
• 迴圈終止： 當 $\text{number} = \text{accuracy}$ 時終止迴圈。因此，最後累加的項為 $\text{number} = \text{accuracy}-1$ 的項。

3. 數學式結論： 變數 $e$ 所計算的數學式為： $e = \sum_{k=0}^{\text{accuracy}-1} \frac{x^k}{k!} = 1 + \frac{x^1}{1!} + \frac{x^2}{2!} + \cdots + \frac{x^{\text{accuracy}-1}}{(\text{accuracy}-1)!}$ 此式即為計算指數函數 $e^x$ 之馬克勞林級數展開式的前 $\text{accuracy}$ 項近似值。

---

二、遞迴方法 etx(int accuracy, int x) 設計

題目要求使用固定簽名 public static double etx(int accuracy, int x)：

1. 拆解子問題： 定義前 $n$ 項之和為 $S(n)$：

• 當 $n \le 1$ 時：$S(1) = 1.0$。

核心觀念

本題出自經典教材（Deitel & Deitel 的《Java How to Program》）之經典鏈結串列（Linked List）章節，主要評量以下核心觀念：

1. 物件導向建構子串接（Constructor Chaining）：多載建構子之間透過 this(...) 相互呼叫的傳值流程與物件屬性初始化。
2. 單向鏈結串列（Singly Linked List）的狀態追蹤與指標操作：節點的新增、走訪、前端刪除（removeFromFront）及尾端刪除（removeFromBack）的指標指向與邊界條件。
3. Java 例外處理機制（Exception Handling）：在串列為空時丟出自訂執行時期例外（RuntimeException），以及 try-catch 區塊在拋出例外時的流程轉移與 printStackTrace 輸出。

---

解題方法

第 (1) 小題：建構子呼叫流程與屬性值推導

1. 呼叫的方法（建構子）與傳遞之參數值：

• 當執行 List<Integer> list = new List<>; 時，程式會先呼叫 List 類別的無參數建構子 public List，此時未傳入引數（無參數）。
• 在 public List 內部，第一行敘述為 this("list");，此敘述會進一步呼叫同類別中帶有一個字串參數的多載建構子 public List(String listName)，傳送的參數值為字串 "list"。
• （List(String) 會隱式呼叫其父類別 Object 的無參數建構子 super，完成物件實體化）。

2. 新物件 list 的屬性值：

• 進入 public List(String listName) 後，執行：
• name = listName;：屬性 name 被指派為 "list"。
• firstNode = lastNode = null;：指標屬性 firstNode 與 lastNode 均被設為 null。
• 因此，建立完成後該物件的三個屬性值分別為：
• name："list"
• firstNode：null
• lastNode：null

---

第 (2) 小題：程式執行追蹤與印出內容

依序追蹤 ListTest.java 內 main 方法中 try 區塊的執行步驟：

1. 建立串列：list 初始化，name = "list"，串列為空。
2. 前端插入資料：

• list.insertAtFront(-1);：串列內容為 [-1]。
• list.insertAtFront(99);：新節點插在最前端，串列內容為 [99, -1]。

3. 第一次 list.print;：

• 串列非空，走訪印出每個節點的 data：
• 印出：

The list is: 99 -1 

（注意 -1 後方有一空格並換行）。 4. 前端刪除資料：

• int removedItem = list.removeFromFront;：移除首節點 99，串列剩餘 [-1]。
• removedItem = list.removeFromFront;：移除首節點 -1，串列變為空串列（firstNode = lastNode = null）。

5. 第二次 list.print;：

• 此時 isEmpty 為 true，進入 if (isEmpty) 分支。
• 依據 System.out.printf("Empty %s%n", name);，印出：

Empty list

6. 第三次前端刪除與例外引發：

• 執行 removedItem = list.removeFromFront;。
• 由於此時串列已空，removeFromFront 內部判斷 isEmpty 為真，立即拋出例外： throw new EmptyListException(name);（其中包含訊息 "list is empty"）。

7. 例外處理與控制流程轉移：

• 例外拋出後，try 區塊隨即中斷，其後方的第三次 list.print; 不會被執行。
• 程式流程直接跳入 catch (EmptyListException emptyListException) 區塊，執行 emptyListException.printStackTrace;。
• printStackTrace 將例外類型、錯誤訊息及呼叫堆疊（Call Stack）輸出至標準錯誤輸出（System.err），首行印出：

EmptyListException: list is empty

其後跟隨引發錯誤之方法與行號追蹤資訊（如 at List.removeFromFront(...)、at ListTest.main(...)）。

---

第 (3) 小題：撰寫 removeFromBack

單向鏈結串列從尾端刪除節點時，無法像雙向鏈結串列那樣直接透過尾節點回溯，因此必須從頭走訪找到「倒數第二個節點」，並將其 nextNode 設為 null，使其成為新的 lastNode。

演算法步驟：

1. 檢查串列是否為空：若為空，拋出 EmptyListException(name)。
2. 暫存欲回傳之值：取出 lastNode.data。

核心觀念

本題出自民國 108 年公務人員高等考試三級考試（資訊處理類科）《程式語言》，主要評量以下核心觀念：

1. 物件導向程式設計（OOP）的繼承（Inheritance）與程式碼重用（Code Reuse）：

• 子類別 Stack<T> 透過關鍵字 extends 繼承父類別 List<T>，可直接調用父類別已定義之公開（public）或保護（protected）成員與方法。
• 子類別建構子必須透過 super 呼叫父類別建構子完成基底物件的初始化。

2. 泛型（Generics）機制：

• 使用型態參數（Type Parameter）$T$ 實現具型態安全性（Type Safety）的容器結構，避免執行時期型態轉換錯誤（ClassCastException）。

3. 堆疊（Stack）之抽象資料型態（ADT）與 LIFO 特性：

• 堆疊遵循後進先出（Last-In-First-Out, LIFO）原則，所有元素的插入（push）與刪除（pop）均限制在同一端（頂端，Top）。

4. 單向鏈結串列（Singly Linked List）的時間複雜度考量：

• 在單向鏈結串列中，於「前端（Front/Head）」進行節點插入與刪除僅需常數次指標變更，時間複雜度為 $O(1)$。
• 若在「後端（Back/Tail）」進行刪除，即使維護了尾端指標，仍需由前端走訪至倒數第二個節點更新指標，時間複雜度退化為 $O(n)$。
• 為滿足堆疊操作皆須為 $O(1)$ 之效能要求，堆疊頂端（Top）必須對應至鏈結串列的前端（Front）。

5. 例外傳遞（Exception Propagation）：

• pop 宣告拋出檢查例外（Checked Exception）EmptyListException，呼叫父類別前端刪除方法時，若串列為空會直接向上傳遞該例外，無需在子類別重複捕捉。

---

解題方法

本題為經典物件導向教科書（如 Deitel & Deitel《Java How to Program》之資料結構章節）的標準題型。上題（第二題）定義之泛型鏈結串列 List<T>，具備前端插入 insertAtFront(T) 與前端刪除 removeFromFront 等操作。解題切入點如下：

1. 建構子 public Stack：

• 任務：初始化堆疊。
• 作法：直接呼叫父類別建構子 super;（或傳入字串識別名稱 super("stack");）完成底層鏈結串列之建構。

2. 方法 public void push(T object)：

• 任務：將元素置入堆疊頂端。
• 作法：呼叫父類別繼承而來的 insertAtFront(object) 方法，將節點加入鏈結串列首端，耗時 $O(1)$。

3. 方法 public T pop throws EmptyListException：

• 任務：移出並回傳堆疊頂端的元素；若堆疊為空則丟出例外。

核心觀念

本題主要測驗物件導向程式設計（Object-Oriented Programming, OOP）在 Python 中的核心機制：

1. 類別定義與建構子（__init__）：物件實例化時的初始化行為與實例變數（Instance Attributes）的綁定。
2. 單一繼承（Single Inheritance）與方法繼承：子類別自動繼承父類別的方法；未被子類別覆寫（Override）的方法，執行時會沿著方法解析順序（Method Resolution Order, MRO）往父類別尋找。
3. 方法覆寫（Method Overriding）：子類別重新定義與父類別同名的方法，以實現專屬的行為邏輯。
4. 實例屬性的獨立性：透過 self 綁定的實例屬性分別儲存於個別物件的命名空間（__dict__）中，修改特定物件的屬性絕不影響其他物件。
5. 容器結構存取：Python 字典（Dictionary）作為物件參照（Reference）的容器，透過鍵值（Key）取出物件後呼叫其屬性與方法。

---

解題方法

本題為追蹤程式執行流程題，切入點為依序分析類別架構，並針對程式中三個 print 敘述進行逐步推導：

一、類別階層與架構分析

1. Shape 類別（基礎父類別）

• 建構子 __init__(self, x, y)：設定屬性 self.x = x、self.y = y、self.description = "unknown"。
• 方法 area(self)：回傳 $self.x \times self.y$。
• 方法 perimeter(self)：回傳 $2 \times self.x + 2 \times self.y$。
• 方法 describe(self, text)：修改屬性 self.description = text。

2. Square 類別（繼承自 Shape）

• 覆寫建構子 __init__(self, x)：設定 self.x = x、self.y = x（未呼叫父類別建構子）。
• 繼承 Shape 的 area、perimeter 與 describe。

3. DoubleSquare 類別（繼承自 Square，間接繼承 Shape）

• 覆寫建構子 __init__(self, y)：設定 self.x = 2 * y、self.y = y。
• 覆寫方法 perimeter(self)：回傳 $2 \times self.x + 3 \times self.y$。
• 繼承 Shape 的 area 與 describe。

---

二、程式逐行執行與輸出推導

1. 第一段：計算 rectangle.perimeter

• 執行 rectangle = Shape(100, 45)： 呼叫 Shape.__init__，建立 Shape 實例，其屬性為 $x = 100$、$y = 45$。
• 呼叫 rectangle.perimeter： 使用 Shape 定義的周長公式： $2 \times self.x + 2 \times self.y = 2 \times 100 + 2 \times 45 = 200 + 90 = 290$
• 輸出第 1 行結果為：290。