GESP 202606 C++ 七级 试题

一、 单项选择题（共 15 题，每题 2 分，共计 30 分）

1. [2 分] 下列 C++ 代码的输出结果是（ ）。

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

（ {{ select(1) }} ）

• 9
• 10
• 11
• 12

2. [2 分] 下列关于 <cmath> 或 <math.h> 中的数学函数的说法，正确的是（ ）。 （ {{ select(2) }} ）

• sqrt(49) 的返回值可以参与浮点运算。
• log2(32) 的返回值类型为 int。
• pow(2, 5) 的返回值类型一定为 int。
• sin(90) 的参数 90 表示 90 度。

3. [2 分] 下列关于 C++ 函数参数传递的说法，正确的是（ ）。 （ {{ select(3) }} ）

• 函数形参一定和实参使用同一块内存。
• 值传递时，在函数内修改形参一定会修改实参。
• 引用形参绑定到实参后，在函数内修改引用形参通常会修改实参。
• 指针形参不能用于修改实参指向的数据。

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

• 62
• 64
• 67
• 69

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

• dp[i][j] = a[i][j] + min(dp[i - 1][j], dp[i][j - 1])
• dp[i][j] = max(dp[i - 1][i - 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]

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

• 10
• 11
• 12
• 13

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--) {
        __________;
    }
}

（ {{ select(7) }} ）

• 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])

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);
    }
}

（ {{ select(8) }} ）

• 泛洪算法
• 二分查找
• 贪心算法
• 归并排序

9. [2 分] 下列关于排序稳定性的说法，正确的是（ ）。 （ {{ select(9) }} ）

• 冒泡排序在只交换相邻逆序元素时是稳定排序
• 选择排序一定是稳定排序
• 快速排序一定是稳定排序
• 稳定排序一定会改变相等元素的相对顺序

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

• 1, 2, 3, 4
• 2, 3, 4
• 3, 4
• 3, 4, 5

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

• 0
• 4
• 5
• 6

12. [2 分] 关于哈希表处理冲突的方法，下列说法正确的是（ ）。 （ {{ select(12) }} ）

• 线性探测法发生冲突后，只能放弃插入该元素。
• 链地址法可以把哈希到同一位置的多个元素组织在同一个桶中。
• 只要哈希表长度是素数，就一定不会发生冲突。
• 开放定址法查找元素时不需要考虑冲突位置。

13. [2 分] 某算法需要枚举 $n$ 个对象；对每个对象，还需要进行一次二分查找。若二分查找的对象规模也是 $n$，则该算法的时间复杂度通常为（ ）。 （ {{ select(13) }} ）

• $O(n)$
• $O(n \log n)$
• $O(n^2)$
• $O(\log n)$

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

• 令闭区间右边界变为 mid - 1
• 令闭区间左边界变为 mid + 1
• 立即返回 mid
• 交换 a[mid] 与 $x$

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

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

（ {{ select(15) }} ）

• 5
• 6
• 7
• 8

---

二、 判断题（每题 2 分，共 20 分）

16. [2 分] 使用 <cmath> 或 <math.h> 中的三角函数时，角度参数默认采用角度制。 （ {{ select(16) }} ）

• 正确
• 错误

17. [2 分] 使用 <cmath> 或 <math.h> 中的 pow(2, 10) 计算 $2^{10}$ 时，由于参数均为整型 int，返回值类型也为整型 int。 （ {{ select(17) }} ）

• 正确
• 错误

18. [2 分] 0/1 背包使用一维数组优化时，容量从小到大枚举也能保证每件物品最多被选一次。 （ {{ select(18) }} ）

• 正确
• 错误

19. [2 分] 哈希表采用开放定址法时，即使哈希函数设计合理，也仍然可能发生冲突。 （ {{ select(19) }} ）

• 正确
• 错误

20. [2 分] 同一个图从同一个起点进行深度优先搜索，访问序列一定与邻接点的枚举顺序无关。 （ {{ select(20) }} ）

• 正确
• 错误

21. [2 分] 泛洪算法可以用递归 DFS 实现，但地图很大时可能由于递归层数过深导致调用栈溢出等运行时错误。 （ {{ select(21) }} ）

• 正确
• 错误

22. [2 分] 哈夫曼树中不存在度为 1 的结点。 （ {{ select(22) }} ）

• 正确
• 错误

23. [2 分] 冒泡排序的常见实现是稳定排序，选择排序也是。 （ {{ select(23) }} ）

• 正确
• 错误

24. [2 分] 在无向图中从起点执行 BFS 时，某个顶点第一次被访问到的层数等于起点到该顶点经过的最少边数。 （ {{ select(24) }} ）

• 正确
• 错误

25. [2 分] 在二维动态规划中，状态 dp[i][j] 的计算常常依赖其他状态，这些状态的计算必须在完成 dp[i][j] 的计算前完成。 （ {{ select(25) }} ）

• 正确
• 错误