2019 CSP-S初赛选择题11-15精析：二叉树、补码、递归、排序与static考点详解

每年 CSP-S 初赛考完我的微信基本都会炸一波“老师选择题第 11 题到底选啥”“第 15 题那个 static 变量是不是每次调用都会重新初始化”问的人一多我慢慢发现一个规律大家丢分最集中的地方往往就是选择题的中段——也就是 11 到 15 题。这几道题不像前 10 题那样纯考概念记忆也不像阅读程序题那样需要完整读完一大段代码它处在“基础知识和综合推理”的临界区命题人最喜欢在这里埋陷阱。今天我就把 2019 年 CSP-S 第一轮也就是原来常说的提高组初赛选择题第 11 到 15 题单独拎出来挨个拆一遍答案、考点和解题思路。带过几年竞赛生之后我越来越觉得这套题的中段选择题特别适合用来练“选择题手感”因为它几乎覆盖了初赛必考的二叉树、补码、递归、排序和 C 语言特性五大块。无论你是第一次准备 CSP-S 的萌新还是已经进入冲刺阶段的选手把这五道题吃透都能直接迁移到近几年的真题里。先说明一下下面按当年考生回忆并对照多个整理版本还原的题干个别措辞未必和官方原卷一字不差但选项逻辑和考点是对得上的。你可以把它当作考后复盘材料重点看解题思路而不是死记答案。1. 2019年CSP-S初赛选择题真题的总体观察与命题趋势1.1 选择题在整卷中的定位与分值分布CSP-S 第一轮满分 100 分选择题通常是 15 道单题分值虽然不高但它的性价比极高——因为选择题是整张卷子里唯一可以“用排除法、特例法、直接代入法”快速拿分的题型不需要像阅读程序题那样把代码从头到尾推演一遍。从命题位置上看第 1 到第 10 题往往偏向计算机基础、进制转换、网络常识、数据结构基础定义这类“记忆型”内容只要你复习过就能做对而第 11 到第 15 题开始进入“理解型”和“推理型”区间命题人会刻意把两个甚至三个知识点揉在一道题里。比如排序题不会只问你“哪种排序最快”而是把时间复杂度和稳定性放在一起考C 语言题不会只问“static 有什么用”而是直接给一段小程序让你推输出结果。所以 11-15 这个位置是整张试卷的“分水岭”。基础扎实但缺乏刷题训练的学生往往从这里开始连续丢分。反过来如果把这几道题的套路摸清了整套卷子的下限就有了保障。1.2 11-15题的命题逻辑从“考记忆”到“考推理”我统计过 2019 年前后几年的 CSP-S 真题选择题中段的高频考点非常集中二叉树的遍历还原、补码与原码转换、递归过程模拟、排序算法性质、C 关键字和程序语义。这几个考点有一个共同特征——它们都能用很小的题干考察很深的底层理解。比如二叉树遍历题目只给你两个序列你要在草稿纸上完整画出树的结构补码题只给你一个负数你要知道它在内存里怎么存递归题往往只有几行代码但你得清楚每一次调用压栈、回溯的过程。这些能力不是背概念能练出来的必须亲手推演。这其实透露了命题组的一个态度初赛虽然是笔试但它考察的是“你会不会像计算机一样思考”。这也是为什么我建议选手不要只刷选择题而是把选择题当成“知识体检”。做错一道题不要只看答案要追问自己我是二叉树还原不会还是递归边界条件理解有误还是 static 只记了个名字把原因找出来再看对应章节的知识点比盲目刷十套题都管用。2. 选择题11-15逐题精析与答案解读2.1 第11题二叉树遍历与树的还原回忆版题干一棵二叉树的先序遍历序列为ABDECFGH中序遍历序列为DBEAFCGH则它的后序遍历序列是选项A.DEBHFCGAB.DEBGHFCAC.DEFBHGCAD.DEBFHGCA答案D这道题是初赛最经典的“遍历还原”题。先序遍历的顺序是“根、左、右”中序遍历的顺序是“左、根、右”。所以先序序列的第一个字符 A 一定是整棵树的根。拿着 A 去中序序列里找位置它把中序分成了两半左边DBE是左子树的中序右边FCGH是右子树的中序。接下来回到先序序列A 后面的BDE是左子树的先序CFGH是右子树的先序。对左子树继续套同样的方法B 是左子树的根中序DBE里 B 左边是 D、右边是 E所以 D 是 B 的左孩子E 是 B 的右孩子。右子树同理C 是根中序FCGH里 F 在 C 左边GH 在 C 右边所以 F 是 C 的左孩子再对 G 这棵子树用先序FGH和剩余的中序GH还原G 是根H 是 G 的右孩子。最后画出来的树是这样的A / \ B C / \ / \ D E F G \ H写出后序遍历左、右、根左子树 D E B右子树 F H G C最后根 A所以是DEBFHGCA。这类题有两个易错点一是把中序当成“根左右”来分割导致整棵树画反二是还原完树之后写后序序列时把左右子树的输出顺序搞混。我的建议是草稿纸上一定要把树形图画出来不要心算画完图再写序列基本不会错。补充一个重要结论只有“先序中序”或“后序中序”才能唯一确定一棵二叉树只有先序和后序是无法唯一确定的这个结论本身也是初赛选择题的常客。2.2 第12题补码与printf(%x)输出回忆版题干在 32 位系统下执行代码int a -8; printf(%x, a);输出结果是选项A.fffffff8B.80000008C.fff8D.00000008答案A这道题当年正确率不算高因为不少人只记住了“负数的补码是原码取反加一”但不会套到具体的机器位数和%x格式上。先推补码-8 的绝对值是 832 位补码表示中8 的二进制是0000...0000 1000前面 28 个 0。按位取反得到1111...1111 0111再加 1 得到1111...1111 1000。转成十六进制从低位开始四位一组1000是 8前面全是1111也就是 f所以完整结果是fffffff8。很多人会选 Cfff8这是把 int 当成了 16 位来算。int 在 32 位环境下是 4 字节也就是 8 个十六进制位不可能只输出 4 位。还有人会卡在“负数怎么用%x输出”这个问题上。实际上printf(%x, a)不会因为 a 是负数就报错它只是把内存里的二进制按无符号十六进制格式直接打印不涉及什么“负数的十六进制”。理解到这一层以后遇到%x输出负数的题就知道核心是补码展开。从这里还能引出一个常考的操作判断一个整数二进制表示里有多少个 1。做法是不断n n - 1每次去掉最低位的 1直到 n 变成 0循环次数就是 1 的个数。2019 年前后好几套模拟题都改编过这个考点建议当成必会技能掌握。2.3 第13题递归调用过程与边界条件回忆版题干int f(int x) { if (x 10) return x; return f(x / 10) x % 10; }执行cout f(2019);后输出什么选项A. 10B. 11C. 12D. 13答案C这题表面上是递归求和其实就是“把一个整数的各位数字加起来”。如果你一眼看出来了甚至可以绕过递归直接算 2 0 1 9 12。但考试不能只靠直觉还是要把递归过程完整模拟一遍。调用过程是这样展开的f(2019) f(201) 9 f(201) f(20) 1 f(20) f(2) 0 f(2) 2所以从最内层往回推f(2)2f(20)202f(201)213f(2019)3912。这道题容易踩的坑有两个。第一个是边界条件没看清楚有的同学以为是x 0时返回 0这样会把f(0)当成最终返回点但这里边界是x 10所以最内层返回的是 2 而不是 0。第二个坑是加减顺序递归展开时是“先递归再加右侧的余数”回溯时不要漏掉最外层的那次加法。递归题在初赛选择题里几乎年年出现变化形式包括递归逆序输出、递归求最大公约数、递归计算斐波那契数列等。做题的时候强烈建议在草稿纸上把“调用链”完整写出来先压栈再回溯像上面那样一层一层标号能避免绝大多数低级失误。2.4 第14题排序算法复杂度与稳定性回忆版题干下列排序算法中最坏时间复杂度为 O(n log n) 且排序结果稳定的是选项A. 快速排序B. 堆排序C. 归并排序D. 选择排序答案C这道题考的是排序算法的两个基本性质时间复杂度和稳定性属于初赛必考内容但想拿分必须把常见算法的特性表背熟、记准。逐个分析快速排序平均时间复杂度是 O(n log n)但最坏情况比如每次选取的基准值都是最大或最小值会退化到 O(n²)而且快排是不稳定的。堆排序最坏确实是 O(n log n)但它也是不稳定的。选择排序最坏是 O(n²)同样不稳定。只有归并排序无论是平均还是最坏时间复杂度都是 O(n log n)而且它是稳定排序所以正确答案只有 C。这里解释一下“稳定”到底是什么意思如果数组里有两个相等的元素 a[i] 和 a[j]i 在 j 前面排序完成后 a[i] 仍然在 a[j] 前面那这个排序算法就是稳定的。稳定性的实际价值在于多关键字排序比如先按总分排序总分相同再按语文排序。如果排序算法不稳定第二次排序可能会打乱第一次的主排序结果处理起来就非常麻烦。为了方便记忆我教学生一个口诀“快选堆”不稳定——也就是快速排序、选择排序、堆排序不稳定冒泡排序、插入排序、归并排序稳定。把这些性质和复杂度表一起背比单独记一个“归并稳定”有用得多。后面 3.1 节我会再展开冒泡排序也很爱在初赛里出现。2.5 第15题static关键字与程序输出回忆版题干#include iostream using namespace std; void func() { static int x 10; x; cout x; } int main() { func(); func(); func(); return 0; }程序输出什么选项A.111213B.101112C.111111D. 编译错误答案A这道题专门考察 C 里static局部变量。static int x 10;的作用不是把 x 变成全局变量而是改变 x 的生命周期它不再是函数每次调用时创建、结束时销毁的自动变量而是第一次执行到这一行时初始化一次之后一直活在静态存储区直到程序结束。具体到这段代码第一次调用func()x 初始化为 10然后 x 变成 11输出 11第二次调用时不会重新执行x 10这行初始化x 继续是 11加一变成 12输出 12第三次调用同理x 从 12 变 13输出 13。所以最终结果是111213。很多同学会选 B默认每次调用都从 10 开始这是自动变量和静态变量最核心的区别。还有人选 C以为 static 变量在程序运行中始终不变这同样不对static 只是“初始化一次”后续仍然可以被修改。至于 D 编译错误没有任何理由这段代码语法完全没问题。另外别忘了它的作用域仍然是函数内部main 函数不能直接访问 func 里的 x。这一点也经常出现在“阅读程序”题的追问里static 局部变量的作用是局部可见生命周期全局两者并不矛盾。C 语言特性不止 staticconst、final 等关键字也同样是初赛高频考点我放到第 3 部分一起梳理。3. 高频考点背后的C底层原理串联3.1 从第14题延伸冒泡排序的比较次数与代码实现第 14 题只考了归并排序但排序算法整体是初赛的“题库常青树”。特别是冒泡排序因为代码简单、性质复杂反而最容易出小题。比如问你n 个元素做冒泡排序最坏情况下需要比较多少次答案是 n(n-1)/2。这个数怎么来的第一趟比较 n-1 次第二趟 n-2 次一直到最后一趟 1 次等差数列求和就是 n(n-1)/2。带提前退出优化的冒泡排序最好情况只需要比较 n-1 次。也就是说冒泡排序的“最坏比较次数”和“最好比较次数”差距巨大命题人非常喜欢在这个点上做文章。平时自己写冒泡时建议加上提前退出标志void bubbleSort(int a[], int n) { for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { swap(a[j], a[j 1]); swapped true; } } if (!swapped) break; } }这样每轮如果没有任何交换说明数组已经有序直接结束。这种“优化细节”属于程序阅读题的常见素材写代码时养成的习惯考试时自然能看懂。再说说排序稳定性的综合应用。假设你有全班学生成绩先按学号排好再按分数排。如果使用不稳定排序第一次按学号排好的相对顺序可能被打乱最终结果就不符合“分数相同则按学号排序”的需求。所以工程上很多场景会优先考虑稳定的归并排序这也是归并排序虽然额外空间是 O(n)仍然被广泛使用的原因。3.2 const、static、final 三类关键字到底怎么记第 15 题考了 static但热词里同时提到 const 和 final说明它们也经常是初赛和复赛的共同考点。我把这三类关键字放在一起做一个“最少必要知识”梳理。static有三种常见位置函数内的静态局部变量生命周期全局作用域局部只初始化一次第 15 题考点。全局静态变量/全局静态函数限制在本文件内部使用外部文件无法通过 extern 引用。类中的静态成员属于整个类而不是某个对象所有对象共享同一份数据静态成员函数只能访问静态成员。const的核心含义是“承诺不修改”但位置不同含义不同const int *p指针指向的值不能通过 p 修改但 p 本身可以指向别处。int *const p指针本身不能重新赋值但它指向的值可以修改。const int *const p值和指针都不能改。const 成员函数函数内部不能修改对象的普通成员变量。final是 C11 引入的修饰符作用很明确class A final {};表示 A 不能被继承。virtual void f() final;表示这个虚函数不能在派生类中被重写。这三类关键字在初赛里不会考得太深但会通过“判断正误”或“程序输出”来考察你是否理解它们在生命周期、作用域、可修改性上的本质区别。我的建议是不要死记中文翻译而是每次看到关键字强制自己在心里说一遍“它影响的是生命周期还是作用域还是可修改性”这个习惯对复赛读代码也特别有帮助。3.3 从第13题延伸递归与系统栈的对应关系递归题如果只停留在“算结果”层面碰到难一点的变式很容易翻车。我更喜欢带学生从系统栈的角度理解递归每次函数调用系统都会在内存中分配一个栈帧里面保存局部变量、参数和返回地址。递归调用也一样只是被调用的函数是它自己。以第 13 题的f(2019)为例调用链会依次压入f(2019)、f(201)、f(20)、f(2)四个栈帧。最内层的f(2)先返回然后一层层弹出栈帧并继续执行后面的 x % 10。所以展开时“先递进再回归”后进栈的先出栈。理解了栈模型之后有两个常考推论你就能秒懂递归太深会导致栈溢出因为每个栈帧都占用内存无限递归或者深度过大会耗尽栈空间。递归能改写成循环或迭代本质是用显式栈模拟调用过程很多“递归改非递归”的程序题都是在考察这个思路。看到递归题先问自己三个问题边界条件是什么每次调用之后参数怎么变化返回值怎么合并想清楚这三个问题再复杂的递归都能吃透。第 13 题正是这三个问题的完美标本拿它当例题来练一点不亏。4. 做这类选择题最容易踩的坑与备考建议4.1 三个丢分习惯尤其要注意第一个坏习惯是只看正确选项不看错误选项。我批改学生试卷时发现很多人错题订正只写一个正确答案根本分析不出其他三个选项错在哪。这样做题错一道只是错一道下次换个说法照样错。正确做法是每道题都要能说出“A 错在哪里、B 错在哪里、C 错在哪里、D 为什么对”。四选一的选择题只有把四个选项都弄明白才算真正掌握了这道题。第二个坏习惯是遇到语言特性题就靠背诵。比如 static 的特性背口诀“只初始化一次”当然有用但如果不理解生命周期和作用域的区别遇到“static 变量能不能被其他函数访问”这种变式就会懵。背知识点只能应对原题理解原理才能应对变式。第三个坏习惯是不做验算。二叉树还原之后一定要自己把后序序列再还原成中序检查能不能回到题目给的序列递归题算完答案建议用最朴素的方法再模拟一遍。初赛时间一般够用多花 30 秒验算能避免很多低级失误。4.2 考场时间分配前15道题控制在20分钟内CSP-S 第一轮考试总共 120 分钟后面有阅读程序、完善程序这些大题每个都需要完整的推演时间。所以选择题不能拖太久我个人要求学生前 15 道题尽量控制在 20 分钟以内平均每道题 1 分多一点。如果某道题卡了 3 分钟还没思路先随便选一个标记出来跳过去做后面的题最后有时间再回头验算。这里有个技巧选择题的选项本身是很好的提示。比如第 11 题的遍历还原如果你发现好几个选项的后序序列长得特别像说明命题人故意在某个位置上埋了陷阱点这时候就要重点核对右子树的输出顺序。再比如补码题看到选项里有fff8和fffffff8就知道陷阱一定在“int 到底是几字节”上找出题人的陷阱比闷头计算更高效。4.3 错题整理把一套真题吃出三套的效果最后说说怎么做错题本。很多学生的错题本就是“题目答案”的抄写本完全没有复习价值。我推荐用“考点卡片”的形式每道错题记录五件事题目位置、涉及考点、我当时选的错误答案、正解的完整推演、一句话考点总结。以第 15 题为例卡片可以写成题目位置2019 CSP-S 选择 15 考点static 局部变量生命周期 我的错误答案B以为每次调用都重新初始化 正解推演第一次初始化 x10后续不再初始化三次输出 11 12 13 一句话总结static 局部变量只初始化一次但作用域仍在函数内整理完卡片之后还要做一件很重要的事——改编题目。递归题可以把f(2019)换成f(0)排序题可以把“选稳定排序”改成“选不稳定排序”static 题可以改成“把 static 去掉输出是什么”。一个考点延伸出三五种变化再去对照近几年的真题你会发现很多看似新题的东西骨子里还是这套逻辑。我个人带学生复习这套 2019 年真题时最喜欢用“反讲法”让学生把某道题的完整思路讲给我听每讲一步我就追问一句“为什么”尤其是逼他们解释另外三个错误选项。只要能把一道选择题讲得让同桌听明白这道题背后的所有考点基本就消化透了。这个方法不挑题目11 到 15 题每道都值得这样过一遍。距离考试还有时间的话不妨现在就找一道题试试。