GESP2026年9月认证C++五级( 第一部分选择题（8~15题）精讲

第8题：递归函数f(4)到底是多少？

题目：

int f(int n) { if (n == 1) return 1; return n + f(n - 1); }

问：

f(4)

是多少？

答案：D：10。

① 先别害怕“递归”

很多同学看到：

f(n)

又出现：

f(n - 1)

会觉得：

“函数怎么又调用自己了？不会无限循环吗？”

其实不会。

因为这里有一个非常重要的“刹车”：

if (n == 1) return 1;

这就是：

🛑递归的终点，也叫递归出口。

② 我们把f(4)拆开

程序：

return n + f(n - 1);

所以：

f(4) = 4 + f(3)

继续：

f(3) = 3 + f(2)

继续：

f(2) = 2 + f(1)

到了：

f(1) = 1

因为触发：

if (n == 1) return 1;

③ 从最里面往外算

现在开始“返回”：

f(1) = 1 f(2) = 2 + 1 = 3 f(3) = 3 + 3 = 6 f(4) = 4 + 6 = 10

所以：

答案 = 10

🌟 把它想成爬楼梯

f(4)就像问：

“从第4层往下走，每一层把自己的数字加起来，最后走到1层。”

4 ↓ 3 ↓ 2 ↓ 1

最后：

4 + 3 + 2 + 1 = 10

🧠 记忆口诀

递归题：先找到出口，再一层一层拆，最后倒着算回来。

第9题：二分查找“第一个大于 x”的位置

这道题非常重要。

题目：

int upperBound(const vector &a, int x) { int l = 0, r = (int)a.size(); while (l < r) { int mid = l + (r - l) / 2; if (__________________) { l = mid + 1; } else { r = mid; } } return l; }

题目要求：

在升序数组中，找第一个严格大于x的元素位置。

答案：C：

a[mid] <= x

① 什么叫“第一个严格大于”？

比如：

数组： 1 3 3 5 7 9

如果：

x = 3

我们寻找：

第一个大于3的数。

答案是：

5

它的位置：

0 1 2 3 4 5 ↑

所以答案位置是：

3

② 为什么判断a[mid] <= x？

想象我们站在mid这个位置。

情况一：

如果：

a[mid] <= x

例如：

a[mid] = 3 x = 3

我们要找的是：

严格大于 3

所以3肯定不行。

怎么办？

往右找！

于是：

l = mid + 1;

情况二：

如果：

a[mid] > x

例如：

a[mid] = 7 x = 3

7 已经符合要求。

但是：

会不会左边还有一个更小的位置，也同样大于3？

当然可能！

所以不能直接结束。

应该：

往左缩小范围

于是：

r = mid;

③ 所以整个逻辑就是

a[mid] <= x ↓ 不够大 ↓ 往右

而：

a[mid] > x ↓ 符合要求 ↓ 左边继续找

所以：

if (a[mid] <= x) l = mid + 1; else r = mid;

答案：

C

⭐ 一个非常重要的二分口诀

如果题目问：

第一个大于 x

就记：

a[mid] <= x

因为：

小于等于 x 的都不要，继续向右。

第10题：二分答案——猜一个“最小载重”

这一题非常有意思。

题目背景：

有很多箱货物，要按原来的顺序分成days天运输，每天运输连续的一段货物。要求找到能够完成任务的最小载重量。

程序已经有：

check(cap)

它可以告诉我们：

“如果卡车载重是cap，能不能在规定天数内完成？”

题目问二分部分怎么填写。

答案：B。

① 这道题真正的秘密

我们不是直接找答案。

而是在：

猜答案！

例如：

最小可能载重 = 10 最大可能载重 = 100

我们猜：

mid = 55

然后问：

check(55)

② 如果 55 可以完成

说明：

55够用

但是问题是：

55 是最小的吗？

不知道！

所以应该：

继续尝试更小

也就是：

r = mid;

③ 如果 55 不够

说明：

55太小

那就必须提高载重量：

往右寻找

所以：

l = mid + 1;

④ 所以答案是

if (check(mid)) { r = mid; } else { l = mid + 1; }

也就是：

check(mid) 成功 ↓ mid 可以 ↓ 答案可能更小 ↓ 往左 check(mid) 失败 ↓ mid 太小 ↓ 往右

🧠 这就是“二分答案”

普通二分：

在数组里找数字。

二分答案：

在答案范围里猜答案。

这是非常重要的算法思想。

记忆口诀：

能做成 → 尝试更小。 做不成 → 必须更大。

第11题：归并排序为什么选择<=？

题目是归并排序的合并过程：

while (i <= mid && j <= right) { if (__________________) { temp.push_back(a[i++]); } else { temp.push_back(a[j++]); } }

题目要求：

如果希望排序保持稳定，应该怎样填写？

答案：

D：

a[i] <= a[j]

原题代码及选项见试卷。

① 什么叫“稳定排序”？

这是这道题最重要的概念。

假设有两个学生：

小明：分数90 小红：分数90

他们原来的顺序：

小明 → 小红

如果排序以后：

小明 → 小红

顺序没有变化。

这叫：

稳定。

② 归并排序正在干什么？

假设左右两边已经排好：

左边： 90(小明) 右边： 90(小红)

现在两个 90 一模一样。

程序：

if (a[i] <= a[j])

因为：

90 <= 90

成立。

于是选择：

左边的小明

再选择：

右边的小红

最终：

小明 → 小红

原来的顺序被保留。

③ 如果写成<呢？

如果：

if (a[i] < a[j])

当：

90 < 90

是：

false

程序就会选择右边：

小红

可能变成：

小红 → 小明

原来的顺序被改变。

所以为了保证稳定性：

a[i] <= a[j]

⭐ 小学生记忆法

归并排序遇到：

左边 = 右边

怎么办？

公平一点，先让左边的人过。

所以：

a[i] <= a[j]

答案：

D

第12题：快速排序的 partition

题目：

int partition(int a[], int left, int right) { int pivot = a[right]; int i = left - 1; for (int j = left; j < right; j++) { if (__________________) { i++; swap(a[i], a[j]); } } swap(a[i + 1], a[right]); return i + 1; }

题目说：

以a[right]为枢轴，并把不大于枢轴的元素移动到左侧。

答案：

A：

a[j] <= pivot

原题代码见试卷。

① pivot 是什么？

pivot可以理解成：

🏰守门员

比如：

5 2 8 3 7

假设：

pivot = 7

我们希望：

≤7的

站到左边。

而：

>7的

留在右边。

最终大概形成：

≤7 | 7 | >7

② 代码正在扫描谁？

for (int j = left; j < right; j++)

也就是：

j ↓ 一个一个检查

如果发现：

a[j] <= pivot

说明：

“这个小朋友应该站到左边。”

于是：

i++; swap(a[i], a[j]);

③ 为什么不是a[j] > pivot？

题目明确说：

不大于 pivot 的放左边。

“不大于”数学语言就是：

≤

所以：

a[j] <= pivot

答案：

A

第13题：活动安排的经典贪心

题目：

一个教室要安排尽可能多场活动，每场活动有开始时间start和结束时间end。

采用贪心算法时，正确策略是：

A. 每次选择开始时间最早

B. 每次选择持续时间最短

C. 每次选择参与人数最少

D.按结束时间从早到晚排序，依次选择与已选活动不冲突的活动

答案：

D。

① 为什么不是“开始得最早”？

比如：

活动A：1 ───────── 10 活动B：2 ─ 3 活动C：4 ─ 5 活动D：6 ─ 7

如果选择：

开始最早的 A

整个教室：

1 ───────── 10

后面的 B、C、D 全没了。

只能安排：

1场

② 如果选择结束最早的呢？

先看：

B：2 ─ 3

结束时间最早。

选 B。

接下来：

C：4 ─ 5

不冲突，继续选。

然后：

D：6 ─ 7

继续选。

最终：

B → C → D

安排了：

3场

③ 为什么“结束得早”这么聪明？

因为：

越早结束，就越早把教室空出来。

后面留下的时间越多。

所以：

结束早 ↓ 给后面的活动留下更多空间 ↓ 最终活动数量可能最多

这就是经典的：

区间调度问题的贪心策略。

⭐ 贪心口诀

遇到：

“一间教室最多安排多少个互不冲突的活动？”

立刻想到：

按结束时间从小到大排序

然后：

能选就选

答案：

D

第14题：最大连续子段和

题目给数组：

{-2, 3, -1, 5, -6, 2}

函数：

int maxSubArray(const vector &a) { int best = a[0]; int current = a[0]; for (int i = 1; i < (int)a.size(); i++) { current = max(a[i], current + a[i]); best = max(best, current); } return best; }

问返回多少？

答案：

C：7

① 什么叫“连续子段”？

比如：

-2 3 -1 5 -6 2

可以选择：

3

也可以：

3 -1

还可以：

3 -1 5

但是不能：

3 5

因为中间的-1被跳过了。

所以必须：

连续！

② 我们从左往右走

核心代码：

current = max(a[i], current + a[i]);

这句话是什么意思？

到了一个新数字：

我要不要把它接在以前的队伍后面？

有两个选择：

选择1：重新开始

a[i]

选择2：接着以前的队伍

current + a[i]

哪个大，就选哪个。

③ 一步一步算

数组：

-2 3 -1 5 -6 2

初始：

current = -2 best = -2

来到 3

比较：

3

和：

-2 + 3 = 1

选择：

3

所以：

current = 3 best = 3

来到 -1

比较：

-1

和：

3 + (-1) = 2

选择：

2

于是：

current = 2 best = 3

来到 5

比较：

5

和：

2 + 5 = 7

选择：

7

于是：

current = 7 best = 7

按照题目给出的代码，{-2,3,-1,5,-6,2}的最大连续子段和是7。

因为：

3 + (-1) + 5 = 7

继续验证后面也一样：

-6： 7 + (-6) = 1

所以：

current = 1 best = 7

最后：

2： 1 + 2 = 3

最终：

best = 7

✅ 第14题答案：C，7

第15题：高精度加法中的进位

最后一道选择题非常经典。

题目给两个高精度整数：

a b

而且采用：

低位在前

也就是：

a[0] = 个位 a[1] = 十位 a[2] = 百位

代码：

vector add(const vector &a, const vector &b) { vector c; int carry = 0; int n = max(a.size(), b.size()); for (int i = 0; i < n; i++) { int sum = carry; if (i < a.size()) sum += a[i]; if (i < b.size()) sum += b[i]; c.push_back(sum % 10); ____________________ } if (carry) c.push_back(carry); return c; }

选项：

A. carry = sum % 10; B. carry = sum; C. carry = sum / 10; D. carry = c[i] / 10;

答案：

C：

① 为什么需要高精度？

C++ 的：

int long long

都有范围限制。

如果数字特别特别大：

123456789012345678901234567890

普通整数装不下。

怎么办？

我们自己用数组保存。

② 为什么“低位在前”？

例如：

1234

存成：

a[0] = 4 a[1] = 3 a[2] = 2 a[3] = 1

这样做有一个巨大好处：

加法正好从个位开始。

这就和我们小学数学竖式加法完全一样。

③ 看一个简单例子

例如：

58 +67

个位：

8 + 7 = 15

个位写：

5

同时产生：

进位 1

所以：

sum = 15

那么：

sum % 10

得到：

5

这就是当前这一位。

而：

sum / 10

得到：

1

这就是：

下一位要加的进位。

所以：

carry = sum / 10;

④%10和/10一定要分清

这是本题最核心的知识。

假设：

sum = 18

那么：

sum % 10

得到：

8

它负责：

留下当前这一位。

而：

sum / 10

得到：

1

它负责：

把进位送给下一位。

所以：

18 ↙ ↘ %10 /10 ↓ ↓ 8 1 当前位 进位

🌟 8～15题最终总结

🧠 “考场藏宝图”：

如果考试中看到这些关键词，可以快速联想到算法：

“递归” ↓ 先找出口 “第一个大于” ↓ upper_bound ↓ a[mid] <= x “最小载重量” ↓ 二分答案 “保持稳定” ↓ 相等时左边优先 ↓ <= “pivot / partition” ↓ 快速排序 “最多安排活动” ↓ 结束时间最早 ↓ 贪心 “最大连续子段和” ↓ current / best “高精度加法” ↓ 个位开始 ↓ %10 当前位 /10 进位

尤其要把最后这一组口诀记住：

二分：能行就往左，不行就往右。

贪心：活动安排看结束时间。

最大子段和：要么重新开始，要么接着前面。

高精度：%10留自己，/10往前进。