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

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

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

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

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

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

第 6 题 已知 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] 的值为（ ）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

三、编程题（每题 25 分，共 50 分）

第 1 题 染色

题面描述

小杨同学有一张包含 $n$ 个结点的无向图 $G$，$G$ 中的结点依次以 $1,2,\cdots, n$ 编号。

小杨同学发现 $G$ 中每个结点的度数都是 $2$。显然 中恰好有 $n$ 条边。

小杨同学想为 $G$ 中的结点染色，使得任意一条边两端的结点都有不同的颜色。

小杨同学想知道最少需要多少种颜色才能在满足条件的前提下为 $G$ 染色。

输入格式

本题包含多组数据。

第一行，一个正整数 $t$，表示数据组数。

对于每组数据：

第一行，一个正整数 $n$，表示无向图 $G$ 中的结点数。

接下来 $n$ 行，每行两个正整数 $u_i,v_i$，表示一条连接结点 $u_i$ 与 $v_i$ 的无向边，整数之间以空格分隔。

保证 $G$ 中没有重边与自环。

输出格式

对于每组数据：输出一行，一个整数，表示在满足条件的前提下为 $G$ 染色需要的最少颜色数。

4
6
1 6
2 1
3 2
4 3
5 4
6 5
6
1 3
3 5
5 1
2 4
4 6
6 2
3
1 2
2 3
3 1
5
1 4
2 5
3 1
4 2
5 3

2
3
3
3

数据要求

对于 $40\%$ 的测试点，保证 $\sum n \le 500$，$\sum n$ 指每个输入中多组数据的 $n$ 的总和。

对于所有测试点，保证 $1 \le t \le 100$，$3 \le n \le 10^5$ ，$\sum n \le 10^5$ 。保证 $G$ 中没有重边与自环。

第 2 题 消消乐

题面描述

给定一个由 $n$ 个整数构成的数组 $a=[a_1,a_2,\cdots,a_n]$。每次你可以对数组 $a$ 进行以下操作，直到数组 $a$ 变为空：

- 指定 $a$ 中的一个元素，获得该元素两侧相邻元素之和的分数，并将该元素从 $a$ 中删去。

特别地，如果相邻元素不存在则该元素的值视为 $0$。例如，对于$a=[1,2,3]$ 可以进行以下操作：

- 指定元素 $2$，获得分数 $1+3$，删去 $2$ 后 $a=[1,3]$ ；

- 指定元素 $1$，获得分数 $0+3$，删去 $1$ 后 $a=[3]$；

- 指定元素 $3$，获得分数 $0+0$，删去 $3$ 后 $a$变为空。

请问你能获得的分数总和最大是多少？

输入格式

第一行，一个正整数 $n$，表示数组长度。

第二行，$n$ 个非负整数 $a_1,a_2,\cdots,a_n$，表示数组 $a$ 中的整数。

输出格式

输出一行，一个整数，表示能获得的最大分数总和。

6
1 6 3 2 9 1

55

5
3 1415 926 53 58

5771

数据要求

对于 $40\%$ 的测试点，保证 $1 \le n \le 50$，$0 \le a_i \le 10^3$ 。

对于所有测试点，保证 $1 \le n \le 100$，$0 \le a_i \le 10^9$ 。