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

GESP认证C++编程真题解析 | 202603 八级

news 2026/5/9 9:31:53

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

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

适合人群：

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

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

单选题

第1题

某班级有8名男生和6名女生，现要选出3人组成学习小组，要求小组中至少有1名男生和1名女生，则不同的选法共有（）种。

A. 112

B. 168

C. 224

D. 288

【答案】：D

【解析】

分为 1男2女和 2男1女两类。

1男2女：$C_{8}^{1}\times C_{6}^{2}=8\times 15 = 120$

2男1女：$C_{8}^{2}\times C_{6}^{1}=28\times 6 = 168$

合计 288种。

第2题

在杨辉三角中，从第0行开始计数，第10行的所有数之和为（）。

A. 512

B. 1024

C. 2048

D. 4096

【答案】：B

【解析】

第10行数字之和为 $C_{10}^{0}+C_{10}^{1}+...+C_{10}^{10}$，等价对10个物品，每个考虑选或不选，有 $2^{10}$ 种选法。

第3题

下列代码实现了快速幂算法，其时间复杂度为（）。

long long fastPow(long long b, long long e, long long mod) {long long result = 1;while (e > 0) {if (e & 1)result = result * b % mod;b = b * b % mod;e >>= 1;}return result;
}

A. $O(logb)$

B. $O(loge)$

C. $O(logmod)$

D. $O(e)$

【答案】：B

【解析】

循环次数与 e 的值有关，每次循环时， e>>=1 会使得 e 的值每次减半，至多 $log e$ 此就可以使得 e 变为 0。

第4题

从5本不同的数学书和4本不同的物理书中选取3本书，要求至少包含1本数学书，则不同的选法有（）种。

A. 60

B. 74

C. 80

D. 84

【答案】：C

【解析】

分为 1数2物、2数1物、3数0物三类。

1数2物：$C_{5}^{1}\times C_{4}^{2} = 5\times 6 = 30 $

2数1物：$C_{5}^{2}\times C_{4}^{1}=10\times 4 =40$

3数0物：$C_{5}^{3}\times C_{4}^{0}=10\times 1 = 10$

合计 80 种。

第5题

在二叉搜索树（BST）中，若中序遍历的序列为 {1, 2, 3, 4, 5} ，且先序遍历的第一个序列元素为 3 ，则下列说法正确的是（）。

A. 该树一定是一棵完全二叉树

B. 元素4和5不可能是兄弟节点

C. 元素1所在节点的深度可能大于3（根节点深度为1）

D. 元素2一定是元素1的父节点

【答案】：B

【解析】

由先序遍历首元素可知根节点为3，结合二叉搜索数的“左小右大”性质，以及中序遍历序列。将树划分为含结点1、2的左子树和含结点4、5的右子树，A错误。

右子树只含4和5两个结点，必然是父子层级关系，B错误。

左子树仅含1和2两个结点，最大深度为3，C错误。

1可能是2的父节点，2也可能是1的父节点，D错误。

第6题

在一个有向带权图中，使用Dijkstra算法求单源最短路时，若使用优先队列（小根堆）优化，其时间复杂度为（）。

A. $O(V^2)$

B. $O(V\cdot E)$

C. $O((V+E)logV)$

D. $O(V^2logV)$

【答案】：C

【解析】

使用优先队列优化的Dijkstra算法，会在每次从队列中取出距离最小的顶点时，花费 $O(logV)$ 的复杂度。也会在枚举每条边，更新邻居结点的距离时，进行入队操作，同样花费 $O(logV)$ 的复杂度。共有 $V$ 个点和 $E$ 条边，总复杂度为 $O((V+E)logV)$。

第7题

对于含 $n$ 个顶点（$n\ge 2$）的连通加权有向图，若图中不存在负权环，则任意两点之间的最短路径（简单路径）最多包含（）条边。

A. $n$

B. $n-1$

C. $n+1$

D. 无法确定，取决于图的具体边数

【答案】：B

【解析】

若不存在负权环，则任意两点之间的最短路径必然是简单路径（不包含重复结点）。因此，在含有 $n$ 个顶点的图中，一条简单路径最多经过所有 $n$ 个顶点，此时路径上的边数为顶点数减 $1$，即 $n-1$ 条。

第8题

在使用Floyd算法求任意两点间最短路径时，时间复杂度为 $O(V^3)$。若在某次算法执行前，已经用 Dijkstra 算法正确求出了所有点对的最短路并存入了 dist 数组。如果此时继续对该 dist 数组执行一次完整的 Floyd 算法过程（无任何提前终止），执行完毕后 dist 数组内的值（）。

A. 会发生改变，因为 Floyd 又做了一次松弛

B. 不会发生改变

C. 可能变大，因为未针对已有最短路优化

D. 可能在某些负权图中陷入死循环

【答案】：B

【解析】

若初始的 dist 已经包含了所有点对的最短路径，那么更新操作不会改变任何值，故 dist 数组保持不变。

第9题

关于图论中的最短路径算法，下列说法中严格正确的是（）。

A. Dijkstra 算法能够高效处理包含负权边的有向图。

B. Floyd 算法可以求出任意两点间的最短路径，且允许图中存在负权边（但不能有负权环）。

C. 单源最短路径算法无法用于无向图，无向图只能通过 BFS 求解。

D. Dijkstra 算法的每一步必定从当前未访问的节点中，选取距离起始点最远的节点进行松弛操作。

【答案】：B

【解析】

Dijkstra 算法基于贪心策略，要求所有边权非负，A错误。

单源最短路径算法均可用于无向图，只需将无向边视为两条方向相反的有向边。BFS仅适用于无权图。C错误。

Dijkstra 算法每次选取当前距离起点最近的未访问结点进行松弛，而非最远。

第10题

有6个人排成一排照相，其中甲、乙两人必须相邻，且丙不能站在排头的不同排法有（）种。

A. 120

B. 144

C. 192

D. 240

【答案】：C

【解析】

采用捆绑法，先考虑甲、乙相邻，将两人视为一个整体，内部有2种排列。此时相当于有5个元素进行全排列，总数为 $5!\times 2=120\times 2 = 240$ 种。

再减去丙在排头的情况：固定丙在第一位，剩余4个位置需排列甲、乙（相邻）和其他3人。选定位置后，整体内部有2种，其余3人全排列有 $3!=6$ 种，故丙在排头的排法数为 $4\times 2\times 6 = 48$ 种。

因此满足条件的排法数为 240 - 48 = 192 种。

第11题

下列代码试图实现Floyd算法求所有点对之间的最短路径，横线处应填入（）。

void floyd(int n, int dist[][MAXN]) {for (int k = 0; k < n; k++)for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)if (__________) // 在此处填入选项dist[i][j] = dist[i][k] + dist[k][j];
}

A. dist[i][k] + dist[k][j] < dist[i][j]

B. dist[i][k] != INF && dist[k][j] != INF

C. dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]

D. dist[i][j] == INF

【答案】：C

【解析】

A选项缺少对无穷大的判断，可能导致无效运算，错误。

B选项缺少大小比较，会错误地将所有可达路径都更新，错误。

D选项不符合逻辑，错误。

第12题

用数字 0、1、2、3、4 组成无重复数字的五位偶数，共有（）个。

A. 48

B. 60

C. 72

D. 96

【答案】：B

【解析】

个位为0：首位有4种选择，后三位全排列，共 $4\times 6 = 24$ 种。

个位为2：首位有3种选择，后三位全排列，共 $3\times 6 = 18$ 种。

个位为4：同上，也有18种。

总数为 24 + 18 + 18 = 60。

第13题

在一个无向带权图中，若使用 Prim 算法从顶点 0 开始构造最小生成树（边权均为正整数，且 graph[u][v] == 0 表示无边），下列代码中横线处应填入（）。

int prim(vector<vector<int>>& graph, int n) {vector<bool> inMST(n, false);vector<int> minEdge(n, INT_MAX);minEdge[0] = 0;int result = 0;for (int i = 0; i < n; i++) {int u = -1;for (int j = 0; j < n; j++)if (!inMST[j] && (u == -1 || minEdge[j] < minEdge[u]))u = j;inMST[u] = true;result += minEdge[u];for (int v = 0; v < n; v++)if (__________) // 在此处填入选项minEdge[v] = graph[u][v];}return result;
}

A. graph[u][v] && !inMST[v] && graph[u][v] < minEdge[v]

B. !inMST[v] && graph[u][v] < minEdge[v]

C. graph[u][v] > 0 && !inMST[v]

D. !inMST[v] && minEdge[v] > 0

【答案】：A

【解析】

Prim算法中，每次将一个顶点 u 加入生成树后，需要更新其他未加入顶点 v 到当前树的最小边权。更新条件为：

v 不在树中；
存在边(u,v)（权值非零）；
该边的权值小于当前记录的最小边权 minEdge[v]。

选项A完整包含了这3个条件，正确。

第14题

已知三个点 $A(x_1,y_1),B(x_2,y_2),C(x_3,y_3)$ 在平面直角坐标系中的坐标。下列 C++ 表达式中，在精度误差范围1e-8内能正确计算判断这三个点是三点共线的表达式是（）。

A. (x2-x1)/(y2-y1) == (x3-x1)/(y3-y1)

B. (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1) == 0

C. fabs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)) < 1e-8

D. fabs((x2-x1)/(y2-y1)-(x3-x1)/(y3-y1)) < 1e-8

【答案】：C

【解析】

判断三点共线的常用方法是利用向量叉积：$\overrightarrow {AB}\times \overrightarrow {AC}=(x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1)$。

若叉积为0，则贡献。但浮点数运算存在精度误差，应使用绝对值小于某个阈值。选C。

第15题

在64位操作系统下（LP64 / LLP64 模型），下面代码的输出结果是（）。

#include <iostream>
using namespace std;int main() {int a[4] = {1, 2, 3, 4};int (*p)[4] = &a;int *q = a;cout << sizeof(a) << " ";cout << sizeof(p) << " ";cout << sizeof(p + 1) << " ";cout << sizeof(q + 1) << " ";cout << (p + 1) - p << " ";cout << (q + 1) - q << endl;
}

A. 16 8 8 8 1 1

B. 16 8 16 8 1 1

C. 16 8 8 4 4 1

D. 16 8 8 8 4 1

【答案】：A

【解析】

在64位系统下，指针大小为8字节，int大小为4字节。