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

1. 下列代码执行后的输出结果是（ ）。

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

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

int main() {
    Animal *p = new Cat();
    p->speak();
    delete p;
    return 0;
}

{{ select(1) }}

• Animal
• Cat
• Animal Cat
• 编译错误

2. 下列代码中，横线处应填写（ ），才能正确调用基类的带参数构造函数。

class Machine {
    protected:
    string id;

     public:
     Machine(string s) : id(s) {}
};

class Robot : public Machine {
    int level;

     public:
     Robot(string s, int n) : __________, level(n) {}
};

{{ select(2) }}

• Machine(s)
• Machine::id(s)
• super(s)
• id(s)

3. 下列代码执行后的输出顺序是（ ）。

class Base {
    public:
    Base() {
        cout << "B ";
    }
    virtual ~Base() {
        cout << "~B ";
    }
};

class Derived : public Base {
    public:
    Derived() {
        cout << "D ";
    }
    ~Derived() {
        cout << "~D ";
    }
};

int main() {
    Base *p = new Derived();
    delete p;
    return 0;
}

{{ select(3) }}

• B D ~B ~D
• D B ~D ~B
• B D ~D ~B
• B D ~B

4. 下列代码执行后的输出结果是（ ）。

stack<int> s;
queue<int> q;
for (int i = 2; i <= 6; i += 2) {
    s.push(i);
    q.push(i);
}
s.pop();
q.pop();
cout << s.top() << " " << q.front();

{{ select(4) }}

• 2 4
• 4 4
• 4 6
• 6 2

5. 下面循环队列采用“空出一个位置”的方式区分队空和队满。横线处应填写（ ）。

const int MAXN = 8;
int data[MAXN];
int front = 0, rear = 0;

bool full() {
    return __________________________;
}

{{ select(5) }}

• rear == front
• (front + 1) % MAXN == rear
• (rear + 1) % MAXN == front
• rear == MAXN - 1

6. 下列函数实现了二叉树的哪种遍历方式（ ）。

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

{{ select(6) }}

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

7. 已知一棵二叉树的先序遍历序列为 A B D E C F ，中序遍历序列为 D B E A C F ，则其后序遍历序列是（ ）。

{{ select(7) }}

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

8. 下面函数用于计算二叉树的高度，横线处应填写（ ）。

int height(TreeNode *root) {
    if (root == nullptr)
        return 0;
    int leftH = height(root->left);
    int rightH = height(root->right);
    return __________________________;
}

{{ select(8) }}

• leftH + rightH
• min(leftH, rightH) + 1
• max(leftH, rightH)
• max(leftH, rightH) + 1

9. 以下代码实现二叉树左子树优先的深度优先搜索算法，则横线上应填写（ ）。

void dfs(TreeNode *root) {
    if (root == nullptr)
        return;

     stack<TreeNode *> s;
     s.push(root);
     while (!s.empty()) {
         TreeNode *node = s.top();
         s.pop();
         cout << node->value << " ";

         ———————————————————————— // 在此处填入代码
     }
}

{{ select(9) }}

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

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

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

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

10. 下面函数在二叉搜索树中查找值 x 。横线处应填写（ ）。

TreeNode *searchBST(TreeNode *root, int x) {
    if (root == nullptr || root->val == x)
        return root;
    if (x < root->val)
        return searchBST(root->left, x);
    return __________________________;
}

{{ select(10) }}

• searchBST(root->left, x)
• searchBST(root->right, x)
• searchBST(root, x + 1)
• root->right

11. 有 5 个字符，其出现频率分别为 2、4、5、9、12。按哈夫曼算法构造编码树，其最小带权路径长度 WPL 为（ ）。

{{ select(11) }}

• 68
• 69
• 71
• 73

12. 下面代码用反射法生成 n 位格雷编码，横线处应填写（ ）。

vector<string> gray(int n) {
    vector<string> ans = {"0", "1"};
    for (int bit = 2; bit <= n; ++bit) {
        int oldSize = ans.size();
        for (int i = oldSize - 1; i >= 0; --i)
            ans.push_back(__________________________);
        for (int i = 0; i < oldSize; ++i)
            ans[i] = "0" + ans[i];
    }
    return ans;
}

{{ select(12) }}

• ans[i] + "1"
• "0" + ans[i]
• "1" + ans[i]
• ans[oldSize - i - 1]

13. 下面代码计算走到第 n 级台阶的方法数，每次可以走 1 级或 2 级。横线处应填写（ ）。

int ways(int n) {
    if (n <= 2)
        return n;
    vector<int> dp(n + 1);
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; ++i)
        dp[i] = __________________________;
    return dp[n];
}

{{ select(13) }}

• dp[i - 1] + 1
• dp[i - 1] + dp[i - 2]
• dp[i - 2] + 2
• 2 * dp[i - 1]

14. 下面代码求从包含非负元素的数组中选择若干个互不相邻元素所能得到的最大和。横线处应填写（ ）。

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

{{ select(14) }}

• dp[i - 1] + a[i]
• dp[i - 2] + a[i]
• max(dp[i - 1], dp[i - 2] + a[i])
• max(dp[i - 1], a[i])

15. 下面是一维数组实现的 0/1 背包。内层循环必须从大到小枚举容量，主要原因是（ ）。

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

{{ select(15) }}

• 保证每件物品最多被选择一次
• 保证物品必须按照重量从大到小选择
• 降低时间复杂度到 $O(n)$
• 防止数组 dp 发生越界

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

16. 下列代码可以正常编译，因为编译器会自动为 Student 类生成一个无参数构造函数。

class Student {
    public:
    Student(int x) {
        age = x;
    }

     private:
     int age;
};

int main() {
    Student s;
}

{{ select(16) }}

• 正确
• 错误

17. 下列代码合法，因为派生类可以直接访问基类的私有成员 value 。

class Base {
    private:
    int value = 10;
};

class Child : public Base {
    public:
    int get() {
        return value;
    }
};

{{ select(17) }}

• 正确
• 错误

18. 下列代码执行后，输出结果为 30 。

queue<int> q;
q.push(10);
q.push(20);
q.push(30);
q.pop();
cout << q.front();

{{ select(18) }}

• 正确
• 错误

19. 一棵完全二叉树按照从上到下、从左到右的顺序，将节点依次存储在数组 tree[1] 、 tree[2] 、……中。若节点 tree[i] 存在左孩子，则其左孩子存储在 tree[2 * i] 中。

{{ select(19) }}

• 正确
• 错误

20. 对任意一棵二叉搜索树执行中序遍历，得到的关键字序列一定是非递减的。

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

{{ select(20) }}

• 正确
• 错误

21. 若使用下列代码从节点 start 开始访问一棵树，则第一次到达某个节点时所经过的边数，一定是从start 到该节点的最少边数。

vector<int> tree[100];
bool visited[100];
int dist[100];

void search(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    dist[start] = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : tree[u]) {
            if (!visited[v]) {
                visited[v] = true;
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

{{ select(21) }}

• 正确
• 错误

22. 哈夫曼编码的生成过程基于贪心算法，出现频率越高的字符，其编码长度一定不会比出现频率更低的字符更长。

{{ select(22) }}

• 正确
• 错误

23. 在 $n$ 位格雷码中，任意两个编码之间都只相差一个二进制位。

{{ select(23) }}

• 正确
• 错误

24. 下列一维动态规划代码实现的是完全背包问题，因为在处理第 i 种物品时，同一种物品可能被重复选择。

for (int i = 0; i < n; ++i) {
    for (int w = weight[i]; w <= W; ++w) {
        dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
    }
}

{{ select(24) }}

• 正确
• 错误

25. 下列递归程序能得到正确的斐波那契数，其时间复杂度和空间复杂度都是 $O(n)$。

int fib(int n) {
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}

{{ select(25) }}

• 正确
• 错误