2019年的CSP-S初赛，是很多信奥赛选手又爱又恨的一份卷子。那一年，大家熟悉的“NOIP提高组”换了名字，CSP-S第一次出现在准考证上，C++依然是唯一的指定参赛语言，而选择题第11到第15题，位置正好卡在整张卷子的“腰部”。前面10题还在聊进制转换、逻辑表达式、C++语法这些相对温柔的内容，到了第11题往后，命题人明显开始上强度了——排序、二叉树、二分查找、图遍历、组合概率，全是正经的数据结构与算法分析。这篇文章就把这5道题掰开揉碎，每题从题目还原讲到公式推导，再讲到考场上的快速判断方法，最后附上我这些年刷题带学生总结出来的避坑经验。无论你是第一次准备csp-s初赛的新手，还是刷题遇到瓶颈的进阶选手，这5道题都值得停下来多看几遍。
1. 2019年CSP-S初赛：这套卷子为什么值得反复刷
1.1 那一年，初赛换了张脸
2019年对信息学竞赛圈子来说是特殊的一年。原来的NOIP系列赛事改名为CSP，分为面向入门选手的CSP-J和面向提高组选手的CSP-S，CSP-S第一轮就是大家俗称的“初赛”。虽然名字变了，但考试内核几乎没有变：仍然是笔试，仍然要求选手用C++这门语言所附带的数据结构与算法知识去解题，仍然要过线才能进入第二轮上机考试。
第一轮的满分是100分，题型结构和之前保持一致：一、单项选择题（15题，每题2分，共30分）；二、问题求解（2题，共10分）；三、阅读程序写结果（4题左右，共约40分）；四、完善程序（2题，约20分）。这个结构很有意思：单选虽然只占30分，但它决定了一个人的基本盘。很多选手上机能力很强，可初赛单选因为知识面有漏洞，莫名其妙丢个8到10分，最后就差一两分进不了复赛，这种事每年都有。所以单选的每一道题——尤其是偏算法分析的第11到15题——都不应该凭感觉蒙。
1.2 选择题11-15在整卷中的位置与命题风格
如果你纵向看过近几年csp-s初赛真题，会发现一个规律：选择题前面的1到10题，以语言语法、进制运算、简单数据结构识记为主，属于“送分区”；而从第11题左右开始，命题人开始调转枪口，集中考察经典算法的复杂度分析、树与图的性质推导、组合数学和概率计算。也就是说，第11到第15题是单选部分真正的分水岭，也是不少选手丢分的重灾区。
这几道题的命题风格非常统一：题干不会很长，但每个选项都经过精心设计，干扰项往往来自“记混了的公式”。比如把最坏情况当最好情况、把完全二叉树的节点公式带错、把邻接表的时间复杂度记成O(n²)等等。换句话说，第11到15题考的不是你会不会写代码，而是你能不能把课本里的原理真正理解到位，并且能在考场那种紧张状态下快速作出正确判断。这也是我为什么建议所有准备csp-s初赛复习的人，把2019年这份卷子的这5道题当作“样例题”反复吃透——它们几乎涵盖了初赛单选最核心的几大算法考点。
2. 第11题：冒泡排序的比较次数，最坏情况到底是多少
2.1 题目还原
第11题是一道非常经典的排序算法复杂度题，题目大致是这样的（按常见考场版本整理）：
用冒泡排序对n个互不相同的元素进行升序排序，在最坏情况下，算法执行过程中需要进行的元素比较次数为（ ）。
A. n-1
B. n(n-1)/2
C. nlog2n
D. n²
这道题的正确答案是B。
很多同学看到“最坏情况”四个字，第一反应是“反序嘛，那比较次数不就是n²吗？”然后果断选了D。这个错误太典型了——n²只是数量级上的描述，而题目问的是精确次数，两者不是一回事。冒泡排序的最坏情况比较次数是一个确定的等差数列求和结果，不是n²。
2.2 推导：为什么最坏是n(n-1)/2
要彻底搞清楚这个问题，我们先回忆一下标准冒泡排序的C++实现。不优化的版本长这样：
for (int i = 0; i < n - 1; ++i) { for (int j = 0; j < n - 1 - i; ++j) { if (a[j] > a[j+1]) { swap(a[j], a[j+1]); } } }外层循环一共跑n-1趟，第1趟时内层j从0到n-2，比较n-1次；第2趟内层j少比较一个，比较n-2次；最后一趟比较1次。把所有趟的比较次数加起来，就是：
(n-1) + (n-2) + ... + 1 = n(n-1)/2。
重点来了：这个次数里，每一趟都会老老实实把相邻元素比较一遍，不管它们是否已经有序。也就是说，在最坏情况下（元素完全反序）比较次数是n(n-1)/2，在最好情况下（元素原本就是升序）比较次数依然是n(n-1)/2——只要用的是上面这种不带任何优化的标准实现。这就是冒泡排序最容易被忽略的性质：它的比较次数在无优化版本下是固定的，与初始数据顺序无关。
至于交换次数，才和数据顺序有关：最坏情况下每比较一次都要交换，交换次数也是n(n-1)/2；最好情况下一次交换都不发生。所以如果题目问的是“最坏情况下交换次数”，答案同样是B；如果问“最好情况下交换次数”，答案是0。
2.3 优化版本：加了flag之后结果会变
说到这里，有经验的选手肯定会想到一种优化写法：在某趟比较中如果一次交换都没有发生，说明数组已经有序，可以直接结束循环。
bool flag = true; for (int i = 0; i < n - 1 && flag; ++i) { flag = false; for (int j = 0; j < n - 1 - i; ++j) { if (a[j] > a[j+1]) { swap(a[j], a[j+1]); flag = true; } } }加了flag之后，如果初始序列完全有序，第一趟比较n-1次发现没有交换，直接结束，总比较次数就是n-1。这就是为什么网上有些资料会说“冒泡排序最好情况下比较次数是n-1”。两种说法都对，区别在于你讨论的是哪种实现。竞赛初赛命题默认考察的是教材里最标准的无优化版本，所以看到“冒泡排序的最坏比较次数”，选n(n-1)/2准没错。但在复习时，一定要把优化版的逻辑也理解透彻，因为阅读程序题里经常出现带flag的冒泡排序，那时候结论就完全不同了。
2.4 同类变式：选择排序和插入排序也来凑热闹
初赛不会只考冒泡排序，通常会把选择排序、插入排序拿出来做干扰对比。这三个排序的“比较次数”要放在一起记：
- 选择排序：无论数据顺序如何，比较次数恒为n(n-1)/2；交换次数最多n-1次，最少0次。
- 插入排序：最好情况下（基本有序）每轮比较1次就插入，总比较次数接近n；最坏情况下（逆序）每轮都要比较到最前面，总比较次数为n(n-1)/2。
- 冒泡排序（标准版）：比较次数恒为n(n-1)/2；交换次数最好0次，最坏n(n-1)/2。
这三兄弟里，选择排序和标准冒泡排序的比较次数完全一样，但交换次数差异很大；插入排序则因为“基本有序时效率极高”这个特性，经常出现在“最好情况复杂度”的考题里。建议复习时自己画一张表，把这几个排序的最坏/最好比较次数、交换次数、稳定性都列出来，考前扫一眼比临时翻书管用得多。
3. 第12题：完全二叉树叶子节点数，两个公式别记混
3.1 题目还原
第12题是一道关于二叉树性质的经典题，题目一般这样表述：
一棵完全二叉树共有1001个节点，则它的叶子节点个数为（ ）。
A. 500
B. 501
C. 502
D. 无法确定
正确答案是B。
这道题考察的是完全二叉树节点数度的关系，几乎每年csp-s初赛知识点里都会出现类似题目。很多同学看到1001这个数字就开始画图，试图把这个二叉树画出来数叶子，这方向就错了——节点数上千的树画到一半人就崩溃了。这类题要用公式，而不是用蛮力。
3.2 用n0 = n2 + 1推导
在任意二叉树中，设度为0的节点数为n0（也就是叶子节点）、度为1的节点数为n1、度为2的节点数为n2。总节点数满足：
n = n0 + n1 + n2。
同时还有一个经典的边数关系：二叉树中边数等于节点总数减1，也等于n1 + 2n2（每个度为1的节点贡献一条边，每个度为2的节点贡献两条边）。所以：
n0 + n1 + n2 - 1 = n1 + 2n2
化简得到：
n0 = n2 + 1
这个结论对任何二叉树都成立，是二叉树题目的万能钥匙。接下来只需要确定n1的值。完全二叉树有个重要性质：除了最后一层可能不满，其余层都是满的；而且最后一层的节点都连续靠在左侧。这意味着度为1的节点最多只有一个，也就是n1只能等于0或1。
现在把n=1001代入总节点公式：
1001 = n0 + n1 + n2 = (n2 + 1) + n1 + n2 = 2n2 + n1 + 1
如果n1=1，那么2n2=999，n2=499.5，不是整数，矛盾；如果n1=0，那么n2=500，n0=501，恰好成立。所以叶子节点数是501。
3.3 更快的考场判断法
上面这种推导虽然严谨，在考场上还是略慢。我常用的技巧是看节点数的奇偶性。完全二叉树中，当总节点数n为奇数时，度为1的节点数为0，叶子节点数n0 = (n+1)/2；当n为偶数时，度为1的节点数为1，叶子节点数n0 = n/2。
1001是奇数，所以叶子节点数直接就是(1001+1)/2 = 501。这个技巧本质上是上面公式的推论，但快得多。如果题目把1001换成1000，那叶子节点数就是1000/2 = 500。我见过不少同学把这两个公式记反，奇数情况当成n/2、偶数情况当成(n+1)/2，一丢就是2分。强烈建议把“奇加偶减”这个口诀写在笔记本扉页上。
3.4 延伸：与其他树结构考点的联动
初赛不会只考一个孤立的知识点，第12题经常和“满二叉树”“二叉搜索树”等概念绑定出题。比如：一棵高度为h的满二叉树，节点总数是2^h - 1（从第1层开始计数时是2^h - 1，从第0层开始是2^(h+1) - 1，做题前要看清题干定义）。再比如：n个节点的完全二叉树，深度（层数）等于⌊log2 n⌋ + 1，1001个节点的完全二叉树深度就是10，因为2^9 = 512 < 1001 ≤ 1024 = 2^10。
考场上如果遇到“完全二叉树+叶子节点+高度+某层节点数”捆绑出现的题目，我的解题顺序是先确定n1，再求n0，最后用高度公式验证结果是否合理。三步走下来基本不会栽跟头。
4. 第13题：二分查找最多比较几次？判定树说了算
4.1 题目还原
第13题考察的是二分查找（折半查找）的时间复杂度精确值，题目类似：
在长度为1000的有序表中用二分查找法查找一个元素（不论该元素是否存在），最多需要比较的次数为（ ）。
A. 9
B. 10
C. 11
D. 1000
正确答案是B。
很多同学记得二分查找时间复杂度是O(log2n)，于是就想：log2(1000)大约是9.97，取整那就是9啊，选A。但这个想法忽略了两个细节：第一，复杂度是数量级，题目问的是精确比较次数；第二，查找失败的情况也会产生额外的一次比较，最大比较次数应该按判定树的高度来算。
4.2 判定树角度
二分查找的过程可以抽象成一颗判定树：每次把当前查找区间从中间分成两半，中间元素作为根节点，左半区间递归构成左子树，右半区间递归构成右子树。在这棵树上，一次查找就是从树根走到某个节点的路径，路径上经过的节点数就是比较次数。查找成功时走到被找到的节点；查找失败时走到一个空指针的位置，也就是树的外部节点。
所以“最多比较几次”这个问题就变成了“这棵判定树最高有几层”。长度为n的有序表，其二分查找判定树中共有n个内部节点，失败节点有n+1个。对于n=1000，判定树的高度为⌈log2(n+1)⌉ = ⌈log2(1001)⌉。因为2^10 = 1024 > 1001，而2^9 = 512 < 1001，所以需要向上取整个10。
4.3 公式与手算验证
二分查找比较次数有两个常用公式，容易混，这里一起说清楚：
- 查找成功时，最多比较⌊log2 n⌋ + 1次；
- 查找失败时，最多比较⌈log2(n+1)⌉次。
n=1000时，成功最多比较⌊log2 1000⌋ + 1 = 9 + 1 = 10次；失败最多比较⌈log2 1001⌉ = 10次。两者一致，答案就是10。
我习惯用一个小例子验证：n=1时，无论成功失败都只比较1次，公式给1；n=2时，判定树一层根节点加一个孩子，最多比较2次，⌊log2 2⌋ + 1 = 2，⌈log2 3⌉ = 2，都对。拿这种极端小数据验证一遍，比死记公式靠谱得多。考场上如果一时忘了公式，直接按n=1、2、3推规律，也能把选项锁定。
4.4 C++实现里的边界坑
二分查找的选择题做对了，上机写代码时还是容易栽，因为边界处理太容易出错。标准写法有很多种，我用的是左闭右闭区间：
int l = 0, r = n - 1; while (l <= r) { int mid = (l + r) / 2; if (a[mid] == target) return mid; else if (a[mid] < target) l = mid + 1; else r = mid - 1; } return -1;注意这里的mid = (l + r) / 2，当l和r都很大的时候可能存在整数溢出风险，稳妥的写法是mid = l + (r - l) / 2。另外，循环条件是l <= r而不是l < r，后者会导致查找区间缩到单个元素时出错。初赛阅读程序题里经常故意把l < r写出来作为坑，这时候要从“区间是否还需要继续查找”的角度判断，而不是凭对错直觉。
初赛选择题只问“最多比较几次”时，不需要写代码，但理解代码边界能反过来帮你理解判定树的分支逻辑：每次比较后区间减半，直到区间为空才停止，所以判定树的高度本质就是“区间被不断折半直到变空的次数”。
5. 第14题：邻接表存图，DFS为什么是O(n+m)
5.1 题目还原
第14题考察图的基本存储与遍历复杂度，题目大约是：
用邻接表存储一个有n个顶点、m条边的有向图，对该图进行深度优先遍历，算法的时间复杂度为（ ）。
A. O(n)
B. O(m)
C. O(n+m)
D. O(n×m)
正确答案是C。
这道题的正确率其实很高，但很多人只是记住了“DFS是O(n+m)”，并不知道为什么。初赛一旦换一种问法——比如“用邻接矩阵存储，DFS的时间复杂度是多少”——错误率立刻就上来了。所以这道题一定要从原理上吃透。
5.2 邻接矩阵与邻接表的复杂度对比
先看两种存储结构。邻接矩阵是一个n×n的二维数组，a[i][j]=1表示从顶点i到顶点j有边。在这种结构下，无论图中有多少条边，想要遍历一个顶点的所有出边，都必须扫描一整行n个位置；整个DFS要把每个顶点都访问到，并且每个顶点都要扫描一行，所以总复杂度是O(n²)。这个复杂度只和顶点数有关，和边数m无关。
邻接表则完全不同：每个顶点带一条链表，链表里存的是从这个顶点出发能直接到达的邻居顶点。遍历顶点v的出边时，只需要顺着v的链表走一遍，花费的时间正比于这个顶点的出度。所有顶点的出度之和等于有向图的边数m，所以扫描所有边总共花费O(m)。再加上每个顶点需要O(1)时间打标记、递归调用，n个顶点就是O(n)。两部分合并，总复杂度O(n+m)。
注意一个小小的细节：如果是无向图，每条边在邻接表中会存两次（u的链表里有v，v的链表里有u），所有链表的节点总数是2m。但时间复杂度依然是O(n+m)，因为2m和m同阶，常数不影响大O表示。初赛如果问“邻接表中有向图边表节点的个数”，答案是m；问无向图，答案是2m。这两个数字容易混，做题时先确认图是有向还是无向。
5.3 DFS的完整开销拆解
为了把O(n+m)彻底讲明白，我把DFS的递归实现拆成三部分开销：
第一，初始化部分。需要给每个顶点打上“未访问”标记，这是一个长度为n的数组，O(n)。
第二，访问顶点部分。每个顶点最多被调用一次DFS，因为一旦访问就会标记，不会重复进入。n个顶点，每个顶点的进出栈操作是O(1)，合计O(n)。
第三，遍历邻接表部分。在顶点v的DFS内部，要循环处理v的所有邻居。循环次数等于v的出度。所有顶点出度之和等于m，所以循环总次数是O(m)。就算某个顶点出度为0，也只是空转一次循环体，不产生额外边开销。
把三部分加起来，O(n) + O(n) + O(m) = O(n+m)。这个推导同样适用于BFS，只是BFS把递归栈换成了队列，本质开销完全相同。所以初赛如果问BFS的复杂度，答案依然是O(n+m)。
5.4 初赛对图遍历的常见考法
图这块内容在csp-s初赛选择题里出镜率很高，除了“DFS/BFS复杂度”之外，还喜欢考这么几件事：
一是“连通分量”。对无向图做一次DFS，能访问到的顶点集合就是其中一个连通分量；如果一次DFS后还有未访问的顶点，说明图不连通。要求“判断一个图是否连通”的标准做法就是做一次DFS或BFS，看是否所有顶点都被访问。
二是“边的方向”。对有向图做DFS，会遇到四种边：树边、反向边、前向边、横向边。初赛不常考这么细，但阅读程序题里可能出现“用DFS统计边的数量”这类变形。
三是“邻接矩阵与邻接表的选择”。如果题目给出一个稀疏图（m远小于n²），用邻接表更省空间且遍历更快；如果是稠密图，邻接矩阵的O(1)判断两点是否相连反而有优势。2019年这道第14题虽然只问复杂度，但后续复习一定要把存储结构的适用场景一起掌握，因为第二轮上机写图论题时，选错存储结构直接决定你能不能拿满分。
6. 第15题：随机取两个数的奇偶和，概率题别硬数
6.1 题目还原
第15题是一道组合计数与概率结合的题，题目类似：
从1到10这10个整数中随机取出两个不同的数，则这两个数之和为偶数的概率为（ ）。
A. 1/2
B. 4/9
C. 5/9
D. 1/3
正确答案是B。
这道题拿到手，第一反应如果是“直接列出来数”，那就容易数错。10个数取两个一共有45种组合，手工列出45个和再数偶数，不是不行，但考场时间不允许。组合计数题的正确姿势永远是先分类，再套组合数公式。
6.2 组合计数推导
两数之和为偶数，只有两种情况：两个数都是偶数，或者两个数都是奇数。在1到10里，偶数有2、4、6、8、10共5个，奇数有1、3、5、7、9共5个。
取两个不同数的总方案数是从10个里取2个的组合数：
C(10, 2) = 10 × 9 / 2 = 45
两个都是偶数的方案数：C(5, 2) = 10
两个都是奇数的方案数：C(5, 2) = 10
满足和为偶数的方案数总共：10 + 10 = 20
所以概率为20/45 = 4/9。
注意这里不能用“取到两个偶数的概率是1/2 × 1/2 = 1/4，取到两个奇数同理1/4，加起来1/2”来算，因为这是不放回抽取，第一次取到偶数的概率是5/10，第二次再取到偶数的概率变成4/9，连续两次取到偶数的概率是(5/10)×(4/9) = 2/9，两个2/9相加是4/9。这样一算就和组合数完全一致了。
6.3 概率题的通用破题姿势
这5道选择题里，第15题属于“题目最短、思维量最大”的一类。我整理了一套概率题的通用流程，适合csp-s初赛所有概率题：
第一步，确定样本空间。题目说的是“取出两个不同的数”，样本就是组合数C(10,2)，不是排列数P(10,2)。区分组合与排列，第一步错了后面全错。
第二步，把事件拆成互斥子事件。“和为偶数”拆成“偶+偶”和“奇+奇”，这两个子事件互斥，概率可以直接相加。
第三步，每个子事件内部用组合数算数量，再除以总数。如果题目偷懒改成“随机放回地取两次”，那样本空间就变成10×10=100个有序对，答案会变成1/2。说明稍微改一个字，结果天差地别，读题时看到“不放回”三个字要格外警觉。
第四步，验证概率范围。算出的概率必须在0到1之间，且所有互斥事件概率之和为1。比如这题“和为奇数”的概率就是1 - 4/9 = 5/9，反过来想也一样：一个奇数一个偶数，共有5×5=25种，25/45=5/9。用两种思路互相验证，答案基本稳了。
6.4 用C++随机数做模拟验证
很多同学复习组合概率时会觉得抽象，我提供一个很实用的自检方法：用C++的随机数模拟跑大量实验，观察频率是否趋近于理论概率。这也是最近csp-s初赛复习群里常有人问“c++随机数怎么用”的典型场景。
#include <bits/stdc++.h> using namespace std; int main() { srand(time(0)); long long cnt = 0, T = 1000000; for (int i = 0; i < T; ++i) { int a = rand() % 10 + 1; int b = rand() % 10 + 1; while (b == a) b = rand() % 10 + 1; if ((a + b) % 2 == 0) ++cnt; } cout << (double)cnt / T << endl; return 0; }这段代码模拟的是“不放回取两个不同数”的过程，跑100万次实验后输出的结果会在0.444附近波动，也就是4/9的小数形式。如果模拟出来明显偏差，说明题目条件理解反了。这招特别适合验证那种“感觉自己做对了但心里没底”的概率题，比翻答案踏实得多。当然，真上考场还是得靠手算，模拟是课后验证用的。
7. 五个题串起来：初赛选择题的高频考点与应试策略
7.1 考点矩阵：排序、树、查找、图、计数
把这5道题放在一起看，2019年CSP-S初赛选择题第11到15题几乎就是一张“算法基础考点清单”。我整理了一个速查矩阵，准备csp-s初赛复习时可以直接对照自查：
| 题号 | 核心考点 | 关键公式或结论 | 最容易踩的坑 |
|---|---|---|---|
| 11 | 冒泡排序 | 标准版比较次数恒为n(n-1)/2 | 把数量级n²当成精确次数 |
| 12 | 完全二叉树 | n0=n2+1；奇数节点n0=(n+1)/2 | n1取0或1判断错误 |
| 13 | 二分查找 | 最多比较⌈log2(n+1)⌉或⌊log2n⌋+1 | 直接取log2(1000)的下整9 |
| 14 | 图的DFS | 邻接表O(n+m)，邻接矩阵O(n²) | 无向图边表节点数是2m |
| 15 | 组合概率 | 不放回抽样用组合数 | 用放回思路导致答案变1/2 |
这张表浓缩了5道题的全部精华。你会发现它们有一个共同特征：全部都是“公式记忆+逻辑推导”的五五开。公式记不准，推导再快也白搭；推导不会，公式背得再熟也容易用错。所以复习时一定要把两者结合起来，每道题都要能讲清楚“为什么是这个答案”。
7.2 考场时间分配与读题顺序
CSP-S初赛总时长通常是2小时，前面30分的选择题不建议花超过20分钟。我的建议是：前10道语言基础题控制在8分钟内，第11到15题控制在12分钟内，平均每题2分多钟。如果某道题卡了超过3分钟，先圈出来跳过去，把后面问题求解和阅读程序的分拿到再说。
读题顺序上有一点小技巧：做排序、树、图这类算法题时，先看选项再读题干。因为选项里往往藏着“比较次数”还是“交换次数”、“有向图”还是“无向图”、“放回”还是“不放回”这样的关键区分。带着区分点去读题干，能有效避免读完一遍发现没注意细节、又得重读一遍的尴尬。这个习惯我在带学生刷csp-s模拟题时反复强调，实测能省下不少时间。
7.3 近年CSP-S初赛对这几块的调整
翻一翻2020年之后的csp-s初赛真题，会发现命题组并没有抛弃这几类考点，只是换着花样考。2020年前后爱把二分查找放进阅读程序题，让你手算mid的变化过程；2021年左右把二叉树和堆结合，问“插入一个元素后堆的调整次数”；组合概率题则越来越多地结合C++随机数、期望值等概念，题干变得比2019年更绕。但万变不离其宗，底层的公式和推导逻辑，第11到15题里已经全部涉及了。
所以我的结论很明确：2019年这套卷子的选择题第11到15题，就是一份浓缩的“初赛单选高频考点地图”。把它彻底吃透，比盲目刷十套模拟题都管用。
8. 常见问题与避坑速查
8.1 记忆版本不同怎么办
每年考完都有选手在群里争论“第12题到底是1001还是1000”“第15题到底是奇数还是偶数”，主要原因就是不同渠道流传的回忆版题目存在细节差异。应对方法有两个：一是以官方公布的真题为准复习，民间回忆版只用来熟悉题型；二是把同类题的变体都练一遍。比如二叉树节点数，1001和1000的答案差一个，你就把这两个数都算一遍，顺便把999也算一下，这样不管考场碰到哪个数都不慌。我做解析时，题目按常见考场版本整理，个别表述细节可能与原卷略有差异，但核心考点与答案不受影响，复习时重在掌握思路而不是背原题。
8.2 五个高频失分点
结合我这些年的经验，第11到15题的丢分原因高度集中，基本就这五条：
第一，排序题没分清“比较次数”和“交换次数”。比较次数决定了排序算法的效率上界，交换次数才是数据移动的开销。标准冒泡排序最坏比较和交换都是n(n-1)/2，但选择排序最坏比较n(n-1)/2、交换却只有n-1次，两者混在一起必错。
第二，完全二叉树忘了考虑n1的取值。有些同学只知道n0=n2+1，不知道完全二叉树中n1只能是0或1，结果代入公式时随便猜一个n1，答案自然错。记住：先判断节点总数奇偶，再定n1。
第三，二分查找的向上取整和向下取整记反。成功最多比较⌊log2n⌋+1，失败最多比较⌈log2(n+1)⌉，两个公式别混。如果实在记不牢，就用n=1、2、3的小数据现场验证。
第四，图的复杂度没区分存储结构。邻接矩阵O(n²)，邻接表O(n+m)，这个结论必须刻在脑子里。无向图邻接表的边表节点数2m、有向图m，也是高频陷阱。
第五，概率题没看清“放回”还是“不放回”。一字之差，样本空间从组合变成排列，概率从4/9变成1/2。考场读题时遇到这类字眼可以用笔圈出来。
8.3 速查表：公式加答案汇总
最后放一份浓缩版速查表，考前30分钟翻一遍即可：
| 考点 | 必背结论 |
|---|---|
| 冒泡排序比较次数 | 标准版恒为n(n-1)/2；优化版有序时n-1 |
| 完全二叉树叶子节点 | n为奇数n0=(n+1)/2；n为偶数n0=n/2 |
| 二分查找最大比较次数 | ⌈log2(n+1)⌉（失败），⌊log2n⌋+1（成功） |
| 邻接表DFS/BFS复杂度 | O(n+m)；邻接矩阵为O(n²) |
| 无放回取两数和为偶数 | 同奇偶组合数相加 / 总组合数 |
这5道题对应的答案，我再说一遍：第11题B，第12题B，第13题B，第14题C，第15题B。有意思的是，第11到13题答案都是B，这提醒我们考场对答案分布不要有太多心理暗示——不要因为前面连续选B就怀疑自己做错了，只要推导过程站得住，答案就是对的。
我个人的建议是，刷完这套题后不要急着做下一套，先花10分钟把这5道题的推导过程自己在草稿纸上完整写一遍，再用7.1节的考点矩阵做自测。我在实际教学中发现，能独立写出“为什么选B”的选手，在之后任何一次初赛中遇到同类题，正确率都明显高于只背答案的同学。这种“讲得出道理”的复习方式，才是信奥赛这条路能走远的真正底气。
