关于Python类的说法，错误的是（ ）。

下面代码执行结果是（ ）。

class Vehicle:
	def __init__(self, brand):
		self._brand = brand # 私有属性用下划线表示
	def set_brand(self, brand):
		self._brand = brand
	def get_brand(self):
		return self._brand
	def move(self):
		print(f"{self._brand} is moving...")

class Car(Vehicle):
	def __init__(self, brand, seat_count):
		super().__init__(brand)
		self._seat_count = seat_count
	def show_info(self):
	print(f"This car is a {self.get_brand()} with {self._seat_count} seats.")
	def move(self):
	print(f"{self.get_brand()} car is driving on the road!")
def main():
	v1 = Car("Toyota", 5)
	v1.move()
if __name__ == "__main__":
	main()

下面代码中 v1 和 v2 调用了相同接口 move() ，但输出结果不同，这体现了面向对象编程的（ ）特性。

class Vehicle:
	def __init__(self, brand):
		self._brand = brand # 私有属性用下划线表示
	def set_brand(self, brand):
		self._brand = brand
	def get_brand(self):
		return self._brand
	def move(self):
		print(f"{self._brand} is moving...")

class Car(Vehicle):
	def __init__(self, brand, seat_count):
		super().__init__(brand)
		self._seat_count = seat_count
	def show_info(self):
		print(f"This car is a {self.get_brand()} with {self._seat_count} seats.")
	def move(self):
		print(f"{self.get_brand()} car is driving on the road!")

class Bike(Vehicle):
	def __init__(self, brand):
		super().__init__(brand)
	def move(self):
		print(f"{self.get_brand()} bike is cycling on the path!")

def main():
	v1 = Car("Toyota", 5)
	v2 = Bike("Giant")
	v1.move() # 输出: Toyota car is driving on the road!
	v2.move() # 输出: Giant bike is cycling on the path!
if __name__ == "__main__":
	main()

栈的操作特点是（ ）。

循环队列常用于实现数据缓冲。假设一个循环队列容量为 5 （即最多存放 4 个元素，留一个位置区分空与满），依次进行操作：入队数据1，2，3，出队1个数据，再入队数据4和5，此时队首到队尾的元素顺序是（ ）。

以下函数 createTree() 构造的树是什么类型？

class TreeNode:
	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None
def create_tree():
	root = TreeNode(1)
	root.left = TreeNode(2)
	root.right = TreeNode(3)
	root.left.left = TreeNode(4)
	root.left.right = TreeNode(5)
	return root

已知二叉树的 中序遍历 是 [D, B, E, A, F, C]，先序遍历 是 [A, B, D, E, C, F]。请问该二叉树的后序遍历结果是（ ）。

设有字符集 {a, b, c, d, e, f} ，其出现频率分别为 {5, 9, 12, 13, 16, 45} 。哈夫曼算法构造最优前缀编码，以下哪一组可能是对应的哈夫曼编码？（非叶子节点左边分支记作 0，右边分支记作 1，左右互换不影响正确性）。

下面代码生成格雷编码中， gray_code 的目的是生成所有的长度为n位的格雷码,则横线上应填写（ ）。

def gray_code(n):
	if n == 0:
		return ["0"]
	if n == 1:
		return ["0", "1"]
	prev = gray_code(n-1)
	result = []
	for s in prev:
		____________________________
	for i in range(len(prev)-1, -1, -1):
		result.append("1" + prev[i])
	return result

请将下列树的深度优先遍历代码补充完整，横线处应填入（ ）。

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

def dfs(root):
	if not root:
		return
	_________________________
	stack.append(root)
	while stack:
		node = stack.pop()
		print(node.val, end=" ")
	if node.right:
		stack.append(node.right)
	if node.left:
		stack.append(node.left)

令 n 是树的节点数目，下列代码实现了树的广度优先遍历，其时间复杂度是（ ）。

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

def bfs(root):
	if not root:
		return
	q = deque()
	q.append(root)
	while q:
		node = q.popleft()
		print(node.val, end=" ")
		if node.left:
			q.append(node.left)
		if node.right:
			q.append(node.right)

删除二叉排序树节点时，如果节点有两个孩子，则横线处应填入（ ），其中 findMax 和 findMin 分别为找树的最大值和最小值。

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

def find_min(node):
	"""在二叉搜索树中找到最小节点"""
	current = node
	while current and current.left:
		current = current.left
	return current
def delete_node(root, key):
	if not root:
		return None
	if key < root.val:
		root.left = delete_node(root.left, key)
	elif key > root.val:
		root.right = delete_node(root.right, key)
	else:
		if not root.left:
			return root.right
		elif not root.right:
			return root.left
		else:
			temp = find_min(____________)
			root.val = temp.val
			root.right = delete_node(root.right, temp.val)

给定n个物品和一个最大承重为W的背包，每个物品有一个重量 wt[i] 和价值 val[i]，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过W，则横线上应填写( )。

def knapsack(W, wt, val, n):
	dp = [0] * (W + 1)
	for i in range(n):
		for w in range(W, wt[i] - 1, -1):
			_____________________________
	return dp[W]

在 Python 中，类的方法默认是“虚函数”，派生类只要重写方法。如果想复用基类逻辑时，可显式调用基类对应的函数。

哈夫曼编码是最优前缀码，且编码结果唯一。

栈的 pop 操作返回栈顶元素并移除它。

循环队列通过模运算循环使用空间。

一棵有 n 个结点的二叉树一定有 n-1 条边。

以下代码实现了二叉树的中序遍历，输入以下二叉树，中序遍历结果是 4 2 5 1 3 6 。

# 1
# / \
# 2 3
# / \ \
# 4 5 6

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

def inorder_iterative(root):
	stack = []
	curr = root
	while curr or stack:
		while curr:
			stack.append(curr)
			curr = curr.left
		curr = stack.pop()
		print(curr.val, end=" ")
		curr = curr.right

下面代码实现的二叉搜索树的查找操作时间复杂度是 O(h)，h 为树高。

def searchBST(root, val):
	while root and root.val != val:
		root = root.left if val < root.val else root.right
	return root

下面代码实现了动态规划版本的斐波那契数列计算，其时间复杂度是 O(2ⁿ)。

def fib_dp(n):
	if n <= 1:
		return n
	dp = [0] * (n + 1)
	dp[0] = 0
	dp[1] = 1
	for i in range(2, n + 1):
		dp[i] = dp[i - 1] + dp[i - 2]
	return dp[n]

有一排香蕉，每个香蕉有不同的甜度值。小猴子想吃香蕉，但不能吃相邻的香蕉。以下代码能找到小猴子吃到最甜的香蕉组合。

def find_selected_bananas(bananas, dp):
	selected = []
	i = len(bananas) - 1
	while i >= 0:
		if i == 0:
			selected.append(0)
			break
		if dp[i] == dp[i-1]:
			i -= 1
		else:
			selected.append(i)
			i -= 2
	selected.reverse()
	print("小猴子吃了第: ", end="")
	for idx in selected:
		print(idx + 1, end=" ")
	print("个香蕉")

def main():
	bananas = [1, 2, 3, 1] # 每个香蕉的甜度
	if not bananas:
		return
	n = len(bananas)
	dp = [0] * n
	dp[0] = bananas[0]
	if n > 1:
		dp[1] = max(bananas[0], bananas[1])
	for i in range(2, n):
		dp[i] = max(bananas[i] + dp[i-2], dp[i-1])
	find_selected_bananas(bananas, dp)
if __name__ == "__main__":
	main()