2026年9月 GESP C++ 8级认证考试真题（客观题部分）
选 单选题（共 15 题，每题 2 分）
用数字 、 、 、 、 、 组成没有重复数字的三位数，且该三位数能被 整除，共有（ ）个。
个⼈围成一圈就座，座位没有区分，但区分时针方向，且甲、⼄两⼈必须相邻，则共有（ ）种不同坐
法。
有 堆⽯⼦，数量分别为 、 、 、 。每次可以合并相邻两堆，合并代价为两堆⽯⼦数之和。将所有⽯⼦合
并成一堆的最小总代价为（ ）。
某二叉树的先序遍历序列为 A B D E C F G，中序遍历序列为 D B E A F C G，则其后序遍历序列为
（ ）。
关于快速幂算法，下列说法正确的是（ ）。
杨辉三角中，第 行第 个数（行、列均从 开始计数）是（ ）。
一个长方形的长是宽的 倍，周长为 ，则该长方形的面积为（ ）。
若 ， ，则 的值为（ ）。
关于最小生成树（MST）算法，下列说法正确的是（ ）。
某连通带权无向简单图的边集合为 ，其中，每
条边的三元组 表⽰结点 和结点 之间有一条权值为 的无向边。使用 Kruskal 算法按边权从小到大扫
描，第 条被选入最小生成树的边是（ ）。
在使用小根堆（优先队列）优化的 Dijkstra 算法中，堆中每个元素通常存储的是（ ）。
在 Floyd 算法的经典三重循环 for (k) for (i) for (j) 中，最外层变量 k 表⽰（ ）。
下列常见复杂度量级，按渐近增长速度从慢到快排列，正确的是（ ）。
对长度为 的数组使用差分数组支持 次区间加操作，最后通过一次前缀和还原每个位置的最终值，整个
过程的渐进时间复杂度为（ ）。
下列程序的输出结果为（ ）。
#include <iostream>
using namespace std;
class A {
public:
A() {
cout << "A";
}
~A() {
cout << "~A";
}
};
class B : public A {
public:
B() {
cout << "B";
}
~B() {
cout << "~B";
}
};
int main() {
B b;
return 0;
}
判 判断题（共 10 题，每题 2 分）
从 本不同的书中选出 本，分别分给甲、⼄、丙 ⼈，每⼈至多 本，共有 种不同分法。
对任意正整数 ，二项式 的展开式中，按项序从第 项起计数，奇数项系数之和等于偶数项系数之
和。
若一个连通无向图的最小生成树中存在权值相同的边，则最小生成树一定不唯一。
使用邻接表存储图时，Dijkstra 算法的朴素实现（不使用堆优化）的时间复杂度为 ，其中 为结点
数。
堆排序是一种稳定的排序算法。
每个大于 的整数都可以唯一地分解为若⼲个质因数的乘积（不考虑因⼦顺序）。
循环队列通过牺牲一个存储单元，可以区分队空和队满两种状态。
在 C++ 语⾔的私有继承中，基类的 public 成员在派生类中仍为 public 成员。
使用滚动数组优化动态规划时，通常只能降低空间复杂度，不能降低时间复杂度。
一个三角形的三条边的边长分别为 、 、 ，则它的面积为 。
编 编程操作题（共 2 题，共 50 分）
试题名称：生成树计数
时间限制：1.0 s | 内存限制：512.0 MB
题目描述
给定一张有 $n$ 个顶点 $m$ 条边的无向连通图 $G$，顶点依次以 $1,2,\ldots,n$ 编号。$G$ 有以下特殊的性质：
- $G$ 中的每条边至多属于一个简单环。
- $G$ 中没有重边与自环。
简单环是指环中顶点互不相同，且不经过重复边的回路。
请你求出 $G$ 的不同生成树的数量。两棵生成树不同，当且仅当存在一条边在其中一棵生成树中出现，而不在另一棵生成树中出现。
由于答案可能很大，你只要求出答案对 $998244353$ 取模的结果。
输入格式
第一行，两个正整数 $n,m$，分别表示 $G$ 的顶点数与边数。
接下来 $m$ 行，每行两个整数 $u_i,v_i$，表示一条连接顶点 $u_i,v_i$ 的无向边。
输出格式
输出一行，一个整数，表示 $G$ 的不同生成树的数量对 $998244353$ 取模的结果。
样例输入 #1
7 8
1 2
2 3
3 1
3 4
4 5
5 6
6 7
7 4
样例输出 #1
12
样例输入 #2
5 4
1 2
1 3
2 4
2 5
样例输出 #2
1
说明/提示
对于 $40\%$ 的测试点，保证 $1\le n\le 8$，$1\le m\le 10$。
对于 $60\%$ 的测试点，保证 $1\le n\le 2000$，$1\le m\le 2000$。
对于所有测试点，保证 $1\le n\le 10^5$，$1\le m\le 10^5$，$1\le u_i,v_i\le n$。
试题名称：末班车
时间限制：1.0 s | 内存限制：512.0 MB
题目描述
城市里有 $n$ 个地铁站以及 $m$ 条地铁线路，地铁站依次以 $1,2,\ldots,n$ 编号。
第 $i$ 条地铁线路（$1\le i\le m$）的列车从地铁站 $u_i$ 单向驶向地铁站 $v_i$，最晚发车时间为第 $l_i$ 分钟，途中行驶需要 $t_i$ 分钟。从第 $0$ 分钟到第 $l_i$ 分钟，每分钟都会有一班列车从地铁站 $u_i$ 发出。第 $x$ 分钟（$0\le x\le l_i$）发出的列车会在第 $x+t_i$ 分钟到达地铁站 $v_i$，乘坐这班列车的乘客可以换乘第 $x+t_i$ 分钟以及之后的所有从地铁站 $v_i$ 发出的任意线路的列车。
现在有 $q$ 组询问。第 $i$ 组询问（$1\le i\le q$）给出起点地铁站编号 $x_i$，终点地铁站编号 $y_i$ 以及出发时间 $s_i$，你需要判断第 $s_i$ 分钟从地铁站 $x_i$ 出发是否能到达地铁站 $y_i$。第 $s_i$ 分钟从地铁站 $x_i$ 出发意味着你可以乘坐第 $s_i$ 分钟以及之后的所有从地铁站 $x_i$ 发出的任意线路的列车。
输入格式
第一行，三个正整数 $n,m,q$，分别表示地铁站数量，地铁线路数量，询问数量。
接下来 $m$ 行，每行四个整数 $u_i,v_i,l_i,t_i$，分别表示地铁线路的起点，终点，最晚发车时间，行驶所需时间。
接下来 $q$ 行，每行三个整数 $x_i,y_i,s_i$，分别表示行程起点，行程终点，出发时间。
输出格式
输出共 $q$ 行。对于每组询问，如果第 $s_i$ 分钟从地铁站 $x_i$ 出发能到达地铁站 $y_i$ 则输出一行 Yes，否则输出一行 No。请注意输出区分大小写。
样例输入 #1
3 4 5
1 2 3 3
2 3 5 2
3 1 4 1
1 3 0 6
1 3 2
2 1 2
2 1 3
3 2 2
3 2 3
样例输出 #1
Yes
Yes
No
Yes
No
说明/提示
对于 $40\%$ 的测试点，保证 $q\le 100$。
对于所有测试点，保证：
- $1\le n\le 500$
- $1\le m\le 1000$
- $1\le q\le 5\times 10^5$
- $1\le u_i,v_i,x_i,y_i\le n$
- $0\le l_i,s_i\le 10^5$
- $1\le t_i\le 10^4$