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

void traverse(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << " ";
    traverse(root->left);
    traverse(root->right);
}

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

TreeNode* findNode(TreeNode* root, int target) {
    if (root == nullptr) return nullptr;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* current = q.front();
        q.pop();
        if (current->val == target) {
            return current; // 找到目标节点
        }
        ___________________________________ // 在此处填入代码
    }
    return nullptr; // 未找到目标节点
}

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

vector<string> generateGrayCode(int n) {
    if (n == 0) return {"0"};
    if (n == 1) return {"0", "1"};
    vector<string> prev = generateGrayCode(n - 1);
    vector<string> result;
    for (string s : prev) {
        result.push_back("0" + s); // 在前缀添加 0
    }
    for (int i = prev.size() - 1; i >= 0; i--) {
        __________________________________ // 在此处填入代码
    }
    return result;
}

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

以下代码实现了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];
}

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

class MyClass {
    public:
        MyClass() {
            cout << "Constructor called!" << endl;
        }
};
int main() {
    MyClass obj1;
    MyClass obj2 = obj1;
    return 0;
}

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

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

bool isBalanced(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false; // 无左括号匹配
            char top = st.top();
            st.pop();
            if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return ________________; //在此处填入代码
}

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

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;
}

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

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

int countLeafNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    stack<TreeNode*> s;
    s.push(root);
    int count = 0;
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        if (node->left == nullptr && node->right == nullptr) {
            count++;
        }
        if (node->right) s.push(node->right);
        _____________________________________ // 在此处填入代码
    }
    return count;
}

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

class CircularQueue {
        int* arr;
        int front, rear, size;
    public:
        CircularQueue(int k) {
            size = k;
            arr = new int[k];
            front = rear = -1;
        }
        bool enQueue(int value) {
            if (isFull()) return false;
            if (isEmpty()) front = 0;
            rear = (rear + 1) % size;
            arr[rear] = value;
            return true;
        }
};

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

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

TreeNode* op(TreeNode* root, int val) {
    if (root == nullptr) return new TreeNode(val);
    if (val < root->val) {
        root->left = op(root->left, val);
    } else {
        root->right = op(root->right, val);
    }
    return root;
}

关于下面代码，说法【错误】的是？（ ）

class Shape {
    protected:
        string name;
    public:
        Shape(const string& n) : name(n) {}
        virtual double area() const {
            return 0.0;
        }
};
class Circle : public Shape {
    private:
        double radius; // 半径
    public:
        Circle(const string& n, double r) : Shape(n), radius(r) {}
        double area() const override {
            return 3.14159 * radius * radius;
        }
};
class Rectangle : public Shape {
    private:
        double width; // 宽度
        double height; // 高度
    public:
        Rectangle(const string& n, double w, double h) : Shape(n), width(w), height(h) {
        }
        double area() const override {
            return width * height;
        }
};
int main() {
    Circle circle("MyCircle", 5.0);
    Rectangle rectangle("MyRectangle", 4.0, 6.0);
    Shape* shapePtr = &circle;
    cout << "Area: " << shapePtr->area() << endl;
    shapePtr = &rectangle;
    cout << "Area: " << shapePtr->area() << endl;
    return 0;
}

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

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

以下代码创建的树是一棵完全二叉树。（ ）

TreeNode* root = new TreeNode{1};

root->left = new TreeNode{2};

root->right = new TreeNode{3};

root->left->left = new TreeNode{4};

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

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

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

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

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

以下代码实现的是二叉树的中序遍历。（ ）

void traverse(TreeNode* root) {
    if (root == nullptr) return;
    traverse(root->left);
    cout << root->val << " ";
    traverse(root->right);
}

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

环线

时间限制：1 s，内存限制：512 MB

【问题描述】

小 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<=200000， -10^9<=ai<=10^9。

正确答案： 暂无（答题 0次，答对 0次，正确率：0%）

树上漫步

时间限制：1 s，内存限制：512 MB

【问题描述】

小 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

【数据范围】

对于 20% 的测试点，保证 1<=n<=1000。

对于所有测试点，保证 1<=n<=200000。