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

1. 以下不属于计算机输出设备的有（ ）。

{{ select(1) }}

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

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

{{ select(2) }}

• $6$
• $7$
• $8$
• $100$

3. 关于分治算法，下列说法错误的是（ ）。

{{ select(3) }}

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

4. 下面关于 $\tt C$++ 类的说法中，正确的是（ ）。

{{ select(4) }}

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

5. 关于下面 $\tt C$++ 代码说法错误的是（ ）。

   #include <iostream>
   #include <string>
   
   using namespace std;
   
   class Pet {
   public:
   	string kind;
   	int age;
   	Pet(string _kind, int _age) : kind(_kind), age(_age) {}
   };
   
   class Dog : public Pet {
   public:
   	string color;
   	Dog(string _kind, int _age, string _color) : Pet(_kind, _age), color(_color) {}
   };
   
   int main() {
   	auto dog = Dog("dog", 3, "white");
   	cout << "kind: " << dog.kind << endl;
   	cout << "age: " << dog.age << endl;
   	cout << "color: " << dog.color << endl; // 输出行 A
   
   	return 0;
   }
   

{{ select(5) }}

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

6. 以下几个类定义中不能顺利通过编译的是（ ）。

   class A {
   public:
   	void func(int a, int b, int c) {}
   };
   
   class B {
   public:
   	void func(int a, int b = 1, int c = 1) {}
   };
   
   class C {
   public:
   	void func(int a = 3, int b, int c) {}
   };
   
   class D {
   public:
   	void func(int a = 3, int b = 1, int c = 0) {}
   };
   

{{ select(6) }}

• $\tt class\ A$
• $\tt class\ B$
• $\tt class\ C$
• $\tt class\ D$

7. 关于运算符重载，下列说法正确的是（ ）。

{{ select(7) }}

• 对于下列代码中的两个运算符重载实现：虽然它们的参数类型都是 int 与 Test 的组合，这段代码仍可以通过编译。这是因为在两个重载实现中，int 与 Test 在参数中的顺序不同，编译器能够唯一地确定调用哪个运算符实现代码

  #include <iostream>
  
  using namespace std;
  
  class Test {
  public:
    int data;
    Test(int d) : data(d) {}
  };
  
  Test operator +(const Test& a, const int& b) {
    return Test(a.data + b);
  }
  
  Test operator +(const int& b, const Test& a) {
    return Test(-a.data - b);
  }
  
  int main() {
    Test obj(1);
    int data = 2;
    cout << (obj + data).data << endl;
    cout << (data + obj).data << endl;
  
    return 0;
  }
  

• $A$ 的说法是错误的。这是因为加法满足交换律，因此即便调换 Test 和 int 的顺序，加法运算的实现仍必须保持一致，编译器在编译时也会检查这一点。如将后一处 int 改为 double，则可通过编译
• $A$ 和 $B$ 的说法都是错误的。运算符重载时，所有参数以及返回值的类型必须完全相同。因此，即便是下列代码中的运算符重载实现，也不能通过编译

  class Test {
  public:
  	int data;
  	Test(int d) : data(d) {}
  };
  
  Test operator +(const Test& a, const int& b) {
  	return Test(a.data + b);
  }
  

• $A$、$B$、$C$ 的说法都是错误的

8. 关于 $\tt C$++ 程序的异常处理，以下选项中描述错误的是（ ）。

{{ select(8) }}

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

9. 有关下面 $\tt C$++ 代码的说法，正确的是（ ）。

   #include <iostream>
   #include <cassert>
   
   using namespace std;
   
   class MoreData {
   	int* __data;
   	int head, tail, capacity;
   
   public:
   	MoreData(int cap) {
   		capacity = cap;
   		__data = new int[capacity];
   		head = tail = 0;
   	}
   
   	MoreData& push(int val) {
   		assert(tail < capacity);
   		__data[tail++] = val;
   		return *this;
   	}
   
   	int pop() {
   		assert(head < tail);
   		return __data[--tail];
   	}
   
   	int size() {
   		return tail - head;
   	}
   };
   
   int main() {
   	auto myData = MoreData(100);
   	myData.push(4).push(5);
   
   	cout << myData.pop() << endl;
   	cout << myData.pop() << endl;
   	cout << myData.pop() << endl;
   
   	return 0;
   }
   

{{ select(9) }}

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

10. 如下图所示的哈夫曼树，按照哈夫曼编码规则，假设图中字符 $\tt C$ 的编码为 $0$，则 $\tt E$ 的编码为（ ）。

    

{{ select(10) }}

• $1111$
• $1010$
• $1101$
• $1001$

11. 下面有关格雷码的说法，错误的是（ ）。

{{ select(11) }}

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

12. 在具有 $2N$ 个结点的完全二叉树中，叶子结点个数为（ ）。

{{ select(12) }}

• $N/2$
• $N-1$
• $N$
• $N+1$

13. 有关下图的二叉树，说法正确的有（ ）个。

    

    • 是完全二叉树
    • 是二叉搜索树
    • 是平衡二叉树

{{ select(13) }}

• $0$
• $1$
• $2$
• $3$

14. 现希望存储整数 $N$ 的所有质因子，请问其空间复杂度上界是（ ）。

{{ select(14) }}

• $O(\log \log N)$
• $O(\log N)$
• $O(\sqrt{N})$
• $O(N)$

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

    void my_sort(int arr[], int begin, int end) {
    	if (begin >= end - 1) return ;
    
    	int i = begin, j = end - 1, x = arr[begin];
    	while (i < j) {
    		while (i < j && arr[j] >= x)
    			j--;
    		if (i < j)
    			arr[i++] = arr[j];
    
    		while (i < j && arr[i] < x)
    			i++;
    		if (i < j)
    			arr[j--] = arr[i];
    	}
    
    	arr[i] = x;
    	my_sort(arr, begin, i);
    	my_sort(arr, i + 1, end);
    }
    

{{ select(15) }}

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

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

1. 质数的判定和筛法的目的并不相同，质数判定旨在判断特定的正整数是否为质数，而质数筛法意在筛选出范围内的所有质数。（ ）

{{ select(16) }}

• 正确
• 错误

2. 唯一分解定理指的是分解质因数只有唯一的一种算法。（ ）

{{ select(17) }}

• 正确
• 错误

3. 一般情况下，在 $\tt C$++ 中定义一个类时，构造函数和析构函数都不是必须手动定义的。（ ）

{{ select(18) }}

• 正确
• 错误

4. 如果一个对象具有另一个对象的性质，那么它们之间就是继承关系。（ ）

{{ select(19) }}

• 正确
• 错误

5. 哈夫曼编码树中，两个频率相同的字符一定具有相同的哈夫曼编码。（ ）

{{ select(20) }}

• 正确
• 错误

6. 宽度优先搜索算法的英文简写是 $\tt BFS$。（ ）

{{ select(21) }}

• 正确
• 错误

7. 深度优先遍历算法的时间复杂度为 $O(N \log N)$，其中 $N$ 为树的节点数。（ ）

{{ select(22) }}

• 正确
• 错误

8. 任意二叉树都至少有一个结点的度是 $2$。（ ）

{{ select(23) }}

• 正确
• 错误

9. 将 $N$ 个数据按照从小到大顺序存放在一个单向链表中。如果采用二分查找，那么查找的平均时间复杂度是 $O(\log N)$。（ ）

{{ select(24) }}

• 正确
• 错误

10. 深度优先遍历一般需要借助数据结构栈来实现，广度优先遍历一般需要借助数据结构队列来实现。（ ）

{{ select(25) }}

• 正确
• 错误