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) 的增长率。本题中 a=2，b=2，所以 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*(b+c)-d 的后缀表达式是？

A. abc*+d- B. ab+c*d- C. abc+d- D. ab+c-d

答案：C，abc+*d-。

中缀表达式转后缀，是栈这个数据结构最经典的应用场景。我习惯用的方法是“加括号大法”：先按运算顺序给整个表达式补全括号，然后从最内层开始，把每个运算符移动到它所在那一层右括号的后面。

以这道题为例，a*(b+c)-d 完整加括号后是 ((a*(b+c))-d)。最内层 b+c 的后缀是 bc+；接着 a*(bc+) 变成 abc+*；最后整体再减去 d，得到 abc+*d-。这个方法的好处是几乎不会出错，而且对复杂嵌套表达式同样适用。

3.2 栈模拟的完整流程

如果只背“加括号大法”而不理解栈的运作，一旦题目变成“根据后缀表达式求值”或者“判断某个序列能不能由栈输出”，还是会卡住。所以栈模拟的规则也建议吃透：

从左到右扫描中缀表达式，遇到操作数直接输出；遇到运算符，先看栈顶。如果栈顶运算符优先级不低于当前运算符，就弹出栈顶并输出，一直弹到栈顶优先级更低为止，再把当前运算符压入栈。遇到左括号直接压栈，遇到右括号则一直弹出并输出，直到弹出左括号，左括号本身不输出。

用这个规则跑一遍 a*(b+c)-d：输出 a；乘号压栈；左括号压栈；输出 b；加号压栈（因为栈顶是左括号，不弹）；输出 c；遇到右括号弹出加号并输出；遇到减号时栈顶是乘号，乘号优先级高于减号，弹乘号输出，再压入减号；输出 d；最后弹出减号。最终就是 abc+*d-，和加括号法的结果完全一致。

3.3 常见陷阱提醒

这题最大的坑是选项 A 的 abc*+d-。它看起来很像正确答案，但对应的是表达式 ab+c-d，也就是先算 ab，再算 c，最后统一加减。很多同学转后缀时习惯把乘号先输出，忽略了 b+c 因为有括号必须先结合，结果就掉进这个陷阱。

判断后缀表达式是否正确有个快速自检法：把写出来的后缀表达式再模拟栈还原成中缀，如果能还原回原表达式，就说明正确。每次做完这类题都花十秒钟验证一下，能避免大部分粗心错误。

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-L2+1，不是 R1-L1+1，这两个数特别容易搞混。

本题中，i=4，j=5，基地址100，总列数=6-0+1=7，单个元素4字节。代入公式：100 + ((4-0)*7 + (5-0))*4 = 100 + (28+5)*4 = 100+132 = 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-1=2，不是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、中序 BD，B 是根，中序里 D 在 B 右边，说明 D 是 B 的右孩子。再递归处理右子树：前序 CEF、中序 ECF，C 是根，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

答案：B，15。

无向完全图的边数是 C(7,2)=21，也就是7个顶点两两之间都有一条边。而一棵7个顶点的树，边数一定是7-1=6。要把完全图变成树，需要删掉的边数就是 21-6=15。

这里要用到两个基础公式：无向完全图 n 个顶点的边数是 n(n-1)/2；n 个顶点的树边数是 n-1。有向完全图的边数则是 n(n-1)，因为每两个顶点之间有两条不同方向的边。初赛偶尔会把有向和无向放在同一个题干里当陷阱，读题时一定要圈出“无向”还是“有向”。

6.2 公式记不住时怎么办

如果考场上一时想不起公式，可以用小规模特例来推。拿 n=3 举例，3个顶点的无向完全图是三角形，有3条边；3个顶点的树需要2条边；要变成树需要删 3-2=1 条边。用这个特例反推一般情况，n个顶点的完全图边数就是 n(n-1)/2，树边数是 n-1，删除数是 n(n-1)/2 - (n-1) = (n-1)(n-2)/2。代入 n=7，得到 (6*5)/2=15。

特值法在初赛选择题里非常好用，尤其是遇到公式记忆模糊的时候。与其空想，不如画一个最小的例子，把规律看清楚再推广。

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这组题型的排查表，遇到问题可以直接对照。

8.2 考场时间策略

选择题6到10虽然不算最难的题，但计算量大，一旦卡住容易打乱整场节奏。我一般给自己定一条红线：这五道题总用时不超过8分钟。如果某道题30秒内没有明确思路，先跳过去，做完后面的题再回头处理。初赛的时间风险通常不在个别难题，而在某道题上耗太久导致后面大题全部赶工。

计算过程中多用特值法和排除法。特值法能帮你快速验证公式，排除法能直接消灭明显错误的选项。比如树遍历题，先看后序最后一位是不是根；数组地址题，先看 A[0][0] 代进去是不是基地址。这些操作加起来不到十秒，却能避免大量低级失误。

8.3 一点个人体会

我梳理这五道题最深的感触是：初赛选择题并不靠新知识，靠的是基础熟练度。同样是复杂度递归式，有人需要完整推导主定理才能确定答案，有人看到“2T(n/2)+nlog2n”这种结构就能直接反应出 O(nlog^2 n)，差距就是反复训练拉开的。

所以别小看这五道“只有2分”的选择题。吃透它们，不仅初赛稳拿分，更重要的是，复杂度分析、栈、数组存储、二叉树、图这些基本功，会在后面每一年的竞赛里反复用到。把这组题练到“闭眼都能写对”，你收获的远不止5道题的分数。