一、单项选择题解析

1. A ｜ bool 类型默认用 cout 输出时，false 输出为 0。

2. C ｜ $101011_2 = 43$，$36_8 = 30$，和为 $73$。

3. A ｜ a += b 会先将 $a$ 改为 $7$，表达式值也是 $7$，随后再次输出 $a$，所以为 7 7。

4. C ｜ 若先弹出 $4$，栈中从顶到底为 $3, 2, 1$，此时不能直接弹出 $2$。

5. B ｜ 删除 p 的直接后继结点，本质是让 p 的 next 跳过原来的下一个结点。

6. C ｜ 设叶子数为 $n_0$，有两个孩子的结点数为 $n_2$，满足 $n_0 = n_2 + 1$。总结点数 $n_0 + n_2 = 13$，所以 $n_0 = 7$。

7. A ｜ 拓扑序要求每条有向边的起点都出现在终点之前，只有选项 A 满足所有约束。

8. C ｜ 先计算 $b - c$，再乘以 $d$，最后加上 $a$，后缀表达式为 abc-d*+。

9. C ｜ 哈夫曼合并过程为 $2 + 4 = 6$，$6 + 7 = 13$，$9 + 13 = 22$，频率为 $2$ 的字符深度为 $3$。

10. B ｜ 根为 $A$，左子树由 $B, D$ 构成，右子树由 $C, E$ 构成，后序遍历为 $D\ B\ E\ C\ A$。

11. C ｜ $2^{10} = 1024$，$1025$ 个元素最坏情况下最多比较 $11$ 次。

12. A ｜ 外层 $i$ 依次为 $1, 2, 4, \ldots$，内层次数约为 $n + n/2 + n/4 + \cdots$，总复杂度为 $O(n)$。

13. B ｜ 至少 $2$ 名女生，方案数为 $C_4^2 \times C_5^1 + C_4^3 = 30 + 4 = 34$。

14. C ｜ $f(3) = 4$，$f(4) = 7$，$f(5) = 12$。

15. C ｜ return 是 C++ 关键字，不能作为变量名。

二、阅读程序解析

阅读程序（一）

函数 f 统计整数二进制表示中 $1$ 的个数；函数 g 从 $1$ 开始不断乘 $2$，直到再乘 $2$ 会超过 $x$，因此返回不超过 $x$ 的最大 $2$ 的幂。

16. A（正确） ｜ 输入 $10$，$f(10) = f(1010_2) = 2$，$g(10) = 8$，输出 2 8。

17. A（正确） ｜ 若 $n$ 是 $2$ 的正整数次幂，则二进制表示只有 $1$ 个 $1$，$f(n) = 1$。

18. A（正确） ｜ $g$ 函数不断将 $r$ 乘 $2$，直到 $r \times 2 > x$，返回的 $r$ 就是不超过 $x$ 的最大 $2$ 的幂。

19. B ｜ $2026 = 11111101010_2$，有 $8$ 个 $1$，$g(2026) = 1024$，输出 8 1024。

20. C ｜ 函数 f 和 g 的循环次数都与 $\log n$ 成正比，时间复杂度为 $O(\log n)$。

阅读程序（二）

函数 f 枚举两个字符串的起点，再向后比较连续相同的长度，求的是最长公共子串长度；函数 g 从两端向中间比较，判断字符串是否为回文串。

21. A（正确） ｜ 函数 f 通过枚举起点并扩展匹配长度，确实求的是最长公共子串长度。

22. A（正确） ｜ 若两个字符串完全相同，则从起点 $(0, 0)$ 开始可以匹配整个字符串长度。

23. A（正确） ｜ 函数 g 从两端向中间逐对比较字符，是标准的回文判断方法。

24. B ｜ abca 和 bcab 的最长公共子串是 bca，长度为 $3$；abcabc 不是回文串，g 返回 $0$。

25. C ｜ abc 和 cba 的最长公共子串长度为 $1$；abccba 是回文串，g 返回 $1$。

26. D ｜ 两层循环枚举起点 $O(nm)$，内层 while 最多扩展 $\min(n, m)$ 次，总复杂度 $O(nm \min(n, m))$。

阅读程序（三）

转移条件是 a[j] <= a[i]，因此求的是最长不下降子序列，而不是最长严格上升子序列。$dp_i$ 表示以第 $i$ 个元素结尾时的最优长度。

27. B（错误） ｜ 转移条件是 a[j] <= a[i]（允许相等），求的是最长不下降子序列，不是严格上升。

28. A（正确） ｜ 若所有数相等，任意子序列都是不下降的，以第 $i$ 个数结尾的最长不下降子序列长度为 $i$，最大值为 $n$。

29. A（正确） ｜ $dp_i$ 的定义就是以第 $i$ 个数结尾的最长不下降子序列长度。

30. C ｜ 输入 3 1 2 2 1 4，最长不下降子序列为 1 2 2 4，长度为 $4$。

31. B ｜ 输入 5 4 3 2 1 1 1，最长不下降子序列为 1 1 1，长度为 $3$。

32. B ｜ 输入 2 1 3 2 4 3 5 4，最长不下降子序列为 1 2 3 4 或 1 2 3 5 等，长度为 $4$。

三、完善程序解析

完善程序（一）

这是归并过程。两个数组都还有元素时，比较当前元素，把较小者放入结果数组；某一边用完后，再把另一边剩余元素依次加入。

33. C ｜ ① 处是主循环条件，两个数组都还有元素时才继续比较，应填 i <= n && j <= m。

34. A ｜ ② 处判断哪个元素更小，升序合并应填 a[i] <= b[j]。

35. B ｜ ③ 处是 a[i] 更小时的操作，应将 a[i] 放入结果数组，填 c[++k] = a[i++]。

36. C ｜ ④ 处是处理 b 数组剩余元素的条件，应填 j <= m。

37. D ｜ ⑤ 处是将 b 数组剩余元素加入结果，应填 c[++k] = b[j++]。

完善程序（二）

这是最长公共子序列动态规划。若 $a_{i-1} = b_{j-1}$，则可以由 $dp_{i-1,j-1}$ 转移并加 $1$；否则从去掉 $a$ 当前字符或去掉 $b$ 当前字符两种情况中取最大值。

38. B ｜ ① 处是外层循环上界，遍历字符串 $a$，应填 n。

39. C ｜ ② 处是内层循环上界，遍历字符串 $b$，应填 m。

40. B ｜ ③ 处判断字符是否相等，注意下标从 $1$ 开始，应填 a[i - 1] == b[j - 1]。

41. C ｜ ④ 处是字符不相等时的转移，取两种情况的最大值，应填 max(dp[i - 1][j], dp[i][j - 1])。

42. D ｜ ⑤ 处输出最终结果，最长公共子序列长度存储在 dp[n][m]。