下列哪一项不是面向对象编程（OOP）的基本特征？

为了让Dog类的构造函数能正确地调用其父类Animal的构造方法，横线处应填入（ ）。

class Animal:
def __init__(self, name: str):
self.name = name
print("Animal created")
def speak(self) -> None:
print("Animal speaks")
class Dog(Animal):
______________________________
print("Dog created")
def speak(self) -> None:
print("Dog barks")
if __name__ == "__main__":
animal: Animal = Dog("Rex", "Labrador")
animal.speak()
def __init__(self, name: str, breed: str):
super().__init__(name)
self.breed = breed
def __init__(self, name: str, breed: str):
self.breed = breed
def __init__(self, name: str, breed: str):
self.breed = breed

A.

B.

C.

D.

代码同上一题，代码animal.speak()执行后输出结果是（ ）。

以下Python代码执行后其输出是（ ）。

from collections import deque
stack = []
queue = deque()
# 元素入栈/入队（1, 2, 3）
for i in range(1, 4):
stack.append(i)
queue.append(i)
print(f"{stack[-1]} {queue[0]}")

在一个使用列表实现的循环队列中，front 表示队头元素的位置（索引），rear 表示队尾元素的下一个插入位置（索引），队列的最大容量为 maxSize。那么判断队列已满的条件是（ ）

在二叉树中，只有最底层的节点未被填满，且最底层节点尽量靠左填充的是（ ）。

在使用数组表示完全二叉树时，如果一个节点的索引为i（从1开始计数），那么其左子节点的索引通常是（ ）。

已知一棵二叉树的前序遍历序列为GDAFEMHZ，中序遍历序列为ADFGEHMZ，则其后序遍历序列为（ ）。

设有字符集{a, b, c, d, e}，其出现频率分别为{5, 8, 12, 15, 20}，得到的哈夫曼编码为（ ）。

a: 010
b: 011
c: 00
d: 10
e: 11
a: 00
b: 10
c: 011
d: 100
e: 111
a: 10
b: 01
c: 011
d: 100
e: 111
a: 100
b: 01
c: 011
d: 100
e: 00

3位格雷编码中，编码101之后的下一个编码是（ ）。

请将下列Python实现的深度优先搜索（DFS）代码补充完整，横线处应填入（ ）。

from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def dfs_preorder(root: Optional[TreeNode], result: List[int]) -> None:
if root is None:
return
result.append(root.val)
dfs_preorder(root.left, result)
dfs_preorder(root.right, result)
result.append(root.val)
dfs_preorder(root.left, result)
result.append(root.val)
dfs_preorder(root.right, result)
dfs_preorder(root.left, result)
dfs_preorder(root.right, result)

给定一个二叉树，返回每一层中最大的节点值，结果以数组形式返回，横线处应填入（ ）。

from collections import deque
import math
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def largestValues(root: Optional[TreeNode]) -> List[int]:
result = []
if not root:
return result
queue = deque([root])
while queue:
level_size = len(queue)
max_val = -math.inf
for _ in range(level_size):
________________________
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(max_val)
return result
node = queue.popright()
max_val = max(max_val, node.val)
node = queue.popleft()
max_val = max(max_val, node.val)
node = queue.popleft()
max_val = max(max_val, node.val)

下面代码实现一个二叉排序树的插入函数（没有相同的数值），横线处应填入（ ）。

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def insert(root, key):
if root is None:
return TreeNode(key)
return root
if key < root.val:
root.left = insert(root.left, key)
elif key > root.val:
root.right = insert(root.right, key)
if key > root.val:
root.left = insert(root.left, key)
elif key > root.val:
root.right = insert(root.right, key)
if key < root.val:
root.left = insert(root.left, key)
elif key >= root.val:
root.right = insert(root.left, key)
if key < root.val:
root.left = insert(root.right, key)
elif key > root.val:
root.right = insert(root.left, key)

以下关于动态规划算法特性的描述，正确的是（ ）。

给定 一个物品和一个最大承重为W 的背包，每个物品有一个重量wt{i}和价值val{i}，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过 。关于下面代码，说法正确的是（ ）。
def knapsack1D(W: int, wt: list[int], val: list[int], n: int) -> int:
dp = [0] * (W + 1)
for i in range(n):
for w in range(W, wt[i] - 1, -1):
dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
return dp[W]

构造函数只能自动不可以被手动调用。（ ）

给定一组字符及其出现的频率，构造出的哈夫曼树是唯一的。（ ）

为了实现一个队列，使其出队操作（ pop ）的时间复杂度为O（1） 并且避免数组删除首元素的O（n） 问题，一 种常见且有效的方法是使用环形数组，通过调整队首和队尾指针来实现。

对一棵从小到大的二叉排序树进行中序遍历，可以得到一个递增的有序序列。（ ）

如果二叉搜索树在连续的插入和删除操作后，所有节点都偏向一侧，导致其退化为类似于链表的结构，这时其查找、插入、删除操作的时间复杂度会从理想情况下的O(log n) 退化到O(nlog n) 。

执行下列代码，my_dog.name的最终值是Charlie。（ ）

class Dog:
def __init__(self, name):
self.name = name
if __name__ == "__main__":
my_dog = Dog("Buddy")
my_dog.name = "Charlie"

下列Python代码可以成功执行，并且子类Child的实例能通过其成员函数访问父类Parent的属性_value。（ ）

class Parent:
def __init__(self):
self._value = 100
class Child(Parent):
def get_protected_val(self):
return self._value

下列代码中的tree列表，表示的是一棵完全二叉树（-1代表空节点）按照层序遍历的结果。（ ）

tree = [1, 2, 3, 4, -1, 6, 7]

在树的深度优先搜索（DFS）中，可以使用栈作为辅助数据结构以实现"先进后出"的访问顺序。（ ）

下面代码采用动态规划求解零钱兑换问题：给定n种硬币，第i种硬币的面值为coins[i-1]，目标金额为amt，每种硬币可以重复选取，求能够凑出目标金额的最少硬币

下面代码采用动态规划求解零钱兑换问题：给定 种硬币，第 𝑖 种硬币的面值为 𝑐𝑜𝑖𝑛𝑠[𝑖 − 1] ，目标金额为𝑎𝑚𝑡 ，每种硬币可以重复选取，求能够凑出目标金额的最少硬币数量；如果不能凑出目标金额，返回 -1 。
def coinChangeDPComp(coins: list[int], amt: int) -> int:
n = len(coins)
MAX = amt + 1
dp = [MAX] * (amt + 1)
dp[0] = 0
for i in range(1, n + 1):
for a in range(1, amt + 1):
if coins[i - 1] > a:
dp[a] = dp[a]
else:
dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1)
return dp[amt] if dp[amt] != MAX else -1

学习小组

时间限制：3.0 s 内存限制：512.0 MB
题目描述：班主任计划将班级里的n名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。观察发现，如果一个学习小组中恰好包含k名同学，则该学习小组的讨论积极度为a_k。
给定讨论积极度a_1~a_n，请你计算将这n名同学划分为学习小组的所有可能方案中，讨论积极度之和的最大值。

第一行，一个正整数n，表示班级人数。第二行，n个非负整数a_1~a_n，表示不同人数学习小组的讨论积极度。

输出共一行，一个整数，表示所有划分方案中，学习小组讨论积极度之和的最大值。

样例输入：
4
1 5 6 3
样例输出：
10

最大因数

时间限制：6.0 s 内存限制：512.0 MB
题目描述：给定一棵有n个结点的有根树，这些结点依次以1~n编号，根结点的编号为1。对于编号为i（i>1）的结点，其父结点的编号为i的因数中除1以外最大的因数。
现在有m组询问，第j组询问给定x_j和y_j，请你求出编号分别为x_j和y_j的两个结点在这棵树上的距离。两个结点之间的距离是连接这两个结点的简单路径所包含的边数。

第一行，一个正整数m，表示询问组数。接下来m行，每行两个正整数x_j和y_j，表示询问结点的编号。

输出共m行，每行一个整数，表示结点x_j和y_j之间的距离。

样例输入：
3
1 3
2 5
4 8
样例输出：
1
2
1