以下是 2023 年 CSP-J 第一轮试题的详细解答与解析：

---

一、 单项选择题

1. 答案：B
解析：在 C++ 中，const 关键字用于声明常量，其值在初始化后不能被修改。unsigned 是无符号修饰符，static 是静态存储修饰符，mutable 用于允许修改 const 对象中的特定成员。

2. 答案：D
解析：八进制加法，逢 8 进 1：

  12345670
+ 07654321
----------
  22222211

从右向左：0+1=1；7+2=9（写1进1）；6+3+1=10（写2进1）；5+4+1=10（写2进1）；4+5+1=10（写2进1）；3+6+1=10（写2进1）；2+7+1=10（写2进1）；1+0+1=2。结果为 $22222211_8$。

3. 答案：A
解析：union Data data; 声明了一个联合体变量 data。访问联合体成员应使用点运算符 .，因此正确方式是 data.value = 3.14;。

4. 答案：A
解析：在链表头部插入新节点的标准操作是：1. 创建新节点并赋值；2. 将新节点的 next 指向当前的 head；3. 将 head 更新为新节点。即 newNode->data = 42; newNode->next = head; head = newNode;。

5. 答案：C
解析：高度为 $h$ 的满三叉树的节点总数公式为 $N = \frac{3^h - 1}{2}$。

• $h=6$ 时，$N = (729-1)/2 = 364$
• $h=7$ 时，$N = (2187-1)/2 = 1093$
• $h=8$ 时，$N = (6561-1)/2 = 3280$ 2023 个节点超过了 7 层的最大容量，因此高度至少为 8。

6. 答案：B
解析：使用插空法或组合数学。设选择了 $k$ 个时间段，则需要至少 $2(k-1)$ 个空闲时间段作为间隔。剩余可自由分配的时间段为 $7 - 2(k-1)$。

• $k=1$：$C_7^1 = 7$ 种
• $k=2$：$C_{7-2}^2 = C_5^2 = 10$ 种
• $k=3$：$C_{7-4}^3 = C_3^3 = 1$ 种 总方案数 = $7 + 10 + 1 = 18$ 种。

7. 答案：C
解析：高精度乘法的时间复杂度与两个整数的位数都有关（朴素算法为 $O(L_1 \times L_2)$），而不是只与较长者的位数有关。因此 C 说法错误。

8. 答案：A
解析：后缀表达式转中缀表达式，按运算符优先级和结合性加括号：

• 2 3 + $\rightarrow$ (2+3)
• 6 (2+3) - $\rightarrow$ (6-(2+3))
• 8 2 / $\rightarrow$ (8/2)
• 3 (8/2) + $\rightarrow$ (3+8/2)
• 两者相乘 $\rightarrow$ ((6-(2+3))*(3+8/2))
• ^ 2 $\rightarrow$ ((6-(2+3))*(3+8/2))^2
• + 3 $\rightarrow$ ((6-(2+3))*(3+8/2))^2+3

9. 答案：D
解析：统一转换为十进制计算：

• $101010_2 = 32 + 8 + 2 = 42_{10}$
• $166_8 = 1 \times 64 + 6 \times 8 + 6 = 118_{10}$
• 和 = $42 + 118 = 160_{10}$
• $160_{10} = 16 \times 10 = A0_{16}$。

10. 答案：A
解析：构造哈夫曼树：合并 5 和 9 得 14；合并 12 和 13 得 25；合并 14 和 16 得 30；合并 25 和 30 得 55；合并 45 和 55 得 100。 各字符编码长度应为：45(1位), 16(3位), 12(3位), 13(3位), 5(4位), 9(4位)。选项 A 的长度分布 (4, 4, 3, 3, 3, 1) 完全符合，且满足前缀码性质。

11. 答案：A
解析：根据前序 ABDECFG 和中序 DEBACFG 重建二叉树：

• 根为 A。左子树中序 DEB，前序 BDE $\rightarrow$ 根 B，D 为 B 的左孩子，E 为 D 的右孩子。左子树后序为 EDB。
• 右子树中序 CFG，前序 CFG $\rightarrow$ 根 C，F 为 C 的右孩子，G 为 F 的右孩子。右子树后序为 GFC。
• 总后序遍历（左-右-根）：EDB + GFC + A = EDBGFCA。

12. 答案：B
解析：边为 (1,2), (1,3), (2,4), (3,4)。拓扑排序要求 1 必须在 2 和 3 之前，2 和 3 必须在 4 之前。因此合法的排序只能是 1, 2, 3, 4 或 1, 3, 2, 4。选项 B 符合。

13. 答案：B
解析：比特 (bit) 是计算机中最小的数据存储容量单位，1 Byte = 8 bit。

14. 答案：A
解析：使用“正难则反”法。从 22 人中任选 3 人的总组合数为 $C_{22}^3 = \frac{22 \times 21 \times 20}{6} = 1540$。全是男生的组合数为 $C_{10}^3 = \frac{10 \times 9 \times 8}{6} = 120$。至少包含 1 个女生的组合数 = $1540 - 120 = 1420$。

15. 答案：D
解析：HTML (HyperText Markup Language) 是一种超文本标记语言，用于创建网页，不是操作系统。Linux, Windows, Android 均为操作系统。

---

二、 阅读程序

(1) 海伦公式求三角形面积

16. 答案：A (正确)
解析：输入 2, 2, 2，半周长 $s=3$。面积 $S = \sqrt{3 \times 1 \times 1 \times 1} = \sqrt{3} \approx 1.73205$。程序设置了保留 4 位小数，四舍五入后输出 1.7321，正确。

17. 答案：A (正确)
解析：实数乘法满足交换律，(s-b)*(s-c) 与 (s-c)*(s-b) 计算结果完全相同，不影响程序运行。

18. 答案：B (错误)
解析：题目仅说明“输入的所有数都为不超过1000的正整数”，并未保证这三个数一定能构成三角形。如果输入 1 1 3，则 $s(s-a)(s-b)(s-c)$ 为负数，sqrt 函数将返回 NaN (Not a Number)，此时输出为 nan，而不是四位小数。因此“总是”说法错误。

19. 答案：A
解析：输入 3, 4, 5，构成直角三角形，面积为 $\frac{1}{2} \times 3 \times 4 = 6$。保留 4 位小数输出 6.0000。

20. 答案：B
解析：输入 5, 12, 13，构成直角三角形，面积为 $\frac{1}{2} \times 5 \times 12 = 30$。保留 4 位小数输出 30.0000。

(2) 字符串最长公共子序列 (LCS) 变种

21. 答案：A (正确)
解析：f 函数计算的是两个字符串的最长公共子序列 (LCS) 的长度。公共子序列的长度不可能超过参与比较的任何一个字符串的长度，因此必定 $\le \min(n, m)$。

22. 答案：B (错误)
解析：f 函数计算的是最长公共子序列 (Subsequence，不要求连续)，而不是最长公共子串 (Substring，要求连续)。

23. 答案：A (正确)
解析：若输入两个完全相同的字符串 $x$ 和 $y$（即 $x=y$），则 $x+x$ 必然包含完整的 $x$ 作为子序列。因此 f(x+x, y) 的返回值等于 $y$ 的长度，g 函数返回 true。

24. 答案：D
解析：二维数组 v 的维度是 (m+1) \times (n+1)。如果将其替换为 v[n][m]，当 $n > m$ 时，行下标 $n$ 将超出最大合法下标 $m$，导致数组越界访问，程序可能非正常退出（如段错误）。

25. 答案：B
解析：输入 x="csp-j", y="p-jcs"。x+x 为 "csp-jcsp-j"。在 x+x 中可以按顺序找到 y 的所有字符：p(idx 2), -(idx 3), j(idx 4), c(idx 5), s(idx 6)。LCS 长度为 5，等于 y.size()，g 返回 true。C++ 中 cout << true 默认输出 1。

26. 答案：D
解析：输入 x="csppsc", y="spsccp"。x+x 为 "csppsccsppsc"。在 x+x 中可以按顺序找到 y：s(1), p(2), s(4), c(5), c(6), p(8)。LCS 长度为 6，等于 y.size()，g 返回 true，输出 1。

(3) 因子平方和计算

27. 答案：A (正确)
解析：solve2 函数通过遍历 $1$ 到 $\sqrt{n}$，找到所有因子对 $(i, n/i)$，并将它们的平方累加，正是计算 $n$ 的所有因子的平方和。

28. 答案：A (正确)
解析：当 $n$ 是完全平方数时，$i = n/i$。第 13-14 行的 if 判断确保了这个平方根因子只被累加一次，避免了重复计算。

29. 答案：A (正确)
解析：若 $n$ 为质数，其正因子只有 $1$ 和 $n$。平方和为 $1^2 + n^2 = n^2 + 1$。

30. 答案：B
解析：若 $n = p^2$ ($p$ 为质数)，其因子为 $1, p, p^2$。平方和为 $1^2 + p^2 + (p^2)^2 = 1 + p^2 + p^4$。因为 $n = p^2$，代入得 $1 + n + n^2$。

31. 答案：D
解析：第一项为 $n^2$ 的因子平方和，第二项为 ($n$ 的因子平方和) 的平方。

• 当 $n=1$ 时，第一项 = 1，第二项 = 1，差值 = 0。
• 当 $n=2$ 时，第一项 = solve2(4) = $1^2+2^2+4^2 = 21$；第二项 = solve1(solve2(2)) = solve1(1^2+2^2) = solve1(5) = 25。差值 = 21 - 25 = -4 < 0。 因此差值小于等于 0 且不一定小于 0。

32. 答案：C
解析：输入 $n=5$。

• 第一项：solve2(25)。25 的因子为 1, 5, 25。平方和 = $1 + 25 + 625 = 651$。
• 第二项：solve1(solve2(5))。5 的因子为 1, 5。平方和 = $1 + 25 = 26$。solve1(26) = $26^2 = 676$。 输出为 651 676。

---

三、 完善程序

(1) 寻找被移除的元素

33. 答案：B
解析：在未缺失的连续部分，应满足 nums[i] == nums[0] + i。因此 ① 处填 nums[0]。

34. 答案：A
解析：若 nums[mid] == mid + nums[0]，说明 mid 及之前的元素都是连续的，缺失的元素必然在 mid 的右侧，故 left = mid + 1。

35. 答案：C
解析：若不相等，说明缺失发生在 mid 或 mid 之前，故右边界收缩为 right = mid。

36. 答案：A
解析：循环结束时 left == right，指向第一个发生偏移的位置。该位置原本应有的值为 left + nums[0]。

37. 答案：D
解析：如果移除的是首尾元素，数组依然保持连续，二分查找会一直向右推进，最终 left 停在 n-1，返回值为 n-1 + nums[0]，这恰好等于数组的最后一个元素 nums[n-1]。因此判断连续的条件是 missing_number == nums[n-1]。

(2) 编辑距离 (动态规划)

38. 答案：A
解析：当 i == 0 时，str1 为空串，要变成 str2 的前 j 个字符，需要 j 次插入操作。故 ① 填 j。

39. 答案：B
解析：当 j == 0 时，str2 为空串，str1 的前 i 个字符要变成空串，需要 i 次删除操作。故 ② 填 i。

40. 答案：A
解析：当两个字符相等时，不需要额外操作。C++ 字符串下标从 0 开始，长度为 i 的前缀的最后一个字符是 str1[i-1]。故 ③ 填 str1[i-1] == str2[j-1]。

41. 答案：B
解析：字符相等时，当前编辑距离等于去掉这两个字符后的子问题的编辑距离，即 dp[i-1][j-1]。故 ④ 填 dp[i-1][j-1]。

42. 答案：C
解析：字符不相等时，取删除 (dp[i-1][j])、插入 (dp[i][j-1])、替换 (dp[i-1][j-1]) 三种操作的最小值加 1。外层已有 1 +，故 ⑤ 填 dp[i-1][j-1]。