CCF编程能力等级认证GESP—C++6级—20230923

单选题（每题 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;
}