参考答案与详细解析

一、 单项选择题

1. A。16位有符号整数的范围是 $-2^{15}$ 到 $2^{15}-1$，即 $-32768$ 到 $32767$。最大值 $32767$ 最接近 $3 \times 10^4$。
2. B。x & -x 是经典的 lowbit 运算，用于获取二进制表示中最低位的 1 及其后面的 0 组成的值。$12$ 的二进制是 1100，-12 的补码是 ...0100，按位与结果为 0100，即十进制的 $4$。
3. B。递归展开：$f(0)=0, f(1)=1$。$f(2)=f(1)+f(0)+1 = 2$。$f(3)=f(2)+f(1)+1 = 2+1+1=4$。$f(4)=f(3)+f(2)+1 = 4+2+1=7$。$f(5)=f(4)+f(3)+1 = 7+4+1=12$。
4. B。构造哈夫曼树：合并 5 和 9 得到 14；合并 12 和 13 得到 25；合并 14 和 16 得到 30；合并 25 和 30 得到 55。WPL = $5\times3 + 9\times3 + 12\times2 + 13\times2 + 16\times2 = 15 + 27 + 24 + 26 + 32 = 124$。
5. C。无向图中，每条边为两个顶点的度数各贡献 1，因此所有顶点的度数之和等于边数的 2 倍（握手定理）。
6. A。总选法 $C(9,3) = 84$。全红的选法 $C(4,3) = 4$。全蓝的选法 $C(5,3) = 10$。满足条件的选法 = $84 - 4 - 10 = 70$。
7. A。原式 $= (\neg a \lor \neg b) \lor (a \land c) = \neg a \lor \neg b \lor (a \land c)$。根据分配律，$\neg a \lor (a \land c) = (\neg a \lor a) \land (\neg a \lor c) = \text{True} \land (\neg a \lor c) = \neg a \lor c$。因此原式等价于 $\neg a \lor \neg b \lor c$，即 !a || !b || c。
8. A。数列模 5 的斐波那契数列（Pisano period）周期为 20。数列为：0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, (0, 1...)。$2025 \pmod{20} = 5$，对应 $a_5 = 0$。
9. B。vector 在尾部插入均摊 $O(1)$，但当容量不足触发扩容时，需要重新分配内存并复制元素，最坏情况为 $O(N)$。A 错在 capacity $\ge$ size；C 错在 erase 后元素会前移；D 错在 vector 内存是连续的。
10. A。p 是指针，*p 修改了 a 的值，a 变为 $3+4=7$。q 是值传递，函数内 q 的改变不影响外部的 b，b 仍为 4。
11. A。总路径数 $C(3+4, 3) = C(7,3) = 35$。经过 (1,1) 的路径数 = (0,0)到(1,1)的路径数 $\times$ (1,1)到(3,4)的路径数 = $C(2,1) \times C(2+3, 2) = 2 \times 10 = 20$。不经过的路径数 = $35 - 20 = 15$。
12. A。简单选择排序每趟从未排序部分选出最小值与当前位置交换。第1趟：1和5交换 {1, 2, 8, 5, 9} (1次)；第2趟：2已在位 (0次)；第3趟：5和8交换 {1, 2, 5, 8, 9} (1次)；第4趟：8已在位 (0次)。共 2 次。
13. B。$11010_2 = 26_{10}$，$1A_{16} = 16+10 = 26_{10}$。和为 $52_{10}$。$52 \div 8 = 6 \dots 4$，即 $64_8$。
14. C。设非叶子节点数为 $I$，叶子节点数为 $L$。总节点数 $I + L = 2023$。总分支数（即除根外的节点数）为 $3I = L + I - 1 \Rightarrow L = 2I + 1$。代入得 $3I + 1 = 2023 \Rightarrow 3I = 2022 \Rightarrow I = 674$。$L = 2023 - 674 = 1349$。
15. A。操作过程：[1] $\rightarrow$ [2, 1] $\rightarrow$ [2] (pop 1) $\rightarrow$ [2, 3] $\rightarrow$ [4, 2, 3] $\rightarrow$ [2, 3] (pop 4)。结果为 2, 3。

二、 阅读程序

（1）

16. A (正确)。程序统计 $1 \dots n$ 中约数个数为奇数的数的个数。约数个数为奇数的数是完全平方数。10 以内的完全平方数有 1, 4, 9，共 3 个。
17. B (错误)。改为 j++ 后，内层循环失去了“枚举倍数”的意义，不仅结果会完全错误（变成了统计 $i \le j$ 的次数），且时间复杂度会退化为 $O(n^2)$，运行时间变长。
18. A (正确)。内层循环执行次数为 $n/1 + n/2 + \dots + n/n = n(1 + 1/2 + \dots + 1/n) \approx n \ln n$，时间复杂度为 $O(n \log n)$。
19. C。cnt[i] == 2 意味着统计只有 2 个约数的数，即质数。10 以内的质数有 2, 3, 5, 7，共 4 个。
20. B。100 以内的完全平方数有 $1^2, 2^2, \dots, 10^2$，共 10 个。
21. B。在函数内声明大数组会分配在栈区，容易导致栈溢出 (Stack Overflow)。全局变量分配在数据区，空间更大，且 C++ 保证全局数组自动初始化为 0。

（2）

22. B (错误)。该双指针（滑动窗口）算法的前提是数组元素均为非负数。如果存在负数，sum 增大时 right 右移，但 sum 也可能因为负数而减小，此时收缩 left 可能会错过正确的解。
23. A (正确)。如果 a[right] > k，sum 会大于 $k$，如果没有 left <= right 的限制，left 会一直增加直到超过 right，导致逻辑错误甚至越界访问。
24. B (错误)。虽然有两层循环，但 right 从 0 增加到 $n-1$，left 也最多从 0 增加到 $n-1$。每个元素最多被 left 和 right 各访问一次，因此时间复杂度是 $O(n)$。
25. B。right=2 时，子数组 [2, 3] 和为 5，ans=1；right=4 时，子数组 [5] 和为 5，ans=2。共 2 个。
26. B。如果原本 sum == k，进入 while 循环后 sum 会减去 a[left] 而变小，导致错失这次 sum == k 的判定，造成漏解。
27. B。所有元素为 1，求和为 3 的连续子数组，即长度为 3 的子数组。在长度为 10 的数组中，长度为 3 的连续子数组共有 $10 - 3 + 1 = 8$ 个。

（3）

28. A (正确)。这是经典的二维网格最大路径和 DP，状态转移方程正确限制了只能从上方或左方转移。
29. A (正确)。如果改为 0，当矩阵全为负数时，算法可能会错误地从边界外（值为0）转移，从而得到 0 或偏大的结果，而不是真实的负数最大和。
30. B (错误)。由于 dp[i][j] 只依赖于 dp[i-1][j] 和 dp[i][j-1]，可以使用滚动数组（只保留上一行和当前行，甚至一维数组）将空间复杂度优化到 $O(m)$。
31. C。路径 1 $\rightarrow$ 4 $\rightarrow$ 5 $\rightarrow$ 6 的和为 16，是所有路径中的最大值。
32. A。增加对角线转移来源 from_diag，并在取最大值时将其纳入考量，符合新规则。
33. C。全为 -1 的 $3 \times 3$ 矩阵，从 (0,0) 到 (2,2) 无论怎么走，都需要经过 5 个格子（向右2步，向下2步，共5个节点）。最大和即为 $5 \times (-1) = -5$。

三、 完善程序

（1）快速幂算法

34. B。累乘器 res 的初始值应为乘法单位元 1。
35. B。判断指数 b 的当前最低位是否为 1，即 b % 2 == 1（或 b & 1）。
36. B。每次处理完最低位后，指数右移一位，即 b = b / 2（或 b >>= 1）。
37. B。循环结束后，res 中存储的即为最终结果。
38. B。C++ 中输出换行通常使用 endl。

（2）最长递增子序列 (LIS) $O(n \log n)$ 解法

39. B。二分查找的目标是找到 tail 数组中第一个大于或等于 a[i] 的元素位置。当 tail[mid] < a[i] 时，说明目标在右侧，left = mid + 1；否则目标在左侧或就是 mid，故 right = mid。
40. A。如果 left == tail.size()，说明 a[i] 比 tail 中所有元素都大，可以延长最长递增子序列，故调用 push_back(a[i])。
41. A。否则，用 a[i] 替换 tail[left]，目的是在保证长度不变的前提下，让该长度的子序列的末尾元素尽可能小，以便后续接上更多的数。
42. B。tail 数组的长度即为最长严格递增子序列的长度，使用 size() 获取。
43. B。输出结果后换行，使用 endl。