当前位置：首页 > news >正文

GESP认证C++编程真题解析 | 202506 七级

news 2026/5/8 22:58:35

欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
希望系统学习C++/Python编程的初学者
想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

单选题

第1题

已知小写字母 b 的ASCII码为98，下列C++代码的输出结果是（）。

#include <iostream>
using namespace std;
int main() {char a = 'b' ^ 4;cout << a;return 0;
}

A.b

B.bbbb

C.f

D.102

【答案】：C

【解析】

C++中，运算符^表示对两个操作数进行按位异或的运算，对表达式'b'^4，其会将'b'类型转换，得到ASCII 码98，来与4运算。98和4的二进制表示分别为：01100010，，00000100，故98^4=102。

但结果保存至char 类型的变量a中，故输出a时，结果应为ASCII码102所对应的字符，故选选C。

第2题

已知 a 为 int 类型变量， p 为 int * 类型变量，下列赋值语句不符合语法的是（）。

A.*(p + a) = *p;

B.*(p - a) = a;

C.p + a = p;

D.p = p + a;

【答案】：C

【解析】

A选项中，*p 表示指针p所指向的 int 型变量，p与a的+运算，表示p 的地址向后偏移a *(类型所对应的字节)单位后的新地址，例如：若p 指向 int 型数组b[100]，则p+a指向其中的元素b[a]，故A选项符合语法。同理，B选项也符合语法。但需要注意的是：符合语法只能确保通过编译，程序运行时，若p+a、p-a指向了非法的地址，则可能导致程序出现运行时错误(RTE)。

C、D选项中，p+a 的运算结果仍为 int*型，其可赋值为p，即：可以作为右值，但其不能作为左值，不能将 p 赋值给p+a的整体，故C选项不符合语法。

第3题

下列关于C++类的说法，错误的是（）。

A.如需要使用基类的指针释放派生类对象，基类的析构函数应声明为虚析构函数。

B.构造派生类对象时，只调用派生类的构造函数，不会调用基类的构造函数。

C.基类和派生类分别实现了同一个虚函数，派生类对象仍能够调用基类的该方法。

D.如果函数形参为基类指针，调用时可以传入派生类指针作为实参。

【答案】：B

【解析】

C++中，基类是用来提供基础功能或接口的类。它可以包含成员变量和成员函数，并能够被其他类继承。派生类则是通过继承基类来扩展功能的类。其继承了基类的成员，可以直接使用它们，也可以重写或扩展。

构造函数是用来初始化对象的特殊成员函数，在创建对象时自动调用。它的名字与类名相同，没有返回值类型。析构函数是用来清理对象或释放资源的特殊成员函数，在对象销毁时自动调用。它的名字是类名的前面加~(如~Base)，没有返回值，也不能带参数。

若基类的析构函数未声明为虚析构函数，而使用基类指针删除派生类对象时，可能只会调用基类的析构函数，导致派生类对象未正确释放其资源。因此，基类的析构函数应声明为虚析构函数，以确保派生类的析构函数被调用。故A选项正确。

构造派生类对象时，会先调用基类的构造函数，再调用派生类的构造函数。这是类继承对象构造的机制，基类构造函数负责初始化基类部分，派生类构造函数负责初始化派生类部分。故B选项错误。

虽然基类和派生类实现了同一个虚函数，但通过基类指针或引用调用时，若未发生多态，则可能调用基类版本的方法；若发生多态(虚函数机制生效)，则会根据对象的实际类型调用派生类版本的方法。故C选项正确。

派生类指针可以隐式转换为基类指针，因此基类指针形参可以接受派生类指针作为实参。这是基类和派生类之间向上类型转换的特点。故D选项正确。

第4题

下列C++代码的输出是（）。

#include <iostream>
using namespace std;
int main() {int arr[5] = {2, 4, 6, 8, 10};int * p = arr + 2;cout << p[3] << endl;return 0;
}

A.6

B.8

C.编译出错，无法运行。

D.不确定，可能发生运行时异常。

【答案】：D

【解析】

p是 int * 类型，其为指向int 型的指针，具体指向arr[2]=6这一元素。

对p[3]，可按p[i]=*(p+i)理解，从而有p[3]=*(arr+5)，然而arr 是仅有5个元素的数组，故p[3]会导致下标越界，虽然能够通过编译，但其为未定义行为，可能会导致运行时错误，故选D。

第5题

假定只有一个根节点的树的深度为 \(1\)，则一棵有 \(N\) 个节点的完全二叉树，则树的深度为（）。

A.\(\lfloor log_2(N)\rfloor + 1\)

B.\(\lfloor log_2(N)\rfloor\)

C.\(\lceil log_2(N)\rceil\)

D.不能确定

【答案】：A

【解析】

对深度为k的完全二叉树，其结点个数的取值范围为\([2^{k-1}, 2^k)\)。令 N 满足 \(2^{k-1}≤N<2^k\)，不等式串两边以2为底取对数，则有\(k-1≤log_2N<k\)，即 \(k = \lfloor log_2N\rfloor + 1\)，故选A。

第6题

对于如下图的二叉树，说法正确的是（）。

在这里插入图片描述

A.先序遍历是 ABDEC 。

B.中序遍历是 BDACE 。

C.后序遍历是 DBCEA 。

D.广度优先遍历是 ABCDE 。

【答案】：D

【解析】

图中二叉树的先序遍历为ABDCE 中序遍历为DBAEC，后序遍历为DBECA，故A、B、C选项错误。

二叉树的广度优先遍历为：按层自顶向下，每层从左向右，图中二叉树的广度优先遍历确为 ABCDE，故D选项正确。

第7题

图的存储和遍历算法，下面说法错误的是（）。

A.图的深度优先遍历须要借助队列来完成。

B.图的深度优先遍历和广度优先遍历对有向图和无向图都适用。

C.使用邻接矩阵存储一个包含个顶点的有向图，统计其边数的时间复杂度为。

D.同一个图分别使用出边邻接表和入边邻接表存储，其边结点个数相同。

【答案】：A

【解析】

图的深度优先遍历需要借助栈来完成，但图上的两种遍历泛用性很高：无论图是有向图还是无向图，是否有重边或自环，都可以使用深度优先遍历和广度优先遍历，故A选项错误，B选项正确。

使用邻接矩阵存图时，需要双重循环，枚举边的起点、终点，来分别统计两点间的边数。而使用邻接表存图时，无论是对各点保存入边还是出边，总边数都不变，故C、D选项正确。

第8题

一个连通的简单有向图，共有28条边，则该图至少有（）个顶点。

A.5

B.6

C.7

D.8

若该简单有向图只有5个顶点，则其为完全图时，边数最多，但此时也只有5*(5-1)=20条边，对于28条边的图，需要在完全图的基础上再新增8条边，必然产生重边，这与图是简单图矛盾。

可令图有6个顶点，此时图最多可以有6*(6-1)=30条边，对于仅有28条边的图，为使其(强)连通，只需从6个顶点的完全图中删去某两点间直接相连的两条边，可以保证这两个点仍能通过其他路径相互到达，故B选项正确。

第9题

以下哪个方案不能合理解决或缓解哈希表冲突（）。

A.在每个哈希表项处，使用不同的哈希函数再建立一个哈希表，管理该表项的冲突元素。

B.在每个哈希表项处，建立二叉排序树，管理该表项的冲突元素。

C.使用不同的哈希函数建立额外的哈希表，用来管理所有发生冲突的元素。

D.覆盖发生冲突的旧元素。

【答案】：D

【解析】

哈希表是一种支持插入、查询元素的数据结构，其将元素本身的值通过哈希函数，计算得到需要插入至哈希表中的下标，并结合某些策略完成元素的最终插入操作，对于插入后的元素，理应能在哈希表中再查询得到。以下分析中，以插入若干整数，取哈希函数H(×)=×%10为例。

在每个哈希表项处，可使用不同的哈希函数再建立一个哈希表。例如，插入1、11、21、...时，这些元素会在哈希表中下标为1的表项处发生冲突，此时在该表项处，可取新哈希函数H2(×)=×%10007，这样可以将冲突元素在二级哈希表中散开，故A选项可以缓解哈希表冲突。

在每个哈希表项处，可建立二叉排序树，因为对于存在偏序关系的类型的元素，二叉排序树也可以实现元素的快速插入和查找，故B选项可以缓解哈希表冲突。

对发生冲突的元素，可使用不同的哈希函数建立额外的哈希表，例如，取新哈希函数H2(×)=×%10007建立额外的哈希表，则向哈希表插入1，其会存入原哈希表中下标为1的表项，而插入11、21、...时，其先与已有元素的表项冲突，然后能够再插入到额外的哈希表中，故C选项可以缓解哈希表冲突。

然而，若只是简单地覆盖发生冲突的旧元素，则不能保证哈希表查询元素的功能。例如，插入1、11、21、...时，每次插入元素，都会导致下标为1的原有表项被覆盖而丢失，从而再查询1时，会判定为元素不存在，使哈希表的功能失真。故D选项不能缓解哈希表冲突。

第10题

以下关于动态规划的说法中，错误的是（）。

A.动态规划方法通常能够列出递推公式。

B.动态规划方法的时间复杂度通常为状态的个数。

C.动态规划方法有递推和递归两种实现形式。

D.对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。

【答案】：B

【解析】

动态规划方法一般可以列出递推式计算，也称作状态转移方程，例如，最大子段和问题的递推式为：f[i]=max(f[i - 1], 0)+a[i]。代码实现时，既可以循环递推计算，又可以实现为递归形式，使用记忆化搜索的方式计算，一般两种实现的时间复杂度相同，故A、C、D选项正确。

动态规划方法的时间复杂度，不仅取决于状态的个数，还应考虑各个状态计算时，可以做的转移个数。例如，最长上升子序列问题中，以f[i] 表示以 a[i] 为结尾的上升子序列的最大长度，可见状态只有n个，但每个状态有O(n)个转移，从而总时间复杂度复杂度达到O(n²)。故B选项错误。

第11题

下面程序的输出为（）。

#include <iostream>
using namespace std;
int rec_fib[100];
int fib(int n) {if (n <= 1)return n;if (rec_fib[n] == 0)rec_fib[n] = fib(n - 1) + fib(n - 2);return rec_fib[n];
}
int main() {cout << fib(6) << endl;return 0;
}

A.8

B.13

C.64

D.结果是随机的

【答案】：A

【解析】

由代码实现，可知 fib 函数的功能是求斐波那契数列，且fib(1)=1，fib(2)=1。故fib(6)即为斐波那契数列的第6项：1、1、2、3、5、8，A选项正确。

第12题

下面程序的时间复杂度为（）。

int rec_fib[MAX_N];
int fib(int n) {if (n <= 1)return n;if (rec_fib[n] == 0)rec_fib[n] = fib(n - 1) + fib(n - 2);return rec_fib[n];
}

A.\(O(2^n)\)

B.\(O(\phi^n),\phi = \frac{\sqrt 5-1}{2}\)

C.\(O(n^2)\)

D.\(O(n)\)

【答案】：D

【解析】

由代码实现，可知程序虽为递归实现，但采用了记忆化搜索的技术，对各个n，fib(n) 只会递归计算一次，便将结果保存在 rec_fib[n]中，后续直接调用，故选项D正确。

第13题

下面 search 函数的平均时间复杂度为（）。

int search(int n, int * p, int target) {int low = 0, high = n;while (low < high) {int middle = (low + high) / 2;if (target == p[middle]) {return middle;} else if (target > p[middle]) {low = middle + 1;} else {high = middle;}}return -1;
}

A.\(O(nlog(n))\)

B.\(O(n)\)

C.\(O(log(n))\)

D.\(O(1)\)

【答案】：C

【解析】

由代码实现，可知程序要在有序数组p中二分查找目标值 target，二分查找算法的平均时间复杂度为 O(log n)，故c选项正确。

第14题

下面程序的时间复杂度为（）。

int primes[MAXP], num = 0;
bool isPrime[MAXN] = {false};
void sieve() {for (int n = 2; n <= MAXN; n++) {if (!isPrime[n])primes[num++] = n;for (int i = 0; i < num && n * primes[i] <= MAXN; i++) {isPrime[n * primes[i]] = true;if (n % primes[i] == 0)break;}}
}

A.\(O(n)\)

B.\(O(n\times log n)\)

C.\(O(n\times log log n)\)

D.\(O(n^2)\)

【答案】：A

【解析】

由代码实现，可知程序枚举n，构造得到必然不是质数的 n *primes[i]，将其筛去，且在 primes[i] | n 时，不再考虑之后的数，这是因为：之后的 n * primes[i +1]、... 中，primes[i + 1] 等已经不再是 n 的最小质因子了，也就是说，筛法中每个合数都会被其最小质因子筛去恰好一次，这就是线性筛法的思路，故A选项正确。

第15题

下列选项中，哪个不可能是下图的广度优先遍历序列（）。

在这里插入图片描述