CSP-J 2025 选择题与阅读程序训练

答案版
考试时间：7月9日下午
题型：单项选择题 / 阅读程序题
题量：33题
满分：100分
用途：课堂讲评 / LearnDash 嵌入
一、单项选择题
每题只有一个正确选项。单项选择题每题2分，阅读程序题按答案版标注计分，点击按钮显示答案和简短解析。
1. 一个32位无符号整数可以表示的最大值，最接近下列哪个选项？
A. 4 * 10^9
B. 3 * 10^10
C. 2 * 10^9
D. 2 * 10^10
答案：A。32位无符号整数最大值是 2^32 - 1 = 4294967295，约为 4.29 * 10^9，最接近 A。
2. 在C++中，执行 int x = 255; cout << (x & (x - 1)); 后，输出的结果是？
A. 255
B. 254
C. 128
D. 0
答案：B。255 的二进制末尾全是 1，255 & 254 = 254。
3. 函数 calc(n) 的定义如下，则 calc(5) 的返回值是多少？
calc 函数
cpp
1int calc(int n) {
2 if (n <= 1) return 1;
3 if (n % 2 == 0) return calc(n / 2) + 1;
4 else return calc(n - 1) + calc(n - 2);
5}
A. 5
B. 6
C. 7
D. 8
答案：B。先看递归出口：calc(0)=1，calc(1)=1。因为 2 是偶数，calc(2)=calc(1)+1=1+1=2；3 是奇数，calc(3)=calc(2)+calc(1)=2+1=3；4 是偶数，calc(4)=calc(2)+1=2+1=3；5 是奇数，所以 calc(5)=calc(4)+calc(3)=3+3=6。
4. 用5个权值10、12、15、20、25构造哈夫曼树，该树的带权路径长度是多少？
A. 176
B. 186
C. 196
D. 206
答案：B。每次选当前最小的两个权值合并：10+12=22，15+20=35，22+25=47，35+47=82。可以画成下面的哈夫曼树： 
        82
      /    \
    35      47
   /  \    /  \
 15   20  25   22
              /  \
             10  12
叶子结点深度为：15、20、25 的深度都是 2，10、12 的深度都是 3。因此带权路径长度 WPL = 15*2 + 20*2 + 25*2 + 10*3 + 12*3 = 30+40+50+30+36 = 186。也可以用每次合并代价求和：WPL = 22+35+47+82 = 186。
5. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，这个总和等于？
A. 顶点数
B. 边数
C. 顶点数 + 边数
D. 顶点数 * 2
答案：B。有向图中每条边贡献1个出度和1个入度，因此两者总和都等于边数。
6. 从5位男生和4位女生中选出4人组成一个学习小组，要求学习小组中男生和女生都有。有多少种不同的选举方法？
A. 126
B. 121
C. 120
D. 100
答案：C。总选法 C(9,4)=126，减去全男 C(5,4)=5 和全女 C(4,4)=1，得到 120。
7. 假设 a、b、c 都是布尔变量，逻辑表达式 (a && b) || (!c && a) 的值与下列哪个表达式不始终相等？
A. a && (b || !c)
B. (a || !c) && (b || !c) && (a || a)
C. a && (!b || c)
D. !(!a || !b) || (a && !c)
答案：C。原式可化为 a && (b || !c)，C 的条件是 a && (!b || c)，不恒等。
8. 已知 f[0] = 1，f[1] = 1，并且对于所有 n >= 2 有 f[n] = (f[n - 1] + f[n - 2]) % 7，那么 f[2025] 的值是多少？
A. 2
B. 4
C. 5
D. 6
答案：D。先按递推式逐项计算，得到 f[0] 到 f[32]：
前一段后一段
f[0]=1
f[1]=1f[17]=1
f[2]=2f[18]=2
f[3]=3f[19]=3
f[4]=5f[20]=5
f[5]=1f[21]=1
f[6]=6f[22]=6
f[7]=0f[23]=0
f[8]=6f[24]=6
f[9]=6f[25]=6
f[10]=5f[26]=5
f[11]=4f[27]=4
f[12]=2f[28]=2
f[13]=6f[29]=6
f[14]=1f[30]=1
f[15]=0f[31]=0
f[16]=1f[32]=1
表中从 f[1] 到 f[16] 与 f[17] 到 f[32] 逐行相同，说明序列每隔 16 项重复一次，所以周期为 16。2025 ÷ 16 余 9，因此 f[2025]=f[9]=6。
9. 下列关于C++ string 类的说法，正确的是？
A. string 对象的长度在创建后不能改变。
B. 可以使用 + 运算符直接连接一个 string 对象和一个 char 类型的字符。
C. string 的 length() 和 size() 方法返回的值可能不同。
D. string 对象必须以 '\0' 结尾，且这个结尾符计入 length()。
答案：B。C++ string 支持 string 与 char 连接；length() 和 size() 等价，长度也可以改变。
10. 考虑以下C++函数，在 main 函数调用 solve 后，x 和 y 的值分别是？
solve 函数
cpp
1void solve(int &a, int b) {
2 a = a + b;
3 b = a - b;
4 a = a - b;
5}
6
7int main() {
8 int x = 5, y = 10;
9 solve(x, y);
10}
A. 5，10
B. 10，5
C. 10，10
D. 5，5
答案：C。a 是 x 的引用，b 是 y 的副本；函数内把 x 改成 10，但 y 仍为 10。
11. 一个8 * 8的棋盘，左上角坐标为 (1,1)，右下角为 (8,8)。一个机器人从 (1,1) 出发，每次只能向右或向下走一格。要到达 (4,5)，有多少种不同的路径？
A. 20
B. 35
C. 56
D. 70
答案：B。表中每个数字表示：从起点 (1,1) 走到该位置的不同路径条数。起点记为 1，第一行和第一列都只有 1 种走法，其余位置等于“上方数字 + 左方数字”。
1111
1234
13610
141020
151535
从 (1,1) 到 (4,5) 需要向右 3 步、向下 4 步，共 7 步。也就是从 7 步中选出 3 步向右，所以路径数为 C(7,3)=35。
12. 某同学用冒泡排序对数组 {6,1,5,2,4} 进行升序排序，请问需要进行多少次元素交换？
A. 5
B. 6
C. 7
D. 8
答案：B。冒泡排序升序交换次数等于逆序对数量，共6个。
13. 十进制数 720 和八进制数 270 的和用十六进制表示是多少？
A. 38816
B. 3DE16
C. 28816
D. 99016
答案：A。方法一：2708=18410，720+184=904，90410=38816。方法二：转成二进制相加，72010=10110100002，2708=101110002。 
  1011010000
+ 0010111000
------------
  1110001000
再从右往左每 4 位一组：11100010002=0011 1000 10002=38816。
14. 一棵包含1000个结点的完全二叉树，其叶子结点的数量是多少？
A. 499
B. 512
C. 500
D. 501
答案：C。完全二叉树中叶子结点数为 ceil(n/2)，n=1000 时为500。
15. 给定一个初始为空的整数栈 S 和一个空的队列 P。按顺序处理 7，5，8，3，1，4，2：奇数入栈，偶数且栈非空则弹出栈顶加入 P。处理完后，队列 P 的内容是什么？
A. 5，1，3
B. 7，5，3
C. 3，1，5
D. 5，1，3，7
答案：A。7、5入栈，遇8弹出5；3、1入栈，遇4弹出1，遇2弹出3，所以 P 为 5，1，3。
二、阅读程序题
阅读下面的程序代码，回答16~21题。
gcd 与三元组计数程序
cpp
1#include <algorithm>
2#include <cstdio>
3#include <cstring>
4inline int gcd(int a, int b) {
5 if (b == 0)
6 return a;
7 return gcd(b, a % b);
8}
9int main() {
10 int n;
11 scanf("%d", &n);
12 int ans = 0;
13 for (int i = 1; i <= n; ++i) {
14 for (int j = i + 1; j <= n; ++j) {
15 for (int k = j + 1; k <= n; ++k) {
16 if (gcd(i, j) == 1 && gcd(j, k) == 1 && gcd(i, k) == 1) {
17 ++ans;
18 }
19 }
20 }
21 }
22 printf("%d\n", ans);
23 return 0;
24}
16. 当输入为2时，程序并不会执行第16行的判断语句。
A. TRUE
B. FALSE
答案：A。n=2 时不存在满足 i<j<k 的三元组，最内层循环不会进入，因此第16行不会执行。
17. 将第16行中的 && gcd(i, k) == 1 删去不会影响程序运行结果。
A. TRUE
B. FALSE
答案：B。例如 2、3、4 中 gcd(2,3)=1 且 gcd(3,4)=1，但 gcd(2,4) 不等于1，删去条件会改变计数。
18. 当输入的 n >= 3 的时候，程序总是输出一个正整数。
A. TRUE
B. FALSE
答案：A。只要 n>=3，三元组 1、2、3 一定存在。它们两两互质是因为 gcd(1,2)=1，gcd(1,3)=1，gcd(2,3)=1，所以这个三元组会被计入答案，ans 至少为1。
19. 将第7行的 gcd(b, a % b) 改为 gcd(a, a % b) 后，程序可能出现的问题是？
A. 输出的答案大于原答案。
B. 输出的答案小于原答案。
C. 程序有可能陷入死循环。
D. 可能发生整型溢出问题。
答案：B。程序中常调用 gcd(较小数, 较大数)，修改后会错误地返回较小数，导致很多本应互质的判断失败，答案会变小。
20. 当输入为8的时候，输出为？
A. 37
B. 42
C. 35
D. 25
答案：D。枚举 1 到 8 中两两互质的三元组，共有25个，具体为：
  1. (1,2,3)，(1,2,5)，(1,2,7)
  2. (1,3,4)，(1,3,5)，(1,3,7)，(1,3,8)
  3. (1,4,5)，(1,4,7)
  4. (1,5,6)，(1,5,7)，(1,5,8)
  5. (1,6,7)，(1,7,8)
  6. (2,3,5)，(2,3,7)，(2,5,7)
  7. (3,4,5)，(3,4,7)，(3,5,7)，(3,5,8)，(3,7,8)
  8. (4,5,7)，(5,6,7)，(5,7,8)
所以输出为 25。
21. 调用 gcd(36, 42) 会返回？
A. 6
B. 252
C. 3
D. 2
答案：A。欧几里得算法计算 36 和 42 的最大公约数，结果为6。
继续阅读下面的程序代码，回答22~27题。
排序去重与区间计数程序
cpp
1#include <algorithm>
2#include <cstdio>
3#include <cstring>
4#define ll long long
5int n, k;
6int a[200007];
7int ans[200007];
8int main() {
9 scanf("%d%d", &n, &k);
10 for (int i = 1; i <= n; ++i) {
11 scanf("%d", &a[i]);
12 }
13 std::sort(a + 1, a + n + 1); // 将 a[1] 到 a[n] 按从小到大排序
14 n = std::unique(a + 1, a + n + 1) - a - 1; // 将不重复值移到前面，并把 n 改成有效个数
15 for (int i = 1, j = 0; i <= n; ++i) {
16 for (; j < i && a[i] - a[j + 1] > k; ++j)
17 ;
18 ans[i] = ans[j] + 1;
19 }
20 printf("%d\n", ans[n]);
21 return 0;
22}

程序功能：把输入的若干正整数先排序、逻辑去重，然后按数值范围分组，求最少需要分成多少组，使得每组内最大值和最小值的差不超过 k。

  • 第 13 行先把数组从小到大排序。
  • 第 14 行调用 unique 做逻辑去重：它把不重复的值移到数组前面，并返回新末尾位置；代码再把 n 改成前面这段有效数据的个数，后面的旧内容不会再使用。
  • 第 15~18 行用双指针计算答案：考虑前 i 个不同的数，最后一组以 a[i] 结尾。
  • j + 1 是最后一组的第一个数，需要满足 a[i] - a[j + 1] <= k；如果差值太大，就把 j 向右移动。
  • ans[i] = ans[j] + 1 表示前 j 个数已经分好组，j + 1 到 i 作为新的一组。

例如 k=2，逻辑去重后的有效数据为 1 2 3 7 8，可以分成 1 2 3 和 7 8 两组，所以答案是 2。

22. 当输入为 3 1 3 2 1 时，输出结果为2。
A. TRUE
B. FALSE
答案：A。排序去重后为 1、2、3，k=1，前两个数一组，3 单独一组，输出2。
23. 假设输入的 n 为正整数，输出的答案一定小于等于 n，大于等于1。
A. TRUE
B. FALSE
答案：A。去重后仍至少有1个数，每次 ans[i]=ans[j]+1 且 j<i，因此最终答案在 1 到 n 之间。
24. 将第14行的 n = std::unique(a + 1, a + n + 1) - a - 1; 删去后，有可能出现与原本代码不同的输出结果。
A. TRUE
B. FALSE
答案：B。重复值不会改变按数值区间划分所需的组数，删去去重语句不改变最终输出。
25. 假设输入的 a 数组和 k 均为正整数，执行第18行代码时，一定满足的条件不包括？
A. j≤i
B. a[i]−a[j]>k
C. j≤n
D. a[j]<a[i]
答案：B。若 j=0 且 a[i]≤k，则 a[i]-a[j] 不一定大于 k；其余条件在正整数和排序去重后成立。
26. 当输入的 n=100，k=2，a={1,2,...,100} 时，输出为？
A. 34
B. 100
C. 50
D. 33
答案：A。每组最多覆盖连续的3个数，例如 1、2、3；因此需要 ceil(100/3)=34 组。
27. 假设输入的 a 数组和 k 均为正整数，但 a 数组不一定有序，若误删去第13行的 std::sort(a + 1, a + n + 1);，程序有可能出现的问题有？
A. 输出的答案比原本答案更大
B. 输出的答案比原本答案更小
C. 出现死循环行为
D. 以上均可能发生
答案：B。例如 n=2、k=1、a 为 3、1，原程序输出2；删去排序后会输出1。循环变量 j 单调增加，不会死循环。
继续阅读下面的程序代码，回答28~33题。
最长公共子序列程序
cpp
1#include <algorithm>
2#include <cstdio>
3#include <cstring>
4#define ll long long
5int f[5007][5007];
6int a[5007], b[5007];
7int n;
8int main() {
9 scanf("%d", &n);
10 for (int i = 1; i <= n; ++i) {
11 scanf("%d", &a[i]);
12 }
13 for (int i = 1; i <= n; ++i) {
14 scanf("%d", &b[i]);
15 }
16 for (int i = 1; i <= n; ++i) {
17 for (int j = 1; j <= n; ++j) {
18 f[i][j] = std::max(f[i][j], std::max(f[i - 1][j], f[i][j - 1]));
19 if (a[i] == b[j]) {
20 f[i][j] = std::max(f[i][j], f[i - 1][j - 1] + 1);
21 }
22 }
23 }
24 printf("%d\n", f[n][n]);
25 return 0;
26}

程序功能：读入两个长度都为 n 的整数序列 a 和 b，用动态规划求它们的最长公共子序列长度，最后输出 f[n][n]。

  • f[i][j] 表示：只看 a[1..i] 和 b[1..j] 这两个前缀时，最长公共子序列的长度。
  • 第 18 行从上方和左方继承最优值：不选 a[i] 或不选 b[j]，所以取 f[i - 1][j] 和 f[i][j - 1] 的较大值。
  • 第 19~20 行处理当前位置匹配的情况：如果 a[i] == b[j]，就可以在两个更短前缀的答案 f[i - 1][j - 1] 后面接上这个公共元素，因此候选值为 f[i - 1][j - 1] + 1。
  • 双层循环把所有 i,j 的状态都算出来，最终 f[n][n] 就是两个完整序列的最长公共子序列长度。

例如序列 1 2 3 4 和 1 3 2 2 的最长公共子序列长度是 2，可以取 1,3，也可以取 1,2。

28. 当输入 4 1 2 3 4 1 3 2 2 时，输出为2。
A. TRUE
B. FALSE
答案：A。两个序列的最长公共子序列长度为2，例如 1、3 或 1、2。
29. 当程序运行完毕后，对于所有的 1 <= i, j <= n，都一定有 f[i][j] <= f[n][n]。
A. TRUE
B. FALSE
答案：A。f[i][j] 表示两个前缀的最长公共子序列长度，前缀扩展后答案不会变小。
30. 将第18行的状态继承语句删去后，并不影响程序运行结果。
A. TRUE
B. FALSE
答案：B。第18行负责从上方和左方继承最优值，删去后无法正确处理不在当前位置匹配的情况。
31. 输出的答案满足的性质有？
A. 小于等于 n
B. 大于等于 0
C. 不一定大于等于 1
D. 以上均是
答案：D。LCS 长度不会超过 n，至少为0；若两个序列没有公共元素，则答案为0。
32. 如果在第16行的循环前加上排序两个数组的语句，则答案会？
A. 变大或不变
B. 变小或不变
C. 一定变大
D. 不变
答案：A。两个数组排序后，LCS 等于按值可匹配的公共元素数量，不会小于原序列受顺序限制的 LCS。
33. 如果输入的 a={1,2,...,n}，且 b 数组中数字均为1~n中的正整数，则上述代码等价于下面哪个问题？
A. 求 b 数组去重后的长度
B. 求 b 数组的最长上升子序列
C. 求 b 数组的长度
D. 求 b 数组的最大值
答案：B。与 1,2,...,n 做 LCS，等价于在 b 中找一个按数值递增的最长子序列。