109 地方特考三等 資訊處理 程式設計 考古題詳解

109 年・地方特考・三等・資訊處理
試題代碼 程式設計

第 一 題30 分

請使用 Java、C#、C++ 或 Python 等物件導向程式語言，建立矩陣相關運算的系統。系統一共有三個類別，分別為抽象類別 Matrix、實作類別 MatrixMultiply 及 MatrixAdd，其中：

  1. 抽象類別 Matrix 中所有的變數與方法皆為 protected，主要包含：

    • matrix1、matrix2、resultM 三個實數值二維矩陣資料。
    • 一個抽象的 checkDimension() 方法，用來檢查 matrix1 與 matrix2 是否適合進行所指定的運算。
    • 一個抽象的 matrixOperation() 方法，用來對 matrix1 與 matrix2 進行運算。
    • 一個 setMatrix() 方法，可以將所傳入的兩個矩陣複製到 matrix1、matrix2。
    • 改寫物件的 toString() 方法，可以顯示 matrix1、matrix2 及 resultM 的內容。

  2. 類別 MatrixMultiply 繼承類別 Matrix：

    • 實作 Matrix 中的兩個抽象方法，分別實現父類別內 matrix1 及 matrix2 進行乘法時的維度檢查及乘法運算。進行運算前會主動呼叫 checkDimension()，確定是否可以進行相關運算；如無法運算，resultM 會被設定為 null 並回傳，否則進行運算，結果存於父類別的 resultM 並回傳。
    • 提供一個空建構子，以及一個可以接受兩個二維矩陣的建構子。建構子中呼叫父類別的 setMatrix() 方法，設定 matrix1 及 matrix2；空建構子會將 matrix1 及 matrix2 設為 null。

  3. 類別 MatrixAdd 同 MatrixMultiply，僅在實作抽象方法時，以矩陣加法為對象，進行維度檢查及運算。

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題考查物件導向程式設計中的抽象類別、繼承、多型與封裝，並結合矩陣加法、乘法的維度條件。

  • Matrix 是抽象父類別，集中管理兩個輸入矩陣 matrix1、matrix2 與結果矩陣 resultM。
  • checkDimension 與 matrixOperation 的處理方式會因運算種類不同而異，因此在父類別中宣告為抽象方法，由 MatrixMultiply 和 MatrixAdd 各自實作。
  • setMatrix 負責複製輸入矩陣，避免只保存外部傳入矩陣的參考。
  • 子類別執行運算前先檢查維度；不符合條件時將 resultM 設為 null。

矩陣加法要求兩矩陣列數與行數皆相同。若 AA、BB 均為 m×nm \times n 矩陣，則：

(A+B)ij=Aij+Bij(A+B)_{ij}=A_{ij}+B_{ij}

矩陣乘法要求左矩陣的欄數等於右矩陣的列數。若 AA 為 m×nm \times n、BB 為 n×pn \times p，則結果 C=ABC=AB 為 m×pm \times p，且：

Cij=∑k=0n−1AikBkjC_{ij}=\sum_{k=0}^{n-1}A_{ik}B_{kj}

解題方法

以下以 Java 實作。double[][] 表示實數值二維矩陣；程式假設輸入矩陣不是 null、每列長度一致，且兩個矩陣均非空。setMatrix 逐元素複製矩陣內容。

🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

第 二 題20 分

請使用 Java、C、C++、C# 或 Python，分別使用 iterative 與 recursive 方法，撰寫二元搜尋法，搜尋已排序的整數值數列。

註：假設數列資料是以具有 array 性質的 list 來存放。

  • 模組程式應能接受欲搜尋的資料及已排序數列的相關資料。
  • 模組程式應回傳所欲搜尋的資料是否在數列資料中。

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

二元搜尋法適用於已排序的數列。每次檢查目前搜尋範圍的中間元素：

  • 若中間值等於目標值，搜尋成功。
  • 若目標值較小，只搜尋左半部。
  • 若目標值較大，只搜尋右半部。

每次比較後，搜尋範圍約縮小為原來的一半，因此時間複雜度為 O(log⁡n)O(\log n)；數列未排序時，不能直接使用此方法。

本題要求分別以 iterative（迭代）及 recursive（遞迴）寫出模組，並回傳目標值是否存在。以下以 Python 為例，索引採零起算，使用左閉右開區間 [low,high)[low, high)。

解題方法

令數列長度為 nn，初始搜尋範圍為 [0,n)[0,n)。每次以

mid=⌊low+high2⌋mid = \left\lfloor \frac{low+high}{2} \right\rfloor

取得中間索引。若 target<a[mid]target < a[mid]，令 high=midhigh=mid；若 target>a[mid]target > a[mid]，令 low=mid+1low=mid+1。當 low=highlow=high 時，搜尋範圍為空，代表找不到目標值。

Iterative：迴圈版本

def binary_search_iterative(a, target):
 low = 0
 high = len(a) # 搜尋區間為 [low, high)

 while low < high:
 mid = (low + high) // 2

 if a[mid] == target:
 return True
 elif target < a[mid]:
 high = mid
 else:
 low = mid + 1

 return False

迴圈每次都縮小搜尋區間，因此最後會找到目標值或使區間變空。此版本時間複雜度為 O(log⁡n)O(\log n)，額外空間複雜度為 O(1)O(1)。

Recursive：遞迴版本

🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

第 三 題25 分

請使用 Java、C、C++、C# 或 Python 撰寫相關程式模組，使用 stack（先進後出的線性資料結構）來完成 preorder 的深度優先（Depth First Search）樹狀圖追蹤（traversal）。

註：

  • 假設樹狀圖的節點資料可以為任意型別。
  • 假設樹狀圖的節點結構內含三個全域變數：資料、父節點、所有子節點串接的 linked list。

模組程式需求如下：

  • 模組程式應能接受樹狀圖的樹根。
  • 模組程式應以字串數列方式，回傳樹狀圖追蹤的結果，以空白、逗號或換行符號區隔資料字串。
  • 樹狀圖中的節點需另以獨立的 class 定義節點資料、相關的建構子（Constructor）與存取子（Accessor/Mutator）。

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題考查以 stack（堆疊）實作樹的 preorder 深度優先走訪，以及節點類別的設計。

  • Preorder（前序走訪）：先拜訪目前節點，再依序走訪各子樹。
  • Stack（堆疊）：後進先出（LIFO）。因此，若希望子節點依原本順序被拜訪，必須將子節點反向推入堆疊。
  • 題目允許節點資料為任意型別，因此節點資料可用泛型表示，例如 Java 的 TreeNode<T>。
  • 節點包含資料、父節點及子節點 linked list。下列實作以 List<TreeNode<T>> 表示子節點串列，並提供建構子、存取子與修改子節點的方法。

解題方法

先將根節點推入堆疊。每次從堆疊取出一個節點，將其資料加入結果，再把該節點的子節點由右至左推入堆疊。由於堆疊是後進先出，最左側子節點會最先被取出，因而維持子節點原有順序。

例如根節點 A 的子節點依序為 B、C、D，將 D、C、B 推入堆疊後，下一個取出的便是 B，走訪結果會依序進入 B 子樹、C 子樹、D 子樹。

Java 參考程式

🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

第 四 題25 分

請使用 Java、C、C++、C# 或 Python 撰寫相關模組程式，可以找出某一整數的所有 generator(s)。

digit-sum：正整數 NN 的 digit-sum 定義為「該正整數本身與構成該整數的個別數字總和」。例如，245245 的 digit-sum 為 256256，因為 245+2+4+5=256245+2+4+5=256。

generator：正整數 MM 是正整數 NN 的 digit-sum 時，則 NN 為 MM 的 generator。例如：

  • 245245 是 256256 的 generator。
  • 19791979 是 20052005 的 generator，因為 1979+1+9+7+9=20051979+1+9+7+9=2005。
  • 198198 及 207207 皆是 216216 的 generator，而 198198 是 216216 最小的 generator。

模組程式需求如下：

  • 模組程式應能接受使用者由標準輸入裝置所輸入的資料。
  • 模組程式中應控制使用者輸入資料的正確性與合法性。如輸入資料非正整數，程式應顯示輸入資料不正確的訊息，然後結束程式。
  • 輸入資料無誤，執行程式後，應顯示該輸入資料的所有 generator(s)。

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題考查整數運算、迴圈搜尋與輸入資料驗證。

正整數 MM 的 digit-sum 定義為：

digitSum⁡(M)=M+各位數字之和\operatorname{digitSum}(M)=M+\text{各位數字之和}

若 digitSum⁡(M)=N\operatorname{digitSum}(M)=N，則 MM 是 NN 的 generator。題目要求找出輸入正整數 NN 的所有 generator。

解題方法

依序檢查小於 NN 的正整數 MM，計算 MM 加上各位數字總和；若結果等於 NN，就輸出 MM。因為各位數字總和非負，所以 generator 不可能大於或等於 NN，搜尋範圍只需從 11 到 N−1N-1。

例如輸入 216216：

  • 198198 的各位數字和為 1+9+8=181+9+8=18，且 198+18=216198+18=216。
  • 207207 的各位數字和為 2+0+7=92+0+7=9，且 207+9=216207+9=216。

因此 216216 的 generators 為 198198、207207。

以下以 Python 撰寫。程式先驗證輸入是否為正整數，再逐一搜尋並輸出所有符合條件的數字；若沒有 generator，則明確顯示無解。

🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

其他考古題

資訊處理《程式設計》其他年度

111110