首页 › 题库 › GESP编程能力等级认证 › GESP-C++六级

GESP-C++六级 题库

共 270 道题 ,第 5 / 14 页 · 按题型筛选,点「查看答案」核对解析
81 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.2 哈夫曼树

假设字母表 {a,b,c,d,e} 在字符串出现的频率分别为 10%,15%,30%,16%,29%。若使用哈夫曼编码方式对字母进行二进制编码,则字符 abcdef 分别对应的一组哈夫曼编码的长度分别为( )。(2024.9-6)

A
4, 4, 1, 3, 2
B
3, 3, 2, 2, 2
C
3, 3, 1, 2, 1
D
4, 4, 1, 2, 2
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
82 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 2.1 格雷编码

以下C++代码实现 n nn 位的格雷码,则横线上应填写( )。

#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 生成 n 位的格雷码
vector<string> generate_graycode(int n) {
	vector<string> graycode_list;
	if (n <= 0) {
		return graycode_list;
	}
	
	// 初始1位格雷码
	graycode_list.push_back("0");
	graycode_list.push_back("1");
	
	// 迭代生成 n 位的格雷码
	for (int i = 2; i <= n; i++) {
		int current_size = graycode_list.size();
		
		for (int j = current_size - 1; j >= 0; j--) {
			graycode_list.push_back("1" + graycode_list[j]);
		}
		
		for (int j = 0; j < current_size; j++) {
			———————————————————————— // 在此处填入代码
		}
	}
	return graycode_list;
}


A
graycode_list.push_back(“0” + graycode_list[j]);
B
graycode_list[j] = “0” + graycode_list[j];
C
graycode_list.push_back(“1” + graycode_list[j]);
D
graycode_list[j] = “1” + graycode_list[j];
答案与解析
正确答案:B

格雷码(Gray code)是一种相邻两个代码之间只有单个比特不同的二进制数字系统。要生成n位的格雷码,可以通过迭代的方式生成更长的格雷码序列。在这段代码中,首先生成了1位的格雷码,即"0"和"1"。然后通过迭代,每次都将现有的格雷码列表翻倍,并且在新加入的格雷码前加上不同的前缀来保证相邻格雷码之间的差异性。在每一轮迭代中,首先将现有的格雷码序列反转并加上前缀"1",然后原有的格雷码序列加上前缀"0"。

仔细观察,可以看到第一个循环是从末尾向前遍历,将’1’添加到现有元素的前面。这意味着,对于第二个循环,我们应该从头部开始遍历,同样将’0’添加到现有元素的前面,所以选B而不是选A。

题目详情
83 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

给定一棵二叉树,其前序遍历结果为:ABDECFG,中序遍历结果为:DEBACFG,则这棵树的正确后序遍历结果是( )。(2024.9-6)

A
EDBGFCA
B
EDGBFCA
C
DEBGFCA
D
DBEGFCA
答案与解析
正确答案:A

在前序遍历中找根,在中序遍历中找根的左右子树,建好树后进行后序遍历。

题目详情
84 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

一棵有 n 个结点的完全二叉树用数组进行存储与表示,已知根结点存储在数组的第 1 个位置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点,则它的兄弟结点和右子结点的位置分别是( )。(2024.9-6)

A
8, 18
B
10, 18
C
8, 19
D
10, 19
答案与解析
正确答案:C

完全二叉树兄弟结点一般是左偶右奇,9号结点的兄弟结点只能是8号,而右子结点即9*2+1 = 19,选C

题目详情
85 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

二叉树的深度定义为从根结点到叶结点的最长路径上的结点数,则以下基于二叉树的深度优先搜索实现的深度计算函数中横线上应填写( )。

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

// 计算二叉树的深度
int max_depth(tree_node* root) {
	if (root == nullptr) {
		return 0; // 如果根结点为空,则深度为 0
	}
	
	int left_depth = max_depth(root->left);
	int right_depth = max_depth(root->right);
	
	———————————————————————— // 在此处填入代码
}
A
return left_depth + right_depth;
B
return max(left_depth, right_depth);
C
return max(left_depth, right_depth) + 1;
D
return left_depth + right_depth + 1;
答案与解析
正确答案:C

代码的思路是计算出当前根结点左子树的深度,右子树的深度,那么以根结点为子树的深度即max(左子树,右子树)+1,+1即将根结点的深度也计算在内,所以选C。

题目详情
86 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

上一题的二叉树深度计算还可以采用二叉树的广度优先搜索来实现。以下基于二叉树的广度优先搜索实现的深度计算函数中横线上应填写( )。

#include <queue>
int max_depth_bfs(tree_node* root) {
	if (root == nullptr) {
		return 0; // 如果树为空,深度为 0
	}
	
	queue <tree_node*> q;
	q.push(root);
	int depth = 0;
	
	// 使用队列进行层序遍历
	while (!q.empty()) {
		———————————————————————— // 在此处填入代码
		for (int i = 0; i < level_size; ++i) {
			tree_node* node = q.front();
			q.pop();
			
			if (node->left) {
				q.push(node->left);
			}
			if (node->right) {
				q.push(node->right);
			}
		}
	}
	
	return depth;
}
A
int level_size = q.size(); depth++;
B
int level_size = 2; depth++;
C
int level_size = q.size(); depth += level_size;
D
int level_size = 2; depth += level_size;
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
87 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

二叉搜索树中的每个结点,其左子树的所有结点值都小于该结点值,右子树的所有结点值都大于该结点值。以下代码对给定的整数数组(假设数组中没有数值相等的元素),构造一个对应的二叉搜索树,横线上应填写():

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

// 插入结点到二叉搜索树中
tree_node* insert(tree_node* root, int val) {
	if (root == nullptr) {
		return new tree_node(val);
	}
	
	———————————————————————— // 在此处填入代码
	
	return root;
}

// 根据给定数组构造二叉搜索树
tree_node* constructBST(const int arr[], int size) {
	tree_node* root = nullptr;
	
	for (int i = 0; i < size; ++i) {
		root = insert(root, arr[i]);
	}
	return root;
}
A
if (val < root->val)
	root->left = insert(root->left, val);
else
	root->right = insert(root->right, val);
B
if (val > root->val)
	root->left = insert(root->left, val);
else
	root->right = insert(root->right, val);
C
if (val < root->val)
	root->left = insert(root, val);
else
	root->right = insert(root, val);
D
if (val > root->val)
	root->left = insert(root, val);
else
	root->right = insert(root, val);
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
88 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

对上题中的二叉搜素树,当输入数组为[5,3,7,2,4,6,8] 时,构建二叉搜索树,并采用如下代码实现的遍历方式,得到的输出是( )。

#include <iostream>
using namespace std;

// 遍历二叉搜索树,输出结点值
void traversal(tree_node* root) {
	if (root == nullptr) {
		return;
	}
	
	traversal(root->left);
	cout << root->val << " ";
	traversal(root->right);
}


A
5 3 7 2 4 6 8
B
2 3 4 5 6 7 8
C
2 4 3 6 8 7 5
D
2 4 3 5 6 7 8
答案与解析
正确答案:B

根据输入数组建BST,然后根据 “左根右”的遍历规则输出为: 2 3 4 5 6 7 8,选B

题目详情
89 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

动态规划通常用于解决( )。(2024.9-6)

A
无法分解的问题
B
可以分解成相互依赖的子问题的问题
C
可以通过贪心算法解决的问题
D
只能通过递归解决的问题
答案与解析
正确答案:B

一个问题是否能用DP来解决我们的考虑一般有两点:① 最优子结构,②无后效性

最优子结构即 选项中B的可分解成相互依赖的子问题的问题,因此选B。

题目详情
90 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

阅读以下用动态规划解决的0-1背包问题的函数,假设背包的容量 W 是10kg,假设输入4个物品的重量weights 分别为1,3,4,6(单位为kg),每个物品对应的价值values 分别为20,30,50,60,则函数的输出为( )。

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

// 0/1背包问题
int knapsack(int W, const vector<int>& weights, const vector<int>& values, int n) {
	vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
	
	for (int i = 1; i <= n; ++i) {
		for (int w = 0; w <= W; ++w) {
			if (weights[i - 1] <= w) {
				dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
			}
			else
			{
				dp[i][w] = dp[i - 1][w];
			}
		}
	}
	
	return dp[n][W];
}


A
90
B
100
C
110
D
140
答案与解析
正确答案:C

01背包问题,dp[n][w]表示将前n个物品放入容量为w的背包中得到的最大价值,4个物品的重量为1 3 4 6,价值为20 30 50 60,背包容量为10,最大价值是1 3 6 对应的110。

题目详情
91 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 5.1 面向对象思想

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

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

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

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

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

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

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

题目详情
92 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 5.1 面向对象思想

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

#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。

题目详情
93 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 5.1 面向对象思想

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

#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:

题目详情
94 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

向一个栈顶为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;

题目详情
95 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 6.1 栈

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

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

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

题目详情
96 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 6.1 栈

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

#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.

题目详情
97 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 5.1 面向对象思想

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

#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指针,这时表明队列已满,反之则未满。

题目详情
98 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 5.1 面向对象思想

对“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。

题目详情
99 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

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

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

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

题目详情
100 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

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

A
31
B
32
C
33
D
16
答案与解析
正确答案:A

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

题目详情