全套试题标准参考答案与讲师深度剖析

快速查对速查表

逐题深度解析

第一部分：单项选择题

1. 【答案】A
   【解析】

   • $(11010110)_2 = 214$。十六进制 $(2E)_{16} = 2 \times 16 + 14 = 46 = (00101110)_2$。
   • 逐位按位与运算：
     11010110 & 00101110 = 00000110（十进制 6）。
   • 八进制 $(53)_8 = 5 \times 8 + 3 = 43 = (00101011)_2$。
   • 逐位按位或运算：
     00000110 | 00101011 = 00101111（十进制 47）。
   • 将 00101111 转换为十六进制：低 4 位 1111 为 F，高 4 位 0010 为 2，即 0x2F。选 A。

2. 【答案】A
   【解析】
   条件运算符优先级高于赋值运算符。

   • 条件 y > z 即 3 > 4 为假（false）；
   • 因此计算冒号右边的表达式 z *= 2。此时 z 自乘 2 变为 $8$，且该子表达式的返回值为 $8$；
   • 最后执行加等：x += 8，x 从 2 变为 $10$；
   • 变量 y 未被修改仍为 $3$。故最终结果为 x = 10, y = 3, z = 8。选 A。

3. 【答案】B
   【解析】
   从 6 男 4 女中选 4 人，要求至少 2 男且男女都有，按男生人数分类讨论：

   • 选 2 男 2 女：$C_6^2 \times C_4^2 = 15 \times 6 = 90$ 种；
   • 选 3 男 1 女：$C_6^3 \times C_4^1 = 20 \times 4 = 80$ 种；
   • （不能选 4 男，因为要求有女生；不能选 1 男，因为要求至少 2 男）。
     总方案数为 $90 + 80 = 170$ 种。选 B。

4. 【答案】A
   【解析】
   格雷码转二进制公式为：最高位 $B_3 = G_3$，后续位 $B_i = B_{i+1} \oplus G_i$。
   已知 $G = 1101$：

   • $B_3 = G_3 = 1$
   • $B_2 = B_3 \oplus G_2 = 1 \oplus 1 = 0$
   • $B_1 = B_2 \oplus G_1 = 0 \oplus 0 = 0$
   • $B_0 = B_1 \oplus G_0 = 0 \oplus 1 = 1$
     得到二进制数为 1001（验算：1001 ^ (1001 >> 1) = 1001 ^ 0100 = 1101）。选 A。

5. 【答案】B
   【解析】
   头插法标准步骤：首先让待插入节点 p 的指针指向原本的头节点（p->next = head;），然后更新头节点指针为 p（head = p;）。若颠倒则导致后继丢失。选 B。

6. 【答案】C
   【解析】
   大根堆数组下标从 1 开始，依次插入模拟：

   1. 插入 18 $\rightarrow [18]$
   2. 插入 7 $\rightarrow [18, 7]$
   3. 插入 25 $\rightarrow 25 > 18$，上浮：$[25, 7, 18]$
   4. 插入 12 $\rightarrow 12 > 7$，上浮：$[25, 12, 18, 7]$
   5. 插入 33 $\rightarrow 33 > 12$，与 12 换，再 $33 > 25$，上浮到根：$[33, 25, 18, 7, 12]$
   6. 插入 40 $\rightarrow$ 插入下标 6（18 的左孩子），$40 > 18$，上浮与 18 交换，接着 $40 > 33$，上浮到根与 33 交换！此时堆数组为：
      下标 1：40
      下标 2：25
      下标 3：33
      下标 4：7
      下标 5：12
      下标 6：18
   7. 插入 20 $\rightarrow$ 插入下标 7（33 的右孩子），$20 < 33$，不上浮。
      因此数组下标 3 的元素严格为 33。对应选项 C。

7. 【答案】D
   【解析】
   带提前退出判断标志位（如 bool swapped）的优化冒泡排序，在数组本身完全有序的“最好情况”下，仅需扫描一趟进行 $n-1$ 次比较即可发现未发生交换并直接退出，时间复杂度为 $O(n)$。因此“无论在最好还是最坏情况下比较次数均等于 $\frac{n(n-1)}{2}$”是错误的。选 D。

8. 【答案】D
   【解析】
   哈希表长 13，$H(x) = x \bmod 13$。

   • 插入 26：$26 \bmod 13 = 0$，占位置 0；
   • 插入 39：$39 \bmod 13 = 0$，冲突。$0 + 1^2 = 1$，占位置 1；
   • 插入 52：$52 \bmod 13 = 0$，冲突。
     探测 1：$0 + 1^2 = 1$，已被占用；
     探测 2：$(0 - 1^2 + 13) \bmod 13 = 12$ 空闲！
     故 52 被存放在下标 12。选 D。

9. 【答案】A
   【解析】

   • $n$ 个顶点的无向连通图，最少需要 $n-1$ 条边以保证连通；一旦边数达到 $n$ 条或更多，必定会产生回路（环），A 正确；
   • $n$ 点 $n-1$ 边的图若不连通则不是树，B 错；
   • 生成树的边数恒等于 $n-1$，C 错；
   • 根据握手定理，奇数度节点的个数必定是偶数，D 错。

10. 【答案】C
    【解析】
    Floyd-Warshall 算法的底层设计思想是动态规划（DP），其状态转移方程为 $dp[k][i][j] = \min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])$，不属于贪心算法。选 C。

第二部分：程序阅读题

（一）区间选点覆盖

• 第 11 题（A / 对）：这是按照区间右端点排序、贪心选取右端点的标准区间选点模板，说法正确。
• 第 12 题（B / 错）：若按左端点排序，当大区间包含小区间（如 [1, 100] 与 [2, 3]）时，贪心会选错点，无法得到最优解，说法错误。
• 第 13 题（B）：按右端点排序后：
  1. [2, 4]：选点 4；
  2. [1, 5]：已包含 4；
  3. [3, 6]：已包含 4；
  4. [5, 8]：不包含 4，新选点 8；
  5. [7, 9]：已包含 8。
     最少只需选 2 个点（点 4 和点 8）。选 B（2）。
• 第 14 题（A）：所有区间右端点均为 10 且互相重叠，第一个区间选中 10 后，后续所有区间左端点 $\le 10$，全部被覆盖，输出 1。选 A。

（二）快速选择第 K 大

• 第 15 题（A / 对）：快速选择每次只递归进入包含第 $k$ 小元素的一侧分支，递归规模 $n + \frac{n}{2} + \frac{n}{4} + \dots = O(n)$，平均时间复杂度为 $O(n)$。
• 第 16 题（B / 错）：若基准每次都极度不平衡（如退化为单边），最坏时间复杂度会退化为 $O(n^2)$。
• 第 17 题（B）：排序后数组为 3, 4, 5, 7, 12, 19, 26，第 4 小的元素是 7。选 B。
• 第 18 题（B）：元素全相等时，两个内层 while 条件由于使用严格不等号 < 和 > 会立刻停住，外层不断交换并使 $i++, j--$，循环次数约为 $n/2$ 次。选 B。

（三）Prim 最小生成树

• 第 19 题（A / 对）：邻接矩阵版 Prim 算法复杂度与边数无关，固定为 $O(n^2)$，特别适合稠密图。
• 第 20 题（B / 错）：min_dist[u] + graph[u][v] 是 Dijkstra 单源最短路径算法的松弛条件，绝非 Prim 算法的求树边条件，改动后彻底错误。
• 第 21 题（A）：逐步加入边：(2, 3, 1)，(1, 2, 2)，(3, 4, 2)，总权值为 $1 + 2 + 2 = 5$。选 A。
• 第 22 题（D）：点 1,2 与点 3,4 分立在两个不连通的子图中，Prim 算法检测到不连通返回 -1。选 D。

第三部分：完善程序题（并查集）

• 第 23 题（A）：标准的路径压缩递归实现：parent_node[x] = find(parent_node[x])。选 A。
• 第 24 题（A）：小树合并到大树 rootX 后，大树的大小应累加小树的大小：set_size[rootX] += set_size[rootY]。选 A。
• 第 25 题（B）：成功合并两个独立的连通块后，连通块总数减少 1：components--。选 B。
• 第 26 题（A）：初始时每个节点独立构成一个集合，其大小为 1：set_size[i] = 1。选 A。
• 第 27 题（B）：判断连通性必须通过 find 函数找到各自的代表元素（根节点）进行比较：find(u) == find(v)。选 B。