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

1. 以下不属于计算机输出设备的有 ( ) {{ select(1) }}

• 麦克风
• 音箱
• 打印机
• 显示器

2. 小明想了一个 $1$ 到 $100$ 之间的整数。你可以做多次猜测，每次猜测之后，如果你没有猜中，小明会告诉你，你猜的数比他想的数大还是小。你希望你在运气最坏的情况下花费最少的次数猜中，请问你运气最坏的情况下会猜几次？（包括最后猜中的那次） {{ select(2) }}

• 6
• 7
• 8
• 100

3. 关于分治算法，下列说法错误的是 ( ) {{ select(3) }}

• 分治算法的核心思想是分而治之，即把问题转化为多个规模更小的子问题求解。
• 分治算法可以不使用递归实现。
• 分治算法的时间复杂度是 $𝑂(log 𝑁)$，其中 $𝑁$ 表示问题的规模。
• 二分法、快速排序等算法都是典型的使用分治思想的算法。

4. 下面关于 $C++$ 类的说法中，正确的是 ( ) {{ select(4) }}

• 派生类不能和基类有同名成员函数，因为会产生歧义。
• 派生类可以和基类有同名成员函数，派生类覆盖基类的同名成员函数。
• 派生类可以和基类有同名成员函数，但是否覆盖同名成员函数需要取决于函数参数是否一致。
• C++中派生类不继承基类的任何成员函数。

5. 关于下面 $C++$ 代码说法错误的是 ( )  {{ select(5) }}

• Pet 类是基类，Dog 类是子类。
• Dog 类的构造函数中，将自动调用 Pet 类的构造函数。
• dog 是 Dog 类的实例。
• 最后一行（即输出行 A）输出代码会报错，因为 Pet 类中没有成员变量 color。

6. 以下几个类定义中不能顺利通过编译的是 ( )  {{ select(6) }}

• class A
• class B
• class C
• class D

7. 关于运算符重载，下列说法正确的是 ( ) {{ select(7) }}

• 对于下列代码中的两个运算符重载实现：虽然它们的参数类型都是 int 与 Test 的组合，这段代码仍可以通过编译。这是因为在两个重载实现中，int 与 Test 在参数中的顺序不同，编译器能够唯一地确定调用哪个运算符实现代码。 
• A 的说法是错误的。这是因为加法满足交换律，因此即便调换 A 和 int 的顺序，加法运算的实现仍必须保持一致，编译器在编译时也会检查这一点。如将后一处 int 改为 double，则可通过编译。
• A 和 B 的说法都是错误的。运算符重载时，所有参数以及返回值的类型必须完全相同。因此，即便是下列代码中的运算符重载实现，也不能通过编译。
• A、B、C 的说法都是错误的。

8. 关于 $C++$ 程序的异常处理，以下选项中描述错误的是 ( ) {{ select(8) }}

• 编程语言中的异常和错误是不同的概念。
• 异常一旦发生，程序便一定不能继续执行。
• 通过 try、catch 等保留字提供异常处理功能。
• 程序使用 throw 在任何地方抛出各种异常。

9. 有关下面 $C++$ 代码的说法，正确的是 ( )  {{ select(9) }}

• moreData 类可用于构造队列（queue）数据结构。
• myData.push(4).push(5);的连续 push()用法将导致错误。
• 前两个 cout << myData.pop() << endl;代码可以正确运行，分别输出 4 和 5。
• 最后一个 cout << myData.pop() << endl;代码可以通过编译，但不能正常运行，因为 pop 函数中的断言 assert(head < tail);会失败。

10. 如下图所示的哈夫曼树，按照哈夫曼编码规则，假设图中字符 $C$ 的编码为 $0$，则 $E$ 的编码为 ( )  {{ select(10) }}

• 1111
• 1010
• 1101
• 1001

11. 下面有关格雷码的说法，错误的是 ( ) {{ select(11) }}

• 格雷码是无权码。
• 格雷码是循环码。
• 011 和 100 是一组相邻的格雷码。
• 格雷码相邻的码组间仅有一位不同。

12. 在具有 $2𝑁$ 个结点的完全二叉树中，叶子结点个数为 ( ) {{ select(12) }}

• 𝑁/2
• 𝑁 − 1
• N
• 𝑁 + 1

13. 有关下图的二叉树，说法正确的有 ( ) 个 

    是完全二叉树

    是二叉搜索树

    是平衡二叉树 {{ select(13) }}

• 0
• 1
• 2
• 3

14. 现希望存储整数 $𝑁$ 的所有质因子，请问其空间复杂度上界为是 ( ) {{ select(14) }}

• $𝑂(log log 𝑁)$
• $𝑂(log 𝑁)$
• $𝑂(\sqrt𝑁)$
• $𝑂(𝑁)$

15. 下面 $C++$ 代码实现了某种排序算法，其中代码片段 my_sort(arr, begin, i); my_sort(arr, i + 1, end);采用的算法思想是 ( )  {{ select(15) }}

• 递推
• 贪心
• 分治
• 搜索

二、判断题 (每题 $2$ 分，共 $20$ 分)

16. 质数的判定和筛法的目的并不相同，质数判定旨在判断特定的正整数是否为质数，而质数筛法意在筛选出范围内的所有质数。 {{ select(16) }}

• 正确
• 错误

17. 唯一分解定理指的是分解质因数只有唯一的一种算法。 {{ select(17) }}

• 正确
• 错误

18. 一般情况下，在 $C++$ 中定义一个类时，构造函数和析构函数都不是必须手动定义的。 {{ select(18) }}

• 正确
• 错误

19. 如果一个对象具有另一个对象的性质，那么它们之间就是继承关系。 {{ select(19) }}

• 正确
• 错误

20. 哈夫曼编码树中，两个频率相同的字符一定具有相同的哈夫曼编码。 {{ select(20) }}

• 正确
• 错误

21. 宽度优先搜索算法的英文简写是 $BFS$。 {{ select(21) }}

• 正确
• 错误

22. 深度优先遍历算法的时间复杂度为 $𝑂(𝑁 log 𝑁)$，其中𝑁为树的节点数。 {{ select(22) }}

• 正确
• 错误

23. 任意二叉树都至少有一个结点的度是 $2$。 {{ select(23) }}

• 正确
• 错误

24. 将𝑁个数据按照从小到大顺序存放在一个单向链表中。如果采用二分查找，那么查找的平均时间复杂度是 $𝑂(log 𝑁)$ {{ select(24) }}

• 正确
• 错误

25. 深度优先遍历一般需要借助数据结构栈来实现，广度优先遍历一般需要借助数据结构队列来实现。 {{ select(25) }}

• 正确
• 错误