GESP 客观题评测系统

2026-06-Level-7

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

单选题

第 1 题（单选题，2 分）

下列 C++ 代码的输出结果是（）。

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    cout << (int)(sqrt(50) + log2(8));
    return 0;
}

正确答案B

解析详情

【答案】B

【考点】数学库函数与类型转换

【解析】 `sqrt(50)` 约为 7.071，`log2(8)=3`，两者之和约为 10.071。强制转换为 `int` 会截去小数部分，输出 10。

【易错点】 `(int)` 是向零截断，不是四舍五入。

第 2 题（单选题，2 分）

下列关于 <cmath> 或 <math.h> 中的数学库函数的说法，正确的是（）。

sqrt(49) 的返回值可以参与浮点运算。

log2(32) 的返回值类型为 int。

pow(2, 5) 的返回值类型一定为 int。

sin(90) 的参数 90 表示 90 度。

正确答案A

解析详情

【答案】A

【考点】cmath 数学库函数

【解析】 `sqrt` 返回浮点数，因此 `sqrt(49)` 的结果可以继续参与浮点运算。`log2` 和 `pow` 通常返回浮点类型；`sin` 的参数使用弧度而不是角度。

【易错点】不要根据参数是整数就推断数学函数的返回类型也是整数。

第 3 题（单选题，2 分）

下列关于 C++ 函数参数传递的说法，正确的是（）。

函数形参一定和实参使用同一块内存。

值传递时，在函数内修改形参一定会修改实参。

引用形参绑定到实参后，在函数内修改引用形参通常会影响实参。

指针形参不能用于修改实参指向的数据。

正确答案C

解析详情

【答案】C

【考点】函数参数传递

【解析】引用形参是实参的别名，函数内给引用形参赋值通常会直接改变实参。值传递会复制参数；指针形参虽然自身按值传递，但可通过解引用修改所指对象。

【易错点】区分“修改指针变量本身”和“修改指针指向的数据”。

第 4 题（单选题，2 分）

有5个字符，它们出现的次数分别为3、4、7、8、9。使用哈夫曼编码时，最小的带权路径长度WPL为（）。

正确答案D

解析详情

【答案】D

【考点】哈夫曼树与带权路径长度

【解析】按最小权值合并：3+4=7，7+7=14，8+9=17，最后 14+17=31。哈夫曼树的 WPL 等于各次合并权值之和，即 7+14+17+31=69。

【易错点】每次必须选择当前权值最小的两个结点，合并后还要把新权值放回集合。

第 5 题（单选题，2 分）

已知网格上每个网格点有一个数字，a[i][j] 表示第 i 行第 j 列处网格点上的数字。若 dp[i][j] 表示从网格左上角（第 0 行第 0 列）走到第 i 行第 j 列时能取得的最大数字和，且每次只能向右或向下移动。对于 i > 0 且 j > 0 的位置，正确的状态转移代码为（）。

dp[i][j] = a[i][j] + min(dp[i - 1][j], dp[i][j - 1])

dp[i][j] = max(dp[i - 1][j - 1], dp[i][j])

dp[i][j] = a[i][j] + max(dp[i - 1][j], dp[i][j - 1])

dp[i][j] = a[i][j] + dp[i - 1][j - 1]

正确答案C

解析详情

【答案】C

【考点】网格动态规划

【解析】到达 `(i,j)` 的最后一步只能来自上方 `(i-1,j)` 或左方 `(i,j-1)`。要求最大数字和，应选两者较大值再加当前格子的 `a[i][j]`，即选项 C。

【易错点】状态转移不要漏加当前格子的权值，也不能从左上角斜着转移。

第 6 题（单选题，2 分）

已知 f[0] = 0，f[1] = 2，并且对 i >= 2 有 f[i] = max(f[i - 1], f[i - 2] + a[i])。若 a[1 .. 5] = {2, 7, 9, 3, 1}，则 f[5] 的值为（）。

正确答案C

解析详情

【答案】C

【考点】动态规划递推

【解析】依次计算：`f[2]=max(2,0+7)=7`，`f[3]=max(7,2+9)=11`，`f[4]=max(11,7+3)=11`，`f[5]=max(11,11+1)=12`。

【易错点】递推中的 `a[i]` 与 `f[i-2]` 配对，不能把所有正数直接相加。

第 7 题（单选题，2 分）

下面代码是一维数组优化 0/1 背包的核心片段，其中 w[i] 表示第 i 件物品的重量，v[i] 表示第 i 件物品的价值。横线处应填入（）。

for (int i = 1; i <= n; i++) {
    for (int c = W; c >= w[i]; c--) {
        __________;
    }
}

dp[c] = max(dp[c], dp[c + w[i]] + v[i])

dp[c] = min(dp[c], dp[c - w[i]] + v[i])

dp[c] = dp[c - w[i]] + v[i]

dp[c] = max(dp[c], dp[c - w[i]] + v[i])

正确答案D

解析详情

【答案】D

【考点】0/1 背包一维优化

【解析】容量 `c` 从大到小枚举时，`dp[c-w[i]]` 仍是处理第 i 件物品前的状态，因此转移为 `dp[c]=max(dp[c],dp[c-w[i]]+v[i])`，保证每件物品最多使用一次。

【易错点】若容量正序枚举，本轮刚更新的状态可能被再次使用，会变成完全背包。

第 8 题（单选题，2 分）

下面程序片段主要体现的算法思想是（）。

void dfs(int x, int y) {
    vis[x][y] = true;
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (inside(nx, ny) && a[nx][ny] == 1 && !vis[nx][ny])
            dfs(nx, ny);
    }
}

泛洪算法

二分查找

贪心算法

归并排序

正确答案A

解析详情

【答案】A

【考点】泛洪算法

【解析】函数从一个格子出发，递归访问上下左右相连、值为 1 且未访问的格子，从而遍历整个连通区域，这正是 DFS 实现的泛洪算法。

【易错点】泛洪关注的是连通区域遍历，不是按大小有序查找或排序。

第 9 题（单选题，2 分）

下列关于排序稳定性的说法，正确的是（）。

冒泡排序在只交换相邻逆序元素时是稳定排序

选择排序一定是稳定排序

快速排序一定是稳定排序

稳定排序一定会改变相等元素的相对顺序

正确答案A

解析详情

【答案】A

【考点】排序稳定性

【解析】冒泡排序只交换相邻逆序元素时，相等元素不会互换先后位置，因此稳定。普通选择排序可能把被选中的最小元素跨过相等元素，所以不稳定；快速排序通常也不稳定。

【易错点】稳定排序保持相等关键字元素的原相对顺序，而不是改变它。

第 10 题（单选题，2 分）

无向图的边为 (1, 2) ， (1, 3) ， (2, 4) ， (3, 4) ， (4, 5) 。从顶点 1 开始进行 BFS，每轮根据出队顶点，将与其相邻顶点按编号从小到大入队，则顶点 4 第一次入队时，队列的状态为（）。

1, 2, 3, 4

2, 3, 4

3, 4

3, 4, 5

正确答案C

解析详情

【答案】C

【考点】广度优先搜索队列

【解析】初始队列 `[1]`。1 出队后按序加入 2、3，队列为 `[2,3]`；2 出队后，1 已访问，4 首次入队，此时队列为 `[3,4]`。

【易错点】题目问的是 4 刚入队后的状态，队首已经出队的 2 不应保留。

第 11 题（单选题，2 分）

一个长度为 11、下标为 0 到 10 的哈希表采用线性探测法处理冲突，哈希函数为 h(x) = x \% 11。依次插入 22、33、4、15、26，则 26 最终存放在下标（）。

正确答案D

解析详情

【答案】D

【考点】哈希表线性探测

【解析】 22 哈希到 0；33 也到 0，探测到 1；4 到 4；15 到 4，探测到 5；26 到 4，4、5 均占用，继续探测到 6。

【易错点】线性探测要从哈希位置开始逐格检查，不能只处理一次冲突。

第 12 题（单选题，2 分）

关于哈希表处理冲突的方法，下列说法正确的是（）。

线性探测法发生冲突后，只能放弃插入该元素。

链地址法可以把哈希到同一位置的多个元素组织在同一个桶中。

只要哈希表长度是素数，就一定不会发生冲突。

开放定址法查找元素时不需要考虑冲突位置。

正确答案B

解析详情

【答案】B

【考点】哈希冲突处理

【解析】链地址法为每个哈希位置维护一个桶，哈希值相同的多个元素可存入同一桶的链表或其他容器中。素数表长只能改善分布，不能保证无冲突。

【易错点】哈希函数把更大的键空间映射到有限槽位，冲突无法仅靠合理设计彻底消除。

第 13 题（单选题，2 分）

某算法需要枚举 n 个对象；对每个对象，还需要进行一次二分查找。若二分查找的对象规模也是 n，则该算法的时间复杂度通常为（）。

O(n)

O(n \log n)

O(n^2)

O(\log n)

正确答案B

解析详情

【答案】B

【考点】时间复杂度

【解析】外层枚举 n 个对象，共执行 n 次；每次二分查找耗时 `O(log n)`，相乘得到总复杂度 `O(n log n)`。

【易错点】嵌套操作的复杂度通常相乘，不是简单相加。

第 14 题（单选题，2 分）

在升序数组中用二分查找第一个大于等于 x 的位置。若当前中点 mid 满足 a[mid] < x，下一步应（）。

令闭区间右边界变为 mid - 1

令闭区间左边界变为 mid + 1

立即返回 mid

交换 a[mid] 与 x

正确答案B

解析详情

【答案】B

【考点】二分查找边界

【解析】当 `a[mid] < x` 时，`mid` 及其左侧元素都不可能是第一个大于等于 x 的位置，因此应令左边界为 `mid+1`，继续搜索右半区间。

【易错点】查找 lower_bound 时即使 `a[mid] >= x` 也不能立即返回，还要尝试向左缩小答案。

第 15 题（单选题，2 分）

在如下网格中，# 表示不能经过的格子，．表示可以经过的格子。从左上角走到右下角，每次只能向右或向下移动，不同路径共有（）条。

.....
.#.#.
.....
#.#..
.....

正确答案D

解析详情

【答案】D

【考点】网格路径动态规划

【解析】令每个可达格的路径数等于上方与左方路径数之和，障碍格为 0。逐行计算到最后一行得到 `0,1,1,3,8`，所以右下角共有 8 条路径。

【易错点】障碍格不能经过，且其路径数必须清零；只能从上方或左方转移。

判断题

第 1 题（判断题，2 分）

使用 cmath 或 math.h 中的三角函数时，角度参数默认采用角度制。

正确答案错误

解析详情

【答案】错误

【考点】三角函数参数单位

【解析】 C++ 数学库的 `sin`、`cos`、`tan` 等函数参数默认使用弧度。例如 90° 应传入 `π/2`，直接传 90 表示 90 弧度。

【易错点】角度制数值必须先换算为弧度。

第 2 题（判断题，2 分）

使用 cmath 或 math.h 中的 pow(2, 10) 计算 2^{10} 时，由于参数均为整型 int，返回值类型也为整型 int。

正确答案错误

解析详情

【答案】错误

【考点】pow 的返回类型

【解析】 `pow` 的常用重载返回浮点类型，`pow(2,10)` 不会因为两个实参写成整数就必然返回 `int`。需要整数时还应考虑类型转换和浮点误差。

【易错点】实参类型不能单独决定数学库函数一定返回整数。

第 3 题（判断题，2 分）

0/1 背包使用一维数组优化时，容量从小到大枚举也能保证每件物品最多被选一次。

正确答案错误

解析详情

【答案】错误

【考点】0/1 背包枚举顺序

【解析】一维 0/1 背包必须让容量从大到小枚举。若从小到大，本轮更新后的 `dp[c-w[i]]` 可能再次参与转移，使同一件物品被重复选取。

【易错点】正序容量适用于允许重复选取的完全背包。

第 4 题（判断题，2 分）

哈希表采用开放定址法时，即使哈希函数设计合理，也仍然可能发生冲突。

正确答案正确

解析详情

【答案】正确

【考点】哈希冲突

【解析】开放定址法用于解决冲突，并不消除冲突。不同键仍可能得到相同哈希位置，此时需按线性探测、二次探测等规则寻找其他槽位。

【易错点】哈希函数分布合理只能降低冲突概率，不能保证冲突为零。

第 5 题（判断题，2 分）

同一个图从同一个起点进行深度优先搜索，访问序列一定与邻接点的枚举顺序无关。

正确答案错误

解析详情

【答案】错误

【考点】深度优先搜索

【解析】当一个顶点有多个未访问邻接点时，DFS 会优先沿最先枚举的邻接点深入。因此改变邻接表顺序，访问序列可能随之改变。

【易错点】 DFS 的可达结果通常不变，但具体访问顺序并不唯一。

第 6 题（判断题，2 分）

泛洪算法可以用递归 DFS 实现，但地图很大时可能由于递归层数过深导致调用栈溢出等运行时错误。

正确答案正确

解析详情

【答案】正确

【考点】递归 DFS 的栈空间

【解析】递归 DFS 的调用深度最坏可达到连通区域的格子数。地图很大且搜索路径很深时，调用栈可能耗尽并发生栈溢出，可改用显式栈或队列。

【易错点】时间复杂度可接受不代表递归栈空间一定安全。

第 7 题（判断题，2 分）

哈夫曼树中不存在度为1的结点。

正确答案正确

解析详情

【答案】正确

【考点】哈夫曼树结构

【解析】构造哈夫曼树时，每次把两个结点合并为一个新父结点，因此每个内部结点恰有两个孩子；叶结点度为 0，不会出现只有一个孩子的内部结点。

【易错点】这里的“度”指孩子数，不是图论中无向结点的关联边数。

第 8 题（判断题，2 分）

冒泡排序的常见实现是稳定排序，选择排序也是。

正确答案错误

解析详情

【答案】错误

【考点】排序稳定性

【解析】常见冒泡排序只交换相邻逆序元素，因而稳定；普通选择排序会把最小元素与当前位置直接交换，可能跨过相等元素，因而通常不稳定。题目把两者都说成稳定是错误的。

【易错点】不能因为排序结果相同就忽略相等元素原有的先后次序。

第 9 题（判断题，2 分）

在无权图中从起点执行 BFS 时，某个顶点第一次被访问到的层数等于起点到该顶点经过的最少边数。

正确答案正确

解析详情

【答案】正确

【考点】BFS 最短路

【解析】 BFS 按距离起点的层次逐层扩展。在无权图中，每条边代价相同，顶点第一次被访问时不可能再由后续层得到更少边数，因此该层数就是最短边数。

【易错点】这一结论针对无权图或等权图；带不同边权时不能直接套用。

第 10 题（判断题，2 分）

在二维动态规划中，状态 dp[i][j] 的计算常常依赖其他状态，这些状态的计算必须在完成 dp[i][j] 的计算前完成。

正确答案正确

解析详情

【答案】正确

【考点】动态规划计算顺序

【解析】动态规划的转移必须读取已计算好的依赖状态。例如网格 DP 常按从上到下、从左到右计算，使 `dp[i-1][j]` 和 `dp[i][j-1]` 先于 `dp[i][j]` 得到。

【易错点】若遍历顺序违反依赖关系，读到的可能是未初始化或旧状态。