第 1 题 已知小写字母 b 的 ASCII 码为 98，下列 C++ 代码的输出结果是（ ）。

#include <iostream>
using namespace std;
int main() {
	char a = 'b';
	cout << a + 1;
	return 0;
}

{{ select(1) }}

• b
• c
• 98
• 99

---

第 2 题 已知 a 为 int 类型变量， p 为 int* 类型变量，下列赋值语句不符合语法的是（ ）。

{{ select(2) }}

• +a = *p;
• *p = +a;
• a = *(p + a);
• *(p + a) = a;

---

第 3 题 已知数组 a 的定义 int a[10] = {0};，下列说法不正确的是（ ）。

{{ select(3) }}

• 语句 a[-1] = 0; 会产生编译错误。
• 数组 a 的所有元素均被初始化为 0。
• 数组 a 至少占用 10 个 int 大小的内存，一般为 40 个字节。
• 语句 a[13] = 0; 不会产生编译错误，但会导致难以预测的运行结果。

---

第 4 题 下列关于 C++ 类的说法，错误的是（ ）。

{{ select(4) }}

• 构造函数不能声明为虚函数，但析构函数可以。
• 函数参数如声明为类的引用类型，调用时不会调用该类的复制构造函数。
• 静态方法属于类、不属于对象，因此不能使用 对象.方法(...) 的形式调用静态方法。
• 析构派生类的对象时，一定会调用基类的析构函数。

---

第 5 题 下列关于有向图的说法，错误的是（ ）。

{{ select(5) }}

• $n$ 个顶点的弱连通有向图，最少有 $n-1$ 条边。
• $n$ 个顶点的强连通有向图，最少有 $n$ 条边。
• $n$ 个顶点的有向图，最多有 $n \times (n-1)$ 条边。
• $n$ 个顶点的有向完图，有 $n \times (n-1)$ 条边。

---

第 6 题 一棵二叉树的每个结点均满足：结点的左子树和右子树，要么同时存在，要么同时不存在。该树有 197 个结点，则其叶结点有多少个？（ ）

{{ select(6) }}

• 98
• 99
• 不存在这样的树。
• 无法确定叶结点数量。

---

第 7 题 下列关于二叉树的说法，错误的是（ ）。

{{ select(7) }}

• 二叉排序树的中序遍历顺序与元素排序的顺序是相同的。
• n 个元素的二叉排序树，其高一定为 $\lfloor \log_2 n \rfloor$。
• 自平衡二叉查找树（AVL 树）是一种二叉排序树。
• 任意的森林，都可以映射为一颗二叉树进行表达和存储。

---

第 8 题 一个简单无向图有 10 个结点、6 条边。在最差情况，至少增加多少条边可以使其连通？（ ）

{{ select(8) }}

• $3$
• $4$
• $6$
• $9$

---

第 9 题 一个哈希表，包括 $n$ 个位置（编号 $0$ ~ $n-1$），每个位置最多存储一个元素。只有插入和查询操作。以下说法错误的是（ ）。

{{ select(9) }}

• 若哈希函数范围 $0$~$n-1$，碰撞时循环向后寻空位，则查询最差时间复杂度为 $O(n)$。
• 若哈希函数范围 $0$~$n-1$，碰撞时仅向后一个位置寻空位，则查询最差时间复杂度为$O(1)$。
• 若哈希函数范围 $0$~$m-1$（$m<n$），碰撞时仅在 $m~n-1$ 寻空位，则查询最差时间复杂度为 $O(n-m)$。
• 查询时若哈希位置为空，该元素仍可能出现在表内。

---

第 10 题 以下关于动态规划的说法中，错误的是（ ）。

{{ select(10) }}

• 动态规划可避免重复子问题的计算。
• 动态规划方法通常能够列出递推公式。
• 动态规划有递推和递归两种实现形式。
• 递推实现动态规划的时间复杂度总是不低于递归实现。

---

第 11 题 下⾯程序的输出为

 #include <iostream>
 #include <cmath>
 using namespace std;
 int main() {
 	cout << (int)exp(2) << endl;
 	return 0;
 }

{{ select(11) }}

• $4$
• $7$
• $100$
• 无法通过编译。

---

第 12 题 下面程序的输出为（ ）。

#include <iostream>
#define N 10
using namespace std;
int h[N];
int main() {
	h[0] = h[1] = 1;
	for (int n = 2; n < N; n++)
		for (int j = 0; j < n; j++)
			h[n] += h[j] * h[n- j- 1];
	cout << h[6] << endl;
	return 0;
}

{{ select(12) }}

• $132$
• $1430$
• $16796$
• 结果是随机的。

---

第 13 题 上题中程序的时间复杂度为（ ）。

{{ select(13) }}

• $O(N)$
• $O(Nlog\ N)$
• $O(N^{3/2})$
• $O(N^2)$

---

第 14 题 下面 init_sieve 函数的时间复杂度为（ ）。

int sieve[MAX_N];
void init_sieve(int n) {
	for (int i = 1; i <= n; i++)
		sieve[i] = i;
	for (int i = 2; i <= n; i++)
		for (int j = i; j <= n; j += i)
			sieve[j]--;
}

{{ select(14) }}

• $O(n)$
• $O(nlogn)$
• $O(n^2)$
• 无法正常结束。

---

第 15 题 下列选项中，哪个不可能是下图的深度优先遍历序列（ ）。

{{ select(15) }}

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

---