1 单选题（每题 $2$ 分，共 $30$ 分）

1. 以下关于面向对象编程的描述，错误的是（ ）。{{ select(1) }}

• 面向对象编程中的类可以包含属性和方法。
• 封装、继承和多态是面向对象编程的三大基本特性。
• 在C++中，一个类的实例化对象可以通过构造函数进行初始化。
• 在面向对象编程中，一切皆为对象，包括整数、字符等基本数据类型也必须通过类来定义。

2. 以下关于类的继承的描述，正确的是（ ）。{{ select(2) }}

• 派生类可以访问基类的所有成员
• 一个基类可以有多个派生类，一个派生类只能有一个基类。
• 如果基类中存在虚函数，派生类可以使用 $override$ 关键字来重写这些函数。
• 静态成员函数中可以直接调用非静态成员。

3. 在循环队列中，$front$ 指向队首，$rear$ 指向队尾元素的下一个位置，即下一个插入位置，队列容量为 $size$，判断队列为空的条件是（ ）。{{ select(3) }}

• front == rear
• front == (rear + 1) % size
• rear == size - 1
• front == 0

4. 考虑以下C++代码片段，关于类 Rectangle 的描述和使用，哪个选项是正确的？

#include <iostream>
using namespace std;
class Rectangle {
public:
    int width, height;
    Rectangle(int w, int h) : width(w), height(h) {}
    int area() {
        return width * height;
    }
};

int main() {
    Rectangle rect(10, 20);
    cout << "Area: " << rect.area() << endl;
    
    rect.width = 30; 
    cout << "New Area: " << rect.area() << endl;
    
    return 0;
}

{{ select(4) }}

• Rectangle rect(10, 20); 这行代码会报错，因为没有提供参数名称。
• 程序将输出 Area: 200 和 New Area: 600。
• area 函数无法正确计算矩形的面积，因为它不是静态成员函数。
• 不能在 main 函数中直接修改 rect.width，必须通过公共方法来修改。

5. 以下代码实现了对二叉搜索树的遍历，选项中说法错误的是（）

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

{{ select(5) }}

• 代码属于树的中序遍历。
• 输出的数字可能是无序的。
• 该函数使用递归的方式遍历二叉树。
• 若该树是一棵二叉搜索树，则输出的序列是升序的。

6. 关于哈夫曼树的构造，每次应选择（ ）合并。{{ select(6) }}

• 权值最小的两个节点
• 最大权值的节点
• 随机节点
• 深度最深的节点

7. 以下代码定义了一个 Queue 的类：

class Queue {
private:
    int data[5];  
    int front, rear;

public:
    Queue() : front(0), rear(0) {}
    
    bool isEmpty() const { return front == rear; }
    bool isFull() const { return rear == 5; }

    void push(int x) {
        if (isFull()) {
            cout << "Queue full" << endl;
            return;
        }
        data[rear++] = x;
    }

    int pop() {
        if (isEmpty()) {
            throw std::runtime_error("Queue empty");
        }
        return data[front++];
    }
};

在执行了下面的代码后，再执行 q.push(70);，会发生什么？

Queue q; q.push(10); 
q.push(20); q.pop(); q.push(30); 
q.push(40); q.push(50); q.push(60);

{{ select(7) }}

• 输出 "Queue full"，因为当前 rear == 5
• 出现编译错误，因为此时超过了 data 的大小。
• 成功将 $70$ 入队，因为队列中仍有空位
• 输出 "Queue full"，因为当前 rear - front == 4

8. 给定一组字符及其对应的频率如下，根据哈夫曼编码算法生成哈夫曼树，并为每个字符分配相应的编码。下列选项中哪一个是字符 E 的可能的哈夫曼编码？

字符	频率
A	5
B	9
C	12
D	13
E	16
F	45

{{ select(8) }}

• 00
• 10
• 110
• 1111

9. 在栈的操作中，以下描述正确的是（ ）。{{ select(9) }}

• 入栈操作的时间复杂度为 $O(N)$
• 出栈操作的时间复杂度为 $O(1)$
• 栈的访问顺序是“先进先出”
• 栈只能用数组实现

10. 一个有 $124$ 个叶子节点的完全二叉树，最多有多少个节点？{{ select(10) }}

• 247
• 248
• 249
• 250

11. 一棵树的先序遍历：A B D E C F，中序遍历：D B E A F C，其后序遍历为？{{ select(11) }}

• D E B F C A
• E D B F C A
• D E B C F A
• E D B C F A

12. 对于二叉树 A(B(C,D(E,F(G))))，其层序遍历的顺序为？{{ select(12) }}

• C E G F D B A
• C B E D G F A
• A B C D E F G
• A C B D E F G

13. $3$ 位格雷编码的顺序是？{{ select(13) }}

• $000,001,010,011,100,101,110,111$
• $000,001,011,010,110,111,101,100$
• $000,010,001,011,100,110,101,111$
• $000,010,110,100,111,101,011,001$

14. 以下代码片段的输出是（ ）。

#include <iostream>
using namespace std;
class Base {  
public:  
    virtual void show() { cout << "Base"; }  
};  
class Derived : public Base {  
public:  
    void show() override { cout << "Derived"; }  
};  
int main() {  
    Base* b = new Derived();  
    b->show();  
    return 0;  
}

{{ select(14) }}

• Derived
• Base
• BaseDerived
• 编译错误

15. 以下代码的功能是（ ）。

int function(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 0);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    for (int i=2; i<n; i++) 
        dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
    return dp[n-1];
}

{{ select(15) }}

• 计算数组最大子序和
• 计算相邻元素的最大和
• 计算不相邻元素的最大和
• 计算数组平均值

2 判断题（每题 $2$ 分，共 $20$ 分）

1. 完全二叉树的任意一层都必须是满的。{{ select(16) }}

• 正确
• 错误

2. 格雷编码相邻两个编码只有一位不同。{{ select(17) }}

• 正确
• 错误

3. 构造函数不能被重载，只能有一个版本。{{ select(18) }}

• 正确
• 错误

4. 广度优先搜索（BFS）通常使用队列作为辅助数据结构来进行遍历。{{ select(19) }}

• 正确
• 错误

5. 深度优先搜索（DFS）使用队列作为辅助数据结构。{{ select(20) }}

• 正确
• 错误

6. 二叉排序树（二叉搜索树）的中序遍历序列是升序的。{{ select(21) }}

• 正确
• 错误

7. 以下为解决01背包问题的代码，将 for (int j = W; j >= w[i]; j--) 改为 for (int j = w[i]; j <= W; j++) 不会影响结果。

for (int i = 0; i < n; i++) { 
    for (int j = W; j >= w[i]; j--) 
        dp[j] = max(dp[j], dp[j - w[i]] + val[i]);

{{ select(22) }}

• 正确
• 错误

8. 用 BFS 求树的深度，在遍历过程中，如果某个节点 X 为叶子节点，则可以直接停止遍历，因为已经找到了最深的节点。{{ select(23) }}

• 正确
• 错误

9. 完全二叉树中，度为 $1$ 的节点最多只有 $1$ 个。{{ select(24) }}

• 正确
• 错误

10. 可以使用栈来检测一个单向链表是否为回文结构。{{ select(25) }}

• 正确
• 错误