GESP C++ 编程七级 · 2026 年 3 月卷

假设一个算法时间复杂度的递推式是 T(n) = 2T(n − 1) + 1（n 为正整数），且 T(0) = 1，那么这个算法的时间复杂度是（ ）。

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

下面关于“唯一分解定理”和“素数筛法”的说法中，错误的是（ ）。

• A.如果预处理出 n 以内每个数的最小质因子，那么可以在 O(log n) 时间内完成任意一个不超过 n 的整数的质因数分解。
• B.线性筛（欧拉筛）能够保证每个合数只被其最小质因子筛掉一次，这一性质依赖于唯一分解定理。
• C.唯一分解定理保证：若一个数未被任何不超过其平方根的质数筛去，则它一定是质数。
• D.唯一分解定理是埃氏筛时间复杂度为 O(n log log n) 的根本原因。

若字符串 A 与字符串 B 的最长公共子序列（LCS）长度为 5，则（ ）。

• A.它们的编辑距离为 5
• B.它们至少有 5 个公共字符
• C.它们最长公共子串长度为 5
• D.它们一定长度相等

对于一棵包含 n 个顶点（n ≥ 2）的树，其所有顶点的度数之和必定等于（ ）。

• A.n − 1
• B.2n − 2
• C.2n
• D.n²

关于哈希表（Hash Table）在不考虑扩容且采用简单均匀哈希函数的前提下，下列说法中错误的是（ ）。

• A.装载因子越大，发生冲突的概率通常越高
• B.开放定址法在删除元素时实现相对复杂
• C.链地址法在最坏情况下查找时间复杂度为 O(n)
• D.查找哈希表的时间复杂度总是 O(1)

深度优先搜索（DFS）在遍历图时，每当访问到某个顶点后，选择一个相邻的未访问顶点继续搜索，直到某个顶点的所有相邻顶点均已被访问，则退回到前一顶点继续搜索。该算法主要运用了（ ）。

• A.分治
• B.贪心
• C.动态规划
• D.回溯

下面程序的运行结果为（ ）。 1 #include <iostream> 2 #include <algorithm> 4 bool check(int n, int a[], int k, int dist) { 5 int cnt = 1; 6 int last = a[0]; 8 for (int i = 1; i < n; i++) { 9 if (a[i] - last >= dist) { 10 cnt++; 11 last = a[i]; 12 } 13 } 15 return cnt >= k; 16 } 18 int solve(int n, int a[], int k) { 19 std::sort(a, a + n); 21 int l = 0; 22 int r = a[n - 1] - a[0]; 24 while (l < r) { 25 int mid = (l + r + 1) / 2; 27 if (check(n, a, k, mid)) 28 l = mid; 29 else 30 r = mid - 1; 31 } 33 return l; 34 } 36 int main() { 37 int a[] = {1, 2, 8, 4, 9}; 38 int n = 5; 39 int k = 3; 41 std::cout << solve(n, a, k) << std::endl; 43 return 0; 44 }

• A.2
• B.3
• C.4
• D.5

下面程序的时间复杂度是（ ），假设数组 a 的值域范围是 D。 1 #include <iostream> 2 #include <algorithm> 4 bool check(int n, int a[], int k, int dist) { 5 int cnt = 1; 6 int last = a[0]; 8 for (int i = 1; i < n; i++) { 9 if (a[i] - last >= dist) { 10 cnt++; 11 last = a[i]; 12 } 13 } 15 return cnt >= k; 16 } 18 int solve(int n, int a[], int k) { 19 std::sort(a, a + n); 21 int l = 0; 22 int r = a[n - 1] - a[0]; 24 while (l < r) { 25 int mid = (l + r + 1) / 2; 27 if (check(n, a, k, mid)) 28 l = mid; 29 else 30 r = mid - 1; 31 } 33 return l; 34 } 36 int main() { 37 int a[] = {1, 2, 8, 4, 9}; 38 int n = 5; 39 int k = 3; 41 std::cout << solve(n, a, k) << std::endl; 43 return 0; 44 }

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

某二叉树共有 10 个结点，记为 A~J，已知它的先序遍历序列为：A B D H I E C F J G，中序遍历序列为：H D I B E A F J C G，则该二叉树的后序遍历序列是（ ）。

• A.H I D E B J F G C A
• B.H I D B E J F G C A
• C.I H D E B J F G C A
• D.H I D E B F J G C A

下面哪一个可能是下图的深度优先遍历序列（ ）。

• A.1, 5, 4, 8, 7, 9, 6, 3, 2
• B.1, 5, 8, 4, 7, 9, 6, 3, 2
• C.2, 5, 8, 7, 9, 6, 3, 4, 1
• D.8, 9, 6, 3, 2, 5, 1, 4, 7

下面这个有向图的强连通分量的个数是（ ）。

• A.3
• B.4
• C.5
• D.6

关于泛洪算法（Flood Fill）的说法，正确的是（ ）。

• A.泛洪算法只适用于二维网格中的四连通或八连通问题。
• B.泛洪算法必须使用递归方式实现。
• C.泛洪算法本质上是对图进行一次从起点出发的搜索。
• D.泛洪算法只能用于统计连通块个数，不能用于计算面积或周长。

有6个字符，它们出现的次数分别为： {2, 3, 3, 4, 6, 8} ，现在用哈夫曼编码为这些字符编码，最小加权路径长度 WPL（每个字符的出现次数x它的编码长度，再把每个字符结果加起来）的值为（ ）。

• A.58
• B.60
• C.62
• D.64

关于单链表、双链表和循环链表，下列说法正确的是（ ）。

• A.在单链表中，若已知某结点的指针，则可以在 O(1) 时间内删除该结点。
• B.循环链表中一定不存在空指针。
• C.在循环双链表中，尾结点的 next 指针一定为 NULL。
• D.在带头结点的循环单链表中，判定链表是否为空只需判断头结点的 next 是否指向自身。

下列关于树的遍历的说法中，正确的一项是（ ）。

• A.对任意一棵树进行深度优先遍历，所得序列一定唯一。
• B.已知一棵二叉树的先序遍历和后序遍历序列，可以唯一确定这棵二叉树。
• C.已知一棵二叉树的先序遍历和中序遍历序列，可以唯一确定这棵二叉树。
• D.一棵二叉树的中序遍历序列是单调递增的，则该二叉树一定是二叉平衡树。

C++ 语言中，表达式4 ^ 2的结果类型为int ，值为6 。

C++ 中引用可以重新绑定。

在 C++ 中，若函数形参为引用类型，则在函数内部对该形参的修改会影响对应的实参。

如果一个最值问题可以用动态规划在多项式时间内求解，那么也一定存在一种贪心策略，可以在多项式时间内求得最优解。

使用归并排序对 n 个元素进行排序时，无论最好、最坏还是平均情况，时间复杂度均为 O(n log n)。

在无向连通图中删除一条边，该图就一定变成非连通图。

在一个无向图中，每个顶点有不同的编号，在执行深度优先遍历过程中选择下一个顶点时总是优先选择编号更小的相邻顶点，则从指定顶点开始的遍历序列是唯一的。

若所有字符出现频率相同，则哈夫曼编码一定会得到完全二叉树。

使用math.h或cmath头文件中的函数，表达式sin(90)的结果为1 。

在一个无向连通图中，从任意顶点开始进行深度优先遍历，最终得到的 DFS 生成树一定包含图中的所有顶点。

试题名称：拆分 时间限制：1.0 s　内存限制：512.0 MB 题目描述：小 A 想将正整数 n 拆分成若干个正整数之和，并最大化拆分后的正整数之积。小 A 希望你帮他计算出拆分后正整数之积的最大值。由于答案可能很大，你只需要求出答案对 10^9 取模的结果。 形式化地，n 的拆分是满足 a_1 + ⋯ + a_k = n 的若干个正整数 a_1, …, a_k，其中 1 ≤ k ≤ n。你需要求出 n 的所有拆分中 a_1 × ⋯ × a_n 的最大值对 10^9 取模的结果。 输入格式：第一行，一个正整数 t，表示数据组数。 对于每组数据：一行，一个整数 n，表示给定的正整数。 输出格式：对于每组数据：输出一行，一个整数，表示 n 拆分后正整数之积的最大值对 10^9 取模的结果。 输入样例1：3 5 8 100 输出样例1：6 18 755407364 数据范围：对于 40% 的测试点，保证 n ≤ 50。 对于所有测试点，保证 1 ≤ t ≤ 10^4，1 ≤ n ≤ 10^6。

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

试题名称：物流网络 时间限制：1.0 s　内存限制：512.0 MB 题目描述：一个物流网络由 n 个城市和 m 条双向公路组成。每条公路都有两个属性： 运输费用 w_i 景观评分 b_i 当一辆运输车从城市 1 运送货物到城市 n 时，需要支付经过道路的运输费用之和。 为了推广旅游线路，物流公司推出了一项优惠政策：在运输路径上，可以免除景观评分最高的那条公路的运输费用。如果有多条公路的景观评分同为最大值，则只免除其中一条的费用。 请你计算，从城市 1 到城市 n 的最小运输费用。 输入格式：第一行两个整数 n, m，分别表示城市数量和公路数量。 接下来 m 行，每行四个整数 u, v, w, b，表示存在一条连接城市 u 和城市 v 的双向公路，其中 w 为运输费用，b 为景观评分。 输出格式：输出一个整数，表示从城市 1 到城市 n 的最小费用。如果无法到达，输出 -1 。 输入样例1：3 3 1 2 10 5 2 3 20 6 1 3 100 1 输出样例1：0 样例解释1：路径 1 → 2 → 3：费用 10 + 20，最大美丽值 6（边 2 − 3）。免除 20，总花费 10。路径 1 → 3：费用 100，最大美丽值 1（边 1 − 3）。免除 100，总花费 0。最小费用为 0。 数据范围：1 ≤ n ≤ 5000，1 ≤ m ≤ 5000，1 ≤ w, b ≤ 10^9。

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