一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

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

{{ 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(n-1) 条边。
• n 个顶点的有向完全图，有 n(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. 关于哈希表的说法，错误的是（ ）。 {{ select(9) }}

• 如果哈希函数取值范围为0 ~ (n-1)，且当发⽣哈希函数碰撞时循环向后寻找空位，则查询操作的最差时间复杂 度为 O(n)。（“循环向后”指：0向后⼀位为1，1向后⼀位为2，……，(n-2)向后⼀位为(n-1)，(n-1)向后⼀位为0
• 如果哈希函数取值范围为0 ~ (n-1)，且当发⽣哈希函数碰撞时仅循环向后⼀个位置寻找空位，则查询操作的最 差时间复杂度为 O(1)。
• 如果哈希函数取值范围为0 ~ (m-1)（m < n），且当发⽣哈希函数碰撞时仅在m ~ (n-1)的范围内寻找空位，则查询操作的最差时间复杂度为 O(n-m)。
• 查询时，若发现目标位置为空位，该元素仍可能在哈希表内。

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

• 动态规划将原问题分解为相似子问题。
• 动态规划通常能够列出递推公式。
• 动态规划有递推和递归两种实现形式。
• 递推实现动态规划的时间复杂度总是不低于递归实现。

11. 下面程序的输出为（ ）。

{{ select(11) }}

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

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

{{ select(12) }}

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

13. 上题中程序的时间复杂度为（ ）。 {{ select(13) }}

• A. $O(N)$
• B. $O(N log N)$
• C. $O(N^{3/2})$
• D. $O(N^{2})$

14. init_sieve 函数的时间复杂度为（ ）。

{{ 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

---

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

16. 表达式 5 ^ 3 的结果为 125。 {{ select(16) }}

• 正确
• 错误

17. 在 C++ 语言中，函数定义和函数调用可以不在同一个文件内。 {{ select(17) }}

• 正确
• 错误

18. 在 n个元素中进行二分查找，平均时间复杂度是 O(log n)，但须要事先进行排序。 {{ select(18) }}

• 正确
• 错误

19. unsigned long long 的表达范围约为 0 ~ $2^{64}-1$，超出该范围的运算无法用 C++ 直接表示。 {{ select(19) }}

• 正确
• 错误

20. 使用 cmath 头文件中的函数，表达式 log2(32) 的结果为 5，类型为 int。 {{ select(20) }}

• 正确
• 错误

21. C++ 是一种面向对象编程语言，C 不是；继承是面向对象三大特性之一，因此使用 C 语言无法实现继承。 {{ select(21) }}

• 正确
• 错误

22. 邻接表遍历单个顶点的所有边更快；邻接矩阵判断两顶点是否有边更快。 {{ select(22) }}

• 正确
• 错误

23. MD5 能对任意长度数据生成 128 位哈希值，中国科学家首次提出了实用的 MD5 破解方法，此后 MD5 被逐渐取代。 {{ select(23) }}

• 正确
• 错误

24. 递归层数过多会导致程序崩溃，可用循环配合栈替代递归。 {{ select(24) }}

• 正确
• 错误

25. 一个交通网络若用“城市”为顶点、“交通方式”为有向边，则该图是简单有向图。 {{ select(25) }}

• 正确
• 错误