GESP 客观题评测系统

2025-12-Level-7

试卷解析总览，可直接查看每题答案与解析。

单选题（每题 2 分）

第 1 题（单选题）

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

形参是函数定义时所指定的变量，它只在函数内部有效。

在函数内部，可以修改传入的形参的值，即使该形参是一个常量引用。

实参和形参的类型必须完全一致，否则会导致编译错误。

使用指针作为形参时，形参是指向实参的地址，因此对该指针赋值会影响实参。

正确答案A

解析详情

【答案】A

【考点】函数形参与实参；常量引用；作用域

【解析】形参是在函数定义处声明的变量，默认只在该函数体内有效，所以 A 正确。 B 错在常量引用不能通过该引用修改对象；C 错在实参和形参不必完全同型，存在隐式类型转换时仍可调用；D 错在把指针形参重新赋值只会改变形参本身，不会改掉实参保存的地址。

【易错点】容易把“修改指针指向的内容”和“修改指针变量本身”混为一谈。

第 2 题（单选题）

已知三个序列：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}。以下哪个序列是它们的最长公共子序列（）。

{1, 8, 5, 6}

{1, 5, 6, 7}

{1, 8, 6}

{1, 5, 7, 4}

正确答案A

解析详情

【答案】A

【考点】最长公共子序列；序列匹配；相对顺序

【解析】公共子序列要求三个序列中都按相同先后顺序出现。A 中的 1,8,5,6 在 s1、s2、s3 中都能找到，长度为 4。 B 虽然在 s2、s3 中可行，但在 s1 中 7 出现在 6 之后，不能形成 1,5,6,7；D 在 s2 中 4 出现在 7 之前，也不满足顺序。既然 A 已经达到长度 4，而其余可行候选没有更长，所以答案是 A。

【易错点】容易只看元素是否都出现，而漏掉“相对顺序必须一致”这个条件。

第 3 题（单选题）

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

正确答案D

解析详情

【答案】D

【考点】哈希函数；开放寻址；线性探测

【解析】先算哈希地址：h(1)=2，h(3)=1，h(5)=8。h(7)=1，与 3 冲突，再探测 2 也被 1 占用，所以 7 放到 3。接着 h(9)=(81+9) mod 11=2，2 已占、3 已占，再往后探测到 4 为空，因此 9 最终存入地址 4。

【易错点】容易算出初始哈希值后就停下，忘了按题意继续顺序探测空位。

第 4 题（单选题）

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

在解决0/1背包问题时，使用贪心算法可以保证找到最优解，因为物品只能放入一次。

0/1背包是P问题（多项式时间可解问题），它可以在O(nW)的时间复杂度内解决。

0/1背包问题中，动态规划解法的空间复杂度为O(nW)，但可以通过滚动数组技巧将空间复杂度优化到O(W)。

0/1背包问题中，每个物品只能选择一次，并且子问题之间是独立的，无法重用计算结果。

正确答案C

解析详情

【答案】C

【考点】0/1背包；动态规划；滚动数组优化

【解析】 0/1 背包的经典状态转移是 dp[i][j]，时间复杂度为 O(nW)，空间复杂度为 O(nW)。因为第 i 行只依赖第 i-1 行，可以把二维数组压成一维滚动数组，把空间降到 O(W)，所以 C 正确。 A 错在 0/1 背包不能靠贪心保证最优；B 错在 O(nW) 是伪多项式时间，不能据此说 0/1 背包是通常意义上的多项式时间可解；D 错在子问题明显可以复用，这正是动态规划成立的原因。

【易错点】容易把“状态数按 W 计”误当成“对输入长度的多项式时间”。

第 5 题（单选题）

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

正确答案B

解析详情

【答案】B

【考点】完全二叉树；结点数量；树的层数

【解析】深度为 6 且是完全二叉树时，前 5 层必须全部填满，第 6 层至少有 1 个结点。前 5 层共有 1+2+4+8+16=31 个结点，再加上第 6 层最少 1 个，总数最少为 32，所以选 B。

【易错点】容易把“完全二叉树”误算成“满二叉树”，直接写成 63。

第 6 题（单选题）

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

D E B F H J I G C A 是它的后序遍历序列。

A B C D E F G H I J 是它的广度优先遍历序列。

A B D E C F G H I J 是它的先序遍历序列。

D B E A F C H G J I 是它的中序遍历序列。

正确答案D

解析详情

【答案】D

【考点】二叉树遍历；先序中序后序；层序遍历

【解析】由图可得这棵树的结构为 A 的左子树是 B(D,E)，右子树是 C(F,G(H,I(J)))。按此结构计算：后序遍历为 D E B F H J I G C A，先序遍历为 A B D E C F G H I J，层序遍历为 A B C D E F G H I J，前三项都对。中序遍历应为 D B E A F C H G I J，而不是 D B E A F C H G J I，所以错误项是 D。

【易错点】容易把结点 I 和 J 的父子关系看反，导致中序末尾顺序写错。

第 7 题（单选题）

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

#include <iostream>

int query(int n, int *a, int x) {
    int l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    if (l == n) return -1;
    return l;
}

int main() {
    int n = 10;
    int x = 3;
    int num[] = {1, 2, 2, 3, 3, 4, 5, 5, 6, 7};
    std::cout << query(n, num, x) << "\n";
    return 0;
}

正确答案B

解析详情

【答案】B

【考点】二分查找；lower_bound；数组下标

【解析】这个 query 函数寻找的是数组中第一个大于等于 x 的位置。初始 l=0,r=10，mid=5 时 a[5]=4>=3，所以 r=5；mid=2 时 a[2]=2<3，所以 l=3；mid=4 时 a[4]=3>=3，所以 r=4；mid=3 时 a[3]=3>=3，所以 r=3。循环结束时 l=r=3，函数返回 3，因此输出为 3，对应 B。

【易错点】容易把结果当成“第几个 3”，却忘了函数返回的是从 0 开始的下标。

第 8 题（单选题）

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

#include <iostream>

int query(int n, int *a, int x) {
    int l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    if (l == n) return -1;
    return l;
}

int main() {
    int n = 10;
    int x = 3;
    int num[] = {1, 2, 2, 3, 3, 4, 5, 5, 6, 7};

    std::cout << query(n, num, x) << "\n";
    return 0;
}

O(1)

O(\log n)

O(n)

O(n \log n)

正确答案B

解析详情

【答案】B

【考点】时间复杂度；二分查找；对数级算法

【解析】 while 循环每执行一次，搜索区间 [l,r) 都会缩小到原来的一半左右。区间长度从 n 逐步减到 0，需要的迭代次数约为 log n。循环体内部只有常数次比较和赋值，因此总时间复杂度是 O(log n)，选 B。

【易错点】容易只看到 while 循环就误判成 O(n)，没有注意区间是按二分速度缩小的。

第 9 题（单选题）

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

正确答案B

解析详情

【答案】B

【考点】哈夫曼树；带权路径长度；贪心合并

【解析】每次取当前最小的两个权值合并：2 和 2 合并得 4，贡献 4；3 和 3 合并得 6，贡献 6。再把 4 和 5 合并得 9，贡献 9；最后 6 和 9 合并得 15，贡献 15。总 WPL 为 4+6+9+15=34，所以选 B。

【易错点】容易只把最后一层的结果相加，漏掉每一次合并产生的代价都要计入 WPL。

第 10 题（单选题）

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

#include <iostream>
using namespace std;
int f(int n) {
    if (n <= 2) return n * 2;
    return f(n - 1) + f(n - 2);
}
int main() {
    cout << f(5) << endl;
    return 0;
}

正确答案B

解析详情

【答案】B

【考点】递归函数；递推计算；程序运行结果

【解析】先算边界：f(1)=2，f(2)=4。 f(3)=f(2)+f(1)=4+2=6，f(4)=f(3)+f(2)=6+4=10，f(5)=f(4)+f(3)=10+6=16，所以程序输出 16。因此正确选项是 B。

【易错点】容易把 n<=2 的返回值看成 n，忽略了这里返回的是 n*2。

第 11 题（单选题）

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

正确答案C

解析详情

【答案】C

【考点】无向图度数；握手定理；图的基本性质

【解析】无向图所有顶点度数之和等于边数的两倍，所以总度数为 2×36=72。每个顶点度数都为 4，设顶点数为 V，则 4V=72，解得 V=18，因此选 C。

【易错点】容易忘记无向边会给两个端点各贡献 1 次度数。

第 12 题（单选题）

下面关于二叉树的说法正确的是（）。

任意二叉树的中序遍历与后序遍历必定不相同。

对任意二叉树，若已知先序遍历与后序遍历，则该二叉树唯一确定。

若二叉树有

n

个结点，根节点高度为 1，则其高度满足：

\left|\log_2(n+1)\right| \leq h \leq n

。

在二叉树的先序遍历中，根后紧跟的结点一定是根的左孩子。

正确答案C

解析详情

【答案】C

【考点】二叉树性质；遍历序列；树高范围

【解析】二叉树有 n 个结点时，高度最小出现在尽量“满”的情形，此时 h 约为 log2(n+1)；高度最大出现在退化成链时，此时 h=n，所以 C 正确。 A 错，因为单结点树的中序和后序都只有同一个结点；B 错，因为只给先序和后序时一般不能唯一确定二叉树；D 错，如果根没有左孩子，先序遍历中根后面紧跟的可能是右孩子。

【易错点】容易把“某些特殊二叉树可唯一确定”误当成“任意二叉树都能唯一确定”。

第 13 题（单选题）

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

O(n\sqrt{n})

O(n\sqrt{n}\log n)

O(n^2)

O(n^2\log n)

正确答案B

解析详情

【答案】B

【考点】主定理；递归时间复杂度；分治算法

【解析】这里 a=8，b=4，所以 n^{log_b a}=n^{log_4 8}=n^{3/2}=n\sqrt{n}。递推中的非递归部分 f(n)=n\sqrt{n}，恰好与 n^{log_b a} 同阶，属于主定理第二种情形，因此 T(n)=Θ(n\sqrt{n}\log n)。对应选项 B。

【易错点】容易把 n^{log_4 8} 算成 n^2，忽略了 log_4 8=3/2。

第 14 题（单选题）

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

1, 5, 6, 3, 2, 8, 9, 4, 7

1, 5, 8, 9, 7, 4, 6, 3, 2

3, 2, 1, 4, 7, 6, 9, 5, 8

2, 5, 6, 3, 8, 7, 9, 4, 1

正确答案B

解析详情

【答案】B

【考点】深度优先搜索；图遍历；回溯顺序

【解析】只要存在一种邻接点访问顺序能得到该序列，这个选项就“可能”是 DFS 序列。从 1 出发，依次走 1→5→8→9，9 无新点后回溯到 8；再访问 7、4，继续回溯到 5；然后访问 6，再到 3，最后到 2，首次访问顺序正好是 1,5,8,9,7,4,6,3,2，因此 B 可以作为一次深度优先遍历序列。

【易错点】容易按“边经过顺序”去读图，而不是按“首次到达顶点的顺序”记录 DFS 序列。

第 15 题（单选题）

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

正确答案C

解析详情

【答案】C

【考点】强连通分量；有向图；缩点分析

【解析】按互相可达关系分组：1 和 2 可以互达，构成一个强连通分量；4、5、7、8 之间也能互相到达，构成一个分量。右侧 6、9、10、11 之间存在回路 6→10→11→6，且 10→9、9→11，所以这四个点互相可达；3 只能走向右侧却回不到自身，单独成分量；12 也只能走向 11 或 9，无法被它们返回，所以也单独成分量。共得到 {1,2}、{3}、{4,5,7,8}、{6,9,10,11}、{12} 五个强连通分量，因此选 C。

【易错点】容易只看局部回路，把能通过多步互达的 9、10、11、6 错拆成多个分量。

判断题（每题 2 分）

第 1 题（判断题）

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

正确答案错误

解析详情

【答案】错误

【考点】位运算；C++表达式求值

【解析】在 C++ 里 `^` 表示按位异或，不表示乘方。 3 的二进制是 11，2 的二进制是 10，异或结果是 01，也就是整数 1，所以题干中“值为 9”的说法错误。表达式结果类型仍是整型，但结论整体为错误。

【易错点】容易把数学里的幂运算符号直接套到 C++ 的 `^` 上。

第 2 题（判断题）

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

正确答案错误

解析详情

【答案】错误

【考点】三角函数；弧度制；cmath 库

【解析】 `cmath` 中的 `sin` 函数参数按弧度解释，不按角度解释。因此 `sin(90)` 计算的是 90 弧度的正弦值，结果大约是 0.894，不接近 1；只有 `sin(π/2)` 才等于 1，所以题干说法错误。

【易错点】容易把程序库函数默认的弧度制误当成角度制。

第 3 题（判断题）

使用 strcmp("10", "9") 比较两个字符串，返回值大于0，说明 "10" 比 "9" 大。

正确答案错误

解析详情

【答案】错误

【考点】字符串比较；strcmp；字典序

【解析】 `strcmp` 按字符的字典序逐个比较，而不是把字符串先转成整数。比较 "10" 和 "9" 时，先比较首字符 `1` 和 `9`，因为 `1` 的编码更小，所以返回值小于 0，表示 "10" 在字典序上比 "9" 小。题干说返回值大于 0，因此错误。

【易错点】容易把字符串比较误认为数值大小比较。

第 4 题（判断题）

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

正确答案正确

解析详情

【答案】正确

【考点】排序稳定性；选择排序；冒泡排序

【解析】选择排序会把后面的最小元素直接交换到前面，这个交换可能改变相同关键字元素的先后顺序，所以它不稳定。冒泡排序只交换相邻且逆序的元素，若实现时相等元素不交换，则相同关键字的相对顺序保持不变，因此它是稳定排序。题干判断正确。

【易错点】容易只记算法名字，不区分“能否保持相同元素原有顺序”这一稳定性定义。

第 5 题（判断题）

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

正确答案正确

解析详情

【答案】正确

【考点】最长公共子序列；动态规划；空间优化

【解析】 LCS 的二维状态转移通常是 dp[i][j]，其中第 i 行只依赖上一行和当前行左边的状态。因此没有必要保留完整的 n×n 表，只保留两行或一行滚动数组就能完成转移，空间复杂度可以从 O(n^2) 降到 O(n)。所以题干说法正确。

【易错点】容易因为看到二维状态表，就误以为空间复杂度一定不能压缩。

第 6 题（判断题）

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

正确答案正确

解析详情

【答案】正确

【考点】无向图度数；握手定理

【解析】无向图中的每一条边都会分别给它连接的两个端点各贡献 1 次度数。所以把所有顶点度数加起来时，每条边都会被计算两次，总和恰好等于边数的两倍，题干说法正确。

【易错点】容易把“边数”与“度数和”直接对应，漏掉每条边对应两个端点。

第 7 题（判断题）

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

正确答案错误

解析详情

【答案】错误

【考点】图的存储；广度优先搜索；时间复杂度

【解析】若用邻接矩阵存图，BFS 访问某个顶点时需要扫描这一整行，检查它与所有 V 个顶点是否相邻。完整遍历最多会对每个顶点都做一次这样的扫描，所以总复杂度是 O(V^2)，不是邻接表情形下的 O(V+E)。因此题干错误。

【易错点】容易把邻接表的复杂度公式直接套到邻接矩阵上。

第 8 题（判断题）

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

正确答案正确

解析详情

【答案】正确

【考点】泛洪算法；广度优先搜索；深度优先搜索

【解析】 flood fill 的核心是从起点出发，不断扩展到所有满足条件的相邻位置。这个扩展过程既可以用队列按层推进形成 BFS，也可以用递归或显式栈不断深入形成 DFS，两种方法都能覆盖连通区域，所以题干正确。

【易错点】容易把某一种常见实现当成唯一实现方式。

第 9 题（判断题）

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

正确答案正确

解析详情

【答案】正确

【考点】哈希冲突处理；链地址法；最坏时间复杂度

【解析】链地址法把映射到同一槽位的元素串成链表或其他线性结构。如果所有元素都落到同一个槽位，查找最坏情况下需要顺着整条链比较到最后一个元素，共比较 n 次量级，所以最坏时间复杂度是 O(n)。题干说法正确。

【易错点】容易只记住哈希表“平均很快”，忽略严重冲突时的最坏情况。

第 10 题（判断题）

一个包含 V 个顶点的连通无向图，其任何一棵生成树都恰好包含 V - 1 条边。

正确答案正确

解析详情

【答案】正确

【考点】生成树；连通无向图；树的边数

【解析】生成树要包含原图全部 V 个顶点，同时保持连通且不能有环。一棵有 V 个顶点的树必有 V-1 条边；反过来，少一条就不连通，多一条就会成环，所以任何连通无向图的生成树都恰好有 V-1 条边。题干正确。

【易错点】容易把“原图边数很多”误认为生成树也会保留很多边。