1. $\$ 下列关于 C++ 中继承和多态的描述中，错误的是（ ）。

{{ select(1) }}

• 通过基类指针调用虚函数时，会根据对象实际类型决定调用版本。
• 基类析构函数常声明为虚函数，以便通过基类指针正确释放派生类对象。
• 派生类可以重写基类中的虚函数。
• 构造函数可以声明为 virtual，以便在构造对象时实现动态绑定。

---

2. $\$ 下列代码中，d1->work(); 和 d2->work(); 输出不同结果的主要原因是（ ）。

class Device {
public:
    virtual void work() {
        cout << "Device is working" << endl;
    }
    virtual ~Device() {}
};
class Printer : public Device {
public:
    void work() override {
        cout << "Printer is printing" << endl;
    }
};
class Scanner : public Device {
public:
    void work() override {
        cout << "Scanner is scanning" << endl;
    }
};
int main() {
    Device* d1 = new Printer();
    Device* d2 = new Scanner();
    d1->work();
    d2->work();
    delete d1;
    delete d2;
    return 0;
}

{{ select(2) }}

• Printer 和 Scanner 使用了相同的构造函数。
• work() 是虚函数，且 d1 和 d2 实际指向不同派生类对象，发生动态绑定。
• d1 和 d2 是不同的指针变量。
• 程序中使用了 delete 释放对象。

---

3. $\$ 下面代码在 main() 中有一行会导致编译错误，请找出来。

class Student {
public:
    Student(string n, int s) : name(n), score(s) {}
    string getName() {
        return name;
    }
    void setScore(int s) {
        score = s;
    }
private:
    string name;
    int score;
};
int main() {
    Student stu("Tom", 85);
    cout << stu.getName(); // ①
    stu.setScore(90);     // ②
    stu.score = 100;      // ③
    cout << stu.getName(); // ④
    return 0;
}

{{ select(3) }}

• 第 ① 行
• 第 ② 行
• 第 ③ 行
• 第 ④ 行

---

4. $\$ 某文本编辑器把用户输入的字符依次压入栈 S。用户依次输入 X、Y、Z、W 后，连续执行两次撤销操作。每次撤销都会弹出栈顶一个字符。此时栈从栈底到栈顶的内容是（ ）。

{{ select(4) }}

• X Y
• X Y Z
• Y Z
• X Z

---

5. $\$ 假设循环队列数组长度为 $N=7$，队空判断条件为 front == rear。入队和出队操作如下：

const int N = 7;
int q[N];
int front = 3, rear = 3;
void enqueue(int x) {
    q[rear] = x;
    rear = (rear + 1) % N;
}
void dequeue() {
    front = (front + 1) % N;
}

依次执行：

enqueue(10);
enqueue(20);
enqueue(30);
dequeue();
enqueue(40);
dequeue();
enqueue(50);

最终 $(front,rear)$ 的值是（ ）。

{{ select(5) }}

• $(5,1)$
• $(4,0)$
• $(5,0)$
• $(3,1)$

---

6. $\$ 以下函数 check() 用于判断一棵二叉树是否为（ ）。

bool check(TreeNode* root) {
    if (!root) return true;
    queue<TreeNode*> q;
    q.push(root);
    bool hasNull = false;
    while (!q.empty()) {
        TreeNode* cur = q.front();
        q.pop();
        if (cur == nullptr) {
            hasNull = true;
        } else {
            if (hasNull) return false;
            q.push(cur->left);
            q.push(cur->right);
        }
    }
    return true;
}

{{ select(6) }}

• 满二叉树
• 完全二叉树
• 二叉搜索树
• 平衡二叉树

---

7. $\$ 以下代码实现了二叉树的哪种遍历方式？

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

{{ select(7) }}

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

---

8. $\$ 已知一棵二叉树的先序遍历序列为：A B D E H C F G，中序遍历序列为：D B H E A F C G，则该二叉树的后序遍历序列是（ ）。

{{ select(8) }}

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

---

9. $\$ 有 $6$ 个字符，它们出现的次数分别为：$3,4,7,8,12,15$，现在用哈夫曼编码为这些字符编码，最小加权路径长度 $WPL$ 的值为（ ）。

{{ select(9) }}

• $113$
• $119$
• $126$
• $31$

---

10. $\$ 对 $n$ 个不同符号进行哈夫曼编码。若生成的哈夫曼树共有 $63$ 个结点，则 $n$ 的值是（ ）。

{{ select(10) }}

• $31$
• $32$
• $63$
• $64$

---

11. $\$ 在格雷码中，相邻两个编码只能有一位不同。若当前编码为 $110$，则它的下一个编码不可能是（ ）。

{{ select(11) }}

• $010$
• $111$
• $100$
• $001$

---

12. $\$ 给定一棵二叉树，采用广度优先搜索 BFS 返回其右视图，其中右视图中的每个节点都是该层最右侧的节点。横线处应填写（ ）。

vector<int> rightSideView(TreeNode* root) {
    vector<int> result;
    if (!root) return result;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; ++i) {
            TreeNode* node = q.front();
            q.pop();
            __________________________
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return result;
}

{{ select(12) }}

• if (i == 0) result.push_back(node->val);
• if (i == sz - 1) result.push_back(node->val);
• result.push_back(q.front()->val);
• if (node->right) result.push_back(node->right->val);

---

13. $\$ 下面代码实现二叉搜索树的插入操作。假设树中不存在重复值，横线处应填写（ ）。

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

{{ select(13) }}

• root->left = insertNode(root->left, x);
• root = insertNode(root->left, x);
• root->right = insertNode(root->left, x);
• insertNode(root->left, x);

---

14. $\$ 给定一个整数数组 a，每个元素表示一个位置上的数值。要求从数组中选择若干个元素，使得任意两个被选择的元素在原数组中都不相邻，并且所选元素的总和最大。函数 choose(vector<int>& a) 返回能够得到的最大总和，则横线处应填写（ ）。

int choose(vector<int>& a) {
    if (a.empty()) return 0;
    int n = a.size();
    if (n == 1) return a[0];
    vector<int> dp(n, 0);
    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]
• max(dp[i - 1], dp[i - 2] + a[i])
• max(dp[i - 2], a[i])
• dp[i - 1] + dp[i - 2]

---

15. $\$ 下面代码实现 $0/1$ 背包的一维动态规划。第 $i$ 个物品重量为 wt[i]，价值为 val[i]，背包容量为 $W$。横线处应填写（ ）。

int knapsack(int W, vector<int>& wt, vector<int>& val) {
    int n = wt.size();
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int w = W; w >= wt[i]; --w) {
            __________________________
        }
    }
    return dp[W];
}

{{ select(15) }}

• dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
• dp[w] = max(dp[w - 1], dp[w - wt[i]] + val[i]);
• dp[w] = dp[w] + val[i];
• dp[w - wt[i]] = max(dp[w], val[i]);

---