2025年 CSP-J 第一轮试题解答

一、 单项选择题

1. [2 分] 一个 32 位无符号整数可以表示的最大值

答案：A

解析：32 位无符号整数的取值范围是 $0$ 到 $2^{32} - 1$。

• $2^{10} = 1024 \approx 10^3$
• $2^{30} = (2^{10})^3 \approx (10^3)^3 = 10^9$
• $2^{32} = 2^{30} \times 2^2 \approx 4 \times 10^9$ 因此，最大值 $2^{32}-1$ 最接近 $4 \times 10^9$。

2. [2 分] C++ 位运算 x & (x - 1)

答案：B

解析：x & (x - 1) 是一个经典操作，用于将 x 的二进制表示中最右边的 1 变为 0。

• x = 255 的二进制是 11111111。
• x - 1 = 254 的二进制是 11111110。
• 按位与的结果是 11111110，即十进制的 254。

3. [2 分] 递归函数 calc(5)

答案：B

解析：我们自底向上计算：

• calc(0) = calc(1) = 1
• calc(2) = calc(1) + 1 = 1 + 1 = 2 (偶数)
• calc(3) = calc(2) + calc(1) = 2 + 1 = 3 (奇数)
• calc(4) = calc(2) + 1 = 2 + 1 = 3 (偶数)
• calc(5) = calc(4) + calc(3) = 3 + 3 = 6 (奇数) 所以返回值是 6。

4. [2 分] 哈夫曼树带权路径长度 (WPL)

答案：B

解析：构造哈夫曼树的过程如下：

1. 合并最小的两个：10 和 12 → 新节点 22。剩余：15, 20, 22, 25。
2. 合并 15 和 20 → 新节点 35。剩余：22, 25, 35。
3. 合并 22 和 25 → 新节点 47。剩余：35, 47。
4. 合并 35 和 47 → 根节点 82。 计算 WPL：叶子节点深度乘以其权值再求和。

• 10 和 12 在第 3 层：$(10 + 12) \times 3 = 66$
• 15 和 20 在第 2 层：$(15 + 20) \times 2 = 70$
• 25 在第 2 层：$25 \times 2 = 50$ 总 WPL = $66 + 70 + 50 = 186$。

5. [2 分] 有向图入度与出度之和

答案：B

解析：在有向图中，每条边都有一个起点（贡献一个出度）和一个终点（贡献一个入度）。因此，所有顶点的入度之和等于所有顶点的出度之和，且都等于图中的边数。

6. [2 分] 组合问题（男女生都有）

答案：C

解析：使用“正难则反”思想。

• 总选法：$C_9^4 = 126$
• 全男生选法：$C_5^4 = 5$
• 全女生选法：$C_4^4 = 1$
• 满足条件的选法 = $126 - 5 - 1 = 120$

7. [2 分] 逻辑表达式等价性

答案：C

解析：原表达式 (a && b) || (!c && a) 可化简为 a && (b || !c) (选项 A 正确)。

• 选项 D：!(!a || !b) 等价于 a && b，所以整个表达式为 (a && b) || (a && !c)，与原式相同。
• 选项 B：(a || !c) && (b || !c) && (a || a) 化简后也等价于 a && (b || !c)。
• 选项 C：a && (!b || c)。当 a=true, b=false, c=false 时，原式为 false || true = true，而选项 C 为 true && (true || false) = true？等等，重新验证：
  • 原式: (T&&F) || (T&&T) = F || T = T
  • C: T && (T || F) = T && T = T 再试 a=true, b=true, c=false:
  • 原式: (T&&T) || (T&&T) = T || T = T
  • C: T && (F || F) = T && F = F 此时两者结果不同，故 C 不始终相等。

8. [2 分] 斐波那契模 7 数列

答案：D

解析：斐波那契数列模 7 存在周期（Pisano 周期）。我们列出数列直到出现循环 1, 1： 1, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1, 0, (1, 1)... 周期长度为 16。

• $2025 \div 16 = 126 \times 16 + 9$，余数为 9。
• 数列第 9 项（从 $f[0]$ 开始计数）是 6。

9. [2 分] C++ string 类

答案：B

解析：

• A 错误：string 对象的长度可以通过 +=, append 等方法改变。
• B 正确：C++ 允许 string + char 或 char + string。
• C 错误：length() 和 size() 是完全等价的成员函数，返回值总是相同。
• D 错误：虽然内部实现可能以 \0 结尾，但这个结尾符不计入 length()。

10. [2 分] C++ 引用与值传递

答案：C

解析：这是一个经典的交换函数，但有一个陷阱。

• a 是引用，b 是值传递。
• 执行 a = a + b; → x = 5 + 10 = 15
• 执行 b = a - b; → b = 15 - 10 = 5 (这里的 b 是函数内的局部变量，不影响外部的 y)
• 执行 a = a - b; → x = 15 - 5 = 10 最终，x 变成了 10，而 y 因为是值传递，在函数内未被修改，仍为 10。所以结果是 10, 10。

11. [2 分] 网格路径问题

答案：B

解析：从 (1,1) 到 (4,5)，需要向下走 $4-1=3$ 步，向右走 $5-1=4$ 步，共 7 步。 路径总数是从 7 步中选择 3 步向下（或 4 步向右）的组合数：$C_7^3 = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$。

12. [2 分] 冒泡排序交换次数

答案：B

解析：模拟冒泡排序过程 {6,1,5,2,4}：

• 第1轮：6与1换→{1,6,5,2,4}；6与5换→{1,5,6,2,4}；6与2换→{1,5,2,6,4}；6与4换→{1,5,2,4,6} (4次交换)
• 第2轮：5与2换→{1,2,5,4,6}；5与4换→{1,2,4,5,6} (2次交换)
• 第3轮及以后：无需交换。 总交换次数 = 4 + 2 = 6。

13. [2 分] 进制转换与加法

答案：A

解析：

• $720_{10}$ 保持不变。
• $270_8 = 2 \times 8^2 + 7 \times 8^1 + 0 \times 8^0 = 128 + 56 = 184_{10}$
• 和 = $720 + 184 = 904_{10}$
• 将 904 转换为十六进制：$904 \div 16 = 56 \dots 8$，$56 \div 16 = 3 \dots 8$，$3 \div 16 = 0 \dots 3$。所以结果是 $388_{16}$。

14. [2 分] 完全二叉树的叶子节点数

答案：C

解析：对于一棵有 $n$ 个节点的完全二叉树，其叶子节点数为 $\lceil n/2 \rceil$。

• $n = 1000$，$\lceil 1000/2 \rceil = 500$。 另一种思考：最后一个非叶子节点的编号是 $n/2 = 500$，所以叶子节点编号从 501 到 1000，共 500 个。

15. [2 分] 栈与队列的模拟

答案：A

解析：按规则模拟处理队列 A [7,5,8,3,1,4,2]：

• 7 (奇): S = [7]
• 5 (奇): S = [7, 5]
• 8 (偶, S非空): P = [5], S = [7]
• 3 (奇): S = [7, 3]
• 1 (奇): S = [7, 3, 1]
• 4 (偶, S非空): P = [5, 1], S = [7, 3]
• 2 (偶, S非空): P = [5, 1, 3], S = [7] 最终队列 P 的内容是 5,1,3。

---

二、 阅读程序

(1) 三元组互质计数

判断题

16. A (正确)。输入 n=2，外层 i 最大到 2，j 从 i+1=3 开始，但 3 > n=2，所以内层循环不会执行，自然不会执行第16行的判断。
17. B (错误)。三个数两两互质是一个整体条件。删去 gcd(i,k)==1 后，只要 i,j 和 j,k 互质就算，这可能导致 i,k 不互质的三元组被错误计入，结果会变大。
18. B (错误)。题目提示此为错题。反例：当 n=6 时，无法找到三个两两互质的数（因为 2,3,4,5,6 中任意三个数总会包含一对不互质的数），输出为 0。

单选题

19. B。将 gcd(b, a%b) 改为 gcd(a, a%b) 会导致递归参数错误。例如 gcd(36, 42) 会变成 gcd(36, 36%42=36) → gcd(36, 36) → gcd(36, 0) → 返回 36。但实际上 gcd(36,42)=6。这种错误会让 gcd 函数返回比实际值更大的数，导致更多三元组被认为不互质，最终输出的答案小于原答案。
20. D。通过枚举或已知结论，当 n=8 时，满足条件的三元组数量为 25。
21. A。gcd(36, 42)：42 % 36 = 6；36 % 6 = 0。所以返回 6。

(2) 动态规划去重数组

判断题

22. A (正确)。输入为 n=3, k=1, a=[3,2,1]。排序去重后 a=[1,2,3], n=3。

• i=1, j=0: a[1]-a[1]=0 <= 1, ans[1]=ans[0]+1=1
• i=2, j=0: a[2]-a[1]=1 <= 1, ans[2]=ans[0]+1=1
• i=3, j=0: a[3]-a[1]=2 > 1, j++; a[3]-a[2]=1 <= 1, ans[3]=ans[1]+1=2 输出 ans[3]=2，正确。

23. A (正确)。ans[i] = ans[j] + 1，且 ans[0]=0。ans 数组单调不减，最小值为 1（当所有元素都在一个分组内），最大值为去重后的元素个数 n。
24. B (错误)。std::unique 的作用是去除相邻重复元素。如果输入数组本身没有重复元素，删除 unique 不会影响结果。题目问“有可能”，但标准答案认为在一般情况下（有重复时）才会影响，此处根据答案反推为 错误。

单选题

25. B。第18行的 for 循环结束后，j 是满足 a[i] - a[j+1] <= k 的最大下标。因此 a[i] - a[j+1] <= k，但 a[i] - a[j] 的关系不确定，不一定大于 k。
26. A。a={1..100}, k=2。算法本质是将数组划分为最少的组，使得每组内最大值与最小值之差不超过 k。最优分组为 [1,2,3], [4,5,6], ..., [100]，共 34 组 (前99个数33组，100单独一组)。
27. B。std::sort 是算法正确性的前提。如果数组无序，a[i] - a[j+1] > k 的判断将失去意义，可能导致本应分在同一组的元素被错误分开，从而使输出的答案比原本答案更小。

(3) 最长公共子序列 (LCS)

判断题

28. A (正确)。输入为 n=4, a=[1,2,3,4], b=[1,3,2,2]。两个序列的 LCS 是 [1,3] 或 [1,2]，长度为 2。
29. A (正确)。f[i][j] 表示 a[1..i] 和 b[1..j] 的 LCS 长度。随着 i 和 j 增大，LCS 长度只会增加或不变，不会减少。因此 f[n][n] 是全局最大值。
30. B (错误)。第18行的代码 f[i][j] = max(f[i-1][j], f[i][j-1]) 是 LCS 状态转移的核心部分，用于处理 a[i] != b[j] 的情况。如果删除，f[i][j] 将无法从历史状态继承正确的值，导致结果错误。

单选题

31. D。LCS 的长度：

• 最小为 0（两个序列无公共元素）。
• 最大为 n（两个序列完全相同）。
• 不一定大于等于1（可能为0）。 所以 以上均是。

32. A。对两个数组排序后，它们都变成了升序序列。此时，LCS 就变成了两个升序序列的最长公共子序列，这至少不会比原序列的 LCS 短（因为排序可能创造出新的、更长的公共子序列）。例如 a=[2,1], b=[1,2]，原 LCS 长度为1；排序后 a=[1,2], b=[1,2]，LCS 长度为2。所以答案会变大或不变。
33. B。当 a 是严格递增序列 [1,2,...,n] 时，a 和 b 的 LCS 就等价于在 b 中寻找一个最长的子序列，使其也是严格递增的。这正是 最长上升子序列 (LIS) 的定义。

---

三、 完善程序

(1) 字符串解码 (行程长度编码)

34. C。要检查 z[i+1] 是否为数字，必须确保 i+1 不越界，所以条件是 i + 1 < z.length()。
35. B。count 是一个多位数，需要从左到右逐位构建。标准的字符串转整数方法是 count = count * 10 + (当前数字字符 - '0')。
36. B。count 已经解析出完整的重复次数，循环 count 次即可。
37. B。当前字符 ch 只出现一次，直接将其加入结果字符串 s。
38. C。在 else 分支中，我们已经处理了 z[i]，所以 i 需要自增以处理下一个字符。

(2) 精明与糊涂 (多数投票算法)

39. B。初始候选人 candidate=0，其计数 count 应初始化为 1。
40. C。当 count 减到 0 时，说明当前候选人已被淘汰，需要选择一个新的候选人 i。
41. D。淘汰条件是：当前候选人 candidate 认为 i 是糊涂人 或者 i 认为 candidate 是糊涂人。只要有一方说对方是糊涂人，就说明两人中至少有一个是糊涂人，可以进行抵消。
42. A。发生抵消时，将当前候选人的计数 count 减 1。
43. C。经过消除过程后，最后剩下的 candidate 就是精明人，直接输出 candidate。