GESP第13次认证真题解析|C++五级真题回顾

CCF编程能力等级认证，英文名Grade Examination of Software Programming（以下简称GESP），由中国计算机学会发起并主办，是为计算机和编程学习者提供学业能力验证的平台。GESP旨在提升青少年计算机编程能力，培训机构编编程教育水平，推广和普及计算机和编程教育。

GESP考察语言为图形化编程、Python编程及C++编程，主要考察学生掌握相关编程知识和操作能力，熟悉编程各项基础知识和理论框架，通过设定不同等级的考试目标，让学生具备编程从简单的程序到复杂程序设计的编程能力，为后期专业化编程学习打下良好基础。

本次为大家带来的是2026年3月C++五级认证真题解析。

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

第1题 关于单链表、双链表和循环链表，下列说法正确的是（ ）。

A.在单链表中，若已知任意结点的指针，则可以在O(1)时间内删除该结点。

B.循环链表中一定不存在空指针。

C.在循环双链表中，尾结点的next指针一定为nullptr。

D.在带头结点的循环单链表中，判定链表是否为空只需判断头结点的next是否指向自身。

【答案】D

【考纲知识点】单链表、双链表、循环链表

【解析】A选项：单链表中若已知任意结点的指针，要删除该结点通常需要知道其前驱结点，找前驱需要从头遍历，时间复杂度为O(n)，错误。B选项：如果是不带头结点的循环单链表且为空表，其头指针即为空指针，错误。C选项：循环双链表的尾结点的next指向头结点，而不是nullptr，错误。D选项：带头结点的循环单链表中，当为空链表时，头结点的next恰好指向自己，判断正确。

第2题 双向循环链表中要在结点 p之前插入新结点s（均非空），以下指针操作正确的是（ ）。

A.  

B.  

C.  

D.  

【答案】C

【考纲知识点】单链表、双链表、循环链表

【解析】在双向链表中结点p之前插入结点s，需要修改四个指针的方向且不能丢失原有的前驱结点引用。首先处理新结点s的两端：s->next = p; 以及s->prev = p->prev;。接着修改原链表中的指针，必须先修改p的原前驱结点的后继：p->prev->next = s;，最后修改p的前驱指向新结点：p->prev = s;。只有C选项符合此逻辑过程。

第3题 下面函数用“哑结点”统一处理删除单向链表中的头结点与中间结点。横线处应填（ ）。

A.  

B.  

C.  

D.  

【答案】B

【考纲知识点】单链表、双链表、循环链表

【解析】代码中通过建立哨兵结点dummy，并用指针cur遍历链表。当满足条件cur->next->val == x 时，表示cur的下一个结点del即为需要被删除的结点。在单链表中删除del，应当将cur结点的next指针越过被删除的结点，直接指向del->next。因此横线处应填入cur->next = del->next;，选项B正确。

第4题 对如下代码实现的欧几里得算法（辗转相除法），执行gcd(48, 18) 得到的调用序列为（ ）。

A.  

B.  

C.  

D.  

【答案】A

【考纲知识点】辗转相除法（欧几里得算法）

【解析】根据所给的递归代码逻辑，若b != 0，则递归调用gcd(b, a % b)。对于初始调用gcd(48, 18)，因为18非0，会执行48 % 18 = 12，接着进入gcd(18, 12)；同理下一步为18 % 12 = 6，进入gcd(12, 6)；接着12 % 6 = 0，进入gcd(6, 0)。当参数b变为0时，达到递归终点并返回6。所以完整过程如A选项所示。

第5题 下面代码实现了欧拉（线性）筛，横线处应填写（ ）。

A.  j <= n

B.  j < sqrt(n)

C.  j < primes.size()

D.  j < i

【答案】C

【考纲知识点】素数表的埃氏筛法和线性筛法

【解析】线性筛的核心原理是利用每个合数最小的质因子将其筛除。算法中内层循环用于遍历目前已经被发现并收集到primes数组中的质数。数组下标j从0开始，为了防止越界，j必须小于质数数组当前的元素个数，即j < primes.size()。该条件保证了程序可以安全地访问primes[j]。所以选C。

第6题 埃氏筛中将内层循环从 j = i*i 开始而不是j = 2*i 的主要原因是（ ）。

A.因为2*i一定不是合数

B. i*i 一定是质数

C.小于i*i的i的倍数已被更小质因子筛过

D.这样可以把时间复杂度降为O(n)

【答案】C

【考纲知识点】素数表的埃氏筛法和线性筛法

【解析】在埃氏筛法中，当我们遇到一个素数i时，需要将i的所有倍数标记为合数。对于形如k * i（其中k<i）的倍数，因为k小于i，那么这个数必然存在一个更小的素数因子（k的素因子）。在算法之前的遍历过程中，这个数肯定已经被那个更小的素数筛去了，所以内层循环直接从i * i 开始即可避免重复标记。

第7题 下面程序的运行结果为（ ）。

A. 2

B. 3

C. 4

D. 5

【答案】B

【考纲知识点】二分答案（也称二分枚举法）

【解析】本题考察经典的“二分答案”模型（最大化最小值）。数组排序后为{1, 2, 4, 8, 9}，在其中选择k=3个元素使得相邻差值最大。当假定最小距离为3时，可以选择1、4、8（4−1≥3且8−4≥3），满足条件；假定距离为4时，选了1之后只能选8，选不够3个，不满足条件。因此最大满足要求的距离是3，选B。

第8题 在升序数组中查找第一个大于等于x的位置，下面循环中横线应填（ ）。

A.  r = mid;

B.  r = mid - 1;

C.  l = mid;

D.  l = mid + 1;

【答案】A

【考纲知识点】二分查找

【解析】题目要求在升序数组中查找第一个大于等于x的元素位置（即lower_bound）。在二分过程中，如果满足条件a[mid] >= x，说明当前的mid可能是目标位置，或者目标位置在mid的左侧。为了不漏掉这个可能的答案，右边界应该更新为mid，即r = mid;。这种二分写法也不会导致死循环。

第9题 关于递归函数调用，下列说法错误的是（ ）。

A.递归调用层次过深时，可能会耗尽栈空间导致栈溢出

B.尾递归函数可以通过编译器优化来避免栈溢出

C.所有递归函数都可以通过循环结构来改写，从而避免栈溢出

D.栈溢出发生时，程序会抛出异常并可以继续执行后续代码

【答案】D

【考纲知识点】递归

【解析】A选项：每次递归都会消耗系统栈内存，层数过深确实会溢出。B选项：尾递归在某些编译器和优化设置下可能被优化为循环，从而减少栈空间消耗，但这不是C++标准强制保证的行为，相比之下D选项明显错误。C选项：依据理论，所有递归问题都可用显式栈配合循环来转换为非递归实现。D选项：在C/C++等语言中，栈溢出通常会导致严重错误（如段错误或进程崩溃），操作系统会强行终止进程，不能通过普通的异常捕获来继续正常执行后续代码，说法错误。

第10题 给定n根木头，第i根长度为a[i]。要切成不少于m段等长木段，求最大可能长度，则横线上应填写（ ）。

A.  

B.  

C.  

D.  

【答案】A

【考纲知识点】二分答案（也称二分枚举法）

【解析】本题依然采用二分答案求最大可能长度。当check(mid)为真时，说明长度为mid是可行的，我们要继续寻找有没有更大的长度。此时记录了最优解ans = mid，因此接下来的搜索范围可以安全地避开mid，转到[mid + 1, r]，故应填l = mid + 1;。反之若不可行，则转到[l, mid - 1] 寻找，填r = mid - 1;。选A。

第11题 下面代码用分治求“最大连续子段和”，其时间复杂度为（ ）。

A. O(n²)

B. O(nlogn)

C. O(logn)

D. O(n)

【答案】B

【考纲知识点】分治算法（归并排序和快速排序）

【解析】该算法采用典型的分治思想，将规模为n的问题划分为两个规模为n2的子问题进行递归处理。而合并步骤中，为了计算跨越中点的最大子段和，代码向左和向右分别遍历了一遍当前区间的元素，合并操作的时间开销为O(n)。因此其递归时间复杂度表达式为T(n)=2T(n/2)+O(n)，根据主定理得出该算法的时间复杂度为O(nlogn)。

第12题 游戏大赛决赛，两组选手分别按得分从小到大排好队，现在要把他们合并成一个有序排行榜。

A组：A = {12, 35, 67, 89}，B组：B = {20, 45, 55, 78}，下面是归并合并函数的核心循环，横线处应填入（ ）。

A. A[i] >= B[j]

B. A[i] <= B[j]

C. i >= j

D. i <= j

【答案】B

【考纲知识点】分治算法（归并排序和快速排序）

【解析】这是归并排序中合并两个有序数组的经典过程。题目要求最终合并为从小到大的有序排行榜。因此当遍历时，应当比较A组和B组当前的元素大小，谁小就优先将谁放入结果数组中。为了保证相同元素时原有顺序不改变（稳定性），在A[i] <= B[j] 时选取前面数组的元素A[i]并将其对应的指针i后移。选项B符合逻辑。

第13题 有n位同学的成绩已经从小到大排好序，现在对它执行下面这段以第一个元素为pivot的快速排序，请问此次排序的时间复杂度是（ ）。

A. O(n)

B. O(nlogn)

C. O(n²)

D. O(logn)

【答案】C

【考纲知识点】分治算法（归并排序和快速排序）

【解析】在快速排序中，若总是选取第一个元素作为枢轴（pivot），且给定数组已经是有序状态，那么在每次划分子数组时，pivot右边没有比它小的元素。这会导致划分产生的两个子数组长度极度不平衡，一个是0，另一个是n−1。此时递归树退化成了一条链式结构，递归深度达到n，每层的时间开销依然是O(n)，导致总时间复杂度退化为最坏情况O(n2)。

第14题 下面关于排序算法的描述中，不正确的是( )。

A.冒泡排序和插入排序都是稳定的排序算法

B.快速排序和归并排序都是不稳定的排序算法

C.冒泡排序和插入排序最好时间复杂度均为O(n)

D.归并排序在最好、最坏和平均三种情况的时间复杂度均为O(nlogn)

【答案】B

【考纲知识点】算法：排序概念和稳定性

【解析】

A选项正确，冒泡和插入排序只在相邻元素间操作，不会改变相等元素的相对位置，所以稳定。

B选项错误，快速排序中枢轴交换的过程会导致不稳定，但归并排序在合并子数组时严格控制了相等元素的插入顺序，是典型的稳定排序算法。

C选项正确，插入排序在已有序时为O(n)；冒泡排序若采用“本轮无交换则提前结束”的优化，最好情况为O(n)。在常见教材语境下，冒泡排序最好复杂度通常指优化版，因此C可视为正确。

D选项正确，归并排序恒定对半分，时间复杂度固定。

第15题 下面代码实现两个整数除法，其中被除数为一个“大整数”，用字符串表示，除数是一个小整数，用int表示，则横线处应该填写（ ）。

A.  rem /= b;

B.  rem %= b;

C.  rem = b;

D.  rem = q;

【答案】B

【考纲知识点】（C++）数组模拟高精度加法、减法、乘法、除法

【解析】这道题使用数组模拟高精度被除数除以单精度除数的过程。在模拟竖式除法的每一位计算中，需要将“上一位的余数乘10再加上当前位数字”构成本次计算的新被除数rem。将新被除数整除单精度除数b得到当前位的商q，而参与下一位运算的则是本次计算剩下的余数，因此通过rem %= b; 获取新余数，B选项正确。

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

第1题 有一个存储了n个整数的线性表，分别用数组和单链表两种方式实现。在已知下标（或结点指针）的前提下，数组的随机访问是O(1)， 而在链表中已知某结点的指针时，在该结点之后插入一个新结点的操作也是O(1)。

【答案】√

【考纲知识点】单链表、双链表、循环链表

【解析】数组的底层是连续的内存空间，支持通过下标直接进行偏移计算获取元素，因此随机访问的时间复杂度是O(1)。在单链表中，如果不考虑查找前驱的时间，仅仅是在已知当前节点p指针的基础上插入新结点s，只需执行s->next = p->next; p->next = s;，操作与链表总长度无关，因此复杂度同样也是O(1)。描述正确。

第2题 若数组 a已按升序排列，则下面代码可以正确实现 “在 a中查找第一个大于等于x的元素的位置”。

【答案】√

【考纲知识点】二分查找

【解析】这是一个典型的求解下界（lower_bound）的二分查找算法实现。当a[mid] >= x 成立时，说明目标位置一定不会大于mid，所以应当把右边界收缩至当前位置即r = mid；当a[mid] < x 成立时，说明目标一定严格在mid的右边，因此左边界更新为l = mid + 1。该逻辑能正确处理并跳出循环。描述正确。

第3题 快速排序只要每次都选取中间元素作为枢轴，就一定是稳定排序。

【答案】×

【考纲知识点】算法：排序概念和稳定性

【解析】排序算法稳定性的定义是指相等大小的元素在排序后能够保持原有相对顺序不变。快速排序的工作机制决定了它会把元素按照和枢轴的大小关系交换到两侧。不论选取哪个元素作为枢轴，这种远距离位置跳跃式的交换都有可能会打乱原本数值相等的两个元素的先后次序。所以快速排序本质上是不稳定的算法。

第4题 若某算法满足递推式：T(n)=2T(n/2)+O(n)，则其时间复杂度为O(nlogn)。

【答案】√

【考纲知识点】算法复杂度的估算（含多项式、指数、对数复杂度）

【解析】该递推关系式表明，算法将规模为n的大问题划分为了2个规模为n2的子问题进行求解，且在合并或拆分过程花费了额外的O(n)时间。根据时间复杂度分析的主定理（Master Theorem）或通过绘制递归树可推导：树的高度为logn，且每一层的操作代价总和均为O(n)。因此最终的时间复杂度为O(nlogn)。描述正确。

第5题 在一个数组中，如果两个元素 a[i]和a[j]满足i < j且a[i] > a[j]，则a[i]和a[j]是一个逆序对。

下面代码可以正确统计数组a区间[l,r]内的逆序对总数。

【答案】×

【考纲知识点】分治算法（归并排序）

【解析】该代码只有在[l,m]和[m+1,r]两个区间已经分别有序时，才能正确统计“跨越左右区间”的逆序对数量；但题目说的是统计数组区间[l,r]内的逆序对总数，代码既没有递归统计左右区间内部逆序对，也没有将左右区间合并成有序状态，因此不能正确统计总逆序对。

第6题 根据唯一分解定理，如果大于1的整数不能被任何不超其平方根的质数整除，那么n必定是质数。

【答案】√

【考纲知识点】唯一分解定理

【解析】根据数论中的唯⼀分解定理及素因数分解原理，如果一个大于1的整数n是合数，那么它一定可以分解为至少两个质因子的乘积，且这两个因子中必然至少存在一个较小因子是不大于n的。逆反地推论，如果n没有发现任何小于等于n的质因数来整除它，那就说明n没有除自身外的质因子，因此n一定是素数。描述正确。

第7题 假设数组 a的值域范围是D，以下程序的时间复杂度是

【答案】√

【考纲知识点】二分答案（也称二分枚举法）

【解析】程序先对数组排序，复杂度为O(nlogn)。随后在距离范围[0, a[n-1] - a[0]]上进行二分。若值域范围为D，则二分次数为O(logD)。每次调用check都需要线性扫描数组，复杂度为O(n)。因此总复杂度为O(nlogn+nlogD)。

第8题 若一个问题满足最优子结构性质，则一定可以用贪心算法得到最优解。

【答案】×

【考纲知识点】贪心算法

【解析】满足“最优子结构”仅仅是使得问题具备可以使用动态规划或贪心算法进行求解的前提条件。要保证贪心算法真正可以得出全局最优解，该问题还必须满足更严格的“贪心选择性质”，也就是在当前步骤做的每一步局部最优选择，未来一定能导向最终的全局最优。缺乏贪心选择性质时，只有使用动态规划去全局推导才是安全的。描述错误。

第9题 线性筛相比埃氏筛的核心改进在于：埃氏筛中一个合数可能被多个质数重复标记，线性筛通过"每个合数只被其最大质因子筛去"的策略，保证每个合数恰好被标记一次，从而实现O(n)的时间复杂度。

【答案】×

【考纲知识点】素数表的埃氏筛法和线性筛法

【解析】题目描述前半部分解释埃氏筛法的重复标记缺陷是正确的，并且线性筛（欧拉筛）的初衷也是为了保证每个数只被筛选一次进而实现严格的O(n)时间复杂度。但线性筛的正确实现策略是确保“每个合数只被其最小质因子筛除”而不是最大质因子。概念表述错误，判定为错。

第10题 任何递归程序都可以改写为等价的非递归程序，但改写后的非递归程序一定需要显式地使用栈来模拟递归调用过程。

【答案】×

【考纲知识点】递归

【解析】递归程序都可以改写为非递归程序，但不一定必须使用“显式栈”，还可以用循环或数学递推等形式。例如递归求阶乘，就可以改写成循环迭代的形式。

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

1.3.1 编程题1

试题名称：有限不循环小数

时间限制：1.0 s

内存限制：512.0 MB

1.3.1.1 题目描述

若1a可化为一个有限的，不循环的小数，则称a为终止数。

请你求出在L到R中终止数的数量。

1.3.1.2 输入格式

输入一行，包含两个整数L,R。

1.3.1.3 输出格式

输出一行，包含一个整数，表示L到R中终止数的数量。

1.3.1.4 样例

1.3.1.4.1 输入样例

2 11

1.3.1.4.2 输出样例

5

1.3.1.5 样例解释

在[2,11]终止数有2、4、5、8、10。

1.3.1.6 数据范围

保证1≤L≤R≤10⁶。

1.3.1.7 参考程序

【考纲知识点】初等数论

【解析】这道题的考点在于识别分数能够化为有限小数的充要数学规律。由于十进制的基数是10，根据数论原理，一个最简分数的分母如果仅仅包含素因子2和5，它就可以化为不循环的有限小数。代码遍历L到R之间的每一个数，利用不断除以2和5将这两个因子全部剔除，最后判断如果剩下的值等于1，就说明这是个终止数并累加答案。

1.3.2 编程题2

试题名称：找数

时间限制：1.0 s

内存限制：512.0 MB

1.3.2.1 题目描述

给定一个包含n个互不相同的正整数的数组A与一个包含m个互不相同的正整数的数组B，请你帮忙计算有多少数在数组A与 数组 B中均出现。

1.3.2.2 输入格式

第一行包含两个整数n,m。

第二行包含n个正整数a₁,a₂,⋯,a_n表示数组A。

第三行包含m个正整数b₁,b₂,⋯,b_m表示数组B。

1.3.2.3 输出格式

输出一个整数，表示在数组A与 数组 B中均出现的数的个数。

1.3.2.4 样例

1.3.2.4.1 输入样例

3 5

4 2 3

3 1 5 4 6

1.3.2.4.2 输出样例

2

1.3.2.5 样例解释

样例1中，4、3在数组A与B中均出现。

1.3.2.6 数据范围

对于40%的数据，保证1≤n,m≤1000。

对于100%的数据，保证1≤n,m≤10⁵，1≤a_i,b_i≤10⁹。

1.3.2.7 参考程序

【考纲知识点】二分查找

【解析】本题需要在庞大数据量的数组A中寻找数组B里的元素。暴力遍历查询的时间复杂度为O(n×m)，会造成超时。正确且高效的做法是将其中一个数组（如数组A）预先通过std::sort排序，其开销为O(nlogn)。然后在遍历数组B的过程中，采用二分查找的思想去查询数组A中是否存在相同的值，将查询时间降至O(mlogn)，整体算法可满足百万级数据的限时要求。

策划：GESP技术委员会副主席 刘晓庆

技术支持：GESP技术委员会常务委员 宋旭彤