一、单选题（每题 $2$ 分，共 $30$ 分）

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

01 #include <iostream>
02 using namespace std;
03 int main() {
04     char a = 'b' ^ 4;
05     cout << a;
06     return 0;
07 }

{{ select(1) }}

• b
• bbbb
• f
• 102

$2、$ 已知 a 为 int 类型变量，p 为 int* 类型变量，下列赋值语句不符合语法的是（）。 {{ select(2) }}

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

$3、$ 下列关于 C++ 类的说法，错误的是（）。 {{ select(3) }}

• 如需要使用基类的指针释放派生类对象，基类的析构函数应声明为虚析构函数
• 构造派生类对象时，只调用派生类的构造函数，不会调用基类的构造函数
• 基类和派生类分别实现了同一个虚函数，派生类对象仍能够调用基类的该方法
• 如果函数形参为基类指针，调用时可以传入派生类指针作为实参

$4、$ 下列 C++ 代码的输出是（）。

01 #include <iostream>
02 using namespace std;
03 int main() {
04     int arr[5] = {2, 4, 6, 8, 10};
05     int *p = arr + 2;
06     cout << p[3] << endl;
07     return 0;
08 }

{{ select(4) }}

• 6
• 8
• 编译出错，无法运行
• 不确定，可能发生运行时异常

$5、$ 假定只有一个根节点的树的深度为 1，则一棵有 N 个节点的完全二叉树深度为（）。 {{ select(5) }}

• ⌊log₂(N)⌋ + 1
• ⌊log₂(N)⌋
• ⌈log₂(N)⌉
• 不能确定

$6、$ 对于如下图的二叉树，说法正确的是（）。

{{ select(6) }}

• 先序遍历是 ABDEC
• 中序遍历是 BDACE
• 后序遍历是 DBCEA
• 广度优先遍历是 ABCDE

$7、$ 图的存储和遍历算法，下列说法错误的是（）。 {{ select(7) }}

• 图的深度优先遍历需要借助队列来完成
• 图的深度优先遍历和广度优先遍历对有向图和无向图都适用
• 使用邻接矩阵存储一个包含 v 个顶点的有向图，统计其边数的时间复杂度为 O(v²)
• 同一个图分别使用出边邻接表和入边邻接表存储，其边结点个数相同

$8、$ 一个连通的简单有向图共有 28 条边，则该图至少有（）。 {{ select(8) }}

• 5
• 6
• 7
• 8

$9、$ 以下哪个方案不能合理解决或缓解哈希表冲突（）。 {{ select(9) }}

• 在每个哈希表项处，使用不同的哈希函数再建立一个哈希表，管理该表项的冲突元素
• 在每个哈希表项处，建立二叉排序树，管理该表项的冲突元素
• 使用不同的哈希函数建立额外的哈希表，用来管理所有发生冲突的元素
• 覆盖发生冲突的旧元素

$10、$ 以下关于动态规划的说法中，错误的是（）。 {{ select(10) }}

• 动态规划方法通常能够列出递推公式
• 动态规划方法的时间复杂度通常为状态的个数
• 动态规划方法有递推和递归两种实现形式
• 对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当

$11、$ 下列程序的输出为（）。

01 #include <iostream>
02 using namespace std;
03 int rec_fib[100];
04 int fib(int n) {
05     if (n <= 1)
06         return n;
07     if (rec_fib[n] == 0)
08         rec_fib[n] = fib(n - 1) + fib(n - 2);
09     return rec_fib[n];
10 }
11 int main() {
12     cout << fib(6) << endl;
13     return 0;
14 }

{{ select(11) }}

• 8
• 13
• 64
• 结果是随机的

$12、$ 下列程序的时间复杂度为（）。

01 int rec_fib[MAX_N];
02 int fib(int n) {
03     if (n <= 1) return n;
04     if (rec_fib[n] == 0)
05         rec_fib[n] = fib(n - 1) + fib(n - 2);
06     return rec_fib[n];
07 }

{{ select(12) }}

• $O(2ⁿ)$
• $O(\phi^n),\phi=\frac{\sqrt{5}-1}{2}$
• $O(n²)$
• $O(n)$

$13、$ 下列 search 函数的平均时间复杂度为（）。

01 int search(int n, int *p, int target) {
02     int low = 0, high = n;
03     while (low < high) {
04         int middle = (low + high) / 2;
05         if (target == p[middle])
06             return middle;
07         else if (target > p[middle])
08             low = middle + 1;
09         else
10             high = middle;
11     }
12     return -1;
13 }

{{ select(13) }}

• $O(n log n)$
• $O(n)$
• $O(log n)$
• $O(1)$

$14、$ 下列程序的时间复杂度为（）。

01 int primes[MAXP], num = 0;
02 bool isPrime[MAXN] = {false};
03 void sieve() {
04     for (int n = 2; n <= MAXN; n++) {
05         if (!isPrime[n])
06             primes[num++] = n;
07         for (int i = 0; i < num && n * primes[i] <= MAXN; i++) {
08             isPrime[n * primes[i]] = true;
09             if (n % primes[i] == 0)
10                 break;
11         }
12     }
13 }

{{ select(14) }}

• $O(n)$
• $O(n × log n)$
• $O(n × log log n)$
• $O(n²)$

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

{{ select(15) }}

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

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

$16、$ C++ 语言中，表达式 9 & 12 的结果类型为 int、值为 8。
{{ select(16) }}

• 正确
• 错误

$17、$ C++ 语言中，指针变量指向的内存地址不一定都能够合法访问。
{{ select(17) }}

• 正确
• 错误

$18、$ 对 n 个元素的数组进行快速排序，最差情况的时间复杂度为 $O(n log n)$。
{{ select(18) }}

• 正确
• 错误

$19、$ 一般情况下，long long 类型占用的字节数比 float 类型多。
{{ select(19) }}

• 正确
• 错误

$20、$ 使用 math.h 或 cmath 头文件中的函数，表达式 pow(10, 3) 的结果的值为 1000、类型为 int。
{{ select(20) }}

• 正确
• 错误

$21、$ 二叉排序树的中序遍历序列一定是有序的。
{{ select(21) }}

• 正确
• 错误

$22、$ 无论哈希表采用何种方式解决冲突，只要管理的元素足够多，都无法避免冲突。
{{ select(22) }}

• 正确
• 错误

$23、$ 在 C++ 语言中，类的构造函数和析构函数均可以声明为虚函数。
{{ select(23) }}

• 正确
• 错误

$24、$ 动态规划方法将原问题分解为一个或多个相似的子问题，因此必须使用递归实现。
{{ select(24) }}

• 正确
• 错误

$25、$ 如果将城市视作顶点，公路视作边，将城际公路网络抽象为简单图，可以满足城市间的车道级导航需求。
{{ select(25) }}

• 正确
• 错误