CSP-J2024 试题知识点·下

CSP-J 2024 知识点精讲（下篇）

下篇聚焦 2024 年 CSP-J 入门级第一轮阅读程序题（第 16-26 题）。这一部分共涉及两道程序，分值 22 分，重点考查同学们对算法逻辑、程序执行流程以及边界条件的理解能力。

一、阅读程序题知识点总览

题号	对应程序	考查主题	核心知识点
16-20	程序（1）	素数相关	质数判定、枚举优化、循环条件分析
21-26	程序（2）	动态规划	上楼梯最小花费、DP 状态转移、数组越界

二、程序（1）：素数统计

程序代码

#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 是否为素数
`countPrimes(n)`	统计 2~n 中素数个数
`sumPrimes(n)`

第 16 题：输入 10 时的输出

答案：√

2~10 中的素数为：2、3、5、7

素数个数：4
素数之和：2 + 3 + 5 + 7 = 17

程序输出 4 17，判断正确。

第 17 题：修改 isPrime 条件后的输出

答案：×

题目说：将 i * i <= n 改为 i <= n/2，输入 20 时 countPrimes(20) 的输出变为 6。

分析：

修改循环条件只会降低效率，不会改变正确性
20 以内的素数：2、3、5、7、11、13、17、19，共 8 个
所以输出应为 8，不是 6

核心知识点：优化条件不影响算法正确性

i * i <= n 只是提前终止循环，只要 n 有约数，在 sqrt(n) 之前一定能找到。

第 18 题：sumPrimes 函数功能

答案：√

sumPrimes(n) 遍历 2~n，将素数累加，确实计算 2~n 所有素数之和。

第 19 题：输入 50 时 sumPrimes 的输出

答案：B. 328

2~50 的素数：2、3、5、7、11、13、17、19、23、29、31、37、41、43、47

求和：2+3+5+7+11+13+17+19+23+29+31+37+41+43+47 = 328

第 20 题：循环条件修改的影响

答案：A. 将不能正确计算 10 以内素数个数及其和

分析：

将 i * i <= n 改为 i <= n 后，isPrime 会枚举到 i = n。

由于任何数 n % n == 0，所以所有数都会被判定为合数，程序无法正确统计素数。

核心知识点：循环边界的重要性

边界条件错误会直接导致算法结果错误，阅读程序时一定要仔细分析循环终止条件。

三、程序（2）：上楼梯最小花费

程序代码

#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; }

功能说明

这是一个经典的动态规划问题：

有一组台阶，每级台阶有一个花费 cost[i]。每次可以跨 1 级或 2 级，求从地面到达顶部的最小花费。

dp[i] 表示到达第 i 级台阶的最小花费。

状态转移方程：

dp[i] = min(dp[i-1], dp[i-2]) + cost[i-1]

最后返回 min(dp[n], dp[n-1])，因为最后一步可能跨 1 级或 2 级到达顶部。

第 21 题：cost = {10, 15, 20} 的输出

答案：√

最优路径：地面 → 第 2 级 → 顶部

花费：15

所以输出为 15，判断正确。

第 22 题：数组越界与编译错误

答案：×

将 dp[i-1] 改为 dp[i-3]：

不会产生编译错误
：语法上 dp[i-3] 是合法的数组访问
会产生运行错误
：当 i = 2 时，dp[-1] 越界

核心知识点：编译错误 vs 运行错误

编译错误：语法问题，程序无法编译
运行错误：逻辑问题，程序运行时报错或异常

第 23 题：程序是否输出最小元素

答案：×

程序输出的是"从地面到顶部的最小总花费"，不是 cost 数组中的最小元素。

例如 cost = {10, 15, 20}，最小元素是 10，但程序输出 15。

第 24 题：cost = {1,100,1,1,1,100,1,1,100,1} 的输出

答案：A. 6

最优路径：走花费为 1 的台阶，避开 100 的台阶。

走过的台阶：第 1、3、5、7、8、10 级，每个花费 1。

总花费：1 + 1 + 1 + 1 + 1 + 1 = 6

第 25 题：cost = {10,15,30,5,5,10,20} 的输出

答案：B. 30

最优路径：地面 → 第 2 级(15) → 第 4 级(5) → 第 6 级(10) → 顶部

总花费：15 + 5 + 10 = 30

第 26 题：修改状态转移方程后的输出

答案：A. 10

修改后代码变为：

dp[i] = dp[i-1] + cost[i-2];

代入 cost = {5, 10, 15}：

dp[0] = 0
dp[1] = cost[0] = 5
dp[2] = dp[1] + cost[0] = 5 + 5 = 10
dp[3] = dp[2] + cost[1] = 10 + 10 = 20

最终返回 min(dp[3], dp[2]) = min(20, 10) = 10

核心知识点：状态转移方程决定 DP 含义

一个微小的改动就可能改变整个 DP 的含义，阅读程序时要逐行跟踪状态变化。

四、下篇知识点清单

1. 素数算法

素数判定：试除法
试除法优化：枚举到 √n
循环边界对结果的影响
素数个数统计与素数和

2. 动态规划入门

DP 状态定义：dp[i] 表示到达第 i 级台阶的最小花费
状态转移方程：dp[i] = min(dp[i-1], dp[i-2]) + cost[i-1]
边界条件：dp[0] = 0，dp[1] = cost[0]
最终结果：min(dp[n], dp[n-1])

3. 程序阅读技巧

先读函数名和主函数，把握整体功能
再逐行跟踪变量变化
注意数组下标是否越界
区分编译错误和运行错误
循环边界条件改变会产生什么影响

五、2024 年 CSP-J 第一轮整体备考建议

1. 时间分配

选择题（1-15）：建议 20-25 分钟
阅读程序题（16-32）：建议 35-40 分钟
完善程序题（33-42）：建议 25-30 分钟

2. 重点突破方向

计算机基础
：进制转换、存储单位、ASCII 码、操作系统常识
数据结构
：栈、队列、二叉树、图的基础性质
算法思维
：二分、递归、动态规划初步
C++ 语法
：数据类型、循环、数组、函数、递归

3. 刷题建议

近 5 年 CSP-J 初赛真题至少刷 2 遍
每道题不仅要知道答案，还要能说出对应知识点
建立个人错题本，按知识点分类整理

上篇回顾：第 1-15 题知识点精讲已发布，包含整数表示、进制转换、图论、树遍历、排列组合等核心内容。