简介2024年信息学奥赛CSP-J初赛真题详解面向初中生、少儿编程学员和C爱好者帮助备考者系统把握入门组初赛命题脉络。资源包仅含1个docx文档大小约121KB但内容精炼覆盖2024年CSP-J初赛单项选择题、阅读程序题等真实题目每题均附答案和解析适合考前冲刺或日常查漏。文档重点剖析了32位int存储范围、格雷码、存储单位换算、进制转换、二分查找、栈与队列、无向图度数、二叉树遍历、排列组合、C基本数据类型与循环结构、操作系统识别等高频考点并在解析中穿插组合数学和图论方法帮助读者拓宽解题思路。借助这份分析考生可快速理解考点背后的计算机科学原理提升逻辑推理和代码阅读能力并通过错题对照明确复习重点。已有2593人学习使用是信息学奥赛入门阶段高性价比的参考资料。1. 2024年信息学奥赛CSP-J初赛真题考点拆解真正拉分的是70分代码题2024年CSP-J初赛单选题第1题直接问32位int的存储范围这几乎是明送分可每年都有考生在C和D选项之间反复纠结最后凭感觉选错。第2题把八进制、十六进制、二进制混在一个式子里看着像复杂计算实际先统一转成十进制再代入就结束。初赛总分100分单选30分、阅读程序40分、完善程序30分也就是说70分都在读代码和补代码光背知识点根本拿不稳必须按题型练手感。这篇围绕2024年CSP-J初赛真题展开把单选高频考点、阅读程序常见的三类模型、完善程序的补全套路逐题拆开最后单列易错点和答题顺序。适合正在备赛的初中生、带赛的教练也适合正在学少儿编程、准备往信奥方向转的学生尤其是已经学完C语法但刷题量不够、一读程序就发懵的选手。2. 单选高频考点int范围、进制换算、组合计数与数据结构的送分套路2.1 整型范围与进制计算先翻译再代入第1题答案选C。int占4字节共32位用补码表示时范围是-2^31到2^31-1对应十进制就是-2147483648到2147483647。选项A和B都把下界写成了-2147483647选项D又把上界多写了一位。这个考点的记忆方法很简单补码的负数比正数多一个下界的绝对值比上界大1。32位二进制中最高位是符号位剩余31位表示数值所以最大值是2^31-1最小值是-2^31不对称。第2题考的是混合进制计算答案A。表达式(148−10102)∗D16−11012里148是八进制D16中的D是十六进制里的1311012是二进制。先把它们分别转成十进制148按权展开是1×8412D16就是1311012是1×81×40×2113。代入原式得到(12-10)×13-132×13-1313。这类题的通用做法是看到带下标或字母的数字先统一转十进制再计算不要拿八进制数字直接当十进制算也不要看到D就当字母跳过。平时练习时把0到15的二进制、八进制、十六进制对照表默写一遍混算题基本不会丢分。2.2 组合与排列分类乘完再相加相邻捆绑要记牢第3题是典型的分类组合计数答案B。题干是10名员工分3个部门选4人且每个部门至少1人。因为只选4人必然有1个部门出2人另外两个部门各出1人。分三种情况A部门出2人B、C各出1人方案数是C(4,2)×C(3,1)×C(3,1)6×3×354B部门出2人A、C各出1人方案数是C(4,1)×C(3,2)×C(3,1)4×3×336C部门出2人A、B各出1人同样36。三种情况互不重叠按加法原理相加得到543636126。凡是遇到每个组至少一个的题目先判断哪个组多分了一个再分类写出组合式最后相加三步走基本不会错。第14题考相邻排列答案A。3个女生必须相邻用捆绑法先把3个女生看成一个整体与5个男生一起排共有6个对象排列数是A(6,6)720女生内部还可以交换位置有A(3,3)6种按乘法原理相乘得到720×64320。看到必须相邻就用捆绑看到不能相邻就用插空这是排列组合里两个固定套路。写题时先把谁和谁绑在一起圈出来再算整体排列容易漏掉的是内部排列这一层乘数。2.3 格雷码与存储单位背性质不背码表第4题考4位格雷码答案D。格雷码的定义是相邻两个编码之间只有1位不同。验证选项D0000到0001只有最后一位变化0001到0011只有倒数第二位变化0011到0010是最后一位变化后面0110到0111、0111到0101都满足相邻差1位。选项A最后从0101跳到1000至少要变3位直接排除。这个考点不需要背整张格雷码表只需要拿相邻码只有1位不同这个性质逐项检查哪个选项全程满足就选哪个。第5题考存储单位换算答案D。记1KB1024字节1MB1024KB1字节8位那么1MB1024×1024×88388608位。这里有两个坑一是有人把1024近似成1000算出8000000二是有人只算到字节数1048576忘了乘8。换算题建议分两步写先算字节数再算位数每一步写清楚单位基本不会错。CSP-J几乎每年都会在存储单位、进制、补码范围这三类基础题中轮流出题这几分属于必须拿满的。2.4 C语言与操作系统常识考得细但都来自课本第6题选C。C的基本数据类型是int、float、char、bool这些struct是复合数据类型由基本数据类型组合而成不是基本类型。第7题选D。C的循环语句只有for、while、do-while三种repeat-until是Pascal风格的语法不在C里。这类以下哪个不是的题陷阱就是把别的语言的语法混进来复习时把C的运算符、控制语句、数据类型列表过一遍就能应对。第8题考char运算答案B。C/C中字符是连续编码的a13表示从a往后数13个字母。从a开始数a是第0个b是第1个c是第2个一直数到第13个是n所以(char)(a13)等于n。第15题考编译器作用答案B。编译器把源代码转换成机器代码注意直接执行源代码是解释器的事情管理程序运行时的内存是操作系统的职责这几个概念在初赛里经常互换干扰。2.5 算法数据结构四件套二分、图论、二叉树、栈第9题答案是10。1000个元素的有序表用二分查找最多比较次数是⌈log2 1000⌉因为2^95122^1010241000夹在中间所以需要10次。这个考点可以记成公式最大比较次数⌊log2 N⌋1N1000时⌊log2 1000⌋9加1得到10。第11题考图论基础答案B。无向图中每条边连接两个顶点贡献2个度所以所有顶点的度数之和等于边数的两倍。这个结论在判断图的性质、计算可遍历性时经常用到。第12题考二叉树遍历答案A。前序遍历是[A,B,D,E,C,F,G]中序遍历是[D,B,E,A,F,C,G]。从前序可知根是A看中序A左边的是左子树[D,B,E]右边的是右子树[F,C,G]。左子树的前序是[B,D,E]所以B是左子树的根再看中序D在B左边、E在B右边确定D是B的左孩子、E是B的右孩子。右子树同理C是根F和G分别是左右孩子。最后按后序遍历的左右根顺序写出[D,E,B,F,G,C,A]。第13题考栈的出栈合法性答案D。模拟一遍选项D的序列1,3,5,2,4,61入栈后出栈得到1然后2入栈、3入栈、3出栈得到3再4入栈、5入栈、5出栈得到5此时栈里从底到顶是2、4下一个要出的是2但栈顶是4必须先出4才能出2所以这个序列不可能。验证栈序列的通用方法是每遇到一个输出x就不断地把输入序列的下一个元素入栈直到x出现在栈顶再弹出如果x在栈中但不在栈顶这个序列就非法。3. 阅读程序高频考点素数、爬楼梯DP、递归函数的读题模型3.1 素数计数与求和改循环边界不等于改结果阅读程序第一题的核心是三个函数isPrime判断素数countPrimes统计2到n之间的素数个数sumPrimes求这些素数的和。isPrime的关键代码是for(int i2;i*in;i)枚举到根号n就能判断是否有因子这是素数判断的标准写法。bool isPrime(int n) { if (n 1) return false; for (int i 2; i * i n; i) { if (n % i 0) return false; } return true; } int countPrimes(int n) { int count 0; for (int i 2; i n; i) { if (isPrime(i)) count; } return count; }第16题判断输入10时第一个输出4、第二个输出17是否正确。10以内的素数是2、3、5、7共4个和是17所以判断为真。这道题只要会列素数表就能拿分。第17题是整份卷子里最容易错的判断题之一。题目说把isPrime里的循环条件改成in/2输入20时countPrimes(20)的输出会变成6。这个说法是错误的。原因在于i*in和in/2都是合法的枚举上界前者是√n后者是n/2n/2比√n更大枚举更充分不会漏掉任何因子也不会多判出错。所以countPrimes(20)的结果仍然是8不是6。这个题的坑在于很多考生看到循环条件变了就认为结果必然变化没有去想更大范围是否改变判定结果。读程序题时改动循环边界要先判断是否影响函数语义再判断是否影响输出。第19题求输入50时sumPrimes的输出答案B。把50以内素数全部列出2、3、5、7、11、13、17、19、23、29、31、37、41、43、47求和得到328。这类求和题没有捷径平时练熟100以内的素数表考试时列出来逐个加就行。3.2 最小花费爬楼梯从转移式反推dp表阅读程序第二题从题干给出的转移式可以看出它是最小花费爬楼梯的动态规划模型。题干没有给完整代码但dp[i]min(dp[i-1],dp[i-2])cost[i-1]或cost[i]这种形式是标准写法。按题目反推代码逻辑等价于int minCost(vectorint cost) { int n cost.size(); vectorint dp(n); dp[0] cost[0]; dp[1] cost[1]; for (int i 2; i n; i) { dp[i] min(dp[i - 1], dp[i - 2]) cost[i]; } return min(dp[n - 1], dp[n - 2]); }dp[i]的含义是踩到第i级台阶所需的最小花费。到达第i级只能从第i-1级或第i-2级过来所以取两者中较小的花费再加上当前这一级的费用cost[i]。最终结果取最后两级中的较小值因为最后可以跨过最后一级。第21题输入cost数组{10,15,20}输出15。手动填表dp[0]10dp[1]15dp[2]min(15,10)2030最终输出min(30,15)15判断为真。第24题输入{1,100,1,1,1,100,1,1,100,1}答案是6。逐项计算dp[0]1dp[1]100dp[2]min(100,1)12dp[3]min(2,100)13dp[4]min(3,2)13dp[5]min(3,3)100103dp[6]min(103,3)14dp[7]min(4,103)15dp[8]min(5,4)100104dp[9]min(104,5)16最终输出min(6,104)6。第26题把转移式改成dp[i-1]cost[i-2]输入{5,10,15}时输出10。修改后不再是两条路取最小而是只能从前一级过来并且费用取前前级的cost[i-2]。dp[0]5dp[1]10dp[2]dp[1]cost[0]10515输出min(15,10)10。做这类题时先把dp数组的下标定义写在草稿纸上再手工填一张小表就能避开大部分坑。3.3 customFunction递归先写递推式再数调用次数阅读程序第三题考递归函数。从第30题输入5和4返回625可以反推customFunction(a,b)的功能等价于求a的b次方。第27题输入2和3时函数返回值应该是2^38不是64所以判断为假。第28题说b为负数时会陷入无限递归这是真的因为递归过程中b每次减1负数方向永远到不了终止条件。第29题说b越大运行时间越长也是真的递归层数随b线性增长。第30题输入5和45^4625选B。第31题输入x3、y3最终输出是144。注意题目问的是程序的最终输出不是customFunction(3,3)单次调用的返回值。customFunction(3,3)27最终输出144说明main里对返回值做了多次调用或组合运算。这类题的通用检查法在草稿纸上把每次调用的入参和返回值列成表再顺着main的表达式从左到右代入少一步都会掉坑。第32题把函数体改成return a customFunction(a-1,b-1)输入3和3。改造后的递推式是f(a,b)af(a-1,b-1)展开f(3,3)时先加3再调f(2,2)f(2,2)先加2再调f(1,1)逐层展开到终止条件后再从最底层把返回值逐层带回。递推展开时容易漏掉某一层的a值或终止条件的返回值所以每一层都要在纸上写清楚当前层加几、下一层入参变成什么。4. 完善程序高频考点平方数枚举与汉诺塔递归的填空套路4.1 判断平方数五空就是一个枚举查找模板完善程序第一题是判断正整数n是否为完全平方数。补全后的isSquare函数如下bool isSquare(int num) { int i 1; int bound (int)floor(sqrt(num)); for (; i bound; i) { if (num i * i) { return true; } } return false; }第33题①处填1。题目说存在正整数x所以枚举从1开始不能从0开始。第34题②处填(int)floor(sqrt(num))。枚举上界是num的平方根取整sqrt返回浮点数先floor向下取整再转int保证i最多取到√num。如果选sqrt(num/2)-1会漏掉4这类平方数因为sqrt(2)取整是1i取不到2。第35题③处填numii。这里必须是双等号判断相等如果写成numii就把num的值改掉了循环后面的判断全部错乱。第36题④处填true找到i*inum就返回真。第37题⑤处填false整个循环结束都没找到说明不是平方数。这类完善程序的读题顺序是先看函数整体在做什么再确定枚举起点和枚举上界最后看返回值的真假分支。五个空对应的就是起点、终点、条件、命中返回、未命中返回套这个模板基本不会错。4.2 汉诺塔三步递归与参数换位完善程序第二题是汉诺塔补全后的dfs函数如下void dfs(int i, char src, char tmp, char tgt) { if (i 1) { move(src, tgt); return; } dfs(i - 1, src, tgt, tmp); move(src, tgt); dfs(i - 1, tmp, src, tgt); }汉诺塔的递归思路只有三步先把上面i-1个盘子从src借助tgt挪到tmp再把第i个盘子从src直接挪到tgt最后把i-1个盘子从tmp借助src挪回tgt。第38题①处填1只有一个盘子时直接移动这是递归出口。第39题②处填src,tgt即move(src,tgt)。注意这里不是src,tmp因为当前这一步就是把最大的盘子挪到目标柱。第40题③处填src,tgt,tmp第一次递归的参数顺序是源、目标、中转让第i-1个盘子全部先到临时柱。第41题④处填tmp,src,tgt第二次递归的参数顺序是中转、源、目标让盘子从临时柱回到目标柱。第42题⑤处填i-1调用规模每次减1。这道题最容易错的是③和④的参数顺序正好相反。记忆口诀是盘中盘先借道大盘直接走再来一盘借道回。考场上如果拿不准用n2手工走一遍验证dfs(2,A,B,C)先把1个盘子从A经C挪到B再把第2个盘子从A挪到C最后把B上的盘子经A挪到C。三步顺序和参数一一对应验证完再填答案。5. 常见易错点与失分点初赛最容易丢分的五个位置5.1 int范围记成对称区间错在哪第1题在A、B、D之间犹豫最后选了一个上下界关于0对称的选项。为什么错脑子里只记得2^31约等于21亿忽略了补码表示中负数比正数多一个。怎么答对死记下界绝对值比上界大132位int下界是-2147483648上界是2147483647。考试时遇到这个考点直接把-2^31到2^31-1默写出来再对选项。5.2 混合进制没有统一成十进制错在哪第2题把148当成十进制14或18来算把D16当成字母D忽略掉导致整个式子算错。为什么错不同进制混在同一个表达式里时每一位的权值不同不能直接按十进制加减。怎么答对看到八进制、十六进制、二进制混算第一步全部转十进制第二步再代入计算。八进制转十进制按权展开十六进制先记住A到F对应10到15二进制从低位开始每一位对应1、2、4、8。5.3 存储单位换算漏掉bit与byte的8倍关系错在哪第5题算出1048576或8000000前者只换算到字节数后者把1024近似成1000。为什么错1MB到KB再到B都是1024倍B到bit还要乘8任何一步漏掉都会错。怎么答对写清楚链路1MB1024KB1024×1024B1024×1024×8bit分步计算每一步标注单位最后结果8388608。5.4 二分查找次数该向上取整却向下取整错在哪第9题算出log2 1000约9.97部分考生取9就选了7次。为什么错二分查找最多比较次数需要保证覆盖所有元素比较次数必须是整数且要够用所以要向上取整。怎么答对用2的幂判断2^9512不够覆盖10002^101024才够所以是10次。这类题不要直接看小数而是找相邻的2的幂。5.5 栈出栈序列只凭直觉没做完整模拟错在哪第13题看到1,3,5,2,4,6觉得大小交错很有规律选成可能。为什么错没有模拟到5出栈之后栈里还剩2和4且4在2上面。栈是后进先出4没出栈前2不可能先出。怎么答对每验证一个出栈序列就手动模拟入栈和出栈全过程当输出x时持续入栈直到x在栈顶如果x已经入栈但被压在下面直接判定非法。把ABCD四个序列全部模拟一遍宁慢勿错。6. 答题技巧用代入、填表、边界检查三招稳住初赛成绩先按模块分配时间。2024年初赛总分100分建议单选30分控制在25到30分钟内完成阅读程序40分用40分钟完善程序30分用25分钟剩余时间全部留给检查。如果一道题卡了超过5分钟先标记跳过去初赛判断题和选择题对错各占一半分值卡题不如先保后面的代码题。模块分值建议用时单项选择题30分25到30分钟阅读程序40分40分钟完善程序30分25分钟检查25分20到25分钟读阅读程序题时第一招是小数据代入。拿题目给的输入n10或更小的样例手算一遍和代码输出对比能快速发现理解偏差。第二招是填表凡是遇到dp或递归就在草稿纸上画一张状态表dp题填dp[0]到dp[n]的值递归题列每次调用的入参和返回值把抽象执行变成具体数值。第三招是边界检查n0、n1、负数、空数组都要单独想一遍很多程序题把边界藏在if(n1)这种分支里完善程序填空也经常在终止条件处设空。从那以后我每次带学生练真题都强制先走一遍代入、填表、边界这三步再长的程序也不凭感觉直接选。初赛的坑其实很固定踩过一次长记性比刷十套题都管用。希望帮到你。本文还有配套的精品资源点击获取
简介2024年信息学奥赛CSP-J初赛真题详解面向初中生、少儿编程学员和C爱好者帮助备考者系统把握入门组初赛命题脉络。资源包仅含1个docx文档大小约121KB但内容精炼覆盖2024年CSP-J初赛单项选择题、阅读程序题等真实题目每题均附答案和解析适合考前冲刺或日常查漏。文档重点剖析了32位int存储范围、格雷码、存储单位换算、进制转换、二分查找、栈与队列、无向图度数、二叉树遍历、排列组合、C基本数据类型与循环结构、操作系统识别等高频考点并在解析中穿插组合数学和图论方法帮助读者拓宽解题思路。借助这份分析考生可快速理解考点背后的计算机科学原理提升逻辑推理和代码阅读能力并通过错题对照明确复习重点。已有2593人学习使用是信息学奥赛入门阶段高性价比的参考资料。1. 2024年信息学奥赛CSP-J初赛真题考点拆解真正拉分的是70分代码题2024年CSP-J初赛单选题第1题直接问32位int的存储范围这几乎是明送分可每年都有考生在C和D选项之间反复纠结最后凭感觉选错。第2题把八进制、十六进制、二进制混在一个式子里看着像复杂计算实际先统一转成十进制再代入就结束。初赛总分100分单选30分、阅读程序40分、完善程序30分也就是说70分都在读代码和补代码光背知识点根本拿不稳必须按题型练手感。这篇围绕2024年CSP-J初赛真题展开把单选高频考点、阅读程序常见的三类模型、完善程序的补全套路逐题拆开最后单列易错点和答题顺序。适合正在备赛的初中生、带赛的教练也适合正在学少儿编程、准备往信奥方向转的学生尤其是已经学完C语法但刷题量不够、一读程序就发懵的选手。2. 单选高频考点int范围、进制换算、组合计数与数据结构的送分套路2.1 整型范围与进制计算先翻译再代入第1题答案选C。int占4字节共32位用补码表示时范围是-2^31到2^31-1对应十进制就是-2147483648到2147483647。选项A和B都把下界写成了-2147483647选项D又把上界多写了一位。这个考点的记忆方法很简单补码的负数比正数多一个下界的绝对值比上界大1。32位二进制中最高位是符号位剩余31位表示数值所以最大值是2^31-1最小值是-2^31不对称。第2题考的是混合进制计算答案A。表达式(148−10102)∗D16−11012里148是八进制D16中的D是十六进制里的1311012是二进制。先把它们分别转成十进制148按权展开是1×8412D16就是1311012是1×81×40×2113。代入原式得到(12-10)×13-132×13-1313。这类题的通用做法是看到带下标或字母的数字先统一转十进制再计算不要拿八进制数字直接当十进制算也不要看到D就当字母跳过。平时练习时把0到15的二进制、八进制、十六进制对照表默写一遍混算题基本不会丢分。2.2 组合与排列分类乘完再相加相邻捆绑要记牢第3题是典型的分类组合计数答案B。题干是10名员工分3个部门选4人且每个部门至少1人。因为只选4人必然有1个部门出2人另外两个部门各出1人。分三种情况A部门出2人B、C各出1人方案数是C(4,2)×C(3,1)×C(3,1)6×3×354B部门出2人A、C各出1人方案数是C(4,1)×C(3,2)×C(3,1)4×3×336C部门出2人A、B各出1人同样36。三种情况互不重叠按加法原理相加得到543636126。凡是遇到每个组至少一个的题目先判断哪个组多分了一个再分类写出组合式最后相加三步走基本不会错。第14题考相邻排列答案A。3个女生必须相邻用捆绑法先把3个女生看成一个整体与5个男生一起排共有6个对象排列数是A(6,6)720女生内部还可以交换位置有A(3,3)6种按乘法原理相乘得到720×64320。看到必须相邻就用捆绑看到不能相邻就用插空这是排列组合里两个固定套路。写题时先把谁和谁绑在一起圈出来再算整体排列容易漏掉的是内部排列这一层乘数。2.3 格雷码与存储单位背性质不背码表第4题考4位格雷码答案D。格雷码的定义是相邻两个编码之间只有1位不同。验证选项D0000到0001只有最后一位变化0001到0011只有倒数第二位变化0011到0010是最后一位变化后面0110到0111、0111到0101都满足相邻差1位。选项A最后从0101跳到1000至少要变3位直接排除。这个考点不需要背整张格雷码表只需要拿相邻码只有1位不同这个性质逐项检查哪个选项全程满足就选哪个。第5题考存储单位换算答案D。记1KB1024字节1MB1024KB1字节8位那么1MB1024×1024×88388608位。这里有两个坑一是有人把1024近似成1000算出8000000二是有人只算到字节数1048576忘了乘8。换算题建议分两步写先算字节数再算位数每一步写清楚单位基本不会错。CSP-J几乎每年都会在存储单位、进制、补码范围这三类基础题中轮流出题这几分属于必须拿满的。2.4 C语言与操作系统常识考得细但都来自课本第6题选C。C的基本数据类型是int、float、char、bool这些struct是复合数据类型由基本数据类型组合而成不是基本类型。第7题选D。C的循环语句只有for、while、do-while三种repeat-until是Pascal风格的语法不在C里。这类以下哪个不是的题陷阱就是把别的语言的语法混进来复习时把C的运算符、控制语句、数据类型列表过一遍就能应对。第8题考char运算答案B。C/C中字符是连续编码的a13表示从a往后数13个字母。从a开始数a是第0个b是第1个c是第2个一直数到第13个是n所以(char)(a13)等于n。第15题考编译器作用答案B。编译器把源代码转换成机器代码注意直接执行源代码是解释器的事情管理程序运行时的内存是操作系统的职责这几个概念在初赛里经常互换干扰。2.5 算法数据结构四件套二分、图论、二叉树、栈第9题答案是10。1000个元素的有序表用二分查找最多比较次数是⌈log2 1000⌉因为2^95122^1010241000夹在中间所以需要10次。这个考点可以记成公式最大比较次数⌊log2 N⌋1N1000时⌊log2 1000⌋9加1得到10。第11题考图论基础答案B。无向图中每条边连接两个顶点贡献2个度所以所有顶点的度数之和等于边数的两倍。这个结论在判断图的性质、计算可遍历性时经常用到。第12题考二叉树遍历答案A。前序遍历是[A,B,D,E,C,F,G]中序遍历是[D,B,E,A,F,C,G]。从前序可知根是A看中序A左边的是左子树[D,B,E]右边的是右子树[F,C,G]。左子树的前序是[B,D,E]所以B是左子树的根再看中序D在B左边、E在B右边确定D是B的左孩子、E是B的右孩子。右子树同理C是根F和G分别是左右孩子。最后按后序遍历的左右根顺序写出[D,E,B,F,G,C,A]。第13题考栈的出栈合法性答案D。模拟一遍选项D的序列1,3,5,2,4,61入栈后出栈得到1然后2入栈、3入栈、3出栈得到3再4入栈、5入栈、5出栈得到5此时栈里从底到顶是2、4下一个要出的是2但栈顶是4必须先出4才能出2所以这个序列不可能。验证栈序列的通用方法是每遇到一个输出x就不断地把输入序列的下一个元素入栈直到x出现在栈顶再弹出如果x在栈中但不在栈顶这个序列就非法。3. 阅读程序高频考点素数、爬楼梯DP、递归函数的读题模型3.1 素数计数与求和改循环边界不等于改结果阅读程序第一题的核心是三个函数isPrime判断素数countPrimes统计2到n之间的素数个数sumPrimes求这些素数的和。isPrime的关键代码是for(int i2;i*in;i)枚举到根号n就能判断是否有因子这是素数判断的标准写法。bool isPrime(int n) { if (n 1) return false; for (int i 2; i * i n; i) { if (n % i 0) return false; } return true; } int countPrimes(int n) { int count 0; for (int i 2; i n; i) { if (isPrime(i)) count; } return count; }第16题判断输入10时第一个输出4、第二个输出17是否正确。10以内的素数是2、3、5、7共4个和是17所以判断为真。这道题只要会列素数表就能拿分。第17题是整份卷子里最容易错的判断题之一。题目说把isPrime里的循环条件改成in/2输入20时countPrimes(20)的输出会变成6。这个说法是错误的。原因在于i*in和in/2都是合法的枚举上界前者是√n后者是n/2n/2比√n更大枚举更充分不会漏掉任何因子也不会多判出错。所以countPrimes(20)的结果仍然是8不是6。这个题的坑在于很多考生看到循环条件变了就认为结果必然变化没有去想更大范围是否改变判定结果。读程序题时改动循环边界要先判断是否影响函数语义再判断是否影响输出。第19题求输入50时sumPrimes的输出答案B。把50以内素数全部列出2、3、5、7、11、13、17、19、23、29、31、37、41、43、47求和得到328。这类求和题没有捷径平时练熟100以内的素数表考试时列出来逐个加就行。3.2 最小花费爬楼梯从转移式反推dp表阅读程序第二题从题干给出的转移式可以看出它是最小花费爬楼梯的动态规划模型。题干没有给完整代码但dp[i]min(dp[i-1],dp[i-2])cost[i-1]或cost[i]这种形式是标准写法。按题目反推代码逻辑等价于int minCost(vectorint cost) { int n cost.size(); vectorint dp(n); dp[0] cost[0]; dp[1] cost[1]; for (int i 2; i n; i) { dp[i] min(dp[i - 1], dp[i - 2]) cost[i]; } return min(dp[n - 1], dp[n - 2]); }dp[i]的含义是踩到第i级台阶所需的最小花费。到达第i级只能从第i-1级或第i-2级过来所以取两者中较小的花费再加上当前这一级的费用cost[i]。最终结果取最后两级中的较小值因为最后可以跨过最后一级。第21题输入cost数组{10,15,20}输出15。手动填表dp[0]10dp[1]15dp[2]min(15,10)2030最终输出min(30,15)15判断为真。第24题输入{1,100,1,1,1,100,1,1,100,1}答案是6。逐项计算dp[0]1dp[1]100dp[2]min(100,1)12dp[3]min(2,100)13dp[4]min(3,2)13dp[5]min(3,3)100103dp[6]min(103,3)14dp[7]min(4,103)15dp[8]min(5,4)100104dp[9]min(104,5)16最终输出min(6,104)6。第26题把转移式改成dp[i-1]cost[i-2]输入{5,10,15}时输出10。修改后不再是两条路取最小而是只能从前一级过来并且费用取前前级的cost[i-2]。dp[0]5dp[1]10dp[2]dp[1]cost[0]10515输出min(15,10)10。做这类题时先把dp数组的下标定义写在草稿纸上再手工填一张小表就能避开大部分坑。3.3 customFunction递归先写递推式再数调用次数阅读程序第三题考递归函数。从第30题输入5和4返回625可以反推customFunction(a,b)的功能等价于求a的b次方。第27题输入2和3时函数返回值应该是2^38不是64所以判断为假。第28题说b为负数时会陷入无限递归这是真的因为递归过程中b每次减1负数方向永远到不了终止条件。第29题说b越大运行时间越长也是真的递归层数随b线性增长。第30题输入5和45^4625选B。第31题输入x3、y3最终输出是144。注意题目问的是程序的最终输出不是customFunction(3,3)单次调用的返回值。customFunction(3,3)27最终输出144说明main里对返回值做了多次调用或组合运算。这类题的通用检查法在草稿纸上把每次调用的入参和返回值列成表再顺着main的表达式从左到右代入少一步都会掉坑。第32题把函数体改成return a customFunction(a-1,b-1)输入3和3。改造后的递推式是f(a,b)af(a-1,b-1)展开f(3,3)时先加3再调f(2,2)f(2,2)先加2再调f(1,1)逐层展开到终止条件后再从最底层把返回值逐层带回。递推展开时容易漏掉某一层的a值或终止条件的返回值所以每一层都要在纸上写清楚当前层加几、下一层入参变成什么。4. 完善程序高频考点平方数枚举与汉诺塔递归的填空套路4.1 判断平方数五空就是一个枚举查找模板完善程序第一题是判断正整数n是否为完全平方数。补全后的isSquare函数如下bool isSquare(int num) { int i 1; int bound (int)floor(sqrt(num)); for (; i bound; i) { if (num i * i) { return true; } } return false; }第33题①处填1。题目说存在正整数x所以枚举从1开始不能从0开始。第34题②处填(int)floor(sqrt(num))。枚举上界是num的平方根取整sqrt返回浮点数先floor向下取整再转int保证i最多取到√num。如果选sqrt(num/2)-1会漏掉4这类平方数因为sqrt(2)取整是1i取不到2。第35题③处填numii。这里必须是双等号判断相等如果写成numii就把num的值改掉了循环后面的判断全部错乱。第36题④处填true找到i*inum就返回真。第37题⑤处填false整个循环结束都没找到说明不是平方数。这类完善程序的读题顺序是先看函数整体在做什么再确定枚举起点和枚举上界最后看返回值的真假分支。五个空对应的就是起点、终点、条件、命中返回、未命中返回套这个模板基本不会错。4.2 汉诺塔三步递归与参数换位完善程序第二题是汉诺塔补全后的dfs函数如下void dfs(int i, char src, char tmp, char tgt) { if (i 1) { move(src, tgt); return; } dfs(i - 1, src, tgt, tmp); move(src, tgt); dfs(i - 1, tmp, src, tgt); }汉诺塔的递归思路只有三步先把上面i-1个盘子从src借助tgt挪到tmp再把第i个盘子从src直接挪到tgt最后把i-1个盘子从tmp借助src挪回tgt。第38题①处填1只有一个盘子时直接移动这是递归出口。第39题②处填src,tgt即move(src,tgt)。注意这里不是src,tmp因为当前这一步就是把最大的盘子挪到目标柱。第40题③处填src,tgt,tmp第一次递归的参数顺序是源、目标、中转让第i-1个盘子全部先到临时柱。第41题④处填tmp,src,tgt第二次递归的参数顺序是中转、源、目标让盘子从临时柱回到目标柱。第42题⑤处填i-1调用规模每次减1。这道题最容易错的是③和④的参数顺序正好相反。记忆口诀是盘中盘先借道大盘直接走再来一盘借道回。考场上如果拿不准用n2手工走一遍验证dfs(2,A,B,C)先把1个盘子从A经C挪到B再把第2个盘子从A挪到C最后把B上的盘子经A挪到C。三步顺序和参数一一对应验证完再填答案。5. 常见易错点与失分点初赛最容易丢分的五个位置5.1 int范围记成对称区间错在哪第1题在A、B、D之间犹豫最后选了一个上下界关于0对称的选项。为什么错脑子里只记得2^31约等于21亿忽略了补码表示中负数比正数多一个。怎么答对死记下界绝对值比上界大132位int下界是-2147483648上界是2147483647。考试时遇到这个考点直接把-2^31到2^31-1默写出来再对选项。5.2 混合进制没有统一成十进制错在哪第2题把148当成十进制14或18来算把D16当成字母D忽略掉导致整个式子算错。为什么错不同进制混在同一个表达式里时每一位的权值不同不能直接按十进制加减。怎么答对看到八进制、十六进制、二进制混算第一步全部转十进制第二步再代入计算。八进制转十进制按权展开十六进制先记住A到F对应10到15二进制从低位开始每一位对应1、2、4、8。5.3 存储单位换算漏掉bit与byte的8倍关系错在哪第5题算出1048576或8000000前者只换算到字节数后者把1024近似成1000。为什么错1MB到KB再到B都是1024倍B到bit还要乘8任何一步漏掉都会错。怎么答对写清楚链路1MB1024KB1024×1024B1024×1024×8bit分步计算每一步标注单位最后结果8388608。5.4 二分查找次数该向上取整却向下取整错在哪第9题算出log2 1000约9.97部分考生取9就选了7次。为什么错二分查找最多比较次数需要保证覆盖所有元素比较次数必须是整数且要够用所以要向上取整。怎么答对用2的幂判断2^9512不够覆盖10002^101024才够所以是10次。这类题不要直接看小数而是找相邻的2的幂。5.5 栈出栈序列只凭直觉没做完整模拟错在哪第13题看到1,3,5,2,4,6觉得大小交错很有规律选成可能。为什么错没有模拟到5出栈之后栈里还剩2和4且4在2上面。栈是后进先出4没出栈前2不可能先出。怎么答对每验证一个出栈序列就手动模拟入栈和出栈全过程当输出x时持续入栈直到x在栈顶如果x已经入栈但被压在下面直接判定非法。把ABCD四个序列全部模拟一遍宁慢勿错。6. 答题技巧用代入、填表、边界检查三招稳住初赛成绩先按模块分配时间。2024年初赛总分100分建议单选30分控制在25到30分钟内完成阅读程序40分用40分钟完善程序30分用25分钟剩余时间全部留给检查。如果一道题卡了超过5分钟先标记跳过去初赛判断题和选择题对错各占一半分值卡题不如先保后面的代码题。模块分值建议用时单项选择题30分25到30分钟阅读程序40分40分钟完善程序30分25分钟检查25分20到25分钟读阅读程序题时第一招是小数据代入。拿题目给的输入n10或更小的样例手算一遍和代码输出对比能快速发现理解偏差。第二招是填表凡是遇到dp或递归就在草稿纸上画一张状态表dp题填dp[0]到dp[n]的值递归题列每次调用的入参和返回值把抽象执行变成具体数值。第三招是边界检查n0、n1、负数、空数组都要单独想一遍很多程序题把边界藏在if(n1)这种分支里完善程序填空也经常在终止条件处设空。从那以后我每次带学生练真题都强制先走一遍代入、填表、边界这三步再长的程序也不凭感觉直接选。初赛的坑其实很固定踩过一次长记性比刷十套题都管用。希望帮到你。本文还有配套的精品资源点击获取
