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

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

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

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

bool isCompleteTree(TreeNode* root) {
if (root == nullptr) return true;
queue<TreeNode*> q;
q.push(root);
bool hasNull = false;
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (node == nullptr) {
hasNull = true;
} else {
if (hasNull) return false;
q.push(node->left);
q.push(node->right);
}
}
return true;
}

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

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

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

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

以下代码实现了循环队列的哪种操作？

以下代码实现了二叉树的深度优先搜索（DFS），并统计叶子结点的数量，则横线上应填写（ ）。

以下代码实现了二叉树的广度优先搜索（BFS），并查找特定值的节点，则横线上应填写（ ）。

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

以下代码实现了0/1背包问题的动态规划解法。假设物品重量为weights[]，价值为values[]，背包容量为W，横线上应填写（ ）。

int knapsack(int W, vector<int>& weights, vector<int>& values) {
int n = weights.size();
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
if (weights[i-1] > j) {
dp[i][j] = dp[i-1][j]; // 当前物品装不下
} else {
dp[i][j] = max(_________________________); // 在此处填入代码
}
}
}
return dp[n][W];
}

以下代码用于检查字符串中的括号是否匹配，横线上应填写（ ）。

关于下面代码，说法错误的是（ ）。（代码包含基类Shape和派生类Circle、Rectangle，使用虚函数实现多态）

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

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

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

以下代码实现的是二叉树的中序遍历：

C++支持构造函数重载，但默认无参数的构造函数只能有一个。

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

在动态规划解决一维硬币找零问题时，若硬币面额为[1,3,4]，目标金额为6，则最少需要2枚硬币（3+3）。

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

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

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

树上漫步

小A有一棵n个结点的树，这些结点依次以1~n标号。小A想在这棵树上漫步。具体来说，小A会从树上的某个结点出发，每一步可以移动到与当前结点相邻的结点，并且小A只会在偶数步（可以是零步）后结束漫步。现在小A想知道，对于树上的每个结点，从这个结点出发开始漫步，经过偶数步能结束漫步的结点有多少个（可以经过重复的节点）。

第一行，一个正整数n。
接下来n-1行，每行两个整数u,v，表示树上有连接结点u和结点v的边。

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

【样例输入1】

3
1 3
2 3
【样例输出1】

2 2 1
对于所有测试点，保证1≤n≤2×10^5。

环线

小A喜欢坐地铁。地铁环线有n个车站，依次以1~n标号。车站i(i<n)的下一个车站是车站i+1。特殊地，车站n的下一个车站是车站1。小A会从某个车站出发，乘坐地铁环线到某个车站结束行程，这意味着小A至少会经过一个车站。小A不会经过一个车站多次。当小A乘坐地铁环线经过车站i时，小A会获得a_i点快乐值。请你安排小A的行程，选择出发车站与结束车站，使得获得的快乐值总和最大。

第一行，一个正整数n，表示车站的数量。
第二行，n个整数a_i，分别表示经过每个车站时获得的快乐值。

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

【样例输入1】

4
-1 2 3 0
【样例输出1】

5
对于所有测试点，保证1≤n≤2×10^5，-10^9≤a_i≤10^9。