试卷总分：100分
选择题 15题 30分
判断题 10题 20分
编程题 2题 50分
在Python的面向对象编程中，下列关于“动态绑定（等效于虚函数）”的描述中，错误的是（ ）。
执行如下代码，将输出 钢琴：叮咚叮咚 和 吉他：咚咚当当 而不是两行 乐器在演奏声音 ，这体现了面向对象编程的（ ）特性。
class Instrument: """基类：乐器""" def play(self): print("乐器在演奏声音") def __del__(self): pass class Piano(Instrument): """子类：钢琴""" def play(self): print("钢琴：叮咚叮咚") class Guitar(Instrument): def play(self): print("吉他：咚咚当当") if __name__ == "__main__": instruments = [Piano(), Guitar()] for inst in instruments: inst.play()
执行下面代码，将输出（ ）。
class Instrument: def play(self): print("乐器在演奏声音") def __del__(self): pass class Piano(Instrument): def play(self): print("钢琴：叮咚叮咚") class Guitar(Instrument): def play(self): print("吉他：咚咚当当") if __name__ == "__main__": instruments = [Piano(), Guitar()] for inst in instruments: Instrument.play(inst)
某文本编辑器把用户输入的字符依次压入栈 S。用户依次输入 A , B , C , D 后，用户按了两次撤销（每次撤销，弹出栈顶一个字符）。此时栈从栈底到栈顶的内容是：（ ）。
假设循环队列数组长度为 N ，其中队空判断条件为： front == rear ，队满判断条件为： (rear + 1) % N == front ，出队对应的操作为： front = (front + 1) % N ，入队对于的操作为： rear = (rear + 1) % N 。循环队列长度 N = 6 ，初始 front = 1 , rear = 1 ，执行操作序列为：入队, 入队, 入队, 出队, 入队, 入队，则最终 (front, rear) 的值是（ ）。
以下函数 check() 用于判断一棵二叉树是否为（ ）。
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right from collections import deque 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 traverse(root.left) traverse(root.right) print(root.val, end=" ") if __name__ == "__main__": root = TreeNode(1) root.right = TreeNode(2) root.right.left = TreeNode(3) print("后序遍历结果：", end="") traverse(root)
下面代码实现了哈夫曼编码，则横线处应填写的代码是（ ）。
class Symbol: def __init__(self, ch='', freq=0, code=''): self.ch = ch self.freq = freq self.code = code class Node: def __init__(self, w=0, l=-1, r=-1, sym=-1): self.w = w self.l = l self.r = r self.sym = sym def pop_min_node(nodes, leaf_idx, n, pA, internal_idx, pB): if pA[0] < n and (pB[0] >= len(internal_idx) or nodes[leaf_idx[pA[0]]].w <= nodes[internal_idx[pB[0]]].w): res = leaf_idx[pA[0]] pA[0] += 1 return res else: res = internal_idx[pB[0]] pB[0] += 1 return res def dfs_build_codes(u, nodes, sym_list, path): if u == -1: return if nodes[u].sym != -1: sym_list[nodes[u].sym].code = ''.join(path) return path.append('0') dfs_build_codes(nodes[u].l, nodes, sym_list, path) path.pop() path.append('1') dfs_build_codes(nodes[u].r, nodes, sym_list, path) path.pop() def build_huffman_codes(sym_list): n = len(sym_list) for sym in sym_list: sym.code = '' if n <= 0: return -1 if n == 1: sym_list[0].code = '0' return 0 nodes = [] leaf_idx = [] for i in range(n): leaf_idx.append(len(nodes)) nodes.append(Node(sym_list[i].freq, -1, -1, i)) leaf_idx.sort(key=lambda x: (nodes[x].w, nodes[x].sym)) internal_idx = [] pA = [0] pB = [0] for k in range(1, n): x = pop_min_node(nodes, leaf_idx, n, pA, internal_idx, pB) y = pop_min_node(nodes, leaf_idx, n, pA, internal_idx, pB) z = len(nodes) ______________________________ root = internal_idx[-1] if internal_idx else -1 path = [] dfs_build_codes(root, nodes, sym_list, path) return root if __name__ == "__main__": syms = [ Symbol('A', 5), Symbol('B', 9), Symbol('C', 12), Symbol('D', 13), Symbol('E', 16), Symbol('F', 45) ] root = build_huffman_codes(syms) print(f"哈夫曼树根节点下标：{root}") for sym in syms: print(f"字符 '{sym.ch}' (频率 {sym.freq})：编码 {sym.code}")
以下关于哈夫曼编码的说法，正确的是（ ）。
以下函数实现了二叉排序树（BST）的（ ）操作。
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def op(root, x): if not root: return TreeNode(x) if x < root.val: root.left = op(root.left, x) else: root.right = op(root.right, x) return root
下列代码实现了树的深度优先遍历，则横线处应填入（ ）。
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None def dfs1(root): if not root: return temp = [] temp.append(root) while temp: node = temp[-1] temp.pop() print(node.val, end=" ") if node.right: temp.append(node.right) if node.left: temp.append(node.left) def dfs2(root): if not root: return st = [] st.append(root) while st: node = st[-1] st.pop() print(node.val, end=" ") if node.right: st.append(node.right) __________________
给定一棵普通二叉树（节点值没有大小规律），下面代码判断是否存在值为 x 的结点，则横线处应填入（ ）。
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None from collections import deque def bfs_find(root, x): if not root: return None q = deque() q.append(root) while q: cur = q.popleft() if cur.val == x: return cur ______________________ return None
在二叉排序树（Binary Search Tree, BST）中，假设节点值互不相同。给定如下搜索函数，以下说法 一定正确的是（ ）。
class Node: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def find(root, x): while root: if root.val == x: return True if x < root.val: root = root.left else: root = root.right return False
0/1 背包（每件物品最多选一次）问题通常可用一维动态规划求解，核心代码如下。遍历的方向无所谓，则下面说法正确的是（ ）。
def zero_one_knapsack(items, W): dp = [0] * (W + 1) for w, v in items: for j in range(W, w - 1, -1): dp[j] = max(dp[j], dp[j - w] + v) return dp[W]
以下关于动态规划的说法中，错误的是（ ）。
以下代码中，构造函数被调用的次数是1次。
class Test: init_count = 0 def __init__(self): Test.init_count += 1 print("T ", end="") def __copy__(self): print("（拷贝构造，不触发__init__）", end="") new_obj = Test.__new__(Test) return new_obj if __name__ == "__main__": a = Test() import copy b = copy.copy(a)
面向对象编程中，封装是指将数据和操作数据的方法绑定在一起，并对外隐藏实现细节。
以下代码能够正确统计二叉树中叶子结点的数量。
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def count_leaf(root): if not root: return 0 if not root.left and not root.right: return 1 return count_leaf(root.left) + count_leaf(root.right) if __name__ == "__main__": root1 = TreeNode(1) root1.left = TreeNode(2) root1.right = TreeNode(3) root1.left.left = TreeNode(4) root1.left.right = TreeNode(5) root1.right.right = TreeNode(6) print(f"二叉树1的叶子节点数：{count_leaf(root1)}") root2 = TreeNode(1) print(f"二叉树2的叶子节点数：{count_leaf(root2)}") 1 root3 = None print(f"空树的叶子节点数：{count_leaf(root3)}")
广度优先遍历二叉树可用栈来实现。
函数调用管理可用栈来管理。
在二叉排序树（BST）中，若某结点的左子树为空，则该结点一定是整棵树中的最小值结点。
下面的函数能正确判断一棵树是不是二叉排序树（左边的数字要比当前数字小，右边的数字要比当前数字大）。
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def is_bst(root, min_val=float('-inf'), max_val=float('inf')): if not root: return True if root.val <= min_val or root.val >= max_val: return False return is_bst(root.left, min_val, root.val) and is_bst(root.right, root.val, max_val)
格雷编码相邻两个编码之间必须有多位不同，以避免数据传输错误。
小杨在玩一个闯关游戏，从第 1 关走到第 4 关。每一关的体力消耗如下（下标表示关卡编号）： cost = [0, 3, 5, 2, 4 ] ，其中 cost[i] 表示到达第 i 关需要消耗的体力， cost[0]=0 表示在开始状态，体力消耗为0。小杨每次可以从当前关卡 前进 1 步或 2 步。按照上述规则，从第 1 关到第 4 关所需消耗的最小体力为 7。
假定只有一个根节点的树的深度为1，则一棵有n个节点的完全二叉树，则树的深度为[log2(n)]+1。