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

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

class Vehicle:
def __init__(self, brand):
self._brand = 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 move(self):
print(f"{self.get_brand()} car is driving on the road!")
v1 = Car("Toyota", 5)
v1.move()

下面代码中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]。请问该二叉树的后序遍历结果是（ ）。

完全二叉树可以用数组连续高效存储。如果节点从1开始编号，则对有两个孩子节点的节点i，（ ）。

设有字符集 {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
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)

在二叉搜索树中查找元素50，从根结点开始：若根值为60，则下一步应去（ ）。

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

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)

给定 个物品和一个最大承重为 的背包，每个物品有一个重量 和价值 ，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过 ，则横线上应填写（ ）。
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中，类的方法默认是"虚函数"，派生类只要重写方法。如果想复用基类逻辑时，可显式调用基类对应的函数。（ ）

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

一个含有n个结点的完全二叉树，高度为⌈log₂(n+1)⌉。（ ）

栈的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(n)。（ ）

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()

划分字符串

时间限制：3.0 s 内存限制：512.0 MB
问题描述：小A有一个由n个小写字母组成的字符串s。他希望将s划分为若干个子串，使得子串中每个字母至多出现一次。例如，对于字符串street来说，str+e+e+t是满足条件的划分；而s+tree+t不是，因为子串tree中e出现了两次。
额外地，小A还给出了价值a，表示划分后长度为k的子串价值为a_k。小A希望最大化划分后得到的子串价值之和。你能帮他求出划分后子串价值之和的最大值吗？

第一行，一个正整数n，表示字符串的长度。第二行，一个包含n个小写字母的字符串s。第三行，n个正整数a，表示不同长度的子串价值。

一行，一个整数，表示划分后子串价值之和的最大值。

样例输入：
6
street
2 1 7 4 3 3
样例输出：
13

货物运输v

A 国有n 座城市，依次以 1,2....,n编号，其中1 号城市为首都。这 座城市由n-1 条双向道路连接，第 i条道路（1≤i现在 A 国需要从首都向各个城市运送货物。具体来说，满载货物的车队会从首都开出，经过一座城市时将对应的货物送出，因此车队需要经过所有城市。A 国希望你设计一条路线，在从首都出发经过所有城市的前提下，最小化经过的道路长度总和。注意一座城市可以经过多次，车队最后可以不返回首都。

第一行，一个正整数n，表示A国的城市数量。接下来n-1行，每行三个整数u,v,w，表示一条双向道路连接编号为u和v的两座城市，道路长度为w

一行，一个整数，表示你设计的路线所经过的道路长度总和。

样例输入：
4
1 2 6
1 3 1
3 4 5
样例输出：
18