参考答案与详细解析

一、 单项选择题

1. B。计算机中存储容量单位换算是基于二进制的，1 TB = 1024 GB。
2. B。x & -x 是 lowbit 运算，用于提取二进制表示中最低位的 1。$12$ 的二进制为 1100，-12 的补码为 ...0100，按位与结果为 0100，即十进制的 $4$。
3. D。这是斐波那契数列的变体。$f(0)=1, f(1)=1, f(2)=2, f(3)=3, f(4)=5, f(5)=8$。
4. C。若 D 第一个出栈，说明 A, B, C 均已入栈且仍在栈中。此时栈顶为 C，下一个出栈的只能是 C，不可能是 A。
5. A。二叉树的基本性质：对于任何非空二叉树，若叶子结点数为 $n_0$，度为 2 的结点数为 $n_2$，则 $n_0 = n_2 + 1$。
6. A。插空法。3 个红球排好后产生 4 个空隙（包括两端），从中选 2 个位置放入白球，方案数为 $C_4^2 = 6$。
7. A。根据德·摩根定律和分配律：!(A && B) || (A && C) = !A || !B || (A && C) = (!A || A) && (!A || C) || !B = True && (!A || C) || !B = !A || C || !B。
8. C。$10110_2 = 22_{10}$，$1A_{16} = 16+10 = 26_{10}$。和为 $48_{10}$。$48 \div 8 = 6 \dots 0$，即 $60_8$。
9. B。vector::push_back 的均摊时间复杂度为 $O(1)$。但当容量不足触发重新分配内存时，单次操作需要复制所有元素，时间复杂度为 $O(N)$。
10. B。a 是引用传递，b 是值传递。函数内 t=5, a=10, b=5。调用结束后，外部的 x 被修改为 10，而 y 保持原值 10 不变。
11. A。从 $(1,1)$ 到 $(4,4)$ 需要向右走 3 步，向下走 3 步，共 6 步。路径数为组合数 $C_{3+3}^3 = C_6^3 = 20$。
12. D。数组完全逆序，冒泡排序每次相邻比较都会发生交换。总交换次数为 $4 + 3 + 2 + 1 = 10$ 次。
13. C。构造哈夫曼树：合并 2, 3 得到 5；合并 5, 5 得到 10；合并 7, 9 得到 16；合并 10, 16 得到 26。WPL = $2\times3 + 3\times3 + 5\times2 + 7\times2 + 9\times2 = 6 + 9 + 10 + 14 + 18 = 57$。
14. B。外层循环执行 $n$ 次，内层循环执行 $i$ 次。总执行次数为 $1 + 2 + \dots + n = \frac{n(n+1)}{2}$，时间复杂度为 $O(n^2)$。
15. A。操作过程：入 1,2,3 $\rightarrow$ 队列 [1, 2, 3]；出 $\rightarrow$ [2, 3]；入 4,5 $\rightarrow$ [2, 3, 4, 5]；出, 出 $\rightarrow$ [4, 5]。

二、 阅读程序

（1）

16. A (正确)。$1 \dots 3$ 的二进制中 1 的个数分别为：1(1), 2(1), 3(2)。奇数个 1 的数有 1 和 2，共 2 个。
17. A (正确)。while(x) 循环每次将 $x$ 右移一位，循环次数等于 $x$ 的二进制位数，即 $O(\log x)$。
18. B (错误)。对于正整数，x & 1 和 x % 2 在判断奇偶性上完全等价，不会改变结果。
19. B。$1 \dots 7$ 中二进制 1 的个数：1(1), 2(1), 3(2), 4(1), 5(2), 6(2), 7(3)。奇数个 1 的数有 1, 2, 4, 7，共 4 个。
20. B。外层循环 $n$ 次，内层 count_ones 耗时 $O(\log i)$，总时间复杂度为 $O(n \log n)$。

（2）

21. A (正确)。连续递增子序列有 [1, 2, 5] (长度3) 和 [3, 4] (长度2)，最大长度为 3。
22. A (正确)。若全部相等，a[i] > a[i-1] 始终为假，cur_len 始终重置为 1，max_len 保持初始值 1。
23. B (错误)。若删除 cur_len = 1;，当遇到非递增元素时，cur_len 不会重置，会继续累加或保持错误状态，导致结果错误。
24. A。数组严格递减，a[i] > a[i-1] 始终为假，max_len 保持初始值 1。
25. B。程序使用了一个大小为 $n$ 的 vector<int> a，空间复杂度为 $O(n)$。
26. B。若初始为 0，当数组严格递减时，循环内 max_len 不会被更新，最终输出 0，而正确答案应为 1（单个元素本身构成长度为 1 的序列）。

（3）

27. A (正确)。逆序遍历保证了在更新 dp[j] 时，dp[j - w[i]] 使用的是上一轮（未加入当前物品）的状态，符合 0-1 背包每个物品只能用一次的要求。若正序，则会多次使用同一物品，变为完全背包。
28. A (正确)。两层循环，外层 $n$ 次，内层最多 $W$ 次，时间复杂度为 $O(n \times W)$。
29. A (正确)。dp 全 0 初始化表示容量为任何值时，不选任何物品的价值为 0，允许背包有空余容量。
30. B。物品：(2,3), (1,2), (3,4)，容量 4。最优解为选择物品 2 (重1, 价2) 和物品 3 (重3, 价4)，总重 4，总价值 $2+4=6$。
31. B。恰好装满的初始化标准做法：dp[0] = 0（容量为0时价值为0，合法），其余 dp[j] = -INF（表示不可达）。
32. C。正序遍历变为完全背包。物品可无限次使用。容量 4 时，最优解为选 4 个物品 2 (重1, 价2)，总价值 $4 \times 2 = 8$。

三、 完善程序

（1）二分查找

33. A。找到满足 a[mid] >= x 的位置，记录当前 mid 为潜在答案 ans = mid。
34. B。为了寻找“第一个”满足条件的元素，需要继续在左半区间查找，故 right = mid - 1。
35. C。若 a[mid] < x，说明目标在右半区间，故 left = mid + 1。
36. A。题目要求输出“下标”，若找到则输出 ans。
37. C。若 ans 仍为初始值 $n$，说明未找到，按题目要求输出 -1。

（2）最长递增子序列 (LIS)

38. B。每个元素自身至少可以构成长度为 1 的递增子序列，故 dp 数组初始化为 1。
39. B。同理，最小可能的最长递增子序列长度为 1，故 max_len 初始化为 1。
40. B。状态转移方程：若 a[i] > a[j]，则 a[i] 可以接在 a[j] 后面，长度为 dp[j] + 1。
41. B。每计算完一个 dp[i]，都需要用它来更新全局最大值 max_len。
42. C。最终结果即为全局记录的最大长度 max_len。