高级程序阅读

概念讲解

程序阅读技巧

  1. 变量追踪法： 用表格记录每个变量的值
  2. 递归树法： 画出递归调用树
  3. 模拟法： 一步一步模拟程序执行

常见程序类型

  1. 递归程序
  2. DFS/BFS 程序
  3. STL 容器程序
  4. 动态规划程序

递归程序阅读

示例

1234int f(int n) {
    if (n <= 1) return 1;
    return f(n - 1) + f(n - 2);
}

分析

f(0) = 1
f(1) = 1
f(2) = f(1) + f(0) = 2
f(3) = f(2) + f(1) = 3
f(4) = f(3) + f(2) = 5
f(5) = f(4) + f(3) = 8

DFS 程序阅读

示例

12345678void dfs(int u) {
    visited[u] = true;
    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

分析

  • 标记当前节点为已访问
  • 遍历所有邻居
  • 如果邻居未访问，递归访问

STL 容器程序阅读

示例

1234567stack<int> s;
s.push(1);
s.push(2);
s.push(3);
cout << s.top() << endl;
s.pop();
cout << s.top() << endl;

分析

push(1): stack = [1]
push(2): stack = [1, 2]
push(3): stack = [1, 2, 3]
top(): 输出 3
pop(): stack = [1, 2]
top(): 输出 2

考点分析

初赛考查方式

  1. 程序阅读： 手动模拟程序执行
  2. 选择题： 程序输出
  3. 填空题： 变量值

常见题型

  • 递归程序
  • DFS/BFS 程序
  • STL 容器程序

例题精讲

例题 1：递归程序

题目： 以下程序的输出是什么？

12345int f(int n) {
    if (n == 0) return 0;
    return f(n - 1) + n;
}
cout << f(5);

解答：

f(0) = 0
f(1) = f(0) + 1 = 1
f(2) = f(1) + 2 = 3
f(3) = f(2) + 3 = 6
f(4) = f(3) + 4 = 10
f(5) = f(4) + 5 = 15
输出：15

例题 2：STL 程序

题目： 以下程序的输出是什么？

1234567queue<int> q;
q.push(1);
q.push(2);
q.push(3);
cout << q.front() << endl;
q.pop();
cout << q.front() << endl;

解答：

push(1): queue = [1]
push(2): queue = [1, 2]
push(3): queue = [1, 2, 3]
front(): 输出 1
pop(): queue = [2, 3]
front(): 输出 2

练习题

  1. 模拟递归程序的执行
查看答案

模拟递归程序的方法：

  1. 画递归树：画出所有递归调用
  2. 从下往上计算：先计算叶子节点的返回值
  3. 记录每一步：用表格记录每个变量的值

例如：f(5) = f(4) + 5 = 10 + 5 = 15

  1. 理解 DFS/BFS 程序
查看答案

DFS/BFS 程序的理解：

  • DFS：使用栈或递归，深度优先遍历
  • BFS：使用队列，广度优先遍历

关键点：

  1. 标记已访问节点
  2. 遍历所有邻居
  3. 递归/入队
  1. 阅读 STL 容器程序
查看答案

STL 容器程序的阅读：

  • stack：后进先出（LIFO）
  • queue：先进先出（FIFO）
  • vector：动态数组
  • set：有序集合
  • map：键值对

注意每个容器的操作和特性。

易错点

⚠️ 注意：

  1. 程序阅读要仔细
  2. 递归程序要画递归树
  3. STL 容器要理解特性
  4. 注意边界条件