GESP 2026年3月C++五级真题完整解析

CCF GESP 编程能力等级考试 · 2026年3月认证

C++ 五级 · 满分100分 · 27题

获取 202603gesp5级完整真题及详细解析.pdf

请关注状元编程公众号，回复 202603gesp5

📋 考试概况

一、单选题（每题2分，共30分）

第1题

关于带头结点的循环单链表，下列说法正确的是？

A) 判空条件是头指针为空 B) 判空条件是头结点的next为空 C) 判空条件是头结点的next等于头指针 D) 判空条件是头结点的next指向自身

答案：D

在带头结点的循环单链表中，空表的特征是头结点的 next 指针指向头结点自身（即 head->next == head），而非 NULL。这是循环链表与普通链表的关键区别。

💡 知识点：循环链表。尾节点的 next 指回头结点形成环，判空时检查 head->next == head。

第2题

在双向循环链表中，在节点 p 之前插入节点 s，正确的操作序列是？

A)s->next=p; s->prev=p->prev; p->prev=s; s->prev->next=sB)s->next=p; s->prev=p->prev; p->prev->next=s; p->prev=sC)s->prev=p->prev; s->next=p; p->prev=s; s->prev->next=sD)s->prev=p; s->next=p->next; p->next->prev=s; p->next=s

答案：B

关键在于先修改新节点的指针，再修改原有节点的指针，且修改 p->prev 必须在 p->prev->next 之后。

正确顺序：

1. s->next = p — s的next指向p
2. s->prev = p->prev — s的prev指向p的前驱
3. p->prev->next = s — p的前驱的next指向s
4. p->prev = s — p的prev指向s

⚠️ 易错点：如果先执行 p->prev = s，则 p->prev->next 就变成了 s->next，导致原前驱节点的next无法正确更新。指针修改顺序是链表操作的核心难点。

第3题

使用哑结点（dummy node）删除单链表中 cur 的下一个节点 del，正确的操作是？

A)del = cur->next; cur->next = del->next; delete delB)cur->next = del->next; delete delC)del->next = cur->next; cur->next = delD)cur->next = cur->next->next

答案：A

使用哑结点删除操作的标准步骤：先保存待删除节点指针，再跳过它（cur->next = del->next），最后释放内存（delete del）。选项A包含完整的删除+释放流程。

第4题

执行 gcd(48, 18) 的辗转相除法，递归过程为？

A)gcd(48,18) -> gcd(18,16) -> gcd(16,2) -> gcd(2,0) 返回2 B)gcd(48,18) -> gcd(18,12) -> gcd(12,6) -> gcd(6,0) 返回6 C)gcd(48,18) -> gcd(30,18) -> gcd(12,18) -> gcd(6,0) 返回6 D)gcd(48,18) -> gcd(18,12) -> gcd(12,0) 返回12

答案：B

辗转相除法：gcd(a, b) = gcd(b, a % b)，当 b == 0 时返回 a。

• gcd(48, 18) → 48 % 18 = 12 → gcd(18, 12)
• gcd(18, 12) → 18 % 12 = 6 → gcd(12, 6)
• gcd(12, 6) → 12 % 6 = 0 → gcd(6, 0) → 返回 6

💡 辗转相除法（欧几里得算法）：时间复杂度 O(log(min(a,b)))，是求最大公约数的经典算法。

第5题

欧拉筛（线性筛）中，内层循环的循环变量 j 的条件是？

A)j < nB)j < sqrt(n)C)j < primes.size()D)j <= primes.size()

答案：C

欧拉筛的核心思想：每个合数只被其最小质因子筛去一次。内层循环遍历已找到的质数 primes[j]，条件为 j < primes.size()，且当 i % primes[j] == 0 时跳出，保证每个合数只被筛一次。

💡 欧拉筛 vs 埃氏筛：欧拉筛时间复杂度 O(n)，每个合数只标记一次；埃氏筛时间复杂度 O(n log log n)，可能有重复标记。

第6题

埃氏筛法中，筛 i 的倍数时从 i² 开始而非 2*i 的原因是？

A) 从 2*i 开始会越界 B) 从 i² 开始可以减少内存使用 C) 小于 i² 的 i 的倍数已被更小的质因子筛过 D) 从 i² 开始可以避免整数溢出

答案：C

对于任意合数 i * k（其中 k < i），k 必有一个质因子 p ≤ k < i，因此 i * k 已经在筛 p 的倍数时被标记过了。从 i² 开始可以避免重复标记，提高效率。

第7题

在 [1, 2, 4, 8, 9] 中选3个数，使最小距离最大化，最大最小距离为？

A) 2 B) 3 C) 4 D) 7

答案：B

二分答案+贪心验证。排序后尝试不同的最小距离 d：

• d=3：选1, 4, 8（或1, 4, 9），间距分别为3和4 ≥ 3 ✅
• d=4：选1后下一个≥5，选8后下一个≥12（超出范围）❌

最大最小距离为 3。

💡 二分答案：将"求最值"问题转化为"判定可行性"问题，对答案空间二分搜索。

第8题

lower_bound 函数中，当 a[mid] >= x 时应执行？

A)r = mid（左闭右开区间） B)l = mid + 1C)r = mid - 1D)l = mid

答案：A

lower_bound 查找第一个不小于x 的位置。当 a[mid] >= x 时，答案可能在 mid 或更左边，因此 r = mid（左闭右开区间写法，r 是开区间右端点）。

💡 lower_bound vs upper_bound：lower_bound 找第一个 >= x 的位置，upper_bound 找第一个 > x 的位置。

第9题

关于递归函数，下列说法正确的是？

A) 递归深度过大可能导致栈溢出 B) 递归函数一定比迭代效率高 C) 递归函数不会出现栈溢出 D) 栈溢出时程序会自动转换为迭代执行

答案：A

每次函数调用都会在栈上分配空间保存返回地址和局部变量。递归深度过大时，栈空间耗尽导致栈溢出（Stack Overflow），程序通常会崩溃，不能安全继续执行。

⚠️ 注意：栈溢出属于未定义行为，程序通常直接崩溃，不能依赖"安全"处理。

第10题

二分答案中，当 check(mid) 返回 true（可行）时，应如何更新边界？

A)l = mid + 1（求最大值时） B)r = mid（求最大值时） C)l = mid（求最小值时） D)r = mid - 1（求最大值时）

答案：A

二分答案求最大值时：check(mid) 为真说明 mid 可行，尝试更大的值，故 l = mid + 1。check(mid) 为假说明 mid 不可行，缩小范围 r = mid - 1。

💡 二分答案模板：求最大值 → check(true) 时 l=mid+1；求最小值 → check(true) 时 r=mid-1。

第11题

分治法求最大连续子段和，时间复杂度为？

A) O(n) B) O(n log n) C) O(n²) D) O(2ⁿ)

答案：B

分治法将数组分为两半，分别递归求解左半、右半的最大子段和，再考虑横跨中间的情况。递推式 T(n) = 2T(n/2) + O(n)，由主定理得时间复杂度 O(n log n)。

第12题

归并排序合并两个有序数组时，升序排列的条件是？

A)A[i] <= B[j] 时取 A[i]B)A[i] >= B[j] 时取 A[i]C)A[i] < B[j] 时取 A[i]D)A[i] > B[j] 时取 A[i]

答案：B

升序排列时，每次取两个数组头部中较小的元素。A[i] <= B[j] 时取 A[i]（使用 <= 保证稳定性）。

💡 归并排序：时间复杂度 O(n log n)，空间复杂度 O(n)，是稳定排序。

第13题

快速排序在什么情况下退化为 O(n²)？

A) 数组完全随机 B) 数组已升序且选第一个元素作pivot C) 数组元素全部相同 D) 数组长度为偶数

答案：B

当数组已升序且选择第一个元素作pivot时，每次分区后一侧为空，另一侧有 n-1 个元素，递归深度退化为 O(n)，总时间复杂度 O(n²)。

⚠️ 快排退化：最坏情况 O(n²)，平均 O(n log n)。可通过随机化pivot或三数取中法避免最坏情况。

第14题

关于排序算法的稳定性，正确的是？

A) 快速排序是稳定的 B) 快速排序不稳定，归并排序稳定 C) 归并排序不稳定 D) 快速排序和归并排序都稳定

答案：B

• 快速排序：分区交换可能改变相同元素的相对顺序 → 不稳定
• 归并排序：合并时使用 <= 保证相同元素相对顺序不变 → 稳定

第15题

大整数除法中，逐位计算后更新余数的操作是？

A)rem = rem * 10 + digitB)rem %= bC)rem /= bD)rem *= b

答案：B

大整数除法模拟手工除法：每一位处理时，rem = rem * 10 + digit 得到当前余数，quotient_digit = rem / b 得到商的当前位，然后 rem %= b 更新余数，为下一位计算做准备。

二、判断题（每题2分，共20分）

判断题精选解析

第3题：快速排序的不稳定性来源于分区过程中的交换操作。即使选择中间元素作为pivot，当存在相同关键字时，交换仍可能改变它们的相对顺序。稳定性是排序算法的固有属性，不因pivot选择策略而改变。

第5题：完整的归并排序需要：①分解（递归拆分）→ ②合并（有序归并）。如果代码只实现了合并部分而缺少递归分解步骤，数组并未被分解到单元素，合并结果错误。

第8题：最优子结构是贪心算法可行的必要条件（贪心选择必须基于子问题的最优解），但不是充分条件。还需要满足贪心选择性质（局部最优选择能导致全局最优）。例如：0-1背包问题有最优子结构，但贪心策略不一定最优。

第9题：欧拉筛的核心保证是每个合数只被其最小质因子筛去一次。当 i % primes[j] == 0 时，primes[j] 是 i 的最小质因子，后续 primes[k] 筛掉的 i * primes[k] 的最小质因子是 primes[j] 而非 primes[k]，故跳出循环。

第10题：尾递归是指递归调用是函数的最后一步操作。编译器可以将尾递归直接优化为等价的循环，不需要额外的栈空间。因此不一定需要显式使用栈来模拟。

三、编程题（每题25分，共50分）

3.1 有限不循环小数

题目描述： 若 1/a 可化为有限不循环小数，称 a 为终止数。求 [L,R] 中终止数数量。

核心思路： 1/a 为有限小数 ⇔ a 的质因数只含 2 和/或 5

数据范围： 1 ≤ L ≤ R ≤ 10⁶

参考程序：

#include<iostream>usingnamespace std;intmain(){int l, r, cnt = 0;    cin >> l >> r;for (int i = l; i <= r; i++) {int tmp = i;while (tmp && tmp % 2 == 0) tmp /= 2;while (tmp && tmp % 5 == 0) tmp /= 5;if (tmp == 1) cnt++;    }    cout << cnt << endl;return0;}

样例： 输入 2 11 → 输出 5（终止数：2, 4, 5, 8, 10）

💡 数学原理：1/a 为有限小数当且仅当 a 的质因数分解中只含 2 和 5。因为 10 = 2 × 5，只有 2 和 5 的幂次可以表示为有限小数。

3.2 找数

题目描述： 给定数组 A（n个）和 B（m个），求同时在 A、B 中出现的数的个数。

数据范围： n,m ≤ 10⁵, aᵢ,bᵢ ≤ 10⁹

方法一 — 排序+二分查找（O(n log n + m log n)）：

#include<iostream>#include<algorithm>usingnamespace std;constint MAX_N = 100010;intmain(){    ios::sync_with_stdio(false);    cin.tie(0);int n, m, cnt = 0, A[MAX_N], tmp;    cin >> n >> m;for (int i = 0; i < n; i++) cin >> A[i];sort(A, A + n);for (int i = 0; i < m; i++) {        cin >> tmp;int left = 0, right = n - 1;while (left <= right) {int mid = left + (right - left) / 2;if (A[mid] == tmp) { cnt++; break; }elseif (A[mid] < tmp) left = mid + 1;else right = mid - 1;        }    }    cout << cnt << endl;return0;}

方法二 — 哈希集合（O(n+m)）：

#include<iostream>#include<unordered_set>usingnamespace std;intmain(){    ios::sync_with_stdio(false);    cin.tie(nullptr);int n, m, tmp, cnt = 0;    cin >> n >> m;    unordered_set<int> setA;for (int i = 0; i < n; i++) { cin >> tmp; setA.insert(tmp); }for (int i = 0; i < m; i++) {        cin >> tmp;if (setA.find(tmp) != setA.end()) cnt++;    }    cout << cnt << endl;return0;}

样例： 输入 A=[4,2,3], B=[3,1,5,4,6] → 输出 2（3和4均出现）

💡 两种方法对比：排序+二分不需要额外空间，适合内存受限场景；哈希集合时间更优但需要 O(n) 额外空间。注意哈希集合中重复元素只算一次。

📊 答案速查表

单选题

判断题

📈 考点分布分析

💡 备考建议

1. 链表操作是五级重点：熟练掌握单链表、双向链表、循环链表的插入删除操作，特别注意指针修改顺序
2. 数论基础要扎实：辗转相除法（GCD）、埃氏筛、欧拉筛的原理和代码实现，理解筛法优化原理
3. 二分查找三种变体：精确查找、lower_bound/upper_bound、二分答案，掌握不同区间写法的边界处理
4. 分治思想：理解分治三步（分解→解决→合并），能分析递推式并用主定理求复杂度
5. 排序算法全面掌握：各排序算法的时间复杂度、空间复杂度、稳定性，以及适用场景
6. 贪心的必要条件与充分条件：最优子结构是必要条件，贪心选择性质是充分条件，两者缺一不可
7. 尾递归优化：理解尾递归可被编译器优化为循环，避免栈溢出
8. 编程题多方法思考：同一问题尝试不同解法（排序+二分 vs 哈希），根据数据范围选择最优方案

📌 GESP C++ 五级 考察的核心是数据结构（链表）和算法基础（数论、二分、分治、排序）。相比四级，五级从语法层面上升到算法思维层面，建议多做链表操作题和算法实现题，深入理解每种算法的设计思想。