5622：[GESP202609七级] 客观题
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：文本裁判
金币值：
命题人：
提交：0
解决：0
题目描述
## 一、单选题（每题 2 分，共 30 分）
**第 1 题** 下列 `C++` 代码的输出结果是（ ）
```cpp
01 #include
02 using namespace std;
03 int main() {
04 int a = 5, b = 3;
05 cout << (a & b) + (a | b) << endl;
06 return 0;
07 }
```
- $6$
- $7$
- $8$
- $9$
**第 2 题** 使用 `cmath` 或 `math.h` 中的数学库函数，下列说法中正确的是（ ）
- `pow(2, 3)` 的返回值类型为 `int`
- `sin(30)` 的参数 `30` 表示 $30$ 度
- `sqrt(4)` 的返回值类型为 `int`
- `log(1)` 的返回值为 `0.0`，且类型为 `double`
**第 3 题** 有 $4$ 个字符，出现次数分别为 $1$、$2$、$3$、$4$。构造哈夫曼树后，出现次数为 $1$ 的字符的哈夫曼编码长度为（ ）
- $1$
- $2$
- $3$
- $4$
**第 4 题** 从 $4 \times 5$ 个点连接成的网格的左上角走到右下角，每次只能向右或向下移动，不同的路径共有（ ）条。
- $20$
- $35$
- $70$
- $126$
**第 5 题** 在含有 $n$ 个结点的二叉排序树中查找一个元素，平均时间复杂度和最坏时间复杂度分别为（ ）
- $O(\log n)$、$O(n)$
- $O(n)$、$O(\log n)$
- $O(\log n)$、$O(\log n)$
- $O(1)$、$O(n)$
**第 6 题** 有 $4$ 堆石子，数量分别为 $1$、$2$、$3$、$4$。每次可以合并相邻两堆，合并代价为两堆石子数之和。将所有石子合并成一堆的最小总代价为（ ）
- $17$
- $19$
- $20$
- $23$
**第 7 题** 在无权图中，使用 $BFS$ 从起点开始遍历，并在访问由结点 $u$ 扩展的相邻结点 $v$ 时记录 $dist[v] = dist[u] + 1$，且起点的 $dist$ 为 $0$，则最终 $dist[v]$ 表示的是（ ）
- 起点到结点 $v$ 的最少边数
- 结点 $v$ 的度数
- 从起点到结点 $v$ 的路径上经过的最大边权
- 包含结点 $v$ 的连通块大小
**第 8 题** 在二维网格上实现泛洪填充时，为了防止递归层数过深，最适合的非递归实现方式是（ ）
- 使用哈希表记录每个格子被访问的次数
- 使用快速排序预处理网格
- 使用二分查找定位边界
- 使用队列实现 `BFS` 或使用显式栈模拟 `DFS`
**第 9 题** 关于哈希表，下列说法正确的是（ ）
- 只要哈希函数选择合适，就可以完全避免冲突
- 在链地址法中，查找一个元素的时间复杂度一定为 $O(1)$
- 开放定址法发生冲突后，会在表内寻找下一个可用位置
- 哈希表的查找速度与表中元素个数无关
**第 10 题** 下列 C++ 代码的输出结果是（ ）
```cpp
01 #include
02 using namespace std;
03
04 void inc(int &x) {
05 x++;
06 }
07 int main() {
08 int a = 3;
09 inc(a);
10 cout << a;
11 return 0;
12 }
```
- $3$
- $4$
- $5$
- 编译错误
**第 11 题** 用动态规划求两个序列 $s_1$ 和 $s_2$ 的最长公共子序列长度，若 `dp[i][j]` 表示 $s_1$ 前 $i$ 个元素与 $s_2$ 前 $j$ 个元素的 LCS 长度。当 $s_1[i-1] = s_2[j-1]$ 时，正确的状态转移是（ ）
- `dp[i][j] = dp[i - 1][j - 1] + 1`
- `dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])`
- `dp[i][j] = dp[i - 1][j] + 1`
- `dp[i][j] = dp[i][j - 1]`
**第 12 题** 下列代码是一维数组优化 `0/1` 背包的核心片段，执行后 `dp[8]` 的输出结果是（ ）
```cpp
01 #include
02 #include
03 using namespace std;
04 int main() {
05 int w = 3, v = 5, W = 8;
06 int dp[9] = {0};
07 for (int c = W; c >= w; c--)
08 dp[c] = max(dp[c], dp[c - w] + v);
09 cout << dp[8] << endl;
10 return 0;
11 }
```
- $0$
- $1$
- $3$
- $5$
**第 13 题** 若要求排序后相等元素的相对顺序保持不变，下列排序算法中最不适宜使用的是（ ）
- 冒泡排序
- 插入排序
- 归并排序
- 快速排序
**第 14 题** 下列代码片段的时间复杂度为（ ）
```cpp
01 long long s = 0;
02 for (int i = 1; i <= n; i++)
03 for (int j = 1; j <= n; j += i)
04 s += i + j;
```
- $O(n)$
- $O(n\log n)$
- $O(n^2)$
- $O(n\sqrt{n})$
**第 15 题** 已知 `int a[6] = {1, 3, 5, 7, 9, 11}; int *p = a + 1;`，则表达式 `*(p + 3)` 的值是（ ）
- $5$
- $7$
- $9$
- $11$
## 二、判断题（每题 2 分，共 20 分）
**第 1 题** 使用 `cmath` 或 `math.h` 中的函数，表达式 `exp(0)` 的结果值为 $1.0$，且类型为 `double`。
- 正确
- 错误
**第 2 题** 采用开放定址法处理冲突的哈希表中，删除一个元素后可以直接将该位置置空，不会影响后续查找。
- 正确
- 错误
**第 3 题** 在哈夫曼树中，出现次数更多的叶子结点，其深度总是更小。
- 正确
- 错误
**第 4 题** 在一个有向图中，所有顶点的入度之和总是等于所有顶点的出度之和。
- 正确
- 错误
**第 5 题** 广度优先搜索通常借助队列实现，深度优先搜索通常借助栈或递归实现。
- 正确
- 错误
**第 6 题** 快速排序的平均时间复杂度为 $O(n\log n)$，最坏时间复杂度也为 $O(n\log n)$。
- 正确
- 错误
**第 7 题** 为解决 `0/1` 背包问题，使用一维数组优化时，内层容量循环应从大到小枚举。
- 正确
- 错误
**第 8 题** 使用邻接表存储图时，遍历某个顶点的所有邻边所需时间与图中顶点数成正比。
- 正确
- 错误
**第 9 题** 在按层序从 $1$ 开始对结点编号的完全二叉树中，编号为 $i$（$i > 1$）的结点的父结点编号为 $\lfloor i/2 \rfloor$。
- 正确
- 错误
**第 10 题** 在定义了数组 `int arr[10];` 后，表达式 `arr` 和表达式 `&arr[0]` 总是等价的。
- 正确
- 错误