E1126 2025-12 CCF-GESP Python六级真题-练习

在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个节点的完全二叉树，则树的深度为[log₂(n)]+1。