一、单选题（每题 2 分，共 30 分）

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

{{ select(1) }}

• 类是一个抽象的概念，用于描述具有相同属性和行为的对象集合。
• 类可以包含属性和方法，属性用于描述对象的状态，方法用于描述对象的行为。
• 类可以被实例化，生成具体的对象。
• 类一旦定义后，其属性和方法不能被修改或扩展。

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

{{ select(2) }}

• 哈夫曼编码是一种变长编码，频率高的字符使用较短的编码，频率低的字符使用较长的编码。
• 在构造哈夫曼树时，频率越低的字符离根节点越近，频率越高的字符离根节点越远。
• 哈夫曼编码的生成过程基于贪心算法，每次选择频率最低的两个节点进行合并。
• 哈夫曼编码是一种前缀编码，任何一个字符的编码都不会是另一个字符编码的前缀，因此可以实现唯一解码。

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

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

{{ select(3) }}

• 前序遍历
• 中序遍历
• 后序遍历
• 层次遍历

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

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

{{ select(4) }}

• 该代码用于判断一棵树是否为满二叉树
• 该代码用于判断一棵树是否为完全二叉树
• 该代码用于判断一棵树是否为二叉搜索树
• 该代码用于计算树的高度

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

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

{{ select(5) }}

• 查找
• 插入
• 删除
• 遍历

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

{{ select(6) }}

• $\tt A: 0,\ B: 100,\ C: 11,\ D: 101$
• $\tt A: 11,\ B: 100,\ C: 0,\ D: 101$
• $\tt A: 0,\ B: 101,\ C: 11,\ D: 100$
• $\tt A: 10,\ B: 101,\ C: 0,\ D: 100$

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

{{ select(7) }}

• 动态规划算法的时间复杂度总是低于贪心算法。
• 动态规划要求问题必须具有最优子结构和重叠子问题两个性质。
• 动态规划通过递归实现时不需要存储中间结果。
• 动态规划的核心思想是将问题分解为互不重叠的子问题。

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

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

{{ select(8) }}

• $1$
• $2$
• $3$
• $0$

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

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

{{ select(9) }}

• 入队
• 出队
• 查看队首元素
• 判断队列是否为空

10. 以下代码实现了二叉树的深度优先搜索（$\tt 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;
    }
    

{{ select(10) }}

• if (node->left) s.push(node->left);
• if (node->left) s.pop(node->left);
• if (node->left) s.front(node->left);
• if (node->left) s.push(node->right);

11. 以下代码实现了二叉树的广度优先搜索（$\tt 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; // 未找到目标节点
    }
    

{{ select(11) }}

• if (current->left) q.push(current->left);
  if (current->right) q.push(current->right);
  

• if (current->left) q.pop(current->left);
  if (current->right) q.pop(current->right);
  

• if (current->left) q.front(current->left);
  if (current->right) q.front(current->right);
  

• if (current->left) q.push(current->right);
  if (current->right) q.push(current->left);
  

12. 以下代码用于生成 $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;
    }
    

{{ select(12) }}

• result.push_back("1" + prev[i]);
• result.push_back("0" + prev[i]);
• result.push_back(prev[i] + "1");
• result.push_back(prev[i] + "0");

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

{{ select(13) }}

• dp[i-1][j], values[i-1]
• dp[i-1][j], dp[i-1][j - weights[i-1]] + values[i-1]
• dp[i][j-1], values[i-1]
• dp[i-1][j - weights[i-1]] + values[i-1], dp[i][j-1]

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

    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 ________________; //在此处填入代码
    }
    

{{ select(14) }}

• true
• false
• st.empty()
• !st.empty()

15. 关于下面代码，说法错误的是（ ）。

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

{{ select(15) }}

• 语句 Shape* shapePtr = &circle; 和 shapePtr = &rectangle; 出现编译错误
• Shape 为基类，Circle 和 Rectangle 是派生类
• 通过继承，Circle 和 Rectangle 复用了 Shape 的属性和方法，并扩展了新的功能
• Circle 和 Rectangle 通过重写（$\tt override$）基类的虚函数 area 和基类指针，实现了运行时多态

二、判断题（每题 2 分，共 20 分）

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

{{ select(16) }}

• 正确
• 错误

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

{{ select(17) }}

• 正确
• 错误

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

{{ select(18) }}

• 正确
• 错误

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

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

{{ select(19) }}

• 正确
• 错误

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

{{ select(20) }}

• 正确
• 错误

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

{{ select(21) }}

• 正确
• 错误

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

{{ select(22) }}

• 正确
• 错误

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

{{ select(23) }}

• 正确
• 错误

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

   TreeNode* root = new TreeNode{1};
   root->left = new TreeNode{2};
   root->right = new TreeNode{3};
   root->left->left = new TreeNode{4};
   

{{ select(24) }}

• 正确
• 错误

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

{{ select(25) }}

• 正确
• 错误