GESP-Python六级 题库
二叉树T,已知其先根遍历是 1 2 4 3 5 7 6(数字为结点的编号,以下同),中根遍历是 2 4 1 5 7 3 6,则该二叉树的后根遍历是( )。
一棵二叉树的前序遍历序列是 ABCDEFG,后序遍历序列是 CBFEGDA,则根结点的左子树的结点个数可能是( )。
完全二叉树的顺序存储方案,是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根结点存放在数组的 1 号位置,则第 k 号结点的父结点如果存在的话,应当存放在数组的( )号位置。
如果根结点的深度记为 1,则一棵恰有 2011 个叶结点的二叉树的深度最少是( )。
在程序运行过程中,如果递归调用的层数过多,会因为( )引发错误。
前序遍历序列与中序遍历序列相同的二叉树为( )。
假设字母表 {a,b,c,d,e} 在字符串出现的频率分别为 10%,15%,30%,16%,29%。若使用哈夫曼编码方式对字母进行二进制编码,则字符 abcdef 分别对应的一组哈夫曼编码的长度分别为( )。
求哈夫曼编码需要先构建哈夫曼树,构建方法:① 从频率表中取出最小的两个元素,构建出新元素,② 将新元加入到频率表中,所以很明显abcdef分别对应的一组哈夫曼编码长度为3 3 2 2 2
给定一棵二叉树,其前序遍历结果为: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
小杨想编写一个判断任意输入的整数N是否为素数的程序,下面哪个方法不合适?( )
埃氏筛法
线性筛法
二分答案
枚举法
有关下面Python代码的说法,正确的是( )。

第17行代码执行后将报错,因为 Rect 类没有定义 in 运算符
第16行代码将 Point 对象作为参数,将导致错误
in是成员运算符,不适用于 Rect 类
由于 Rect 类定义了 __contains__ 魔术方法,因此第17行代码能正确执行
有关下面Python代码的说法,正确的是( )。

第8行代码错误,第9行正确
第9行代码错误,第8行代码正确
第8、9两行代码都正确
第4行代码可修改为 objCounter += 1