到了秋招季算法岗笔试的第一步往往不是编程题而是十几道看似零散的选择题。最近我在整理2020算法练习一的专题把某短视频平台2020校园招聘秋招笔试算法A卷的选择题重新复盘了一遍最大的感受是题干短但每个选项都在挖坑。很多同学刷题时只记住“答案是B”换个问法就完全找不到北。这篇文章不打算只给答案我会从命题逻辑开始讲再给出通用解法和一组贴近原卷风格的练习选择题最后说说怎么用这套卷子反推复习计划。正在筹备校招笔试、想提高选择题正确率的同学可以直接按这篇的思路去练。1. 复盘之前先弄懂A卷选择题的出题意图1.1 选择题在筛选什么不是记住结论而是理解边界算法岗的笔试选择题存在一个很容易被低估的特点它不像编程题那样只要能跑通就算过而是把一个知识点的“边界条件”做成四个选项。比如同样是“快速排序”基础题考平均复杂度进阶题就考最坏情况什么时候出现再进阶一点就考“大量重复元素时快排为什么退化”。这三个考法表面都在说快排实际上分别对应结论、边界、机制。所以选择题真正筛掉的是那些只会背结论的人。命题人不会把“快排平均复杂度是多少”这种话写上去而是把平均复杂度、最坏复杂度、空间复杂度、稳定性混在一起再塞一个“归并排序也稳定所以可以替换”的诱导项。你只要对任何一个概念的理解有裂缝这道题就变成了纠结题。这也是为什么A卷会把选择题放在最前面。系统直接判分不需要人工看过程效率很高。几十道题扫过去每个考点覆盖一次分数梯度自然拉开。对于候选人来说这些题不是“热身”而是第一道门槛。你连题都看不完、算不对后面的编程题根本没机会展示。1.2 A卷的大致科目配比和时间预算我不可能把原卷原样搬过来但按常规校招算法卷的分布可以给出一个大致估计。算法A卷的选择题通常在10到20道之间科目配比有明显规律数据结构与算法基础占大头数学推导次之机器学习基础偶尔出现但不会超过三分之一。我按常见口径做了个估算表方便你对照自己的薄弱环节。考点模块大致题量占比常见出题方式难度数据结构栈、队列、树、图、哈希30% ~ 40%性质判断、结构计算、冲突处理中算法策略排序、二分、DP、贪心、字符串30% ~ 40%复杂度计算、边界条件、适用场景中高数学基础递推、概率、期望、组合10% ~ 20%期望推导、递推公式、计数中复杂度与代码细节10% ~ 20%最好/最坏情况、递归栈空间低中时间预算上我建议把选择题单题用时压到两到三分钟整套选择题不超过总时长的三分之一。如果你拿到卷子发现选择题有15道那就意味着你最多留给选择题45分钟剩下时间必须归编程题。很多同学挂在选择题上不是因为不会而是因为在一道题上死磕了十分钟最后编程题只能乱写。2. 选择题的三种通用解法特值代入、极端绑定、反例排除2.1 特值代入法用最简单的实例拆掉抽象题干选择题题干往往写成抽象形式比如“长度为n的数组”“含n个节点的完全二叉树”“n个关键字的哈希表”。抽象形式看起来难其实恰恰适合用具体数字代入。我复盘这套A卷时遇到不少同学在二叉树节点计算题上翻车。题目的标准描述是“一棵完全二叉树共有n个结点求叶子结点数”。有人直接背公式背错了就完蛋。我的做法是先取特例n1时叶子数是1n2时叶子数是1n3时叶子数是2然后把这些结果代入已知关系式校验马上就能发现自己的公式哪里出了问题。特值法的好处是你不需要从抽象层面理解完整关系只需要找到一个小规模实例把选项里的答案一个个代进去比对就能锁定。2.2 极端法与反例法找到最容易反转的那个条件很多选择题的干扰项来自绝对化表述。比如“时间复杂度是O(n log n)的排序一定比O(n²)快”“Dijkstra算法可以处理负权边”“快排总是比堆排序快”。这类说法只要遇到一个反例就崩了。极端法就是主动构造那个反例。遇到复杂度比较题直接想象n等于1万、10万甚至100万时的增长曲线遇到排序题直接构造一个已经有序的数组、全部相同元素的数组遇到图算法题直接画一个带负权环的图。如果你发现构造出来的反例正好击中某个选项那这个选项基本就是错的。我印象很深的一道题是“以下哪种情况可能导致快速排序退化到O(n²)”很多同学一眼选中“数据完全随机”实际上随机数据恰恰是快排最舒服的场景真正容易退化的是“数据近似有序、基准取首元素、重复元素极多”这一组组合。这种题用极端法最有效因为你可以瞬间构造一个有序数组手动模拟一次划分过程看到分区比例极端失衡答案自然浮出来。2.3 考场时间策略选择题要做到“两分钟定生死”选择题不要求你写出计算过程所以它天然适合用“排除法加快速验证”的策略。我给自己定的规矩是拿到选项后先做一轮快速扫描能确定的秒选不能确定的用特值或反例在草稿纸上推一遍超过两分钟还没有头绪就标记题目蒙一个当前最可能的选项立刻进入下一题。这套策略看起来功利但校招笔试的通过线不是满分而是前百分之二三十。你不需要每道题都对你需要的是把会做的题全部拿到分。死磕一道偏题损失的是后面两道简单题的时间。复盘这套A卷时我发现那些最终通过笔试的同学都有一个共性他们很少在某一道选择题上表现出“恋战”倾向。3. 贴近真题风格的十二道选择题逐题复盘先说清楚以下题目不是原题而是我按照A卷考察点整理的脱敏模拟题选项设计逻辑和原题高度一致。每道题我都会给出考点、答案、完整推演和易错点你可以先自己选一遍再看解析。3.1 复杂度与排序类第1-3题第1题对长度为n的数组执行快速排序平均时间复杂度是多少A. O(n) B. O(n log n) C. O(n²) D. O(log n)答案B。推演快排每次选择一个基准数把数组分成左右两半。平均情况下每次分区比例接近1:1递归层数约O(log n)每层要比较所有元素合计O(n log n)。要注意的是这里的“平均”指的是输入数据随机分布时的期望表现它不排除最坏情况。易错点有同学选O(n²)这是把最坏情况当默认情况。更有同学看到“快速”两个字就直接选O(n)完全没理解排序问题的下限。第2题以下稳定排序是A. 快速排序 B. 堆排序 C. 归并排序 D. 选择排序答案C。推演稳定性的定义是值相同的元素在排序前后相对顺序不变。归并排序在合并两个子数组时遇到相等元素总是先取左边因此稳定。快排的交换过程会跨越很远的位置相同值可能被换到另一边堆排序的调整过程是父子节点交换无法保证相对顺序选择排序每一轮会选一个最小值放到前面也可能跨过相等元素。易错点很多人记成“堆排序稳定”因为堆的交换看起来有顺序。实际上一旦你写一个堆调整过程就能发现相等元素的相对位置很容易被破坏。第3题已知归并排序的时间复杂度为O(n log n)它在合并两个有序子数组时额外空间复杂度为A. O(1) B. O(log n) C. O(n) D. O(n log n)答案C。推演合并时需要临时数组暂存结果长度最多等于当前待合并子数组的总长度也就是O(n)。虽然递归调用会占用栈空间但那属于另一部分空间这里单独问合并时的额外空间选O(n)没问题。易错点把递归栈空间也混进来最后算成O(n log n)。严格来说这也没错但单问“合并”就要看题目限定范围。3.2 数据结构细节类第4-7题第4题一棵完全二叉树共有1000个结点它的叶子结点数是多少A. 498 B. 499 C. 500 D. 501答案C。推演完全二叉树中只有度为0、1、2三种结点。设叶子结点数为n0度为1的为n1度为2的为n2。任意二叉树满足n0 n2 1总结点数n n0 n1 n2 n0 n1 n0 - 1 2n0 n1 - 1。对于1000个结点1000 2n0 n1 - 1。完全二叉树的n1只能是0或11000是偶数因此n1必须为1代进去解得n0 500。易错点忘记完全二叉树n1取值的约束直接用n/2取整有人得出499。这道题其实是在考“完全二叉树最后一层节点分布”和度关系式两个知识点。第5题哈希表长度为7哈希函数为H(key) key % 7采用链地址法处理冲突。依次插入关键字14、21、28、35、42每个关键字对应的链表长度分别是A. 全为1 B. 第一条长度为5其余为0 C. 五条链表各1 D. 无法确定答案B。推演14 % 7 021 % 7 028 % 7 035 % 7 042 % 7 0。五个关键字全部映射到0号槽所以0号链表长度为51到6号全空。易错点有些同学默认哈希函数是随机均匀的没有意识到“取模”在数据恰好是模数倍数时会全部撞车。这道题也提醒你链地址法不是不冲突而是冲突后还能正常存。第6题中缀表达式 a b * (c - d) / e 转换为后缀表达式结果是什么A. a b c d - * e / B. a b c d - e / * C. a b c d - * e / D. a b c d * - e / 答案A。推演先看括号内c-d后缀写为c d -然后乘号优先级高于括号外的除号所以先算乘法b c d - *再算除法e除最后加a得到a b c d - * e / 。可以用栈模拟验证遇到操作数直接输出遇到操作符比较优先级右括号弹出到左括号。易错点很多人把除法和乘法的顺序搞反写出B。关键在于乘号优先级和括号内部整体优先级后缀表达式的核心是“先出现的操作符不一定先输出”。第7题关于Dijkstra算法以下说法正确的是A. 能处理带负权边的图 B. 能处理带负权环的图 C. 能处理所有正权边图 D. 只能处理无向图答案C。推演Dijkstra基于贪心策略每次从未确定最短路的节点中选距离最小的扩展。它要求所有边权非负因为一旦扩展某个节点它的距离就不会再被其他未扩展节点更新。负权边存在时这个前提破坏算法可能给出错误结果。带负权环更不能用直接导致无最短路。易错点把Dijkstra和Bellman-Ford适用条件混淆。后者的价值恰恰在于能处理负权边Dijkstra不能。3.3 算法流程与边界类第8-10题第8题在长度为15的有序数组中做二分查找最坏情况下需要比较几次A. 3 B. 4 C. 5 D. 15答案B。推演每次比较后搜索区间减半15个元素最多需要ceil(log2(15 1)) 4次。你可以手动模拟第一次比较中点剩7个第二次剩3个第三次剩1个第四次找到或确定不存在。这就是下限。易错点有人记成“二分查找最多比较log n次”没加1。当n不是2的幂时实际比较次数要上取整后再加1。第9题关于拓扑排序以下说法正确的是A. 拓扑排序结果唯一 B. 有环图也可以拓扑排序 C. 每次优先选择入度为0的节点 D. 拓扑排序等价于深度优先遍历答案C。推演拓扑排序针对有向无环图核心操作是反复取入度为0的节点并删除其出边。因为入度为0意味着没有前驱可以安全输出。如果图中有环环上每个节点入度都不可能降到0所以无法完成排序。易错点拓扑排序结果不唯一因为同时可能有多个入度为0的节点可以选。很多同学只记住“和DFS有关”忽略Kahn算法用的其实是队列BFS思想。第10题主串长度为n模式串长度为m用朴素模式匹配算法最坏情况下的时间复杂度是A. O(n) B. O(m) C. O(n m) D. O(n * m)答案D。推演朴素算法在主串每个位置尝试匹配模式串一旦某个字符不匹配就右移一位。最坏情况是模式串前面m-1个字符都匹配最后一个字符不匹配例如主串“aaaaab”模式串“aaab”需要比较约n*m量级。易错点很多人知道KMP是O(nm)就把朴素算法也选成O(nm)。KMP的改进在于利用next数组跳过重复比较朴素算法没有这个优化差距就在这里。3.4 概率与递推类第11-12题第11题上楼梯一次可以跨1阶或2阶问上10阶楼梯有多少种不同走法A. 55 B. 89 C. 144 D. 34答案B。推演设f(n)为上n阶的走法数。最后一步可能是1阶或2阶所以f(n) f(n-1) f(n-2)初始f(1)1f(2)2。递推f(3)3f(4)5f(5)8f(6)13f(7)21f(8)34f(9)55f(10)89。易错点斐波那契数列从f(1)1, f(2)2出发而不是从f(0)0出发。有人从f(0)1开始算最后得出144其实那是另一种定义。做题时先写初始条件再递推不要凭感觉背数字。第12题连续掷一枚均匀硬币直到出现连续两次正面为止期望需要掷多少次A. 4 B. 5 C. 6 D. 8答案C。推演设E为从零状态开始掷到连续两次正面的期望次数再设H为当前已经连续掷出一个正面的期望次数。当前已有一次正面时下一次若仍是正面就结束若反面则回到零状态所以H 1 0.5 * E。零状态时下一次若反面仍在零状态若正面进入H状态所以E 1 0.5 * E 0.5 * H。联立可解E 6。易错点直接猜4的人把“两次正面”当成两次独立事件实际是连续条件需要考虑状态转移。这类题在选择题里属于中高难度但用状态递推就能稳定拿下。4. 选择题背后最容易翻车的三个数学细节4.1 递归空间复杂度的正确算法很多选择题目会问递归实现的空间复杂度最常见的是递归快排、归并排序、二叉树遍历。答案往往不是单纯O(n)或O(log n)而是“递归栈深度辅助数组”。以归并排序为例合并阶段需要O(n)的辅助数组递归调用栈深度为O(log n)总空间为O(n log n)约等于O(n)。如果把递归栈也算进去你不能说它只是O(log n)因为辅助数组的占用显然更大。反过来某些原地算法比如迭代堆排序才真正是O(1)空间。选择题只要看到“递归”两个字就要立刻问自己栈帧空间算进去了吗辅助空间算进去了吗4.2 哈希冲突概率和期望长度的估算哈希表的平均查找长度是校招选择题的常客。考察点集中在两个口径查找成功和查找失败。查找成功时要统计每个元素在它的哈希位置往后探测了多少次累加后除以元素个数。查找失败时要统计每个槽位如果发生查询要探测多少次才能确认不存在累加后除以槽位数。很多人混用这两个口径导致一个简单题算错。比如线性探测法中如果某个槽位被连续占用了三次查找成功时第三个元素可能只比较1次或2次但查找失败时从该槽位开始要连续探测4次才能遇到空位。选择题问“平均查找长度”时必须确认题目限定的是“成功”还是“失败”不要默认。4.3 快排局部有序时的退化陷阱快排复杂度相关的选择题十道里有七道在考退化条件。核心线索是基准值选择策略如果基准总是取第一个元素而输入数组基本有序那么每次分区都极不均匀递归层数退化到O(n)总复杂度直接变O(n²)。这个退化在基本有序和重复元素多的场景中都可能出现。重复元素多时标准分区的指针交错会变得复杂如果实现没做三路切分大量相等元素会反复参与比较。所以选项里一旦出现“基本有序”“首元素基准”“无三路切分”这些关键词就要警惕它是在诱导你选“O(n²)”。反过来随机化快排通过随机选基准把退化概率降到极低复杂度期望值仍是O(n log n)。5. 从一套选择题反推复习路线5.1 把选择题变成知识图谱做完一套选择题最忌讳的是只看总分。我复盘这套A卷时会把每道错题对应的考点写成一张检查表比如“完全二叉树叶子计算”算数据结构“Dijkstra负权边”算图论“朴素匹配复杂度”算字符串算法然后回到自己的知识笔记里找对应章节。这样做的价值在于选择题的考点密度高于编程题。编程题可能只考一个考点选择题能在十五分钟内覆盖十几个考点。你把这十几个考点挨个检查一遍比盲目刷十道编程题更能暴露短板。如果你发现连续几道题都错在“复杂度计算”那就说明你最近需要集中看排序、图算法、递归分析的复杂度推导。5.2 错题整理的正确方法和常见误区错题不是把题目抄一遍、答案写一遍就完了。我会用“错因分类”的方式整理是知识点记忆错误还是条件没看清还是计算粗心记忆错误的题要重看教材条件没看清的题要训练读题习惯计算粗心的题只能靠多做。另一个有效动作是组队复盘。找三五个同学一起过选择题你讲一道我讲一道讲的过程中就能发现哪些人只是答案对、逻辑是虚的。我在准备2020算法练习系列时经常用这种方式模拟“给新人讲题”反而把很多自己以为懂、其实不懂的知识点暴露了出来。最后说点实在的。我在复盘这套题时发现选择题的难点从来不在“知不知道答案”而在你能不能快速地用特值、反例、极端情况验证一个模糊选项。命题人的套路其实很固定你做多了会发现那些看似复杂的选项最后都能用几个边界条件拆穿。这套2020算法练习一做完把错题标记好一周之后再做一遍比再刷十道新题都有用。后面我会继续按同样的方式输出把笔试选择题的坑一个个填平。
