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

GESP-Python六级 题库

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

下面程序是一个二叉排序树的,横线处应该填入的是( )。

class BinarySortTree:
	def __init__(self):
		self.root = None
		
	def insert(self, key, value):
		node = TreeNode(key, value)
		if self.root is None:
			self.root = node
			return
		current = self.root
		while True:
			if key < current.key:
				___________________________
				current = current.left
			else:
				if current.right is None:
					current.right = node
					return
				current = current.right
		
	def search(self, key):
		current = self.root
		while current:
			if current.key == key:
				return current.value
			elif current.key > key:
				current = current.left
			else:
				current = current.right
		return None
		
	def inorder_traversal(self, node):
		if node:
			self.inorder_traversal(node.left)
			print(node.key, node.value)
			self.inorder_traversal(node.right)
A
if current.left is None:
	current.right = node
	return
B
if current.right is None:
	current.right = node
	return
C
if current.right is None:
	current.left = node
	return
D
if current.left is None:
	current.left = node
	return
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
42 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

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

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

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

结果为EDBGFCA

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

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

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

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

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

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

class Node:
	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None
		
def max_depth(root_node):
	if root_node is None:
		return 0
	else:
		left_depth = max_depth(root_node.left)
		right_depth = max_depth(root_node.right)
		_______________________________________
A
return max(left_depth, right_depth)
B
return min(left_depth, right_depth) + 1
C
return max(left_depth, right_depth) + 1
D
return max(left_depth, right_depth) - 1
答案与解析
正确答案:C

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

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

以下基于二叉树的搜索实现的深度计算函数中横线上应填写( )。

class Node:
	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None
		
def height(root):
	if root is None:
		return 0
	else:
		left_height = height(root.left)
		right_height = height(root.right)
		_________________________________
A
return max(left_height, right_height) + 1
B
return min(left_height, right_height) - 1
C
return min(left_height, right_height) + 1
D
return max(left_height, right_height) - 1
答案与解析
正确答案:A

我们需要计算二叉树的深度。二叉树的深度是指从根节点到最远叶子节点的最长路径上的边数。这里的深度计算逻辑是递归的。基本情况:如果根节点 root 为空,返回 0,表示空树的深度为 0。

递归情况:

计算左子树的深度 left_height。

计算右子树的深度 right_height。

返回左右子树中深度较大的那个加上 1(根节点的高度)。

根据上述逻辑,横线处应该填写:

return max(left_height, right_height) + 1

这是因为我们要返回左右子树中深度较大的那个,并加上根节点的高度。

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

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

class TreeNode:
	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None
		
class Solution:
	def isValidBST(self, root: TreeNode) -> bool:
		def helper(node, min_val, max_val):
			if not node:
				return True
			————————————————————————————————————————————————
				return False
			return helper(node.left, min_val, node.val) and helper(node.right,node.val, max_val)
			
		return helper(root, float('-inf'), float('inf'))
A
if node.val <= min_val or node.val >= max_val:
B
if node.val >= min_val or node.val >= max_val:
C
if node.val <= min_val or node.val <= max_val:
D
if node.val >= min_val or node.val <= max_val:
答案与解析
正确答案:A

题目描述了二叉搜索树(Binary Search Tree, BST)的性质,并给出了一个用于验证给定树是否为有效二叉搜索树的函数。我们需要填充横线上的代码,使其能够正确验证树的性质。

上述代码是一个用于验证二叉搜索树是否有效的函数isValidBST,并通过递归辅助函数helper来实现验证逻辑。

helper的作用是递归地验证当前节点node是否满足二叉搜索树的性质,即:

左子树的所有节点值小于当前节点值。

右子树的所有节点值大于当前节点值。

此外,函数还会传递当前节点值的有效范围min_val和max_val,确保节点值在指定范围内。

我们需要在横线上填充代码来检查当前节点的值是否在其有效范围内。具体来说:

如果当前节点值 node.val 小于等于 min_val 或者大于等于 max_val,则说明该节点不满足二叉搜索树的性质。

否则,继续递归检查左子树和右子树。

因此,正确的填充代码应该是:

if node.val <= min_val or node.val >= max_val: return False

因此选A

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

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

def traversal(tree_node* root) :
	if (root == nullptr) {
		return
	}
	
traversal(root->left)
print(root->val)
print(" ")
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

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

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

A

完全二叉树可以用 list 存储

B

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

C

满二叉树可以用 list 存储

D

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

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

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

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

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

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

若所有字符出现频率相同,则哈夫曼编码一定会得到完全二叉树。

A
对
B
错
答案与解析
正确答案:错
分析字符频率分布对哈夫曼树结构的影响;考察哈夫曼算法在频率相同情况下的构建机制;观察每次合并过程中的节点选择逻辑;追踪左右子树生成顺序与队列中节点优先级的关系;检查最终二叉树的层深度一致性与分支完整性;确认是否存在某层节点未完全填充的情况。
题目详情
52 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

哈夫曼编码是一种变长的前缀编码,在解码时不需要额外的分隔符就能唯一还原,这是因为在哈夫曼树中,任何一个字符的叶子结点都不会成为另一个字符结点的祖先。

A
对
B
错
答案与解析
正确答案:对
哈夫曼编码基于字符出现频率构建二叉树,频率越低的字符位于更深的叶子节点。编码过程中,从根节点到每个叶子节点的路径对应一个字符的二进制编码,向左分支记为0,向右分支记为1。由于所有字符均存储于叶子节点,内部节点不表示字符,因此任意字符的编码路径不会是另一字符编码路径的前缀。这种结构确保了编码序列在解析时可唯一分解,无需分隔符即可逐位还原原始字符序列。解码时从根节点开始,依比特流逐位移动,到达叶子节点后输出对应字符并返回根节点继续后续解码。
题目详情
53 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

在Python 中使用列表存储按层序遍历的完全二叉树时,若根节点存储在tree[0],则对于任意非空节点 tree[i],其右孩子(如果存在)必然位于tree[2 * i + 2]。

A
对
B
错
答案与解析
正确答案:对
在完全二叉树的层序遍历中,若根节点位于索引0,则任意非空节点i的左孩子位于2*i+1,右孩子位于2*i+2。该存储规则由数组下标与二叉树结构间的映射关系决定。当tree[i]存在右孩子时,其在数组中的位置必为2*i+2。此位置的有效性取决于2*i+2是否小于数组长度且对应节点非空。数组存储方式固定了父子节点间的数学关系,不因树的实际形态改变而改变。
题目详情
54 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

在Python 中使用列表模拟栈来非递归地实现二叉树的前序遍历,为了保证遍历顺序正确,在处理完当前结点后,应该先将该结点的左孩子压入栈中,然后再将右孩子压入栈中。()

A
对
B
错
答案与解析
正确答案:错
使用列表模拟栈进行二叉树前序遍历,需将根结点先压入栈。每次从栈顶弹出一个结点并访问,随后判断该结点是否存在右孩子和左孩子。若存在右孩子,则将其压入栈;若存在左孩子,则将其压入栈。由于栈具有后进先出特性,为确保左孩子在右孩子之前被处理,必须先压入右孩子,再压入左孩子。因此,在处理完当前结点后,应先将右孩子入栈,再将左孩子入栈,以保证遍历顺序符合前序要求。
题目详情
55 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

设二叉树共有n个结点,函数 preorderTraversal 的时间复杂度为O(n),空间复杂度为O(n)。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def preorder(root, res):
    if root is None:
        return
    res.append(root.val)
    preorder(root.left, res)
    preorder(root.right, res)

def preorderTraversal(root):
    res = []
    preorder(root, res)
    return res

if __name__ == "__main__":
    root = TreeNode(1)
    root.right = TreeNode(2)
    root.right.left = TreeNode(3)
    result = preorderTraversal(root)
    print("前序遍历结果: ", result)
A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
56 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

对如下结构的树,执行travel 函数,输出结果是1 2 3 4 5。

class Node:
    def __init__(self, v):
        self.val = v
        self.left = None
        self.right = None

def travel(root):
    if not root:
        return
    stack = []
    stack.append(root)
    while stack:
        cur = stack.pop()
        print(cur.val, end=" ")
        if cur.right:
            stack.append(cur.right)
        if cur.left:
            stack.append(cur.left)

if __name__ == "__main__":
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    travel(root)
A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
57 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

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

class TreeNode: 
    def __init__(self, val=0, left=None, right=None): 
        self.val = val 
        self.left = left 
        self.right = right 
def count_leaf(root): 
    if not root: 
        return 0 
    if not root.left and not root.right: 
        return 1 
    return count_leaf(root.left) + count_leaf(root.right) 
if __name__ == "__main__": 
    root1 = TreeNode(1) 
    root1.left = TreeNode(2) 
    root1.right = TreeNode(3) 
    root1.left.left = TreeNode(4) 
    root1.left.right = TreeNode(5) 
    root1.right.right = TreeNode(6) 
    print(f"二叉树1的叶子节点数:{count_leaf(root1)}") 
    root2 = TreeNode(1) 
    print(f"二叉树2的叶子节点数:{count_leaf(root2)}") 1 
    root3 = None 
    print(f"空树的叶子节点数:{count_leaf(root3)}")


A
对
B
错
答案与解析
正确答案:对
分析二叉树结构,识别叶子结点的定义为左右子树均为空的结点。通过递归遍历根结点,判断当前结点是否为空,若为空则返回0;若当前结点为叶子结点则返回1;否则递归计算左子树和右子树的叶子结点数量并求和。对每个测试用例,分别构建对应的二叉树或空树,调用统计函数处理不同形态的树结构,包括单结点树、多层树及空树的情况。
题目详情
58 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

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

A
对
B
错
答案与解析
正确答案:错
广度优先遍历要求按层级顺序访问节点,先访问根节点,再依次访问各层子节点。实现时需在访问当前节点后,将其子节点暂存以便后续处理。栈的特点是后进先出,会导致最后存入的子节点最先被取出,从而打破层级访问顺序。若使用栈存储待访问节点,则节点的处理顺序受压入顺序影响,无法保证同一层节点在下一层节点之前被统一处理。为维持层级遍历特性,需采用先进先出的数据结构管理待访问节点序列。
题目详情
59 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

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

A
对
B
错
答案与解析
正确答案:错
分析二叉排序树的性质,其中每个结点的左子树所有结点值均小于该结点值,右子树所有结点值均大于该结点值。若某结点左子树为空,则不存在比该结点值更小的左后代结点。根据二叉排序树的中序遍历特性,最小值结点位于最左侧路径的末端。判断该结点是否处于从根开始的最左路径的终点,需考察其祖先结点及路径上的比较过程。结合树的整体结构与结点位置关系,推导该结点在全局中的相对大小位置。
题目详情
60 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

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

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def is_bst(root, min_val=float('-inf'), max_val=float('inf')):
    if not root:
        return True
    if root.val <= min_val or root.val >= max_val:
        return False
    return is_bst(root.left, min_val, root.val) and is_bst(root.right, root.val, max_val)
A
对
B
错
答案与解析
正确答案:对

1. 检查当前节点是否为空,若为空则返回True。
2. 判断当前节点的值是否满足大于最小值且小于最大值的约束条件。
3. 递归检查左子树,更新最大值约束为当前节点的值。
4. 递归检查右子树,更新最小值约束为当前节点的值。
5. 所有递归调用均需同时满足约束条件和子树的判断结果。

题目详情