GESP-C++六级 题库

共 136 道题 ,第 3 / 7 页 · 按题型筛选,点「查看答案」核对解析
41 单选题 适中 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

题目详情
42 单选题 适中 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。

题目详情
43 单选题 适中 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
这道题暂未补解析。
题目详情
44 单选题 适中 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
这道题暂未补解析。
题目详情
45 单选题 适中 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

题目详情
46 单选题 适中 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;

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

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

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

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

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

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

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

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

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

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

#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

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

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

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

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

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

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

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

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

在构建哈夫曼树时,每次应该选择(   )合并。

A

最小权值的节点

B

最大权值的节点

C

随机节点

D

深度最深的节点

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
53 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

以下代码希望能在一棵二叉排序树中搜索特定的值,请在横线处填入(   ),使其能正确实现相应功能。

TreeNode* search(TreeNode* root, int target) {
	if (root == NULL || root->val == target) {
		return root;
	}
	if (_______________) {
		return search(root->left, target);
	} else {
		return search(root->right, target);
	}
}
A
target < root->left
B
target < root->val
C
target > root->val
D
target > root->left
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
54 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

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

void bfs(TreeNode* root) {
	if (root == NULL) {
		return;
	}
	queue<TreeNode*> q;
	q.push(root);
	while (!q.empty()) {
		TreeNode* current = q.front();
		q.pop();
		cout << current->val << " ";
		if (current->left) {
			q.push(current->left);
		}
		if (current->right) {
			q.push(current->right);
		}
	}
}

使用以上算法遍历以下这棵树,可能的输出是(   )。

A
1 2 8 9 4 5 3 6 7 10 11
B
1 2 3 4 5 6 7 8 9 10 11
C
1 2 3 8 9 6 4 5 7 10 11
D
1 2 3 8 9 4 5 6 7 10 11
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
55 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

一个有 124 个叶子节点的完全二叉树,最多有(   )个结点。

A
247
B
248
C
249
D
250
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
56 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

若一棵二叉树的先序遍历为:A, B, D, E, C, F、中序遍历为:D, B, E, A, F, C,它的后序遍历为(   )。

A
D, E, B, F, C, A
B
E, D, B, F, C, A
C
D, E, B, C, F, A
D
E, D, B, C, F, A
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
57 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 综合练习

线性筛法与埃氏筛法相比的优势是(   )。

A
更容易实现
B
更节省内存
C
更快速
D
更准确
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
58 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 综合练习

有关下面C++代码的说法,错误的是(   )。

A

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

B

在类中定义的类被称为内部类,定义类的类被称为外部类

C

内部类可以随便访问,不需要通过外部类来访问

D

代码中 Point 被称为内部类,可以通过外部类 Rectangle 来访问, Rectangle::Point

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
59 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 综合练习

有关下面C++代码的说法,正确的是(   )。

A

第14行代码错误,第15行正确

B

第15行代码错误,第14行代码正确

C

第14、15两行代码都正确

D

第6行代码可修改为 objCounter += 1

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
60 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 综合练习

有关下面C++代码的说法,错误的是(   )。

A

上列C++代码适用于构造各种二叉树

B

代码 struct BiNode 用于构造二叉树的节点

C

代码 BiTree(){root=Creat();} 用于构造二叉树

D

析构函数不可以省略

答案与解析
正确答案:D
这道题暂未补解析。
题目详情