GESP2025年6月认证C++五级( 第一部分选择题（9-15））
🎯 第9题：找最大值的“分身术”
1、🌈故事
数字王国举行比赛：谁是最大数？
魔法师用了一个技能：
👉 把队伍一分为二
👉 左边找最大、右边找最大
👉 最后再比一次！
2、🧠步骤分析
① 分成两半（拆问题）
② 各自解决（递归）
③ 合并答案（取较大）
👉 这就是：分治算法
3、⚠️易错点
❌ 不是贪心
👉 贪心是“一步一步选最优”，这里是“分开解决再合并”
4、✅结论
🎉答案：C
📌小口诀
👉 一分为二再合并 = 分治
🎯 第10题：另一种找最大值的方法
1、🌈故事
这次不用魔法了，用最朴素的方法：
👉 从头到尾，一个一个比较！
2、🧠步骤分析
① 设第一个数为最大值
② 依次遍历
③ 遇到更大的就更新
👉 这是：普通遍历（循环）
3、⚠️关注点
❌没有递归
4、✅结论
🎉答案：D
这道题是争议题：
👉 其实，这两个方法时间复杂度一样，都是O(n)
但是：
| 项目 | 分治法 | 遍历法 |
|---|---|---|
| 写法 | 复杂 | 简单 |
| 速度 | 稍慢（有递归开销） | 更快 |
| 空间 | O(log n) | O(1) |
5、📌小口诀
👉 一个一个比 = 遍历
🎯 第11题：二分查找（找最后一个）
1、🌈故事
你在书里找某个单词📖
👉 不是找“有没有”
👉 是找“最后一次出现的位置”
2、🧠步骤分析
① 每次取中间
② 如果还满足条件 → 往右找
③ 否则 → 往左找
关键代码：
👉mid = (low + high + 1) / 2
3、🎯这段代码的“配套规则”是：
| 条件 | mid写法 | 更新方式 |
|---|---|---|
| low < high | (low + high + 1)/2 | if(lst[mid]<=target) { low=mid; }else{ high=mid-1; |
👉 这一整套是“找右边界”的标准写法
4、⚠️易错点
❌B.当target小于lst中所有元素时，该函数会返回 0❌
return -1;❌C.循环条件改为while (low <= high)程序执行效果相同，且能提高准确性
原本规则是： 👉 当只剩一个位置（low == high）就停 但如果改成： 👉 low <= high 那就变成： 👉 只剩一个位置也继续找！ ⚠️ 这就容易出问题！❌D.将代码中(low + high + 1) / 2修改为(low + high) / 2效果相同
👉 可能会：
卡住
死循环
5、✅结论
🎉答案：A
6、📌小口诀
👉 二分查找，找最后一个→ mid一定要偏右！
🎯 第12题：二分求平方根
1、🌈故事
数学精灵要算：
👉 √n（平方根）
但可能是小数！
2、🧠步骤分析
👉 分两步：
① 找整数部分
② 用二分逼近小数
停止条件：
👉high - low < epsilon
3、⚠️易错点
❌ 题目中说：“浮点数不能这样比较”
👉 实际上：
✔️ 这是标准写法！
4、✅结论
🎉答案：D
5、📌小口诀
👉 浮点二分靠误差
🎯 第13题：找零钱问题
1、🌈故事
你买东西要找钱 💰
规则：
👉 每次优先用最大面额
2、🧠步骤分析
例如：
要找 18
硬币：10，5，1
👉 先用10
👉 再用5
👉 再用1
👉 每一步都选“当前最优”
3、⚠️易错点
❌ 不是分治
❌ 不是枚举
👉 是：贪心！
4、✅结论
🎉答案：A
5、📌小口诀
👉 能用大的先用大的
🎯 第14题：快速排序的秘密
1、🌈故事
排序大师用“快速排序”：
👉 选一个数当“分界线”（pivot）
👉 小的放左边，大的放右边
2、🧠步骤分析
① 随机选 pivot
② 分区
③ 递归排序左右
3、⚠️易错点
❌ “快速排序是稳定的”
👉 实际上：
🚨 快排是不稳定排序
4、✅结论
🎉答案：D
5、📌小口诀
👉 快排很快，但不稳定
🎯 第15题：高精度除法（竖式计算）
1、🌈故事
普通数字太小了！
👉 现在用“超级大整数”做除法
就像手算除法一样👇
2、🧠步骤分析
关键动作：
👉 “往下带一位”
步骤：
① 当前余数左移
② 加入新的一位
③ 再去减
对应代码：
r.d[0] = a.d[i]; r.len++;3、⚠️易错点
❌ 不能乱放位置
❌ 不能覆盖错误下标
4、✅结论
🎉答案：A
5、📌小口诀
👉 除法核心：一位一位往下带
🌟 知识点总结：
👉 7个关键知识：
1️⃣ 分治：拆开再合并
2️⃣ 遍历：一个一个比
3️⃣ 二分：找最后一个要偏右
4️⃣ 浮点二分：靠误差停止
5️⃣ 贪心：每步选最优
6️⃣ 快排：不稳定
7️⃣ 高精度：模拟竖式