GESP 七级 · 2025 真题

下⾯关于C++中形参、实参和定义域的说法中，正确的⼀项是（ ）。

已知三个序列：s1={3，1，8，2，5，6，7，4}，s2={1，5，1，8，6，4，7，5，6}，s3={1，8，3，5，7，6，2，4}。以下哪个序列是它们的最长公共子序列()。

现有一个地址区间为 $0\sim10$ 的哈希表，当出现冲突情况，会往后找第一个空的地址存储(到 $10$ 冲突了就从 $0$ 开始往后)，现在要依次存储 $(1,3,5,7,9)$，哈希函数为 $h(x)=(x^2+x) \bmod 11$。其中 $9$ 存储在哈希表哪个地址中( )。

在 $0/1$ 背包问题中，给定一组物品，每个物品有一个重量和价值，背包的容量有限。假设背包的最大容量为 $W$ ，物品的数量为 $n$ ，其中第 $i$ 个物品的重量为 $w[i]$，价值为 $v[i]$。以下关于 $0/1$ 背包问题的描述，正确的是()。

⼀棵深度为 $6$（根节点深度为 $1$ ）的完全⼆叉树，节点总数最少有（ ）。

对于如下二叉树，下面关于访问的顺序说法错误的是（ ）。

下面程序的运行结果为（ ）。

01++
02#include <iostream>
03
04int query(int n, int *a, int x) {
05    int l = 0, r = n;
06    while (l < r) {
07        int mid = l + (r - l) / 2;
08        if (a[mid] >= x) r = mid;
09        else l = mid + 1;
10    }
11
12    if (l == n) return -1;
13    return l;
14}
15
16int main() {
17    int n = 10;
18    int x = 3;
19    int num[] = {1, 2, 2, 3, 3, 4, 5, 5, 6, 7};
20    
21    std::cout << query(n, num, x) << "\n";
22    return 0;
23}

下面程序中，函数 query 的时间复杂度是（ ）。

01++
02#include <iostream>
03
04int query(int n, int *a, int x) {
05    int l = 0, r = n;
06    while (l < r) {
07        int mid = l + (r - l) / 2;
08        if (a[mid] >= x) r = mid;
09        else l = mid + 1;
10    }
11
12    if (l == n) return -1;
13    return l;
14}
15
16int main() {
17    int n = 10;
18    int x = 3;
19    int num[] = {1, 2, 2, 3, 3, 4, 5, 5, 6, 7};
20    
21    std::cout << query(n, num, x) << "\n";
22    return 0;
23}

有 $5$ 个字符，它们出现的次数分别为 $2$ 次、$2$ 次、$3$ 次、$3$ 次、$5$ 次。现在要⽤哈夫曼编码的⽅式来为这些字符进⾏编码，最⼩加权路径长度 $WPL$（每个字符的出现次数 $\times$ 它的编码长度，再把每个字符结果加起来）的值为（ ）。

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

01++
02#include <iostream>
03using namespace std;
04int f(int n) {
05    if (n <= 2) return n * 2;
06    return f(n - 1) + f(n - 2);
07}
08int main() {
09    cout << f(5) << endl;
10    return 0;
11}

⼀个简单⽆向图 $G$ 有 $36$ 条边，且每个顶点的度数都为 $4$，则图 $G$ 的顶点个数为（ ）。

下⾯关于⼆叉树的说法正确的是（ ）。

假设⼀个算法时间复杂度的递推式是 $T(n) = 8T(\frac{n}{4}) + n\sqrt{n}$ ($n$ 为正整数)，和 $T(0)=1$ ，那么这个算法的时间复杂度是（ ）。

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

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

C++语⾔中，表达式 3 ^ 2 的结果类型为 int，值为 9。

使⽤ cmath 头⽂件中的正弦函数，表达式 sin(90) 的结果类型为 double，值约为 $1.0$。

使⽤ strcmp("10", "9") ⽐较两个字符串，返回值⼤于 $0$，说明 "10" ⽐ "9" ⼤。

选择排序是⼀种不稳定的排序算法，⽽冒泡排序是⼀种稳定的排序算法。

求两个长度为 $n$ 序列的最长公共⼦序列（LCS）长度时，可以使⽤滚动数组将空间复杂度从 $O(n^2)$ 优化到 $O(n)$ 。

在⽆向图中，所有顶点的度数之和等于边数的两倍。

使⽤邻接矩阵存储⼀个有 $V$ 个顶点、$E$ 条边的图，对该图进⾏⼀次完整的 $BFS$ 遍历，时间复杂度为 $O(V+E)$ 。

在图像处理或游戏开发中，泛洪（flood fill）算法既可以⽤BFS实现，也可以⽤DFS实现。

使⽤链地址法处理冲突的哈希表，当所有元素都映射到同⼀个槽位时，查找操作的最坏时间复杂度为 $O(n)$，其中 $n$ 为元素个数。

⼀个包含 $V$ 个顶点的连通⽆向图，其任何⼀棵⽣成树都恰好包含 $V-1$ 条边。