GESP2025年6月认证C++五级( 第二部分判断题（1-10））
🎯 第1题：gcd万能吗？
1、🌈故事
数学骑士拿出一个函数：
👉 不管 a > b 还是 a < b，都能算最大公约数！
2、🧠判断步骤
① 核心代码：
while (b) { int temp = b; b = a % b; a = temp; }② 如果 a < b 会怎样？
👉 第一轮就会自动交换！
3、✅结论
✔️ 正确
4、📌小口诀
👉 辗转相除法，自带交换功能
🎯 第2题：最小公倍数公式
1、🌈故事
数学精灵说：
👉 lcm(a, b) = a × b ÷ gcd(a, b)
2、🧠判断步骤
① gcd 是最大公约数
② 公式是标准数学结论：
3、⚠️注意
👉 只要 gcd 正确，这个公式就成立
4、✅结论
✔️ 正确
5、📌小口诀
👉 最小公倍数 = 乘积 ÷ 最大公约数
🎯 第3题：质因数分解代码
1、🌈故事
程序员想输出：
👉 6 → [2, 3]
👉 8 → [2, 2, 2]
2、🧠检查代码
关键错误：
prime_factor[i] = prime_factor[i] + j;❌ vector 不能这样加！
3、🧠正确写法应该是：
prime_factor[i].push_back(j);4、❌结论
❌ 错误
5、📌小口诀
👉 vector 加元素要用 push_back
🎯 第4题：归并排序只执行一次？
1、🌈故事
程序里打印：
👉 "HERE"
有人说：
👉 只会打印一次！
2、🧠分析
归并排序：
👉 会不断拆分 + 合并
每一次合并都会调用 merge！
3、❌结论
❌ 错误
👉 会打印很多次！
4、📌小口诀
👉 分治算法 → 会多次合并
🎯 第5题：归并排序复杂度
1、🌈故事
归并排序被称为“稳定的排序大师”
2、🧠分析
👉 不管情况如何：
最好：O(n log n)
最坏：O(n log n)
平均：O(n log n)
3、✅结论
✔️ 正确
4、📌小口诀
👉 归并排序稳如泰山：O(n log n)
🎯 第6题：查字典 = 二分查找？
1、🌈故事
查字典：
👉 一次翻一半！
2、🧠分析
① 看中间
② 判断往前还是往后
③ 继续缩小范围
👉 完全就是二分查找！
3、✅结论
✔️ 正确
4、📌小口诀
👉 每次砍一半 = 二分查找
🎯 第7题：Dijkstra是贪心？
1、🌈故事
最短路径大师：
👉 每次选“当前最近的点”
2、🧠分析
👉 每一步都选最优（最近）
👉 典型贪心思想！
3、✅结论
✔️ 正确
4、📌小口诀
👉 每次选最近 = 贪心
🎯 第8题：分治一定更慢？
1、🌈故事
有人说：
👉 分治要拆开再合并，所以更慢！
2、🧠分析
❌ 不一定！
👉 很多算法更快，比如：
快速排序
归并排序
3、❌结论
❌ 错误
4、📌小口诀
👉 分治不仅不慢，还很聪明
🎯 第9题：递归会无限循环？
1、🌈故事
函数：
if (n == 1) return 1; if (n % 2 == 0) return puzzle(n / 2); return puzzle(3 * n + 1);2、🧠分析
这是“3n+1问题”（猜想）
👉 有些数会变来变去！
但题目问：
👉一定无限递归吗？
3、❌结论
❌ 错误
👉 不一定无限（当3n+1= 2 ^ n, 数会回到1）
4、📌小口诀
👉 看起来危险，但不一定死循环
🎯 第10题：线性筛复杂度
1、🌈故事
筛法高手登场：
👉 每个合数只被筛一次！
2、🧠分析
👉 时间复杂度：
👉O(n)
3、✅结论
✔️ 正确
4、📌小口诀
👉 每个数只筛一次 = 线性
🌟 知识点总结：
1️⃣ gcd 自带交换
2️⃣ lcm = ab / gcd
3️⃣ vector 用 push_back
4️⃣ merge 会执行多次
5️⃣ 归并排序永远 n log n
6️⃣ 查字典就是二分
7️⃣ Dijkstra 是贪心
8️⃣ 分治不一定慢
9️⃣ 递归不一定死循环
🔟 线性筛是 O(n)