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 分。