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

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

{{ select(1) }}

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

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

{{ select(2) }}

• $5$
• $6$
• $7$
• $100$

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

{{ select(3) }}

• 分治算法的核心思想是分而治之，即把问题转化为多个规模更小的子问题求解
• 分治算法可以不使用递归实现
• 分治算法的时间复杂度是 $O(\log N)$，其中 $N$ 表示问题的规模
• 分治算法通常较容易在多核处理器上实现加速

4. 有关下面 $\tt C$++ 代码说法错误的（ ）。

   #include <iostream>
   
   using namespace std;
   
   int factA(int n) {
   	if (n <= 1)
   		return 1;
   	
   	int ret = 1;
   	for (int i = 2; i <= n; ++i)
   		ret *= i;
   	
   	return ret;
   }
   
   int factB(int n) {
   	return n == 1 ? 1 : n * factB(n - 1);
   }
   
   int main() {
   	int n;
   	cin >> n;
   	cout << factA(n) << " " << factB(n) << endl;
   	
   	return 0;
   }
   

{{ select(4) }}

• factA() 采用循环方式求 $n$ 的阶乘，factB() 采用递归方式求 $n$ 的阶乘
• 程序执行时如果输入 $5$，能实现求其阶乘，程序输出结果为 $120\ 120$
• 任何递归程序都可以使用循环改写
• 程序执行时如果输入 $100$，不能正确求出 $100$ 的阶乘

5. 下面 $\tt C$++ 代码意在实现字符串反序的功能。关于这段代码，以下说法正确的是（ ）。

   #include <iostream>
   #include <cstring>
   
   using namespace std;
   
   void printSReverse(char* sIn, int len) {
   	if (len <= 1) {
   		cout << sIn[0];
   	}
   	else {
   		cout << sIn[0];
   		printSReverse(sIn + 1, len - 1);
   	}
   }
   
   int main() {
   	char sIn[100] = "Hello";
   	printSReverse(sIn, strlen(sIn));
   	
   	return 0;
   }
   

{{ select(5) }}

• 这段代码可以正确实现字符串反序的功能，其输出为 olleH
• 这段代码不能正确实现字符串反序的功能，其输出为 Hello
• 这段代码不能正确实现字符串反序的功能，其输出为 HHHHH
• 这段代码不能正确实现字符串反序的功能，其输出为 ooooo

6. 阅读下面 $\tt C$++ 实现的二分查找代码，下列说法中错误的是（ ）。

   int binarySearch(int * arr, int l, int r, int x) {
   	if (r >= l) {
   		int mid = l + (r - l) / 2;
   		if (arr[mid] == x)
   			return mid;
   		else if (arr[mid] > x)
   			return binarySearch(arr, l, mid - 1, x);
   		else
   			return binarySearch(arr, mid + 1, r, x);
   	}
   	else 
   		return -1;
   }
   

{{ select(6) }}

• 上面代码实现的二分查找，最少只需查找一次即可得到结果
• 如果调用该函数在列表 $\{2, 3, 4, 10, 12\}$ 中查找元素 $0$，则它实际被调用 $3$ 次
• 如果调用该函数在列表 $\{2, 3, 4, 10, 12\}$ 中查找元素 $3$，则它实际被调用 $3$ 次
• 如果调用该函数在列表 $\{2, 3, 4, 10, 12\}$ 中查找元素 $10$，则它实际被调用 $3$ 次

7. 使用如下代码片段定义四个字符串（假设头文件已正确定义），以下说法错误的是（ ）。

   string str1 = "abc";
   string str2 = str1;
   char str3[] = "abc";
   char * str4 = str3;
   

{{ select(7) }}

• 对于四个字符串，都可以使用 std::cout 输出其中的内容（例如，cout << str3;）
• $\tt str3$ 只占用 $4$ 字节内存，但 $\tt str1$ 却要占用更多内存
• 由于 $\tt str2$ 由 $\tt str1$ 直接赋值得到，因此二者指向同一块内存，即修改 $\tt str1$ 的内容后 $\tt str2$ 的内容也会随之改变
• 由于 $\tt str4$ 由 $\tt str3$ 直接赋值得到，因此二者指向同一块内存，即修改 $\tt str3$ 的内容后 $\tt str4$ 的内容也会随之改变

8. 有关下面 $\tt C$++ 代码正确的是（ ）。

   #include <iostream>
   
   using namespace std;
   
   void f1() {
   	cout << "f1()" << endl;
   }
   
   void f1(int x) {
   	cout << "f1(" << x << ")" << endl;
   }
   
   int main() {
   	f1();
   	f1(0);
   	f1('0');
   
   	return 0;
   }
   

{{ select(8) }}

• 该程序不能正常运行，因为 $f1$ 函数被重复定义
• 该程序可以正常运行，输出结果共 $3$ 行，依次为 $f1()$、$f1()$、$f1()$
• 该程序可以正常运行，输出结果共 $3$ 行，依次为 $f1()$、$f1(0)$、$f1(0)$
• 该程序可以正常运行，输出结果共 $3$ 行，依次为 $f1()$、$f1(0)$、$f1(48)$

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

{{ select(9) }}

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

10. 下面代码执行后的输出是（ ）。

    #include <iostream>
    
    using namespace std;
    
    int fibonacci(int N) {
    	cout << N << ",";
    	if (N == 1 || N == 2) {
    		return 1;
    	} else {
    		return fibonacci(N - 1) + fibonacci(N - 2);
    	}
    }
    
    int main() {
    	cout << fibonacci(5) << endl;
    
    	return 0;
    }
    

{{ select(10) }}

• $5,4,3,2,1,2,1,5$
• $5,4,3,2,1,2,3,2,1,5$
• $5,4,4,3,2,1,3,2,1,5$
• $5,4,3,2,1,3,2,1,5$

11. 下列代码中，函数 $f$ 的作用是（ ）。

    void f(int a, int b) {
    	return b == 0 ? a : f(b, a % b);
    }
    

{{ select(11) }}

• 求 $a$ 和 $b$ 的最大公共质因子
• 求 $a$ 和 $b$ 的最小公共质因子
• 求 $a$ 和 $b$ 的最大公约数
• 求 $a$ 和 $b$ 的最小公倍数

12. 下面 $\tt C$++ 代码用于排序，下列说法中错误的是（ ）。

    void sortA(int * arr, int n) {
    	for (int i = 0; i < n; ++i)
    		for (int j = 0; j < n - i - 1; ++j)
    			if (arr[j] > arr[j + 1]) {
    				int tmp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = tmp;
    			}
    }
    
    void sortB(int * arr, int start, int end) {
    	if (start >= end)
    		return ;
    	
    	int middle = (start + end) / 2;
    	sortB(arr, start, middle);
    	sortB(arr, middle + 1, end);
    
    	int leftSize = middle - start + 1;
    	int rightSize = end - middle;
    
    	int * left = new int[leftSize];
    	int * right = new int[rightSize];
    
    	for (int i = 0; i < leftSize; i++)
    		left[i] = arr[start + i];
    	for (int j = 0; j < rightSize; j++)
    		right[j] = arr[middle + 1 + j];
    
    	int i = 0;
    	int j = 0;
    	int k = start;
    	while (i < leftSize && j < rightSize) {
    		if (left[i] <= right[j]) {
    			arr[k] = left[i];
    			i++;
    		} else {
    			arr[k] = right[j];
    			j++;
    		}
    		k++;
    	}
    	while (i < leftSize) {
    		arr[k] = left[i];
    		i++;
    		k++;
    	}
    	while (j < rightSize) {
    		arr[k] = right[j];
    		j++;
    		k++;
    	}
    
    	delete[] left;
    	delete[] right;
    }
    

{{ select(12) }}

• 两种排序算法的时间复杂度不同
• 两种排序算法的空间复杂度一致
• $\tt sortA$ 的时间复杂度在最好和最坏情况下都是 $O(N^2)$
• $\tt sortB$ 的平均时间复杂度、最好情况的时间复杂度都是 $O(\log N)$，最坏情况的时间复杂度是 $O(N^2)$

13. 上一题中的 $\tt sortB$ 函数，明显体现出的算法思想和编程方法包括（ ）。

{{ select(13) }}

• 递归
• 分治
• $A$、$B$ 都正确
• $A$、$B$ 都不正确

14. 下列哪个算法并没有体现分治思想？（ ）

{{ select(14) }}

• 二分查找
• 埃氏筛法
• 归并排序
• 快速排序

15. 下列关于链表说法，正确的是（ ）。

{{ select(15) }}

• 不能用数组来实现链表。
• 在链表头部插入元素的时间复杂度是 $O(1)$。
• 循环链表使得任意一个结点都可以很方便地访问其前驱与后继。
• 从双向链表的任意一个节点出发，并不一定能够访问到所有其他节点。

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

1. 计算机硬件主要包括运算器、控制器、存储器、输入设备和输出设备。（ ）

{{ select(16) }}

• 正确
• 错误

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

{{ select(17) }}

• 正确
• 错误

3. 埃氏筛法用于找出自然数 $N$ 以内的所有质数，其时间复杂度为 $O(N\sqrt{N})$，因为判定一个数是否为质数的时间复杂度为 $O(N)$。（ ）

{{ select(18) }}

• 正确
• 错误

4. 贪心法的每一步都采取局部最优策略，因此必然能实现全局最优。（ ）

{{ select(19) }}

• 正确
• 错误

5. 在 $\tt C$++ 语言中，函数的参数也可以是另一个函数。（ ）

{{ select(20) }}

• 正确
• 错误

6. 在 $\tt C$++ 语言中，内置的排序算法（$\tt algorithm$ 库中的 $\tt sort$ 函数）只能对 $\tt C$++ 的基础类型（如 int、double 等）做排序，而不能对自定义类型做排序。（ ）

{{ select(21) }}

• 正确
• 错误

7. 在任何场景下，链表都是比数组更优秀的数据结构。（ ）

{{ select(22) }}

• 正确
• 错误

8. 在 $\tt C$++ 语言中，可以使用 delete 来释放指针指向的内存空间。（ ）

{{ select(23) }}

• 正确
• 错误

9. 选择排序和快速排序都是不稳定的。（ ）

{{ select(24) }}

• 正确
• 错误

10. 二分查找法可以应用于有序序列（如升序排序的整数数组），也可以应用于无序序列（如乱序的整数数组）。（ ）

{{ select(25) }}

• 正确
• 错误