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比特1Byte8bit。存储容量换算里1KB(2^{10})B1MB(2^{20})B1GB(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(ji; jn; j)那总次数就是n(n-1)...1 n(n1)/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(ne)其中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[k1][j] cost(i,j))其中cost(i,j)是把两个子区间合并的代价。做区间DP题有个口诀“先枚举区间长度再枚举区间起点最后枚举分割点”。这个顺序不能乱因为计算长区间的时候需要用到短区间的结果所以必须从短到长计算。这道题还考了一个细节DP数组的初始值应该设成什么。如果是求最小值初始值应该设成一个很大的数比如0x3f3f3f3f如果是求最大值初始值应该设成一个很小的数。初始值设错了整个DP就全错了。5. 常见问题与避坑指南带学生刷CSP-J 2020这套卷子的时候我发现有些错误是反复出现的。下面我把这些问题整理出来配上排查思路和解决方法希望能帮大家少走弯路。5.1 单选题高频错误错误类型典型表现原因分析解决方法进制转换方向搞反二进制转十六进制时从左边分组没有养成“从右往左”的习惯记住口诀右起分组不够补零补码还原忘记加1取反后直接当结果对补码的定义理解不透补码转真值取反加一符号位不变排序稳定性记混把快排当成稳定排序只背结论不理解原理理解快排分区会打乱相对顺序时间复杂度数错循环次数嵌套循环直接相乘忽略内层循环依赖外层变量写出求和公式不要凭感觉5.2 阅读程序题常见陷阱阅读程序题最大的陷阱是“看起来像但实际不是”。比如代码里写了一个for循环看起来是遍历整个数组但循环条件里有个i n-1少遍历了最后一个元素。这种细节如果不注意模拟出来的结果就全错了。另一个常见陷阱是变量的作用域。CSP-J的代码里经常有全局变量和局部变量同名的现象函数内部修改的是局部变量但学生以为是全局变量结果模拟出来的值跟实际不符。读代码的时候看到变量先确认它是全局的还是局部的这个习惯能帮你避开很多坑。还有一点数组越界。CSP-J的代码有时候会故意写一个越界的访问问你会发生什么。在C里数组越界是未定义行为可能崩溃也可能读到垃圾值。但初赛一般不会考这种“未定义行为”如果出现了通常是题目在暗示你“这个循环条件有问题”。5.3 完善程序题丢分原因完善程序题丢分主要有三个原因一是没看懂程序要干什么二是看懂了但找不到对应的选项三是找到了选项但填错了位置。第一个原因最好解决先看题目描述知道程序的功能是什么然后再去看代码。第二个原因需要你对常见的算法模板比较熟悉比如字符串替换、区间DP、二分查找这些看到代码结构就能联想到对应的模板。第三个原因最可惜通常是粗心导致的比如把i和j搞混了或者把1和-1写反了。我的建议是做完完善程序题后把你选的选项代回代码里从头到尾快速读一遍看看逻辑是否通顺。这个检查过程花不了两分钟但能帮你抓住大部分低级错误。提示完善程序题的选项里通常会有一些“看起来很像”的干扰项比如dp[i][k] dp[k1][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%以上。
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比特1Byte8bit。存储容量换算里1KB(2^{10})B1MB(2^{20})B1GB(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(ji; jn; j)那总次数就是n(n-1)...1 n(n1)/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(ne)其中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[k1][j] cost(i,j))其中cost(i,j)是把两个子区间合并的代价。做区间DP题有个口诀“先枚举区间长度再枚举区间起点最后枚举分割点”。这个顺序不能乱因为计算长区间的时候需要用到短区间的结果所以必须从短到长计算。这道题还考了一个细节DP数组的初始值应该设成什么。如果是求最小值初始值应该设成一个很大的数比如0x3f3f3f3f如果是求最大值初始值应该设成一个很小的数。初始值设错了整个DP就全错了。5. 常见问题与避坑指南带学生刷CSP-J 2020这套卷子的时候我发现有些错误是反复出现的。下面我把这些问题整理出来配上排查思路和解决方法希望能帮大家少走弯路。5.1 单选题高频错误错误类型典型表现原因分析解决方法进制转换方向搞反二进制转十六进制时从左边分组没有养成“从右往左”的习惯记住口诀右起分组不够补零补码还原忘记加1取反后直接当结果对补码的定义理解不透补码转真值取反加一符号位不变排序稳定性记混把快排当成稳定排序只背结论不理解原理理解快排分区会打乱相对顺序时间复杂度数错循环次数嵌套循环直接相乘忽略内层循环依赖外层变量写出求和公式不要凭感觉5.2 阅读程序题常见陷阱阅读程序题最大的陷阱是“看起来像但实际不是”。比如代码里写了一个for循环看起来是遍历整个数组但循环条件里有个i n-1少遍历了最后一个元素。这种细节如果不注意模拟出来的结果就全错了。另一个常见陷阱是变量的作用域。CSP-J的代码里经常有全局变量和局部变量同名的现象函数内部修改的是局部变量但学生以为是全局变量结果模拟出来的值跟实际不符。读代码的时候看到变量先确认它是全局的还是局部的这个习惯能帮你避开很多坑。还有一点数组越界。CSP-J的代码有时候会故意写一个越界的访问问你会发生什么。在C里数组越界是未定义行为可能崩溃也可能读到垃圾值。但初赛一般不会考这种“未定义行为”如果出现了通常是题目在暗示你“这个循环条件有问题”。5.3 完善程序题丢分原因完善程序题丢分主要有三个原因一是没看懂程序要干什么二是看懂了但找不到对应的选项三是找到了选项但填错了位置。第一个原因最好解决先看题目描述知道程序的功能是什么然后再去看代码。第二个原因需要你对常见的算法模板比较熟悉比如字符串替换、区间DP、二分查找这些看到代码结构就能联想到对应的模板。第三个原因最可惜通常是粗心导致的比如把i和j搞混了或者把1和-1写反了。我的建议是做完完善程序题后把你选的选项代回代码里从头到尾快速读一遍看看逻辑是否通顺。这个检查过程花不了两分钟但能帮你抓住大部分低级错误。提示完善程序题的选项里通常会有一些“看起来很像”的干扰项比如dp[i][k] dp[k1][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%以上。
