112 高普考普通考試 資訊處理 程式設計概要 考古題詳解
第 一 題25 分
根據以下 C 程式碼，回答下列問題：
#include <stdio.h>
void g(int *x, int *y) { *x = *y - 1; *y = *y - 2; printf("*x = %d, *y = %d\n", *x, *y); }
void f(int *z, int *w) { int n = 13; g(w, &n); printf("*z = %d, *w = %d, n = %d\n", *z, *w, n); }
int main() { int i = 21; int j = 5; int n = 137; f(&i, &j); printf("print 1: i = %d, j = %d, n = %d\n", i, j, n); g(&n, &n); printf("print 2: i = %d, j = %d, n = %d\n", i, j, n); return 0; }
（一）請說明程式碼第 8 行至第 12 行中，每一行之運算子符號 及 操作所代表的意義。
（二）請問該程式碼執行後輸出的結果為何？
登入後即可作答並保存紀錄。
核心觀念
本題考 C 語言的指標、取址運算子 &、間接取值運算子 *，以及函式呼叫時傳入指標所造成的變數變化。
&變數：取得該變數的記憶體位址。指標：儲存記憶體位址的變數。*指標：透過指標存取該位址上的變數值；用在指派左側時，會修改該變數。
呼叫函式時，C 語言仍是傳值；傳入指標時，複製的是位址，因此函式可透過該位址修改呼叫端的變數。
（一）運算子 * 與 & 的意義
題目第 8 行至第 12 行對應 f 函式中的程式：
int n = 13;
g(w, &n);
printf("*z = %d, *w = %d, n = %d\n", *z, *w, n);
g(w, &n)中的w是指標變數，內容為呼叫端傳入的位址；直接使用w，表示把這個位址傳給g。&n使用取址運算子，取得f函式區域變數n的位址。printf格式字串中的*z、*w只是輸出的文字，不是運算式。printf引數中的*z、*w使用間接取值運算子，分別讀取z、w所指向的整數值。
（二）輸出結果
**解題方法：**逐次追蹤每個指標指向哪個變數，再依照 g 內的指派順序更新變數。特別注意，若兩個指標指向同一個變數，後一次指派會使用前一次更新後的值。
第一次呼叫 f(&i, &j)
呼叫時 z 指向 i，w 指向 j，而 f 內的區域變數 n 初值為 。
第 二 題25 分
根據以下 C 程式碼，回答下列問題：
#include <stdio.h>
int f(int a, int b) { if (b == 1) return a; else { int value = a + f(a, b - 1); return value; } }
int main() { printf("%d\n", f(5, 3)); printf("%d\n", f(0, 0)); }
（一）請問哪一行是此遞迴程式的中止條件？
（二）請說明第 10 行的輸出，以及其運作邏輯。
（三）請說明第 11 行的輸出，以及其運作邏輯。
（四）請說明函式 的主要功能，包含輸入參數與輸出結果的關係。
登入後即可作答並保存紀錄。
核心觀念
本題考查遞迴函式的中止條件、函式呼叫與回傳值，以及如何由遞迴關係判斷函式功能。
函式 f(a, b) 的定義是：
- 當
b == 1，回傳a。 - 否則，先計算
a + f(a, b - 1)，再回傳結果。
解題方法
從遞迴呼叫的第二個參數逐步追蹤，直到符合中止條件；接著由最內層開始逐層代回計算。
（一）遞迴程式的中止條件
中止條件是第 2 行：
if (b == 1)
當 b 等於 1 時，函式直接執行 return a;，不再呼叫自己。
（二）第 10 行的輸出與運作邏輯
第 10 行執行 f(5, 3)：
f(5, 3) = 5 + f(5, 2)
= 5 + 5 + f(5, 1)
= 5 + 5 + 5
= 15
當 b 降為 1 時，符合中止條件，f(5, 1) 回傳 5。其餘兩層各自再加上 a = 5，因此輸出為：
15
（三）第 11 行的輸出與運作邏輯
第 11 行執行 f(0, 0)。因為 b 不等於 1，程式會持續呼叫 f(0, b - 1)：
f(0, 0) → f(0, -1) → f(0, -2) → ⋯
第 三 題25 分
關於搜尋法程式：
（一）說明循序（Sequential）搜尋法，以及二元（Binary）搜尋法的優缺點。
（二）以下二元搜尋程式碼有部分錯誤。若要修正為正確程式，請說明「最少」需修改程式碼行數、原因與修改方法。
public class BinarySearch { public int faultyBinarySearch(int[] arr, int x) { int l = 0, r = arr.length - 1; int m = (l + r) / 2; while (l <= r) { m = (l + r) / 2; if (arr[m] == x) return m; if (arr[m] > x) l = m + 1; if (arr[m] < x) r = m - 1; } return -1; } }
登入後即可作答並保存紀錄。
核心觀念
本題考查循序搜尋（Sequential Search）與二元搜尋（Binary Search）的比較，以及二元搜尋程式中「比較結果後，應縮小哪一側搜尋範圍」的邏輯。
二元搜尋的前提是資料已依遞增或遞減順序排列。以遞增排列為例，令左、右界限分別為 與 ，每次取中間位置
再比較 與目標值 。若 ，目標只可能在右半部；若 ，目標只可能在左半部。
解題方法
（一）兩種搜尋法的優缺點
| 搜尋法 | 方法與時間複雜度 | 優點 | 缺點 |
|---|---|---|---|
| 循序搜尋 | 從頭至尾逐一比較；最壞情況需比較 次，時間複雜度為 | 不要求資料排序；實作簡單；適用於小型或未排序資料 | 資料量大時搜尋較慢 |
| 二元搜尋 | 每次比較中間元素並排除一半範圍；時間複雜度為 | 對大量資料搜尋效率高 | 資料必須已排序，且通常需能以索引快速存取中間元素；維護排序資料也可能增加成本 |
（二）最少修改行數與修正方式
錯誤在兩個界限更新條件：程式把 時的左界限往右移，把 時的右界限往左移，方向都與二元搜尋的判斷相反。
- 若 ，較大的元素位於中間位置，目標若存在，只會在左半部，因此應令 。
- 若 ，目標若存在，只會在右半部，因此應令 。
第 四 題25 分
請依據以下 Java 程式碼回答下列問題：
import java.util.Scanner;
public class MyJavaCode { public static void main(String[] args) { Scanner in = new Scanner(System.in); int a = in.nextInt(); Animal dog = new Dog(); dog.run(a); dog.run(); } }
class Dog extends Animal { public void run(int units) { System.out.println("Dog's running speed is " + units); }
public void run() {
System.out.println("Dog's default running speed is 20");
}
}
（一）請說明 Java 中 class、abstract class 與 interface 之間的主要差異。
（二）請說明上述程式碼那幾行會產生編譯錯誤，以及錯誤的原因。
（三）不改變原 1－19 行程式碼順序的條件下，請修正問題（二）之編譯問題，使之可以正常執行。修正不包含左右大括號「{}」，新增或修改之指令行數不可以超過 3 行。
登入後即可作答並保存紀錄。
核心觀念
本題考查 Java 的型別宣告、繼承與方法多載。class、abstract class 和 interface 都能定義型別，但在能否直接建立物件、能否包含實作內容，以及類別如何繼承或實作等方面有所不同。
class（一般類別）：可包含欄位、建構子及已實作的方法；具體類別可以直接建立物件。Java 類別只能直接繼承一個父類別。abstract class（抽象類別）：以abstract宣告，不能直接建立物件，可包含抽象方法和已實作的方法，也可有欄位及建構子。子類別必須實作繼承而來的抽象方法，否則子類別也要宣告為抽象類別。interface（介面）：描述一組型別應提供的操作，類別以implements表示實作介面。一個類別可實作多個介面。介面可宣告抽象方法，也可包含default、static等方法；介面中的常數欄位具有public static final性質。
解題方法
先檢視每個型別是否已宣告，再檢查子類別是否完成父類別要求的抽象方法，最後檢查呼叫的方法是否存在於變數的編譯時型別。
（一）三種型別的主要差異
| 比較項目 | class | abstract class | interface |
|---|---|---|---|
| 可否直接建立物件 | 具體類別可以 | 不可以 | 不可以 |
| 方法內容 | 可有已實作的方法 | 可有已實作及抽象方法 | 可有抽象方法，也可有 default、static 等方法 |
| 繼承／實作關係 | 類別只能直接繼承一個類別 | 子類別以 extends 繼承 | 類別以 implements 實作，可實作多個介面 |
| 常見用途 | 建立具體物件 | 提供共用狀態或部分實作，並要求子類別補完方法 | 定義可由不同類別共同遵循的操作規格 |
（二）編譯錯誤及原因
會產生編譯錯誤的宣告是：
class Dog extends Animal {
原因是程式中沒有宣告 Animal 類別或介面，編譯器無法解析 Animal。因此 Dog 的父類別無效，後續 Animal dog = new Dog; 也無法通過編譯，因為 Animal 仍是未定義型別。
題目其餘方法本身並無錯誤：Dog 宣告了 run(int units) 與 run，兩者參數不同，屬於方法多載。但要讓整段程式可編譯，還需在 Dog 的父類別宣告中提供合法的 Animal 型別。