2026年3月GESP C++八级 真题深度解析
「GESP练题小程序艾墨舟编程小先锋」专为GESP考生打造的免费题库。涵盖图形化/Python/C++全真题，支持真题模考、考前预测、错题整理与学习统计，一站式攻克客观题。
GESP考级免费刷题小程序
一、选择题解析
──── ✨ 第1题 ✨ ────
题目： 某班级有8名男生和6名女生，现要选出3人组成学习小组，要求小组中至少有1名男生和1名女生，则不同的选法共有（ ）种。
考查知识点： 组合数学（分类计数原理、组合数计算）
解题思路：“至少1男1女”的反面是“全男”或“全女”。总选法为从14人中选3人：C(14,3)=364。
全男选法：C(8,3)=56 全女选法：C(6,3)=20 因此，符合要求的选法为：364 - 56 - 20 = 288。
选项详解：
───── ✨ 第2题 ✨ ────
题目： 在杨辉三角中，从第0行开始计数，第10行的所有数之和为（ ）。
考查知识点： 杨辉三角的性质（二项式系数和）
解题思路：杨辉三角第n行的所有数之和等于2^n。第10行（n=10）的和为2^10 = 1024。
选项详解：
───── ✨ 第3题 ✨ ────
题目： 下列代码实现了快速幂算法，其时间复杂度为（ ）。
考查知识点： 快速幂算法的时间复杂度分析
解题思路：快速幂算法通过将指数e二进制分解，每次循环e右移一位（e >>= 1），循环次数取决于e的二进制位数，即O(log e)。
选项详解：
───── ✨ 第4题 ✨ ────
题目： 从5本不同的数学书和4本不同的物理书中选取3本书，要求至少包含1本数学书，则不同的选法有（ ）种。
考查知识点： 组合数学（分类计数、组合数）
解题思路：总共有9本书。至少1本数学书，可分为三类：
1数2物：C(5,1)C(4,2)=56=30 2数1物：C(5,2)C(4,1)=104=40 3数0物：C(5,3)C(4,0)=101=10 合计：30+40+10=80。 也可用排除法：总选法C(9,3)=84，减去全物理书C(4,3)=4，得80。
选项详解：
───── ✨ 第5题 ✨ ────
题目： 在二叉搜索树（BST）中，若中序遍历的序列为{1, 2, 3, 4, 5}，且先序遍历的第一个序列元素为3，则下列说法正确的是（ ）。
考查知识点： 二叉搜索树的性质、遍历序列
解题思路：中序遍历有序，说明BST节点值就是1,2,3,4,5。先序遍历第一个是根节点3。因此，左子树包含{1,2}，右子树包含{4,5}。分析选项： A. 不一定是完全二叉树，例如根3，左子2，右子4，2的左子1，4的右子5，就不是完全二叉树。 B. 元素4和5在右子树，它们可能是兄弟节点（如果4是父节点，5是其右子；或者5是父节点，4是其左子；但若右子树根为4，则5只能是4的右子，不是兄弟；若右子树根为5，则4是5的左子，也不是兄弟）。实际上，在BST中，4和5如果都是某个节点的子节点，那么它们只能是父子关系，不能是兄弟，因为兄弟节点一个大于父、一个小于父，而4和5都大于3。所以B正确。 C. 元素1所在节点的深度可能大于3。例如根3，左子2，2的左子1，深度为3（根深度1）。深度不可能大于3，因为只有5个节点，1在最左下角时深度最大为3。 D. 元素2不一定是元素1的父节点，例如根3，左子1，1的右子2，此时2是1的子节点。
选项详解：
───── ✨ 第6题 ✨ ────
题目： 在一个有向带权图中，使用Dijkstra算法求单源最短路时，若使用优先队列（小根堆）优化，其时间复杂度为（ ）。
考查知识点： Dijkstra算法的时间复杂度（堆优化版本）
解题思路：使用优先队列（二叉堆）优化的Dijkstra算法，每个节点入队出队一次，每次出队调整堆O(log V)，每条边可能松弛一次导致入队O(log V)。总复杂度为O((V+E) log V)，通常简化为O(E log V)。
选项详解：
───── ✨ 第7题 ✨ ────
题目： 对于含n个顶点（n>=2）的连通加权有向图，若图中不存在负权环，则任意两点之间的最短路径（简单路径）最多包含（ ）条边。
考查知识点： 最短路径的性质（简单路径、无负权环）
解题思路：最短路径一定是简单路径（无环）。n个顶点的简单路径最多经过n-1条边（经过所有顶点一次）。如果包含n条或更多边，则必然重复经过某个顶点，形成环。由于没有负权环，这个环可以去掉而不增加路径长度（如果是零环或正环，去掉后路径更短或不变）。因此，最短路径最多包含n-1条边。
选项详解：
───── ✨ 第8题 ✨ ────
题目： 在使用Floyd算法求任意两点间最短路径时，时间复杂度为O(n^3)。若在某次算法执行前，已经用Dijkstra算法正确求出了所有点对的最短路并存入了dist数组。如果此时继续对该dist数组执行一次完整的Floyd算法过程（无任何提前终止），执行完毕后dist数组内的值（ ）。
考查知识点： Floyd算法的性质（动态规划、松弛操作）
解题思路：Floyd算法的核心是动态规划：dist[k][i][j]表示只经过前k个中间节点时i到j的最短距离。当dist数组已经存储了所有点对的最短路径（即已经是最优解）时，再进行Floyd的松弛操作（dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])）不会改变任何值，因为dist[i][j]已经是最小值，不会大于dist[i][k]+dist[k][j]（由三角不等式）。因此数组不会改变。
选项详解：
───── ✨ 第9题 ✨ ────
题目： 关于图论中的最短路径算法，下列说法中严格正确的是（ ）。
考查知识点： 最短路径算法（Dijkstra、Floyd、BFS）的性质与适用条件
解题思路：A. Dijkstra不能处理负权边，因为其贪心策略假设当前最短路径是全局最短，负权边会破坏这个假设。 B. Floyd算法基于动态规划，可以处理负权边，只要没有负权环（负权环会导致最短路无界）。 C. 单源最短路径算法（如Dijkstra、Bellman-Ford）也可用于无向图，只需将无向边视为两条有向边。BFS只能用于无权图。 D. Dijkstra每一步选取距离起始点最近的未访问节点，不是最远。
选项详解：
───── ✨ 第10题 ✨ ────
题目： 有6个人排成一排照相，其中甲、乙两人必须相邻，且丙不能站在排头的不同排法有（ ）种。
考查知识点： 排列组合（捆绑法、特殊位置优先考虑）
解题思路：先将甲、乙捆绑成一个整体，内部有2种排法（甲乙、乙甲）。 现在相当于有5个“元素”排队：{甲乙}、丙、丁、戊、己。 要求丙不在排头。 先计算总排法（不考虑丙）：5个元素全排列，5! = 120，乘以捆绑内部2种，得1202=240。 再减去丙在排头的情况：将丙固定排头，剩下4个元素（包括{甲乙}）全排列，4! = 24，乘以捆绑内部2种，得242=48。 因此，符合要求的排法为：240 - 48 = 192。
选项详解：
───── ✨ 第11题 ✨ ────
题目： 下列代码试图实现Floyd算法求所有点对之间的最短路径，横线处应填入（ ）。
考查知识点： Floyd算法的核心松弛条件
解题思路：Floyd算法的松弛操作是：如果经过中间节点k能使i到j的路径变短，即dist[i][k] + dist[k][j] < dist[i][j]，则更新。需要确保dist[i][k]和dist[k][j]都是有效的（不是无穷大），否则加法可能溢出。通常代码中会判断dist[i][k]和dist[k][j]不为无穷大（INF）后再比较。
选项详解：
───── ✨ 第12题 ✨ ────
题目： 用数字0、1、2、3、4组成无重复数字的五位偶数，共有（ ）个。
考查知识点： 排列组合（特殊位置优先、分类讨论）
解题思路：五位偶数，个位必须是0、2、4。 分两类：
个位是0：则万位可以从1、2、3、4中选一个，有4种；剩下三位从剩下的3个数字中选排，有3! = 6种。共4*6=24。 个位是2或4：以个位=2为例。万位不能是0，且不能是2（已用），所以万位可以从1、3、4中选一个，有3种；中间三位从剩下的3个数字（包括0）中选排，有3! = 6种。所以个位=2有3*6=18种。同理个位=4也有18种。 总计：24 + 18 + 18 = 60。
选项详解：
───── ✨ 第13题 ✨ ────
题目： 在一个无向带权图中，若使用Prim算法从顶点0开始构造最小生成树（边权均为正整数，且graph[u][v] == 0表示无边），下列代码中横线处应填入（ ）。
考查知识点： Prim算法的实现细节（松弛操作的条件）
解题思路：Prim算法中，当选中一个顶点u加入MST后，需要更新其他未加入顶点v的最小边权minEdge[v]。更新条件是：顶点v未加入MST，且存在边(u,v)（即graph[u][v] != 0），且该边权小于当前minEdge[v]。 选项分析： A. graph[u][v] && !inMST[v] && graph[u][v] < minEdge[v] —— 正确，graph[u][v]非0表示有边，且满足Prim的松弛条件。 B. 缺少对边存在的判断（graph[u][v]可能为0）。 C. 缺少与minEdge[v]的比较，可能将不是更小的边更新进去。 D. 缺少对边存在的判断，且minEdge[v] > 0不是判断边存在的条件。
选项详解：
───── ✨ 第14题 ✨ ────
题目： 已知三个点(x1,y1), (x2,y2), (x3,y3)在平面直角坐标系中的坐标。下列C++表达式中，在精度误差范围1e-8内能正确计算判断这三个点是三点共线的表达式是（ ）。
考查知识点： 计算几何（三点共线的判断、浮点数精度处理）
解题思路：三点共线的条件是向量(x2-x1, y2-y1)与向量(x3-x1, y3-y1)的叉积为0，即(x2-x1)*(y3-y1) - (x3-x1)*(y2-y1) == 0。 由于浮点数计算有精度误差，不能直接判等，应判断绝对值是否小于一个很小的数（如1e-8）。 选项分析： A. 直接除法比较，可能除零（分母为0），且浮点数判等不靠谱。 B. 叉积判等，未考虑精度误差。 C. 叉积绝对值小于1e-8，正确。 D. 除法差值绝对值，同样有除零和精度问题。
选项详解：
───── ✨ 第15题 ✨ ────
题目： 在64位操作系统下（LP64/LLP64模型），下面代码的输出结果是（）。
考查知识点： C++ sizeof运算符、指针运算、数组与指针的区别
解题思路：
sizeof(a): a是int[4]，大小为4*4=16字节（int在64位通常为4字节）。 sizeof(p): p是指向int[4]的指针，在64位系统指针大小为8字节。 sizeof(p+1): p+1是指针运算，结果仍是指针，大小为8字节。 sizeof(q+1): q是指向int的指针，q+1也是指针，大小为8字节。 (p+1)-p: p是int(*)[4]，p+1跳过整个int[4]（16字节），指针相减得到元素差为1。 (q+1)-q: q是int*，q+1跳过一个int（4字节），指针相减得到元素差为1。 因此输出为"16 8 8 8 1 1"。
选项详解：
二、判断题解析
───── ✨ 第1题 ✨ ────
题目： 在C++中，若结构体中包含一个static成员变量，则该变量的存储空间属于结构体对象的一部分。（ ）
考查知识点： C++静态成员变量的存储特性
解题思路：static成员变量属于类/结构体本身，而不是任何一个对象实例。所有对象共享同一个static变量，它存储在静态存储区，不在对象的内存布局中。
选项详解：
───── ✨ 第2题 ✨ ────
题目： 对于任意正整数n，二项式(a+b)^n展开式中各项的二项式系数之和等于2^n。（ ）
考查知识点： 二项式定理的性质
解题思路：二项式系数之和为C(n,0)+C(n,1)+...+C(n,n)=2^n。这是二项式定理中令a=b=1的直接结果。
选项详解：
───── ✨ 第3题 ✨ ────
题目： 在C++中，若函数参数类型为const int &，则该参数既可以绑定左值，也可以绑定右值。（ ）
考查知识点： C++引用绑定规则（const左值引用）
解题思路：const左值引用可以绑定到左值（如变量），也可以绑定到右值（如临时对象、字面量）。这是C++的特性，延长了右值的生命周期。
选项详解：
───── ✨ 第4题 ✨ ────
题目： 若一个无向图的最小生成树唯一，则图中所有边权必定各不相同。（ ）
考查知识点： 最小生成树的唯一性条件
解题思路：最小生成树唯一的充分条件是图中所有边权互不相同。但如果边权有重复，最小生成树也可能唯一（例如，重复边权但选择不影响唯一性）。因此，“必定各不相同”是充分但不必要条件。题目说“必定”，过于绝对。
选项详解：
───── ✨ 第5题 ✨ ────
题目： 使用快速排序对n个元素进行排序时，无论最好、最坏还是平均情况，时间复杂度均为O(n log n)。（ ）
考查知识点： 快速排序的时间复杂度分析
解题思路：快速排序的平均时间复杂度为O(n log n)，最坏情况（如已排序数组且选择第一个元素为枢轴）为O(n^2)。因此，并非所有情况都是O(n log n)。
选项详解：
───── ✨ 第6题 ✨ ────
题目： 若一个图中所有顶点的度数为偶数，则一定存在欧拉回路。（ ）
考查知识点： 欧拉回路的判定条件（无向图）
解题思路：对于无向图，存在欧拉回路的充要条件是：图是连通的，且所有顶点的度数都是偶数。题目只说了度数条件，未提连通性。如果图不连通，即使每个连通分量内顶点度数为偶数，也不存在经过所有边的回路。因此，“一定存在”过于绝对。
选项详解：
───── ✨ 第7题 ✨ ────
题目： 使用倍增法预处理区间最值问题时，预处理的时间复杂度为O(n log n)，查询的时间复杂度为O(1)。（ ）
考查知识点： 倍增法（RMQ）的复杂度分析
解题思路：倍增法（Sparse Table）预处理需要计算每个起点、每个2的幂长度的区间最值，复杂度为O(n log n)。查询时通过两个重叠区间可以O(1)得到答案。
选项详解：
───── ✨ 第8题 ✨ ────
题目： 如果将⼀个连通⽆向图G中所有边的权值都统⼀增加同⼀个正整数常数k，形成图G'。则G'的最⼩⽣成树中每条边在G中对应的边组成的树，⼀定是G的最⼩⽣成树。（ ）
考查知识点： 最小生成树的性质（边权同增同减）
解题思路：最小生成树的形状取决于边权的相对大小，而不是绝对大小。如果所有边权增加相同的正常数k，边权的大小关系不变，因此最小生成树的边集不会改变。所以G'的MST对应回G的边集，仍然是G的MST。
选项详解：
───── ✨ 第9题 ✨ ────
题目： 在图论算法中，Kruskal算法和Prim算法都可以用来求解最小生成树，且这两者的贪心策略无论在任何连通无向图上求得的最小生成树总边权和必定相同。（ ）
考查知识点： 最小生成树算法的正确性
解题思路：Kruskal和Prim算法虽然策略不同（一个按边贪心，一个按顶点贪心），但都是求解最小生成树的正確算法。对于同一个连通无向图，最小生成树的边权总和是唯一的（尽管边集可能不唯一）。因此，两种算法求出的总边权和一定相同。
选项详解：
───── ✨ 第10题 ✨ ────
题目： 在动态规划问题中，“状态转移方程+递推”和“递归+记忆化搜索”通常是解决同一问题的两种不同实现方式，它们的时间复杂度总是相同的。（ ）
考查知识点： 动态规划的两种实现方式及其复杂度
解题思路：两种方式本质相同，都是基于状态转移方程计算子问题。递归+记忆化搜索（自顶向下）和递推（自底向上）访问的状态数量相同，每个状态的计算代价也相同，因此时间复杂度相同。空间复杂度可能略有差异（递归栈 vs 数组），但时间复杂度一致。
选项详解：
三、编程题解析
3.1 编程题1：消息查找
题目大意：有n条消息，每条消息可能引用一条编号比它小的消息（r[i]表示引用的消息编号，0表示不引用）。从当前消息x出发，可以执行两种操作：1) 定位到编号减1的消息；2) 如果当前消息引用了某条消息，则定位到那条消息。问从x到y的最少操作次数。
解题思路：关键观察：操作只有两种：向左移动一步（x-1），或跳转到引用消息r[x]（如果r[x]!=0）。由于引用消息的编号一定小于当前消息，所以所有移动都是向左的。 因此，问题转化为在一条链（消息编号1~n）上，有一些“快捷通道”（引用），求从x到y的最短路径长度（只能向左走）。
由于引用消息数量不超过2000条（题目保证），我们可以将涉及引用的消息编号提取出来作为“关键点”。预处理所有关键点之间的最短距离（使用DP，因为只能向左，可以递推）。 对于查询(x,y)：
如果x <= y，显然不可能到达（因为只能向左），但题目保证x>=y？题目描述说“当前位于消息i，可以定位到消息i-1”，所以只能向左。但输入样例中x可能大于y，也可能小于y？仔细看样例：查询(4,1)、(6,2)、(6,3)，都是x>y。数据范围说x,y在[1,n]，但未保证x>=y。然而，如果x<y，由于只能向左，无法到达，操作次数应为无穷？但题目未说明。从参考代码看，它假设了x>=y（因为输出x-y）。我们假设x>=y。 策略：从x向左走到最近的关键点pre[x]，然后通过关键点之间的最短距离跳到目标点附近的关键点suf[y]，再向右走到y。或者，如果pre[x] < suf[y]（即中间没有关键点），则直接步行x-y步更优。
参考代码的核心：
标记所有引用消息和被引用的消息为关键点。 对关键点按编号排序，预处理它们之间的最短距离d[i][j]（i>=j）。 对于每个位置i，预处理左边最近的关键点pre[i]和右边最近的关键点suf[i]。 查询时，若pre[x] < suf[y]，说明可以直接走过去（中间无关键点），答案为x-y；否则，答案为x到pre[x]的步行距离 + pre[x]到suf[y]的关键点距离 + suf[y]到y的步行距离。
复杂度分析：设关键点数量为C（C<=2000）。预处理距离d复杂度O(C^2)。查询O(1)。总复杂度O(C^2 + q)。
参考代码：
#include <cstdio>#include <algorithm>using namespace std;const int N = 1e5 + 5;const int C = 2e3 + 5;const int oo = 1e9;int n, q;int r[N], mark[N], pos[N];int p[C], cnt;int d[C][C];int pre[N], suf[N];int main() { scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) { scanf("%d", &r[i]); if (r[i]) mark[i] = mark[r[i]] = 1; } for (int i = 1; i <= n; i++) if (mark[i]) { p[++cnt] = i; pos[i] = cnt; } for (int i = 1; i <= cnt; i++) { for (int j = 1; j <= i; j++) d[i][j] = oo; d[i][i] = 0; for (int j = i; j > 1; j--) { d[i][j - 1] = min(d[i][j - 1], d[i][j] + p[j] - p[j - 1]); if (r[p[j]]) { int k = pos[r[p[j]]]; d[i][k] = min(d[i][k], d[i][j] + 1); } } } for (int i = 1; i <= n; i++) { pre[i] = pre[i - 1]; if (mark[i]) pre[i] = i; } suf[n + 1] = n + 1; for (int i = n; i; i--) { suf[i] = suf[i + 1]; if (mark[i]) suf[i] = i; } while (q--) { int x, y; scanf("%d%d", &x, &y); if (pre[x] < suf[y]) printf("%d\n", x - y); else printf("%d\n", x - pre[x] + d[pos[pre[x]]][pos[suf[y]]] + suf[y] - y); } return 0;}
3.2 编程题2：子图最短路
题目大意：给定一个n个节点m条边的无向带权图。对于每个区间[l, r]（1<=l<=r<=n），考虑子图G(l,r)：只保留节点编号在[l,r]之间的节点及其之间的边。定义d(l,r,i,j)为子图G(l,r)中节点i到j的最短距离（若不连通则为1e9）。求所有区间、所有点对(i,j)（i<=j）的d(l,r,i,j)之和，模1e9。
解题思路：暴力做法：枚举所有区间[l,r]，对每个子图跑Floyd算法求所有点对最短路，然后求和。复杂度O(n^4)，不可行。
观察：n<=100，可以考虑优化。参考代码采用了一种巧妙的DP：
先用邻接矩阵存储原图的最短边（处理重边）。 然后枚举左端点l，初始化g矩阵为原图的邻接矩阵。 接着枚举右端点r从l到n，每次将节点r作为中间点，用Floyd的思想更新g矩阵（松弛所有点对）。此时，g[i][j]表示在区间[l, r]上，只经过节点[l, r]作为中间点时，i到j的最短距离。当r扩展时，我们实际上是在逐步构建包含更多节点的子图的最短路。 对于当前区间[l,r]，g[i][j]已经是在该子图上的最短距离（因为Floyd的k循环到了r）。然后对i,j在[l,r]内且i<=j的d(l,r,i,j)求和，累加到答案。
这样，总复杂度为O(n^4)？实际上，外层l循环O(n)，内层r循环O(n)，每次r扩展需要三重循环更新g（i,j,k都是1~n），但代码中k固定为r，所以是O(n^2)更新。然后对区间内点对求和O(n^2)。所以总复杂度O(n^4)？但n=100，n^4=1e8，加上常数可能勉强可过（时间限制1s可能较紧，但参考代码应该经过优化）。
关键点：
利用Floyd的动态规划特性，当区间右端点r扩大时，只需用新加入的节点r作为中间点进行松弛，即可更新所有点对在新区间上的最短路。 这样避免了为每个区间重新跑完整Floyd。
参考代码：
#include <cstdio>#include <algorithm>using namespace std;const int N = 105;const int mod = 1e9;int n, m;int f[N][N];int g[N][N];int ans;int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) f[i][j] = mod; f[i][i] = 0; } for (int i = 1; i <= m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); f[u][v] = min(f[u][v], w); f[v][u] = min(f[v][u], w); } for (int l = 1; l <= n; l++) { for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) g[i][j] = f[i][j]; for (int r = l; r <= n; r++) { for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) g[i][j] = min(g[i][j], g[i][r] + g[r][j]); for (int i = l; i <= r; i++) for (int j = i; j <= r; j++) ans = (ans + g[i][j]) % mod; } } printf("%d\n", ans); return 0;}
四、学习建议
组合数学：掌握分类计数、分步计数、捆绑法、插空法等基本方法，熟练计算排列组合数。 图论算法：深入理解Dijkstra、Floyd、Prim、Kruskal等算法的原理、实现细节、时间复杂度和适用条件。 动态规划与贪心：理解状态设计、转移方程，并能用递推和记忆化搜索两种方式实现。 C++语言特性：熟悉sizeof、指针运算、引用、静态成员等概念，避免常见陷阱。 编程实践：对于编程题，学会分析问题本质，设计高效算法，注意边界条件和特殊情况的处理。
