CSP-S 2022 提高级第一轮试题答案与解析：逐题拆解与备考指南

1. 从一份初赛卷子说起：CSP-S 2022 第一轮到底考了什么

每年九月，信息学竞赛圈子里最热闹的话题之一就是 CSP-S 提高级第一轮。2022 年那场初赛，考完之后网上讨论度非常高，有人觉得选择题偏基础，有人被阅读程序题里的递归和位运算绕晕，还有人栽在完善程序题的动态规划上。我当年带学生复盘这套卷子的时候，前后完整刷了三遍，每一遍都有新的体会。这篇文章就把 CSP-S 2022 提高级第一轮试题的答案和解析做一次系统梳理，同时把每道题背后的知识点、出题意图、常见错误和备考方法讲透。

如果你正在准备 CSP-S 初赛，或者想搞清楚这套卷子为什么这样出、答案为什么是这个，那这篇内容会很有参考价值。我会按卷面结构逐块拆解：单项选择题、阅读程序题、完善程序题，每一部分都给出答案、推导过程和避坑提醒。基础薄弱的同学也能看懂，因为我会把涉及的前置知识一并补上。

先交代一下 CSP-S 第一轮的卷面结构，这是理解整套卷子的前提。满分 100 分，考试时间 120 分钟，题型固定为三块：单项选择题 15 道，每题 2 分，共 30 分；阅读程序题 3 段代码，每段附带若干判断和选择，共 40 分；完善程序题 2 段代码，每段挖空若干处，共 30 分。这个结构从 2019 年改革之后基本稳定下来，2022 年也没有例外。

提示：CSP-S 第一轮的通过线各省不同，但通常集中在 40 到 60 分区间。选择题是基本盘，阅读程序和完善程序是拉开差距的地方。

很多同学误以为初赛就是背知识点，其实 2022 年这套卷子明显在往“理解代码行为”的方向靠。纯记忆性的题目占比在下降，需要你真正读懂一段代码在干什么、复杂度是多少、边界情况会怎样。这个趋势从 2020 年就开始了，2022 年体现得尤其明显。

2. 单项选择题逐题解析与答案推导

单项选择题一共 15 道，覆盖了计算机基础、进制转换、数据结构、算法复杂度、图论、组合数学等方向。这部分看似简单，但每年都有几道题专门设陷阱。下面我挑重点题目讲，同时把答案和推导过程写清楚。

2.1 前五题：计算机基础与进制运算

前几题通常考计算机组成原理和进制转换这类基本功。2022 年这里考了补码表示、浮点数概念、存储单位换算等内容。

关于补码的题目，核心结论要记牢：n 位补码能表示的整数范围是 -2^(n-1) 到 2^(n-1)-1。这个范围不对称，负数比正数多一个，原因在于 0 只有一种表示，省下来的编码给了最小的负数。很多同学记成对称范围，结果一考就错。推导方法很简单：最高位是符号位，权值是 -2^(n-1)，其余位权值是正的，全部取 1 时得到最小值 -2^(n-1)，全部取 0 时得到 0，符号位为 0 其余全 1 时得到最大值 2^(n-1)-1。

进制转换题一般考二进制、八进制、十六进制之间的互转。这里有个提速技巧：八进制和十六进制都可以通过二进制作为中转，因为 8=2^3，16=2^4，所以一位八进制对应三位二进制，一位十六进制对应四位二进制。做题时先把所有数转成二进制，比较和运算都方便，最后再转回目标进制。这个技巧在考场上能省不少时间。

存储单位换算要区分清楚：1 Byte = 8 bit，1 KB = 1024 B，1 MB = 1024 KB，1 GB = 1024 MB。注意 bit 和 Byte 差 8 倍，这是最常见的陷阱。题目里如果说“一个汉字占 2 字节”，换算成 bit 就是 16 bit，别搞混。

2.2 中间五题：数据结构与算法复杂度

这部分是选择题的重头戏，2022 年考了栈和队列的性质、二叉树的遍历、排序算法复杂度、哈希表冲突处理等。

栈的核心性质是后进先出，队列是先进先出。有一道题给了一个入栈序列，问哪个出栈序列不可能出现。这类题的通用判断方法：模拟入栈出栈过程，看能否构造出目标序列。更快的技巧是，对于出栈序列中的任意元素，在它之后出栈且比它先入栈的元素，必须保持逆序关系。这个规律用熟了，几秒钟就能排除错误选项。

二叉树遍历题要牢记三种遍历的定义和相互推导。已知前序和中序可以唯一确定一棵二叉树，已知后序和中序也可以，但已知前序和后序不行。2022 年考的是根据前序和中序还原树然后求后序。操作步骤：前序的第一个元素是根，在中序里找到根的位置，左边是左子树，右边是右子树，递归处理。这个过程画图最直观，别硬算。

排序算法复杂度是必考内容。快速排序平均 O(n log n)，最坏 O(n^2)；归并排序稳定 O(n log n)；堆排序 O(n log n)；冒泡和插入最坏 O(n^2)。这里要注意“稳定性”这个概念：稳定排序指相等元素的相对顺序在排序后不变。冒泡、插入、归并是稳定的，快排、堆排、选择排序不稳定。这个知识点几乎每年都考。

哈希表冲突处理有开放地址法和链地址法两大类。开放地址法里线性探测容易产生聚集，二次探测和再哈希法能缓解。链地址法把冲突元素挂在同一个桶的链表上。题目常问在某个装填因子下的平均查找长度，这个需要记公式，但更重要的是理解为什么装填因子越大冲突越多。

2.3 后五题：图论、组合数学与综合应用

最后几道选择题难度上来了，2022 年涉及图的存储、最短路算法、排列组合、容斥原理等。

图的存储方式要分清邻接矩阵和邻接表。邻接矩阵空间 O(n^2)，适合稠密图，判断两点是否相邻 O(1)；邻接表空间 O(n+m)，适合稀疏图，遍历某点所有邻居 O(degree)。选择题常问在特定场景下选哪种存储更优，判断依据就是图的稠密程度和操作类型。

最短路算法要记住适用条件：Dijkstra 不能处理负权边，Floyd 可以处理负权边但不能有负环，Bellman-Ford 可以检测负环。时间复杂度分别是 Dijkstra 用堆优化 O(m log n)，Floyd O(n^3)，Bellman-Ford O(nm)。2022 年考了一道判断算法适用性的题，只要记住负权边这个关键点就能选对。

排列组合和容斥原理属于数学题。排列考虑顺序，组合不考虑顺序。容斥原理的核心公式是 |A∪B∪C| = |A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|。做题时先明确“总情况数”和“限制条件”，再用容斥把不满足条件的减掉。这类题画韦恩图辅助理解很有效。

下面用一张表把选择题高频考点和对应答案要点汇总一下，方便复习时快速查阅。

3. 阅读程序题：读懂代码比背答案更重要

阅读程序题是 CSP-S 第一轮的分水岭。三段代码，每段后面跟着判断题和选择题，考的是你能不能准确理解一段陌生代码的行为。2022 年这三段代码分别涉及递归与分治、位运算与模拟、字符串处理与动态规划思想。这部分我讲得细一点，因为很多同学在这里丢分最多。

3.1 第一段代码：递归与分治的典型套路

第一段代码通常是一段递归函数，2022 年考的是一个类似归并排序或快速幂的递归结构。读这类代码的关键是抓住三点：递归的终止条件、递归的递推关系、每层递归的工作量。

拿到代码先找终止条件，也就是 if 语句里直接 return 的分支。终止条件决定了递归的深度和边界。然后看递归调用了几次自己，每次的参数怎么变化。如果每次问题规模减半，那复杂度大概率带 log；如果每次规模减一，那可能是线性或平方级。

判断复杂度时，用主定理或者直接展开递归树。比如 T(n) = 2T(n/2) + O(n) 对应 O(n log n)，T(n) = T(n/2) + O(1) 对应 O(log n)，T(n) = 2T(n-1) + O(1) 对应 O(2^n)。2022 年这道题的递归式是 T(n) = T(n-1) + O(n)，展开后是 O(n^2)，不少同学误判成 O(n log n)。

注意：阅读程序题里的判断题经常考“程序输出是否与输入顺序有关”“是否存在整数溢出”这类细节。读代码时要把变量类型和取值范围也考虑进去。

这段代码还有一处容易看错的地方：递归调用前后的语句顺序。如果输出语句在递归调用之前，那是前序输出；在之后是后序输出。顺序不同，结果完全不一样。我在带学生时反复强调，读递归代码一定要在草稿纸上画出调用树，标出每层执行到哪一步，这样才不会看漏。

3.2 第二段代码：位运算与模拟的细节陷阱

第二段代码 2022 年考的是位运算相关的模拟，涉及与、或、异或、移位操作。位运算题的难点在于，很多操作看起来相似，实际结果差别很大，必须逐位分析。

先复习几个基本结论：x & (x-1) 可以消掉 x 最低位的 1，这个技巧常用来统计二进制中 1 的个数；x & (-x) 可以取出最低位的 1，常用于树状数组；x ^ x = 0，x ^ 0 = x，异或满足交换律和结合律。这些结论在阅读程序题里出现频率极高。

移位操作要注意：左移 k 位相当于乘 2^k，右移 k 位相当于除以 2^k 向下取整。对于有符号整数，右移的行为依赖具体实现，但在竞赛题里通常按算术右移处理，即符号位保持不变。无符号整数的右移是逻辑右移，高位补 0。这个区别在判断题里经常设坑。

2022 年这道题还考了位运算的优先级。记住：移位运算符的优先级低于加减法，高于关系运算符。也就是说 a + b << c 等价于 (a + b) << c，而不是 a + (b << c)。这个优先级顺序和很多人的直觉相反，是高频错误点。写代码时建议一律加括号，读代码时也要特别留意。

3.3 第三段代码：字符串处理与动态规划思想

第三段代码一般综合性最强，2022 年考的是字符串匹配或最长公共子序列这类带动态规划思想的代码。读这类代码要抓住状态定义和状态转移。

动态规划代码的阅读方法：先找 dp 数组的定义，通常从数组名和初始化能看出来；然后找状态转移方程，也就是循环体里 dp 值是怎么由之前的值推出来的；最后看答案取的是哪个 dp 值。把这三步理清楚，代码行为就基本掌握了。

字符串处理要注意边界：空串、单字符、全部相同字符、全部不同字符，这几种情况最容易暴露代码的 bug。判断题常问“当输入为空串时程序会怎样”“当字符串长度为 1 时输出是什么”，读代码时就要主动想这些边界。

2022 年这道题的时间复杂度是 O(n^2)，空间复杂度也是 O(n^2)。有同学问能不能优化到 O(n)，答案是可以的，用滚动数组把空间降到 O(n)，但时间复杂度不变。这个优化思路在完善程序题里也出现过，属于进阶考点。

下面这张表把阅读程序题三段代码的核心考点和易错点整理出来。

4. 完善程序题：动态规划与图论填空实战

完善程序题是整张卷子最考验综合能力的地方。2022 年两道题，一道是动态规划，一道是图论相关。每道题挖了五个空，每个空 3 分，共 30 分。这部分我按“题目背景—解题思路—逐空分析—答案验证”的结构来讲。

4.1 第一道完善程序：动态规划的状态设计与转移

第一道题 2022 年考的是一个经典的动态规划模型，类似背包问题或最长上升子序列的变体。做完善程序题，第一步不是看空，而是通读整段代码，搞清楚它在解决什么问题。

读代码时先看输入输出部分，输入是什么格式，输出是什么含义。然后看数组定义，dp 数组的维度往往暗示了状态的设计。接着看主循环的嵌套结构，外层循环通常枚举阶段，内层循环枚举状态或决策。

状态转移方程是填空的重点。判断某个空该填什么，方法是看这个位置需要用到哪些变量，以及这些变量在上下文中的含义。比如如果空在 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) 这种结构里，那填的就是决策的两种选择。

2022 年这道题有个空考的是初始化。动态规划的初始化非常关键，边界状态设错，后面全错。常见的初始化有：dp[0] = 0，其余设为负无穷（求最大值时）或正无穷（求最小值时）。具体设什么，取决于状态定义和题目要求。

提示：完善程序题填完后一定要代入验证。用题目给的样例数据手动跑一遍，看输出是否和预期一致。这一步能救回不少分。

还有一个空考的是循环边界。循环是从 0 开始还是从 1 开始，上界是 n 还是 n-1，这些细节直接决定程序对不对。判断方法：看数组下标的使用范围，如果代码里出现了 dp[i-1]，那 i 最小只能从 1 开始。

4.2 第二道完善程序：图论算法的实现细节

第二道题 2022 年考的是图论，可能是最短路、最小生成树或拓扑排序。图论代码的填空，核心是记住算法的标准实现框架。

以最短路为例，Dijkstra 的标准框架是：初始化距离数组，起点距离为 0，其余为无穷；每次从未访问节点中选距离最小的，标记为已访问；用这个节点去松弛它的邻居。填空常考的是“选最小距离节点”和“松弛操作”这两处。

最小生成树的 Kruskal 算法框架是：把所有边按权值排序；依次取边，如果两个端点不在同一集合就加入，用并查集维护集合。填空常考并查集的 find 和 union 操作。并查集的路径压缩写法要记牢：find(x) 里如果 parent[x] != x，就 parent[x] = find(parent[x])。

拓扑排序的框架是：统计每个点的入度；把入度为 0 的点入队；每次出队一个点，把它所有邻居的入度减一，减到 0 就入队。填空常考入度数组的维护和队列操作。

2022 年这道题的一个空考的是邻接表的遍历。邻接表的标准写法是用数组模拟链表：head 数组存每个点的第一条边，next 数组存下一条边的编号，to 数组存边的终点。遍历时 for (int e = head[u]; e != -1; e = next[e]) 这样写。这个框架必须烂熟于心。

4.3 完善程序题的通用解题流程

把完善程序题的解题流程总结成一套可复用的方法，考场上按这个顺序走，能提高准确率。

第一步，通读代码，确定算法。不要一上来就看空，先花两三分钟把整段代码读一遍，搞清楚它想干什么。代码里的注释、变量名、函数名都是线索。

第二步，定位每个空的作用。把空分成几类：初始化类、循环边界类、状态转移类、辅助操作类。不同类型的空，判断方法不同。

第三步，代入样例验证。填完之后，用题目给的样例输入手动模拟，看能不能得到正确输出。如果时间允许，再想一个边界情况测一下。

第四步，检查变量类型和溢出。竞赛题里经常考 int 溢出，如果涉及大数运算，要考虑用 long long。这个细节在完善程序题里也出现过。

下面这张表把完善程序题两道题的考点和答案要点汇总。

5. 高频失分点与考场实战经验

讲完题目本身，再说说考场上的实战经验。这部分是很多解析文章不会写的，但恰恰是最有用的。我带过几届学生，发现大家丢分的地方高度集中，下面把这些坑一个个点出来。

5.1 选择题的时间分配与蒙题策略

选择题 15 道，建议控制在 20 到 25 分钟内做完。平均一道题一分半，遇到卡壳的先跳过，标记一下回头再看。很多同学在选择题上花太多时间，导致后面阅读程序题没时间仔细读，这是最亏的。

蒙题也有策略。选择题四个选项，如果能排除两个，剩下两个蒙一个，正确率 50%。如果完全不会，优先选那些看起来“最不像”的选项，因为出题人往往把正确答案设得不那么显眼。当然这是下策，能算出来还是老老实实算。

计算类题目要养成验算习惯。比如进制转换，转完之后反向转回去验证一下。复杂度分析，用 n=10 这种小数据代入估算一下量级。这些小动作能显著降低低级错误。

5.2 阅读程序题的读代码方法

阅读程序题最大的问题是“读不懂”。我的建议是：不要试图在脑子里模拟整个执行过程，而是抓住代码的结构和关键变量。

具体做法：先看函数签名和全局变量，了解输入输出；然后找主函数，看整体流程；最后深入每个函数，理解它的功能。读的时候在草稿纸上记下关键变量的变化，尤其是循环变量和累加变量。

遇到递归代码，画调用树。遇到循环代码，列出前几次迭代的结果，找规律。遇到位运算，把数写成二进制逐位看。这些方法看起来笨，但比硬想要快得多。

判断题要特别小心“一定”“所有”“必然”这类绝对化表述，这类选项往往是错的。选择题要看清问的是“正确”还是“错误”，是“最大”还是“最小”，每年都有人因为看错题干丢分。

5.3 完善程序题的填空技巧

完善程序题的填空，有个实用技巧：先填最有把握的空，用这些空去推断其他空。因为代码是连贯的，一个空填对了，上下文就清晰了，其他空也容易判断。

如果某个空实在不会，用排除法。把选项代入，看哪个能让代码逻辑通顺。注意，通顺不等于正确，还要考虑边界和复杂度。有时候两个选项都能让代码跑通，但一个复杂度更优，那选优的。

填完之后一定要整体检查一遍。检查内容包括：变量是否都初始化了，循环边界对不对，数组下标有没有越界，有没有死循环风险。这几项检查完，能排除大部分错误。

注意：完善程序题每个空 3 分，错一个空可能连带影响后面的判断。所以填的时候要稳，不要为了赶时间乱填。

5.4 常见问题速查表

把备考和考试中常见的问题整理成一张表，方便对照排查。

6. 备考 CSP-S 初赛的实操路线

最后聊聊怎么备考。CSP-S 初赛不是靠临时抱佛脚能过的，需要系统准备。我按时间线给一条可执行的路线。

6.1 基础阶段：知识点全覆盖

考前两到三个月，先把知识点过一遍。计算机基础、进制转换、数据结构、算法复杂度、图论、组合数学，这些都要覆盖到。推荐用一本竞赛教材配合历年真题，边学边练。

这个阶段的重点是理解概念，不要死记。比如复杂度分析，理解了递归树怎么展开，就不用背公式。数据结构，理解了每种结构的适用场景，选择题自然能选对。

每天保持一定的代码阅读量。找一些经典的竞赛代码，比如快排、归并、Dijkstra、并查集，逐行读懂。这个习惯坚持一个月，阅读程序题的正确率会明显提升。

6.2 强化阶段：真题实战

考前一个月，开始刷真题。从最近的年份往前刷，2022、2021、2020 这样倒着来。每套卷子严格计时，模拟真实考场环境。

刷完一套，认真复盘。错题要分析错因：是知识点不会，还是粗心，还是时间不够。不同原因对应不同的改进方法。知识点不会就回去补，粗心就养成检查习惯，时间不够就调整做题顺序。

2022 年这套卷子建议至少刷两遍。第一遍计时做，第二遍只做错题和不确定的题。两遍下来，这套卷子的价值就榨干了。

6.3 冲刺阶段：查漏补缺与心态调整

考前一周，不要再刷新题了，把错题本和笔记过一遍。重点看那些反复错的知识点，确保不再犯。

考前一天，把考试用品准备好，准考证、身份证、笔、橡皮。提前看好考场路线，别迟到。晚上早点睡，保证考试时头脑清醒。

考试当天，先做选择题，再做阅读程序，最后做完善程序。遇到难题先跳过，把能拿的分先拿到。心态放平，初赛通过线没那么高，正常发挥就能过。

6.4 我个人的几点体会

带学生这些年，我发现初赛失分最多的不是难题，而是基础题。很多同学觉得选择题简单，做得快，结果错一堆。反而是阅读程序和完善程序，认真读的同学能拿到不错的分数。

还有一个体会是，代码阅读能力是可以练出来的。刚开始读一段代码要十分钟，练多了三分钟就能抓住重点。这个能力不仅对初赛有用，对复赛和以后的编程工作都有帮助。

最后说一句，CSP-S 初赛只是第一步，过了初赛还有复赛。但初赛的知识点本身就是编程的基础，认真准备初赛的过程，也是在打牢基础。别把它当成负担，当成一次系统梳理知识的机会。