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

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

A. 输⼊
B. 输出
C. 控制
D. 记录

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)

3、以下不属于面向对象程序设计语言的是（ ）。

A. C++
B. Python
C. Java
D. C

4、下⾯有关 C++类定义的说法，错误的是（ ）。

A. C++类实例化时，会执行构造函数。
B. C++自定义类可以通过定义构造函数实现自动类型转换。
C. C++自定义类可以通过重载 > 、 < 等运算符实现⼤⼩比较。
D. C++自定义类可以包含任意类型的成员。

5、有关下⾯C++代码的说法，错误的是（ ）。

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

class MyStr {
	string data;
public:
	MyStr(string _data): data(_data){}
};
int main(){
	MyStr st("ABC");
	cout << st << endl; 
	return 0;
}

A. 代码 cout << st << endl; 不会报错，将正常输出 ABC 。
B. 第 6 ⾏代码的 data 是 MyStr 类的成员变量。
C. 代码 MyStr st("ABC"); 不会报错，将执⾏构造函数。
D. 以上说法均没有错误。

6、下列关于命名空间的说法错误的是（ ）。

A. 命名空间可以嵌套, 例如 namespace A { namespace B { int i;}} 。
B. 命名空间只可以在全局定义。
C. 命名空间中可以存放变量和函数。
D. 如果程序中使⽤了 using 命令同时引用了多个命名空间，并且命名空间中存在相同的函数，会出现程序运行错误。

7、有关下⾯C++代码的说法，正确的是（ ）。

#include <iostream>

using namespace std;

class ManyData{
	int * __data;
	int head, tail, capacity;
public:
	ManyData(int cap){
		capacity = cap;
		__data = new int[capacity];
		head = tail = 0;
	}
	void push(int val){
		__data[tail++] = val;
	}
	int pop(){
		return __data[--tail];
	}
	int size(){
		return tail - head;
	}
};
int main(){
	auto myData = ManyData(100);
	myData.push(1); 
	myData.push(2); 
	myData.push(3); 
	myData.push(100);
	cout << myData.size() << endl; 
	cout << myData.pop() << endl; 
	return 0;
}

A.这段代码不能正常运行。
B. ManyData 类可⽤于构造队列（Queue）数据结构。
C.在上⾯代码环境，代码 cout<< myData.__data[0] << endl; 可以增加到代码main 函数末尾（ return 0; 之前），且不会导致报错。
D.可以为 ManyData 类的 push() 、 pop() 函数增加异常处理代码，否则在使用ManyData 类时可能导致运⾏时错误或逻辑错误（不⼀定局限于上述代码中的main 函数）。

8、有关下⾯C++代码的说法，错误的是（ ）。

#include <iostream>

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){
		__data[tail++] = val;
		return *this;
	}
	int pop(){
		return __data[head++];
	}
	int size(){
		return tail - head;
	}
};
int main(){
	auto myData = MoreData(100);
	myData.push(1); 
	myData.push(2); 
	myData.push(3); 
	myData.push(11).push(12).push(13);
	cout << myData.pop() << endl;
	return 0;
}

A. MoreData 类可⽤于构造队列（Queue）数据结构。
B. 代码第 29⾏，连续 push() 的⽤法将导致编译错误。
C. __data 是 MoreData 类的私有成员，只能在类内访问。
D. 以上说法均没有错误。

9、某内容仅会出现 ABCDEFG ，其对应的出现概率为0.40、0.30、0.15、0.05、0.04、0.03、0.03，如下图所⽰。按照哈夫曼编码规则，假设B 的编码为11，则 D 的编码为（ ）。

A. 10010
B. 10011
C. 10111
D. 10001

10、下⾯有关格雷码的说法，错误的是（ ）。

A. 在格雷码中，任意两个相邻的代码只有⼀位二进制数不同。B. 格雷码是⼀种唯⼀性编码。
C. 在格雷码中，最⼤数和最⼩数只有⼀位二进制数不同。D. 格雷码是⼀种可靠性编码。

11、有关下图的二叉树，说法正确的是（ ）。

A. 既是完全二叉树也是满二叉树。
B. 既是二叉搜索树也是平衡二叉树。
C. ⾮平衡二叉树。
D. 以上说法都不正确。

12、个节点的二叉搜索树，其查找的平均时间复杂度为（ ）。

A. O(1)
B. O(N)
C. O(log N)
D. O(N^2)

13、青蛙每次能跳 1 或 2 步。下面是青蛙跳到第 N 步台阶C++实现代码。该段代码采用的算法是（ ）。

int jumpFrog(int N){
	if (N <= 3)
		return N;
	return jumpFrog(N - 1) + jumpFrog(N - 2);
}

A. 递推算法
B. 贪⼼算法
C. 动态规划算法
D. 分治算法

14、N 个节点的双向循环链，在其中查找某个节点的平均时间复杂度是（ ）。

A. O(1)
B. O(N)
C. O(log N)
D. O(N^2)

15、关于 C++语⾔，以下说法不正确的是（ ）。

A. 若对象被定义为常量，则它只能调⽤以 const 修饰的成员函数。
B. 所有的常量静态变量都只能在类外进⾏初始化。
C. 若类 A 的对象 a 是类 B 的静态成员变量，则 a 在main() 函数调⽤之前应被初始化。
D. 静态全局对象、常量全局对象都是在 main 函数调用之前完成初始化，执⾏完 main 函数后被析构。

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

1、TCP/IP 的传输层的两个不同的协议分别是 UDP 和 TCP。

2、5G⽹络中，5G 中的 G 表⽰Gigabytes/s，其中 1 GB = 1024 MB。

3、在面向对象中，类是对象的实例。

4、在 C++类的定义中，使⽤ static 修饰符定义的静态成员被该类的所有对象共享。

5、在 C++类的定义中，可以定义初始化函数或运算符函数等。

6、DFS 是深度优先算法的英⽂简写。

7、哈夫曼编码是⼀种有损压缩算法。

8、有些算法或数据结构在 C/C++语⾔中使⽤指针实现，⼀个典型的例⼦就是链表。因此，链表这⼀数据结构在 C/C++语⾔中只能使⽤指针来实现。

9、如果节点数为 N ，⼴度搜索算法的最差时间复杂度为O(N)。

10、二叉搜索树的左右⼦树也是二叉搜索树。

编程题 (每题 25 分，共 50 分)

小杨买饮料

【问题描述】
⼩杨来到了⼀家商店，打算购买⼀些饮料。这家商店总共出售N 种饮料，编号从 0⾄N-1，其中编号为 i 的饮料售价 ci 元，容量 li 毫升。⼩杨的需求有如下⼏点：
1、⼩杨想要尽可能尝试不同种类的饮料，因此他希望每种饮料至多购买1 瓶；
2、⼩杨很渴，所以他想要购买总容量不低于 L 的饮料；
3、⼩杨勤俭节约，所以在 1 和 2 的前提下，他希望使用尽可能少的费用。⽅便起见，你只需要输出最少花费的费用即可。特别地，如果不能满⾜⼩杨的要求，则输出 no solution.
【输入描述】
第⼀⾏两个整数 N, L。
接下来 N ⾏，依次描述第 i= 0,1,…,N-1 种饮料：每⾏两个整数ci , li 。
【输出描述】
输出⼀⾏⼀个整数，表⽰最少需要花费多少钱，才能满足⼩杨的要求。特别地，如果不能满足要求，则输出 no solution 。
【特别提醒】
在常规程序中，输⼊、输出时提供提⽰是好习惯。但在本场考试中，由于系统限定，请不要在输⼊、输出中附带任何提⽰信息。
【样例输入 1】
5 100
100 2000
2 50
4 40
5 30
3 20
【样例输出 1】
9
【样例解释 1】
小杨可以购买 1，2，4 号饮料，总计获得 50+40+20=110 毫升饮料，花费2+4+3=9元。
如果只考虑前两项需求，小杨也可以购买 1，3，4 号饮料，它们的容量总和为50+30+20=100 毫升，恰好可以满足需求。但遗憾的是，这个方案需要花费2+5+3=10 元。
【样例输入 2】
5 141
100 2000
2 50
4 40
5 30
3 20
【样例输出 2】
100
【样例解释 2】
1，2，3，4 号饮料总计 140 毫升，如每种饮料至多购买1 瓶，则恰好无法满足需求，因此只能花费 100 元购买 0 号饮料。
【样例输出 3】
4 141
2 50
4 40
5 30
3 20
【样例解释 3】
no solution
【数据规模】
对于 40% 的测试点，保证 N ≤ 20；1 ≤ L ≤100；li ≤ 100。
对于 70% 的测试点，保证 li ≤ 100。
对于所有测试点，保证 1≤ N ≤ 500；1 ≤ L ≤ 2000；1 ≤ ci, li ≤ 10⁶。

小杨的握手问题

【问题描述】
小杨的班级里共有 N 名同学，学号从 0 至 N-1。
某节课上，老师安排全班同学进行一次握手游戏，具体规则如下：老师安排了一个顺序，让全班 N 名同学依次进入教室。每位同学进入教室时，需要和已经在教室内且学号小于自己的同学握手。
现在，小杨想知道，整个班级总共会进行多少次握手。
【提示】
可以考虑使用归并排序进行降序排序，并在此过程中求解。
【输入描述】
输入包含 2 行。第一行一个整数 N，表示同学的个数；第二行N 个用单个空格隔开的整数，依次描述同学们进入教室的顺序，每个整数在0～N-1 之间，表示该同学的学号。
保证每位同学会且只会进入教室一次。
【输出描述】
输出一行一个整数，表示全班握手的总次数。
【特别提醒】
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任 何提示信息。
【样例输入 1】
4
2 1 3 0
【样例输出 1】
2
【样例解释 1】
2 号同学进入教室，此时教室里没有其他同学。
1 号同学进入教室，此时教室里有 2 号同学。1 号同学的学号小于2 号同学，因此他们之间不需要握手。
3 号同学进入教室，此时教室里有 1，2 号同学。3 号同学的学号比他们都大，因此 3 号同学需要分别和另外两位同学握手。
0 号同学进入教室，此时教室里有 1，2，3 号同学。0 号同学的学号比他们都小，因此 0 号同学不需要与其他同学握手。
综上所述全班一共握手 0+0+2+0=2 次。
【样例输入 2】
6
0 1 2 3 4 5
【样例输出 2】
15
【样例解释 2】
全班所有同学之间都会进行握手，因为每位同学来到教室时，都会发现他的学号是当前教室里最大的，所以他需要和教室里的每位其他同学进行握手。
【数据规模】
对于 30% 的测试点，保证 N ≤ 100。
对于所有测试点，保证 2 ≤ N ≤ 3 × 10⁵。

答案及解析

单选题

1、
【答案】A
【考纲知识点】 计算机基础
【解析】本题属于考察计算机基础知识。手写板是输入设备。

2、
【答案】D
【考纲知识点】 运算表达式和位运算
【解析】本题属于考察运算表达式和位运算知识。b 不等于0，a 是b 的3 倍。A选项中，a 右移 3 位，相当于除以 8；B 是取余运算；如果a=7,b=2,a/b 的结果也等于 3，因为是整型，C 选项也不正确；选 D。

3、
【答案】D
【考纲知识点】 计算机语言
【解析】本题属于考察计算机语言知识。C 是面向过程的设计语言。

4、
【答案】D
【考纲知识点】 类的定义
【解析】本题属于考察 C++类的知识。类中的数据成员的类型可以包含整型、浮点型、字符型、数组、指针和引用等，但不能是抽象类、自身等，故选D。A、B、C 都是基本知识。

5、
【答案】A
【考纲知识点】 类与对象
【解析】本题属于考察 C++类的知识。属于应该输出对象的成员，不能直接输出对象名。

6、
【答案】D
【考纲知识点】 C++类的知识
【解析】本题属于考察 C++类的知识。不同命名空间里可以存在相同函数。

7、
【答案】D
【考纲知识点】 C++类的知识
【解析】本题属于考察 C++类的知识。Push 和 pop 函数没有对数组范围做是否越界判断，因此需要增加异常处理。

8、
【答案】B
【考纲知识点】 C++类的知识
【解析】本题属于考察 C++类的知识。对象指向的数组大小是100，程序中push的元素小于 100，因此不会错误。

9、
【答案】B
【考纲知识点】 数据结构中的哈夫曼树
【解析】本题考察的知识点是数据结构中的哈夫曼，哈夫曼树左边的边权是用0来表示，右边的边权值是 1，通常是左 0 右 1。走到 D 是右左左右右，也就是10011，因此选项是 B。

10、
【答案】B
【考纲知识点】 计算机编码的知识
【解析】本题属于考察计算机编码的知识。格雷码的编码不是唯一的编码。任意两个相邻的代码只有一位二进制数不同,则称这种编码为格雷码。所以不是唯一性编码。

11、
【答案】B
【考纲知识点】 数据结构中树的知识
【解析】本题属于考察数据结构中树的知识。是二叉树，左子树都小于根节点，右子树都大于根节点，是二叉搜索树。左右子树的层差小于等于1，是平衡二叉树。

12、
【答案】C
【考纲知识点】 数据结构中树的知识
【解析】本题属于考察数据结构中树的知识。二叉搜索树每次查找，数据规模平均会减半。

13、
【答案】C
【考纲知识点】
【解析】本题属于考察算法的知识。可以通过动态规划来完成求解完成跳台阶方法，故参考答案是 C。

14、
【答案】B
【考纲知识点】 数据结构中链表的知识
【解析】本题属于考察数据结构中链表的知识。链表查找数据需要遍历整个链表，平均时间复杂度是 B 选项。

15、
【答案】D，B
【考纲知识点】 C++中类的知识
【解析】本题属于考察 C++中类的知识。主要考查常量静态变量和全局变量的初始化。A 和 C 是基本要求。D 选项关注动态初始化时机，但基本类型的全局常量可以在编译时完成初始化设定，说法不准确，是可选答案。但B 的说法可以有如下特例。
class A{
const static int b=1;
};
考虑到考试情况，D 和 B 都算对。

判断题

1、
【答案】正确
【考纲知识点】 计算机网络的知识
【解析】本题是计算机网络的知识，传输层是这 2 个协议。

2、
【答案】错误
【考纲知识点】 计算机网络的知识
【解析】本题是计算机网络的知识，G 是 generation 的简写。

3、
【答案】错误
【考纲知识点】C++的知识
【解析】本题是 C++的知识，对象是类的实例。

4、
【答案】正确
【考纲知识点】 C++类的知识
【解析】本题是 C++类的知识，静态成员可以被该类所有对象访问。

5、
【答案】正确
【考纲知识点】 C++类的知识
【解析】本题是 C++类的知识，定义的内容可以是函数和运算符。

6、
【答案】正确
【考纲知识点】 C++算法的知识
【解析】本题是 C++算法的知识，dfs 是深度优先搜索的简写。

7、
【答案】错误
【考纲知识点】 C++数据结构的知识
【解析】本题是 C++数据结构的知识，有损压缩算法是一种用于压缩数字媒体数据的算法。

8、
【答案】错误
【考纲知识点】 C++数据结构的知识
【解析】本题是 C++数据结构的知识，链表可以用数组实现。

9、
【答案】正确
【考纲知识点】 C++数据结构的知识
【解析】本题是 C++数据结构的知识，广搜最差情况最后一个搜到目标。

10、
【答案】正确
【考纲知识点】 C++数据结构的知识
【解析】本题是 C++数据结构的知识，二叉搜索树的定义，左右子树必须也是符合二叉搜索树的特点。

编程题1

1、
【题目大意】
有 n 种饮料，每种饮料只能选 1 瓶，相当于有 n 瓶饮料，每种饮料只有两种状态：选或者不选，即 0 和 1。选择饮料的升数最高是 L 升，表示有上限。希望尽可能的少花钱，就是求满足条件的最小值。符合 01 背包的问题。
【考纲知识点】
基本运算、输入输出语句、循环、动态规划的知识。
【解题思路】
按题目要求定义好需要的变量，并实现输入；
输入 n 行，每行 2 个整数，分别表示饮料的零售价和升数；初始化边界，买 0 升饮料的费用肯定是 0，其他初始化为最大值；每种饮料都要参与判断，选还是不选，更新 L~0 需要的费用；最终求出 L 升饮料需要的费用。

#include <iostream>

using namespace std;

const int INF = 1000000000;
int cost[2001];
int main(){
	int N = 0, L = 0;
	cin >> N >> L;
	cost[0] = 0;
	for (int i = 1; i <= L; i++)
		cost[i] = INF;
	for (int i = 0; i < N; i++){
		int c = 0, l = 0;
		cin >> c >> l;
		for (int j = L; j >= 0; j--)
			cost[j] = min(cost[j], cost[max(j - 1, 0)] + c);
	}
	if (cost[L] == INF)
		cout << "no solution" << endl;
	else
		cout << cost[L] << endl;
	return 0;
}

编程题2

2、
【题目大意】
有 n 个学生，假设第 i 个学生进入教师，找出前 1~i-1 个学生，哪些人的学号比自己小，小的需要握手，贡献值加 1。
【考纲知识点】
基本运算、输入输出语句、循环、归并排序的知识。
【解题思路】
按题目要求定义好需要的变量，并实现输入；
输入 n 个整数，每个数字分别和前面的数字进行比较，如果大于，贡献值加1。可以用双重循环模拟，找到答案；
因为数据范围是 300000，双重循环会超时。
归并排序可以求逆序对，逆序对是指：i<j,a[i]>a[j]；本题相当于“顺序对”,i>j,a[i]>a[j]，同样可以用归并排序求得，时间复杂度是O(Nlogn)。写归并排序，在排序的过程中，统计数量，求和可得结果。

#include <iostream>

using namespace std;

int num[300000];
int tmp[300000];

long long merge(int l, int r){
	if (l + 1 == r)
		return 0;
	int m = (l + r) / 2;
	long long res = merge(l, m) + merge(m, r);
	
	for (int i = l, j = m, k = l; k < r; k++){
		if (j == r || (i < m && num[i] > num[j])){
			tmp[k] = num[i];
			i++;
		}else{
			tmp[k] = num[j];
			j++;
			res += m - i;
		}
	}
	for (int k = l; k < r; k++)
		num[k] = tmp[k];
	return res;
}
int main(){
	int n = 0;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> num[i];
	cout << merge(0, n) << endl; 
	return 0;
}