GESP2025年03月Python六级试卷
从PDF导入：GESP2025年03月Python六级试卷
试卷题目预览
在面向对象编程中，类是一种重要的概念。下面关于类的描述中，不正确的是（ ）。
哈夫曼编码是一种用于数据压缩的算法。以下关于哈夫曼编码的描述中，不正确的是（ ）。
以下代码实现了树的哪种遍历方式？
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def traverse(root):
if root is None:
return
print(root.val, end=" ")
traverse(root.left)
traverse(root.right)
以下关于完全二叉树的代码描述，正确的是（ ）。
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 is_complete_tree(root):
if root is None:
return True
q = deque()
q.append(root)
has_null = False
while q:
node = q.popleft()
if node is None:
has_null = True
else:
if has_null:
return False
q.append(node.left)
q.append(node.right)
return True
以下代码实现了二叉排序树的哪种操作？
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def op(root, val):
if root is None:
return TreeNode(val)
if val < root.val:
root.left = op(root.left, val)
else:
root.right = op(root.right, val)
return root
给定字符集{A, B, C, D}的出现频率分别为{5, 1, 6, 2}，则正确的哈夫曼编码是（ ）。
关于动态规划的描述，正确的是（ ）。
以下代码中，类的构造函数被调用了（ ）次。
import copy
class MyClass:
def __init__(self):
print("Constructor called!")
if __name__ == "__main__":
obj1 = MyClass()
obj2 = copy.deepcopy(obj1)
以下代码中function1()实现了循环队列的哪种操作？
class CircularQueue:
def __init__(self, k):
self.size = k
self.arr = [0] * k
self.front = -1
self.rear = -1
def is_full(self):
return (self.rear + 1) % self.size == self.front
def is_empty(self):
return self.front == -1
def function1(self, value):
if self.is_full():
return False
if self.is_empty():
self.front = 0
self.rear = (self.rear + 1) % self.size
self.arr[self.rear] = value
return True
以下代码实现了二叉树的深度优先搜索（DFS），并统计了叶子节点的数量。横线上应填写（ ）。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def count_leaf_nodes(root):
if root is None:
return 0
stack = []
stack.append(root)
count = 0
while stack:
node = stack.pop()
if node.left is None and node.right is None:
count += 1
if node.right:
stack.append(node.right)
if node.left:
_______________________
以下代码实现了二叉树的广度优先搜索（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 find_node(root, target):
if root is None:
return None
q = deque()
q.append(root)
while q:
current = q.popleft()
if current.val == target:
return current
__________________
if current.left:
q.append(current.right)
if current.right:
q.append(current.left)
if current.left:
q.append(current.left)
if current.right:
q.append(current.right)
if current.left:
q.append(current)
if current.right:
q.append(current.right)
if current.left:
q.append(current.left)
if current.right:
q.append(current)
以下代码用于生成n位格雷编码。横线上应填写（ ）。
def generate_gray_code(n):
if n == 0:
return ["0"]
if n == 1:
return ["0", "1"]
prev = generate_gray_code(n - 1)
result = ["0" + s for s in prev]
__________________________________
return result
以下代码实现了0/1背包问题的动态规划解法。假设物品重量为weights[]，价值为values[]，背包容量为W，横线上应填写（ ）。
def knapsack(W, weights, values):
n = len(weights)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, W + 1):
if weights[i - 1] > j:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(__________________________________)
return dp[n][W]
以下代码用于检查字符串中的括号是否匹配，横线上应填写（ ）。
def is_balanced(s):
stack = []
for c in s:
if c in '([{:
stack.append(c)
else:
if not stack:
return False
top = stack.pop()
if (c == ')' and top != '(') or \
(c == ']' and top != '[') or \
(c == '}' and top != '{'):
return False
__________________
给定一个二叉排序树（BST），其中节点的值均为正整数。以下关于BST的说法中，错误的是（ ）。
哈夫曼树在构造过程中，每次合并权值最小的两个节点，最终生成的树带权路径和最小。（ ）
格雷编码的相邻两个编码之间必须有多位不同，以避免数据传输错误。（ ）
在树的深度优先搜索（DFS）中，使用队列作为辅助数据结构以实现"先进后出"的访问顺序。（ ）
以下代码实现的是二叉树的中序遍历：（ ）
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def traverse(root):
if root is None:
return
traverse(root.left)
print(root.val, end=" ")
traverse(root.right)
Python可以直接定义多个构造函数，但默认无参数的构造函数只能有一个。（ ）
二叉排序树（BST）中，若某节点的左子树为空，则该节点一定是树中的最小值节点。（ ）
在动态规划解决一维硬币找零问题时，若硬币面额为[1, 3, 4]，目标金额为6，则最少需要2枚硬币（3+3）。（ ）
面向对象编程中，封装是指将数据和行为绑定在一起，并对外隐藏实现细节。（ ）
以下代码创建的树是一棵完全二叉树：（ ）
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
栈和队列均可以用双向链表实现，插入和删除操作的时间复杂度为O(1)。（ ）
树上漫步
时间限制：3.0 s 内存限制：512.0 MB
题目描述：小A有一棵n个结点的树，这些结点依次以1~n标号。小A想在这棵树上漫步。具体来说，小A会从树上的某个结点出发，每一步可以移动到与当前结点相邻的结点，并且小A只会在偶数步（可以是零步）后结束漫步。
现在小A想知道，对于树上的每个结点，从这个结点出发开始漫步，经过偶数步能结束漫步的结点有多少个（可以经过重复的节点）。
第一行，一个正整数n。接下来n-1行，每行两个整数x,y，表示树上有一条连接结点x和结点y的边。
一行，n个整数，第i个整数表示从结点i出发开始漫步，能结束漫步的结点数量。
样例输入： 4 1 3 2 3 4 3 样例输出： 2 2 2 1
环线
时间限制：3.0 s 内存限制：512.0 MB
题目描述：小A喜欢坐地铁。地铁环线有n个车站，依次以1~n标号。车站i（1≤i
第一行，一个正整数n，表示车站的数量。第二行，n个整数a_1~a_n，分别表示经过每个车站时获得的快乐值。
一行，一个整数，表示小A能获得的最大快乐值。
样例输入： 4 -1 2 3 0 样例输出： 5