算法跟踪

CIE A-Level 计算机科学· 40 分钟阅读

1. 跟踪迭代算法★★☆☆☆⏱ 15 min

📘 定义

算法跟踪（干运行）

逐步手动模拟算法执行的过程，在每个阶段记录每个变量的值和产生的所有输出。

📐 例题

跟踪下面计算前4个正偶数和的伪代码，找出最终输出：

sum ← 0
FOR count ← 1 TO 4
    number ← 2 × count
    sum ← sum + number
NEXT count
OUTPUT sum

1
1. 进入循环前，初始化已声明的变量：
2
sum = 0，count和number未赋值
3
1. 第一次循环迭代：count被设为1
4
number = $2 \times 1 = 2$ ，sum = $0 + 2 = 2$
5
1. 第二次循环迭代：count自增到2
6
number = $2 \times 2 = 4$ ，sum = $2 + 4 = 6$
7
1. 第三次循环迭代：count自增到3
8
number = $2 \times 3 = 6$ ，sum = $6 + 6 = 12$
9
1. 第四次循环迭代：count自增到4
10
number = $2 \times 4 = 8$ ，sum = $12 + 8 = 20$
11
1. count自增超过4后循环退出，最终输出为：
12
$20$

Exam tip:

一定要在任何循环或条件块运行前，先在跟踪表中填入变量初始值。正确的初始化几乎总能拿到1分。

2. 跟踪嵌套控制结构★★★☆☆⏱ 20 min

嵌套控制结构（循环内的if语句、循环嵌套）需要格外注意，要清楚你当前处于哪一级执行，哪些变量正在被更新。

📘 定义

嵌套迭代

循环体内部包含另一个循环（内层循环）的循环结构。外层循环的每一次迭代都会完整运行一遍内层循环从开头到结束。

📐 例题

跟踪下面的嵌套伪代码，写出所有产生的输出：

FOR outer ← 2 TO 2
    OUTPUT "2 x: "
    FOR inner ← 1 TO 3
        product ← outer × inner
        OUTPUT product
    NEXT inner
NEXT outer

1
1. 外层循环开始：outer = 2，输出字符串 2 x:
2
1. 第一次内层循环迭代：inner = 1
3
product = $2 \times 1 = 2$ ，输出 2
4
1. 第二次内层循环迭代：inner = 2
5
product = $2 \times 2 = 4$ ，输出 4
6
1. 第三次内层循环迭代：inner = 3
7
product = $2 \times 3 = 6$ ，输出 6
8
1. 内层循环退出，外层循环退出。完整输出为：
9
2 x: 2 4 6

Exam tip:

跟踪嵌套循环时，为外层和内层循环索引分别设列，避免在不同迭代间混淆。

3. 跟踪递归算法★★★★☆⏱ 25 min

递归算法（用更小输入调用自身的函数）需要分别跟踪每一个调用栈帧，才能跟踪返回值，正确识别基线条件。

📘 定义

调用栈帧

调用栈中为每个活跃递归调用单独分配的条目，存储该次调用的输入参数和返回地址。

📐 例题

跟踪下面定义的阶乘函数 $f a c t (n)$ ，输入为 $n = 3$ ，找出最终返回值：

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

1
1. 初始调用： $f a c t (3)$ ， $n = 3 \neq = 0$ 因此需要计算 $3 \times f a c t (2)$
2
1. 新调用： $f a c t (2)$ ， $n = 2 \neq = 0$ 因此需要计算 $2 \times f a c t (1)$
3
1. 新调用： $f a c t (1)$ ， $n = 1 \neq = 0$ 因此需要计算 $1 \times f a c t (0)$
4
1. 新调用： $f a c t (0)$ ，触发基线条件，返回 1
5
1. 回退栈： $f a c t (1)$ 返回 $1 \times 1 = 1$
6
1. 回退栈： $f a c t (2)$ 返回 $2 \times 1 = 2$
7
1. 回退栈： $f a c t (3)$ 返回 $3 \times 2 = 6$
8
最终返回值为：
9
$6$

Exam tip:

一定要清晰画出调用栈，用输入参数值标记每一次调用。阅卷人需要看到你理解执行和回退的顺序。

4. 常见陷阱

错误做法:

只写出每个变量的最终值，不在每一步后更新

原因:

阅卷人70%-80%的分数都给中间步骤，因此哪怕最终输出正确，你也会丢失大部分分数

正确做法:

每次变量值改变时，都在跟踪表中更新，不管变化看起来多么微不足道

错误做法:

FOR循环中的差一错误，提前一个迭代停止

原因:

CIE伪代码中的FOR循环包含起始和结束边界，因此当计数器等于结束值时也必须运行

正确做法:

用（结束值 - 起始值 + 1）计算迭代次数，确认你步骤数正确

错误做法:

嵌套循环中，忘记在外层循环每一次迭代时重置内层循环计数器

原因:

这会导致内层循环执行错误，后续所有步骤的变量值都出错

正确做法:

为外层和内层计数器分别设列，每次外层迭代时显式重置内层计数器

错误做法:

递归中还没到基线条件就计算最终返回值

原因:

递归调用依赖更深层调用的返回值，因此提前计算会导致结果错误

正确做法:

先画出从初始输入到基线条件的所有调用，再向上回退计算返回值

5. 速查表

算法类型	核心操作	考试得分提示
迭代	先初始化变量，每一步都更新	正确初始化得1分
嵌套循环	内外层计数器分开放列	迭代次数 = 结束值 - 起始值 + 1
递归	画栈直到基线条件，再向上回退	每个正确栈帧都得分
任意跟踪	记录所有输出，不只是最终结果	遗漏输出 = 失分

6. 常见问题

跟踪题需要我写出每一个步骤吗？

是的，CIE阅卷人将大部分分数分配给中间步骤，而非仅最终输出。哪怕你的最终答案错误，正确的中间变量值也能让你获得部分分数。

我可以用自己的符号做跟踪吗？

只要你的步骤清晰，记录了每一次变量更新就可以，但评分方案推荐的标准表格格式是避免误判的最安全选择。

真题中的出现

AI 根据考纲规律估算的考点位置,请对照官方真题核实准确性。仅作复习重点参考。

2022 · 2
跟踪迭代排序算法
2023 · 2
跟踪递归阶乘函数
2024 · 2
跟踪嵌套循环伪代码

深入阅读

syllabusCIE 9618 官方大纲查看第9节了解学习目标

下一步

算法跟踪是CIE 9618所有算法问题的基础技能，从排序、搜索到递归问题求解都需要它。掌握逐步跟踪不仅能帮你正确回答专门的跟踪题，还能让你在写开放性问题的原创算法时调试自己的伪代码，而开放性问题占了试卷2的大部分分数。持续的跟踪练习能提升速度，帮你避开考试中那些丢掉轻松得分机会的常见错误。