试卷总分：100分
选择题 15题 30分
判断题 10题 20分
编程题 2题 50分
下列代码执行后的输出结果是?
class Animal: def speak(self): print("Animal", end="") class Cat(Animal): def speak(self): print("Cat", end="") def main(): p: Animal = Cat() p.speak() main()
下列代码横线处填写哪一项，才可以正确调用父类的带参数构造函数？
class Machine: def __init__(self, s): self.id = s class Robot(Machine): def __init__(self, s, n): self.level = n ______
下列代码执行后的输出顺序是？
class Base: def __init__(self): print("B", end="") def __del__(self): print("~B", end="") class Derived(Base): def __init__(self): super().__init__() print("D", end="") def __del__(self): print("~D", end="") def main(): p = Derived() del p main()
下列代码执行后的输出结果是？
s = [] q = [] for i in range(2, 7, 2): s.append(i) q.append(i) s.pop() q.pop(0) print(s[-1], q[0])
下面循环队列采用牺牲一个存储单元 (空出一个位置) 的方法区分队空与队满，full () 函数判断队列是否已满，横线处应填写？
MAXN = 8 data = [0] * MAXN front = 0 rear = 0 def full(): return ________
下列函数属于二叉树哪一种遍历？
class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None def visit(root): if root is None: return visit(root.left) print(root.val, end=" ") visit(root.right)
已知一棵二叉树的先序遍历序列为 A B D E C F ，中序遍历序列为 D B E A C F ，则其后序遍历序列是 ( )。
下面函数用来计算二叉树的高度，横线处应填写？
class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None def height(root): if root is None: return 0 leftH = height(root.left) rightH = height(root.right) return ________
下面代码实现二叉树深度优先搜索 (迭代版前序遍历)，横线处应当填写？
class TreeNode: def __init__(self, val): self.value = val self.left = None self.right = None def dfs(root): if root is None: return s = [] s.append(root) while len(s) > 0: node = s.pop() print(node.value, end=" ") # --------此处填空--------
下面函数用于在二叉搜索树里面查找数值 x ，横线处应当填写？
class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None def searchBST(root, x): if root is None or root.val == x: return root if x < root.val: return searchBST(root.left, x) ____________
有 5 个字符，其出现频率分别为 {2, 4, 5, 9, 12} 。按哈夫曼算法构造编码树，其最小带权路径长度 WPL 为 ？
下面代码使用反射法生成 n 位格雷编码，横线处应该填写？
def gray(n): ans = ["0", "1"] for bit in range(2, n + 1): oldSize = len(ans) for i in range(oldSize - 1, -1, -1): ans.append(_______________) for i in range(oldSize): ans[i] = "0" + ans[i] return ans
下面代码计算爬到第 n 级台阶的方案数，每次可以跨 1 级或者 2 级台阶，横线处应填写？
def ways(n): if n <= 2: return n dp = [0] * (n + 1) dp[1] = 1 dp[2] = 2 for i in range(3, n + 1): dp[i] = ________ return dp[n]
代码求解：从包含非负元素的数组选取若干互不相邻的元素，得到最大和，横线处填写？
def maxSum(a): n = len(a) if n == 0: return 0 if n == 1: return a[0] dp = [0] * n dp[0] = a[0] dp[1] = max(a[0], a[1]) for i in range(2, n): dp[i] = ________ return dp[-1]
下面是一维数组实现的 0/1 背包，内层循环必须从大到小枚举容量，主要原因是？
# n物品数量,W背包总容量 for i in range(n): w = W while w >= weight[i]: dp[w] = max(dp[w], dp[w - weight[i]] + value[i]) w -= 1
下面这段描述：代码可以运行时出错，编译器会自动为 Student 生成无参构造函数。
class Student: def __init__(self, x): self.age = x def main(): s = Student() # 尝试调用无参构造 main()
下面代码是合法的，派生类可以直接访问基类的私有成员 value 。
class Base: def __init__(self): self.__value = 10 class Child(Base): def get(self): return self.__value c = Child() c.get()
下列代码执行后，输出结果为 30 。
from collections import deque q = deque() q.append(10) q.append(20) q.append(30) q.popleft() print(q[0])
一棵完全二叉树按照从上到下、从左到右的顺序，将节点依次存储在数组 tree [1] 、tree [2] …… 中。若节点 tree [i] 存在左孩子，则其左孩子存储在 tree [2*i] 中。
对任意一棵左节点更小的二叉搜索树执行中序遍历，得到的关键字序列一定是非递减的。
class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None def inorder(root): if not root: return inorder(root.left) print(root.val, end=" ") inorder(root.right)
从结点 start 出发运行下面代码访问一棵树；第一次抵达某个结点时经过的边数，一定是 start 到达该结点的最少边数。
from collections import deque # tree为邻接表 def search(start, tree): n = 100 visited = [False] * n dist = [0] * n q = deque() q.append(start) visited[start] = True dist[start] = 0 while q: u = q.popleft() for v in tree[u]: if not visited[v]: visited[v] = True dist[v] = dist[u] + 1 q.append(v)
哈夫曼编码的生成过程基于贪心算法，出现频率越高的字符，其编码长度一定不会比出现频率更低的字符更长。
在 n 位格雷码中，任意两个编码之间都只相差一个二进制位。
下列一维 DP 代码实现的是完全背包问题，处理第 i 种物品时，同一件物品有可能被重复选取。
for i in range(n): w = weight[i] while w <= W: dp[w] = max(dp[w], dp[w - weight[i]] + value[i]) w += 1
下面递归函数可以算出正确的斐波那契数值，该代码时间复杂度与空间复杂度均为 O (n)。
def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2)
给定 n 个整数构成的数组 A=[a1,a2,...,an]。
你需要将数组 A 划分为若干非空连续子段。对于划分得到的某个子段，它的偏差值定义为子段内整数和的平方。划
分方案的偏差值定义为所有子段偏差值之和。
你需要最小化划分方案的偏差值。
形式化地，你可以将 A 划分为若干非空连续子段A1,A2,...,Ak，使得A=A1十A2十...Ak，这里的 + 代表数组的连接。对于 1≤i≤k，设数组包含 mi 个整数。你需要最小化 。
第一行，一个正整数n，表示数组A的长度。
第二行，n个整数a1,a2,....an，表示数组A。
一行，一个整数，表示划分方案偏差值的最小值。
1≤n≤2000，-100 ≤ai≤100
4
1 2 -3 4
6
-1 -1 4 -5 -1 4
0
老师有一棵有 n 个结点的树，结点依次以 1,2,...,n 编号。
老师想将这棵树作为奖品分给两位同学。具体而言，老师会选择一条边并从树上删去它，从而将这棵树分为两个连
通块。两位同学分别可以得到其中一个连通块。
如果有同学拿到的连通块结点数明显小于另一位同学，那么这位同学会不太高兴。为了避免这种情况出现，老师想
知道两个连通块结点数之差的绝对值最小是多少。
第一行，一个正整数n，表示结点数量。
接下来 n-1 行，每行两个正整数ui,vi，表示一条连接结点ui和结点vi的边。
输出一行，一个整数，表示答案。
2≤n≤2×10^4
1 2
2 3
3 4
1 3
1 4
1 5
5 6
2