参考答案与深度解析

第一部分：单项选择题

1. 【答案】A

【解析】

1. 八进制 $(65)_8 = 6 \times 8 + 5 = 53 = (00110101)_2$。
2. 十六进制 $(2D)_{16} = 2 \times 16 + 13 = 45 = (00101101)_2$。
3. 二者按位与（AND）：

     0 0 1 1 0 1 0 1  (53)
   & 0 0 1 0 1 1 0 1  (45)
   ------------------
     0 0 1 0 0 1 0 1  (37)
   

4. 与二进制 $(101001)_2 = (00101001)_2$ 进行按位异或（XOR）：

     0 0 1 0 0 1 0 1
   ^ 0 0 1 0 1 0 0 1
   ------------------
     0 0 0 0 1 1 0 0  (= 12)
   

5. 十进制数 $12$ 转为十六进制即为 0x0C。故选 A。

2. 【答案】B

【解析】 逻辑表达式为：(a++ > 1 && ++b > 2) || (c++ == 3 && ++d > 4)。

• 首先计算逻辑或 || 左侧子表达式：(a++ > 1 && ++b > 2)。
  • 先判断 a++ > 1：后置自增，先取 a 的当前值 1 比较，1 > 1 为 false，随后 a 自增为 2。
  • 由于左侧条件为假，触发逻辑与（&&）短路，右侧 ++b > 2 直接跳过不执行！因此 b 仍保持初始值 2。
  • 左侧整个子表达式结果为 false。
• 因为左侧为假，继续执行逻辑或 || 右侧子表达式：(c++ == 3 && ++d > 4)。
  • 先判断 c++ == 3：先取 c 当前值 3 比较，3 == 3 为 true，随后 c 自增为 4。
  • 前半部分为真，不发生短路，继续计算 ++d > 4：前置自增，d 先自增为 5，再比较 5 > 4 为 true。
• 最终各变量状态：a = 2, b = 2, c = 4, d = 5。故选 B。

3. 【答案】B

【解析】 设小明、小华、小红分得的苹果数量分别为 $x_1, x_2, x_3$。 题意即求不定方程：

$$x_1 + x_2 + x_3 = 9$$

在满足整数约束 $x_1 \ge 2, x_2 \ge 1, x_3 \ge 3$ 下的非负整数解的组数。

• 隔板法经典转化： 先满足每人的最低保底需求：先分给小明 1 个、小华 0 个、小红 2 个，共预分配 $1 + 0 + 2 = 3$ 个苹果。 令 $y_1 = x_1 - 1 \ge 1$，$y_2 = x_2 \ge 1$，$y_3 = x_3 - 2 \ge 1$。 方程转化为：$$y_1 + y_2 + y_3 = 9 - 3 = 6 \quad (y_1, y_2, y_3 \ge 1) $$这等价于：将 6 个相同的苹果排成一排，在中间形成的 $6 - 1 = 5$ 个空隙中插入 $3 - 1 = 2$ 块隔板。 不同方案数为：$$C_5^2 = \frac{5 \times 4}{2 \times 1} = 10$$

故选 B。

4. 【答案】A

【解析】 二进制数转换为格雷码的标准异或公式为 $G = B \oplus (B >> 1)$。

• 已知二进制 $B = (10011)_2$。
• 将其逻辑右移 1 位：$B >> 1 = (01001)_2$。
• 逐位按位异或：

    1  0  0  1  1
  ^ 0  1  0  0  1
  ----------------
    1  1  0  1  0
  

得到格雷码为 11010。故选 A。

5. 【答案】A

【解析】 在双向链表中插入节点，核心原则是**“先连新节点的外向指针，再修改原链表的指针”**，以防止断链或丢失后继节点。

• A 选项：
  1. s->next = p->next;：新节点 s 的后继指向原后继节点。
  2. p->next->prev = s;：原后继节点的前驱指向 s。
  3. s->prev = p;：新节点 s 的前驱指向 p。
  4. p->next = s;：p 的后继指向 s。逻辑完全闭环，正确。
• B、C 选项过早执行了 p->next = s;，导致原 p 的后继节点丢失。
• D 选项最后一句执行 p->next->prev = s; 时，由于前面已经将 p->next 赋为 s，相当于执行了 s->prev = s;，形成自环错误。故选 A。

6. 【答案】C

【解析】 初始堆数组（1-indexed）：[0, 3, 7, 5, 12, 9, 8, 10]（堆大小为 7）。

1. 弹出堆顶 3，末尾元素 10 移动到堆顶（下标 1），堆大小变为 6。
2. 第一轮下沉（当前位于下标 1，值为 10）：
   • 左孩子下标 2（值为 7），右孩子下标 3（值为 5）。
   • 孩子中的较小者是右孩子 5（下标 3）。
   • 因为 $5 < 10$，将 10 与 5 交换。5 升至堆顶下标 1，10 下沉到下标 3。
3. 第二轮下沉（当前位于下标 3，值为 10）：
   • 左孩子下标 $3 \times 2 = 6$（值为 8）；右孩子下标 $3 \times 2 + 1 = 7$（已超过当前堆大小 6，无右孩子）。
   • 比较左孩子 8 与当前值 10：$8 < 10$，将 10 与 8 交换。8 升至下标 3，10 最终落入下标 6。
4. 下标 6 此时已为叶子节点，下沉终止。故元素 10 最终所在的数组下标为 6。选 C。

7. 【答案】D

【解析】

• A 正确：希尔排序是分组插入，跨步长导致不稳定，平均复杂度打破了 $O(n^2)$。
• B 正确：归并排序采用分治法，合并过程严格遵循相对顺序，稳定性好，最好/最坏/平均均为 $O(n \log n)$。
• C 正确：冒泡排序每趟通过相邻交换，必定将当前未排序部分的最大（或最小）值“沉底”至最终归位处。
• D 错误：快速排序的空间复杂度由递归调用栈决定。在最好与平均情况下为 $O(\log n)$；但在最坏情况下（例如输入数组已经完全有序且每次选端点作为划分基准），递归树退化为深度为 $n$ 的单支链，空间复杂度为 $O(n)$。故选 D。

8. 【答案】A

【解析】 哈希表长度 $M = 7$，哈希函数 $H(key) = key \bmod 7$。 依次模拟插入过程：

1. 插入 16：$16 \bmod 7 = 2$。下标 2 为空，存入，比较 1 次。
2. 插入 28：$28 \bmod 7 = 0$。下标 0 为空，存入，比较 1 次。
3. 插入 4：$4 \bmod 7 = 4$。下标 4 为空，存入，比较 1 次。
4. 插入 15：$15 \bmod 7 = 1$。下标 1 为空，存入，比较 1 次。
5. 插入 39：$39 \bmod 7 = 4$。下标 4 已被占用（冲突！）：
   • 线性探测下一位 $(4+1) \bmod 7 = 5$；下标 5 为空，存入，共比较 2 次。

散列表最终分布： | 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | 关键字 | 28 | 15 | 16 | 空 | 4 | 39 | 空 | | 比较次数 | 1 | 1 | 1 | - | 1 | 2 | - |

查找成功的平均查找长度：

$$\text{ASL} = \frac{1 + 1 + 1 + 1 + 2}{5} = \frac{6}{5} = 1.2 $$

故选 A。

9. 【答案】B

【解析】 设节点总数为 $N$，叶子节点（度为 0）数为 $n_0$。

• 根据节点分类计数：$$N = n_0 + n_1 + n_2 + n_3 = n_0 + 4 + 2 + 1 = n_0 + 7 $$
• 根据树的边数（分支数）定理：任意树的边数等于 $N - 1$，且边数等于所有节点的度数之和：$$E = N - 1 = 0 \times n_0 + 1 \times 4 + 2 \times 2 + 3 \times 1 = 4 + 4 + 3 = 11 $$
• 由 $N - 1 = 11$ 解得 $N = 12$。
• 代入得：$n_0 + 7 = 12 \implies n_0 = 5$。故选 B。

10. 【答案】B

【解析】

• A 错误：$n$ 个顶点的无向连通树只有 $n-1$ 条边。
• B 正确：欧拉定理指明，一个无向连通图存在欧拉回路的充要条件是所有顶点的度数均为偶数。
• C 错误：若 DAG 存在互不约束的独立分支，则拓扑排序结果不唯一。
• D 错误：全源最短路中，Floyd 复杂度为 $O(V^3)$，代码极简且支持负权边；若图中含负权边，Dijkstra 甚至不能直接使用。故选 B。

---

第二部分：程序阅读题

阅读程序（一）

【程序意图解析】 本题实现的是 LeetCode 经典题“盛最多水的容器”（双指针贪心法）。 两条垂线构成的容器容积为 $\min(h[left], h[right]) \times (right - left)$。每次比较左右边界的高度，较低的那一侧不可能作为未来更大容器的短板（因为无论内部怎么缩短，宽度变小且高度受制于该短板），因此贪心地向内移动较短一侧的指针。

• 第 11 题【答案】正确（A）
  • 当 $n \le 1$ 时，初始 left = 0, right = n - 1 <= 0，循环条件 left < right 初始即为假，循环一次都不执行，直接输出初始化的 max_area = 0。
• 第 12 题【答案】错误（B）
  • 当 h[left] == h[right] 时，无论向右移动 left 还是向左移动 right，被舍弃的端点与区间内任意其他柱子组成的面积都必定严格小于当前面积。因此移动哪一侧都不会遗漏最优解，最终最大面积保持不变。
• 第 13 题【答案】B
  • 手推输入 1 8 6 2 5：
    1. left=0(1), right=4(5): 宽 4，高 1，面积 4。h[left] < h[right] $\to$ left++ 变为 1。
    2. left=1(8), right=4(5): 宽 3，高 5，面积 15。更新 max_area = 15。8 >= 5 $\to$ right-- 变为 3。
    3. left=1(8), right=3(2): 宽 2，高 2，面积 4。right-- 变为 2。
    4. left=1(8), right=2(6): 宽 1，高 6，面积 6。right-- 变为 1。
    5. left == right，循环结束。最终最大面积为 15。故选 B。
• 第 14 题【答案】A
  • 双指针从两端向中间移动，每一步至少移动一个指针，最多移动 $n-1$ 次，时间复杂度为严格的线性 $O(n)$。故选 A。

---

阅读程序（二）

【程序意图解析】 本程序采用分治法（归并排序）在 $O(n \log n)$ 时间内统计序列的逆序对总数。

• 第 15 题【答案】正确（A）
  • 标准归并排序在统计完跨区间逆序对后，将双指针合并后的临时数组 temp_arr 拷回原数组 a，最终整个数组被排为升序。
• 第 16 题【答案】错误（B）
  • 逆序对定义为 $a[i] > a[j]$（严格大于）。若序列中有重复值（例如 2 2）：
    • 原版 a[i] <= a[j] 会优先放左边的 2，不累加逆序对；
    • 改为 a[i] < a[j] 后，当遇到相等时会进入 else 分支，误将相等的元素统计为逆序对，导致输出结果偏大。
• 第 17 题【答案】B
  • 给定序列 5 2 6 3 1 4，手算每个元素后面比它小的元素个数：
    • 5 后面比它小的有：2, 3, 1, 4（共 4 个）
    • 2 后面比它小的有：1（共 1 个）
    • 6 后面比它小的有：3, 1, 4（共 3 个）
    • 3 后面比它小的有：1（共 1 个）
    • 1 后面比它小的有：无（共 0 个）
    • 4 后面比它小的有：无（共 0 个）
    • 逆序对总数 $= 4 + 1 + 3 + 1 + 0 + 0 = 9$。故选 B。
• 第 18 题【答案】B
  • 对于完全降序的序列，任意两个不同位置的数都构成一个逆序对，总数等于从 $n$ 个数中任取 2 个的组合数：$C_n^2 = \frac{n(n-1)}{2}$。故选 B。

---

阅读程序（三）

【程序意图解析】 本题实现的是求解最小生成树（MST）的 Kruskal 算法。将所有边按边权升序排序，借助带路径压缩的并查集判断端点连通性，贪心选取不构成环的最小边。

• 第 19 题【答案】正确（A）
  • 不连通的图无法选出 $n-1$ 条边使整张图连通，循环结束后 edge_count < n - 1，程序执行 else 分支输出 -1。
• 第 20 题【答案】错误（B）
  • 并查集的合并操作必须是将两个集合的根节点进行相连（parent_node[ru] = rv）。若直接写成 parent_node[edges[i].u] = edges[i].v，会严重破坏并查集的树形拓扑结构，导致判环失效。
• 第 21 题【答案】A
  • 边权排序结果为：
    1. 边 (1, 2)，权值 1 $\to$ 两端未连通，选中。累计权值 1，边数 1。
    2. 边 (1, 3)，权值 2 $\to$ 两端未连通，选中。累计权值 $1+2=3$，边数 2。
    3. 边 (3, 4)，权值 3 $\to$ 两端未连通，选中。累计权值 $3+3=6$，边数 $3 = n-1$。 已选满 $n-1=3$ 条边，触发 break 提前退出。总边权为 6。故选 A。
• 第 22 题【答案】C
  • Kruskal 算法的核心开销在于对 $m$ 条边进行快速排序，耗时为 $O(m \log m)$；后续并查集操作在阿克曼反函数 $\alpha(n)$ 级别，耗时极低。故选 C。

---

第三部分：完善程序题

23. 【答案】B

【解析】 初始化长度为 1 的上升子序列末尾最小值为原序列第一个元素，即 d[1] = a[1]。故选 B。

24. 【答案】A

【解析】 题目要求的是严格单调递增。当当前元素 $a[i]$ 严格大于当前已知最长序列的末尾元素（即 $a[i] > d[len]$）时，可以直接将最长长度加 1。若为大于等于则包含相同元素，破坏严格递增。故选 A。

25. 【答案】C

【解析】 当能够延长子序列时，最长长度应先自增 1，再将新末尾值记录在新的长度下标中，即 d[++len] = a[i]（等价于 len++; d[len] = a[i];）。A 选项后置自增会导致先赋值到旧 len 覆盖了原末尾值。故选 C。

26. 【答案】B

【解析】 我们需要在递增数组 d[1 \dots len] 中找到第一个大于等于 $a[i]$ 的位置。 二分判定逻辑：如果中间位置的值满足 d[mid] >= a[i]，说明 mid 可能是我们要找的合法替换位置，先记录 pos = mid，同时收缩右边界 R = mid - 1 尝试在左半段寻找更靠前的替换点；否则在右半段继续二分。故选 B。

27. 【答案】A

【解析】 二分结束后，pos 即为第一个大于等于 $a[i]$ 的元素所在下标。根据贪心优化法则，用更小的 $a[i]$ 替换原先较大的末尾值 d[pos]，能为后面接驳更长的上升子序列带来更大可能，因此执行 d[pos] = a[i]。故选 A。