简介：这份PDF聚焦2020年CSP-J1入门级与CSP-S1提高组初赛，面向备战信息学奥赛第一轮的选手、竞赛教练及需要复盘真题的教师，帮助读者对照答案梳理失分点并理解命题思路。压缩包内仅含1个PDF文件，体积约63KB，内容围绕两套试题的答案、解析与总结展开，并附有相关真题、各省分数线统计与参赛经验等参考线索，便于按需延伸查阅。已有4584人学习，说明其在初赛备考群体中具有一定参考价值。读者可借此核对2020年两级别初赛答案，分析选择题、程序阅读与完善程序等题型的常见陷阱，结合解析归纳数据结构、算法与语法知识点，并借助分数线信息判断自身水平、安排后续训练。整体适合作为赛前查漏补缺、把握难度和赛后复盘的材料，同时可了解当年试题难度与命题风格。

1. 从一段二十行的循环说起：CSP-J 初赛和 CSP-S 初赛到底在考什么

CSP-S 初赛最容易踩坑的地方，往往不是最后两道完善程序，而是阅读程序里那段只有二十行、看起来没什么威胁的双重循环。2020 年那份答案解析被反复传阅，真正有价值的不只是答案本身，而是它把“这道题为什么这么想”展开给你看。第一轮满分 100 分，单选 30、阅读程序 40、完善程序 30，120 分钟，全在答题卡上完成，不写一行能跑的代码。这场考试考的不是你会不会写程序，而是你能不能在纸上把别人的程序读懂、算准、补全。适合已经学完 C++ 基础语法、准备第一次上考场的人，更适合考了两三次还在 60 分上下浮动、想知道自己到底丢在哪一块的人。

2. 分值地图与单选考点：30 分里有 22 分是能背出来的

2.1 三种题型的分值与时间分配

先把分值分配搞清楚，后面所有策略都从这里推导。CSP-J1 和 CSP-S1 的卷面结构一致，只是难度不同，同年两卷的知识点范围高度重叠，所以一份答案解析往往能同时覆盖两个组别。

阅读程序的 40 分里，判断题一般每题 2 分、选择题每题 3 分，具体配比逐年微调，进考场先看卷面说明，不要凭记忆套。很多人在单选上花 40 分钟，结果阅读程序只剩 30 分钟，第三篇直接靠猜，这是最典型的失分场景。

单选 15 题的考点分布大致稳定：计算机基础 3 到 4 题（进制、编码、存储单位、网络常识），C++ 语法 3 到 4 题（运算符优先级、类型转换、指针与引用、数组与字符串），数据结构 3 题（栈队列、树、图、哈希），算法与复杂度 3 题（排序、递归、复杂度量级），数学 2 到 3 题（排列组合、概率、逻辑推理）。前四类靠背和练就能拿，数学类看临场。

提示：单选控制在 25 分钟内做完，遇到卡壳超过 90 秒的直接标记跳过，先把能拿的分收进袋子。

2.2 进制、位运算与原反补码：三步定答案

这三块是单选里最容易“会但算错”的题。进制转换用固定动作，不要心算。

十进制整数转二进制：除 2 取余，倒序排列。小数部分：乘 2 取整，正序排列。二进制转十六进制：从右往左四位一组，不够左边补零，每组换成一个十六进制字符。二进制转八进制：三位一组，同理。

原码、反码、补码只记一条链：正数三码相同；负数的反码是符号位不变、其余位取反，补码是反码加 1。n 位补码的表示范围是 -2^(n-1) 到 2^(n-1)-1，8 位就是 -128 到 127，这个范围每年都有人写成 -127。

位运算记四个常用套路，考试基本跑不出这个圈：

• x & (x - 1)消掉最低位的 1，用来统计二进制中 1 的个数，循环几次就有几个 1。
• x & -x取出最低位的 1，也叫 lowbit，树状数组的基石。
• x ^ x = 0，异或用来找唯一出现奇数次的数，全部异或一遍剩下的就是答案。
• 左移 k 位等于乘 2^k，右移 k 位等于整除 2^k 并向下取整，负数右移要小心。

“三步”指：第一步确定位宽（8 位、16 位还是 32 位），第二步判断正负（看最高位），第三步按链走（负数先减 1 再取反得原码，或先取反再加 1 得补码）。位宽搞错，后面全错。

2.3 数据结构与排序：两张表解决大半道题

数据结构的单选题几乎都是“性质判断”，把下面这张表记住，比现场推快得多。

二叉树有一条必考结论：任何非空二叉树中，叶子结点数 n0 等于度为 2 的结点数 n2 加 1，即 n0 = n2 + 1。推导过程不用背，用“边数 = 结点数 - 1”两分钟能推出来，但考场上直接用结论更稳。

排序算法重点是稳定性和复杂度，这张表建议抄在错题本第一页。

稳定性记一句话：只有“相邻交换”和“分治合并”才稳，跳跃式交换（选择、快排、堆排）都不稳。

2.4 组合计数与概率：加乘原理的边界

这类题错的人最多，因为公式都认识，就是不知道用哪个。判断标准只有一条：做完一件事是“分类”还是“分步”。分类用加法，每类互不重叠；分步用乘法，每步缺一不可。

常用公式：

• 排列 A(n, m) = n! / (n - m)!，从 n 个不同元素里取 m 个排队。
• 组合 C(n, m) = n! / (m!(n - m)!)，只取不排。
• 插板法：n 个相同物品分给 m 个人，每人至少一个，方案数 C(n - 1, m - 1)。
• 错排 D(n) = (n - 1)(D(n - 1) + D(n - 2))，D(1) = 0，D(2) = 1。
• 鸽巢原理：n + 1 个物品放进 n 个抽屉，必有一个抽屉至少两个。

古典概型就是“符合条件的情况数除以总情况数”，两个数都用组合算，别中途换算成百分数，最后一步再换。考场上最容易错的是“至少”两个字，正面算不清楚就反过来用总数减一个都没有的情况。

2.5 真题演练：五道单选题的完整推演

下面五道题按 2020 年卷面结构改写，覆盖上面四类考点，每道给出思路而不是只给答案。

第一题：二进制 1011010 转成十六进制是多少。从右往左四位一组，得到 0101 和 1010，前一组补零后是 5，后一组是 A，结果是 5A。这类题的唯一风险是分组方向搞反，从右往左，不能从左往右。

第二题：8 位补码 1111 0110 对应的真值是多少。最高位是 1，负数。补码减 1 得反码 1111 0101，符号位不变、其余取反得原码 1000 1010，真值 -10。也可以用“取反加 1”的等价算法，两种算法结果必须一致，不一致就是位宽搞错了。

第三题：入栈顺序为 1、2、3、4，下列哪个出栈序列不可能出现。判断方法：对每个候选序列，模拟一遍，只要出现“某个数出栈时，比它小的数还没出栈且被压在它下面”，这个序列就不合法。比如 4、1、2、3 不可能，因为 4 先出栈说明 1、2、3 都在栈里，出栈顺序必须是 3、2、1。

第四题：一棵二叉树有 10 个度为 2 的结点，叶子结点有多少个。直接套 n0 = n2 + 1，答案是 11。这道题不用画图，画图反而浪费时间。

第五题：从 6 个不同元素中取 3 个，要求至少包含某一个指定元素，有多少种取法。正面算是 C(5, 2) = 10，反过来算是 C(6, 3) - C(5, 3) = 20 - 10 = 10。两种算法互相验证，是考场上最省时间的检查方式。

3. 阅读程序题：三段式拆解与三类高频模型

3.1 三段式：定输入、走变量、卡边界

阅读程序给的是 15 到 30 行代码，后面跟 6 个小题，判断题问“输入为某值时输出是否为某值”“把某行改成另一种写法结果是否改变”，选择题问“时间复杂度”“输出结果”“循环执行次数”。

固定动作分三段。

第一段定输入。看cin读几个数、什么类型、有没有范围提示。输入范围决定了三件事：会不会溢出（int 还是 long long）、循环能不能跑完（指数级递归遇到 n = 40 必然超时）、数组够不够大。

第二段走变量。找循环不变量，也就是每一轮开始时恒成立的那个关系。比如“前 i 个元素已经有序”“f[i] 表示前 i 个数的方案数”。找到不变量，代码就不用逐行读。

第三段卡边界。n = 0、n = 1、全相同、全逆序、负数、最大值。判断题有相当一部分就是拿边界值来设陷阱。

注意：阅读程序的选择题里出现“一定”“必然”这种词，先怀疑，再看有没有反例。

3.2 循环与数组类：冒泡排序的交换次数

这是阅读程序里出现频率最高的一类结构，2020 年两卷都有类似的循环嵌套题。

#include <iostream> using namespace std; int a[1005], n, cnt; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n - 1; i++) { // 外层：每轮把一个最大值送到末尾 for (int j = 1; j <= n - i; j++) { // 内层：已排好的尾部不再比较 if (a[j] > a[j + 1]) { // 严格大于才交换 swap(a[j], a[j + 1]); cnt++; // cnt 累计交换次数 } } } cout << cnt << endl; return 0; }

逻辑说明：外层循环控制轮数，共 n - 1 轮；内层上界是 n - i，因为第 i 轮结束时末尾 i 个元素已经有序，再比较就是浪费。cnt记录的是交换次数，而在冒泡排序中，交换次数恰好等于原序列的逆序对数量，这个结论是选择题的高频答案。

参数说明：数组开 1005 是按题目给定的 n 不超过 1000 留的余量，考场上看到 n 的范围一定要回头核对数组大小，越界在纸面上不报错，但答案会错。

判断题常见的两种改法要特别小心。第一种把a[j] > a[j + 1]改成a[j] >= a[j + 1]，排序结果不变，但相等元素也会交换，cnt变大，所以“输出不变”是错的。第二种在两层循环之间加一个bool flag，每轮检查有没有发生交换、没有就break，这时最好情况复杂度从 O(n²) 降为 O(n)，但逆序对数量的结论依然成立。

时间复杂度：外层 n 轮、内层平均 n/2 次，总共 O(n²)，与输入是否有序无关（没加提前退出）。空间复杂度 O(n)，因为开了数组。这两问几乎每篇阅读程序都会有一道。

3.3 递归类：调用次数与指数爆炸

#include <iostream> using namespace std; int f(int n) { if (n <= 1) return n; // 递归出口：f(0)=0，f(1)=1 return f(n - 1) + f(n - 2); // 每层拆成两个子问题 } int main() { int n; cin >> n; cout << f(n) << endl; return 0; }

逻辑说明：这是最朴素的斐波那契递归写法，f(n)的值是第 n 项，但真正要考的不是值，而是调用规模。f(n)展开后形成一棵二叉树，结点总数约为 2^n，所以时间复杂度是 O(2^n)，空间复杂度是递归栈深度 O(n)。

参数说明：n用 int 就够，因为 n 超过 45 时结果会超出 int 范围，但程序本身在 n = 40 左右就已经跑不完了，所以题目通常不会问大数的值，而是问“n = 40 时能否在 1 秒内结束”——答案是不能，指数级增长在 n = 40 时已经是万亿次量级。

判断题常见的坑：把if (n <= 1)改成if (n < 1)，此时 n = 1 会继续递归到 f(0) + f(-1)，f(-1) 又继续往下，栈溢出，程序行为完全改变。这种“改一个不等号”的题，一定要代入边界值实际走一遍。

另一类递归题是“递归求二进制中 1 的个数”或“递归求最大公约数”，结构简单但问法刁钻，比如“把递归改成循环，时间复杂度会不会变”。答案是不会，递归和循环只是写法差别，量级取决于循环次数，不取决于写法。

3.4 位运算与字符串类：逐位拆解

#include <iostream> using namespace std; int main() { int n, ans = 0; cin >> n; while (n) { n = n & (n - 1); // 每次消掉最低位的 1 ans++; // 消几次就有几个 1 } cout << ans << endl; return 0; }

逻辑说明：n & (n - 1)的作用是把 n 的二进制表示中最低位的 1 变成 0，其余位不变。循环每执行一次消掉一个 1，所以ans最终等于 n 的二进制中 1 的个数。循环次数等于 1 的个数，最坏情况（n 全是 1）是 O(log n)，因为 n 的二进制位数是 log n 级别。

参数说明：如果 n 是负数，在补码表示下最高位是 1，这个算法会把符号位也算进去，答案变成 32 或 64。所以题目一定会给 n 是正整数的范围，看到“正整数”三个字要留意，这往往是判断题的考点。

字符串类阅读程序的处理方式不同，重点看三处：字符数组有没有留'\0'的位置、strlen是在循环条件里调用还是提前算好、下标从 0 开始还是从 1 开始。strlen放在for条件里会导致 O(n²) 复杂度，这是选择题的常客。

3.5 判断题的答题口径：错在哪才算错

判断题的表述往往是“当输入为 X 时，输出为 Y”，判错的标准是“程序实际行为与描述不符”，而不是“描述里的数字算错了”。所以做判断题的正确顺序是：先按描述跑一遍程序，看输出对不对；如果输出对，再看描述里有没有额外的限定词（“一定”“仅”“最多”）。

最常见的三种错法：把“第 3 行输出”看成“输出 3”；把“最多执行 n 次”看成“恰好执行 n 次”；把“结果不变”看成“过程不变”。改一个比较符号通常结果不变但过程变了，改一个初值通常过程不变但结果变了，这两种要分清。

还有一类是“复杂度判断”判断题，比如“这段程序的时间复杂度是 O(n log n)”。判断依据是循环层数与每层规模，双重循环且内层规模随外层缩小（如 n、n-1、n-2……）是 O(n²)，内层规模固定减半是 O(n log n)，只有一层且规模减半是 O(log n)。这三个量级每年都有人搞混。

4. 完善程序题：五空填空的答题顺序与两类高频模型

4.1 空位分三类：边界空、递推空、初始化空

完善程序题面一定有一段中文说明，讲清楚这段代码要解决什么问题、用什么算法。很多人上来就看代码，结果读了十分钟还不知道在干什么。正确顺序是：先读中文说明，再扫一遍代码骨架，最后把 5 个空分类。

边界空：循环条件、数组下标、递归出口。判断依据是“这个循环要跑几次”“这个数组要用到第几位”。看到i < n和i <= n要停顿一下，看题目里是 0 下标还是 1 下标。

递推空：状态转移方程、累加式、比较式。判断依据是“这一步要用到前面哪几个状态”。01 背包是f[j] = max(f[j], f[j - w[i]] + v[i])，最长上升子序列是f[i] = max(f[i], f[j] + 1)，这些式子的结构是固定的。

初始化空：dp 数组初值、ans 初值、计数器清零。这类空最容易填，也最容易错。求最小值时 ans 要初始化为一个大数，求最大值时初始化为 0 或 -1，求方案数时f[0] = 1。

答题顺序建议从最有把握的空开始，不要按 1 到 5 的顺序填。填完一个空就在草稿纸上标一下，避免后面改前面的。

4.2 二分与双指针模型

// 在升序数组 a[1..n] 中找第一个大于等于 x 的位置 int l = 1, r = n, ans = n + 1; // ans 初值设为"不存在"的位置 while (l <= r) { int mid = l + (r - l) / 2; // 防溢出写法 if (a[mid] >= x) { ans = mid; // 记录当前可行解 r = mid - 1; // 继续往左找更小的 } else { l = mid + 1; // 当前太小，往右找 } }

逻辑说明：这是“找下界”的标准二分。ans记录当前找到的可行位置，每找到一个更靠左的就更新。循环结束时ans就是第一个大于等于 x 的位置，如果始终没找到，ans保持 n + 1。

参数说明：mid写成l + (r - l) / 2而不是(l + r) / 2，是为了防止 l 和 r 都接近 int 上限时相加溢出。考场上如果题目数据范围不大，两种写法结果一样，但填空处给的形式往往是防溢出写法，因为出题人想考这个点。

完善程序里二分题的填空通常落在三个位置：ans的初值、r = mid - 1还是r = mid、l = mid + 1还是l = mid。判断方法看循环条件：while (l <= r)配mid ± 1，while (l < r)配mid或mid + 1。两种模板不能混用，混用就是死循环。

4.3 搜索与动态规划模型

// 01 背包：n 件物品，容量 m，求最大价值 for (int i = 1; i <= n; i++) { for (int j = m; j >= w[i]; j--) { // 必须倒序 f[j] = max(f[j], f[j - w[i]] + v[i]); } }

逻辑说明：外层枚举物品，内层枚举容量。倒序枚举容量保证每件物品只被选一次，因为计算f[j]时用到的f[j - w[i]]还是上一轮（没选当前物品）的值。

参数说明：如果内层改成正序for (int j = w[i]; j <= m; j++)，f[j - w[i]]可能已经在本轮被更新过，等于同一件物品被选了多次，那就变成了完全背包。这个“正序还是倒序”的填空，几乎是每套完善程序的常客，也是最容易失分的地方。

搜索类完善程序通常是 DFS 或 BFS 的框架，填空落在三处：递归出口（边界判断）、状态标记（vis[x] = 1）和回溯（vis[x] = 0）。判断依据是“这个点能不能重复走”。如果题目说“每个点只能走一次”，就必须有回溯或标记；如果是有向无环图，标记可以省。

4.4 填完之后的自检清单

五个空填完，不要立刻涂卡，按下面四步过一遍。

第一步，用最小规模手算。n = 1、n = 2、只有一个元素、空数组，把这几种情况代进去，看代码会不会越界、会不会死循环、输出是否符合预期。

第二步，查数组下标。题目给的数组是a[1..n]还是a[0..n-1]，循环从 1 开始还是从 0 开始，这两件事必须前后一致，中间改一个就是全错。

第三步，查变量初始化。ans、cnt、f[0]有没有赋值，全局变量默认是 0，局部变量不初始化是随机值，考场上不报错但答案错。

第四步，查数据类型。累加、累乘、方案数统计这三类，很容易超过 int 范围，题目数据范围里出现 10^9 就要考虑 long long。

5. 易错点：五类每年都有人栽的题

5.1 错在循环边界：把 n - 1 当成 n

错在哪：阅读程序里数循环执行次数，看到for (int i = 1; i <= n - 1; i++)就填 n，正确应该是 n - 1。为什么错：C++ 的循环条件是“小于等于”还是“小于”，很多人在纸上读代码时自动脑补成自己习惯的写法，尤其是代码里同时出现i < n和i <= n时，眼睛会跳过符号。怎么答对：每读到一个循环，先在草稿纸上写一遍“i 从几到几，共几次”，把上界单独抄下来，再开始推逻辑，不要心算。

5.2 错在稳定性：把快排记成稳定

错在哪：选择题问“下列排序算法中稳定的是”，把快速排序选进去。为什么错：快排的交换是跳跃式的，相同元素可能在交换中被跨过去，前后顺序变了。很多人只记“快排很快”，没记“快排不稳定”。怎么答对：用一句话做判断标准，交换只发生在相邻位置的是稳定排序（冒泡、插入、归并），交换跨越中间元素的是不稳定排序（选择、快排、堆排）。考场上用这一句话现推，比背表格可靠。

5.3 错在 01 背包正序：把完全背包当 01 背包

错在哪：完善程序里内层循环写成for (int j = w[i]; j <= m; j++)，用正序枚举容量。为什么错：正序时f[j - w[i]]可能在本轮已经被更新过，相当于同一件物品被重复选取，01 背包成了完全背包，答案变大。这个错误在纸上不明显，只有手算小数据才会暴露。怎么答对：记住一条口诀，“01 倒序，完全正序”，倒序保证每一轮用的是上一层的状态。填完空之后拿 n = 1、m = w[1] 试一遍，如果答案等于v[1]就说明只选了一次，如果大于就说明重复选了。

5.4 错在复杂度量级：把 O(n log n) 写成 O(log n)

错在哪：看到二分就写 O(log n)，看到排序就写 O(log n)，看到两层循环就写 O(n)。为什么错：复杂度看的是“基本操作执行了多少次”，不是“代码有几层”。二分查找是每次范围减半，执行 log n 次，所以是 O(log n)；归并排序每层合并 n 次、共 log n 层，所以是 O(n log n)；两层循环且内层每轮减半，是 O(n log n) 而不是 O(n²)。怎么答对：先数层数，再看每层的规模。每层规模都是 n 就是 O(n²)，每层规模减半就是 O(n log n)，只有一层且规模减半就是 O(log n)。三个量级对应三种结构，不要混。

5.5 错在判断题的“一定”：把可能当成必然

错在哪：判断题说“当输入为某值时，程序一定会输出某值”，实际上程序在该输入下行为未定义或依赖随机值。为什么错：全局数组默认初始化为 0，局部数组不会，int溢出是未定义行为，swap相同元素时结果不变但过程变了。题目里只要出现“一定”“必然”“任何情况下”，都要找一个反例。怎么答对：判断题遇到绝对化表述，先找边界值（n = 0、n = 1、全相同、最大值），能举出一个反例就判错，举不出来再判对。这个顺序反过来，就会把“可能”当成“一定”。

6. 考场上的答题顺序与押题思路

我的习惯是：拿到卷子先花 90 秒把三种题型的分值和题量扫一遍，确认阅读程序的判断题、选择题各几分，然后按“单选 → 完善程序 → 阅读程序”的顺序做。

单选放在最前面，因为它最快、最容易进状态，25 分钟内必须结束。完善程序放在第二位，因为题面有中文说明，读完说明就能抓住算法框架，五个空里通常有两到三个是“送分空”（初始化、边界条件），先把这些填掉，心里就有底了。阅读程序放最后，因为它最耗时，一篇阅读程序的手算量可能顶三道单选，而且判断题的容错率低，状态不好时容易连续错。

押题思路按 2020 年两卷的分布看，阅读程序集中在三类结构：循环嵌套模拟（冒泡、选择、前缀和）、递归（斐波那契型、分治型、DFS 型）、位运算或字符串处理（lowbit、popcount、字符数组遍历）。完善程序集中在两类模型：二分或双指针（找下界、找第一个满足条件的位置）、动态规划或搜索（01 背包、最长上升子序列、DFS 标记回溯）。这五类结构覆盖了卷面上八成的代码题，进考场前把这五类各手写一遍，比刷十套卷子管用。

还有一个容易被忽略的点：时间分配要留出 10 分钟填涂和回查。我见过太多人最后五分钟才开始涂卡，结果涂串行。从那以后我每次做完一个题型就涂一次卡，单选涂完涂阅读，阅读涂完涂完善，最后 10 分钟只做检查，不碰新题。

希望帮到你。

本文还有配套的精品资源，点击获取