tobyforever LV 6 SU @ 2026-10-22 11:47:21

给我简单讲解排序算法核心知识点以及快速记忆方法：稳定性（快排/堆排/选择不稳定）、时空复杂度（最坏/最好/平均）、开放寻址与链地址法手算。

初赛（CSP-J/S 与海中自招）中，排序算法和哈希冲突是年年必出选择题的高频阵地。掌握以下体系化的口诀、对照表和手算模板，可在考场上直接秒杀。

第一部分：排序算法核心记忆法

一、稳定性口诀（秒杀判断题）

稳定性的定义：若序列中存在两个相同元素 $A_1 = A_2$ ，排序前 $A_1$ 在 $A_2$ 前面；若排序后 $A_1$ 必定依然在 $A_2$ 前面，则该排序算法是稳定的。

终极记忆口诀：
$$\text{“考前}\mathbf{快}\mathbf{选}\mathbf{堆}\mathbf{希}\text{（快选堆歇），情绪}\mathbf{不稳定}\text{”} $$
- 快：快速排序
- 选：简单选择排序
- 堆：堆排序
- 希：希尔排序（Shell Sort）
考场规则：除了“快、选、堆、希”这 4 种跨步长/跨区间交换的算法不稳定，其余所有常见排序（冒泡、直接插入、归并、基数排序、计数排序）全部都是稳定的！

一句话直击为什么不稳定（反例）：

选择排序：序列 [5, 5*, 2] $\to$ 找到最小值 2，与第 1 个 5 交换 $\to$ [2, 5*, 5]，相对次序颠倒。
快速排序：双指针远距离交换，若遇到相同值元素极易被越过。
堆排序：建立大根堆/小根堆时，父子节点跨层交换调整破坏次序。
希尔排序：按步长分组，相同的两个元素被分到不同组别独立插入。

二、时空复杂度终极对照表

排序算法	最好时间	平均时间	最坏时间	辅助空间	稳定性	考场高频命题特征
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	优化版带 `flag` 标记时，原本有序只需扫一趟 $O(n)$
直接插入	$O(n)$				稳定	基本有序时效率最高（接近 $O(n)$ ）
简单选择	$O(n^2)$				不稳定	无论原数组怎样，都要固定比满 $\frac{n(n-1)}{2}$ 次
希尔排序	$O(n)$	$O(n^{1.3})$				突破 $O(n^2)$ 的第一批算法，步长递减插入
快速排序	$O(n\log n)$		$\mathbf{O(n^2)}$	$O(\log n) \sim O(n)$		原数组已完全有序/逆序且基准选端点时最坏退化为 $O(n^2)$ ；空间为递归栈
堆排序	$\mathbf{O(n\log n)}$			$\mathbf{O(1)}$		表现最稳定（无论好坏都是 $n\log n$ ），且空间只需 $O(1)$
归并排序	$O(n\log n)$			$\mathbf{O(n)}$	稳定	比较类排序中唯一时空平稳且稳定的算法，代价是需要 $O(n)$ 辅助数组
基数排序	$O(d(n+r))$			$O(n+r)$	稳定	非基于比较的排序； $d$ 为位数， $r$ 为基数（如10进制 $r=10$ ）

第二部分：哈希冲突手算（拉链法 vs 开放寻址）

设待插入关键字序列为：{19, 14, 23, 1, 68}，哈希表长度 $M = 11$ ，哈希函数为 $H(key) = key \bmod 11$ 。

先算各元素初始哈希地址：

$19 \bmod 11 = 8$
$14 \bmod 11 = 3$
$23 \bmod 11 = 1$
$1 \bmod 11 = 1$ （冲突）
$68 \bmod 11 = 2$

方法一：链地址法（拉链法 / 链表法）

每个哈希桶维护一个单链表（新节点通常插在表头或表尾，初赛默认按插入次序挂链）：

地址 0: 空
地址 1: -> 23 -> 1
地址 2: -> 68
地址 3: -> 14
地址 4 ~ 7: 空
地址 8: -> 19
地址 9 ~ 10: 空

考题核心计算：平均查找长度（ASL）

成功查找的 ASL（ASL_succ）：
- 查 23：比较 1 次（链表第 1 个）
- 查 1：比较 2 次（链表第 2 个）
- 查 68：比较 1 次
- 查 14：比较 1 次
- 查 19：比较 1 次
$$\text{ASL}_{\text{succ}} = \frac{1 + 2 + 1 + 1 + 1}{5} = \frac{6}{5} = 1.2 $$
失败查找的 ASL（ASL_unsucc）：
（指查找一个不存在的数，哈希定位到该地址后需要比较到空指针的次数，分母为哈希表长 $M$ ）
- 桶 1 有 2 个节点，比较 2 次后发现到链尾 NULL；
- 桶 2、3、8 各有 1 个节点，各比较 1 次；其余 7 个桶为空（比较 0 次）：
$$\text{ASL}_{\text{unsucc}} = \frac{2 + 1 + 1 + 1 + 0\times 7}{11} = \frac{5}{11} $$

方法二：开放寻址法（数组内挪位）

所有元素都存放在同一个大小为 $M$ 的连续数组里。通用探测公式：

H_i = (H(key) + d_i) \bmod M

1. 线性探测法（Linear Probing）

步长 $d_i = 1, 2, 3, 4, \dots$ （冲突了就挨个看右边下一个位置，环形回绕）：

存 19： $H=8$ 空闲，放入桶 8（比较 1 次）；
存 14： $H=3$ 空闲，放入桶 3（比较 1 次）；
存 23： $H=1$ 空闲，放入桶 1（比较 1 次）；
存 1： $H=1$ $H = 1$ 冲突！
- 尝试 $(1+1) \bmod 11 = 2$ ，空闲，放入桶 2（比较 2 次）；
存 68： $H=2$ $H = 2$ 冲突（被 1 占了）！
- 尝试 $(2+1) \bmod 11 = 3$ ，冲突（被 14 占了）；
- 尝试 $(2+2) \bmod 11 = 4$ ，空闲，放入桶 4（比较 3 次）。

最终散列表分布： | 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | 值 | - | 23 | 1 | 14 | 68 | - | - | - | 19 | - | - | | 比较次数 | - | 1 | 2 | 1 | 3 | - | - | - | 1 | - | - |
查找成功的 ASL：
$$\text{ASL} = \frac{1 + 2 + 1 + 3 + 1}{5} = \frac{8}{5} = 1.6 $$

优缺点考点：线性探测容易发生聚集（堆积）现象（Cluster），即连续一段地址被占满后，后续冲突的探测链越来越长，严重拉低性能。

2. 二次探测法（平方探测法，Quadratic Probing）

步长序列： $d_i = +1^2, -1^2, +2^2, -2^2, +3^2, -3^2, \dots$ （即 $+1, -1, +4, -4, +9, -9, \dots$ ）

注意负数取模的手算技巧： $(-k) \bmod M = (M - (k \bmod M)) \bmod M$ 。
例如在 $M=11$ 时： $(2 - 1^2) \bmod 11 = 1$ ； $(2 - 2^2) \bmod 11 = (2 - 4) = -2 \equiv 9$ 。

二次探测核心优点：能有效缓解线性探测的聚集堆积问题，散布更均匀。

0

tobyforever LV 6 SU @ 2026-10-22 11:44:07

给我简单讲解：格雷码

格雷码（Gray Code）是初赛（CSP-J/S 及海中自招）中高频必考的编码知识点（CSP-S 2019 Day 1 第 1 题就直接考了格雷码生成）。

用最通俗易懂的方式，掌握以下 3 个核心 即可完全吃透：

一、什么是格雷码？为什么需要它？

普通二进制的缺点：
从 $3$ 变到 $4$ ：011 $\to$ 100，3 个 bit 同时翻转。在真实的硬件传感器或芯片电路中，多位同时跳变极易因为微小的纳秒级延迟产生毛刺干扰和读数错误。
格雷码的本质：
任意相邻的两个数，二进制表示中只有 1 位（bit）不同。
（首尾相接也是只差 1 位，因此也是一种循环码）。

3 位格雷码与普通二进制对照：

十进制	普通二进制	格雷码	变化位（与上一行对比）
0	000	000	-
1	001	001	最低位变 1
2	010	011	中间位变 1
3	011	010	最低位变 0
4	100	110	最高位变 1
5	101	111	最低位变 1
6	110	101	中间位变 0
7	111	100	最低位变 0

二、考点 1：二进制转格雷码（秒杀公式）

如果你已知十进制或二进制数 $B$ ，求对应的格雷码 $G$ ：

G = B \oplus (B >> 1)

即：原数异或上原数右移 1 位。

手算口诀：

最高位不变： $g_n = b_n$ ；
其余每位等于原码该位与高一位“异或”： $g_i = b_{i+1} \oplus b_i$ 。

实战演练：把二进制 1011 转换为格雷码

  B      =  1  0  1  1
  B >> 1 =  0  1  0  1   (右移补0)
----------------------- (按位异或)
  G      =  1  1  1  0

结果就是 1110，考场上 3 秒得出！

三、考点 2：格雷码还原回二进制（解码）

已知格雷码 $G$ ，求它代表的原二进制 $B$ 。

手算口诀（从左往右前缀异或累积）：

最高位直接抄下来： $b_n = g_n$ ；
往后每一位，用“刚算出的上一位二进制”与“当前格雷码位”做异或： $b_i = b_{i+1} \oplus g_i$

实战演练：把格雷码 1110 还原为普通二进制
- 最高位： $b_3 = g_3 = \mathbf{1}$
- 次高位： $b_2 = b_3 \oplus g_2 = 1 \oplus 1 = \mathbf{0}$
- 第三位： $b_1 = b_2 \oplus g_1 = 0 \oplus 1 = \mathbf{1}$
- 最低位： $b_0 = b_1 \oplus g_0 = 1 \oplus 0 = \mathbf{1}$
- 拼起来得到二进制 1011（还原正确）。

四、考点 3：镜像构造法（递归生成）

$n$ 位格雷码可以由 $n-1$ 位格雷码**“镜像翻转”**推出来：

1 位格雷码：0, 1
2 位格雷码：
- 前半部分：在 1 位码前加 0 $\to$ 00, 01
- 后半部分：把 1 位码倒序并在前面加 1 $\to$ 11, 10
3 位格雷码：
- 前半部分（加0）：000, 001, 011, 010
- 后半部分（倒序加1）：110, 111, 101, 100

考题常见问法（如“求 $n$ 位格雷码中排名第 $k$ 个的编码”）：

若 $k < 2^{n-1}$ ，首位填 0，继续在 $n-1$ 位中找第 $k$ 个；

若 $k \ge 2^{n-1}$ ，首位填 1，接下来在 $n-1$ 位中找第 $(2^n - 1 - k)$ 个（倒序找）。

考场速记卡

// 1. 二进制转格雷码 (一行搞定)
unsigned int binaryToGray(unsigned int n) {
    return n ^ (n >> 1);
}

// 2. 格雷码转二进制 (从高到低异或累加)
unsigned int grayToBinary(unsigned int g) {
    unsigned int b = 0;
    for (; g > 0; g >>= 1) {
        b ^= g;
    }
    return b;
}

0

tobyforever LV 6 SU @ 2026-10-22 11:40:48

给我简单讲解：哈希冲突（Hash Collision）的开地址法（线性探测与二次探测）

在 CSP-J/S 初赛和各省名校自招中，“哈希冲突（Hash Collision）的开地址法（线性探测与二次探测）” 是每年必考、且只要考就属于 100% 拿分的送分题。

这类题目不需要写代码，关键在于搞懂探测公式，并在草稿纸上模拟画表格。

一、核心背景：什么是哈希冲突？

假设我们有一个长度为 $M$ 的哈希表（数组下标 $0 \sim M-1$ ）。
散列函数通常是模运算： $H(key) = key \bmod M$ 。
冲突：两个不同的数算出来的下标一样（比如 $M=11$ ， $key_1=1$ 和 $key_2=12$ ，因为 $1 \bmod 11 = 12 \bmod 11 = 1$ ，它们都想挤进下标 1 的位置）。
开地址法（Open Addressing）：既然原本的家被占了，就按照某种“既定规则”在数组里找下一个空位置。

二、线性探测法（Linear Probing）——“挨个往后挪”

1. 核心公式

如果算出来的初始位置 $H_0 = H(key)$ 已经有人了，就依次往后看：

$$H_i = (H(key) + i) \bmod M \quad (i = 1, 2, 3, \dots) $$

通俗说就是：+1，+2，+3，+4……挨个往后找，走到数组末尾就绕回开头（取模）。

2. 手推实战演练

题目：散列表长 $M = 11$ ， $H(key) = key \bmod 11$ 。采用线性探测法，依次插入 {12, 23, 34}。求 34 最终落在哪个位置？

我们画一个下标 $0 \sim 10$ 的表格：

插入 12： $12 \bmod 11 = 1$ $12 mod 11 = 1$ 。下标 1 是空的，直接放入：
- 表格：位置 1: 12
插入 23： $23 \bmod 11 = 1$ $23 mod 11 = 1$ 。发现下标 1 已经被 12 占了（冲突）！
- 启动线性探测：试探 $(1 + 1) \bmod 11 = 2$ 。
- 下标 2 是空的，放入：
- 表格：位置 1: 12，位置 2: 23
插入 34： $34 \bmod 11 = 1$ $34 mod 11 = 1$ 。下标 1 冲突！
- 试探 $(1 + 1) \bmod 11 = 2$ ，也被 23 占了，继续冲突！
- 试探 $(1 + 2) \bmod 11 = 3$ ，下标 3 是空的，成功放入！
- 结果：34 最终存放在下标 3。

优缺点常考点：容易产生**“聚集/堆积（Clustering）”**现象——连续一长串都被占满，后面的数冲突越来越频繁。

三、二次探测法（Quadratic Probing）——“跳跃着找”

为了解决线性探测“容易扎堆”的问题，二次探测改成了步长平方跳跃（有的教材也叫平方法）。

1. 核心公式

如果 $H(key)$ 冲突，探测序列为：

$$H_i = (H(key) \pm i^2) \bmod M \quad (i = 1, 2, 3, \dots) $$

即偏移量依次为：

$$+1^2, \ -1^2, \ +2^2, \ -2^2, \ +3^2, \ -3^2, \dots $$

也就是：

+1, \ -1, \ +4, \ -4, \ +9, \ -9, \dots

⚠️ 草稿纸算负数取模秘诀（极其重要，考场避坑点）：如果算出来是负数，直接加上表长 $M$ 即可！例如： $(0 - 1) \bmod 11 = -1 \rightarrow -1 + 11 = 10$ 。

2. 手推实战演练

题目：散列表长 $M = 11$ ， $H(key) = key \bmod 11$ 。采用二次探测法，依次插入 {12, 23, 34}。求 34 最终落在哪个位置？

插入 12： $12 \bmod 11 = 1$ ，下标 1 空闲，存入 1。
插入 23： $23 \bmod 11 = 1$ $23 mod 11 = 1$ ，冲突！
- 探测第一步（ $+1^2$ ）： $(1 + 1) \bmod 11 = 2$ ，下标 2 空闲，存入 2。
插入 34： $34 \bmod 11 = 1$ $34 mod 11 = 1$ ，冲突！
- 探测第一步（ $+1^2$ ）： $(1 + 1) \bmod 11 = 2$ ，位置 2 已被 23 占领，继续冲突！
- 探测第二步（ $-1^2$ ）： $(1 - 1) \bmod 11 = 0$ ！
- 下标 0 是空的，成功放入！
- 结果：34 最终存放在下标 0（注意与线性探测得到的结果不同！）。

四、考场应试“三步做题法”

初赛或自招考场上遇到这类选择题，不要在脑子里凭空想，按以下 3 步做：

画尺子：草稿纸画一条横线，标出下标 $0 \sim M-1$ 。
算模数：把每一个给出的数先模上 $M$ ，写在草稿纸上。
按顺序落子：
- 没冲突直接填进去；
- 遇到冲突看清题干：
  - 若是线性：+1, +2, +3... 顺延往后走；
  - 若是二次：先试 +1，不行试 -1，再不行试 +4，再不行试 -4……（负数直接加模数 $M$ ）。

0

tobyforever LV 6 SU @ 2026-10-22 11:35:32

考试范围与备考建议

从题目结构和考点设置来看，这场自主招生考试本质上就是一套高密度的“CSP-J/S 初赛笔试精简版”。题型与全国青少年信息学奥林匹克联赛初赛完全接轨（单选、阅读程序、完善程序），且由于考试时间仅有 1 小时，考查重点在于对经典算法模板的快速理解、手推代码运行过程以及扎实的数据结构基础。

一、考点难度与 GESP / CSP 对应级别映射表

题型	具体考点	GESP 对应级别	CSP 对应级别	核心备考要求与踩坑点
单项选择	进制转换、运算符优先级	GESP 1-3 级	CSP-J 初赛基础题	基础语法送分项，熟练掌握位运算、逻辑与算术运算符结合顺序，确保 100% 准确率。
	排列组合	GESP 5-6 级	CSP-J 初赛数学基础	加乘原理、排列数与组合数计算、隔板法与容斥原理基础。
	格雷码 (Gray Code)	GESP 6-7 级	CSP-S 初赛常考点	掌握二进制与格雷码互转公式（`G = B ^ (B >> 1)`）及递归/对称构造规律。
	链表、优先队列 (堆)	GESP 5-6 级	CSP-J / CSP-S 初赛	链表指针操作、堆的完全二叉树数组表示、`priority_queue` 底层调整时间复杂度。
	排序算法对比、哈希冲突	GESP 5-6 级	CSP-J 初赛常考点	稳定性（快排/堆排/选择不稳定）、时空复杂度（最坏/最好/平均）、开放寻址与链地址法手算。
阅读程序	贪心枚举	GESP 4-5 级	CSP-J 阅读程序	模拟小规模数据运行，推断程序在选局部最优解还是做区间覆盖/背包变体。
	归并排序 (Merge Sort)	GESP 5-6 级	CSP-J/S 核心算法	递归树分析、分治手推、双指针合并过程，注意逆序对计数变体。
	最小生成树 (MST)	GESP 7-8 级	CSP-S 核心图论	Kruskal（结合并查集）与 Prim 算法的手推执行顺序、边权与生成树权值计算。
完善程序	并查集 (Disjoint Set)	GESP 7 级	CSP-J/S 核心数据结构	路径压缩、按秩合并模板填空，查找根节点循环/递归写法。
完善程序	最长上升子序列 (LIS)	GESP 6-7 级	CSP-J/S 经典动态规划	掌握 $O(n^2)$ 传统 DP 转移与 $O(n \log n)$ 贪心+二分（`lower_bound`）两种模板填空。

综合定级结论：

整体难度定位：CSP-J 提高档至 CSP-S 入门档（相当于 GESP 6-7 级水准）。
你当前的差距：你目前在 GESP 4-6 级，已具备基础语法、简单搜索与基础排序思维，主要薄弱点集中在图论算法（最小生成树）、高阶数据结构（并查集/堆/手写链表）及动态规划（LIS）的手推与笔试填空。

二、突击备考规划（阶梯突击计划表）

由于目标是 9 年级下学期开学考试，且属于突击性质，策略应为：“算法模板吃透 + 历年初赛手推技巧训练 + 针对性笔试限时刷题”，无需花海量时间在 Codeforces/洛谷写大黑题，重点吃透笔试出题规律。

阶段	周期	核心突击目标	每日/每周任务拆解	检验标准
第一阶段：补齐盲区知识点	第 1 ~ 3 周	攻克 MST、并查集、LIS、格雷码与优先队列底层	1. 手写并默写 Kruskal、Prim、并查集（路径压缩）、LIS（两类写法）代码模板。

2. 学习格雷码与二进制变换公式、链表指针手写实现。

2. 重点训练根据变量名、边界条件反推算法意图的能力。

2. 针对错题复盘“手推越界”、“算错边界条件”等非知识性失分。 | 模拟考得分稳定在 42/50 分以上。 |

三、考场应试与拿分关键点

答题时间分配策略（满分 50 分，限时 60 分钟）：

单选题（10 题）：控制在 12 分钟内。进制、优先级、排序性质直接秒杀；排列组合草稿纸仔细计算。
完善程序（1 题）：控制在 10 分钟内。因为已经明示考查并查集或 LIS，直接对齐脑海中的经典模板，比对变量名填空即可，性价比最高。
阅读程序（3 题）：留足 30 分钟。每题 10 分钟，先读懂大意（分治、贪心还是图论算法），用题目给的小样例走一遍流程，再去勾选判断与选择。
检查与复核：剩余 8 分钟。重点核对单选计算题与完型填空的数组下标（是 1 还是 0 起始）。

重点突破资料推荐：

直接刷 2020~2024 年 CSP-J/S 第一轮（初赛）真题，重点挑阅读程序和完善程序中的经典算法部分做，精准覆盖上述所有考点。

0

tobyforever LV 6 SU @ 2026-10-22 10:51:37

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

快速查对速查表

题号	1	2	3	4	5	6	7	8	9	10
单选	A	B		A	B			C	A	D

题号	11(判)	12(判)	13(选)	14(选)	15(判)	16(判)	17(选)	18(选)	19(判)	20(判)	21(选)	22(选)
阅读	B(错)	A(对)	A	C	A(对)	B(错)	C	A	A(对)		A	B

题号	23(1)	24(2)	25(3)	26(4)	27(5)
完型	A	C	B	A	C

逐题深度解析

第一部分：单项选择题

【答案】A
【解析】
- $(375)_8 = 3 \times 64 + 7 \times 8 + 5 = 192 + 56 + 5 = 253$。写成二进制为 11111101。
- $(1A)_{16} = 1 \times 16 + 10 = 26$ 。写成二进制为 00011010。
- 按位异或（相同为 0，不同为 1）：
  11111101 ^ 00011010 = 11100111。对应选项 A。
【答案】B
【解析】
C++ 运算符优先级顺序为：算术运算符（* 高于 +、-） > 关系运算符（>） > 相等运算符（!=） > 逻辑与运算符（&&）。
- 先算 b * c = 20，a + 20 = 23；
- 23 > b（即 23 > 4）为真（true）；
- 右边 c - a = 2，2 != 4 为真（true）；
- 最后计算逻辑与：true && true 结果为 1。故选 B。
【答案】B
【解析】
按除以 3 的余数分类：
- 余 0 集合 $A = \{3, 6, 9\}$ （共 3 个）
- 余 1 集合 $B = \{1, 4, 7\}$ （共 3 个）
- 余 2 集合 $C = \{2, 5, 8\}$ （共 3 个）
  选出 3 个数的和是 3 的倍数，有两种情况：
- 情况 1：3 个数来自同一个集合： $C_3^3 + C_3^3 + C_3^3 = 1 + 1 + 1 = 3$ 种；
- 情况 2：3 个数分别来自 3 个不同集合：$C_3^1 \times C_3^1 \times C_3^1 = 3 \times 3 \times 3 = 27$ 种。
  总方案数为 $3 + 27 = 30$ 种。选 B。
【答案】A
【解析】
十进制 11 的二进制为 $B = (1011)_2$ 。
右移 1 位得 $B \gg 1 = (0101)_2$ 。
按位异或：
1011 $\oplus$ 0101 = 1110。选 A。
【答案】B
【解析】
在单链表中插入节点，必须先将新节点 s 的后继指向 p 原来的后继（s->next = p->next;），然后再将 p 的后继修改为 s（p->next = s;）。若先执行 p->next = s;，原后续节点的地址就会丢失造成断链。选 B。
【答案】B
【解析】
已有 15 个节点（此时刚好是一棵高为 4 的满二叉树，节点数 $2^4 - 1 = 15$ ）。新插入第 16 个元素放入完全二叉树的第 5 层。新节点向上调整（Heapify Up）最多沿着树枝一路交换到树根，交换的次数等于节点的深度，即 $\log_2(16) = 4$ 次。选 B。
【答案】B
【解析】
- 冒泡、插入、归并都是稳定排序，B 正确；
- 快速排序在最坏情况下退化为 $O(n^2)$ ，且是不稳定排序，A、C 错误；
- 选择排序跨距离交换相同元素，是不稳定的，D 错误。
【答案】C
【解析】
哈希表长度为 11， $H(x) = x \bmod 11$ ：
- 插入 12： $12 \bmod 11 = 1$ ，存入下标 1；
- 插入 23： $23 \bmod 11 = 1$ ，发生冲突，线性探测到下标 2，存入下标 2；
- 插入 34： $34 \bmod 11 = 1$ ，发生冲突，探测下标 2 仍被占用，继续线性探测到下标 3 空闲，最终存入下标 3。故选 C。
【答案】A
【解析】
无向连通图是树的充分必要条件是：连通且恰好包含 $n-1$ 条边（少一条不连通，多一条必有环）。选 A。
【答案】D
【解析】
0-1 背包问题具有后效性，单纯按照单位重量价值最大贪心无法保证全局最优，必须采用动态规划求解；而分数背包问题才能用贪心。选 D。

第二部分：程序阅读题

（一）区间合并

第 11 题（B / 错）：若按右端点排序，当区间包含时（如 [1, 10] 与 [2, 3]），按右端点排会导致 [2, 3] 排在前面，算法无法单调合并重叠区间，结果会错误。
第 12 题（A / 对）：遍历是一次 $O(n)$ ，瓶颈在于前面的 std::sort，时间复杂度为 $O(n \log n)$ 。
第 13 题（A）：[1, 3] 和 [2, 6] 合并为 [1, 6]（长 5）；[8, 10]（长 2）；[15, 18]（长 3）。总长度为 $5 + 2 + 3 = 10$ 。选 A。
第 14 题（C）：所有区间完全重合，合并后为单个区间 [1, 10]，长度为 $10 - 1 = 9$ 。选 C。

（二）归并求逆序对

第 15 题（A / 对）：当左半段指针 $i$ 处的元素大于右半段 $j$ 时，由于左半段已升序排列，说明从 $i$ 到 $mid$ 的所有元素都大于 $a[j]$ ，共有 $mid - i + 1$ 个逆序对，完全正确。
第 16 题（B / 错）：由于右边已经归并了一部分， $r - j + 1$ 无法正确反映逆序对数量，统计逻辑彻底错误。
第 17 题（C）：长度为 5 的完全逆序数组，逆序对数为 $\frac{5 \times 4}{2} = 10$ 。选 C。
第 18 题（A）：完全升序数组没有任何逆序对，输出为 0。选 A。

（三）Kruskal 最小生成树

第 19 题（A / 对）：find_root 递归时执行了 parent_node[x] = find_root(...)，是标准的路径压缩，平摊复杂度接近 $O(1)$ 。
第 20 题（A / 对）：若图不连通，循环结束时加入的边数 edge_count < n - 1，程序进入 else 分支打印 -1。
第 21 题（A）：
边按权值升序：
1. (1, 2, 1)：选入，权值累加 1
2. (2, 3, 2)：选入，权值累加 2
3. (3, 4, 3)：选入，权值累加 3（此时已选 3 条边， $n-1=3$ ，满足条件终止）
  最小生成树总权值为 $1 + 2 + 3 = 6$ 。选 A。
第 22 题（B）：Kruskal 算法的瓶颈在于对 $m$ 条边排序，时间复杂度为 $O(m \log m)$ 。选 B。

第三部分：完善程序题（LIS 贪心+二分）

第 23 题（A）：在二分查找第一个大于等于 target 的位置时，当 d[mid] >= target，说明 mid 是一个合法候选，但左边可能还有更小的合法位置，因此记录 ans = mid 后收缩右边界：r = mid - 1。选 A。
第 24 题（C）：当 d[mid] < target 时，mid 处过小不满足要求，必须向右寻找，故 l = mid + 1。选 C。
第 25 题（B）：求严格单调递增子序列，新元素只有严格大于当前最长序列的末尾时才能延长长度，故条件为 a[i] > d[len]。选 B。
第 26 题（A）：长度延长至 len 后，该长度子序列的最小末尾即为当前新加入的元素 a[i]，故 d[len] = a[i]。选 A。
第 27 题（C）：二分找到第一个 $\ge a[i]$ 的位置 pos 后，将该位置的末尾值替换为更小的 a[i]，为后续元素留下更充裕的上升空间，故 d[pos] = a[i]。选 C。

5 条题解

给我简单讲解排序算法核心知识点以及快速记忆方法：稳定性（快排/堆排/选择不稳定）、时空复杂度（最坏/最好/平均）、开放寻址与链地址法手算。

第一部分：排序算法核心记忆法

一、稳定性口诀（秒杀判断题）

一句话直击为什么不稳定（反例）：

二、时空复杂度终极对照表

第二部分：哈希冲突手算（拉链法 vs 开放寻址）

方法一：链地址法（拉链法 / 链表法）

考题核心计算：平均查找长度（ASL）

方法二：开放寻址法（数组内挪位）

1. 线性探测法（Linear Probing）

2. 二次探测法（平方探测法，Quadratic Probing）

给我简单讲解：格雷码

一、什么是格雷码？为什么需要它？

二、考点 1：二进制转格雷码（秒杀公式）

手算口诀：

三、考点 2：格雷码还原回二进制（解码）

手算口诀（从左往右前缀异或累积）：

四、考点 3：镜像构造法（递归生成）

考场速记卡

给我简单讲解：哈希冲突（Hash Collision）的开地址法（线性探测与二次探测）

一、 核心背景：什么是哈希冲突？

二、 线性探测法（Linear Probing）——“挨个往后挪”

1. 核心公式

2. 手推实战演练

三、 二次探测法（Quadratic Probing）——“跳跃着找”

1. 核心公式

2. 手推实战演练

四、 考场应试“三步做题法”

考试范围与备考建议

一、 考点难度与 GESP / CSP 对应级别映射表

二、 突击备考规划（阶梯突击计划表）

三、 考场应试与拿分关键点

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

快速查对速查表

逐题深度解析

第一部分：单项选择题

第二部分：程序阅读题

（一）区间合并

（二）归并求逆序对

（三）Kruskal 最小生成树

第三部分：完善程序题（LIS 贪心+二分）

海中自招信息学模拟考试1

信息

状态

开发

支持

关于

还没有账户？

登录

一、核心背景：什么是哈希冲突？

二、线性探测法（Linear Probing）——“挨个往后挪”

三、二次探测法（Quadratic Probing）——“跳跃着找”

四、考场应试“三步做题法”

一、考点难度与 GESP / CSP 对应级别映射表

二、突击备考规划（阶梯突击计划表）

三、考场应试与拿分关键点