中四资讯及通讯科技练习卷：程式编写与算法基础

某程式使用整数变数 a 及 b，程式中 a 的值为 87，b 的值为 12。

(a) 写出 Python 运算式 a // b、a % b 及 a / b 的结果，其中 a / b 须准确至小数后两位。（3 分）
(b) 计算运算式 4 + 3 * 2 ** 3 – 20 // 6 的值，并说明当中的运算次序。（2 分）
(c) 某同学以 0.1 + 0.2 == 0.3 测试浮点数运算，结果为 False。解释原因。（2 分）

(a) 87 // 12 ＝ 7（取商的整数部分）；87 % 12 ＝ 3（余数，因 12 × 7 ＝ 84）；87 / 12 ＝ 7.25（真除法）。（3 分）
(b) 先计算 2 ** 3 ＝ 8（指数优先），再计算 3 × 8 ＝ 24 及 20 // 6 ＝ 3，最后 4 ＋ 24 － 3 ＝ 25。（2 分）
(c) 0.1 及 0.2 在二进制浮点中不能精确表示，储存值为近似值；两者相加后与 0.3 的储存值相差约 5 × 10^-17，故 == 判定为 False。应改用 abs(a – b) 小于 1e-9 的方式比较。（2 分）

以下为一段 Python 程式码：

total = 0;
i = 1;
while i <= 8:
    total = total + i * i
    i = i + 2

(a) 完成追踪表，写出每次迭代后 i 及 total 的值。（4 分）
(b) 写出程式执行完毕后 total 的值，以及循环体执行的次数。（2 分）
(c) 若把 i = i + 2 改为 i = i + 1，total 的值会变成多少？（1 分）

(a) 追踪表：i ＝ 1，total ＝ 1；i ＝ 3，total ＝ 10；i ＝ 5，total ＝ 35；i ＝ 7，total ＝ 84；之后 i ＝ 9，条件 9 不大于 8 不成立，循环结束。（4 分）
(b) total ＝ 84（1 ＋ 9 ＋ 25 ＋ 49），循环体执行 4 次。（2 分）
(c) 若改为 i ＝ i ＋ 1，会累加 1 至 8 的平方，total ＝ 204。（1 分）

以下程式按分数输出等级：

if score >= 85:
    grade = "A"
elif score >= 70:
    grade = "B"
elif score >= 50:
    grade = "C"
else:
    grade = "F"

(a) 分别写出 score 为 85、84、70 及 49 时的输出。（4 分）
(b) 若把第一个条件改为 score > 85，score 为 85 时的输出会是什么？指出这属于哪一类错误。（2 分）
(c) 说明条件排列次序为何会影响程式结果。（1 分）

(a) score ＝ 85 → A；score ＝ 84 → B；score ＝ 70 → B；score ＝ 49 → F。（4 分）
(b) 条件改为 score 大于 85（不含 85）后，score ＝ 85 不符第一条件，落入第二条件（85 不小于 70）→ 输出 B。程式可执行但结果与规格不符，属逻辑错误（logic error）。（2 分）
(c) elif 由上行下行逐一判断，首个成立的分支即执行并跳离整个结构；若把较宽松的条件（如 score 不小于 50）放在前面，高分数会先被归为 C，后面较严格的等级永远不会被选中。（1 分）

某电话簿已按姓名笔划由小至大排序，共有 2,000 笔记录。程式可用线性搜寻或二分搜寻查找记录。

(a) 写出线性搜寻在最坏情况及平均情况下的比较次数。（2 分）
(b) 写出二分搜寻在最坏情况下的比较次数，并列出计算过程。（2 分）
(c) 二分搜寻对资料有何先决条件？若资料未排序，先排序会带来什么额外成本？（3 分）

(a) 线性搜寻最坏情况需 2000 次比较（目标在最后或不存在）；平均情况约 1000.5 次，即 (n ＋ 1) ÷ 2。（2 分）
(b) 二分搜寻每次把搜寻范围减半，最坏比较次数为 ceil(log₂(n ＋ 1)) ＝ ceil(log₂ 2001) ≈ ceil(10.97) ＝ 11 次。（2 分）
(c) 先决条件是资料必须已排序（且能随机存取）。若资料未排序，须先排序，以合并排序为例约需 O(n log n) 时间，这成本可能超过二分搜寻节省的比较次数；故只查一次时线性搜寻反而较实际。（3 分）

以下程式以冒泡排序把列表由小至大排列：

data = [45, 12, 78, 33, 56, 90]

(a) 写出完成第一趟（first pass）后列表的内容。（4 分）
(b) 若程式不设“已排序即停止”的优化，完成整个排序共需多少次比较？以 n 表示公式。（2 分）
(c) 这个列表最少需要多少趟才完成排序？（1 分）
(d) 若某一趟完全没有交换，代表什么？可如何利用这点提早结束？（1 分）

(a) 第一趟由左至右比较相邻元素并交换：45 与 12 交换；45 与 78 不换；78 与 33 交换；78 与 56 交换；78 与 90 不换。结果为 [12, 45, 33, 56, 78, 90]，最大值 90 已到最后位置。（4 分）
(b) 比较次数为 (n － 1) ＋ (n － 2) ＋ … ＋ 1 ＝ n(n － 1) ÷ 2；n ＝ 6 时为 6 × 5 ÷ 2 ＝ 15 次。（2 分）
(c) 最少 3 趟（每趟固定一个元素到最终位置，最后一趟只剩一个元素无须比较）。（1 分）
(d) 某趟完全没有交换，代表列表已排序；可设 swapped 旗标，该趟结束时若为 False 即 break，最好情况只需 1 趟、n － 1 次比较，时间复杂度由 O(n²) 降至 O(n)。（1 分）

以下函数计算补习班费用，每小时 120 元，单次上限 1,000 元：

def lesson_fee(hours, rate=120, cap=1000):
    amount = hours * rate
    if amount > cap:
        amount = cap
    return amount

(a) 写出 lesson_fee(6)、lesson_fee(10) 及 lesson_fee(8.5) 的回传值。（3 分）
(b) 解释 rate 及 cap 作为预设参数的好处。（2 分）
(c) 若传入 hours 为 -3，函数会回传什么？指出问题并提出修正方法。（3 分）

(a) lesson_fee(6) ＝ 6 × 120 ＝ 720；lesson_fee(10) ＝ 1,200，超过上限，回传 1000；lesson_fee(8.5) ＝ 1,020，同样被上限截为 1000。（3 分）
(b) 预设参数让常用值（120 元、1,000 元上限）不必每次传入，呼叫更简洁；需要时仍可覆写（例如 lesson_fee(6, 150)），提高函数重用性而不改函数本体。（2 分）
(c) hours ＝ -3 时回传 -360，属不合理的负数费用。应在函数开头验证输入，例如 if hours 小于 0: raise ValueError(“hours must be non-negative”)，或回传 0／空值并由呼叫者处理。（3 分）

某班 7 位学生的测验分数如下：

marks = [72, 58, 91, 64, 85, 47, 79]

(a) 写出总分、最高分及最低分。（3 分）
(b) 计算平均分，准确至小数后一位。（2 分）
(c) 写出高于平均分的学生人数。（2 分）
(d) 写出可计算高于平均分人数的程式片段。（1 分）

(a) 总分 ＝ 72 ＋ 58 ＋ 91 ＋ 64 ＋ 85 ＋ 47 ＋ 79 ＝ 496；最高分 91；最低分 47。（3 分）
(b) 平均 ＝ 496 ÷ 7 ＝ 70.857…，即 70.9。（2 分）
(c) 高于 70.857 的分数为 72、91、85、79，共 4 人。（2 分）
(d) avg = sum(marks) / len(marks)；count = 0；for m in marks:； if m 大于 avg: count += 1；（或 sum(1 for m in marks if m 大于 avg)）。（1 分）

某程式中字串变数 s 的值为 “Programming”。

(a) 写出 len(s)、s[0:4] 及 s[-3:] 的值。（3 分）
(b) 写出 s.count(“m”) 及 s.count(“g”) 的值。（2 分）
(c) 写出 s[::-1] 的结果。（1 分）
(d) 说明如何用切片判断 s 是否回文（palindrome），并指出 s 是否回文。（2 分）

(a) len(s) ＝ 11；s[0:4] ＝ Prog（索引 0 至 3）；s[-3:] ＝ ing（最后三个字元）。（3 分）
(b) s.count(“m”) ＝ 2；s.count(“g”) ＝ 2。（注意大小写有别，”Programming” 的首字母 P 为大写，但 m 及 g 均为小写，故两者都数得到。）（2 分）
(c) s[::-1] ＝ gnimmargorP。（1 分）
(d) 判断 s == s[::-1] 即可；把字串反转后与原字串比较，相等即回文。本例 gnimmargorP 与 Programming 不同，故 不是回文。（2 分）

以下程式计算嵌套循环的执行次数：

total = 0
for i in range(n):
    for j in range(i):
        total = total + 1

(a) 当 n = 120 时，total 的值是多少？（3 分）
(b) 以 n 表示 total 的通式，并说明推导过程。（2 分）
(c) 写出这段程式的时间复杂度；另有一段 for k in range(3 * n) 的单层循环，其时间复杂度为何？（3 分）
(d) 当 n 由 120 增至 1,200，执行次数约增加多少倍？（2 分）

(a) 外层 i 由 0 至 119，内层执行 i 次，总次数 ＝ 0 ＋ 1 ＋ … ＋ 119 ＝ 119 × 120 ÷ 2 ＝ 7140。（3 分）
(b) 通式为 n(n － 1) ÷ 2，即等差数列 0 ＋ 1 ＋ … ＋ (n － 1) 之和。（2 分）
(c) 嵌套循环的时间复杂度为 O(n²)；单层 for k in range(3 * n) 执行 3n 次，为 O(n)（常数因子不计）。（3 分）
(d) n ＝ 1,200 时次数 ＝ 1,199 × 1,200 ÷ 2 ＝ 719400，比值 ＝ 719400 ÷ 7140 ≈ 101 倍，即 n 增大 10 倍，工作量约增大 100 倍。（2 分）

以下程式目的为计算 2 至 20（包括 20）所有偶数之和，但程式有错：

total = 0
i = 1
while i <= 20:
    if i % 2 == 1:
        total = total + i
    i = i + 1
print(total)

(a) 写出程式实际输出的值。（2 分）
(b) 写出正确答案应为多少。（2 分）
(c) 指出错误所在并写出修正后的一行。（3 分）
(d) 若删去 i = i + 1 一行，程式会出现什么问题？（3 分）

(a) 程式把 i % 2 == 1（奇数）的数累加，即 1 ＋ 3 ＋ … ＋ 19 ＝ 100。（2 分）
(b) 2 至 20 的偶数和 ＝ 2 ＋ 4 ＋ … ＋ 20 ＝ 110。（2 分）
(c) 错误在条件：应为 if i % 2 == 0:（余 0 才是偶数）。原式 i % 2 == 1 只挑奇数。修正后一行：if i % 2 == 0:。（3 分）
(d) 删去 i = i + 1 后 i 永远为 1，条件一直成立，形成无限循环（infinite loop），程式不会结束并可能耗尽内存或挂起；此为执行时出现的逻辑错误，编译器不会指出。（3 分）

以下列表已按数值由小至大排序，程式以二分搜寻查找 key：

ids = [12, 18, 23, 27, 31, 38, 44, 50, 56, 62, 69, 75, 81, 88, 94]

(a) 当 key 为 75 时，逐步写出 low、high、mid 及比较结果，并写出最终索引。（5 分）
(b) 上述查找共比较了多少次？（2 分）
(c) 当 key 为 70（不存在于列表中）时，写出最后一次迭代的 low 及 high，并解释循环如何结束。（3 分）

(a) low ＝ 0，high ＝ 14，mid ＝ 7 → ids[7] ＝ 50，50 小于 75，low ＝ 8；low ＝ 8，high ＝ 14，mid ＝ 11 → ids[11] ＝ 75，相等，找到，索引 11。（5 分）
(b) 共比较 2 次。（2 分）
(c) key ＝ 70：mid ＝ 7（50 小于 70）→ low ＝ 8；mid ＝ 11（75 大于 70）→ high ＝ 10；mid ＝ 9（62 小于 70）→ low ＝ 10；mid ＝ 10（69 小于 70）→ low ＝ 11；此时 low ＝ 11 大于 high ＝ 10，while 条件不成立，循环结束并回报找不到，共 4 次比较。（3 分）

某程式的输入为 8 位学生的分数：

scores = [48, 67, 55, 90, 73, 38, 81, 59]

(a) 计算平均分，准确至小数后一位。（3 分）
(b) 计算及格（50 分或以上）的人数。（2 分）
(c) 计算高于平均分的人数。（2 分）
(d) 写出完整程式，输出平均分（一位小数）、及格人数及高于平均分人数。（3 分）

(a) 总分 ＝ 48 ＋ 67 ＋ 55 ＋ 90 ＋ 73 ＋ 38 ＋ 81 ＋ 59 ＝ 511；平均 ＝ 511 ÷ 8 ＝ 63.875 → 63.9。（3 分）
(b) 50 分或以上者为 67、55、90、73、81、59，共 6 人。（2 分）
(c) 高于 63.875 者为 67、90、73、81，共 4 人。（2 分）
(d) 程式：scores ＝ […]；avg ＝ sum(scores) / len(scores)；passes ＝ 0；above ＝ 0；for s in scores:； if s 不小于 50: passes += 1； if s 大于 avg: above += 1；print(round(avg, 1), passes, above)，输出 63.9 6 4。（3 分）