GESP-Python六级 题库
以下基于二叉树的搜索实现的深度计算函数中横线上应填写( )。
我们需要计算二叉树的深度。二叉树的深度是指从根节点到最远叶子节点的最长路径上的边数。这里的深度计算逻辑是递归的。基本情况:如果根节点 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
动态规划通常用于解决( )。
一个问题是否能用DP来解决我们的考虑一般有两点:① 最优子结构,②无后效性最优子结构即 选项B,可分解成相互依赖的子问题的问题,因此选B。
阅读以下用动态规划解决的0-1背包问题的函数,假设背包的容量 W WW 是10kg,假设输入4个物品的重量 w e i g h t s weightsweights 分别为 1,3,4,6(单位为kg),每个物品对应的价值 v a l u e s valuesvalues 分别为 20,30,50,60,则函数的输出为( )。
01背包问题,dp[n][w]表示将前n个物品放入容量为w的背包中得到的最大价值,4个物品的重量为1 3 4 6,价值为20 30 50 60,背包容量为10,最大价值是1 3 6 对应的110。
小杨想编写一个判断任意输入的整数N是否为素数的程序,下面哪个方法不合适?( )
埃氏筛法
线性筛法
二分答案
枚举法
关于Python类和对象的说法,错误的是( )。
在Python中,一切皆对象,即便是字面量如整数5等也是对象
在Python中,可以自定义新的类,并实例化为新的对象
在Python中,内置函数和自定义函数,都是类或者对象
在Python中,不可以在自定义函数中嵌套定义新的函数
有关下面Python代码的说法,正确的是( )。

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

第8行代码错误,第9行正确
第9行代码错误,第8行代码正确
第8、9两行代码都正确
第4行代码可修改为 objCounter += 1
有关下面Python代码的说法,错误的是( )。

上列Python代码适用于构造各种二叉树
代码 Root = biTree(biTreeNode(5)) 构造二叉树的根节点
代码 Root = biTree( ) 可以构造空二叉树,此时 Root 对象的 root 属性值为 None
代码 Root = biTree(biTreeNode( )) 可以构造空二叉树,此时 Root 对象的 root 属性为 Node
基于上题类的定义,有关下面Python代码的说法错误的是( )。

代码中 Search( ) 函数如果查找到查找值的节点,则返回该节点的对象
代码中 Search( ) 函数先搜索左子树,如果搜索不到指定值,则搜索右子树
代码中 Search( ) 函数采用递归方式实现二叉树节点的搜索
代码中 Search( ) 函数采用动态规划方法实现二叉树节点的搜索
有关下面Python代码的说法正确的是( )。

上述代码构成单向链表
上述代码构成双向链表
上述代码构成循环链表
上述代码构成指针链表
对 hello world 使用霍夫曼编码(Huffman Coding),最少 bit(比特)为( )。
4
32
64
88
下面的 fiboA( ) 和 fiboB( ) 两个函数分别实现斐波那契数列,该数列第1、第2项值为1,其余各项分别为前两项之和。下面有关说法错误的是( )。

fiboA( ) 采用递归方式实现斐波那契数列
fiboB( ) 采用动态规划算法实现斐波那契数列
当N值较大时, fiboA( ) 存在大量重复计算
由于 fiboA( ) 代码较短,其执行效率较高
有关下面Python代码不正确的说法是( )。

该代码可用于求解二叉树的深度
代码中函数 getDepth( ) 的参数 root 表示根节点,非根节点不可以作为参数
代码中函数 getDepth( ) 采用了递归方法
代码中函数 getDepth( ) 可用于求解各种形式的二叉树深度,要求该二叉树节点至少有 left 和 right 属性
下面有关树的存储,错误的是( ).
完全二叉树可以用 list 存储
一般二叉树都可以用 list 存储,空子树位置可以用 None 表示
满二叉树可以用 list 存储
树数据结构,都可以用 list 存储
下面有关Python中 in 运算符的时间复杂度的说法,错误的是( )。
当 in 运算符作用于 dict 时,其时间复杂度为O(1)
当 in 运算符作用于 set 时,其时间复杂度为O(1)
当 in 运算符作用于 list 时,其时间复杂度为O(N)
当 in 运算符作用于 str 时,其时间复杂度为O(N)
下面有关 bool() 函数的说法,正确的是( )。
如果自定义类中没有定义魔术方法 __bool__( ) ,将不能对该类的对象使用 bool( ) 函数
如果自定义类中没有定义魔术方法 __bool__( ) ,将查找有无魔术方法 __len__( ) 函数,如果有__len__( ) 则按 __len__( ) 的值进行处理,如果该值为0则返回 False ,否则 True ,如果没有 __len__() ,则返回值为 True
bool( ) 函数如果没有参数,返回值为 False
表达式 bool(int) 的值为 False