🌟 第8题：代数运算——先别急着算，先看题目给了什么
试卷第 8 题是：
若 x+y = 7，x-y =1，则 x * y 的值为（ ）。
✅ D、12
🧠 这种题应该怎么做？
小朋友做代数题最容易犯的错误就是：
“看到字母就害怕！”
其实字母和数字没有本质区别。
例如：
a = 3 b = 5那么：
a + b就相当于：
3 + 5 = 8🧙 表达式计算的诀窍：
减少变量的数量
x + y = 7 x - y = 1 等式左右分别相加，依然为等式 x + y + (x - y) = 7 + 1 x + x = 8 x = 4我们已经得到 x 的值
4计算 y 的值
4 + y = 7 y = 7 - 4 y = 3计算 x * y 的值
x * y = 4 * 3 = 12我们遇到这种题，可以养成一个习惯：
第一步：把已知条件写出来
a = ? b = ?第二步：找到题目真正要求的东西
例如要求：
a+b a-b a×b a²+b²第三步：合并同类项，减少项数
不要被字母吓住。
🌳 第9题：最小生成树——Kruskal 和 Prim 谁更适合？
第 9 题问的是：
关于最小生成树（MST）算法，下列说法正确的是？
正确答案：
✅ A、
题目给出的选项是：
A. Prim 算法适用于稠密图，Kruskal 算法适用于稀疏图
B. Prim 和 Kruskal 得到的最小生成树边集一定完全相同
C. Kruskal 必须使用邻接矩阵
D. Prim 只能处理有向图。
🌲 什么叫最小生成树？
想象有几个城市：
北京 —— 上海 | | 广州 —— 深圳城市之间修公路，每条公路都有一个价格。
我们的任务：
让所有城市连通，同时修路总成本最低。
这就是：
🌳 最小生成树 MST
🏃 Kruskal：边的“选美大赛”
Kruskal 的思路特别简单：
把所有边按照权值从小到大排序。
例如：
边 价格 A-B 2 B-C 3 A-C 5 C-D 7然后：
2 → 3 → 5 → 7从小到大尝试。
如果加进去：
不会形成环
就选。
🧙 Prim：从一个城市慢慢扩张
Prim 的感觉不一样。
比如从：
A出发。
每次寻找：
连接“已经加入的城市”和“外面的城市”的最小边。
所以它像一支探险队：
已经探索区域 ↓ 寻找最近的新城市 ↓ 加入 ↓ 继续扩大⭐ 为什么 A 正确？
通常来说：
稠密图
边很多：
城市之间到处都有路Prim 往往比较适合。
稀疏图
边比较少：
只有少数道路Kruskal 往往很方便。
所以考试中可以记：
Prim：从点出发扩张。
Kruskal：把边排序后挑。
❌ B 为什么错？
Prim 和 Kruskal 得到的最小生成树边集一定完全相同。
不一定！
如果图存在多个权值相同的边：
A —— B \ / C可能有多棵同样重量的最小生成树。
所以：
最小生成树可能不唯一。
但是它们的：
总权值都是最小的。
❌ C 为什么错？
Kruskal 并不要求邻接矩阵。
它最喜欢的是：
边数组例如：
struct Edge { int u, v, w; };然后：
sort(edge, edge + m, cmp);❌ D 为什么错？
Prim 是用来求：
无向连通图的最小生成树
不是“只能处理有向图”。
事实上，最小生成树这个概念本身就是针对无向图的。
🚂 第10题：Kruskal——第几条边能够上车？
第 10 题继续考 Kruskal：
某连通带权无向简单图，使用 Kruskal 算法按照边权从小到大扫描，第几条被选入最小生成树的边是什么？
这一题真正考：
⭐ “排序 + 判断成环”
🎯 Kruskal 的固定套路
假设边已经按照权值排序：
1 2 3 4 5 6我们从第一条开始：
看！ ↓ 加进去会不会形成环？ ↓ 不会 → 加 会 → 跳过🧩 为什么会出现“跳过”？
例如：
A —— B \ / C假设：
A-B = 1 B-C = 2 A-C = 3先选：
A-B再选：
B-C此时：
A —— B | C已经连通。
再看：
A-C如果加进去：
A —— B \ | \ | C就形成环。
所以：
❌ 不选 A-C。
🧠 考试秘诀
看到：
“Kruskal 按边权从小到大扫描”
脑袋里立刻出现：
排序 ↓ 最小边 ↓ 会不会成环？ ↓ 不成环就选如果是代码题，则会出现：
sort()加上：
并查集🏃 第11题：Dijkstra 的小根堆里放什么？
这道题非常经典。
题目问：
在使用小根堆（优先队列）优化的 Dijkstra 算法中，堆中每个元素通常存储什么？
答案：
✅ A
也就是：
顶点编号 + 当前最短距离。
🗺️ 先理解 Dijkstra
假设：
A ——2—— B ——3—— C \ | 5 1 \ | —— D我们从 A 出发。
我们需要不断寻找：
目前离起点最近的那个点。
🏆 所以我们需要一个“排行榜”
例如：
距离 城市 2 B 5 D ∞ C谁距离最小？
B先处理 B。
这就是优先队列的作用。
🥇 为什么要存两个东西？
只存：
距离不行。
因为你还得知道：
这个距离属于谁？
所以需要：
(距离，顶点)例如：
(2, B) (5, D)💻 C++代码里经常写成
priority_queue< pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > q;里面放：
距离 + 顶点编号🧠 记忆点
把优先队列想成：
🏃 “跑步排行榜”
每个人都有：
姓名 成绩Dijkstra 中：
姓名 → 顶点 成绩 → 当前最短距离所以必须两个一起存。
🌎 第12题：Floyd——k 到底是谁？
本题问：
在 Floyd 算法经典三重循环：
for (k) for (i) for (j)中，最外层k表示什么？
答案：
✅ A
即：
当前允许作为中间顶点的最大编号，也就是只允许编号不超过 k 的顶点作为中间点。
🧙 这是 Floyd 最核心的思想
Floyd 是解决：
任意两点之间最短路
的经典算法。
它的代码大家比较熟悉：
for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) d[i][j] = min( d[i][j], d[i][k] + d[k][j] );🧩 k 在干什么？
假设：
k = 1我们允许：
顶点 1 当中间人。
然后：
k = 2允许：
顶点 1、2 当中间人。
然后：
k = 3允许：
顶点 1、2、3 当中间人。
所以k就像：
🚪 “中间人开放权限”
⭐ 为什么 k 必须放最外层？
因为 Floyd 的状态思想是：
d[i][j]表示：
在允许某些点作为中间点的情况下，i 到 j 的最短距离。
k一层一层扩大：
允许1 ↓ 允许1、2 ↓ 允许1、2、3 ↓ ……这正是动态规划的特点。
🚦 第13题：复杂度——谁跑得慢，谁跑得快？
本题考：
常见复杂度按照渐近增长速度从慢到快排列。
答案是：
✅ C
🐢 复杂度速度排行榜
我们可以把复杂度想象成赛车：
🥇 最快：
O(1)无论数据多大，基本不受影响。
🥈
O(log n)非常快。
典型：
二分查找 快速幂🥉
O(n)数据增加一倍，工作量大约增加一倍。
例如：
for (int i = 1; i <= n; i++)然后：
O(n log n)典型：
归并排序 快速排序平均情况再往后：
O(n²)典型：
for (...) for (...)更可怕：
O(n³)例如 Floyd。
再往后：
O(2^n)通常非常恐怖。
🌟 一定记住这条“速度长龙”
O(1) ↓ O(log n) ↓ O(n) ↓ O(n log n) ↓ O(n²) ↓ O(n³) ↓ O(2^n) ↓ O(n!)越往下面：
😱 数据一大越容易爆炸！
📦 第14题：差分数组——区间加法的魔法
对长度为
n的数组使用差分数组支持m次区间加操作，最后通过一次前缀和还原每个位置的最终值，整个过程的渐进时间复杂度是多少？
答案：
✅ D
题目本身明确描述了“差分数组 + 最后一次前缀和”。
😫 普通方法为什么慢？
假设：
1 2 3 4 5 6 7 8现在要求：
[2, 7]全部加 10。
普通方法：
2 加 3 加 4 加 5 加 6 加 7 加一次操作可能修改很多个数字。
如果有：
m次操作，就可能变得很慢。
🪄 差分数组来了！
差分数组d的思想：
不直接告诉每个人“你加10”，而是只告诉“从这里开始 +10，从这里结束”。
例如：
区间 [2,7] +10只需要：
d[2] += 10; d[8] -= 10;神奇！
🧠 为什么？
因为最后做前缀和：
d[1] d[1]+d[2] d[1]+d[2]+d[3] ...于是：
2～7之间都会自动得到：
+10到了：
8又减回来。
差分数组的核心思想：
我们不直接记录每个位置的具体值，而是记录「相邻两个位置的差值」，把原本需要遍历整个区间的修改，变成只修改两个端点的标记，最后通过一次前缀和还原出最终数组。
1. 差分数组的定义
对于原数组a（长度为n，我们以下标从1开始为例，避免越界特判），它的差分数组diff满足：
diff[1] = a[1]（第一个位置没有前驱，差值就是它本身）diff[i] = a[i] - a[i-1]（i≥2时，存当前位置和前一个位置的差）
反过来，原数组就是差分数组的前缀和：a[i] = diff[1] + diff[2] + ... + diff[i]。
举个最简单的例子：
原数组a = [1, 3, 5, 6, 7]（下标1~5），对应的差分数组计算如下：diff[1] = 1
diff[2] = 3-1 = 2
diff[3] = 5-3 = 2
diff[4] = 6-5 = 1
diff[5] = 7-6 = 1
即差分数组
diff = [1, 2, 2, 1, 1]，对diff求前缀和就能还原回原数组。
2. 区间加操作的原理：为什么只需要改两个点？
如果我们要对原数组的区间[l, r]所有元素都加v，差分数组只会发生两个变化：
在位置 l：
a[l]比a[l-1]多了v，所以diff[l] += v——这个标记的含义是「从位置l开始，后面所有元素都要加v」在位置r+1：
a[r+1]比a[r]少了v，所以diff[r+1] -= v——这个标记的含义是「从位置r+1开始，后面所有元素都减回v，抵消前面的加v效果」
区间内部的元素因为同时加了v，相邻差值完全不变，所以不需要修改diff数组的其他位置。
3. 前缀和还原最终数组
所有操作完成后，对diff数组从头开始求前缀和，就能得到修改后的原数组：
⏱️ 复杂度怎么算？
每一次区间修改：
O(1)做m次：
O(m)最后一次前缀和：
O(n)所以总复杂度：
⭐ O(n + m)
这就是本题最重要的结论。
🤖 第15题：C++对象的构造与析构
这题非常适合小学生理解，因为它像：
机器人出生和离开房间。
代码：
class A { public: A() { cout << "A"; } ~A() { cout << "~A"; } };然后有一个：
class B : public A { public: B() { cout << "B"; } ~B() { cout << "~B"; } };最后：
int main() { B b; return 0; }题目选项给出了：
A. BA~A~B B. BA~B~A C. AB~A~B D. AB~B~A正确答案：
✅ D
👶 第一步：B出生了
我们写：
B b;表面上看：
创建 B。
但是 B 是：
class B : public A也就是说：
B 是 A 的“孩子”。
🧬 C++规定
创建派生类对象时：
先构造父类，再构造子类。
所以：
A构造 ↓ B构造输出：
AB💥 那么销毁呢？
这时候顺序反过来：
先销毁子类，再销毁父类。
所以：
B析构 ↓ A析构输出：
~B~A🎯 合起来
创建：
AB销毁：
~B~A最终：
AB~B~A所以：
🏆 答案 D
🧠 这个知识一定要记住
我们可以想象：
出生：
爸爸先出生 ↓ 孩子再出生回家：
孩子先回家 ↓ 爸爸后回家所以：
⭐ 构造：父 → 子
⭐ 析构：子 → 父
🎯 第8～15题知识地图
| 题号 | 考点 | 一句话记忆 |
|---|---|---|
| 8 | 代数计算 | 先看已知，再代入计算，合并同类项 |
| 9 | MST | Prim扩点，Kruskal挑边 |
| 10 | Kruskal | 边权排序，遇环跳过 |
| 11 | Dijkstra + 堆 | 距离 + 顶点 |
| 12 | Floyd | k是允许的中间点 |
| 13 | 时间复杂度 | 从 O(1) 到 O(n!) 越来越慢 |
| 14 | 差分数组 | 区间修改 O(1)，最后前缀和 |
| 15 | 构造/析构 | 父先子后，析构反过来 |
🏆 “闯关地图”
到这里，选择题1～15题其实已经串成了一张知识地图：
C++八级选择题 │ ┌───────────────┼───────────────┐ ↓ ↓ ↓ 数学 图论 C++ │ │ │ ┌────┼────┐ ┌───┼────┐ ┌──┼───┐ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 排列 杨辉 建模 MST Dijkstra Floyd 析构 复杂度 组合 三角 Kruskal 最短路 构造 差分其中最值得同学们反复掌握的8个“看到题目就要条件反射”的关键词是：
🔴Kruskal → 排序 + 不成环
🟠Prim → 从一个点不断扩张
🟡Dijkstra → 小根堆里放距离 + 点
🟢Floyd → k是中间点
🔵差分 → 区间修改 O(1)
🟣前缀和 → 最后还原
🟤构造 → 父类先、子类后
⚫析构 → 子类先、父类后
