2019年CSP-S第一轮选择题第6到第10题是整张卷子里很值得反复刷的一组题目。它们正好卡在“基础概念”和“复杂计算”的过渡地带前5题基本是记忆型送分后面开始进入阅读程序和补全程序大题而6-10就是那个承上启下的计算密集区。这五道题覆盖的知识点非常集中时间复杂度递归式、中缀表达式转后缀、二维数组地址计算、二叉树遍历还原、无向图与生成树。把这些题吃透相当于提前给后面的程序题铺好了路。本文按通用版本逐题拆解把每一题的答案、推导过程、常见错选原因一起讲清楚。1. 先看清这五道题在整张卷子里的位置1.1 为什么6-10是初赛的“分水岭”CSP-S第一轮是笔试满分100分选择题占的分值不算低。前5题通常考计算机基础、进制转换、语言基本概念这类内容只要平时背过就能快速拿分。但从第6题开始命题风格明显转变不再问“是什么”而是问“怎么算”。这时候光靠记忆就不够了需要真正动笔推导。我见过不少参赛选手前5题做完只花了几分钟信心满满结果在6-10上开始卡壳。尤其是时间复杂度递归式和数组地址计算这类题一旦方法不熟练一道题磨掉五六分钟很正常。更要命的是初赛答题时间本身就紧张后面还有阅读程序、补全程序这些耗时间的大题。所以6-10这部分做得顺不顺直接影响整场考试的节奏。从考点分布看这五道题基本锁定了“数据结构与算法基础”中最核心的几个模块复杂度分析、栈与表达式、多维数组存储、二叉树、图。这些都是后续上机考试里反复使用的基本功。初赛把它们放在选择题里其实是在提醒大家基础不牢后面寸步难行。1.2 真题版本说明与复习定位先说一个很多人在刷题时会纠结的问题网上流传的2019年CSP-S初赛回忆版6-10题在个别用词、数字、选项顺序上可能有细微出入。这是因为初赛题目不同渠道整理时会有偏差但知识点高度稳定核心考点几乎年年不变。所以本文采用大家普遍使用的一个通用版本逐题拆解。你手边的题面如果数字或者下标略有不同不用慌把数字替换进对应公式即可。真正要盯住的不是题号而是每个题背后的解法模板。初赛命题喜欢“换数字不换思路”一套方法吃透能应对好几年的同类题。复习定位上我建议把6-10当成“手算基本功训练组”。这一组题不要求你掌握什么高深算法但要求公式熟练、计算准确、反应够快。每天花10分钟专门刷这类基础计算题比考前突击看十页笔记都有效。2. 第6题时间复杂度递归式主定理一下看出答案2.1 题面与答案解析题目版本若某算法的计算时间满足递归式 T(n)2T(n/2)nlog2n且 T(1)1则该算法的时间复杂度为A. O(n) B. O(nlog2n) C. O(nlog2^2 n) D. O(n^2)答案C。这里需要说明一下O(nlog2^2 n) 里的 log2^2 n 表示 (log2 n)^2也就是 log2 n 的平方。这个写法是竞赛里的常见简写别理解成对 log 再取 log。这题最直接的解法是用主定理。主定理处理的是形如 T(n)aT(n/b)f(n) 的递归式核心是比较 f(n) 和 n^(log_b a) 的增长率。本题中 a2b2所以 n^(log_b a)n^(log2 2)n。再看 f(n)nlog2n它恰好是 n 乘以一个 logn 因子正好落在主定理第二种情况T(n)Θ(n log2^2 n)。如果对主定理不熟用递归树也能推出同样结论后面细说。2.2 为什么很多人会误选B选B的同学通常思路很简单看到递归式里有个 2T(n/2)就联想到归并排序的复杂度 O(nlog2n)于是把后面的 nlog2n 当成合并代价认为总复杂度就是 O(nlog2n)。但这里有个微妙差别归并排序的递归式是 T(n)2T(n/2)O(n)合并代价是线性的 n不是 nlog2n。用递归树来看会更清楚。递归树一共 log2n 层第 i 层有 2^i 个节点每个节点的合并代价是 (n/2^i)log2(n/2^i)。把每一层的总代价加起来得到 n(log2n - i)。对所有层求和结果是 n 乘一个从 log2n 加到 1 的和也就是 O(nlog2^2 n)。如果合并代价只是 n每一层总代价才是 n最后才是 O(nlog2n)。考场上的快速排错法假设答案真是 O(nlog2n)把它代回递归式右边2*(n/2 * log2(n/2)) nlog2n n(log2n - 1) nlog2n 2nlog2n - n这个结果明显比 nlog2n 要大说明假设不成立。虽然代入验证不是严格的证明但在选择题里用来排除错误选项效果极好。3. 第7题中缀转后缀用栈模拟一遍最稳3.1 题面与答案解析题目版本表达式 a*(bc)-d 的后缀表达式是A. abc*d- B. abc*d- C. abcd- D. abc-d答案Cabc*d-。中缀表达式转后缀是栈这个数据结构最经典的应用场景。我习惯用的方法是“加括号大法”先按运算顺序给整个表达式补全括号然后从最内层开始把每个运算符移动到它所在那一层右括号的后面。以这道题为例a*(bc)-d 完整加括号后是 ((a*(bc))-d)。最内层 bc 的后缀是 bc接着 a*(bc) 变成 abc*最后整体再减去 d得到 abc*d-。这个方法的好处是几乎不会出错而且对复杂嵌套表达式同样适用。3.2 栈模拟的完整流程如果只背“加括号大法”而不理解栈的运作一旦题目变成“根据后缀表达式求值”或者“判断某个序列能不能由栈输出”还是会卡住。所以栈模拟的规则也建议吃透从左到右扫描中缀表达式遇到操作数直接输出遇到运算符先看栈顶。如果栈顶运算符优先级不低于当前运算符就弹出栈顶并输出一直弹到栈顶优先级更低为止再把当前运算符压入栈。遇到左括号直接压栈遇到右括号则一直弹出并输出直到弹出左括号左括号本身不输出。用这个规则跑一遍 a*(bc)-d输出 a乘号压栈左括号压栈输出 b加号压栈因为栈顶是左括号不弹输出 c遇到右括号弹出加号并输出遇到减号时栈顶是乘号乘号优先级高于减号弹乘号输出再压入减号输出 d最后弹出减号。最终就是 abc*d-和加括号法的结果完全一致。3.3 常见陷阱提醒这题最大的坑是选项 A 的 abc*d-。它看起来很像正确答案但对应的是表达式 abc-d也就是先算 ab再算 c最后统一加减。很多同学转后缀时习惯把乘号先输出忽略了 bc 因为有括号必须先结合结果就掉进这个陷阱。判断后缀表达式是否正确有个快速自检法把写出来的后缀表达式再模拟栈还原成中缀如果能还原回原表达式就说明正确。每次做完这类题都花十秒钟验证一下能避免大部分粗心错误。4. 第8题二维数组地址计算行优先列优先别搞反4.1 题面与答案解析题目版本设二维数组 A[0..5,0..6]每个元素占4字节已知 A[0][0] 的地址是100按行优先存储求 A[4][5] 的地址。答案232。数组地址计算是初赛选择题里的常客核心就一个公式。对于数组 A[L1..R1][L2..R2]行优先时元素 A[i][j] 的地址等于 基地址 ((i-L1)*总列数 (j-L2))*单个元素字节数。注意总列数是 R2-L21不是 R1-L11这两个数特别容易搞混。本题中i4j5基地址100总列数6-017单个元素4字节。代入公式100 ((4-0)*7 (5-0))*4 100 (285)*4 100132 232。如果把同样的题改成列优先公式就变成基地址 ((j-L2)*总行数 (i-L1))*单个元素字节数结果是 100 ((5-0)*6 (4-0))4 100 344 236。所以拿到题目第一件事是看清楚存储顺序。4.2 考场上的三个惯性坑第一个坑是下标起点。如果题目写的是 A[1..n][1..m]计算时一定要用 i-L1 而不是直接用 i。比如 A[3][4] 在 A[1..5][1..6] 中行偏移是 3-12不是3。第二个坑是单位换算。有的题说每个元素占4字节有的题说数组总字节数还有的题把每个元素描述成“占4个存储单元”。无论说法怎么变最后都要拿到“单个元素字节数”这个值。第三个坑是把行数和列数搞反。A[0..5][0..6] 的实际行数是6列数是7。计算行偏移时乘的是列数7不是行数6。我在教学中看到太多人在这里栽跟头明明公式背得滚瓜烂熟最后因为行列颠倒丢分。检查技巧很简单算完 A[0][0] 的地址必须还是基地址再算 A[0][1] 和 A[1][0]如果 A[0][1] 比 A[1][0] 小一个元素大小说明当前用的是行优先。这个特值检验法十秒钟就能完成强烈建议考场必做。5. 第9题二叉树遍历互推先定位根再分割5.1 题面与答案解析题目版本一棵二叉树的前序遍历为 ABDCEF中序遍历为 BDAECF求后序遍历。答案DBEFCA。这类题的做法是一步一步递归分割。前序遍历的第一个节点一定是整棵树的根这里就是 A。拿着 A 去中序遍历里找位置中序序列 BDAECF 中A 的左边是 BD说明左子树由 BD 组成A 的右边是 ECF说明右子树由 ECF 组成。再看前序序列跟在 A 后面的 BD 就是左子树的前序CEF 就是右子树的前序。递归处理左子树前序 BD、中序 BDB 是根中序里 D 在 B 右边说明 D 是 B 的右孩子。再递归处理右子树前序 CEF、中序 ECFC 是根E 在 C 左边、F 在 C 右边所以 E 和 F 分别是 C 的左、右孩子。树形结构还原后后序遍历的规则是“先左子树、再右子树、最后根”。左子树的后序是 DB右子树的后序是 EFC最后加上根 A得到 DBEFCA。5.2 为什么前序后序不能唯一确定这题给的是前序中序所以能唯一确定二叉树。但初赛还喜欢考一个知识点只有前序和后序通常无法唯一确定一棵二叉树。原因很简单当一个节点只有一个孩子时单靠前序和后序无法判断这个孩子到底是左孩子还是右孩子。比如前序 AB、后序 BA这棵树既可以是 A 的左孩子是 B也可以是 A 的右孩子是 B。中序序列在这里起到了关键作用它把左右子树严格分开。所以凡是遇到树遍历互推的题第一步永远是“用前序或后序找根用中序分左右”。5.3 手算草稿的实用技巧我建议这类题别直接在两个序列之间反复划来划去先在草稿纸上画一棵简易树。画出根、左右子树、再把子树的根标上最后根据树形直接写后序。画树的过程看似多花了几秒实际上能避免大量脑内推演造成的混乱。还有一种排除法后序遍历的最后一个节点一定是整棵树的根所以无论选项怎么变最后一位必须是 A。如果哪个选项最后不是 A直接划掉。这个技巧虽然简单但在考试紧张状态下非常实用能帮你快速缩小范围。6. 第10题完全图到生成树用 n-1 卡住边界6.1 题面与答案解析题目版本由7个顶点组成的无向完全图至少要删除多少条边才能得到一棵生成树A. 14 B. 15 C. 16 D. 21答案B15。无向完全图的边数是 C(7,2)21也就是7个顶点两两之间都有一条边。而一棵7个顶点的树边数一定是7-16。要把完全图变成树需要删掉的边数就是 21-615。这里要用到两个基础公式无向完全图 n 个顶点的边数是 n(n-1)/2n 个顶点的树边数是 n-1。有向完全图的边数则是 n(n-1)因为每两个顶点之间有两条不同方向的边。初赛偶尔会把有向和无向放在同一个题干里当陷阱读题时一定要圈出“无向”还是“有向”。6.2 公式记不住时怎么办如果考场上一时想不起公式可以用小规模特例来推。拿 n3 举例3个顶点的无向完全图是三角形有3条边3个顶点的树需要2条边要变成树需要删 3-21 条边。用这个特例反推一般情况n个顶点的完全图边数就是 n(n-1)/2树边数是 n-1删除数是 n(n-1)/2 - (n-1) (n-1)(n-2)/2。代入 n7得到 (6*5)/215。特值法在初赛选择题里非常好用尤其是遇到公式记忆模糊的时候。与其空想不如画一个最小的例子把规律看清楚再推广。6.3 相关变体要一起掌握这道题还可以延伸出几个变体如果告诉你一个连通图有 n 个顶点、m 条边问至少删几条边才能变成树答案恒为 m-(n-1)。如果题目改成“不连通图要加几条边才能连通”答案等于连通分量数减1。如果把完全图替换成稀疏图那就要先算实际边数再减去 n-1。理解了“树边数n-1”这个底层逻辑这些变体其实都是同一道题。初赛喜欢在选择题里这样玩花样但核心公式不会变。7. 五道题背后的共性考点与备考策略7.1 高频考点画像把这五道题放在一起看可以提炼出一个很清晰的考点清单复杂度分析、表达式处理、存储结构、二叉树、图论基础。这些内容没有一个是超纲的全部是数据结构与算法最底层的知识。我对准备提高组的同学有个建议为每个考点整理一个“手算模板”。复杂度递归式就记主定理三种情况表达式转换就记加括号法和栈模拟数组地址就记行优先、列优先两个公式树遍历就记“根左右、左根右、左右根”的定位方法图就记完全图和树的边数公式。这些模板不用多每个考点的核心解法就一两句话考前过一遍非常高效。7.2 三轮刷题法做这类经典题我推荐三轮刷法。第一轮不限时每一题都完整推导把原理彻底搞懂第二轮限时五道题一起做目标控制在8分钟以内训练考场节奏感第三轮做变体手动换掉题目里的数字、改条件比如把行优先改成列优先、把 n 从7改成10用同样的解法再算一遍。我在准备初赛阶段就是把6-10这类基础计算题反复练到形成条件反射。看到“2T(n/2)nlog2n”直接想到 O(nlog^2 n)看到“无向完全图7个顶点删边成树”直接写15。这种条件反射不是靠死记硬背而是靠大量重复训练建立起来的。7.3 错题整理不要只记答案很多同学整理错题时只写个正确答案过两周再看完全不知道当初为什么错。我的习惯是在每道错题旁边用一句话写“我当时的错误判断”和“正确的判断依据”。比如这五道题里如果错在第8题就写“我当时把行列数算反了正确公式是行偏移乘列数”。这样复习时一眼就能看到自己思维的盲区比反复看题目和选项有用得多。8. 常见问题与排查技巧实录8.1 五个高频问题的速查表这里整理一份针对6-10这组题型的排查表遇到问题可以直接对照。现象可能原因处理方式复杂度递归式套错主定理混淆了第二种和第三种情况比较 f(n) 与 n^(log_b a)只差一个 log 因子就是第二种后缀表达式算出来和答案对不上运算符输出顺序错了用加括号大法重新转或者用栈把后缀还原回中缀验证数组地址计算差一个字节量行列数取反或下标起点没减先写公式再代入 A[0][0] 验证基地址树遍历还原结果不稳定没有先画树脑内推演混乱草稿纸上分层画树再按左右根写后序图删除边数多算或少算完全图公式或树边数记错用 n3 的小例子快速验证公式8.2 考场时间策略选择题6到10虽然不算最难的题但计算量大一旦卡住容易打乱整场节奏。我一般给自己定一条红线这五道题总用时不超过8分钟。如果某道题30秒内没有明确思路先跳过去做完后面的题再回头处理。初赛的时间风险通常不在个别难题而在某道题上耗太久导致后面大题全部赶工。计算过程中多用特值法和排除法。特值法能帮你快速验证公式排除法能直接消灭明显错误的选项。比如树遍历题先看后序最后一位是不是根数组地址题先看 A[0][0] 代进去是不是基地址。这些操作加起来不到十秒却能避免大量低级失误。8.3 一点个人体会我梳理这五道题最深的感触是初赛选择题并不靠新知识靠的是基础熟练度。同样是复杂度递归式有人需要完整推导主定理才能确定答案有人看到“2T(n/2)nlog2n”这种结构就能直接反应出 O(nlog^2 n)差距就是反复训练拉开的。所以别小看这五道“只有2分”的选择题。吃透它们不仅初赛稳拿分更重要的是复杂度分析、栈、数组存储、二叉树、图这些基本功会在后面每一年的竞赛里反复用到。把这组题练到“闭眼都能写对”你收获的远不止5道题的分数。