第二部分 判断题110题 第1题排列组合从4本不同的书中选出3本分别分给甲、乙、丙3人每人至多1本共有 P(4,3)24 种不同分法。答案✅ 对这道题的关键词是选出来以后还要“分别分给”甲、乙、丙。所以这不是单纯的“选3本”而是先选再安排。 举个例子4本书A B C D甲、乙、丙每人拿一本。假设甲拿A乙拿B丙拿C是一种。但是甲拿B乙拿A丙拿C又是另一种。所以顺序非常重要。这就是排列。计算第1个人有4种选择4第2个人剩下3本3第3个人剩下2本2所以4×3×224也就是P(4,3) 24 记忆“选出来还要分给不同的人” → 顺序重要 → 排列所以✅ 第1题正确 第2题二项式展开对任意正整数 n二项式 (ab)^n 的展开式中按项序从第0项起计数奇数项系数之和等于偶数项系数之和。答案✅ 对这道题稍微难一点我们用一个“魔法开关”来理解。 二项式展开是什么例如(ab)^2展开a^2 2ab b^2系数分别是1 2 1注意题目说从第0项开始编号。所以项编号系数a^2012ab12b^221奇数项第1项系数和2偶数项第0、2项系数和112果然相等 为什么永远相等我们来玩两个“开关”。开关1令 a1,b1那么(11) ^ n 2^n得到的是所有系数加起来开关2令 a1,b−1那么(1-1)^n0这相当于偶数项系数之和 - 奇数项系数之和 0所以偶数项系数和 奇数项系数和 小口诀1、1看总和1、-1看差值。所以✅ 第2题正确 第3题最小生成树若一个连通无向图的最小生成树中存在权值相同的边则最小生成树一定不唯一。答案❌ 错这里最大的陷阱是“权值相同” ≠ “一定有多个最小生成树”。 看一个非常简单的例子有三个点A ——1—— B \ / 2 2 \ / C假设AB 1AC 2BC 2这里有两条边AC 2 BC 2它们权值相同但是最小生成树必须选择AB再从 AC、BC 中选择一条。所以有两种最小生成树。这只是说明有时候会不唯一。但是我们要证明题目中的“一定不唯一”那就必须找一个反例。 反例三个点A —— 1—— B | / | 2 1 / | / C假设AB 1AC 1BC 2这里最小生成树就是AB AC而且是唯一的。虽然最小生成树中存在两条权值相同的边AB AC 1但是最小生成树仍然只有这一棵。所以存在相同权值的边不代表最小生成树一定不唯一。 判断题大坑看到一定、必然、所有、任何一定要警觉这些词往往是出题老师藏小陷阱的地方。❌ 第3题错误 第4题Dijkstra算法复杂度使用邻接表存储图时Dijkstra算法的朴素实现不使用堆优化的时间复杂度为 O(V^2)其中 V 为结点数。答案✅ 对这道题考Dijkstra 邻接表 朴素实现 Dijkstra每轮干什么想象我们正在寻找“最短路冠军”。每一轮要做两件事情① 找一个距离最小的未确定点如果不用优先队列就只能1号 2号 3号 4号 ……一个一个检查。一次找最小值可能要O(V)而这样的操作最多进行 VV 次O(V)×O(V) O(V^2)② 松弛它连接的边使用邻接表可以高效访问它的邻居。但整体复杂度仍然被前面的O(V^2)控制。所以朴素Dijkstra 记忆Dijkstra不用堆找最小值靠扫描 → O(V^2)✅ 第4题正确 第5题堆排序堆排序是一种稳定的排序算法。答案❌ 错这里考的是什么叫稳定排序 什么是“稳定”假设有两个小朋友小明90分 小红90分他们分数一样。原来小明 → 小红如果排序之后还是小明 → 小红我们就说排序是稳定的。如果可能变成小红 → 小明就是不稳定。 常见稳定排序例如冒泡排序插入排序归并排序而堆排序不是稳定排序。因为在调整堆的过程中相同元素的相对顺序可能发生变化。所以❌ 第5题错误 第6题质因数分解每个大于1的整数都可以唯一地分解为若干个质因数的乘积不考虑因子顺序。答案✅ 对这是数学里的经典结论⭐ 算术基本定理例如122×2×3也可以写成122^2 × 3再比如602×2×3×5也就是602^2×3×5虽然我们可以交换顺序2×3×2×5但如果说不考虑因子顺序那么本质上的质因数分解是唯一的。 记忆大于1的整数都能拆成质数乘法而且拆法唯一。✅ 第6题正确 第7题循环队列循环队列通过牺牲一个存储单元可以区分队空和队满两种状态。答案✅ 对这道题和我们之前学习的队列直接相关。 为什么会有麻烦假设有一个长度为5的数组[ ][ ][ ][ ][ ]循环队列里front表示队头rear表示队尾但是有一个问题当front rear到底是什么意思可能是队伍是空的。也可能是队伍已经绕了一圈满了这就产生了“撞车”。 怎么解决最常见的方法故意浪费一个位置。比如数组有5个位置实际上最多只放4个元素。于是front rear专门表示队空而(rear 1) % MAXN front表示队满这样就不会混淆了。 超好记循环队列想分清“空”和“满”就故意浪费一个格子。✅ 第7题正确 第8题C私有继承在C语言的私有继承中基类的 public 成员在派生类中仍为 public 成员。答案❌ 错这是一道非常典型的C继承题。关键看private继承 正常继承假设class Animal { public: void eat(); }; class Dog : public Animal { };这是public继承基类的public成员在派生类中仍然是public 但是题目说的是 private继承class Dog : private Animal { };这时候基类的 public 和 protected 成员在派生类中都会变成 private。所以Animal::public ↓ Dog::private不是 public因此题目说“仍为public”是错误的。 小口诀public继承public还是public。private继承public降成private。❌ 第8题错误 第9题滚动数组使用滚动数组优化动态规划时通常只能降低空间复杂度不能降低时间复杂度。答案✅ 对这是非常重要的DP优化思想。 为什么叫“滚动数组”例如dp[i][j]如果我们发现当前这一行只需要上一行的数据。那么为什么要保存所有行比如原来第1行 第2行 第3行 第4行 第5行 ……其实只需要上一行 当前行于是第1行 → 第2行 ↓ 覆盖 第2行 → 第3行 ↓ 覆盖就像一个小滚轮不断向前滚。 它改变了什么原来可能需要O(nm)的空间。滚动数组以后可能只需要O(m)空间。但是每一个状态通常还是要计算。所以时间复杂度一般还是O(nm) 一句话滚动数组主要是“省空间”不是“省计算”。所以✅ 第9题正确 第10题三角形面积一个三角形的三条边分别为5、12、13则它的面积为30。答案✅ 对看到5, 12, 13小朋友应该马上想到一个非常著名的组合⭐ 5-12-13直角三角形因为5^212^2 25144 169而13^2169所以5^212^2 13^2根据勾股定理5和12是直角边13是斜边。所以面积S 12×5 / 2 30因此✅ 第10题正确 考点汇总题号判断核心知识1✅排列 P(4,3)P(4,3)2✅二项式、奇偶项系数3❌最小生成树不唯一4✅Dijkstra O(V2)O(V^2)5❌堆排序不稳定6✅质因数唯一分解7✅循环队列8❌private继承9✅滚动数组10✅勾股定理、三角形面积 “八级判断题防粗心卡”这10题其实集中考了几个非常重要的思维习惯① 遇到“一定”“必然”马上警觉有没有反例第3题就是典型陷阱。② 遇到算法复杂度先问到底有没有堆有没有优化第4题 Dijkstra 不用堆就是 O(V2)O(V^2)。③ 遇到C语法不要凭“感觉”继承方式会不会改变成员访问权限第8题就是如此。④ 遇到算法性质要记住堆排序 ≠ 稳定排序。⑤ 遇到DP优化要分清优化空间 ≠ 优化时间。滚动数组主要解决的是“内存太大”的问题。 最重要的一句话判断题不是“看起来对不对”而是“能不能找到严格的理由证明它对”。这正是判断题最喜欢考的能力。