GESP-Python六级 题库
给定一棵二叉树,其前序遍历结果为:ABDECFG,中序遍历结果为:DEBACFG,则这棵树的正确后序遍历结果是( )。
在前序遍历中找根,在中序遍历中找根的左右子树,建好树后进行后序遍历。
结果为EDBGFCA
一棵有 n 个结点的完全二叉树用数组进行存储与表示,已知根结点存储在数组的第 1 个位置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点,则它的兄弟结点和右子结点的位置分别是( )。
完全二叉树兄弟结点一般是左偶右奇,9号结点的兄弟结点只能是8号,而右子结点即9*2+1 = 19,选C
二叉树的深度定义为从根结点到叶结点的最长路径上的结点数,则以下基于二叉树的深度优先搜索实现的深度计算函数中横线上应填写( )。
代码的思路是计算出当前根结点左子树的深度,右子树的深度,那么以根结点为子树的深度即max(左子树,右子树)+1,+1即将根结点的深度也计算在内,所以选C。
以下基于二叉树的搜索实现的深度计算函数中横线上应填写( )。
我们需要计算二叉树的深度。二叉树的深度是指从根节点到最远叶子节点的最长路径上的边数。这里的深度计算逻辑是递归的。基本情况:如果根节点 root 为空,返回 0,表示空树的深度为 0。
递归情况:
计算左子树的深度 left_height。
计算右子树的深度 right_height。
返回左右子树中深度较大的那个加上 1(根节点的高度)。
根据上述逻辑,横线处应该填写:
return max(left_height, right_height) + 1
这是因为我们要返回左右子树中深度较大的那个,并加上根节点的高度。
二叉搜索树中的每个结点,其左子树的所有结点值都小于该结点值,右子树的所有结点值都大于该结点值。以下代码对给定的整数数组(假设数组中没有数值相等的元素),构造一个对应的二叉搜索树,横线上应填写():
题目描述了二叉搜索树(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
对上题中的二叉搜素树,当输入数组为 [ 5 , 3 , 7 , 2 , 4 , 6 , 8 ] [5,3,7,2,4,6,8][5,3,7,2,4,6,8] 时,构建二叉搜索树,并采用如下代码实现的遍历方式,得到的输出是( )。
根据输入数组建BST为
然后根据 “左根右”的遍历规则输出为:
2 3 4 5 6 7 8,选B
下面有关树的存储,错误的是( ).
完全二叉树可以用 list 存储
一般二叉树都可以用 list 存储,空子树位置可以用 None 表示
满二叉树可以用 list 存储
树数据结构,都可以用 list 存储
有关下图的二叉树,说法正确的是( )。

若所有字符出现频率相同,则哈夫曼编码一定会得到完全二叉树。
哈夫曼编码是一种变长的前缀编码,在解码时不需要额外的分隔符就能唯一还原,这是因为在哈夫曼树中,任何一个字符的叶子结点都不会成为另一个字符结点的祖先。
在Python 中使用列表存储按层序遍历的完全二叉树时,若根节点存储在tree[0],则对于任意非空节点 tree[i],其右孩子(如果存在)必然位于tree[2 * i + 2]。
在Python 中使用列表模拟栈来非递归地实现二叉树的前序遍历,为了保证遍历顺序正确,在处理完当前结点后,应该先将该结点的左孩子压入栈中,然后再将右孩子压入栈中。()
以下代码能够正确统计二叉树中叶子结点的数量。
广度优先遍历二叉树可用栈来实现。
在二叉排序树(BST)中,若某结点的左子树为空,则该结点一定是整棵树中的最小值结点。
下面的函数能正确判断一棵树是不是二叉排序树(左边的数字要比当前数字小,右边的数字要比当前数字大)。
1. 检查当前节点是否为空,若为空则返回True。
2. 判断当前节点的值是否满足大于最小值且小于最大值的约束条件。
3. 递归检查左子树,更新最大值约束为当前节点的值。
4. 递归检查右子树,更新最小值约束为当前节点的值。
5. 所有递归调用均需同时满足约束条件和子树的判断结果。
