每年CSP-S第一轮认证结束我都会收到类似的问题前几道选择题做起来挺顺怎么一到中间就开始发懵2019年的提高组初赛卷尤其典型。从第6题到第10题正好卡在“基础题”和“需要真正动脑的题”的分界线上不少考生在这里被绊住后面做大题的时间也跟着紧张。这篇文章就以2019年CSP-S提高组初赛选择题第6-10题为锚点把这些题的考点逻辑、命题套路和解析方法完整拆一遍帮你搞清楚这一区间到底该怎么复习、怎么做题。很多人要的是一份答案列表但我更愿意把解题的判断过程写出来。因为这一区间的题目换年份、换考法背后的能力要求是稳定的。ABCD给你了你做对了下一套题换个说法照样不会做这才是初赛最大的坑。1. 第6-10题为什么是整张初赛卷的“分水岭”1.1 初赛试卷结构里这一区间承担着“难度爬坡”任务先看大背景。2019年CSP-S提高组第一轮认证是笔试满分100分题型主要包括三块单项选择题15道每题2分共30分阅读程序写结果三大题完善程序两大题。选择题虽然只占30分但它排在试卷最前面答题状态的好坏会直接影响后面的阅读程序题。前5道选择题考的很“软”计算机基础常识、进制转换、编码、简单C语法这些内容只要平时积累过基本可以秒选。但到了第6-10题风向突然变了题目开始往数据结构和算法理论上靠树的遍历、排序复杂度、图论基础、组合计数、栈和队列的模拟操作。这个“难度爬坡”设计并不是偶然的命题人希望用前面几道题稳住心态再从第6题开始逐步筛选出真正理解算法的学生。我统计过辅导学生时的做题情况第一轮认证成绩在60到70分附近的学生第6-10题平均错2到3道。这个区间的失分远高于前5题也高于很多人自己的预期。也就是说能不能进复赛往往不是由最后那道完善程序大题决定的而是由这5道看似普通的选择题决定的。1.2 这一区间的三个特殊“地位”第一层是难度地位。前5题可以靠记忆拿分第6-10题需要推理和计算。你光知道“二叉树有三种遍历”不够还要会根据中序和先序推后序光知道“快排快”不够还要知道快排在最坏情况下会退化到O(n²)而且常见的实现并不稳定。这些东西不是背出来的是做出来的。第二层是心态地位。很多考生第6题卡住之后心里会一直惦记着那道题做后面的阅读程序题时无法专注。初赛总共就那么点时间心理波动对得分率的影响比想象中大得多。第6-10题如果能顺利推进整个人的做题节奏会非常舒服反之很容易陷入“越急越错、越错越急”的循环。第三层是能力地位。这是整张试卷第一次出现“需要动笔验证”的选择题。阅读程序题也需要动笔模拟但难度更高第6-10题相当于一个缓冲带让你提前进入“推演状态”。我用一个表格把选择题部分的能力要求梳理一下方便你对照自己的薄弱位置题号区间主要考查方向能力要求常见丢分原因第1-5题计算机基础、编码进制、语言语法记忆加少量推理概念模糊、细节记岔第6-10题树、排序、图论、计数、数据结构模拟推理加计算验证不写草稿、概念混淆、审题跳词第11-15题综合算法思维、数学应用综合分析、灵活建模时间不足、方法不当2. 2019年这一区间的主要考查方向回忆版梳理先说明一点我这里保留的是当年考生回忆版和民间复现版各版本的选项措辞会有些出入但知识模块高度一致。与其逐字逐句对答案不如把这一区间真正涉及的几块核心内容吃透。2.1 树与二叉树遍历已知两种遍历推第三种这一块在2019年第6-10题区间出现概率很高几乎是初赛必考。核心思路只有一句话先序遍历找根中序遍历分左右。具体来说先序遍历序列的第一个元素一定是根节点拿着这个根节点去中序遍历里找位置中序序列中根节点左边是左子树右边是右子树。然后回到先序序列把左子树和右子树各自看成新的小二叉树继续重复这个“找根-分左右-递归”的过程。后序遍历则是在递归结束时按“左子树、右子树、根”的顺序组合。很多考生在这里犯的错误是只记住了三种遍历的递归写法但遇到具体序列题就不会推。其实这类题就是递归结构草稿纸上拆两轮就出来了。另外要留意一个细节已知先序和后序不一定能唯一确定二叉树除非题目额外注明是满二叉树或完全二叉树。这个点经常被命题人拿来设计“无法判断”这类选项。2.2 排序算法性质复杂度、稳定性、比较次数排序是初赛选择题的“稳定粮仓”几乎每年都有。需要记住的核心结论有平均时间复杂度O(n log n)的排序快速排序、归并排序、堆排序。最坏时间复杂度O(n²)的排序冒泡、插入、选择、快速排序退化情况。稳定排序冒泡、插入、归并。不稳定排序快速排序常见实现、堆排序、希尔排序、选择排序。基于比较的排序最坏情况下比较次数的下界是O(n log n)。这里特别想强调一下稳定性。很多学生只知道“稳定就是相同元素排序后相对顺序不变”但不知道怎么判断。以归并排序为例归并操作时如果左子序列的当前元素和右子序列的当前元素值相等先取左子序列的元素这样相同元素的相对位置就不会变化所以归并稳定。快速排序为什么不稳定因为partition过程会交换元素可能把相同的元素换到对面去。这种“看得见机制”的记忆方式比死背表格靠谱得多。2.3 图论基础概念最短路、生成树、入度出度第6-10题里如果出现图论一般不会让你写Dijkstra的具体代码而是考概念和算法特性。比如无向图的度数和边数的关系有向图的入度和出度。Dijkstra不能处理带负权边的图Floyd可以处理但复杂度高。最小生成树的两种算法Prim适合稠密图Kruskal适合稀疏图。连通图、连通分量、生成树这些基本定义。最容易翻车的点有两个一是把有向图和无向图的“度”搞混二是看到“最短路径”就默认可以用Dijkstra忽略了负权边的情况。选择题里只要出现“任意”“总是”这种绝对化字眼通常都有问题。2.4 组合计数与概率分步与分类的边界组合计数在初赛里属于“数学底子”题很多时候不是不会算而是算错方向。核心是两个基本原理分类用加法分步用乘法。题目里出现“至少”“至多”“恰好”时要先把语言翻译成数学条件。举个例子求“至少一本”的分配方案既可以用容斥原理也可以先按人数拆分再分配。这两种方法在答案一致的前提下一个考验思维严密性一个考验分组基本功。后面第4章我会用一道典型题把两种解法都走一遍。2.5 基础数据结构模拟栈、队列、堆的操作结果这类题一般给一个操作序列问你最后的结果是什么或者判断某个输出序列是否可能。栈的“后进先出”是考查重点队列的“先进先出”和循环队列的判满判空也经常出现。堆的话通常会让你模拟插入一个元素后从堆底向上调整的过程或者删除堆顶后从堆顶向下调整的过程。我在初赛监考时观察到一个现象很多学生做这类题靠“脑子里放电影”不愿意在草稿纸上画栈和队列。实际上哪怕只画一个三层的小栈也能避免一半以上的低级错误。数据结构模拟题是最应该动笔的题型没有之一。3. 选择题解析的通用三步法读题、判定、排除3.1 第一步圈出题干里的“考点信号词”做选择题第一步不是看选项而是把题干里的关键词圈出来。尤其是这几类词否定词“不正确”“错误的是”“不可能”。很多人不是不会做而是把“不正确”看成了“正确”一失手就是2分。程度词“一定”“必须”“任意”“总是”。这些词通常意味着需要举反例验证而不是凭感觉判断。方向词“按关键字比较次数”“平均时间复杂度”“最坏情况下”。这些词直接决定了你要调取哪个知识模块。2019年的选择题里这类“信号词”出现频率不低。做题太快的学生容易直接扫选项结果被出题人埋的“不正确”坑了个正着。我的建议是读题时拿笔在题干上画圈把否定词和条件词标出来再去看选项。这个动作最多花5秒钟但能有效防空。3.2 第二步把每个选项当成判断题来验大多数人的做题习惯是扫一眼选项凭印象选一个“看起来对”的答案剩下三个选项基本不看。这种做法在基础题上也许能蒙对但到了第6-10题这个难度区间很容易翻车。正确的做法是把每个选项当成一道是非题逐个验证。尤其是题干问“错误的是”的时候你需要先找出三个正确的选项剩下的才是答案。这个过程相当于给自己装了一个保险机制即使某个选项模糊不清至少能通过排除法缩小范围。我给学生的比喻是这就像考驾照时的科目三冠军不是开得最快的车而是不违规的车。选择题比的就是谁更稳不是谁更敢猜。能说出三个选项为什么对那个剩下的“错误项”往往自己就暴露了。3.3 第三步排除也要有“证据链”计算题必须写草稿排除法不是“看着不对就排除”而是要有依据地排除。常见依据有三类违反定义、缺少条件、计算数值不符。如果你只说“我感觉这个不对”那和蒙没有区别。计算型选择题还要注意一个习惯用草稿纸。5本书分给3个小朋友这种题心算很容易把某个系数漏掉排序比较次数、二叉树遍历的推演更需要在纸上一步步来。初赛虽然不写程序但“动笔模拟”本身就是竞赛的基本功。我的习惯是每道计算题都在草稿纸上留下完整推导过程这样最后检查的时候还能看到原始思路。4. 四道同源典型题的解析思路还原考虑到不同版本的回忆题在措辞上会有差异我特意选了四道和2019年第6-10题同知识模块、同难度层次的典型题来做演示。你用这四道题练熟方法再回头做当年的真题会发现思路完全套得上。4.1 遍历推树已知先序和中序求后序题目某二叉树先序遍历为ABDCE中序遍历为BDACE求后序遍历。拿到题先不要慌按“先序找根、中序分左右”的流程走。第一步先序序列第一个元素是A所以根节点是A。第二步在中序序列BDACE里找到A的位置A左边是BD这是左子树的中序序列A右边是CE这是右子树的中序序列。第三步回到先序序列去掉根A之后剩下的序列是BDCE。左子树占前面两个位置BD右子树占后面两个位置CE。所以左子树的先序是BD右子树的先序是CE。第四步递归处理左子树先序BD中B是根中序BD中B左边为空右边是D所以D是B的右孩子。递归处理右子树先序CE中C是根中序CE中C左边为空右边是E所以E是C的右孩子。最后后序遍历就是先左子树、再右子树、最后根。左子树的后序是DB右子树的后序是EC根是A所以最终结果是DBECA。这里有个快速验证的小技巧后序遍历的最后一个字符一定是根节点A而先序遍历的第一个字符也是A两个序列的首尾能对上说明结构没推错。4.2 排序性质判断哪个说法才是真命题题目关于排序算法以下说法正确的是 。A. 快速排序的比较次数在任意情况下都小于冒泡排序 B. 归并排序是稳定排序 C. 堆排序在任何情况下的时间复杂度都是O(n log n) D. 简单选择排序是稳定排序这道题最大的陷阱是“绝对化”。A选项里“任意情况下”就是典型错误信号快速排序最坏情况会退化到O(n²)而冒泡排序最好情况下可以做到O(n)所以“都小于”完全不成立。C选项的“任何情况下”也不对建堆的复杂度虽然是O(n)但堆排序整体是O(n log n)问题出在“任何情况”这个措辞太绝对最坏、平均、最好都是O(n log n)倒是没错可真正的考点其实是稳定性判断。D选项简单选择排序每次选择最小的元素放到前面交换过程可能把相同元素的相对顺序打乱所以它是不稳定的。B选项正确归并排序的归并操作遇到相同元素时优先取左子序列能保证相对顺序不变所以稳定。归纳一下这道题真正考的是两张表一张是复杂度表一张是稳定性表。做题时先扫“绝对化”说法再锁定“稳定性”细节基本就能定位答案。4.3 组合计数5本不同的书分给3个小朋友题目把5本互不相同的书全部分给3个小朋友要求每个小朋友至少得到1本一共有多少种分法第一种解法用容斥原理。不考虑“至少一本”限制时每本书有3个选择总共3⁵243种分法。减去有小朋友空手的情况先选1个空手小朋友有C(3,1)3种选法剩下5本书分给2个小朋友每本书2个选择共2⁵32种所以3×3296种。但这会把两个小朋友同时空手的情况多减一次需要加回来选2个空手小朋友C(3,2)3种剩下5本全部给最后1个小朋友只有1种共3种。所以最终答案是243-963150种。第二种解法先分组再分配。5本书分给3个组每组至少1本只有两种分组模式3、1、1或1、2、2。3、1、1的分组数是从5本里选3本放一组剩下两本各一组即C(5,3)10。1、2、2的分组数是C(5,2)×C(3,2)再除以2!因为两个2本组是等价的算出来是15。总分组数101525。再把3个组分配给3个不同的小朋友乘以3!得到25×6150。两种方法殊途同归。这道题最经典的易错点是“分给人”和“分组”混为一谈。一旦忘记除以重复排列或者忘记分给不同人要排序答案就会差出好几倍。4.4 栈的合法性给定入栈顺序判断出栈顺序题目一个栈的入栈序列是1、2、3、4、5以下哪个出栈序列不可能出现 。A. 54321 B. 32154 C. 31245 D. 21543这种题不需要背公式在草稿纸上画个栈模拟就行。A选项1、2、3、4、5全部入栈后依次弹出完全合法。B选项1、2、3入栈后弹出3再弹出2、1然后4、5入栈弹出5、4合法。D选项1、2入栈弹出2、1再3、4、5入栈依次弹出5、4、3合法。C选项为什么不可能因为3要第一个出栈说明1、2都已经入栈了而1先入栈、2后入栈所以2一定在1的上面。栈是后进先出2必须先于1出栈。C里3出栈后紧跟着出栈的是1这说明2还压在下面显然违反栈的规则。这类题还有一个进阶结论n个元素入栈出栈序列的总数是卡特兰数。但初赛选择题一般只要你会模拟判断备考时不必在卡特兰数的推导上花太多时间。5. 当年考生在这一区间丢分的真实原因复盘5.1 一道题死磕太久时间分配失控我见过太多学生整场考试复盘下来发现第7题做了8分钟不算难但就是不甘心。初赛选择题一共15道合理时间分配是20到25分钟平均每道题一分半左右。一旦超过2分钟还没思路最明智的做法是先在卷子上标记一个候选答案然后跳过等到做完全卷再回头。死磕一道选择题丢的不只是这2分还有后面阅读程序题的大量思考时间。5.2 计算题不写草稿全凭脑子演算第6-10题区间的计算量其实不大但足够让“心算选手”翻车。二叉树遍历的左右子树划分、组合计数的乘法因子、栈操作的过程模拟只要在草稿纸上落下来每一步都能回溯。很多学生觉得选择题简单不需要草稿纸结果中间某个系数写漏了整道题带偏。初赛的草稿纸是合法资源不用白不用。5.3 被绝对化表述带偏缺少特例意识“任何情况”“一定”“总是”这类词是命题人最喜欢埋的雷。看到这些词第一反应不是“这个选项可能对”而是“我要找反例”。快速排序一定比冒泡快吗不一定最坏情况就相反。稳定排序一定比不稳定排序好吗要看场景。培养“找反例”的条件反射能帮你躲掉一多半的绝对化陷阱题。5.4 没有形成“先易后难”的做题节奏选择题部分未必必须从第1题做到第15题。你完全可以先把自己最有把握的题目做完再回头处理卡壳的题。2019年第6-10题里如果有一道组合计数让你很不舒服先放一放把后面阅读程序题里比较稳的分数拿到手再回来看它。这个策略和心理素质也是初赛要练的内容之一。6. 从第6-10题的失分点反推备考动作6.1 三轮复习法记忆、理解、模拟第一轮按知识点模块复习。树、排序、图论、计数、数据结构模拟每个模块先把理论吃透。这一轮不要刷成套的真题刷了也是浪费。第二轮做近五年的初赛真题但做题不是目的做完后把每道选择题考查的知识点标注在题号旁边形成“考点坐标图”。第三轮限时模拟。拿出一整张真题卷按考试时间走一遍重点观察选择题部分用时是否超过25分钟。6.2 建立自己的考点自查表这里给一个参考模板你自己在复习时可以根据实际情况增减行考点模块常见考法我的薄弱点是否已复习二叉树遍历已知两序推一序、还原结构中序分左右偶尔出错否排序性质复杂度、稳定性、比较次数稳定性判断靠硬背否图论概念最短路算法适用范围、生成树Dijkstra负权边理解不透是组合计数分组分配、容斥原理除以重复排列总忘否数据结构模拟栈序列合法性、堆调整过程堆的向下调整边界情况是这张表的价值在于它把“我不太会”变成了一条一条具体的复习任务而不是笼统的“我要多刷题”。6.3 刷真题的正确姿势不只对答案要写“选错原因”做完一道题对完答案多问自己一句我当初为什么选了那个错误选项是因为概念记错还是因为读题漏了“不正确”还是计算过程出了错把这些原因直接写在题目旁边。到了考前一周翻错题本时你真正要看的不是正确解法而是那一行行“犯错原因”——它们比任何笔记都更能提醒你考场上该注意什么。我在实际辅导中反复和学生说初赛选择题第6-10题不是难题但它是最能暴露基础是否扎实的地方。2019年这个区间几乎把树、排序、图论、计数、数据结构模拟五块基础内容各考了一遍你要是能在这五道题上快速稳定拿分说明知识体系已经成型。与其刷十套新题不如先把这种“读题-定位考点-动笔验证”的节奏练熟。当年我在这个区间也错过题错的都是觉得“大概对吧”的选项——后来我养成了一个习惯选择题的答案必须能在草稿纸上给出理由说不出理由的选项一律先怀疑。这个小习惯对初赛和复赛都有用。
