以下代码用于生成 位格雷编码。横线上应填写（ ）。

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

给定一个二叉排序树（BST），其中节点的值均为正整数。以下关于BST的说法中，错误的是：

以下代码实现了二叉排序树的哪种操作？

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

以下代码中，类的构造函数被调用了（ ）次。

import copy
class MyClass:
	def __init__(self):
		print("Constructor called!")
if __name__ == "__main__":
	obj1 = MyClass()
	obj2 = copy.deepcopy(obj1)

给定字符集 {A, B, C, D} 的出现频率分别为 {5, 1, 6, 2} ，则正确的哈夫曼编码是（ ）。

以下关于完全二叉树的代码描述，正确的是（ ）。

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

关于动态规划的描述，正确的是（ ）。

以下代码实现了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
	__________________

以下代码实现了二叉树的深度优先搜索（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:
			_______________________
	return count

以下代码中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 fuction1(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

哈夫曼编码是一种用于数据压缩的算法。以下关于哈夫曼编码的描述中，不正确的是（ ）。

以下代码实现了树的哪种遍历方式？

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)

在面向对象编程中，类是一种重要的概念。下面关于类的描述中，不正确的是（ ）。

以下代码实现了二叉树的广度优先搜索（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
	__________________
	return None

在动态规划解决一维硬币找零问题时，若硬币面额为 [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

def traverse(root):
	if root is None:
		return
	traverse(root.left)
	print(root.val, end=" ")
	traverse(root.right)

二叉排序树（BST）中，若某节点的左子树为空，则该节点一定是树中的最小值节点。

python可以直接定义多个构造函数，但默认无参数的构造函数只能有一个。

以下代码创建的树是一棵完全二叉树：

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)

在树的深度优先搜索（DFS）中，使用队列作为辅助数据结构以实现“先进后出”的访问顺序。

栈和队列均可以用双向链表实现，插入和删除操作的时间复杂度为 O(1) 。

哈夫曼树在构造过程中，每次合并权值最小的两个节点，最终生成的树带权路径和最小。

面向对象编程中，封装是指将数据和行为绑定在一起，并对外隐藏实现细节。

格雷编码的相邻两个编码之间必须有多位不同，以避免数据传输错误。

环线

题目描述

小 A 喜欢坐地铁。地铁环线有 n个车站，依次以 1,2,...,n标号。车站 i（ 1≤i＜n）的下一个车站是车站i+1 。

特殊地，车站n 的下一个车站是车站1 。

小 A 会从某个车站出发，乘坐地铁环线到某个车站结束行程，这意味着小 A 至少会经过一个车站。小 A 不会经过一个车站多次。当小 A 乘坐地铁环线经过车站 i时，小 A 会获得 ai点快乐值。请你安排小 A 的行程，选择出发车站与结束车站，使得获得的快乐值总和最大。

输入格式

第一行，一个正整数n ，表示车站的数量。

第二行， n个整数a1,a2,...an, ，分别表示经过每个车站时获得的快乐值。

输出格式

一行，一个整数，表示小 A 能获得的最大快乐值。

输入样例 1

4
-1 2 3 0

输出样例 1

5

输入样例 2

5
-3 4 -5 1 3

输出样例 2

5

数据范围

对于20% 的测试点，保证1≤n≤200 。

对于40 % 的测试点，保证 1≤n≤2000。

对于所有测试点，保证 1≤n≤2*105，-109≤ai≤109 。

树上漫步

题目描述

小 A 有一棵 n个结点的树，这些结点依次以 1,2,...,n标号。

小 A 想在这棵树上漫步。具体来说，小 A 会从树上的某个结点出发，每一步可以移动到与当前结点相邻的结点，并且小 A 只会在偶数步（可以是零步）后结束漫步。

现在小 A 想知道，对于树上的每个结点，从这个结点出发开始漫步，经过偶数步能结束漫步的结点有多少个（可以经过重复的节点）。

输入格式

第一行，一个正整数n 。

接下来n-1 行，每行两个整数ui,vi ，表示树上有一条连接结点ui 和结点vi 的边。

输出格式

一行， n个整数，第 i个整数表示从结点i 出发开始漫步，能结束漫步的结点数量。

输入样例 1

3
1 3
2 3

输出样例 1

2 2 1

输入样例 2

4
1 3
3 2
4 3

输出样例 2

3 3 1 3

数据范围

对于40 % 的测试点，保证1≤n≤103 。

对于所有测试点，保证1≤n≤2*105 。