试卷总分：100分
选择题 15题 30分
判断题 10题 20分
编程题 2题 50分
下列关于 Python 中继承和多态的描述中，错误的是（ ）。
下列代码中，执行 d1.work() 和 d2.work() 输出不同结果的主要原因是（ ）。
class Device: def work(self): print("Device is working") class Printer(Device): def work(self): print("Printer is printing") class Scanner(Device): def work(self): print("Scanner is scanning") if __name__ == '__main__': d1 = Printer() d2 = Scanner() d1.work() d2.work()
下面代码在 main() 中有一行会导致错误，请找出来（ ）。
class Student: def __init__(self, n, s): self.__name = n self.__score = s def get_name(self): return self.__name def set_score(self, s): self.__score = s if __name__ == '__main__': stu = Student("Tom", 85) print(stu.get_name()) # ① stu.set_score(90) # ② print(stu.__score) # ③ print(stu.get_name()) # ④
某文本编辑器把用户输入的字符依次压入栈 S 。用户依次输入 X, Y, Z, W 后，连续执行两次撤销操作。每次撤销都会弹出栈顶一个字符。此时栈从栈底到栈顶的内容是（ ）。
假设循环队列数组长度为 N = 7 ，队空判断条件为 front == rear 。入队和出队操作如下：
N = 7 q = [0] * N front = 3 rear = 3 def enqueue(x): global rear q[rear] = x rear = (rear + 1) % N def dequeue(): global front front = (front + 1) % N
依次执行：
enqueue(10) enqueue(20) enqueue(30) dequeue() enqueue(40) dequeue() enqueue(50)
最终 (front, rear) 的值是（ ）。
以下函数 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
以下代码实现了二叉树的哪种遍历方式？
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def traverse(root): if not root: return print(root.val, end=' ') traverse(root.left) traverse(root.right)
已知一棵二叉树的先序遍历序列为： A B D E H C F G ，中序遍历序列为： D B H E A F C G ，则该二叉树的后序遍历序列是（ ）。
有 6 个字符，它们出现的次数分别为：{3,4,7,8,12,15} ，现在用哈夫曼编码为这些字符编码，最小加权路径长度 WPL 的值为（ ）。
对 n 个不同符号进行哈夫曼编码。若生成的哈夫曼树共有 63 个结点，则 n 的值是（ ）。
在格雷码中，相邻两个编码只能有一位不同。若当前编码为 110 ，则它的下一个编码不可能是（ ）。
给定一棵二叉树，采用广度优先搜索 BFS 返回其右视图，其中右视图中的每个节点都是该层最右侧的节点。横线处应填写（ ）。
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 rightSideView(root): result = [] if not root: return result q = deque([root]) while q: sz = len(q) for i in range(sz): node = q.popleft() __________________________ if node.left: q.append(node.left) if node.right: q.append(node.right) return result
下面代码实现二叉搜索树的插入操作。假设树中不存在重复值，横线处应填写（ ）。
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def insertNode(root, x): if not root: return TreeNode(x) if x < root.val: __________________________ else: root.right = insertNode(root.right, x) return root
给定一个整数数组 a ，每个元素表示一个位置上的数值。要求从数组中选择若干个元素，使得任意两个被选择的元素在原数组中都不相邻，并且所选元素的总和最大。函数 choose(a) 返回能够得到的最大总和，则横线处应填写（ ）。
def choose(a): if not a: return 0 n = len(a) 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 背包的一维动态规划。第 i 个物品重量为 wt[i] ，价值为 val[i] ，背包容量为 W 。横线处应填写（ ）。
def knapsack(W, wt, val): n = len(wt) dp = [0] * (W + 1) for i in range(n): for w in range(W, wt[i] - 1, -1): __________________________ return dp[W]
Python 中没有虚方法的概念， __init__ 也不能声明为虚方法，且构造方法不实现运行时多态。
在 Python 中，执行 del 删除一个子类对象时，会自动先调用子类的 __del__ 方法，再调用父类的 __del__ 方法。
在 Python 标准库中， list 模拟栈时， list 非空的场景下， pop() 函数不传参数被调用时，会返回栈顶元素并将其删除。
程序运行后会输出 2 。
from collections import deque q = deque() q.append(1) q.append(2) q.append(3) q.popleft() print(q[0])
以下函数可以正确完成二叉搜索树的插入，并保持二叉搜索树性质。
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None def insertNode(root, x): if not root: return TreeNode(x) if x < root.val: root.right = insertNode(root.right, x) else: root.left = insertNode(root.left, x) return root
哈夫曼编码一定唯一，只要字符频率相同，得到的编码也一定完全相同。
若用数组按层序存储完全二叉树，且根节点下标为 0 ，则下标为 i 的节点左孩子下标为 2 * i + 1 ，右孩子下标为 2 * i + 2 。
以下代码可以正确地按层换行输出二叉树的节点值。
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 printByLevel(root): if not root: return q = deque([root]) while q: for i in range(len(q)): cur = q.popleft() print(cur.val, end=' ') if cur.left: q.append(cur.left) if cur.right: q.append(cur.right) print()
使用栈非递归实现二叉树前序遍历时，若希望先访问左子树，通常应先将右孩子入栈，再将左孩子入栈。
动态规划问题通常要求具有最优子结构，并且常常存在重叠子问题。
寒假到了，小杨同学打算找一份兼职，顺便体验一下打工人的生活。
小杨同学给一家蛋糕店发送了一份自己的简历，希望可以在寒假来这里帮忙。店长最近正好遇到了一个难题：店里每天会做一条长条蛋糕，但是不同长度的蛋糕块卖出的价格不同，应该怎么分才能卖得最多呢？
有趣的是店长曾经学习过计算机专业。他最近对动态规划算法很感兴趣，于是打算用这个问题考一考小杨同学，问题如下：
给定一条长度为 n 的长条蛋糕和一个价格表，该价格表表示长度为 i（i=1,2,..,n）的蛋糕块的价格为 pi。求蛋糕的分割方案，使得总销售价格最大，注意蛋糕块的长度必须为整数。
第一行一个正整数n(1≤n≤10^3)，表示长条蛋糕的总长度。
第二行n个正整数p1,p2,...,pn(1≤pi≤10^5)，表示不同长度蛋糕块的价格。
一行一个正整数，表示最大总销售价格。
1≤n≤10^3，1≤pi≤10^5
4
1 5 8 9
10
1 5 8 9 10 17 17 20 24 30
30
给定一棵包含 n 个结点的有根二叉树，结点依次以 1,2,...,n 编号，根结点编号为 1。
对于结点 i，其左儿子的编号记为 li，右儿子编号记为 ri。特别地，如果左儿子不存在则 li=0，如果右儿子不存在则 ri=0。
树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有 n 棵子树中，有多少棵子树是满二叉树。满二叉树是指所有叶子深度均相同，且除叶子外均有两个儿子的二叉树，例如以下三棵二叉树均是满二叉树：
() () () / \ / \ () () () () / \ / \ () () () ()
例如，
() / \ () ()
在上面这棵有 3 个节点的二叉树中，有 3 个子树是满二叉树（包括整个树本身，及所有的单个叶子节点）；
又例如，
(1) / \ (2) (3) / \ (4) (5)
在上面这棵有 5 个节点的二叉树中，有 4 个子树是满二叉树（包括节点 3 的子树，以及所有单个叶子节点）。
第一行，一个正整数 n，表示有根二叉树结点数量。
接下来 n 行，每行两个非负整数li,ri，表示结点 i 的左儿子编号和右儿子编号，整数之间以空格分隔。
输出一行，一个整数，表示所有子树中满二叉树的数量。
对于所有测试点，保证1≤n≤10^5
2 3
4 0
0 0
2
3