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

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

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

{{ select(1) }}

• b
• c
• 98
• 99

2. 已知 $a$ 为 $\tt int$ 类型变量，$p$ 为 $\tt 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$ 个 $\tt int$ 大小的内存，一般为 $40$ 个字节
• 语句 a[13] = 0; 不会产生编译错误，但会导致难以预测的运行结果

4. 下列关于 $\tt 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$
• 自平衡二叉查找树（$\tt AVL$ 树）是一种二叉排序树
• 任意的森林，都可以映射为一颗二叉树进行表达和存储

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

{{ select(8) }}

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

9. 一个哈希表，包括 $n$ 个位置（分别编号 $0\sim (n-1)$），每个位置最多仅能存储一个元素。该哈希表只有插入元素和查询两种操作，没有删除或修改元素的操作。以下说法错误的是（ ）。

{{ select(9) }}

• 如果哈希函数取值范围为 $0 \sim (n-1)$，且当发生哈希函数碰撞时循环向后寻找空位，则查询操作的最差时间复杂度为。（循环向后指：$0$ 向后一位为 $1$，$1$ 向后一位为 $2$，……，$(n-2)$ 向后一位为 $(n-1)$，$(n-1)$ 向后一位为 $0$）
• 如果哈希函数取值范围为 $0 \sim (n-1)$，且当发生哈希函数碰撞时仅循环向后一个位置寻找空位，则查询操作的最差时间复杂度为 $O(1)$
• 如果哈希函数取值范围为 $0 \sim (m-1)$（$m < n$），且当发生哈希函数碰撞时仅在 $m \sim (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(N \log N)$
• $O(N^{3/2})$
• $O(N^2)$

14. 下面 $\tt 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(n \log n)$
• $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$

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

1. 表达式 5 ^ 3 的结果为 $125$。（ ）

{{ select(16) }}

• 正确
• 错误

2. 在 $\tt C$++ 语言中，函数定义和函数调用可以不在同一个文件内。（ ）

{{ select(17) }}

• 正确
• 错误

3. 在 $n$ 个元素中进行二分查找，平均时间复杂度是 $O(\log n)$，但需要事先进行排序。（ ）

{{ select(18) }}

• 正确
• 错误

4. unsigned long long 类型是 $\tt C$++ 语言中表达范围最大的非负整数类型之一，其表达范围是。超出该范围的非负整数运算，将无法使用 $\tt C$++ 语言进行计算。（ ）

{{ select(19) }}

• 正确
• 错误

5. 使用 math.h 或 cmath 头文件中的函数，表达式 log2(32) 的结果为 $5$、类型为 int。（ ）

{{ select(20) }}

• 正确
• 错误

6. $\tt C$++ 是一种面向对象编程语言，$\tt C$ 则不是。继承是面向对象三大特性之一。因此，使用 $\tt C$ 语言无法实现继承。（ ）

{{ select(21) }}

• 正确
• 错误

7. 邻接表和邻接矩阵都是图的存储形式。邻接表在遍历单个顶点的所有边时，时间复杂度更低；邻接矩阵在判断两个顶点之间是否有边时，时间复杂度更低。（ ）

{{ select(22) }}

• 正确
• 错误

8. $\tt MD5$ 是一种常见的哈希函数，可以由任意长度的数据生成 $128$ 位的哈希值，曾广泛应用于数据完整性校验。中国科学家的系列工作首次发现了可实用的 $\tt MD5$ 破解方法。之后，$\tt MD5$ 逐渐被其他哈希函数所取代。（ ）

{{ select(23) }}

• 正确
• 错误

9. 递归调用在运行时会由于层数过多导致程序崩溃，可以通过循环配合栈缓解这一问题。（ ）

{{ select(24) }}

• 正确
• 错误

10. 一个图中，每个顶点表达一个城市，连接两个顶点的边表达从一个城市到达另一个城市的一种交通方式。这个图可以用来表达交通网络，且是简单有向图。（ ）

{{ select(25) }}

• 正确
• 错误