📝 一、单项选择题（共 15 题，每题 2 分，共 30 分）
单选题，每题只有一个正确答案。覆盖计算机基础、数学、C++ 语法、算法与数据结构。
cout << (10 << 2); 输出（ ）。（共 15 题，每题 2 分，本模块满分 30 分）
📖 阅读程序 1 —— 素数判断与统计求和
- 01#include <iostream>
- 02using namespace std;
- 03
- 04bool isPrime(int n) {
- 05if (n <= 1) {
- 06return false;
- 07}
- 08for (int i = 2; i * i <= n; i++) {
- 09if (n % i == 0) {
- 10return false;
- 11}
- 12}
- 13return true;
- 14}
- 15
- 16int countPrimes(int n) {
- 17int count = 0;
- 18for (int i = 2; i <= n; i++) {
- 19if (isPrime(i)) {
- 20count++;
- 21}
- 22}
- 23return count;
- 24}
- 25
- 26int sumPrimes(int n) {
- 27int sum = 0;
- 28for (int i = 2; i <= n; i++) {
- 29if (isPrime(i)) {
- 30sum += i;
- 31}
- 32}
- 33return sum;
- 34}
- 35
- 36int main() {
- 37int x;
- 38cin >> x;
- 39cout << countPrimes(x) << " " << sumPrimes(x) << endl;
- 40return 0;
- 41}
10
4 17
🪜 算法思路 + 模拟样例（x=10，期望输出「4 17」）
2 ✓素数 3 ✓素数 4=2×2 ✗ 5 ✓素数 6=2×3 ✗ 7 ✓素数 8=2×4 ✗ 9=3×3 ✗ 10=2×5 ✗
素数个数 = 4（2,3,5,7），素数之和 = 2+3+5+7 = 17
📌 程序主旨
这是一个素数工具集，包含三个函数：
① isPrime(n)：判断 n 是不是素数（质数）。思路：从 2 试除到 √n，如果有任何因子，就不是素数。
② countPrimes(n)：统计 2 ~ n 中有多少个素数。
③ sumPrimes(n)：计算 2 ~ n 中所有素数的和。
主函数读取 x，然后输出「素数个数」和「素数之和」。
📝 判断题。考察：会数 10 以内的素数。
10 以内的素数：2, 3, 5, 7，共 4 个，个数 = 4 ✓
它们的和：2 + 3 + 5 + 7 = 17 ✓
✅ 答案：正确（√）
输入 10 时，输出就是 "4 17"，与题目描述完全一致。
📝 判断题。考察：判断素数的「试除上限」变了会不会影响结果。
把 i*i <= n 改成 i <= n/2，试除范围扩大了，但只要发现有因子就 return false。
所以判断结果不会变，只是慢了一些。
求 1~20 的素数：2, 3, 5, 7, 11, 13, 17, 19，共 8 个，不是 6。
❌ 答案：错误（×）
改完条件后，countPrimes(20) 仍然是 8，不是 6。
📝 判断题。读代码即可。
观察 28~32 行：从 i = 2 开始遍历到 n，遇到素数就累加。
描述完全正确。
✅ 答案：正确（√）
代码逻辑明确就是求 2~n 中素数的和，描述准确。
📝 单选。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
✅ 答案：B. 328
直接枚举 50 以内的素数相加，结果就是 328。
for(int i=2;i*i<=n;i++) 改为 for(int i=2;i<=n;i++)，输入"10"时，程序的输出（ ）
中等
📝 单选。考察：循环条件的细微差别。
原条件 i*i <= n：i 从 2 试到 √n。
新条件 i <= n：i 从 2 一直试到 n 本身。当 i = n 时，n % n == 0，函数会 return false。
注意：n 本身可以是素数（比如 n=7 时 7%7==0，会被错判为合数！），但 isPrime 是被调用的，参数是 2~n 中的 i。
对于 i 本身：isPrime(i) 中当 i 是素数时，循环会跑到 i*i > i（变成 i <= i 即所有 i 都会被试除到 i 本身，n%i==0 必然成立）→ return false。
所以所有数都会被判定为非素数，countPrimes=0，sumPrimes=0。
✅ 答案：A
原条件优化了循环，但改成 i<=n 后会让 isPrime 总是返回 false（因为每个 i 自己就会被 i 整除），从而无法正确计算。
i*i <= n 或 i <= sqrt(n) 就行。如果写成 i <= n，连自己都被整除了，必错！
📖 阅读程序 2 —— 最小花费爬楼梯（动态规划）
- 01#include <iostream>
- 02#include <vector>
- 03using namespace std;
- 04
- 05int compute(vector<int>& cost) {
- 06int n = cost.size();
- 07vector<int> dp(n + 1, 0);
- 08dp[1] = cost[0];
- 09for (int i = 2; i <= n; i++) {
- 10dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i - 1];
- 11}
- 12return min(dp[n], dp[n - 1]);
- 13}
- 14
- 15int main() {
- 16int n;
- 17cin >> n;
- 18vector<int> cost(n);
- 19for (int i = 0; i < n; i++) {
- 20cin >> cost[i];
- 21}
- 22cout << compute(cost) << endl;
- 23return 0;
- 24}
3 10 15 20
15
🪜 DP 推导 + 模拟样例（cost={10,15,20}，期望输出 15）
答案 = min(dp[3], dp[2]) = min(30, 15) = 15（从第 0 级直接跨 2 步到第 2 级只花 15）
📌 程序主旨
这是经典的「爬楼梯」动态规划：
有 n 级台阶，每级台阶有一个花费 cost[i]，从第 0 级或第 1 级起步，每次可以爬 1 级或 2 级，目标是爬到顶部（第 n 级之后）。
状态转移方程：dp[i] = min(dp[i-1], dp[i-2]) + cost[i-1]，其中 dp[i] 表示爬到第 i 阶的最小花费。
最后返回 min(dp[n], dp[n-1])，因为可以站在第 n-1 级或第 n 级结束。
📝 判断题。手算一下 DP。
n = 3，cost = [10, 15, 20]，dp 大小为 4：
• dp[1] = cost[0] = 10
• dp[2] = min(dp[1], dp[0]) + cost[1] = min(10, 0) + 15 = 15
• dp[3] = min(dp[2], dp[1]) + cost[2] = min(15, 10) + 20 = 30
最终返回 min(dp[3], dp[2]) = min(30, 15) = 15
✅ 答案：正确（√）
路线：起步→第 1 级（花费 10）→ 跨 2 级到顶部（花费 15）= 25？不对，cost[1]=15 是在第 1 级的花费。
标准路径：0 → 2（花费 15）= 15，所以正确答案是 15 ✓
📝 判断题。考察：编译错误 vs 运行错误。
C++ 编译时无法知道数组下标是否越界（因为下标是变量），所以 dp[i-3] 这种语法本身完全合法，能编译通过。
但运行时如果 i = 2，访问 dp[-1] 会越界——这是运行时错误，不是编译错误。
❌ 答案：错误（×）
不会产生编译错误，只会在运行时下标越界报运行时错误。
📝 判断题。考察：理解 DP 的本质。
DP 输出的是从起点到终点的最优路径花费总和，不是单纯找最小元素。
反例：cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1}，最小元素是 1，但程序输出是 6（见第 24 题）。
❌ 答案：错误（×）
DP 算的是「最少花费路径的总花费」，不是最小元素。最小元素永远只是 cost 里的某一个数，与 DP 无关。
📝 单选。需要列出 DP 表。
n = 10，注意 dp 大小是 n+1 = 11，下标 1~10。
cost[i-1] 对应：dp[1]+cost[0]，dp[2]+cost[1]，...，dp[10]+cost[9]。
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| cost | 1 | 100 | 1 | 1 | 1 | 100 | 1 | 1 | 100 | 1 |
| dp | 1 | 100 | 2 | 3 | 3 | 103 | 4 | 5 | 105 | 6 |
输出 = min(dp[10], dp[9]) = min(6, 105) = 6
✅ 答案：A. 6
最优策略：每次都跨过 100 的那一级，即在 1→3→5（花费 1+1+1=3）→7→9→10（最终花费 6）。
📝 单选（4 分题）。手算 DP。
n = 7：
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| cost | 10 | 15 | 30 | 5 | 5 | 10 | 20 |
| dp | 10 | 15 | 45 | 20 | 20 | 30 | 50 |
输出 = min(dp[7], dp[6]) = min(50, 30) = 30
✅ 答案：B. 30
最优路径：起步→1（花费10）→2（花费15）→4（花费5）→6（花费10），停在第6级（顶部之前），共 30。或者起步→2（15）→4（5）→6（10）=30。
📝 单选。改动后：
• 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
✅ 答案：A. 10
注意是 dp[i-1] + cost[i-2]，意思是"从 i-1 上来花 i-1 那级的费用"，下标对应有点绕。逐步算下来得到 10。
📖 阅读程序 3 —— 递归函数 customFunction
- 01#include <iostream>
- 02#include <cmath>
- 03using namespace std;
- 04
- 05int customFunction(int a, int b) {
- 06if (b == 0) {
- 07return a;
- 08}
- 09return a + customFunction(a, b - 1);
- 10}
- 11
- 12int main() {
- 13int x, y;
- 14cin >> x >> y;
- 15int result = customFunction(x, y);
- 16cout << pow(result, 2) << endl;
- 17return 0;
- 18}
2 3
64
🪜 递归展开 + 模拟样例（输入「2 3」，期望输出 64）
result = 2×4 = 8，最终输出 8² = 64
验证：输入「5 4」→ cf=5×5=25，输出 625；输入「3 3」→ cf=3×4=12，输出 144
📌 程序主旨
这个递归函数的本质是把 a 连加 (b+1) 次：
customFunction(a, b) = a + a + ... + a（共 b+1 个 a）= a × (b+1)
main 函数读取 x, y，计算 result = customFunction(x, y) = x × (y+1)，最后输出 result²。
📝 判断题。手算递归。
customFunction(2, 3)：
= 2 + customFunction(2, 2)
= 2 + 2 + customFunction(2, 1)
= 2 + 2 + 2 + customFunction(2, 0)
= 2 + 2 + 2 + 2 = 8
注意：64 是输出（pow(8,2)），不是返回值。
❌ 答案：错误（×）
customFunction(2, 3) = 2 × 4 = 8。64 是 main 函数最终输出（pow(8,2)），不是递归返回值。
📝 判断题。递归终止条件是 b == 0。
如果 b < 0：b-1 还是负数，越来越小，永远到不了 0。
直到栈溢出（stackoverflow）报错终止，但表现上就是"无限递归"。
✅ 答案：正确（√）
b 为负数时没有终止条件，会无限递归直到栈溢出。
📝 判断题。b 越大递归层数越多，调用次数 = b+1，运行时间越长。
✅ 答案：正确（√）
递归深度 = b+1，b 越大递归越深，运行时间线性增长。
📝 单选。customFunction(5, 4) = 5 × (4+1) = 25
✅ 答案：B. 25
5 个 5 相加 = 5×5 = 25。
📝 单选。customFunction(3, 3) = 3 × 4 = 12，输出 pow(12, 2) = 144
✅ 答案：C. 144
3×4=12，12²=144。
return a + customFunction(a-1, b-1); 并输入"3 3"，则程序的最终输出为（ ）
较难
📝 单选（4 分题）。改成每次 a 和 b 都 -1。
设 f(a, b)：
• 终止条件 b == 0 时返回 a
• 否则返回 a + f(a-1, b-1)
f(3, 3) = 3 + f(2, 2) = 3 + 2 + f(1, 1) = 3 + 2 + 1 + f(0, 0) = 6 + 0 = 6
输出 = 6² = 36
✅ 答案：D. 36
其实就是计算 3+2+1+0 = 6，再平方得 36。
🛠️ 完善程序 1 —— 判断平方数
📌 题目
给定正整数 n，判断 n 是否为完全平方数（即存在正整数 x 使得 x² = n）。
- 01#include <iostream>
- 02#include <cmath>
- 03using namespace std;
- 04
- 05bool isSquare(int num) {
- 06int i = ①;
- 07int bound = ②;
- 08for (; i <= bound; ++i) {
- 09if (③) {
- 10return ④;
- 11}
- 12}
- 13return ⑤;
- 14}
- 15
- 16int main() {
- 17int n;
- 18cin >> n;
- 19if (isSquare(n)) {
- 20cout << n << " is a square number" << endl;
- 21} else {
- 22cout << n << " is not a square number" << endl;
- 23}
- 24return 0;
- 25}
16
16 is a square number
🪜 补全思路 + 模拟样例（n=16 是平方数；n=20 不是）
n=20：i=1..4，1,4,9,16 都 ≠ 20 ✗ → 输出「20 is not a square number」
📝 填循环变量 i 的初值。
题意：找正整数 x，使 x² = n。最小的正整数是 1，所以 i 从 1 开始枚举。
✅ 答案：A. 1
从 1 开始枚举（n=1 时 1²=1 也是完全平方数，不能漏）。
📝 填循环上限 bound。
如果存在 i² = num，那么 i 最多到 √num，向下取整就是 ⌊√num⌋。
用 C++ 写法：(int)floor(sqrt(num))。
✅ 答案：B. (int)floor(sqrt(num))
sqrt 返回 double，floor 向下取整，(int) 转型为整型。注意 (int) 写在 floor 外面才能保证正确。
(int)sqrt(num)（C++ 默认截断小数），效果相同。
⚠️ 但
sqrt(num) 有精度问题，平方大的数（如 n=10¹⁸）时可能错，不能用于生产代码。
📝 填 if 的判断条件。
题意：判断 i² 是否等于 num。
A、C 是赋值（一个 =），不符合 if 条件；B 是 num == 2*i（两倍），错误；D 才是 num == i*i（平方）。
✅ 答案：D. num == i*i
注意 = 是赋值（返回值），== 才是相等比较。
📝 填 return 的内容。已经找到 i² = num，函数应当返回 true。
C 是直接的 true；A 是 num = 2*i 也是个赋值表达式，赋值结果 2*i 是非零整数，隐式转 bool 仍为 true，效果等价。
官方最终答案：A 或 C 均可得分。
✅ 答案：A 或 C（官方双选）
语义上选 C 最清晰；语法技巧上 A 利用赋值返回值也是 true。考试时按官方标准给分。
return num = 2*i; 是合法的，赋值表达式有返回值（赋值后的值），非零整数 → bool 真。
但这种写法实际工程中不要用，可读性差。
📝 填 for 循环跑完没找到时的返回值。
说明 1 ~ ⌊√num⌋ 中没有 i 满足 i² = num，num 不是完全平方数，返回 false。
✅ 答案：D. false
循环结束都没匹配上，说明不是完全平方数，返回 false。
bool isSquare(int num) {
int i = 1;
int bound = (int)floor(sqrt(num));
for (; i <= bound; ++i) {
if (num == i * i) {
return true;
}
}
return false;
}
🛠️ 完善程序 2 —— 汉诺塔问题
📌 题目
三根柱子 A、B、C。A 柱上有 n 个圆盘从小到大叠放，要把它们全部搬到 C 柱。每次只能移动一个盘子，且大盘必须在小盘下面。问移动方案。
这是经典的递归分治：要把 n 个盘子从 src 移到 tgt：
- 把上面 n-1 个盘子从 src 借助 tgt 挪到 tmp
- 把最下面那个大盘从 src 移到 tgt
- 把 n-1 个盘子从 tmp 借助 src 挪到 tgt
- 01#include <iostream>
- 02#include <vector>
- 03using namespace std;
- 04
- 05void move(char src, char tgt) {
- 06cout << "从柱子" << src << "挪到柱子" << tgt << endl;
- 07}
- 08
- 09void dfs(int i, char src, char tmp, char tgt) {
- 10if (i == ①) {
- 11move(②);
- 12return;
- 13}
- 14dfs(i - 1, ③);
- 15move(src, tgt);
- 16dfs(⑤, ④);
- 17}
- 18
- 19int main() {
- 20int n;
- 21cin >> n;
- 22dfs(n, 'A', 'B', 'C');
- 23return 0;
- 24}
3
从柱子A挪到柱子C 从柱子A挪到柱子B 从柱子C挪到柱子B 从柱子A挪到柱子C 从柱子B挪到柱子A 从柱子B挪到柱子C 从柱子A挪到柱子C
🪜 汉诺塔递归结构 + 模拟样例（n=3，共 7 步）
A→C，A→B，C→B，A→C，B→A，B→C，A→C
📝 填递归终止条件。当 i == 1 时只剩一个盘子，直接移动即可。
✅ 答案：B. 1
剩 1 个盘子就是最简单的情形，直接 move 后返回。
📝 填 move 的参数。i==1 时把唯一盘子从 src 直接搬到 tgt。
✅ 答案：B. src, tgt
从源柱子 src 搬到目标柱子 tgt。
📝 填第一次递归的实参（把上 n-1 个盘子从 src 挪到 tmp，tgt 作辅助）。
对应形参 (src, tmp, tgt)：起点=src，辅助=tgt，目标=tmp。
✅ 答案：B. src, tgt, tmp
原参数顺序是 (src, tmp, tgt)，要把 n-1 个盘子从 src → tmp（用 tgt 作中转），所以填 src, tgt, tmp。
这次：起点 src → 辅助 tgt → 目标 tmp。
📝 填第二次递归的实参（把 n-1 个盘子从 tmp 挪到 tgt，src 作辅助）。
对应形参 (src, tmp, tgt)：起点=tmp，辅助=src，目标=tgt。
✅ 答案：B. tmp, src, tgt
起点=tmp（暂存的 n-1 个盘子所在柱），辅助=src（原起点变辅助），目标=tgt。
📝 填第二次递归的第一个参数（盘子数）。
第二次递归处理的是 n-1 个盘子，所以填 i-1。
✅ 答案：C. i - 1
每次递归都减少 1 个盘子（最大盘已经搬走），剩下 n-1 个递归处理。
void dfs(int i, char src, char tmp, char tgt) {
if (i == 1) {
move(src, tgt);
return;
}
dfs(i - 1, src, tgt, tmp); // 上 n-1 个：src → tmp
move(src, tgt); // 最大盘：src → tgt
dfs(i - 1, tmp, src, tgt); // 下 n-1 个：tmp → tgt
}
📚 汉诺塔移动次数
n 个盘子最少需要 2ⁿ - 1 步。比如 n=3 时需要 7 步。
验证：n=2 时 dfs(2,'A','B','C') 会输出：
A→B、A→C、B→C（共 3 步 = 2²-1）
这是一个时间复杂度 O(2ⁿ)、空间复杂度 O(n) 的算法。
💡 题型分布与备考建议
📊 CSP-J 2024 考点分析
| 题型 | 题号 | 核心考点 |
|---|---|---|
| 阅读1 | 16-20 | 素数判断的试除上界、循环条件细节 |
| 阅读2 | 21-26 | 动态规划爬楼梯、DP 状态转移跟踪 |
| 阅读3 | 27-32 | 递归函数的手工展开、边界条件 |
| 完善1 | 33-37 | 完全平方数判定（试除 + sqrt 上界） |
| 完善2 | 38-42 | 汉诺塔递归分治、柱子角色转换 |
- 阅读程序：拿到题先在草稿上手动跟踪小样例，把代码「跑一遍」。
- 动态规划：2024 年 DP 题变难了，要熟练爬楼梯、打家劫舍等经典模型。
- 递归：一定要敢动手写出展开过程，别只盯着代码看。
- 完善程序：先把整个算法想清楚，再填每个空。注意读代码的「上下文语义」。
- 小心边界：n=0、n=1 这种小输入常常是判断题的反例素材。