GESP-Python六级 题库
以下函数check()用于判断一棵二叉树是否为( )。
from collections import deque class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def check(root): if not root: return True q = deque() q.append(root) has_null = False while q: cur = q.popleft() if not cur: has_null = True else: if has_null: return False q.append(cur.left) q.append(cur.right) return True
满二叉树
完全二叉树
二叉搜索树
平衡二叉树
以下代码实现了二叉树的( )。
前序遍历
中序遍历
后序遍历
层序遍历
下面代码实现了哈夫曼编码,则横线处应填写的代码是( )。
以下关于哈夫曼编码的说法,正确的是( )。
哈夫曼编码是定长编码
哈夫曼编码中,没有任何一个字符的编码是另一个字符编码的前缀
哈夫曼编码一定唯一
哈夫曼编码不能用于数据压缩
以下函数实现了二叉排序树(BST)的( )操作。 class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def op(root, x): if not root: return TreeNode(x) if x < root.val: root.left = op(root.left, x) else: root.right = op(root.right, x) return root
查找
插入
删除
遍历
下列代码实现了树的深度优先遍历,则横线处应填入( )。
给定一棵普通二叉树(节点值没有大小规律),下面代码判断是否存在值为 x 的结点,则横线处应填入( )。
在二叉排序树(Binary Search Tree, BST)中,假设节点值互不相同。给定如下搜索函数,以下说法 一定正确的是( )。
最坏情况下,访问结点数是 O(log n)
最坏情况下 ,访问结点数是O(n)
无论如何 ,访问结点数都不超过树高的一半
一定比在普通二叉树中搜索快
0/1 背包(每件物品最多选一次) 问题通常可用一维动态规划求解 ,核心代码如下 。遍历的方向无所谓 ,则下面说法正确的是( )。
内层 j 必须从小到大,否则会漏解
内层 j 必须从大到小,否则同一件物品会被用多次
j 从大到小或从小到大都一样
只要 dp 初始为 0 ,方向无所谓
以下关于动态规划的说法中,错误的是( )。
动态规划方法通常能够列出递推公式。
动态规划方法的时间复杂度通常为状态的个数。
动态规划方法有递推和递归两种实现形式。
在使用动态规划思想(即避免重复子问题)的前提下,递推实现与递归实现(记忆化搜索)的时间复杂度通常是相当的。
关于Python类的说法,错误的是( )。
构造方法( __init__ )不能声明为虚方法,但析构方法( __del__ )可以。
函数参数传传递的是对象的引用,不会复制对象。
静态方法属于类、不属于对象,因此不能使用 对象.方法(...) 的形式调用静态方法。
当派生类对象被销毁时,不会自动调用基类的 __del__() 。
下面代码执行结果是()。

Toyota is moving...
Toyota car is driving on the road!
编译错误
运行结果不确定
下面代码中 v1 和 v2 调用了相同接口 move() ,但输出结果不同,这体现了面向对象编程的( )特性。


继承 (Inheritance)
封装 (Encapsulation)
多态 (Polymorphism)
链接 (Linking)
循环队列常用于实现数据缓冲。假设一个循环队列容量为 5(即最多存放 4 个元素,留一个位置区分空与满),依次进行操作:入队数据1,2,3,出队1个数据,再入队数据4和5,此时队首到队尾的元素顺序是( )。
[2, 3, 4, 5]
[1, 2, 3, 4]
[3, 4, 5, 2]
[2, 3, 5, 4]
已知二叉树的 中序遍历 是 [D, B, E, A, F, C],先序遍历 是 [A, B, D, E, C, F]。请问该二叉树的后序遍历结果是( )。
[D, E, B, F, C, A]
[D, B, E, F, C, A]
[D, E, B, C, F, A]
[B, D, E, F, C, A]
完全二叉树可以用数组连续高效存储。如果节点从 1 开始编号,则对有两个孩子节点的节点 i ,()。
左孩子位于 2i ,右孩子位于 2i+1
完全二叉树的叶子节点可以出现在最后一层的任意位置
所有节点都有两个孩子
左孩子位于 2i+1 ,右孩子位于 2i+2
设有字符集 {a, b, c, d, e, f} ,其出现频率分别为 {5, 9, 12, 13, 16, 45} 。哈夫曼算法构造最优前缀编码,以下哪一组可能是对应的哈夫曼编码?(非叶子节点左边分支记作 0,右边分支记作 1,左右互换不影响正确性)。
a: 00;b: 01;c: 10;d: 110;e: 111;f: 0
a: 1100;b: 1101;c: 100;d: 101;e: 111;f: 0
a: 000;b: 001;c: 01;d: 10;e: 110;f: 111
a: 10;b: 01;c: 100;d: 101;e: 111;f: 0
下面代码生成格雷编码中, gray_code 的目的是生成所有的长度为n位的格雷码,则横线上应填写( )。

result.append("1" + s)
result.append("0" + s)
result.append("s" + 0)
result.append("0" + 0)
