GESP 七级 · 2026 真题

假设⼀个算法时间复杂度的递推式是 $T(n) = 2T(n-1)+1$，且 $T(0) =1$，那么这个算法的时间复杂度是（）。

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

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

对于⼀棵包含 $n$ 个顶点（$n \ge 2$）的树，其所有顶点的度数之和必定等于（ ）

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

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

下⾯程序的运⾏结果为（ ）。

01#include <iostream>
02#include <algorithm>
03
04bool check(int n, int a[], int k, int dist) {
05    int cnt = 1;
06    int last = a[0];
07
08    for (int i = 1; i < n; i++) {
09        if (a[i] - last >= dist) {
10            cnt++;
11            last = a[i];
12        }
13    }
14
15    return cnt >= k;
16}
17
18int solve(int n, int a[], int k) {
19    std::sort(a, a + n);
20
21    int l = 0;
22    int r = a[n - 1] - a[0];
23
24    while (l < r) {
25        int mid = (l + r + 1) / 2;
26
27        if (check(n, a, k, mid))
28            l = mid;
29        else
30            r = mid - 1;
31    }
32
33    return l;
34}
35
36int main() {
37    int a[] = {1, 2, 8, 4, 9};
38    int n = 5;
39    int k = 3;
40
41    std::cout << solve(n, a, k) << std::endl;
42    
43    return 0;
44}

下⾯程序的时间复杂度是（ ），假设数组 a 的值域范围是 D。

01#include <iostream>
02#include <algorithm>
03bool check(int n, int a[], int k, int dist) {
04    int cnt = 1;
05    int last = a[0];
06    for (int i = 1; i < n; i++) {
07        if (a[i] - last >= dist) {
08            cnt++;
09            last = a[i];
10        }
11    }
12    return cnt >= k;
13}
14int solve(int n, int a[], int k) {
15    std::sort(a, a + n);
16    int l = 0;
17    int r = a[n - 1] - a[0];
18    while (l < r) {
19        int mid = (l + r + 1) / 2;
20        if (check(n, a, k, mid))
21            l = mid;
22        else
23            r = mid - 1;
24    }
25    return l;
26}
27int main() {
28    int a[] = {1, 2, 8, 4, 9};
29    int n = 5;
30    int k = 3;
31    std::cout << solve(n, a, k) << std::endl;
32    return 0;
33}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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