参考答案与详细解析

一、 单项选择题

1. B。插空法。6 个蓝球产生 7 个空隙（包括两端），从中选 4 个位置放入红球，方案数为 $C_7^4 = 35$。
2. A。$P = \text{ababaca}$。长度 1("a"):0, 2("ab"):0, 3("aba"):1, 4("abab"):2, 5("ababa"):3, 6("ababac"):0, 7("ababaca"):1。结果为 $\{0, 0, 1, 2, 3, 0, 1\}$。
3. C。线段树查询区间 $[2, 13]$ 访问的节点为：[0,15], [0,7], [8,15], [0,3], [4,7](完全包含), [2,3], [3,3](完全包含), [8,11](完全包含), [12,15], [12,13](完全包含)。共 10 个节点。
4. C。Trie 树节点：root(1), a(2), p(3), p(4, app结束), l(5), e(6, apple结束), y(7, apply结束), e(8, ape结束), b(9), a(10), t(11, bat结束), g(12, bag结束)。共 12 个节点。
5. B。DAG 存在唯一拓扑排序的充要条件是图中存在一条包含所有顶点的有向路径（即哈密顿路径），此时拓扑序唯一且相邻顶点间必有边。
6. B。二次探查 $H_i = (H(key) + i^2) \bmod 11$。23(1), 34(1->2), 45(1->2满->5), 12(1->2满->5满->10), 56(1->2满->5满->10满->6)。最终位置为 6。
7. B。边权 $w(u, v) = u \times v$。为最小化总权重，每个顶点 $v > 1$ 应直接连接到顶点 1，边权为 $v \times 1 = v$。总权重 = $2+3+4+5+6 = 20$。
8. A。后序最后是 A，故根为 A。中序中 A 分割左右子树：左 D B E，右 F C。左子树后序 D E B，根为 B，中序 D B E 分割得左 D 右 E。右子树后序 F C，根为 C，中序 F C 分割得左 F。前序遍历为：根-左-右 $\rightarrow$ A B D E C F。
9. C。容量 15。物品：(3,8), (4,10), (5,12), (6,15), (7,18)。最优组合为选重量 3, 5, 7 的物品，总重量 $3+5+7=15$，总价值 $8+12+18=38$。
10. D。1 是整棵树的根节点，任何节点与根节点 1 的 LCA 必然是 1。因此 $LCA(12, 1) = 4$ 是不可能出现的。
11. C。主定理：$a=3, b=3, f(n) = n \log n$。$n^{\log_b a} = n^1 = n$。$f(n) = \Theta(n^{\log_b a} \log^1 n)$，属于主定理第二种情况的扩展，时间复杂度为 $O(n \log^2 n)$。
12. C。最大堆插入后为：30 (根), 左子 25, 右子 15; 25 的子节点为 20, 10; 15 的子节点为 5。删除 30 后，5 移至根并下沉，堆变为：25, 20, 15, 10, 5。再删除 25，5 移至根并下沉，堆变为：20, 10, 15, 5。堆顶为 20。
13. B。容斥原理。$N=1000$。$|A|=333, |B|=200, |C|=142$；$|A \cap B|=66, |A \cap C|=47, |B \cap C|=28$；$|A \cap B \cap C|=9$。能被整除的数 = $333+200+142 - 66-47-28 + 9 = 543$。不能被整除的数 = $1000 - 543 = 457$。
14. B。分治法在合并时需要 $O(n)$ 时间计算跨越中点的最大子段和，存在大量重复计算；而 Kadane 算法通过 $O(1)$ 的状态转移避免了重复计算，将复杂度降至 $O(n)$。
15. B。这是经典的带截止时间调度问题（最小化延迟惩罚等价于最大化按时完成的任务权重）。最优贪心策略为：按截止时间排序依次尝试加入，若总时间超过当前任务截止时间，则剔除已选任务中处理时间最长的任务（Moore-Hodgson 算法思想）。

二、 阅读程序

（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)$。
21. B。对于正整数，>> 1 和 / 2 结果相同，且现代编译器优化后两者效率基本不变。

（2）

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

（3）

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

三、 完善程序

（1）二分查找

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

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

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