GESP Python 编程六级 · 2026 年 9 月卷

下列代码执行后的输出结果是（ ）。 1 class Animal: 2 def speak(self): 3 print("Animal ", end="") 4 class Cat(Animal): 5 def speak(self): 6 print("Cat ", end="") 7 def main(): 8 p: Animal = Cat() 9 p.speak() 10 main()

• A.Animal
• B.Cat
• C.Animal Cat
• D.编译错误

下列代码横线处填写哪一项，才可以正确调用父类的带参数构造函数（ ） 1 class Machine: 2 def __init__(self, s): 3 self.id = s 4 class Robot(Machine): 5 def __init__(self, s, n): 6 _______________ 7 self.level = n

• A.Machine(s)
• B.Machine.Machine(s)
• C.super().__init__(s)
• D.self.id = s

下列代码执行后的输出顺序是（ ）。 1 class Base: 2 def __init__(self): 3 print("B ", end="") 4 def __del__(self): 5 print("~B ", end="") 6 class Derived(Base): 7 def __init__(self): 8 super().__init__() 9 print("D ", end="") 10 def __del__(self): 11 print("~D ", end="") 12 def main(): 13 p = Derived() 14 del p 15 main()

• A.B D ~D ~B
• B.B D ~D
• C.D B ~D ~B
• D.B D

下列代码执行后的输出结果是（ ）。 1 s = [] 2 q = [] 3 for i in range(2,7,2): 4 s.append(i) 5 q.append(i) 6 s.pop() 7 q.pop(0) 8 print(s[-1], q[0])

• A.4 4
• B.2 2
• C.6 6
• D.6 2

下面循环队列采用牺牲一个存储单元（空出一个位置）的方法区分队空与队满，full() 函数判断队列是否已满，横线处应填写（ ）。 1 MAXN = 8 2 data = [0] * MAXN 3 front = 0 4 rear = 0 5 def full(): 6 return _______________

• A.rear == front
• B.(front + 1) % MAXN == rear
• C.(rear + 1) % MAXN == front
• D.rear == MAXN - 1

下列函数属于二叉树哪一种遍历（ ） 1 class TreeNode: 2 def __init__(self, val): 3 self.val = val 4 self.left = None 5 self.right = None 6 def visit(root): 7 if root is None: 8 return 9 visit(root.left) 10 print(root.val, end=" ") 11 visit(root.right)

• A.前序遍历
• B.中序遍历
• C.后序遍历
• D.层序遍历

已知一棵二叉树的先序遍历序列为 A B D E C F，中序遍历序列为 D B E A C F，则其后序遍历序列是（ ）。

• A.D E B F C A
• B.D B E F C A
• C.E D B F C A
• D.D E B C F A

下面函数用来计算二叉树的高度，横线处应填写（ ）。 1 class TreeNode: 2 def __init__(self, val): 3 self.val = val 4 self.left = None 5 self.right = None 6 def height(root): 7 if root is None: 8 return 0 9 leftH = height(root.left) 10 rightH = height(root.right) 11 return _______________

• A.leftH + rightH
• B.min(leftH, rightH) + 1
• C.max(leftH, rightH)
• D.max(leftH, rightH) + 1

下面代码实现二叉树深度优先搜索（迭代版前序遍历），横线处应当填写（ ）。 1 class TreeNode: 2 def __init__(self, val): 3 self.value = val 4 self.left = None 5 self.right = None 6 def dfs(root): 7 if root is None: 8 return 9 s = [] 10 s.append(root) 11 while len(s) > 0: 12 node = s.pop() 13 print(node.value, end=" ") 14 # --------此处填空--------

• A.s.append(node.right) s.append(node.left)
• B.s.append(node.left) s.append(node.right)
• C.if node.right: s.append(node.right) if node.left: s.append(node.left)
• D.if node.left: s.append(node.left) if node.right: s.append(node.right)

下面函数用于在二叉搜索树里面查找数值 x，横线处应当填写（ ）。 1 class TreeNode: 2 def __init__(self, val): 3 self.val = val 4 self.left = None 5 self.right = None 6 def searchBST(root, x): 7 if root is None or root.val == x: 8 return root 9 if x < root.val: 10 return searchBST(root.left, x) 11 return _______________

• A.searchBST(root.left, x)
• B.searchBST(root.right, x)
• C.searchBST(root, x + 1)
• D.root.right

有 5 个字符，其出现频率分别为{2, 4, 5, 9, 12}。按哈夫曼算法构造编码树，其最小带权路径长度 WPL 为（ ）。

• A.68
• B.69
• C.71
• D.73

下面代码使用反射法生成 n 位格雷编码，横线处应该填写（ ） 1 def gray(n): 2 ans = ["0", "1"] 3 for bit in range(2, n + 1): 4 oldSize = len(ans) 5 for i in range(oldSize - 1, -1, -1): 6 ans.append(_______________) 7 for i in range(oldSize): 8 ans[i] = "0" + ans[i] 9 return ans

• A."1" + ans[i]
• B.ans[i]
• C."1" + str(i)
• D."0" + ans[i]

下面代码计算爬到第 n 级台阶的方案数，每次可以跨 1 级或者 2 级台阶，横线处应填写（ ）。 1 def ways(n): 2 if n <= 2: 3 return n 4 dp = [0] * (n + 1) 5 dp[1] = 1 6 dp[2] = 2 7 for i in range(3, n + 1): 8 dp[i] = _______________ 9 return dp[n]

• A.dp[i - 1] + 1
• B.dp[i - 1] + dp[i - 2]
• C.dp[i - 2] + 2
• D.2 * dp[i - 1]

代码求解：从包含非负元素的数组选取若干互不相邻的元素，得到最大和，横线处填写（ ） 1 def maxSum(a): 2 n = len(a) 3 if n == 0: 4 return 0 5 if n == 1: 6 return a[0] 7 dp = [0] * n 8 dp[0] = a[0] 9 dp[1] = max(a[0], a[1]) 10 for i in range(2, n): 11 dp[i] = _______________ 12 return dp[-1]

• A.dp[i - 1] + a[i]
• B.dp[i - 2] + a[i]
• C.max(dp[i - 1], dp[i - 2] + a[i])
• D.max(dp[i - 1], a[i])

下面是一维数组实现的 0/1 背包，内层循环必须从大到小枚举容量，主要原因是（ ） 1 # n物品数量，W背包总容量 2 for i in range(n): 3 w = W 4 while w >= weight[i]: 5 dp[w] = max(dp[w], dp[w - weight[i]] + value[i]) 6 w -= 1

• A.保证每件物品最多被选择一次
• B.保证物品必须按照重量从大到小选择
• C.降低时间复杂度到 O(n)
• D.防止数组dp发生越界

下面这段描述：代码可以运行时出错，编译器会自动为 Student 生成无参构造函数。 1 class Student: 2 def __init__(self, x): 3 self.age = x 4 def main(): 5 s = Student() # 尝试调用无参构造 6 main()

下面代码是合法的，派生类可以直接访问基类的私有成员 value。 1 class Base: 2 def __init__(self): 3 self.__value = 10 4 class Child(Base): 5 def get(self): 6 return self.__value 7 c = Child() 8 c.get()

下列代码执行后，输出结果为 30。 1 from collections import deque 2 q = deque() 3 q.append(10) 4 q.append(20) 5 q.append(30) 6 q.popleft() 7 print(q[0])

一棵完全二叉树按照从上到下、从左到右的顺序，将节点依次存储在数组 tree[1]、tree[2]、…… 中。若节点 tree[i] 存在左孩子，则其左孩子存储在 tree[2*i] 中。

对任意一棵左节点更小的二叉搜索树执行中序遍历，得到的关键字序列一定是非递减的。 1 class TreeNode: 2 def __init__(self, val): 3 self.val = val 4 self.left = None 5 self.right = None 6 def inorder(root): 7 if not root: 8 return 9 inorder(root.left) 10 print(root.val, end=" ") 11 inorder(root.right)

从结点 start 出发运行下面代码访问一棵树；第一次抵达某个结点时经过的边数，一定是 start 到达该结点的最少边数。 1 from collections import deque 2 # tree为邻接表 3 def search(start, tree): 4 n = 100 5 visited = [False] * n 6 dist = [0] * n 7 q = deque() 8 q.append(start) 9 visited[start] = True 10 dist[start] = 0 11 while q: 12 u = q.popleft() 13 for v in tree[u]: 14 if not visited[v]: 15 visited[v] = True 16 dist[v] = dist[u] + 1 17 q.append(v)

哈夫曼编码的生成过程基于贪心算法，出现频率越高的字符，其编码长度一定不会比出现频率更低的字符更长。

在 n 位格雷码中，任意两个编码之间都只相差一个二进制位。

下列一维 DP 代码实现的是完全背包问题，处理第 i 种物品时，同一件物品有可能被重复选取。 1 for i in range(n): 2 w = weight[i] 3 while w <= W: 4 dp[w] = max(dp[w], dp[w - weight[i]] + value[i]) 5 w += 1

下面递归函数可以算出正确的斐波那契数值，该代码时间复杂度与空间复杂度均为 O(n)。 1 def fib(n): 2 if n <= 1: 3 return n 4 return fib(n - 1) + fib(n - 2)

试题名称：数组划分 时间限制：1.0 s　内存限制：512.0 MB 题目描述：给定 n 个整数构成的数组 A = [a_1, a_2, …, a_n]。 你需要将数组 A 划分为若干非空连续子段。对于划分得到的某个子段，它的偏差值定义为子段内整数和的平方。划分方案的偏差值定义为所有子段偏差值之和。 你需要最小化划分方案的偏差值。 形式化地，你可以将 A 划分为若干非空连续子段 A_1, A_2, …, A_k，使得 A = A_1 + A_2 + … + A_k，这里的 + 代表数组的连接。对于 1 ≤ i ≤ k，设数组 A_i = [a_1^(i), …, a_{m_i}^(i)] 包含 m_i 个整数。你需要最小化 Σ_{i=1}^{k} (Σ_{j=1}^{m_i} a_j^(i))^2。 输入格式：第一行，一个正整数 n，表示数组 A 的长度。 第二行，n 个整数 a_1, a_2, …, a_n，表示数组 A。 输出格式：一行，一个整数，表示划分方案偏差值的最小值。 输入样例1：4 1 2 -3 4 输出样例1：6 输入样例2：6 -1 -1 4 -5 -1 4 输出样例2：0 数据范围：对于 40% 的测试点，保证 0 ≤ a_i ≤ 50。 对于所有测试点，保证 1 ≤ n ≤ 2000，−100 ≤ a_i ≤ 100。

作答说明：按题目要求完成程序或作品；需要在线运行与自动判分时，可在站内选择「在线考试」。

试题名称：分树规划 时间限制：1.0 s　内存限制：512.0 MB 题目描述：老师有一棵有 n 个结点的树，结点依次以 1, 2, …, n 编号。 老师想将这棵树作为奖品分给两位同学。具体而言，老师会选择一条边并从树上删去它，从而将这棵树分为两个连通块。两位同学分别可以得到其中一个连通块。 如果有同学拿到的连通块结点数明显小于另一位同学，那么这位同学会不太高兴。为了避免这种情况出现，老师想知道两个连通块结点数之差的绝对值最小是多少。 输入格式：第一行，一个正整数 n，表示结点数量。 接下来 n − 1 行，每行两个正整数 u_i, v_i，表示一条连接结点 u_i 和结点 v_i 的边。 输出格式：输出一行，一个整数，表示答案。 输入样例1：4 1 2 2 3 3 4 输出样例1：0 输入样例2：6 1 2 1 3 1 4 1 5 5 6 输出样例2：2 数据范围：对于 40% 的测试点，保证 2 ≤ n ≤ 500。 对于所有测试点，保证 2 ≤ n ≤ 2 × 10^4。

作答说明：按题目要求完成程序或作品；需要在线运行与自动判分时，可在站内选择「在线考试」。