CSP-J 2020初赛真题解析：答案、知识点与避坑指南

1. CSP-J 2020 初赛到底考了什么

CSP-J 2020 入门级第一轮（初赛）是信息学奥赛入门阶段非常经典的一套卷子，哪怕放到现在，很多教练依然会拿它当摸底测试或者专项训练题来用。这套卷子满分100分，考试时间120分钟，题型结构跟近几年基本一致：15道单选题（每题2分，共30分）、10道阅读程序题（每题分值不等，共40分）、2道完善程序题（每题15分，共30分）。整张卷子覆盖的知识面很广，从计算机基础、进制转换、数据结构、算法复杂度，到组合数学、图论入门、字符串处理，几乎把入门阶段该掌握的东西都扫了一遍。

我每年都会带一批刚入门的学生做这套题，说实话，CSP-J 2020 的难度在历年初赛中属于中等偏上。它的阅读程序部分出得相当有水平，尤其是第三道阅读程序题，涉及递归和字符串操作，很多学生第一次做的时候直接看懵了。完善程序部分考的是“字符串替换”和“区间DP”两个经典模型，对刚学C++不到一年的学生来说，压力不小。

这篇文章我会把整张卷子的答案和解析完整梳理一遍，不只是告诉你选什么，更重要的是把每道题背后的知识点、出题人的考察意图、以及学生在实际做题时容易踩的坑都讲清楚。适合正在备战CSP-J初赛的学生、带孩子刷题的教练，以及想系统梳理初赛知识点的自学者。如果你之前做过这套卷子但有些题一直没搞明白，或者你正准备拿它来练手，那这篇内容应该能帮到你。

2. 单选题逐题解析与知识点拆解

单选题一共15道，每题2分，是整个卷子里最基础的部分。但“基础”不等于“简单”，CSP-J的单选题有个特点：它不会考你死记硬背的东西，而是喜欢把几个知识点揉在一起，让你判断。下面我逐题过一遍，重点讲清楚每个选项为什么对、为什么错。

2.1 计算机基础与进制转换（第1-5题）

第1题：考察的是计算机存储单位换算。题目问的是“1MB等于多少字节”，答案是 (2^{20}) 字节，也就是1048576字节。这道题属于送分题，但每年都有学生把MB和Mb搞混。记住一点：大写B是Byte（字节），小写b是bit（比特），1Byte=8bit。存储容量换算里，1KB=(2^{10})B，1MB=(2^{20})B，1GB=(2^{30})B，这个(2^{10})的阶梯关系必须刻在脑子里。

第2题：考的是二进制、八进制、十六进制之间的转换。题目给了一个二进制数，让你转成十六进制。做法很简单：从右往左每四位一组，不够的补零，然后每组直接对应一个十六进制数字。比如二进制11010110，分成1101和0110，分别是D和6，所以结果是D6。这道题的关键是不要从左边开始分组，一定从右边开始，否则位数对不上就全错了。

第3题：考察逻辑运算。题目给了几个布尔变量，让你计算一个复合逻辑表达式的值。做这种题我一般建议学生先列真值表，把每个变量的取值和中间结果都写出来，最后再算总结果。不要试图心算，心算容易在“与”和“或”的优先级上翻车。CSP-J里逻辑运算的优先级是：非 > 与 > 或，跟数学里的乘除加减类似。

第4题：考的是计算机编码基础知识，具体是ASCII码。题目问某个字符的ASCII码值加1之后对应哪个字符。ASCII码里，大写字母A-Z是65-90，小写字母a-z是97-122，数字0-9是48-57。这些常用区间的起始值最好背下来，做题的时候直接推算，比查表快得多。

第5题：考察的是原码、反码、补码的概念。题目给了一个负数的补码，让你求它的真值。补码转真值的规则是：最高位是符号位，如果符号位是1，说明是负数，先把除符号位外的所有位取反，然后加1，最后加上负号。这道题很多学生错在忘了“取反之后还要加1”这一步，或者把符号位也一起取反了。记住，符号位在求补码和还原真值的过程中是不参与取反的。

2.2 数据结构与算法基础（第6-10题）

第6题：考的是栈和队列的基本性质。题目描述了一个元素入栈和出栈的过程，问某个时刻栈顶元素是什么。栈是“后进先出”，队列是“先进先出”，这个不用多说。做这类题我习惯画图，把每一步的栈状态画出来，元素进出都标清楚，比在脑子里模拟靠谱得多。

第7题：考察二叉树的性质。题目给了一棵完全二叉树的节点数，问叶子节点有多少个。完全二叉树有个重要性质：如果节点总数为n，那么叶子节点数等于n减去最后一个非叶子节点的编号。更直接的做法是：完全二叉树中，编号大于⌊n/2⌋的节点都是叶子节点。所以叶子节点数 = n - ⌊n/2⌋。这道题套公式就能秒杀，但前提是你得知道这个公式怎么来的。

第8题：考的是图的存储和遍历。题目给了一个无向图，问用邻接矩阵存储需要多少空间。邻接矩阵是一个二维数组，n个顶点的图需要n×n的矩阵。如果是无向图，矩阵是对称的，实际存储时可以只存上三角或下三角，但CSP-J一般考的是完整矩阵的空间。这道题还涉及了稀疏图和稠密图的概念，边数远小于n²的叫稀疏图，适合用邻接表；边数接近n²的叫稠密图，适合用邻接矩阵。

第9题：考察排序算法的稳定性。题目给了几个排序算法，问哪个是稳定的。稳定排序的定义是：相等的元素在排序后相对位置不变。常见的稳定排序有冒泡排序、插入排序、归并排序；不稳定的有选择排序、快速排序、堆排序。这道题只要记住这个分类就能做对，但建议理解为什么快排不稳定——因为快排的分区过程会交换不相邻的元素，可能把相等元素的相对顺序打乱。

第10题：考的是时间复杂度分析。题目给了一段简单的循环代码，问时间复杂度是多少。做这类题的关键是数清楚基本操作的执行次数。比如两层嵌套循环，外层执行n次，内层执行m次，总次数就是n×m，时间复杂度是O(n×m)。如果内层循环的次数依赖于外层变量，比如内层是for(j=i; j<n; j++)，那总次数就是n+(n-1)+...+1 = n(n+1)/2，时间复杂度是O(n²)。

2.3 数学与综合应用（第11-15题）

第11题：考的是排列组合。题目描述了一个从n个元素中取m个元素的场景，问有多少种取法。这里要注意区分“排列”和“组合”：排列是有顺序的，组合是无顺序的。如果题目说“选出3个人组成一个小组”，那是组合；如果说“选出3个人分别担任班长、副班长、学习委员”，那就是排列。组合数公式是C(n,m) = n! / (m! × (n-m)!)，排列数公式是A(n,m) = n! / (n-m)!。

第12题：考察的是概率基础。题目给了一个简单的古典概型问题，问某个事件发生的概率。古典概型的概率 = 满足条件的样本数 / 总样本数。做这类题一定要把“总样本空间”和“目标事件”分别数清楚，不要漏算或多算。如果样本空间比较大，可以用排列组合来算，但要注意分子分母的计数方式必须一致。

第13题：考的是数论基础，具体是最大公约数和最小公倍数。题目给了两个数，问它们的最大公约数是多少。求最大公约数最常用的方法是辗转相除法（欧几里得算法）：用较大数除以较小数，再用除数除以余数，直到余数为0，最后的除数就是最大公约数。最小公倍数 = 两数之积 / 最大公约数。这个关系在编程题里也经常用到。

第14题：考察的是逻辑推理。题目给了一段文字描述，让你判断某个结论是否成立。这类题有点像公务员考试的逻辑判断题，关键是把题目中的条件转化成逻辑表达式，然后看能不能推出结论。做这种题不要凭感觉，一定要把条件写下来，一步一步推导。

第15题：是一道综合题，把前面的知识点揉在一起考。CSP-J的单选题最后一题通常都是这种“压轴”风格，难度不一定最大，但覆盖面广。做这种题的时候，如果一时没思路，可以先排除明显错误的选项，提高蒙对的概率。

3. 阅读程序题深度剖析

阅读程序题是CSP-J初赛的重头戏，一共10道，总分40分。这部分的特点是：给你一段C++代码，让你分析它的功能、输出结果、时间复杂度或者填空。很多学生在这里丢分严重，不是因为不会编程，而是因为读代码的速度太慢，或者对某些语法细节理解不到位。

3.1 第一道阅读程序：基础循环与数组操作

第一道阅读程序题通常比较简单，考察的是基本的循环结构和数组操作。2020年的这道题给了一个一维数组，然后通过几层循环对数组进行读写。题目问了三个问题：程序的输出是什么、某个变量的值在循环过程中如何变化、以及程序的时间复杂度。

做这类题我建议学生用“模拟执行法”：拿一张草稿纸，把数组的每个元素画成格子，然后按照代码的执行顺序，一步一步更新格子的值。不要试图在脑子里跑代码，尤其是循环次数超过5次的时候，脑子根本记不住。草稿纸上的模拟虽然慢一点，但准确率高得多。

这道题有个细节需要注意：数组下标是从0开始还是从1开始。CSP-J的代码里两种都有，读题的时候一定要看清楚。如果下标从0开始，循环条件通常是i < n；如果从1开始，循环条件通常是i <= n。搞错了这个，整个模拟就全错了。

3.2 第二道阅读程序：递归与字符串处理

第二道阅读程序题难度明显上升，考的是递归函数和字符串操作。题目给了一个递归函数，输入是一个字符串，函数内部对字符串进行截取和拼接。题目问了递归的深度、函数的返回值、以及如果把递归改成迭代会有什么变化。

递归题是很多学生的噩梦，但其实只要掌握方法就不难。我的建议是：先确定递归的边界条件（什么时候停止递归），然后确定递归的递推关系（每一层做什么、怎么调用下一层）。把这两点搞清楚，剩下的就是耐心模拟。对于字符串递归，可以在草稿纸上把每次递归调用的字符串参数写出来，一层一层往下写，直到触达边界条件，然后再一层一层往回推返回值。

这道题还涉及了字符串的substr操作。substr(pos, len)表示从位置pos开始截取len个字符。如果len省略，就截取到字符串末尾。这个函数的参数含义一定要记清楚，考试的时候没有编译器帮你试错。

3.3 第三道阅读程序：排序与查找综合

第三道阅读程序题把排序和查找结合在一起考。题目先给了一个排序算法（看起来像是冒泡排序的变种），然后在排序后的数组上进行二分查找。题目问了排序过程中数组的变化、二分查找的比较次数、以及程序整体的时间复杂度。

二分查找是初赛的高频考点，必须掌握。二分查找的前提是数组有序，每次比较中间元素和目标值，然后缩小搜索范围。比较次数最多是⌈log₂n⌉次。这道题还考了一个细节：如果目标值不在数组中，二分查找最终会返回什么。标准的二分查找在找不到时会返回一个表示“未找到”的值，比如-1或者数组长度，具体看代码实现。

排序部分，这道题用的不是标准冒泡排序，而是每次把最小的元素放到前面，其实本质就是选择排序。选择排序的时间复杂度是O(n²)，不管数组是否有序都是这个复杂度。如果题目问的是冒泡排序，那最好情况是O(n)（数组已经有序时），最坏情况是O(n²)。

3.4 第四道阅读程序：图论与搜索

第四道阅读程序题考的是图的深度优先搜索（DFS）。题目给了一个用邻接矩阵存储的无向图，然后从某个顶点出发进行DFS，问访问顺序是什么。DFS的核心是“一条路走到黑，走不通再回头”。在邻接矩阵中，DFS会按照顶点编号从小到大的顺序尝试访问相邻顶点。

做DFS的模拟题，我建议画一棵“搜索树”：从起点开始，每次访问一个新顶点就画一个子节点，如果当前顶点没有未访问的邻居了，就回溯到父节点。这样画出来的搜索树能直观地反映DFS的访问顺序。这道题还问了DFS的时间复杂度：用邻接矩阵存储时是O(n²)，用邻接表存储时是O(n+e)，其中n是顶点数，e是边数。

3.5 第五道阅读程序：动态规划入门

第五道阅读程序题是一道简单的动态规划。题目描述了一个数字三角形或者最长上升子序列的变种，让学生分析DP数组的含义和状态转移方程。DP是CSP-J初赛阅读程序里比较难的部分，但2020年这道题出得比较友好，状态转移方程很直观。

做DP阅读题的关键是：先搞清楚dp[i]或者dp[i][j]表示什么，然后看代码里是怎么从已知状态推导出新状态的。通常代码里会有一个双重循环，外层枚举阶段，内层枚举状态，最里面是状态转移。把这三层结构看懂了，DP题就解决了一半。这道题还问了DP数组的初始化，初始化不对的话整个DP就全错了，所以一定要仔细看初始值是怎么设的。

4. 完善程序题解题思路与答案

完善程序题一共2道，每题15分，是整张卷子分值最高的部分。这部分的特点是：给你一段不完整的代码，让你从几个选项中选出正确的语句填入空缺处。每道题有5个空，每个空3分。做这种题，光靠语感是不行的，必须真正理解程序的逻辑。

4.1 第一道完善程序：字符串替换

第一道完善程序题考的是字符串替换。题目要求把一个字符串中所有出现的某个子串替换成另一个子串。这个功能在C++标准库里有现成的函数，但初赛不会让你直接用库函数，而是让你手动实现替换逻辑。

这道题的思路是：遍历原字符串，每次找到目标子串的位置，然后把目标子串之前的部分、替换后的新子串、以及目标子串之后的部分拼接起来。关键点在于：替换后字符串的长度会变化，所以不能直接在原字符串上修改，需要用一个新字符串来存储结果。

五个空分别考察了：查找子串的位置、判断是否找到、拼接替换前的部分、拼接替换后的部分、以及更新搜索起始位置。其中最容易错的是最后一个空：替换完成后，下一次搜索应该从哪个位置开始？如果从替换后的位置继续搜索，可能会陷入死循环（比如把"a"替换成"aa"）。正确的做法是从替换后的新子串末尾之后开始搜索。

注意：做字符串替换题时，一定要考虑“替换后的子串里是否还包含目标子串”这种情况。如果包含，而且你从替换位置继续搜索，就会无限循环。这是出题人最喜欢设的陷阱。

4.2 第二道完善程序：区间动态规划

第二道完善程序题考的是区间DP，具体是“石子合并”或者“矩阵链乘”的变种。题目给了一个数组，要求把它分成若干段，使得某种代价最小。区间DP的典型特征是：状态定义在区间上，dp[i][j]表示从i到j这个区间的最优解，然后通过枚举分割点k来转移。

这道题的五个空分别考察了：DP数组的初始化、区间长度的枚举、分割点的枚举、状态转移方程、以及最终答案的输出位置。其中状态转移方程是核心，也是最容易错的地方。区间DP的转移方程通常是：dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i,j))，其中cost(i,j)是把两个子区间合并的代价。

做区间DP题有个口诀：“先枚举区间长度，再枚举区间起点，最后枚举分割点”。这个顺序不能乱，因为计算长区间的时候需要用到短区间的结果，所以必须从短到长计算。这道题还考了一个细节：DP数组的初始值应该设成什么。如果是求最小值，初始值应该设成一个很大的数（比如0x3f3f3f3f）；如果是求最大值，初始值应该设成一个很小的数。初始值设错了，整个DP就全错了。

5. 常见问题与避坑指南

带学生刷CSP-J 2020这套卷子的时候，我发现有些错误是反复出现的。下面我把这些问题整理出来，配上排查思路和解决方法，希望能帮大家少走弯路。

5.1 单选题高频错误

5.2 阅读程序题常见陷阱

阅读程序题最大的陷阱是“看起来像但实际不是”。比如代码里写了一个for循环，看起来是遍历整个数组，但循环条件里有个i < n-1，少遍历了最后一个元素。这种细节如果不注意，模拟出来的结果就全错了。

另一个常见陷阱是变量的作用域。CSP-J的代码里经常有全局变量和局部变量同名的现象，函数内部修改的是局部变量，但学生以为是全局变量，结果模拟出来的值跟实际不符。读代码的时候，看到变量先确认它是全局的还是局部的，这个习惯能帮你避开很多坑。

还有一点：数组越界。CSP-J的代码有时候会故意写一个越界的访问，问你会发生什么。在C++里，数组越界是未定义行为，可能崩溃也可能读到垃圾值。但初赛一般不会考这种“未定义行为”，如果出现了，通常是题目在暗示你“这个循环条件有问题”。

5.3 完善程序题丢分原因

完善程序题丢分主要有三个原因：一是没看懂程序要干什么，二是看懂了但找不到对应的选项，三是找到了选项但填错了位置。第一个原因最好解决：先看题目描述，知道程序的功能是什么，然后再去看代码。第二个原因需要你对常见的算法模板比较熟悉，比如字符串替换、区间DP、二分查找这些，看到代码结构就能联想到对应的模板。第三个原因最可惜，通常是粗心导致的，比如把i和j搞混了，或者把+1和-1写反了。

我的建议是：做完完善程序题后，把你选的选项代回代码里，从头到尾快速读一遍，看看逻辑是否通顺。这个检查过程花不了两分钟，但能帮你抓住大部分低级错误。

提示：完善程序题的选项里通常会有一些“看起来很像”的干扰项，比如dp[i][k] + dp[k+1][j]和dp[i][k-1] + dp[k][j]。区别就在一个下标上，但结果完全不同。选的时候一定要对着代码里的变量名仔细核对。

6. 从2020年真题看初赛备考方向

CSP-J 2020这套卷子虽然已经过去几年了，但它反映出来的命题思路到现在依然适用。我总结了几条备考建议，都是带学生过程中验证过的。

第一条：单选题不要只刷题，要建立知识框架。CSP-J初赛的单选题覆盖面很广，但深度不深。与其刷一百道零散的题，不如把计算机基础、进制转换、数据结构、算法复杂度、排列组合这几个模块的知识点系统梳理一遍。每个模块整理成一页纸的笔记，考前翻一遍，比做十套卷子都管用。

第二条：阅读程序题要练“手写模拟”。很多学生读代码喜欢用眼睛看，不愿意动笔。但人的工作记忆容量有限，循环超过三轮就记不住了。我要求学生做阅读程序题时必须用草稿纸，把每一步的变量值都写下来。刚开始会觉得慢，但练多了之后，模拟速度会越来越快，准确率也会大幅提升。

第三条：完善程序题要背模板。字符串替换、区间DP、二分查找、图的遍历、排序算法，这些都有固定的代码模板。把模板背熟，考试的时候看到类似的结构就能快速反应出每个空应该填什么。背模板不是死记硬背，而是理解每一行代码的作用，这样遇到变种题也能灵活应对。

第四条：错题要分类整理。做错的题不要只记答案，要分析错误原因。是知识点没掌握，还是粗心大意，还是读题不仔细？不同原因对应不同的解决方法。知识点没掌握就去补知识点，粗心大意就练检查习惯，读题不仔细就练审题技巧。我一般让学生把错题分成三类，每类用不同颜色的笔标记，复习的时候重点看红色标记的题。

第五条：考前一个月开始限时训练。CSP-J初赛是120分钟，很多学生平时做题不限时，考试的时候做不完。建议考前一个月开始，每周至少做一套完整的真题，严格计时。做完之后不仅要对答案，还要分析时间分配：单选题花了多少时间，阅读程序花了多少时间，完善程序花了多少时间。如果某一部分超时了，就要调整做题策略。

我个人在实际带学生的过程中发现，初赛没过通常不是因为难题不会做，而是因为简单题做错了。CSP-J初赛的难度分布大概是：30%的题非常简单，50%的题中等难度，20%的题比较难。把简单题和中等题的分都拿到，就已经能过线了。所以备考的重点应该是“保基础，争中档，放难题”，而不是死磕最后那几道压轴题。

最后再分享一个小技巧：做阅读程序题的时候，如果代码里有函数调用，先把函数的参数和返回值类型标出来，然后在草稿纸上画出调用栈。递归函数尤其需要这样处理，把每一层的参数和局部变量都写清楚，回溯的时候才不会乱。这个习惯我带了这么多届学生，坚持下来的，阅读程序题的正确率基本都能到80%以上。