一、单选题（每题 2 分，共 30 分）
1、近年来，线上授课变得普遍，很多有助于改善教学效果的设备也逐渐流行，其中包括⽐较常用的手写板，那么它属于哪类设备？（）。

A. 输⼊
B. 输出
C. 控制
D. 记录
【答案】A
【考纲知识点】 计算机基础知识
【解析】本题属于考察计算机基础知识知识。手写板是输入信息的设备，选A。
2、如果 a 和 b 均为 int 类型的变量，且 b 的值不为0 ，那么下列能正确判断“ a 是 b 的 3 倍”的表达式是（）。
A. (a >> 3 == b)
B. (a - b) % 3 == 0
C. (a / b == 3)
D. (a == 3 * b)
【答案】D
【考纲知识点】 运算表达式和位运算
【解析】本题属于考察运算表达式和位运算知识。b 不等于0，a 是b 的3倍。A 选项中，a 右移 3 位，相当于除以 8；B 是取余运算；如果a=7,b=2,a/b的结果也等于 3，因为是整型，C 选项也不正确；选 D。
3、如果变量 a 和 b 分别为 double 类型和 int 类型，则表达式(a = 6，b = 3 * (7 + 8) / 2， b += a) 的计算结果为（）。

A. 6
B. 21
C. 28
D. 不确定
【答案】C
【考纲知识点】 数据类型和运算表达式
【解析】本题属于考察数据类型、逗号表达式、运算表达式知识。逗号表达式从左到右依次计算每一个表达式，整个逗号表达式的结果是最后一个表达式的计算结果，a=6，b=3*15/2=22,b=6+22=28，选 C。
4、有关下⾯C++代码说法错误的是（ ）。

//sumA()和sumB()用于求从1到N之和
#include <iostream>
using namespace std;
int sumA(int n){
	int sum=0;
	for(int i=1;i< n + 1;i++)
		sum += i;
	return sum;
}
int sumB(int n){
	if(n == 1)
		return 1;
	else
		return n+sumB(n-1);
}
int main(){
	int n=0;
	cin >> n;
	cout<< sumA(n) << " " << sumB(n) << endl;
	return 0;
}

A. sumA() ⽤循环⽅式求从 1 到 N 之和， sumB() ⽤递归⽅式求从1 到N之和。
B. 默认情况下，如果输⼊正整数 1000 ，能实现求从1 到1000 之和。
C. 默认情况下，如果输⼊正整数 100000 ，能实现求从1 到100000 之和。
D. ⼀般说来， sumA() 的效率⾼于 sumB() 。
【答案】C
【考纲知识点】 函数和递归算法
【解析】本题属于考察递归和函数知识。sumA 用循环求的是1 到n 的总和；sumB用递归的方式求 1 到 n 的总和。1 加到 100000 的和大于int 类型最大值，2147483647，会溢出，选 C。
5、下⾯C++代码以递归⽅式实现字符串反序，横线处应填上代码是（）。

//字符串反序
#include <iostream>
#include <string>
using namespace std;
string sReverse(string sIn) {
	if (sIn.length() <= 1) {
		return sIn;
	} else {
		return _______ //此处填写代码
	}
}
int main(){
	string sIn;
	cin >> sIn;
	cout<< sReverse(sIn) << endl;
	return 0;
}

A. sIn[sIn.length() - 1] + sReverse(sIn.substr(0, sIn.length() - 1));
B. sIn[0] + sReverse(sIn.substr(1, sIn.length() - 1));
C. sReverse(sIn.substr(0, sIn.length() - 1)) + sIn[sIn.length() - 1];
D. sReverse(sIn.substr(1, sIn.length() - 1)) + sIn[sIn.length() - 1];
【答案】A
【考纲知识点】 函数和递归算法
【解析】本题属于考察递归和函数知识。要倒序输出字符串，先输出字符串中的最后一个字符，最后一个字符下标是长度-1，然后翻转除了最后一个字符的字符串，这个字符串是从 0 开始，选 sIn.length()-1 个字符，选A。

6、印度古⽼的汉诺塔传说：创世时有三根⾦刚柱，其中⼀柱从下往上按照⼤⼩顺序摞着 64⽚黄⾦圆盘，当圆盘逐⼀从⼀柱借助另外⼀柱全部移动到另外⼀柱时，宇宙毁灭。移动规则：在⼩圆盘上不能放⼤圆盘，在三根柱⼦之间⼀次只能移动⼀个圆盘。下⾯的 C++代码以递归⽅式实现汉诺塔，横线处应填⼊代码是（ ）。

#include<iostream>
using namespace std;

//递归实现汉诺塔，将N个圆盘从A通过B移动C
//圆盘从底到顶，半径必须从大到小
void Hanoi(string A, string B, string C, int N){
	if(N == 1){
		cout<< A <<" -> "<< C << endl;
	}else{
		Hanoi(A, C, B, N-1);
		cout << A << "->" << C << endl;
		__________;//此处填写代码
	}
}
int main(){
	Hanoi("甲", "乙", "丙", 3);
	return 0;
}

A. Hanoi(B, C, A, N - 2)
B. Hanoi(B, A, C, N - 1)
C. Hanoi(A, B, C, N - 2)
D. Hanoi(C, B, A, N - 1)
【答案】B
【考纲知识点】 函数和递归算法
【解析】本题属于考察递归和函数知识。汉诺塔比较经典的递归问题，第11行代码意味这剩下的 N-1 快圆盘，现在 B 柱子上，借助 A 柱，挪到C柱上，选B。

7、根据下⾯C++代码的注释，两个横线处应分别填⼊（）。

#include <algorithm>
using namespace std;

bool isOdd(int N){
	return N%2 == 1;
}
bool compare(int a,int b){
	if(a%2 == 0 && b%2 == 1)
		return true;
	return false;
}
int main(){
	vector<int> lstA; //lstA是一个整型向量
	for( int i = 1; i < 100; i++)
		lstA.push_back(i);
	//对lstA成员按比较函数执行结果排序
	sort(lstA.begin(), lstA.end(), _______ ); //此处填写代码1
	vector<int> lstB;
	for(int i = 0; i < lstA.size(); i++)// lstB成员全为奇数
		if(_______)//此处填写代码2
			lstB.push_back(lstA[i]);

	cout << "lstA: ";
	for(int i = 0; i < lstA.size(); i++)
		cout<< lstA[i] << "";
	cout << endl;
	
	cout<< "lstB: ";
	for(int i = 0; i < lstB.size(); i++)
		cout<< lstB[i] << "";
	cout << endl;
	return 0;
}

A. compare 和 isOdd(lstA[i])
B. compare(x1,y1) 和 isOdd
C. compare 和 isOdd
D. compare(x1,y1) 和 isOdd(lstA[i])
【答案】A
【考纲知识点】 函数的调用、值传递
【解析】本题考察的是 vector 和 sort 函数的使用。本题中首先创建了一个vector
lstA 存储整数 1~99，然后调用 sort 函数对 lstA 进行排序，sort 函数排序需要传递三个参数，前两个参数决定了排序范围的起始位置和结束位置，第三个参数是排序规则函数，排序规则函数需要两个参数和一个 bool 类型的返回值，所以代码 1 处传递排序规则函数 compare，只需要写函数名即可，不需要写成调用的形式，排除选项 B 和 D。接下来的代码是将 lstA 中的奇数存储到另一个 vector lstB 中，判断奇数可以使用自定义函数 isOdd，代码 2 处是调用 isOdd 函数判断当前的lstA[i]是否为奇数，因此需要使用调用函数语法 isOdd(IstA[i])，正确答案为A 选项。

8、有关下面代码正确的是（ ）。

// 在C++语言中，可以通过函数指针的形式，将一个函数作为另一个函数的参数。
// 具体来说: bool checkNum(bool (*Fx)(int), int N);声明了一个函数,
// 其第一个参数是函数指针类型,指向一个接收一个int参数且返回值为bool的函数。
#include<iostream>
using namespace std;

bool isEven(int N){
	return N%2 == 0;
}
bool checkNum(bool (*Fx)(int), int N){
	return Fx(N);
}
int main(){	 
	cout<< checkNum(isEven, 10) << endl;
	return 0;
}

A. checkNum() 函数定义错误。
B. 将 isEven 作为 checkNum() 参数将导致错误。
C. 执⾏后将输出 1 。
D. 运⾏时触发异常。
【答案】C
【考纲知识点】 函数的定义、调用、值传递
【解析】本题考察函数指针的知识。isEven 是一个自定义函数，用于判断为偶数。checkNum 也是一个自定义函数，该函数的第一个参数是一个函数指针类型，需要传递一个函数，所传递的这个函数要求返回值为 bool，并且有一个int 类型参数，isEven 函数复合该类型的要求，所以调用 checkNum 函数时，第一个参数传递函数 isEven，第二个参数传递整数 10 没有错误，执行checkNum函数内部代码 Fx(N)，也就是调用函数 isEven(10)，整数 10 是偶数，因此最后调用的结果是1，因此正确答案选 C。
9、有关下⾯C++代码正确的是（ ）。

#include<iostream>
using namespace std;

bool isOdd(int N){
	return N%2 == 1;
}
int Square(int N){
	return N*N;
}
bool checkNum(bool (*Fx)(int), int x) {
	return Fx(x);
}
int main(){	 
	cout<< checkNum(isOdd, 10) << endl; // 输出行 A
	cout<< checkNum(Square, 10) << endl; // 输出行 B
	return 0;
}

A. checkNum() 函数定义错误。
B. 输出⾏ A 的语句将导致编译错误。
C. 输出⾏ B 的语句将导致编译错误。
D. 该代码没有编译错误。
【答案】C
【考纲知识点】 函数指针
【解析】本题考察函数指针的知识。checkNum 函数的第一个参数需要传递一个返回值为 bool、参数为 int 类型的函数，isEven 函数复合该类型的要求，所以调用 checkNum 函数时，第一个参数传递函数 isEven，不会导致编译错误，Square函数的返回值是 int 类型，不符合 cehckNum 函数的第一个参数的类型要求，因此调用时传递 Square 函数会导致编译错误，所以答案为C 选项。

10、下⾯代码执⾏后的输出是（ ）。

#include<iostream>
using namespace std;

int jumFloor(int N){
	cout<< N << "#";
	if(N == 1 || N == 2){
		return N;
	}else{
		return jumFloor(N-1) + jumFloor(N-2);
	}
	return true;
}

int main(){	 
	cout<< jumFloor(4) << endl;
	return 0;
}

A. 4#3#2#2#4
B. 4#3#2#2#1#5
C. 4#3#2#1#2#4
D. 4#3#2#1#2#5
【答案】D
【考纲知识点】 递归和函数
【解析】本题属于考察递归和函数知识。第 13 行代码调用jumFloor(4)，首先输出 4#，然后返回 jumFloor(3)+ jumFloor(2)，jumFloor(3)输出3#再继续递归调用 jumFloor(2)+ jumFloor(1)依次输出 2#1#并返回 3。jumFloor(2)输出 2#返回 2，所以第 13 行代码调用之后的返回结果是3+2=5，最后的输出结果就是 4#3#2#1#2#5，所以正确答案选 D。
11、下面代码中的 isPrimeA() 和 isPrimeB() 都⽤于判断参数N是否素数，有关其时间复杂度的正确说法是（ ）。

#include<iostream>
#include<cmath>
using namespace std;

bool isPrimeA(int N){
	if(N < 2)
		return false;
	for (int i = 2; i < N; i++)
		if(N % i == 0)
			return false;
	return true;
}
bool isPrimeB(int N){
	if(N < 2)
		return false;
	int endNum = int(sqrt(N));
	for (int i = 2; i <= endNum; i++)
		if(N % i == 0)
			return false;
	return true;
}
int main(){	 
	cout<< boolalpha;
	cout<< isPrimeA(13) << " " << isPrimeB(13) << endl;
	return 0;
}

A. isPrimeA() 的最坏时间复杂度是 0(N) ， isPrimeB() 的最坏时间复杂度是0(log N) ， isPrimeB() 优于 isPrimeA()。
B. isPrimeA() 的最坏时间复杂度是 0(N) ， isPrimeB() 的最坏时间复杂度是0（N½）， isPrimeB() 优于 isPrimeA()。
C. isPrimeA() 的最坏时间复杂度是 0（N½）， isPrimeB() 的最坏时间复杂度是 0(N)， isPrimeA()优于 isPrimeB()。
D. isPrimeA() 的最坏时间复杂度是 0(log N) ， isPrimeB() 的最坏时间复杂度是 0(N)， isPrimeA() 优于 isPrimeB()。
【答案】B
【考纲知识点】 时间复杂度
【解析】本题属于考察时间复杂度的相关知识。isPrimeA 的最坏时间复杂度是O(N)，isPrimeB 的最坏时间复杂度是 O()，O()优于 O(N)，正确答案B选项。

12、下⾯代码⽤于归并排序，其中 merge() 函数被调⽤次数为（）。

#include<iostream>
using namespace std;

void mergeSort(int * listData, int start, int end);
void merge(int * listData, int start, int middle, int end);

void mergeSort(int * listData, int start, int end){
	if (start >= end)
		return;
	int middle = (start + end) / 2;
	mergeSort( listData, start, middle);
	mergeSort( listData, middle+1, end);
	merge( listData, start, middle, end);
}
void merge(int * listData, int start, int middle, int 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] = listData[start + i];
	for (int j = 0; j < rightSize; j++)
		right[j] = listData[middle + 1 + j];
		
	int i = 0, j = 0, k = start;
	while (i < leftSize && j < rightSize){
		if (left[i] <= right[j]){
			listData[k] = left[i];
			i++;
		}else {
			listData[k] = right[j];
			j++;
		}
		k++;
	}
	
	while(i < leftSize){
		listData[k] = left[i];
		i++;
		k++;
	}
	while(j < rightSize){
		listData[k] = right[j];
		j++;
		k++;
	}
	delete[] left;
	delete[] right;
}
int main(){	 
	int lstA[]={1, 3, 2, 7, 11, 5, 3};
	int size = sizeof(lstA) / sizeof(lstA[0]);
	
	mergeSort(lstA, 0, size - 1); //对lstA执行归并排序
	
	for(int i = 0; i<size; i++){
		cout << lstA[i] << " ";
	}
	cout << endl;
	return 0;
}

A. 0
B. 1
C. 6
D. 7
【答案】C
【考纲知识点】 分治算法
【解析】本题考察归并排序的相关知识。listA 的长度为7，根据递归返回的条件s t a r t > = e nd ，merge 函数会被调用 6 次，正确答案C 选项。

13、在上题的归并排序算法中， mergeSort(listData, start, middle); 和mergeSort(listData, middle + 1, end); 涉及到的算法为（）。

A. 搜索算法
B. 分治算法
C. 贪⼼算法
D. 递推算法
【答案】B
【考纲知识点】
【解析】本题属于考察归并排序的相关知识。归并排序采用的是分治算法思想，正确答案 B 选项。
14、归并排序算法的基本思想是（ ）。
A. 将数组分成两个⼦数组，分别排序后再合并。
B. 随机选择⼀个元素作为枢轴，将数组划分为两个部分。
C. 从数组的最后⼀个元素开始，依次与前⼀个元素⽐较并交换位置。
D. ⽐较相邻的两个元素，如果顺序错误就交换位置。

【答案】A
【考纲知识点】 归并排序算法
【解析】本题属于考察归并排序的相关知识。归并排序基本思想就是将数组分成两个⼦数组，分别排序后再合并，正确答案 A 选项。
15、有关下⾯代码的说法正确的是（ ）。

#include<iostream>
using namespace std;

class Node {
public:
	int Value;
	Node * Next;
	
	Node(int Val, Node * Nxt = nullptr) {
		Value = Val;
		Next = Nxt;
	}
};

int main(){	 
	Node * firstNode = new Node(10);
	firstNode->Next = new Node(100);
	firstNode->Next->Next = new Node(111,firstNode);
	return 0;
}

A. 上述代码构成单向链表。
B. 上述代码构成双向链表。
C. 上述代码构成循环链表。
D. 上述代码构成指针链表。
【答案】C
【考纲知识点】 循环链表
【解析】本题考察链表的相关知识。第 15 行代码~第 17 行代码创建了三个链表的节点，第一个节点的 next 指向第二个节点，第二个节点的next 指向第三个节点，第三个节点的 next 又指向了第一个节点，形成了一个环，所以是循环链表，正确答案 C 选项。