首页 › 题库 › GESP编程能力等级认证 › 1.1 树的基本概念

GESP-C++六级 题库

共 95 道题 ,第 3 / 5 页 · 按题型筛选,点「查看答案」核对解析
章节 1.1 树的基本概念 清除
41 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

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

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

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

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

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

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

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

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

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

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

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

A

最小权值的节点

B

最大权值的节点

C

随机节点

D

深度最深的节点

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

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

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

下面有关树的存储,错误的是(   )。

A

完全二叉树可以用 list 存储

B

一般二叉树都可以用 list 存储,空子树位置可以用 None 表示

C

满二叉树可以用 list 存储

D

树数据结构,都可以用 list 存储

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

构造二叉树 [1,2,3,null,4] (   )。

A

1(2()(4))(3)

B

1(2(3)())(4)

C

(1,2(3),(4))

D

(1,(2)(3),(4))

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

有关下图的二叉树,说法正确的是(     )。

A
既是完全二叉树也是满二叉树。
B
既是二叉搜索树也是平衡二叉树。
C
非平衡二叉树。
D
以上说法都不正确。
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
53 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

N个节点的二叉搜索树,其查找的平均时间复杂度为(     )。

A
A.O(1)
B
B.O(N)
C
C.O(logN)
D
D.O(N2)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
54 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

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

A
O(1)
B
O(N)
C
O(logN)
D
O(N2)
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
55 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

以下代码能够正确统计二叉树中叶子结点的数量。

int countLeaf(TreeNode* root) {
    if (!root) 
        return 0;
    if (!root->left && !root->right) 
        return 1;
    return countLeaf(root->left) + countLeaf(root->right);
}
A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
56 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

广度优先遍历二叉树可用栈来实现。2025.12-6

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
57 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

在二叉排序树(BST)中,若某结点的左子树为空,则该结点一定是整棵树中的最小值结点。2025.12-6

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
58 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

下面的函数能正确判断一棵树是不是二叉排序树(左边的数字要比当前数字小,右边的数字要比当前数字大)。

bool isBST(TreeNode* root, int minVal, int maxVal) {
    if (!root) 
        return true;
    if (root->val <= minVal || root->val >= maxVal)
        return false;
    return isBST(root->left, minVal, root->val) &&
           isBST(root->right, root->val, maxVal);
}
A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
59 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

假定只有一个根节点的树的深度为1,则一棵有 n 个节点的完全二叉树,则树的深度为 log2(n)+1

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
60 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

一个含有 100个节点的完全二叉树,高度为 。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情