111 專技高考高等考試 資訊技師 程式設計 考古題詳解

核心觀念

本題評量物件導向程式設計（OOP）之核心機制與經典抽象資料型別（ADT, Abstract Data Type）的底層實作能力，核心觀念包含：

1. 泛型程式設計（Generic Programming）：透過型態參數化（C++ 的 template <typename T> 或 Java 的 <T>），使堆疊（Stack）可容納任意資料型態，達到高重用性與編譯期型態檢查（Type Safety）。
2. 動態陣列（Dynamic Array）與手動記憶體管理：題目明文限制「不得使用其他物件」（嚴格禁止 std::vector、ArrayList 等標準庫容器）。必須直接操作堆積記憶體（Heap Memory），以原生陣列指標配置與釋放（C++ 的 new[] 與 delete[]），並具備解構子釋放資源以防記憶體洩漏（Memory Leak）。
3. 平攤倍增擴容策略（Amortized Doubling Strategy）：當陣列已滿時，動態配置原容量兩倍（$2 \times \text{capacity}$）之新空間，將舊資料搬移後釋放原陣列。此策略可確保連續 $n$ 次 push 操作的平攤時間複雜度維持在 $O(1)$。
4. 資訊隱藏與封裝（Encapsulation）：資料成員（如陣列指標、當前元素數量、陣列容量）宣告為 private，僅透過 public 成員函式對外提供操作介面。
5. 雙指針原地反轉（In-place Reverse Algorithm）：inverse 函式透過頭尾雙指針相向交換，於 $O(n)$ 時間複雜度與 $O(1)$ 額外空間複雜度內完成陣列順序反轉，不耗費額外記憶體。

解題方法

本題要求實作具有擴容機制的動態陣列堆疊。以下以考點涵蓋最全面（包含解構子、手動記憶體回收與指標操作）的 C++ 作為核心解法，並於文末附上 Java 對照實作：

1. 資料成員設計（封裝）：

• T* data：指向動態配置陣列的泛型指標。
• int capacity：動態陣列當前可容納的最大元素量。
• int top：指向堆疊頂端的下一個可用位置，亦等同於目前儲存的元素個數（length）。

2. 建構子與解構子：

• 建構子配置初始容量（如 $4$ 或 $10$），初始化 top = 0。
• 解構子（Destructor）執行 delete[] data;，避免 Memory Leak。

3. 動態擴容（resize）：

• 當 top == capacity 時觸發。
• 配置新空間 newCapacity = capacity * 2，將元素依序複製至新陣列，呼叫 delete[] data 銷毀舊空間，再將指標轉向新陣列。

4. 基本堆疊操作（push、pop、length、clear）：

• push(T a)：檢查容量，不足則擴容；存入 data[top++] = a。
• pop：檢查是否為空（Underflow）；若為空則拋出例外（std::underflow_error）；否則回傳 data[--top]。
• length：直接回傳 top，時間複雜度 $O(1)$。
• clear：令 top = 0 即可在邏輯上清空堆疊，時間複雜度 $O(1)$。

5. 原地顛倒操作（inverse）：

• 設定雙指針 left = 0、right = top - 1。
• 當 left < right 時，交換兩端元素並將指針向內推進，達成原地（In-place）反轉。

選項分析

本題為「非選擇題（實作申論題）」，無選項分析。針對題目所列 6 項函式規格（a 至 f）之關鍵檢驗點解析如下：

• 子題 a（建構子與解構子）：C++ 必須落實 ~Stack 釋放 new[] 的資源；若選用 Java，因具備垃圾回收機制（Garbage Collection），依題意免寫解構子，但建構子需處理泛型陣列初始化。
• 子題 b（push）：必須包含「滿載判定」與「動態擴容」邏輯，不可固定陣列大小，否則違反題目「記憶體空間不足時動態增加空間」之限制。
• 子題 c（pop）：必須處理「空堆疊防護」，不可直接對負索引取值，必須拋出例外或進行邊界防禦。
• 子題 d（length）：直接回傳內部紀錄之元素個數計數器，維持 $O(1)$ 效能。
• 子題 e（clear）：將堆疊元素索引重設為 0，無須逐一刪除基本元素，效率最高。
• 子題 f（inverse）：必須注意不得宣告其他物件（如 std::queue 或其他輔助容器）來輔助反轉，應直接在動態陣列內部交換。

解題技巧與考場陷阱

1. 切忌使用標準函式庫容器： 考卷嚴禁出現 #include <vector> 或 import java.util.ArrayList。若以此類物件包裝，閱卷委員將認定違反「必須使用動態陣列，不能使用其他物件」之題意，直接大幅扣分。
2. Java 泛型陣列抹除陷阱（Type Erasure）： 若使用 Java 撰寫，不可寫 new T[capacity]（編譯錯誤，因 Java 執行期型態抹除不允許直接實例化泛型陣列）。正確寫法為 (T[]) new Object[capacity]，並加上 @SuppressWarnings("unchecked") 註解。
3. C++ 深拷貝與資源安全（Rule of Three）： 在動態配置記憶體的類別中，為避免淺拷貝（Shallow Copy）引發指標重複釋放（Double Free）造成程式崩潰，考場上應主動將複製建構子與賦值運算子設為私有或禁用（delete），展現專業嚴謹度。
4. 擴容倍率選取： 空間不足時「每次 $+1$ 或 $+c$」為低效寫法（連續插入 $n$ 個元素的時間複雜度會退化至 $O(n^2)$）；務必使用「倍增法（$2 \times \text{capacity}$）」，使平攤時間複雜度達 $O(1)$。

【答案】

完整 C++ 實作版本（推薦，完整涵蓋解構子與底層記憶體釋放）

核心觀念

本題考查前端表單驗證與後端資料庫新增流程：

• HTML 建立員工編號、姓名、年齡、電話、住址及提交按鈕。
• JavaScript 在送出表單前檢查欄位是否填妥，並確認年齡是 $1$ 至 $150$ 的整數；驗證失敗時以 alert 跳出警告。
• PHP 與 MySQLi 接收表單資料、確認員工編號沒有重複，再新增至 PBASIC 資料表。

前端檢查是為了即時提示；PHP 仍須在伺服器端檢查資料，不能只依賴 JavaScript。

解題方法

以下以單一 PHP 檔案處理表單顯示與資料新增。資料欄位依題目指定的順序對應 PNO、NAME、AGE、TEL、ADDR；年齡先在前端檢查，再由 PHP 驗證一次。資料庫查重後才執行新增。

核心觀念

本題考查位元組處理、查找表與反向對應。檔案中的每個位元組都可視為 $0$ 至 $255$ 的整數。加密表必須是一個排列：每個輸入值對應唯一的輸出值，且 $0$ 至 $255$ 都恰好出現一次，才能建立可逆的解密表。

若加密表為 table，則：

• 加密：table[原始值] 得到加密值。
• 解密：inverse[加密值] 得到原始值，其中 inverse[table[i]] = i。

解題方法

先將查找表初始化為 $0$ 至 $255$，再用 Fisher–Yates 洗牌法隨機打亂。此方法每次從尚未固定的位置中選出一個位置交換，因此能保證每個數字只出現一次。

接著以二進位模式讀取指定檔案，逐位元組透過查找表轉換，寫入 .en 檔案；同時建立反向查找表，將其 256 個位元組寫入 .key 檔案。以下程式將 .key 儲存為二進位資料，每個位元組是對應的原始值。

核心觀念

本題分成兩部分：

1. 依原圖所示的像素順序，每個像素以 $Y,I,Q$ 三個連續值儲存，將其轉成 $R,G,B$。
2. 以遞迴執行四方向 flood fill，只沿著符合紅色範圍條件的相鄰像素前進。

由題目給的轉換矩陣反矩陣，可得常用的 YIQ 轉 RGB 公式：

轉換後先四捨五入，再將結果限制在 $0$ 到 $255$。

解題方法

以下以 map[y][3*x]、map[y][3*x+1]、map[y][3*x+2] 分別代表第 y 列、第 x 個像素的 $Y,I,Q$；轉換結果也以相同排列存放 $R,G,B$。也就是每列有 $3N$ 個數值，像素座標 $(x,y)$ 中，x 是像素欄、y 是像素列。

static int clampRound(double value) {
 int v = (int)Math.round(value);
 return Math.max(0, Math.min(255, v));
}

static int[][] YIQ2RGB(float[][] map) {
 int h = map.length;
 int[][] rgb = new int[h][];

 for (int y = 0; y < h; y++) {
 rgb[y] = new int[map[y].length];

 // 每 3 個數值為一個像素的 Y、I、Q
 for (int j = 0; j + 2 < map[y].length; j += 3) {
 double Y = map[y][j];
 double I = map[y][j + 1];
 double Q = map[y][j + 2];

 rgb[y][j] = clampRound(Y + 0.956 * I + 0.621 * Q);
 rgb[y][j + 1] = clampRound(Y - 0.272 * I - 0.647 * Q);
 rgb[y][j + 2] = clampRound(Y - 1.106 * I + 1.703 * Q);
 }
 }
 return rgb;
}

Flood fill 以 m[y][3*x] 作為該像素的 $R$ 值。符合範圍時，將三個色彩通道都改為 $127$，並遞迴檢查上、下、左、右四個鄰點。