GESP Python 编程八级 · 2026 年 9 月卷

用数字 0、1、2、3、4、5 组成没有重复数字的三位数，且该三位数能被 3 整除，共有（ ）个。

• A.36
• B.40
• C.44
• D.48

6 个人围成一圈就座，座位没有区分，但区分时针方向，且甲、乙两人必须相邻，则共有（ ）种不同坐法。

• A.24
• B.36
• C.48
• D.120

将 6 个完全相同的小球放入 4 个不同的盒子中，每个盒子均可以为空，共有（ ）种不同的放法。

• A.10
• B.60
• C.84
• D.4096

某二叉树的先序遍历序列为A B D E C F G，中序遍历序列为D B E A F C G，则其后序遍历序列为（ ）。

• A.D E B F G C A
• B.D B E F G C A
• C.D E B G F C A
• D.D E B F C G A

关于快速幂算法，下列说法正确的是（ ）。

• A.快速幂可以处理任意整数负指数的情况
• B.快速幂将指数按二进制拆分，能够把乘法次数从朴素乘幂时的 O(b) 优化为 O(log b)
• C.快速幂只能在模数为质数时使用
• D.快速幂的空间复杂度通常为 O(b)

杨辉三角中，第 7 行第 3 个数（行、列均从 0 开始计数）是（ ）。

• A.21
• B.35
• C.42
• D.56

一个长方形的长是宽的 3 倍，周长为 48，则该长方形的面积为（ ）。

• A.72
• B.96
• C.108
• D.144

若 x + y = 7，x − y = 1，则 x × y 的值为（ ）。

• A.7
• B.8
• C.10
• D.12

关于最小生成树（MST）算法，下列说法正确的是（ ）。

• A.Prim 算法适用于稠密图，Kruskal 算法适用于稀疏图
• B.Prim 算法和 Kruskal 算法得到的最小生成树边集一定完全相同
• C.Kruskal 算法必须使用邻接矩阵存储图
• D.Prim 算法只能处理有向图

某连通带权无向简单图的边集合为{(1, 2, 5), (1, 3, 1), (2, 3, 3), (2, 4, 4), (3, 4, 2), (3, 5, 6), (4, 5, 7)}，其中，每条边的三元组 (u, v, w) 表示结点 u 和结点 v 之间有一条权值为 w 的无向边。使用 Kruskal 算法按边权从小到大扫描，第 3 条被选入最小生成树的边是（ ）。

• A.(1, 2, 5)
• B.(2, 3, 3)
• C.(3, 4, 2)
• D.(4, 5, 7)

Floyd 算法经典三重循环 for k for i for j，最外层变量 k 代表（ ）。

• A.当前允许作为中间顶点的最大编号（即只允许编号不超过k的顶点作为中间点）
• B.当前起点
• C.当前终点
• D.当前最短路径的长度

下列函数按渐近增长速度从慢到快排列，正确的是（ ）。

• A.O(n²)、O(n log n)、O(n)、O(log n)
• B.O(log n)、O(n)、O(n²)、O(n log n)
• C.O(log n)、O(n)、O(n log n)、O(n²)
• D.O(n log n)、O(log n)、O(n)、O(n²)

在使用小根堆（优先队列）优化的 Dijkstra 算法中，堆中每个元素通常存储的是（ ）。

• A.顶点编号和该顶点当前的最短距离
• B.边的权值和边的终点
• C.顶点的入度
• D.父结点编号和边权

对长度为 n 的数组使用差分数组支持 m 次区间加操作，最后通过一次前缀和还原每个位置的最终值，整个过程的渐进时间复杂度为（ ）。

• A.O(mn)
• B.O((n + m) log n)
• C.O(n log m)
• D.O(n + m)

假设在 Python 标准实现下运行下面程序运行打印输出为（ ） 1 class A: 2 def __init__(self): 3 print("A",end="") 4 def __del__(self): 5 print("~A",end="") 6 class B(A): 7 def __init__(self): 8 super().__init__() 9 print("B",end="") 10 def __del__(self): 11 print("~B",end="") 12 def main(): 13 b = B() 14 main()

• A.BA~A~B
• B.BA~B~A
• C.AB~A~B
• D.AB~B

从 4 本不同的书中选出 3 本，分别分给甲、乙、丙 3 人，每人至多 1 本，共有 P(4,3) = 24 种不同分法。

对任意正整数 n，二项式 (a + b)^n 的展开式中，按项序从第 0 项起计数，奇数项系数之和等于偶数项系数之和。

若一个连通无向图的最小生成树中存在权值相同的边，则最小生成树一定不唯一。

使用邻接表存储图时，Dijkstra 算法的朴素实现（不使用堆优化）的时间复杂度为 O(V²)，其中 V 为结点数。

堆排序是一种稳定的排序算法。

每个大于 1 的整数都可以唯一地分解为若干个质因数的乘积（不考虑因子顺序）。

循环队列通过牺牲一个存储单元，可以区分队空和队满两种状态。

Python 子类继承父类后，父类中定义的公开方法，在子类实例对象上一定可以直接对外访问调用。

使用滚动数组优化动态规划时，通常只能降低空间复杂度，不能降低时间复杂度。

一个三角形的三条边的边长分别为 5、12、13，则它的面积为 30。

试题名称：生成树计数 时间限制：1.0 s　内存限制：512.0 MB 题目描述：给定一张有 n 个顶点 m 条边的无向连通图 G，顶点依次以 1, 2, …, 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 ≤ n ≤ 8，1 ≤ m ≤ 10。 对于 60% 的测试点，保证 1 ≤ n ≤ 2000，1 ≤ m ≤ 2000。 对于所有测试点，保证 1 ≤ n ≤ 10^5，1 ≤ m ≤ 10^5，1 ≤ u_i, v_i ≤ n。

作答说明：按题目要求完成程序或作品；需要在线运行与自动判分时，可在站内选择「在线考试」。

试题名称：末班车 时间限制：5.0 s　内存限制：512.0 MB 题目描述：城市里有 n 个地铁站以及 m 条地铁线路，地铁站依次以 1, 2, …, n 编号。 第 i 条地铁线路（1 ≤ i ≤ m）的列车从地铁站 u_i 单向驶向地铁站 v_i，最晚发车时间为第 l_i 分钟，途中行驶需要 t_i 分钟。从第 0 分钟到第 l_i 分钟，每分钟都会有一班列车从地铁站 u_i 发出。第 x 分钟（0 ≤ x ≤ l_i）发出的列车会在第 x + t_i 分钟到达地铁站 v_i，乘坐这班列车的乘客可以换乘第 x + t_i 分钟以及之后的所有从地铁站 v_i 发出的任意线路的列车。 现在有 q 组询问。第 i 组询问（1 ≤ i ≤ 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 ≤ 100。 对于所有测试点，保证： 1 ≤ n ≤ 500 1 ≤ m ≤ 1000 1 ≤ q ≤ 5 × 10^5 1 ≤ u_i, v_i, x_i, y_i ≤ n 0 ≤ l_i, s_i ≤ 10^5 1 ≤ t_i ≤ 10^4

作答说明：按题目要求完成程序或作品；需要在线运行与自动判分时，可在站内选择「在线考试」。