IGCSE 電腦科學 0478 Paper 2 模擬卷｜10 題 100 分｜1 小時 45 分

一位老師用以下虛擬碼演算法處理 1 至 6 的整數。

SET total = 0
SET n = 1
WHILE n <= 6
  IF n MOD 2 = 0 THEN
    total = total + n * n
  ELSE
    total = total + 2 * n
  ENDIF
  n = n + 1
ENDWHILE
OUTPUT total

(a) 完成追蹤表（trace table），列出每輪結束時的 n 及 total。
(b) 寫出程式結束時 total 的值、迴圈執行次數及 n 的最終值。
(c) 若條件改為 n < 6，total 會變成多少？解釋原因。

評分要點：
(a) 每行 1 分，共 6 行：n=1 total=2；n=2 total=6；n=3 total=12；n=4 total=28；n=5 total=38；n=6 total=74。
(b) total = 74（1 分）；迴圈執行 6 次（1 分）；n 最終值 = 7（1 分）。
(c) 條件改為 n < 6 後迴圈只執行 5 次，最後一輪 n=6 的偶數分支被跳過，該輪加上 6 × 6 = 36，故 total = 74 − 36 = 38（2 分，算式及原因各 1 分）。
注意：考生只寫答案而無追蹤過程，最多得一半分。

防盜系統的警報輸出 X 由三個感應器 A、B、C 決定：X = (A AND NOT B) OR (B AND C)。

(a) 完成 8 行真值表。
(b) 寫出 X = 1 的行數。
(c) 證明 X 亦可寫成 (A OR B) AND (NOT B OR C)，並以其中一行說明。

評分要點：
(a) 真值表 8 行（每行 0.5 分，共 4 分），X 依次為 0、0、0、1、1、1、0、1。
(b) X = 1 共 4 行（2 分）。
(c) 化簡：A·B̄ ＋ B·C ＝ (A ＋ B)(B̄ ＋ C)（2 分）；逐行代入驗證（2 分）。例：A=0、B=1、C=1 時原式 = (0 AND 0) OR (1 AND 1) = 1，化簡式 = (0 OR 1) AND (0 OR 1) = 1，兩者相同。
考生若只寫化簡式而無驗證，最多 3 分。

一個已排序陣列有 1,000 個元素，使用二分搜尋法（binary search）；另一個未排序陣列有 2,000 個元素，使用線性搜尋法（linear search）。假設每秒可比較 10,000 次。

(a) 寫出線性搜尋在最壞及平均情況下的比較次數。
(b) 寫出二分搜尋在最壞情況下的最多比較次數，並以 2 的冪解釋。
(c) 計算兩者在最壞情況下的執行時間（毫秒），並比較。

評分要點：
(a) 最壞 2,000 次、平均 1,000 次（各 1 分，共 2 分）。
(b) 最多 10 次（2 分）：因為 2^9 = 512 < 1,001 ≤ 2^10 = 1,024，每比較一次搜尋範圍減半，最多 10 次（解釋 2 分）。
(c) 線性：2,000 ÷ 10,000 = 0.2 秒 = 200 毫秒（2 分）；二分：10 ÷ 10,000 = 0.001 秒 = 1 毫秒（2 分）；相差 200 倍，二分搜尋在大量資料時明顯較快，但前提是資料已排序（2 分）。
任何只寫「二分搜尋較快」而無數字的答案不給分。

一個順序檔（sequential file）有 2,400 筆記錄，每筆 48 位元組；磁碟區塊大小為 4,096 位元組。

(a) 每個區塊可容納多少筆完整記錄？
(b) 整個檔案需要多少個區塊？
(c) 每個區塊剩餘多少位元組？整檔案的內部碎片共多少位元組？
(d) 若要直接讀取第 2,000 筆記錄，應讀取第幾個區塊？

評分要點：
(a) 4,096 ÷ 48 = 85.33，取整數 85 筆（2 分，須顯示除法）。
(b) 2,400 ÷ 85 = 28.24，向上取整 29 個區塊（3 分）。
(c) 每區塊剩餘 4,096 − 85 × 48 = 4,096 − 4,080 = 16 位元組（2 分）；全檔 29 × 16 = 464 位元組（2 分）。
(d) (2,000 − 1) ÷ 85 = 23.51，即第 24 個區塊（1 分）。說明：第 23 塊止於第 1,955 筆，第 24 塊由第 1,956 至 2,040 筆。
若考生把 85.33 當作 85.33 筆記錄，須扣 1 分，因為記錄不可分割。

以下 8 個數字以冒泡排序法（bubble sort）由小至大排序：34, 7, 61, 19, 85, 3, 42, 28。每一趟由左至右比較相鄰兩個元素，較大者向右交換。

(a) 寫出第一趟完成後的序列。
(b) 第一趟共進行多少次比較及多少次交換？
(c) 最壞情況下（n = 8）總比較次數是多少？
(d) 若某一趟完全沒有交換，代表什麼？對演算法的效率有何影響？

評分要點：
(a) 7, 34, 19, 61, 3, 42, 28, 85（3 分，錯一個位置扣 1 分）。
(b) 比較 7 次（2 分）、交換 5 次（2 分）。
(c) 最壞情況總比較次數 = 8 × 7 ÷ 2 = 28 次（2 分）。
(d) 沒有交換表示序列已排序，可提早結束（early exit），最好情況由 O(n²) 降為 O(n)，只需 7 次比較（1 分＋1 分）。
考生若把第一趟寫成由右至左，須按方向重新評分，方向錯誤整題 0 分。

一個 11 位數字碼採用加權模 11 檢查碼：前 10 位由左至右乘以權重 10 至 1，總和除以 11 得餘數 r，檢查碼 = (11 − r) MOD 11（餘數 10 以 X 表示）。

(a) 計算數字 0 3 5 4 2 1 6 9 8 7 的加權總和、餘數及檢查碼。
(b) 寫出完整 11 位碼。
(c) 說明此檢查碼能否偵測兩個相鄰數字對調，並以對調 3 與 5 為例計算。

評分要點：
(a) 加權總和 = 0×10 ＋ 3×9 ＋ 5×8 ＋ 4×7 ＋ 2×6 ＋ 1×5 ＋ 6×4 ＋ 9×3 ＋ 8×2 ＋ 7×1 = 0 ＋ 27 ＋ 40 ＋ 28 ＋ 12 ＋ 5 ＋ 24 ＋ 27 ＋ 16 ＋ 7 = 186（3 分）；186 ÷ 11 = 16 餘 10（2 分）；檢查碼 = (11 − 10) MOD 11 = 1（2 分）。
(b) 03542169871（1 分）。
(c) 對調後總和 = 0 ＋ 5×9 ＋ 3×8 ＋ … = 188，差額 2，2 MOD 11 ≠ 0，故檢查碼改變，可偵測（2 分）。一般情況相鄰權重相差 1，只要兩個數字不同，差額就不可能是 11 的倍數，因此必能偵測。

一班 10 位學生的分數存於陣列：marks = [58, 72, 45, 91, 66, 83, 54, 77, 69, 88]。

(a) 寫出計算平均分的虛擬碼，須包括總和、計數及輸出。
(b) 計算平均分（取一位小數）。
(c) 寫出虛擬碼片段，輸出高於平均分的學生人數。
(d) 說明為何計算平均分時不可只用整數除法。

評分要點：
(a) 正確初始化 total = 0、count = 0；迴圈累加每項；平均 = total / count（3 分，缺初始化或除零保護各扣 1 分）。
(b) 總和 703，703 ÷ 10 = 70.3（3 分）。
(c) 迴圈內 IF marks[i] > average THEN count_above = count_above ＋ 1（2 分），答案為 5 人：72、91、83、77、88（2 分）。
(d) 整數除法 703 ÷ 10 得 70，捨去 0.3，會令 69 與 70 的判斷出錯；應用浮點數（real）保留小數（1 分＋1 分）。

資料庫有一個資料表 students，欄位為 student_id、name、class、score，共有 6 筆記錄：S01 5A 78；S02 5A 92；S03 5B 65；S04 5B 88；S05 5A 54；S06 5B 71。

(a) 寫出 SQL 列出 5A 班而成績高於 60 的學生姓名及成績，按成績由高至低排序。
(b) 寫出求 5B 班平均分的 SQL。
(c) 計算 (a) 的結果有幾行，並列出。
(d) 說明主鍵（primary key）與外鍵（foreign key）的分別。

評分要點：
(a) SELECT name, score FROM students WHERE class = '5A' AND score > 60 ORDER BY score DESC；（4 分：SELECT、WHERE、AND 條件、ORDER BY DESC 各 1 分）。
(b) SELECT AVG(score) FROM students WHERE class = '5B'；（2 分），結果 74.67（1 分）。
(c) 2 行：S02 92、S01 78（2 分）。
(d) 主鍵唯一識別每筆記錄且不可重複或為空；外鍵是另一資料表的主鍵，用來建立關聯並確保參照完整性（1 分＋1 分）。
考生若漏寫 DESC，只給 3 分。

考慮以下遞迴函式：

FUNCTION fact(n)
  IF n <= 1 THEN
    RETURN 1
  ELSE
    RETURN n * fact(n - 1)
  ENDIF
ENDFUNCTION

(a) 寫出 fact(6) 的返回值及各次呼叫的參數。
(b) 計算 fact(6) 時函式被呼叫的總次數。
(c) 說明基本情況（base case）的作用，若缺少會發生什麼事。
(d) 比較遞迴與迭代在記憶體使用上的差別。

評分要點：
(a) 返回值 720（2 分）；呼叫次序 fact(6)、fact(5)、fact(4)、fact(3)、fact(2)、fact(1)（3 分，須由外至內）。
(b) 共 6 次呼叫（2 分）。
(c) 基本情況 n <= 1 時直接返回 1，令遞迴終止（2 分）；若缺少，函式會不斷呼叫 fact(0)、fact(−1)……直至堆疊溢出（stack overflow）（2 分）。
(d) 每次遞迴呼叫都在呼叫堆疊上佔用一個堆疊框（stack frame），深度為 n；迭代只用固定幾個變數，記憶體為 O(1)，遞迴為 O(n)（2 分）。

一個程式把乘客的乘車時間（秒）轉換為「小時、分鐘、秒」。虛擬碼使用整數除法 DIV 及餘數 MOD。

(a) 寫出轉換的虛擬碼，須輸出三個數值。
(b) 完成三個測試數據：3,725 秒、59 秒、7,380 秒。
(c) 說明為何要使用整數除法而非四捨五入。
(d) 指出一個邊界測試值（boundary value）並解釋為何要測它。

評分要點：
(a) hours = seconds DIV 3600；minutes = (seconds MOD 3600) DIV 60；secs = seconds MOD 60；輸出三個值（4 分，每行 1 分，輸出 1 分）。
(b) 3,725 秒 → 1 小時 2 分 5 秒（2 分）；59 秒 → 0 小時 0 分 59 秒（2 分）；7,380 秒 → 2 小時 3 分 0 秒（2 分）。
(c) 時間是整數單位，四捨五入會產生不存在的秒數（例如 59.7 秒變成 60 秒），並令總和不等於原輸入（1 分＋1 分）。
(d) 邊界值如 0 秒（0:0:0）或 3,600 秒（剛好 1 小時，分鐘與秒應為 0）；用以檢查 DIV 與 MOD 在整除時是否正確處理餘數 0（1 分＋1 分）。
考生若把 3,725 秒寫成 1 小時 2 分 5 秒以外的答案，該項 0 分。