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

1. 面向对象编程的三大基本特性是（ ）{{ select(1) }}

• 封装、继承和多态
• 封装、继承和虚函数
• 构造、继承和多态
• 封装、重载和多态

2. 依次将 $1$、$2$、$3$ 压入一个空栈（中途可以弹出），下列不可能得到的出栈序列是（ ）{{ select(2) }}

• 3 2 1
• 2 3 1
• 1 2 3
• 3 1 2

3. 一棵深度为 $4$ 的完全二叉树（根结点的深度为 $1$），最多有（ ）个结点 {{ select(3) }}

• 7
• 15
• 8
• 16

4. 执行以下代码，输出结果是（ ）

#include <iostream>
using namespace std;

class Counter
{
private:
    int c;
public:
    Counter() { c = 0; }
    void add(int x) { c += x; }
    int get() { return c; }
};

int main()
{
    Counter c;
    c.add(5);
    c.add(3);
    cout << c.get();
    return 0;
}

{{ select(4) }}

• 0
• 5
• 8
• 编译错误

5. 下列关于二叉排序树（二叉搜索树）的说法，正确的是（ ）{{ select(5) }}

• 中序遍历得到的序列是升序的
• 左子树所有结点的值都大于根结点的值
• 它一定是完全二叉树
• 删除结点后不需要做任何调整

6. 下列关于哈夫曼编码的说法，正确的是（ ）{{ select(6) }}

• 所有字符的编码长度相同
• 出现频率高的字符编码更短
• 编码可能产生歧义
• 编码长度与字符出现频率无关

7. 循环队列采用「少用一个元素空间」的方法区分队空与队满，队列容量为 size，front 指向队首，rear 指向下一个插入位置，则判断队满的条件是（ ）{{ select(7) }}

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

8. 一棵二叉树的先序遍历为 A B C，中序遍历为 B A C，则其后序遍历为（ ）{{ select(8) }}

• B C A
• C B A
• A B C
• B A C

9. 下列关于 C++ 类继承的说法，正确的是（ ）{{ select(9) }}

• 派生类不能访问基类中的 protected 成员
• C++ 中一个类只能继承一个基类
• 派生类对象创建时，基类的构造函数先执行
• 派生类会丢弃基类的所有成员

10. 队列这种数据结构的特点是（ ）{{ select(10) }}

• 后进先出
• 先进先出
• 只能在中间插入元素
• 元素可以按任意顺序取出

11. 一棵二叉树中有 $10$ 个度为 $2$ 的结点，则它的叶子结点数是（ ）{{ select(11) }}

• 9
• 10
• 11
• 12

12. 给定一组权值 $\{2, 3, 4, 5\}$，构造哈夫曼树，该树的带权路径长度（WPL）是（ ）{{ select(12) }}

• 26
• 30
• 28
• 32

13. $2$ 位格雷编码（相邻两个编码只有一位不同）的序列是（ ）{{ select(13) }}

• 00 01 10 11
• 00 01 11 10
• 00 11 01 10
• 01 10 11 00

14. 执行以下代码，输出结果是（ ）

#include <iostream>
using namespace std;

class Animal
{
public:
    virtual void speak() { cout << "Animal"; }
};

class Dog : public Animal
{
public:
    void speak() override { cout << "Dog"; }
};

int main()
{
    Animal* a = new Dog;
    a->speak();
    return 0;
}

{{ select(14) }}

• Dog
• Animal
• AnimalDog
• 编译错误

15. 下列关于动态规划算法思想的描述，正确的是（ ）{{ select(15) }}

• 每一步都选择当前看来最优的方案
• 穷举所有可能的方案
• 把问题规模不断翻倍
• 把问题分解为子问题并保存子问题的解，避免重复计算

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

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

• 正确
• 错误

2. 类的私有（private）成员可以在类外被任意访问。{{ select(17) }}

• 正确
• 错误

3. 栈是一种先进先出（FIFO）的数据结构。{{ select(18) }}

• 正确
• 错误

4. 在哈夫曼编码中，出现频率最高的字符编码长度一定最长。{{ select(19) }}

• 正确
• 错误

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

• 正确
• 错误

6. 深度优先搜索（DFS）通常使用栈（或递归）来保存待访问的结点。{{ select(21) }}

• 正确
• 错误

7. 二叉搜索树的中序遍历序列是升序的。{{ select(22) }}

• 正确
• 错误

8. 动态规划通过保存子问题的解来避免重复计算。{{ select(23) }}

• 正确
• 错误

9. 一棵深度为 $3$ 的二叉树最多有 $7$ 个结点。{{ select(24) }}

• 正确
• 错误

10. 深度优先搜索总能比广度优先搜索更快地找到最优解。{{ select(25) }}

• 正确
• 错误