试卷总分：100分
选择题 15题 30分
判断题 10题 20分
编程题 2题 50分
以下关于 Python 类继承的代码，执行后输出结果是？
class Animal: def __init__(self, name): self.name = name def speak(self): return "动物叫声" class Dog(Animal): def speak(self): return f"{self.name}：汪汪汪" class Cat(Animal): def __init__(self, name, color): super().__init__(name) # 调用父类构造方法 self.color = color def speak(self): return f"{self.name}（{self.color}）：喵喵喵" dog = Dog("旺财") cat = Cat("咪宝", "橘色") print(dog.speak(), cat.speak())
下列代码中， s1.draw() 和 s2.draw() 能正确运行并输出不同结果的主要原因是（ ）。
class Shape: def draw(self): print("绘制图形") class Circle(Shape): def draw(self): print("绘制圆形") class Rectangle(Shape): def draw(self): print("绘制矩形") if __name__ == "__main__": s1 = Circle() s2 = Rectangle() s1.draw() s2.draw()
下面的代码在主程序 if __name__ == "__main__": 中有没有一行会导致运行错误，如果有请找出错误行（）
class Pet: def __init__(self, n, a): self._name = n self._age = a def get_name(self): return self._name def birthday(self): self._age += 1 if __name__ == "__main__": cat = Pet("奶茶", 2) print(cat.get_name()) # ① cat.birthday() # ② cat._name = "大橘" # ③ print(cat.get_name()) # ④
游乐园的过山车每次限坐 4 人，用循环队列管理排队（容量 MAX=5 ，空一格判满）。下面代码执行后，循环队列是否已满？ rear 的值是多少？
MAX = 5 queue = [None] * MAX front = 0 rear = 0 def enqueue(x): global rear, queue queue[rear] = x rear = (rear + 1) % MAX def dequeue(): global front front = (front + 1) % MAX if __name__ == "__main__": enqueue(1) enqueue(2) enqueue(3) enqueue(4) dequeue() dequeue() enqueue(5) enqueue(6) print("队列数组：", queue) print("front下标位置：", front) print("rear下标位置：", rear)
在以下计算机系统应用场景中，最适合使用循环队列的是（ ）。
在二叉搜索树（BST）中，若中序遍历的序列为 {1, 2, 3, 4, 5}，且先序遍历的第一个序列元素为 3，则下列说法正确的是（ ）。
某二叉树共有10个结点，记为A~J，已知它的先序遍历序列为：A B D H I E C F J G，中序遍历序列为：H D I B E A F J C G，则该二叉树的后序遍历序列是（ ）。
下列关于树的遍历的说法中，正确的一项是（ ）。
有 6 个字符，它们出现的次数分别为： {2, 3, 3, 4, 6, 8} ，现在用哈夫曼编码为这些字符编码，最小加权路径长度 WPL（每个字符的出现次数 它的编码长度，再把每个字符结果加起来）的值为（ ）。
对n个不同符号的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则 的值是（）。
关于格雷编码（Gray Code），下列说法正确的是（ ）。
给定一棵二叉树，采用广度优先搜索 (BFS) 算法，返回右视图所有节点的值。其中右视图定义为：二叉树的右视图是从树的右侧看过去时可见的节点集合，即右视图中的每个节点都是某一层中最右侧的节点。
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None def rightSideView(root): rightmost_value_at_depth = {} max_depth = -1 node_queue = [] depth_queue = [] node_queue.append(root) depth_queue.append(0) while node_queue: node = node_queue.pop(0) depth = depth_queue.pop(0) if node is not None: max_depth = max(max_depth, depth) rightmost_value_at_depth[depth] = node.val node_queue.append(node.left) node_queue.append(node.right) # (1) depth_queue.append(__________) depth_queue.append(__________) right_view = [] # (2) 补全 for depth in range(____________): right_view.append(rightmost_value_at_depth[depth]) return right_view if __name__ == "__main__": root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.right = TreeNode(5) root.right.right = TreeNode(4) print(rightSideView(root))
下列关于树的深度优先搜索（DFS）的说法中，正确的是（ ）。
小朋友们去邻里拜年，每个家里有不同数量的糖果。规则是：不能连续进入两个相邻的房子（即不能同时取相邻两家的糖果）。目标是拿到最多糖果。以下是代码实现，请补全横线。
def visit(nums): if not nums: return 0 size = len(nums) if size == 1: return nums[0] dp = [0] * size dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i in range(2, size): __________________________ return dp[size - 1] if __name__ == "__main__": nums1 = [1,2,3,1] print(visit(nums1)) nums2 = [2,7,9,3,1] print(visit(nums2)) nums3 = [5] print(visit(nums3)) nums4 = [] print(visit(nums4))
元宵节晚上，小朋友沿着一条发光石板路前进，每次可以向前走 1 块或 2 块石板。若 dp[i] = dp[i - 1] + dp[i - 2] ，下面关于 dp[i] 的含义最合适的是（ ）。
下面定义了一个表示二维坐标点的类 Point ， 并提供了一个带参数的构造函数，但第 ② 行 Point b; 会调用编译器自动生成的默认构造函数，将 b.x 和 b.y 被初始化为 0.0，程序可以正常编译运行。
class Point: def __init__(self, px, py): self.x = px self.y = py def print(self): print(f"({self.x}, {self.y})") if __name__ == "__main__": a = Point(3.0, 4.0) # ① # ② b = Point() a.print()
Python 中的继承支持单继承和多继承，但子类无法直接访问父类的私有成员。
对如下结构的树，执行 travel 函数，输出结果是 1 2 3 4 5 。
1 / \ 2 3 / \ 4 5 class Node: def __init__(self, v): self.val = v self.left = None self.right = None def travel(root): if not root: return stack = [] stack.append(root) while stack: = cur = stack.pop() print(cur.val, end=" ") if cur.right: stack.append(cur.right) if cur.left: stack.append(cur.left) if __name__ == "__main__": root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) travel(root)
若所有字符出现频率相同，则哈夫曼编码一定会得到完全二叉树。
哈夫曼编码是一种变长的前缀编码，在解码时不需要额外的分隔符就能唯一还原，这是因为在哈夫曼树中，任何一个字符的叶子结点都不会成为另一个字符结点的祖先。
在 Python 中使用列表存储按层序遍历的完全二叉树时，若根节点存储在 tree[0] ，则对于任意非空节点tree[i] ，其右孩子（如果存在）必然位于 tree[2 * i + 2] 。
在 Python 中使用列表模拟栈来非递归地实现二叉树的前序遍历，为了保证遍历顺序正确，在处理完当前结点后，应该先将该结点的左孩子压入栈中，然后再将右孩子压入栈中。
设二叉树共有n个结点，函数 preorderTraversal 的时间复杂度为O(n)，空间复杂度为O(n)。
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None def preorder(root, res): if root is None: return res.append(root.val) preorder(root.left, res) preorder(root.right, res) def preorderTraversal(root): res = [] preorder(root, res) return res if __name__ == "__main__": root = TreeNode(1) root.right = TreeNode(2) root.right.left = TreeNode(3) result = preorderTraversal(root) print("前序遍历结果：", result)
以下代码实现了0-1背包问题的一维动态规划解法，内层循环采用经典的逆序遍历方式。若将内层循环改为正序遍历（即 for j in range(w[i], W + 1): ），仍能得到正确答案。
def knapsack_01(): W = 5 w = [2, 3, 4] v = [10, 1, 1] n = 3 dp = [0] * (W + 1) for i in range(n): for j in range(W, w[i] - 1, -1): dp[j] = max(dp[j], dp[j - w[i]] + v[i]) print(dp[W]) knapsack_01()
在动态规划问题中，状态空间相同且没有重复计算的情况下，“状态转移方程+递推”与“递归+记忆化搜索”的时间复杂度通常相同。
给定两个包含 个整数的数组 a=[a1,...,an] 与 b=[b1,...,bn] 。你需要指定若干下标 p1<...<pk（1≤k≤n）使得以下条件成立：
你需要在满足以上条件的前提下最大化 Σ(k,i=1)，也即最大化数组 a 对应下标的整数之和。
第一行，一个正整数n，表示数组长度。
第二行，n个正整数a1,a2,...,an，表示数组a。
第三行，n个正整数b1,b2,...,bn，表示数组b。
一行，一个整数，表示在满足下标条件的前提下，数组a对应下标的整数之和的最大值。
对于所有测试点，保证2≤n≤10^5,0≤ai≤10^9,0≤bi≤n
4
1 2 3 4
3 3 1 1
7
6
1 1 4 5 1 4
1 2 3 2 1 0
11
给定一棵包含 n 个结点的有根二叉树，结点依次以 1,2,3,...,n 编号，根结点编号为 1。
对于结点 i，其左儿子的编号记为 li，右儿子编号记为 ri。特别地，如果左儿子不存在则 li=0，如果右儿子不存在则 ri=0。
树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有 n 棵子树中，有多少棵子树是完全二叉树。
第一行，一个正整数n，表示有根二叉树结点数量。
接下来 n 行，每行两个正整数 li,ri，表示结点 i 的左儿子编号和右儿子编号。
输出一行，一个整数，表示所有子树中完全二叉树的数量。
对于所有测试点，保证1≤n≤10^5
2 3
4 0
0 0
3