★ FEATURED ARTICLE 简介面向备战CSP-J初赛的学生、少儿编程教师及信息学竞赛入门者这份2024年真题解析文档围绕初赛单项选择题与阅读程序等题型给出答案与逐题分析帮助读者定位知识薄弱点并建立复习框架。压缩包共1个docx文件大小约121KB内容以试题、参考答案和解析文字为主便于打印或按题型检索。资源已有2594人学习适合用作考前自测、课堂讲评与专题补强。文档覆盖32位int存储范围、进制转换、格雷码、组合计数、二分查找、栈的出栈顺序、二叉树遍历、无向图度数关系、C基本数据类型与循环语句、操作系统常识等考点解析不仅给出结论还呈现推导过程与易错点可帮助读者把零散知识串联成体系提升复杂题目的分析与解题能力。1. 开篇先确定最容易丢分的地方2024 年信息学奥赛 CSP-J 初赛真题里最容易丢分的地方往往不是最后两道完善程序反而是第 5 题那类存储换算。1MB 等于多少 bit四个选项里 8000000 和 8388608 只差一位数字凭感觉选基本靠运气。这场第一轮是纯笔试没有编译器也没有运行结果可看所有答案都得在草稿纸上手推出来。整卷三类题单项选择 15 题每题 2 分阅读程序三段共 40 分完善程序十个空每个 3 分。阅读程序里的判断题一个 1.5 分看着分值低其实是全卷性价比最高的部分读懂一段程序五道题能一起拿到分。这篇内容适合已经会写 C、但还没系统刷过真题的人。2. 卷面结构与单选高频考点30 分怎么一分不丢单选题的 15 道题横跨计算机基础、进制换算、组合计数、数据结构常识和语言细节看起来杂实际上考点重复度很高。把这 30 分当成必须拿到的分数后面阅读程序才有容错空间。2.1 三类题型的分值与时间分配题型题量单题分值小计建议用时单项选择15 题2 分30 分20 分钟阅读程序3 段判断题 单选题判断 1.5 分 / 单选 3 分40 分55 分钟完善程序10 空3 分30 分25 分钟阅读程序的判断题只有两个选项对错各半但它是“读懂一段程序之后连带得分”的题不是靠猜。三段程序分别考素数判断、线性动态规划和递归函数完善程序考完全平方数和汉诺塔。这个组合近几年变化不大复习时有明确的优先级。提示时间分配的关键是别在单选上纠结超过 90 秒。单选 2 分一题阅读程序一段 5 题值 12 分左右后者更值得投入。2.2 int 范围与存储换算两道题的固定算法第 1 题问 32 位 int 的存储范围正确答案是 -2147483648 到 2147483647。这道题的易错点全在边界上很多人会背“2 的 31 次方”然后写成上界 2147483648忽略了 0 也要占一个非负位置。补码表示下负数和 0 共用“非负那一半”所以下界的绝对值比上界大 1。第 5 题是把单位换算串起来考1MB 1024KB1KB 1024B1B 8bit三步连乘得 8388608。这类题没有技巧只有一条先把链条写全再动笔算。# 验证 32 位 int 的边界与 1MB 的二进制位数 bits 32 lo -(2 ** (bits - 1)) # -2147483648下界 hi 2 ** (bits - 1) - 1 # 2147483647上界 print(lo, hi) one_mb_bits 1024 * 1024 * 8 # 1MB 1024KB × 1024B × 8bit print(one_mb_bits) # 8388608这段代码是用来验证手算结果的不是考场必需。bits - 1是因为最高位留给符号hi后面减 1 是因为 0 占了一个非负名额。考场上换成心算时记住 2 的 10 次方是 1024、2 的 20 次方约 1048576、2 的 30 次方约 10.7 亿三个量级够用了。2.3 进制混合运算与格雷码先把进制统一起来第 2 题是 (14₈ − 1010₂) × D₁₆ − 1101₂四个进制混在一个式子里。稳妥的做法是先全部转成十进制再算14₈ 121010₂ 10D₁₆ 131101₂ 13代入得 (12−10)×13−13 13。答案 A。格雷码那道题问“哪个序列对应 0 至 8 的 4 位格雷码”。格雷码的性质只有一条相邻两个编码恰好只有一位不同。用这条性质逐对检查比背编码表快得多。# 检查候选序列相邻两项是否只差 1 位 seq [0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100] for a, b in zip(seq, seq[1:]): diff sum(x ! y for x, y in zip(a, b)) print(a, b, diff) # 每行 diff 必须为 1zip(seq, seq[1:])把相邻两项配对内层zip(a, b)逐位比较sum统计不同的位数。跑一遍能看到每行都是 1说明 D 选项成立。如果某一行出现 2 或 3该选项直接排除。A 选项最后是从 0101 跳到 1000差了 3 位B 选项 0111 到 0100 差 2 位C 选项 0010 到 0100 差 2 位。三个错误选项都有明显断点检查一遍就能全部排除。2.4 组合计数分组选人和捆绑法两个模板第 3 题是 10 名员工分在 3 个部门4 人、3 人、3 人选 4 人且每个部门至少 1 人。这种“每组至少一个”的题第一步永远是确定人数分布4 个人分到 3 个部门且不能有空组只有 211 一种形态。第二步按“哪个部门出 2 人”分类A 部门出 2 人C(4,2)×C(3,1)×C(3,1) 6×3×3 54B 部门出 2 人C(4,1)×C(3,2)×C(3,1) 4×3×3 36C 部门出 2 人C(4,1)×C(3,1)×C(3,2) 4×3×3 36三类相加 126答案 B。这类题最常见的做法是“先任意选再减去不合法的”但如果题干部门人数不一致容斥很容易算漏分类反而更稳。第 14 题是 5 个男生、3 个女生站成一排3 个女生必须相邻。相邻问题用捆绑法把 3 个女生打成一个整体和 5 个男生一共 6 个“单位”全排列6! 720女生内部再排列3! 6相乘 4320答案 A。两个模板对照着记相邻就捆绑不相邻就插空。2.5 语言常识三个“看起来对”的陷阱第 6 题问哪个不是 C 基本数据类型答案是 struct。struct 是把基本类型组合起来的复合类型这个区分在阅读程序里也会用到。第 7 题问哪个不是 C 循环语句选项里混进了 repeat-until那是另一种语言的写法C 只有 for、while、do-while 三种。第 10 题问哪个不是操作系统名字Notepad 是文本编辑器不是系统。第 15 题问编译器的作用答案是“把源代码转换为机器代码”不能选“直接执行源代码”那是解释器的行为。第 8 题是字符运算(char)(a13)从 a 往后数 13 个字母a 是第 0 个数到 n答案 B。这几道题的共同点是选项里混进“其他语言的关键字”或者“应用软件”考的不是知识深度是你有没有把概念边界划清楚。做题时问自己一句“这个东西属于哪一层”比死记答案有用。3. 数据结构与算法四个模型二分、栈、二叉树、图的固定解法单选里有四道题专门考数据结构和算法每道都能在 30 秒内用固定套路拿下。这四个模型也是阅读程序和完善程序的基础值得单独拆开。3.1 二分查找比较次数向上取整别取近似第 9 题1000 个元素的有序表二分查找最多比较几次。答案是 ⌈log₂1000⌉ 10。判断方法很简单2⁹ 512 不够覆盖 10002¹⁰ 1024 够所以 10 次。选项里的 7 是 2⁷128 的量级25 是把比较次数和元素个数搞混了1 是只想到第一次比较。这道题有两种问法最多比较次数和平均比较次数。题干出现“最多”就用向上取整出现“平均”就得算期望两者不是一个答案。考场上先圈出这两个字能省掉一次后悔。提示二分查找的比较次数和“折半次数”是同一件事画一棵判定树树高就是最多比较次数叶子数就是元素个数。3.2 出栈序列判定模拟栈不要找规律第 13 题入栈顺序是 1 2 3 4 5 6问哪个出栈顺序不可能。正确做法是拿纸模拟不要试图找“逆序对”之类的规律。以 D 选项 1 3 5 2 4 6 为例要 1 先出压 1 再弹出要 3 出压 2、压 3弹 3此时栈里剩 2下一个要 5 出压 4、压 5弹 5栈里现在是 2 在下、4 在上下一个要 2 出但栈顶是 4弹不出来判定不可能。所以答案是 D。这个方法可以套用到任何出栈题按目标序列从左到右扫需要谁就压到谁压完立刻检查栈顶是不是下一个要出的。栈顶对不上就判死对得上就弹出继续。整个过程不超过两分钟比背结论可靠。3.3 前序加中序还原二叉树三步定位第 12 题给了前序 [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] 里 D 在 B 左边、E 在右边右子树前序 [C,F,G] 说明 C 是右子树的根中序 [F,C,G] 里 F 在左、G 在右。第三步写后序左子树 D E B右子树 F G C最后根 A合起来 [D,E,B,F,G,C,A]答案 A。这里有个能省时间的检查点后序的最后一个一定是整棵树的根。四个选项末尾分别是 A、C、A、C先排除两个再比对左子树开头是不是 D E B基本就能锁定。3.4 图论度数之和是边数的两倍第 11 题问无向图所有顶点度数之和等于什么答案是边数的两倍。理由是一条边连接两个顶点给这两点各贡献 1 度所以每条边被数了两次。这条性质在阅读程序里也常出现配套的还有一条奇度顶点的个数一定是偶数。图论的选择题一般不深考的都是这种“定义直接推一层”的结论。真正要练的是把结论和具体数字对上给 10 条边度数之和就是 20给 7 个顶点每个度数 4边数就是 14。3.5 这四类题在考场上的手推顺序拿到一道数据结构题先看它问的是“性质”还是“过程”。问性质度数之和、二叉树根的位置、二分次数就直接套结论30 秒解决问过程出栈序列、遍历结果就画图画图比在脑子里想快也比想错强。草稿纸上的画法有讲究二叉树画出节点关系就够不用画得工整栈题画一个竖着的栈每弹一次划掉一个元素图论题把度数标在顶点旁边加起来核对总数。这些小动作看起来浪费时间实际是防止低级失误的唯一办法。4. 阅读程序与完善程序三段代码、十个填空的逐题拆解70 分在这半张卷子上。阅读程序给三段完整代码每段配判断题和单选题完善程序给两段挖了空的代码每空三选一。这两类题的答法完全不同阅读程序要“读懂它在干什么”完善程序要“用上下文填空”。4.1 素数程序i*in 的边界决定一切第一段阅读程序给的是素数判断加统计核心代码是这三行。bool isPrime(int n) { if (n 1) return false; for (int i 2; i * i n; i) { // 循环上界是 sqrt(n) if (n % i 0) return false; // 找到因子即非素数 } return true; }i * i n等价于i sqrt(n)写成乘法是为了避开浮点误差。这个条件保证循环次数在 √n 量级n 取到 10 万时也只有 316 次。第 16 题输入 10第一个输出是 10 以内的素数个数即 2、3、5、7 共 4 个第二个输出是这些素数的和2357 17所以判断为对。第 17 题把条件改成i n/2问输入 20 时 countPrimes(20) 是否变成 6。实际代进去2 到 20 的素数还是 2、3、5、7、11、13、17、19 共 8 个没变。原因是 n/2 比 √n 大循环次数变多但判断结果不变所以“输出变为 6”是错的。第 20 题把条件改成i n这就出问题了。以 7 为例循环会走到 i 7此时 7 % 7 0函数返回 false7 被误判为非素数。所有素数都会在 i 等于自己时被判定为有因子所以答案是不能正确计算选 A。这道题的关键是意识到“n 本身也是 n 的因子”判断素数时不能把自己算进去。4.2 动态规划程序手推表格比读代码快第二段阅读程序是一段线性动态规划递推式是min(dp[i-1], dp[i-2]) cost[i-1]。这种题不要逐行读循环直接在草稿纸上列一张表从下标 0 开始一项一项填。步骤当前下标 i用到的前两项dp[i]备注10无初值按题干定义填21dp[0]依递推式只有一项可选32dp[1]、dp[0]取较小者加 cost开始出现分支43dp[2]、dp[1]同上逐项推进第 21 题 cost 数组只有 3 个元素填两步就能得 15判断为对。第 22 题把 dp[i-1] 改成 dp[i-3]问会不会编译错误答案是错。下标越界在编译期发现不了属于运行期问题而且这题只是逻辑变了语法完全合法。第 23 题问程序是否总是输出 cost 数组的最小元素显然是错的递推式里有累加输出的是某种最优路径的代价。第 24 题给了一串带 100 的 cost 数组答案是 6第 25 题给 7 个元素答案是 30。这两题都得老老实实填表凭感觉选一定会错。第 26 题把递推式改成dp[i-1] cost[i-2]输入 {5,10,15} 得 10答案 A。改递推式之后前两项的含义变了要从头再填一遍不能拿原来的表格改。提示动态规划阅读程序的手推表列数不要超过四列列多了写不下反而乱。每填一项在旁边标注用了哪两个前驱回头检查时一眼能看出错在哪一步。4.3 递归程序从选项反推函数语义第三段阅读程序是一个递归函数题 27 到 32 围绕它出题。原文没给完整代码但给的答案能反推出函数在做幂运算customFunction(5,4) 返回 625正好是 5 的 4 次方。第 27 题说 customFunction(2,3) 返回 64按幂运算应该是 8所以是错的。第 28 题问 b 为负数时会不会无限递归答案是会因为递归的终止条件靠 b 递减到边界负数永远到不了。第 29 题问 b 越大运行时间是否越长答案是对的递归次数随指数增长。第 31 题输入 3 和 3最终输出 144而函数本身返回 27。这说明主程序拿到返回值之后还做了一次运算。这类题的坑就在这只盯着函数看会漏掉最后一行。做题时把 main 函数从头到尾扫一遍看看有没有相加、相乘、平方之类的操作。第 32 题把函数体改成return a customFunction(a-1, b-1)输入 3 3 得 36。这类改函数体的题最稳的办法是展开前三层写在纸上3 加上下一层的结果下一层是 2 加上再下一层写出 3、2、1 这几项就能看出规律再对选项。4.4 完善程序一完全平方数的五个空怎么排第一段完善程序判断一个正整数是不是完全平方数五个空对应枚举起点、枚举上界、判断条件、命中返回值和循环结束返回值。bool isSquare(int num) { int i 1; // ① 从 1 开始枚举 int bound (int)floor(sqrt(num)); // ② 上界取平方根下取整 for (; i bound; i) { if (num i * i) { // ③ 相等即命中 return true; // ④ } } return false; // ⑤ }① 不能填 0因为 0×0 0 会让边界情况出错题干限定正整数从 1 开始最干净。② 只能填(int)floor(sqrt(num))如果填sqrt(num)-1num 9 时上界是 2会漏掉 i 3如果填sqrt(num/2)上界更小漏得更多。③ 必须是num i*i写成赋值号num i*i编译能过但逻辑全错这是最典型的失误点。④ 命中就返回 true。⑤ 循环走完还没找到返回 false。这五个空有依赖关系② 决定了循环范围③ 决定了判断是否正确①④⑤ 相对独立。答题时先填能确定的 ③④⑤再回头处理 ①②比从头顺着填稳。4.5 完善程序二汉诺塔的三行递归与参数顺序第二段是汉诺塔题干把规则写得很清楚一次挪一个、小盘必须在大盘上面。递归函数三个参数分别是源柱、中转柱、目标柱。void dfs(int i, char src, char tmp, char tgt) { if (i 1) { // ① 只剩一个盘 move(src, tgt); // ② 直接从源柱挪到目标柱 return; } dfs(i - 1, src, tgt, tmp); // ③ 先把上面 i-1 个挪到中转柱 move(src, tgt); // 把最大的盘挪到目标柱 dfs(i - 1, tmp, src, tgt); // ④⑤ 再把中转柱的 i-1 个挪到目标柱 }① 填 1只剩一个盘就是递归出口。② 填src, tgt一个盘直接从源到目标。③ 填src, tgt, tmp注意参数顺序是“盘数、源、中转、目标”把 i-1 个盘从 src 挪到 tmp此时 tgt 充当临时中转所以第三个参数是 tgt。④ 填tmp, src, tgt把 tmp 上的 i-1 个盘挪到 tgtsrc 当临时中转。⑤ 填i - 1。这题翻车最多的地方是 ③ 和 ④ 的参数顺序。记一句口诀第一次递归是“源不动目标变中转”第二次递归是“中转变源源变中转”。把三行代码当成“挪开、挪最大、挪回来”三步来理解参数位置就不容易错。提示完善程序里如果有两个空填的是同一组参数的变体先确定其中一个另一个用“谁当临时柱子”推出来比两个一起猜成功率高得多。5. 易错点五类考场上最容易丢分的判断这一章列的五个点都是真题里真实出现过的失分位置。每一条都按“错在哪、为什么错、怎么答对”拆开考前过一遍比刷新题有用。5.1 错在把 int 上界写成 2147483648错在哪第 1 题四个选项里C 和 D 只差上界最后一位D 写成 2147483648很多人手一滑就选了 D。为什么错只记住“2 的 31 次方”忘了补码里 0 占一个非负位置非负那一半要减 1。怎么答对记成“下界绝对值比上界大 1”即 -2³¹ 到 2³¹-1。做题时先写下 -2147483648再写 2147483647两个数一对选项自然就出来了。5.2 错在二分次数直接取 log 的整数部分错在哪1000 个元素算出 log₂1000 ≈ 9.97取整得 9选了错误选项。为什么错二分查找问“最多”比较次数只要元素个数不是 2 的整数次幂就必须向上取整否则覆盖不全。怎么答对找夹住它的两个 2 的幂512 1000 ≤ 1024对应 9 和 10取大的那个。考场上一旦看到“最多”两个字先想向上取整。5.3 错在出栈序列只扫一眼觉得“乱”错在哪第 13 题 D 选项 1 3 5 2 4 6 看起来只是顺序跳跃没细想就放过了。为什么错出栈序列的合法性靠栈的“后进先出”约束肉眼看不出冲突必须模拟。怎么答对按目标序列逐个匹配需要谁就压到谁压完检查栈顶。栈顶对不上立刻判死不要继续往下猜。5.4 错在阅读程序只看循环体不看返回条件错在哪第 17 题把 isPrime 的条件改成i n/2很多人以为 2 和 3 会被漏判直接选了“输出变成 6”。为什么错没有代具体数字进去算。isPrime(2) 时循环条件不成立直接返回 trueisPrime(3) 同理。判断结果根本没变。怎么答对凡是改条件的题挑两个最小、一个最大的输入代进去手算三个数就能验证结论。不要凭“条件变严了所以结果变少”这种直觉。5.5 错在完善程序从第一个空开始顺填错在哪汉诺塔那题很多人先填 ③ 的参数顺序结果 ③ 填错④ 跟着错一错错两空。为什么错③ 依赖对递归整体结构的理解属于难度最高的空① 和 ② 是递归出口逻辑最独立。怎么答对先扫一遍所有空把“不依赖其他空”的先填掉比如递归出口、返回值、循环起点。填完再处理参数顺序这类需要上下文的空。填空顺序对了同样的知识能多拿 6 分。6. 答题节奏三遍做题法与最后十五分钟的检查顺序整卷 100 分两个小时内做完不难难的是做完还有时间检查。我的做法是把卷子过三遍每遍的目标不一样。第一遍 40 分钟只做“看一眼就有答案”的题单选里的 int 范围、存储换算、操作系统、编译器作用阅读程序里的判断题。这一遍的目标是拿到 50 分左右遇到卡壳超过 90 秒的直接跳过在题号旁边画个圈。第二遍 50 分钟攻需要动笔的题组合计数、二叉树还原、出栈序列、动态规划的手推表。这一遍草稿纸要写清楚题号一道题一块区域回头检查时不用重算。阅读程序的选择题放在这一遍做因为判断题做完之后对程序已经有印象了。第三遍 15 分钟只查五类空完全平方数的枚举上界、汉诺塔的参数顺序、动态规划的递推下标、素数的循环边界、判断题里“改成某某条件”的题。这五类是全卷错误率最高的位置其他题检查收益不大。遍次用时目标放弃策略第一遍40 分钟拿到基础分90 秒无思路就跳第二遍50 分钟拿下计算题草稿写清题号第三遍15 分钟查五类高风险空只查不改思路还有一个细节判断题只填对错不确定的也要填空着一定是零分蒙一个还有一半机会。选择题四个选项的题先用排除法去掉两个明显错的再从剩下两个里选比直接猜准确率高。注意不要在最后五分钟改答案。除非你找到了明确的计算错误否则第一遍的判断往往比紧张状态下的反复更可靠。我当年第一次做这套卷子单选错了三道全是存储换算和进制混算阅读程序的判断题对了四道但选择题因为没手推表格错了两道。从那以后我每次做阅读程序题都强制先在草稿纸上画一张表哪怕题目看起来很简单。这个习惯让我后来再没错过动态规划那类题。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
