首页 › 试卷 › GESP编程能力等级认证 › GESP-C++六级 › 2024年6月CCF-GESP编程能力等级认证C++编程六级真题

2024年6月CCF-GESP编程能力等级认证C++编程六级真题 VIP

GESP-C++六级 共 27 题 2024 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、单选题

1. 单选题

面向对象的编程思想主要包括( )原则。

  • A 贪心、动态规划、回溯
  • B 并发、并行、异步
  • C 递归、循环、分治
  • D 封装、继承、多态
查看答案与解析
答案:D
解析:

面向对象的编程思想(OOP)主要包括多态、继承和封装原则。

多态:多态允许程序在运行时根据对象的实际类型来选择执行的方法,增加了代码的灵活性和可扩展性。

继承:通过继承,子类可以扩展父类的功能,而不需要重新编写已有的代码,提高了代码的复用性和维护性。

封装:封装隐藏了对象的内部状态,只提供必要的操作接口,保护对象数据不被外部直接访问,同时确保了数据的安全性和完整性。

这些原则共同构成了面向对象编程的核心,使得代码更加模块化、可重用、可维护和可扩展

2. 单选题

运行下列代码,屏幕上输出( )。

#include <iostream>
using namespace std;

class my_class {
public:
	static int count;
	my_class() {
		count++;
	}
	~my_class() {
		count--;
	}
	static void print_count() {
		cout << count << " ";
	}
};
int my_class::count = 0;
int main() {
	my_class obj1;
	my_class::print_count();
	my_class obj2;
	obj2.print_count();
	my_class obj3;
	obj3.print_count();
	return 0;
}
  • A 1 1 1
  • B 1 2 3
  • C 1 1 2
  • D 1 2 2
查看答案与解析
答案:B
解析:

构造函数my_class()在对象obj实例化时自动调用,静态局部变量count在程序执行到该对象的声明处时被首次初始化为0,在以后的函数调用不再进行初始化;因此后续调用print_count()方法时,输出count依次自增的结果,程序输出结果为1 2 3,另外析构函数~my_class()会在对象结束调用时做“清理善后” 的工作,即程序结束时,会自动调用三次~my_class()方法,因此最终程序结束时,count的值为0。

3. 单选题

运行下列代码,屏幕上输出( )。

#include <iostream>
using namespace std;

class shape {
protected:
	int width, height;
public:
	shape(int a = 0, int b = 0) {
		width = a;
		height = b;
	}
	virtual int area() {
		cout << "parent class area: " <<endl;
		return 0;
	}
};

class rectangle: public shape {
public:
	rectangle(int a = 0, int b = 0) : shape(a, b) { }
	
	int area () {
		cout << "rectangle area: ";
		return (width * height);
	}
};

class triangle: public shape {
public:
	triangle(int a = 0, int b = 0) : shape(a, b) { }
	
	int area () {
		cout << "triangle area: ";
		return (width * height / 2);
	}
};
int main() {
	shape *pshape;
	rectangle rec(10, 7);
	triangle tri(10, 5);
	
	pshape = &rec;
	pshape->area();
	
	pshape = &tri;
	pshape->area();
	return 0;
}
  • A rectangle area: triangle area:
  • B parent class area: parent class area:
  • C 运行时报错
  • D 编译时报错
查看答案与解析
答案:A
解析:

主函数实例化两个对象rectangle rec 和triangle tri,pshape调用rec的area()方法,输出了rectangle area:,之后pshape调用tri的area()方法,输出了triangle area:

4. 单选题

向一个栈顶为hs的链式栈中插入一个指针为s的结点时,应执行( )。

  • A hs->next = s;
  • B s->next = hs; hs = s;
  • C s->next = hs->next; hs->next = s;
  • D s->next = hs; hs = hs->next;
查看答案与解析
答案:B
解析:

指针之间的赋值:A=B可以理解为A指向B,栈的结构为先进后出,因此S需要作为栈顶存在,hs需要指向S,即hs=s;但是在此之前,需要将S链接到hs,即S的下一个指针指向S,有S->next=hs;

5. 单选题

在栈数据结构中,元素的添加和删除是按照什么原则进行的?

  • A 先进先出
  • B 先进后出
  • C 最小值先出
  • D 随机顺序
查看答案与解析
答案:B
解析:

栈的元素添加原则为先进后出(后进先出)。

6. 单选题

要实现将一个输入的十进制正整数转化为二进制表示,下面横线上应填入的代码为( )。

#include <iostream>
using namespace std;

stack<int> ten2bin(int n) {
	stack<int> st;
	int r, m;
	
	r = n % 2;
	m = n / 2;
	st.push(r);
	
	while (m != 1) {
		r = m % 2;
		st.push(r);
		m = m / 2;
	}
	st.push(m);
	return st;
}

int main() {
	int n;
	cin >> n;
	stack<int> bin;
	bin = ten2bin(n);
	while (!bin.empty()) {
		_____________________ // 在此处填入代码
	}
	return 0;
}
  • A cout << bin.top(); bin.pop();
  • B bin.pop(); cout << bin.top();
  • C cout << bin.back(); bin.pop();
  • D cout << bin.front(); bin.pop();
查看答案与解析
答案:A
解析:

如果对十进制X进行拆位:每次用%10取得最低位,同时/10去除最低位,用栈即可得到从个位到高位的各个位,不停弹出即可正常输出十进制的每一位,这个过程可以理解为将十进制转化为二进制,如果将%10 /10 改为%2 /2,那么这就相当于将十进制转化为二进制。

代码中ten2bin()就是拆分各个位并返回栈st,bin接收值后,按照栈的弹出规则依次输出即可,因此答案选B.

7. 单选题

下面定义了一个循环队列的类,请补全判断队列是否满的函数,横向上应填写( )。

#include <iostream>
using namespace std;

class circular_queue {
private:
	int *arr; // 数组用于存储队列元素
	int capacity; // 队列容量
	int front; // 队头指针
	int rear; // 队尾指针
	
public:
	circular_queue(int size) {
		capacity = size + 1; // 为了避免队列满时与队列空时指针相等的情况,多预留一个空间
		arr = new int[capacity];
		front = 0;
		rear = 0;
	}
	
	~circular_queue() {
		delete[] arr;
	}
	
	bool is_empty() {
		return front == rear;
	}
	
	bool is_full() {
		________________ // 在此处填入代码
	}
	
	void en_queue(int data) {
		if (is_full()) {
			cout << "队列已满,无法入队!" << endl;
			return -1;
		}
		arr[rear] = data;
		rear = (rear + 1) % capacity;
		return 1;
	}
	
	int de_queue() {
		if (is_empty()) {
			cout << "队列为空,无法出队!" << endl;
			return -1; // 出队失败,返回一个特殊值
		}
		int data = arr[front];
		front = (front + 1) % capacity;
		return data;
	}
};
  • A return (rear + 1) % capacity == front;
  • B return rear % capacity == front;
  • C return rear == front;
  • D return (rear + 1) == front;
查看答案与解析
答案:A
解析:

判断循环队列是否为满可以让队列的rear指针加1之后对capacity取模结果等于front指针,这时表明队列已满,反之则未满。

8. 单选题

对“classmycls”使用哈夫曼(Huffman)编码,最少需要( )比特。

  • A 10
  • B 20
  • C 25
  • D 30
查看答案与解析
答案:C
解析:

按照哈夫曼编码规则进行建树,如图,按照左0右1的二进制格式编码,可以得到每个字符的编码:

length©=length(S)=length(L)=2,length(A)=3,length(Y)=length(M)=4

经过计算可以得到classmycls的总长=2+2+3+2+2+4+4+2+2+2=25。

9. 单选题

二叉树的( )第一个访问的节点是根节点。

  • A 先序遍历
  • B 中序遍历
  • C 后序遍历
  • D 以上都是
查看答案与解析
答案:A
解析:

先序遍历先根再左子树再右子树,中序遍历先左子树再根再右子树,后序遍历先左子树再右子树再根。

10. 单选题

一棵5层的满二叉树中节点数为( )。

  • A 31
  • B 32
  • C 33
  • D 16
查看答案与解析
答案:A
解析:

一个K层的满二叉树的节点个数为1+2+4+……+2k-1=2k-1 (等比数列/二进制)。

11. 单选题

在求解最优化问题时,动态规划常常涉及到两个重要性质,即最优子结构和( )。

  • A 重叠子问题
  • B 分治法
  • C 贪心策略
  • D 回溯算法
查看答案与解析
答案:A
解析:

动态规划的性质主要包括最优子结构、无后效性和有重叠子问题

最优子结构:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。这意味着问题的最优解可以通过其子问题的最优解来构建。

无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。这一性质确保了动态规划方法的有效性,因为当前阶段的选择不会影响到之前阶段的状态。

有重叠子问题:子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。这一性质是动态规划算法能够通过存储和重用子问题的解来提高效率的关键。

12. 单选题

青蛙每次能跳1或2步,下面代码计算青蛙跳到第n步台阶有多少种不同跳法。则下列说法,错误的是( )。

int jump_recur(int n) {
	if (n == 1) return 1;
	if (n == 2) return 2;
	return jump_recur(n - 1) + jump_recur(n - 2);
}

int jump_dp(int n) {
	vector<int> dp(n + 1); // 创建一个动态规划数组,用于保存已计算的值
	// 初始化前两个数
	dp[1] = 1;
	dp[2] = 2;
	// 从第三个数开始计算斐波那契数列
	for (int i = 3; i <= n; ++i) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n];
}


  • A 函数jump_recur()采用递归方式。
  • B 函数jump_dp()采用动态规划方法。
  • C 当n较大时,函数jump_recur()存在大量重复计算,执行效率低。
  • D 函数jump_recur()代码量小,执行效率高。
查看答案与解析
答案:D
解析:

状态表示:dp[i]表示青蛙到达第i个台阶的跳法。

状态转移方程:第i个台阶由两个状态转移过来①i-2级跳两步②i-1级跳一部,因此状态转移方程为:dp[i]=dp[i-1]+dp[i-2]

目标状态:dp[n]

int jump_recur(int n)使用递归方式(斐波那契),无记忆化,因此复杂度为指数。

int jump_dp(int n)使用动规(递推)方式,复杂度O(n).

13. 单选题

阅读以下二叉树的广度优先搜索代码:

#include <iostream>
#include <queue>

using namespace std;

// 二叉树节点的定义
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 宽度优先搜索(BFS)迭代实现
TreeNode* bfs(TreeNode* root, int a) {
	if (root == nullptr) return nullptr;
	
	queue<TreeNode*> q;
	q.push(root);
	
	while (!q.empty()) {
		TreeNode* node = q.front();
		q.pop();
		
		if (node->val == a)
			return node;
		cout << node->val << " "; // 先访问当前节点
		if (node->left) q.push(node->left); // 将左子节点入队
		if (node->right) q.push(node->right); // 将右子节点入队
	}
	return nullptr;
}

使用以上算法,在以下这棵树搜索数值20时,可能的输出是( )。

  • A 5 2 -4 3 17 9
  • B -4 2 3 5 9 17
  • C 5 2 17 -4 3 9
  • D 以上都不对
查看答案与解析
答案:C
解析:

该程序使用广搜方式,因此为二叉树层序遍历,答案选C

14. 单选题

同上题中的二叉树,阅读以下二叉树的深度优先搜索代码:

#include <iostream>
#include <stack>

using namespace std;

// 非递归深度优先搜索(DFS)
TreeNode* dfs(TreeNode* root, int a) {
	if (root == nullptr) return nullptr;
	
	stack<TreeNode*> stk;
	stk.push(root);
	
	while (!stk.empty()) {
		TreeNode* node = stk.top();
		stk.pop();
		if (node->val == a)
			return node;
			
		cout << node->val << " "; // 访问当前节点
		
		if (node->right) stk.push(node->right); // 先压入右子节点
		if (node->left) stk.push(node->left); // 再压入左子节点
	}
	return nullptr;
}

使用以上算法,在二叉树搜索数值20时,可能的输出是( )。

  • A 5 2 -4 3 17 9
  • B -4 2 3 5 9 17
  • C 5 2 17 -4 3 9
  • D 以上都不对
查看答案与解析
答案:A
解析:

该题目使用栈代替了DFS的递归形式,由输出和push的顺序,可以知道该题目为先序遍历,因此答案为A。

15. 单选题

在上题的树中搜索数值3时,采用深度优先搜索一共比较的节点数为( )。

  • A 2
  • B 3
  • C 4
  • D 5
查看答案与解析
答案:C
解析:

该二叉树中序遍历有序,同时从构造形态上,为一棵二叉排序树,但是程序并不是按照二叉排序树的规则,题目是先序遍历比较,因此比较的节点依次为:5、2、-4、3,共4次。

二、判断题

16. 判断题

哈夫曼编码本质上是一种贪心策略。(2024.6-6)

  • A对
  • B错
查看答案与解析
答案:对
解析:

哈夫曼编码原理为贪心。

17. 判断题

创建一个对象时,会自动调用该对象所属类的构造函数。如果没有定义构造函数,编译器会自动生成一个默认的构造函数。

  • A对
  • B错
查看答案与解析
答案:对
解析:

如果一个类中声明成员都没有,我们简称为空类。但是空类中并不是真的什么都没有,即使我们什么都不写,类中也会自动生成6个默认成员函数。

默认成员函数其实就相当于缺省成员函数。如果不写就会编译器默认生成的,写了编译器就不会生成。

18. 判断题

定义一个类时,必须手动定义一个析构函数,用于释放对象所占用的资源。

  • A对
  • B错
查看答案与解析
答案:错
解析:

由上一题,析构函数编译器会默认生成。

19. 判断题

C++中类内部可以嵌套定义类。

  • A对
  • B错
查看答案与解析
答案:对
解析:

在C++中,类可以在另一个类的内部定义,这种类被称为嵌套类或内部类。内部类可以访问外部类的所有成员,包括私有成员。

20. 判断题

000, 001, 011, 010, 110, 111, 101, 100是一组格雷码。

  • A对
  • B错
查看答案与解析
答案:对
解析:

格雷码的特点为:相邻的两个格雷码,只有一位二进制是不同的。且首尾元素也遵循。

21. 判断题

n个节点的双向循环链表,在其中查找某个节点的平均时间复杂度是O(logn)。

  • A对
  • B错
查看答案与解析
答案:错
解析:

考察数据结构中链表的知识。查找数据 平均时间复杂度是O(n).

22. 判断题

完全二叉树可以用数组存储数据。

  • A对
  • B错
查看答案与解析
答案:对
解析:

完全二叉树比较平衡,因此可以从1开始编号作为根,后续每个节点i,其左右两个孩子的下标为2i,和2i+1。

23. 判断题

在C++中,静态成员函数只能访问静态成员变量。

  • A对
  • B错
查看答案与解析
答案:对
解析:

在C++中,静态成员函数只能访问静态成员变量。这是因为非静态成员变量属于类的对象,而静态成员变量属于类本身。当一个类的实例没有被创建时,非静态成员变量不存在,所以静态成员函数不能访问它们。

24. 判断题

在深度优先搜索中,通常使用队列来辅助实现。

  • A对
  • B错
查看答案与解析
答案:错
解析:

深度优先搜索通常递归方式实现,可以用栈代替递归方式。

25. 判断题

对0-1背包问题,贪心算法一定能获得最优解。

  • A对
  • B错
查看答案与解析
答案:错
解析:

贪心无法得到0-1背包最优解,这是因为部分闲置的空间降低了总体的价值。

三、简答题

26. 简答题

计算得分

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨想要计算由m个小写字母组成的字符串的得分。

小杨设置了一个包含n个正整数的计分序列A=[a1,a2,...,an],如果字符串的一个子串由k(1≤k≤n) 个 abc 首尾相接组成,那么能够得到分数ak,并且字符串包含的字符不能够重复计算得分,整个字符串的得分是计分子串的总和。

例如,假设a=3,字符串 dabcabcabcabzabc 的所有可能计分方式如下:d+abc+abcabc+abz+abc 或者 d+abcabc+abc+abz+abc,其中 d 和 abz 不计算得分,总得分为a1+a2+a1d+abc+abc+abc+abz+abc,总得分为a1+a1+a1+a1d+abcabcabc+abz+abc,总得分为a3+a1

小杨想知道对于给定的字符串,最大总得分是多少。

输入格式

第一行包含一个正整数n,代表计分序列 A 的长度。

第二行包含 n 个正整数,代表计分序列A。

第三行包含一个正整数m,代表字符串的长度。

第四行包含一个由 m 个小写字母组成的字符串。

输出格式

输出一个整数,代表给定字符串的最大总得分。


输入样例

3
3 1 2
13
dabcabcabcabz

输出样例

9

样例解释

最优的计分方式为 d+abc+abc+abc+abz,总得分为a1+a1+a1,共9 分。

数据范围

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; const int N = 1e5+10; int a[30]; string s; int dp[N]; int main(){ int n; cin&gt;&gt;n; for(int i=1;i&lt;=n;i++){ cin&gt;&gt;a[i]; } int m; cin&gt;&gt;m; cin&gt;&gt;s; for(int i=1;i&lt;=m;i++){ dp[i]=dp[i-1]; for(int j=1;j&lt;=n;j++){ if(i-3*j+1&lt;=0)break; int l = i-3*j+1; if(s.substr(l-1,3)=="abc"){ dp[i]=max(dp[i],dp[l]+a[j]); }else break; } } cout&lt;&lt;dp[m]&lt;&lt;"\n"; }</pre>
解析:

20分思路,考虑到ai>=ai+1,此时将abc单独算是最多的,答案为A[1]*abc的个数。

满分思路

状态表示:DP[i]表示前i个字符组成的最大得分。

状态转移方程:

对第i个字符,有两种情况:①不作为答案的一部分。②作为abc的一部分对答案产生贡献;

对于①:DP[i]=DP[i-1] (也可以理解为将i-1的答案顺延到i),这保证了答案为DP[m]

对于②:前i个字符中,最后一个位置作为“abc”,可以考虑用连续的j个abc连接更新答案;

此时i-3*j+1 ~i的范围都为连续的j个abc,产生的代价为A[j]

DP[i]=DP[i-3*j]+A[j]

①和②构成了答案的所有解

有:DP[i]=max(DP[i-1],max(DP[i-3j]+A[j]); i-3j+1>=1

27. 简答题

二叉树

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一棵包含n个节点的二叉树,且根节点的编号为1。这棵二叉树任意一个节点要么是白色,要么是黑色。之后小杨会对这棵二叉树进行q次操作,每次小杨会选择一个节点,将以这个节点为根的子树内所有节点的颜色反转,即黑色变成白色,白色变成黑色。

小杨想知道q次操作全部完成之后每个节点的颜色。

输入格式

第一行一个正整数n,表示二叉树的节点数量。

第二行n−1个正整数,第i(1≤i≤n−1) 个数表示编号为i+1 的节点的父亲节点编号,数据保证是一棵二叉树。

第三行一个长度为n的01 串,从左到右第i(1≤i≤n) 位如果为0,表示编号为i的节点颜色为白色,否则为黑色。

第四行一个正整数q,表示操作次数。

接下来q行每行一个正整数ai(1≤ai≤n),表示第i次操作选择的节点编号。

输出格式

输出一行一个长度为n的01 串,表示q次操作全部完成之后每个节点的颜色。从左到右第i(1≤i≤n) 位如果为0,表示编号为i的节点颜色为白色,否则为黑色。


输入样例

6
3 1 1 3 4
100101
3
1
3
2

输出样例

010000

样例解释

第一次操作后,节点颜色为:011010

第二次操作后,节点颜色为:000000

第三次操作后,节点颜色为:010000

数据范围

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; const int N = 1e5+10; int n; int son[N][2]; int f[N],col[N],sum[N]; void dfs(int x,int now){ now+=sum[x]; if(now&amp;1)col[x]^=1; for(int i=0;i&lt;2;i++){ if(son[x][i]!=-1)dfs(son[x][i],now); } } int main(){ cin&gt;&gt;n; memset(son,-1,sizeof son); for(int i=2;i&lt;=n;i++){ cin&gt;&gt;f[i]; for(int j=0;j&lt;2;j++){ if(son[f[i]][j]==-1){ son[f[i]][j]=i; break; } } } string s; cin&gt;&gt;s; for(int i=1;i&lt;=n;i++){ col[i]=s[i-1]-'0'; } int q; cin&gt;&gt;q; while(q--){ int x; cin&gt;&gt;x; sum[x]+=1; } dfs(1,0); for(int i=1;i&lt;=n;i++){ cout&lt;&lt;col[i]; } cout&lt;&lt;"\n"; }</pre>
解析:

①比较朴素的思路为建树,每次操作时执行DFS,将操作的结果处理,最终输出每个节点颜色,极端情况下每次操作遍历整棵树的话,复杂度O(nq),只能解决40%的数据。

②考虑到程序只要最终结果,因此中间结果没必要完全求得,取反操作的周期为2,具有奇偶性,因此每次操作X时,将X的位置打个标记,表示其将影响X下方的每个节点翻转一次,当所有操作标记完,执行DFS,从root=1出发,统计到达每个节点X时的标记的数量cnt,如果cnt为奇数,则改点颜色取反,否则保持原来颜色。这样只需要O(n+q)的复杂度。