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

GESP-C++六级 题库

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

以下代码实现了树的哪种遍历方式?( )

void traverse(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << " ";
    traverse(root->left);
    traverse(root->right);
}
A
前序遍历
B
中序遍历
C
后序遍历
D
层次遍历
答案与解析
正确答案:A

树的遍历主要方式:

前序遍历:访问顺序:根节点 → 左子树 → 右子树。

中序遍历:访问顺序:左子树 → 根节点 → 右子树。

后序遍历:访问顺序:左子树 → 右子树 → 根节点。

这段代码实现了树的 前序遍历(根→左→右)。

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

以下关于完全二叉树的代码描述,正确的是?( )

bool isCompleteTree(TreeNode* root) {
    if (root == nullptr) return true;
    queue<TreeNode*> q;
    q.push(root);
    bool hasNull = false;
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        if (node == nullptr) {
            hasNull = true;
        } else {
            if (hasNull) return false;
            q.push(node->left);
            q.push(node->right);
        }
    }
    return true;
}
A
该代码用于判断一棵树是否为满二叉树
B
该代码用于判断一棵树是否为完全二叉树
C
该代码用于判断一棵树是否为二叉搜索树
D
该代码用于计算树的高度
答案与解析
正确答案:B

使用队列 q 进行层序遍历,hasNull 标记是否遇到过空节点(初始为 false)。

遍历过程:

每次从队列中取出一个节点 node。

如果 node 是 nullptr:设置 hasNull = true。

如果 node 非空:若之前已遇到空节点(hasNull == true),则直接返回 false(违反完全二叉树的定义)。

否则,将 node 的左右子节点(无论是否为空)加入队列。

代码实现了 完全二叉树的判断逻辑。

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

以下代码实现了二叉排序树的哪种操作?( )

TreeNode* op(TreeNode* root, int val) {
    if (root == nullptr) return new TreeNode(val);
    if (val < root->val) {
        root->left = op(root->left, val);
    } else {
        root->right = op(root->right, val);
    }
    return root;
}
A
查找
B
插入
C
删除
D
遍历
答案与解析
正确答案:B

程序中:

if (root == nullptr) return new TreeNode(val)

若目标值不存在,则在叶子节点位置创建新节点。

若目标值更小,递归查找左子树;若目标值更大,递归查找右子树。

这段代码通过递归查找插入位置并动态创建新节点,实现了 二叉排序树的插入操作。

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

以下代码实现了二叉树的深度优先搜索(DFS),并统计叶子结点的数量,则横线上应填写?( )

int countLeafNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    stack<TreeNode*> s;
    s.push(root);
    int count = 0;
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        if (node->left == nullptr && node->right == nullptr) {
            count++;
        }
        if (node->right) s.push(node->right);
        _____________________________________ // 在此处填入代码
    }
    return count;
}
A
if (node->left) s.push(node->left);
B
if (node->left) s.pop(node->left);
C
if (node->left) s.front(node->left);
D
if (node->left) s.push(node->right);
答案与解析
正确答案:A

空缺的位置在 while 循环的末尾,当前代码已经处理了右子树的压栈操作,需要补充左子树的处理逻辑。

程序使用栈(stack<TreeNode*>)来实现 DFS,空缺部分应该是一个类似的逻辑:如果 node 有左子节点,则将其压入栈。

本题答案为选项A。

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

以下代码实现了二叉树的广度优先搜索(BFS),并查找特定值的节点,则横线上应填写?( )

TreeNode* findNode(TreeNode* root, int target) {
    if (root == nullptr) return nullptr;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* current = q.front();
        q.pop();
        if (current->val == target) {
            return current; // 找到目标节点
        }
        ___________________________________ // 在此处填入代码
    }
    return nullptr; // 未找到目标节点
}
A
if (current->left) q.push(current->left);if (current->right) q.push(current->right);
B
if (current->left) q.pop(current->left);if (current->right) q.pop(current->right);
C
if (current->left) q.front(current->left);if (current->right) q.front(current->right);
D
if (current->left) q.push(current->right);if (current->right) q.push(current->left);
答案与解析
正确答案:A

BFS 遍历:使用队列(queue)来实现 BFS。

初始时,将根节点 root 入队。

在 while 循环中,取出队首节点 current:

如果 current->val == target,则返回 current(找到目标节点)。

空缺部分需要将 current 的子节点(左子节点和右子节点)入队。

本题答案为选项A。

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

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

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

以下关于树的说法,( )是正确的。

A
在一棵二叉树中,叶子结点的度一定是2。
B
满二叉树中每一层的结点数等于 O(2 (层数−1))。
C
在一棵树中,所有结点的度之和等于所有叶子结点的度之和。
D
一棵二叉树的先序遍历结果和中序遍历结果一定相同。
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
28 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

已知字符集 {A, B, C, D} 的出现频率如下表所示:

根据哈夫曼编码法,下面( )是正确的哈夫曼树。

A
 ABCD
 / \
A   BCD
    / \
   D   BC
      / \
     B   C
B
 ABCD
 / \
A   BCD
    / \
   B   CD
      / \
     C   D
C
 ABCD
 / \
D   ABC
    / \
   A   BC
      / \
     B   C
D
 ABCD
 / \
C   ABC
    / \
   B   AD
      / \
     A   D
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
29 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

根据下面二叉树和给定的代码,

#include <iostream>
using namespace std;

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* search(TreeNode* root, int val) {
	cout << root->val << " ";
	if (root == NULL || root->val == val) return root;
	
	if (val < root->val)
		return search(root->left, val);
	else
		return search(root->right, val);
}

给定以下二叉搜索树,调用函数 search(root,7) 时,输出的结果是( )。

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

阅读以下二叉树的深度优先搜索算法,横线上应填写( )。

void dfs(TreeNode* root) {
	if (root == nullptr)
		return;
		
	stack<TreeNode*> s;
	s.push(root);
	while (!s.empty()) {
		———————————————————————— // 在此处填入代码
		cout << node->value << " ";
		
		if (node->right) s.push(node->right);
		if (node->left) s.push(node->left);
	}
}
A
TreeNode* node = s.top();
B
TreeNode* node = s.top(); s.pop();
C
TreeNode* node = s.front();
D
TreeNode* node = s.front(); s.pop();
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
31 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

阅读以下二叉树的广度优先搜索的代码,横线上应填写( )。

#include <queue>
void bfs(TreeNode* root) {
	if (root == NULL) return;
	
	queue<TreeNode*> q;
	q.push(root);
	while (!q.empty()) {
		———————————————————————— // 在此处填入代码
		cout << node->val << " ";
		if (node->left) {
			q.push(node->left);
		}
		if (node->right) {
			q.push(node->right);
		}
	}
}
A
TreeNode* node = q.top();
B
TreeNode* node = q.top(); q.pop();
C
TreeNode* node = q.front();
D
TreeNode* node = q.front(); q.pop();
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
32 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

使用上题中的宽度优先搜索算法遍历以下这棵树,可能的输出是( )。

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

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

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

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

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

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

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

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

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

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

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

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

题目详情