2024 年 CSP-J（入门级）第一轮认证于 2024 年 9 月 21 日举行。继上一篇单项选择题解析后，本文为您带来第二部分：阅读程序题（共 3 大题，计 40 分）的逐题源码分析、逻辑推理与深度全解析。

阅读程序题主要考查对 C++ 语法细节、基础算法逻辑（素数判定、动态规划、递归思想）及代码执行轨迹跟踪能力。

📌 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

📍 第一题：素数判定与统计求和算法

💻 源码展示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int countPrimes(int n) {
    int count = 0;
    for (int i = 2; i <= n; i++) {
        if (isPrime(i)) {
            count++;
        }
    }
    return count;
}

int sumPrimes(int n) {
    int sum = 0;
    for (int i = 2; i <= n; i++) {
        if (isPrime(i)) {
            sum += i;
        }
    }
    return sum;
}

int main() {
    int x;
    cin >> x;
    cout << countPrimes(x) << " " << sumPrimes(x) << endl;
    return 0;
}

💡 程序主旨

本程序包含三个主要函数：

• isPrime(n)：用试除法判断整数 $n$ 是否为素数（试除范围到 $\sqrt{n}$）。
• countPrimes(n)：统计从 $2$ 到 $n$ 之间（包含 $n$）所有素数的个数。
• sumPrimes(n)：计算从 $2$ 到 $n$ 之间（包含 $n$）所有素数数值的总和。

❓ 判断题

1. 当输入为 10 时，程序的第一个输出为 4，第二个输出为 17。（ ）

A. 正确
B. 错误

正确答案： A

深度解析： 当输入 $x = 10$ 时：

• $10$ 以内的素数有：$2, 3, 5, 7$，共有 4 个。因此 countPrimes(10) 返回 4。
• $10$ 以内素数之和为：$2 + 3 + 5 + 7 = \mathbf{17}$。因此 sumPrimes(10) 返回 17。
• 程序主函数输出 4 17，与题干描述完全相符。故本题正确。

2. 若将 isPrime(i) 函数中的条件改为 i<=n/2，输入 20 时，countPrimes(20) 的输出将变为 6。（ ）

A. 正确
B. 错误

正确答案： B

深度解析： 在 isPrime(int n) 函数中，若将循环条件从 i * i <= n 改为 i <= n / 2：

• 对于任何大于 $1$ 的合数 $n$，必然存在小于或等于 $n/2$ 的因数。因此将上限扩大到 $n/2$ 依然能够准确判定任何数的素性（虽然效率有所降低）。
• 当输入 $20$ 时，countPrimes(20) 依然能够正确统计出 $20$ 以内的所有素数：$2, 3, 5, 7, 11, 13, 17, 19$，共 8 个素数，输出依然为 8，而非 6。故本题错误。

3. sumPrimes 函数计算的是从 2 到 $n$ 之间的所有素数之和。（ ）

A. 正确
B. 错误

正确答案： A

深度解析： 观察 sumPrimes(int n) 的实现：循环变量 i 从 2 增加到 n，当 isPrime(i) 为 true 时累加 sum += i，返回值即为 $[2, n]$ 闭区间内所有素数之和。描述完全准确，故本题正确。

❓ 单选题

1. 当输入为 50 时，sumPrimes(50) 的输出为（ ）。

A. 1060
B. 328
C. 381
D. 275

正确答案： B

深度解析： 计算 $50$ 以内的所有素数之和：

• 20 以内的素数：$2, 3, 5, 7, 11, 13, 17, 19$ （和为 $77$）
• 20~30 的素数：$23, 29$ （和为 $52$）
• 30~40 的素数：$31, 37$ （和为 $68$）
• 40~50 的素数：$41, 43, 47$ （和为 $131$）

总和求计算： \(77 + 52 + 68 + 131 = \mathbf{328}\)

故正确答案为 B。

2. 如果将 for (int i = 2; i * i <= n; i++) 改为 for (int i = 2; i <= n; i++)，输入 10 时，程序的输出（ ）。

A. 将不能正确计算 10 以内素数个数及其和
B. 仍然输出 4 和 17
C. 输出 3 和 10
D. 输出结果不变，但运行时间更短

正确答案： A

深度解析： 若将 isPrime(int n) 中的循环条件改为 i <= n：

• 在判断一个数 $n$ 是否为素数时，循环变量 i 会一直递增到等于 $n$。
• 当 i == n 时，必定触发 n % i == 0，函数直接返回 false。
• 这将导致所有数（包括真正的素数如 2, 3, 5 等）都会被误判为合数（返回 false）。
• 输入 $10$ 时，countPrimes(10) 将返回 0，sumPrimes(10) 将返回 0，程序无法正确计算素数个数及和。故正确答案为 A。

📍 第二题：动态规划（爬楼梯/到达顶部的最小花费）

💻 源码展示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
#include <vector>
using namespace std;

int compute(vector<int>& cost) {
    int n = cost.size();
    vector<int> dp(n + 1, 0);
    dp[1] = cost[0];
    for (int i = 2; i <= n; i++) {
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i - 1];
    }
    return min(dp[n], dp[n - 1]);
}

int main() {
    int n;
    cin >> n;
    vector<int> cost(n);
    for (int i = 0; i < n; i++) {
        cin >> cost[i];
    }
    cout << compute(cost) << endl;
    return 0;
}

💡 程序主旨

本题模型来源于经典的动态规划问题——最小花费爬楼梯（Min Cost Climbing Stairs）。

• 数组 cost[i] 表示踏上第 $i$ 阶台阶所需的费用。
• 每次可以跨越 1 个或 2 个台阶。
• dp[i] 表示踏上第 $i$ 阶台阶（1-based 索引，对应 cost[i-1]）所需的累计最小费用。
• 最终目标是到达楼顶（即超过最后一阶），因此返回 min(dp[n], dp[n-1])。

❓ 判断题

1. 当输入的 cost 数组为 {10, 15, 20} 时，程序的输出为 15。（ ）

A. 正确
B. 错误

正确答案： A

深度解析： 逐步追踪 compute 函数：

• n = 3，cost = [10, 15, 20]，初始化 dp[0] = 0, dp[1] = cost[0] = 10。
• $i = 2$：dp[2] = min(dp[1], dp[0]) + cost[1] = min(10, 0) + 15 = 15
• $i = 3$：dp[3] = min(dp[2], dp[1]) + cost[2] = min(15, 10) + 20 = 30
• 返回结果：min(dp[3], dp[2]) = min(30, 15) = 15。

输出确实为 15，故本题正确。

2. 如果将 dp[i-1] 改为 dp[i-3]，程序可能会产生编译错误。（ ）

A. 正确
B. 错误

正确答案： B

深度解析：

• 将 dp[i-1] 改为 dp[i-3] 后，当 $i = 2$ 时，dp[i-3] 即为 dp[-1]。
• 在 C++ 中，std::vector 的 [] 运算符不进行边界检查，下标 -1 属于越界内存访问（Undefined Behavior / 运行期段错误 Segmentation Fault）。
• 这属于运行时错误，编译器在编译阶段无法检测到负下标，不会产生编译错误（Compile Error）。故本题错误。

3. （2 分）程序总是输出 cost 数组中最小的元素。（ ）

A. 正确
B. 错误

正确答案： B

深度解析： 程序求解的是路径上所有选中台阶的花费总和的最小值，而不是找数组元素的最小值。例如，当 cost = [10, 15, 20] 时，输出为 15，而数组中最小的元素是 10。反例明显，故本题错误。

❓ 单选题

1. 当输入的 cost 数组为 {1, 100, 1, 1, 100, 1, 1, 100, 1} 时，程序的输出为（ ）。

A. 6
B. 7
C. 8
D. 9

正确答案： A

深度解析： 数组 cost = [1, 100, 1, 1, 100, 1, 1, 100, 1]，长度 $n = 9$。

填表计算 dp[i]：

最终返回 min(dp[9], dp[8]) = min(6, 104) = 6。故正确答案为 A。

2. （4 分）如果输入的 cost 数组为 {10, 15, 30, 5, 5, 10, 20}，程序的输出为（ ）。

A. 25
B. 30
C. 35
D. 40

正确答案： B

深度解析： 数组 cost = [10, 15, 30, 5, 5, 10, 20]，长度 $n = 7$。

填表计算 dp[i]：

最终返回 min(dp[7], dp[6]) = min(45, 30) = 30。故正确答案为 B。

3. 若将代码中的 min(dp[i-1], dp[i-2]) + cost[i-1] 修改为 dp[i-1] + cost[i-2]，输入 cost 数组为 {5, 10, 15} 时，程序的输出为（ ）。

A. 10
B. 15
C. 20
D. 25

正确答案： A

深度解析： 修改后的状态转移方程为：dp[i] = dp[i-1] + cost[i-2]。 对于 cost = [5, 10, 15]（$n = 3$）：

• dp[0] = 0
• dp[1] = cost[0] = 5
• $i = 2$：dp[2] = dp[1] + cost[0] = 5 + 5 = 10
• $i = 3$：dp[3] = dp[2] + cost[1] = 10 + 10 = 20
• 返回值：min(dp[3], dp[2]) = min(20, 10) = 10。

故正确答案为 A。

📍 第三题：递归函数与数学运算

💻 源码展示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <iostream>
#include <cmath>
using namespace std;

int customFunction(int a, int b) {
    if (b == 0) {
        return a;
    }
    return a + customFunction(a, b - 1);
}

int main() {
    int x, y;
    cin >> x >> y;
    int result = customFunction(x, y);
    cout << pow(result, 2) << endl;
    return 0;
}

💡 程序主旨

• customFunction(a, b) 是一个递归函数： \(customFunction(a, b) = a + a + \dots + a \quad (\text{共 } b+1 \text{ 项}) = a \times (b + 1)\)
• main 函数读取 $x, y$，计算 $result = customFunction(x, y) = x \times (y + 1)$，最后输出 $result^2$。

❓ 判断题

1. 当输入为 2 3 时，customFunction(2, 3) 的返回值为 64。（ ）

A. 正确
B. 错误

正确答案： B

深度解析：

• 注意题干问的是 customFunction(2, 3) 的返回值，而不是主函数的输出！
• customFunction(2, 3) = 2 * (3 + 1) = 8，返回值为 8。
• 主函数输出的是 pow(8, 2) = 64。
• 题干混淆了函数返回值与最终输出，故本题错误。

2. （本题为错题，请同时选择【正确】和【错误】获得对应分数）当 $b$ 为负数时，customFunction(a, b) 会陷入无限递归。（ ）

A. 正确
B. 错误

正确答案： A / B (官方认定本题题目表述存在瑕疵，选择【正确】或【错误】均能获得对应分数)

深度解析：

• 逻辑分析：当 $b < 0$ 时，每次递归 $b$ 变为 $b - 1$（如 $-1, -2, -3 \dots$），永远无法触发终止条件 b == 0，在理论逻辑上确实会陷入无限递归（导致栈溢出 Stack Overflow 异常崩溃）。
• 考试说明：官方将此题判定为错题，双选 A、B 均判对给分。

3. （本题为错题，请同时选择【正确】和【错误】获得对应分数）当 $b$ 的值越大，程序的运行时间越长。（ ）

A. 正确
B. 错误

正确答案： A / B (官方认定本题题目表述存在瑕疵，选择【正确】或【错误】均能获得对应分数)

深度解析：

• 逻辑分析：递归深度与 $b$ 成正比（递归 $b+1$ 次），复杂度为 $O(b)$。理论上 $b$ 越大，时间越长。
• 考试说明：官方将此题判定为错题，双选 A、B 均判对给分。

❓ 单选题

1. 当输入为 5 4 时，customFunction(5, 4) 的返回值为（ ）。

A. 5
B. 25
C. 250
D. 625

正确答案： B

深度解析：

• 再次注意问题问的是 customFunction(5, 4) 的返回值： \(customFunction(5, 4) = 5 \times (4 + 1) = \mathbf{25}\)
• 若问主函数输出则是 $25^2 = 625$（选项 D），但问返回值选 25。故正确答案为 B。

2. 如果输入 x=3 和 y=3，则程序的最终输出为（ ）。

A. 27
B. 81
C. 144
D. 256

正确答案： C

深度解析：

• 计算 result = customFunction(3, 3) = 3 * (3 + 1) = 12。
• 主函数输出 pow(12, 2) = 12^2 = 144。
• 故正确答案为 C。

3. （4 分）若将 customFunction 函数改为 return a + customFunction(a - 1, b - 1);，并输入 3 3，则程序的最终输出为（ ）。

A. 9
B. 16
C. 25
D. 36

正确答案： D

深度解析： 修改后的递归展开：

1
2
3
4
5
6

customFunction(3, 3)
= 3 + customFunction(2, 2)
= 3 + 2 + customFunction(1, 1)
= 3 + 2 + 1 + customFunction(0, 0)
= 3 + 2 + 1 + 0  // 当 b == 0 时，返回第一个参数 a = 0
= 6

主函数最终输出 pow(6, 2) = 6^2 = 36。故正确答案为 D。

[!TIP] 本篇结语 以上为 CSP-J 2024 第一轮认证（初赛）阅读程序题 3 大题的全解析。在本篇中，我们解析了素数判定、动态规划和递归推论等核心题型。 本系列的第三篇将为您带来最后一项重头戏——完善程序题的解析，敬请期待！

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

"luogu-"系列题目可在洛谷题库进行在线评测。

"bcqm-"系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助