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

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

class Base {
public:
    virtual void work() { cout << "Base" << endl; }
};
class Derived1 : public Base {
public:
    void work() override { cout << "D1" << endl; }
};
class Derived2 : public Base {
public:
    void work() override { cout << "D2" << endl; }
};
int main() {
    Base* d1 = new Derived1();
    Base* d2 = new Derived2();
    d1->work();
    d2->work();
    delete d1;
    delete d2;
    return 0;
}

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

#include 
using namespace std;
class Animal {
public:
    virtual void speak() { cout << "Animal" << endl; }  // ①
};
class Dog : public Animal {
public:
    void speak() override { cout << "Dog" << endl; }   // ②
};
int main() {
    Animal* a = new Dog();                              // ③
    a->speak();                                          // ④
    delete a;
    return 0;
}

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

假设循环队列数组长度为 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) 的值是（  ）。

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

bool check(TreeNode* root) {
    if (!root) return true;
    queue 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;
}

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

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

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

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

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

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

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

vector rightSideView(TreeNode* root) {
    vector result;
    if (!root) return result;
    queue 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;
}

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

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

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

int choose(vector& a) {
    int n = a.size();
    if (n == 0) return 0;
    vector dp(n + 1, 0);
    dp[1] = a[0];
    for (int i = 2; i <= n; ++i) {
        dp[i] = __________;
    }
    return dp[n];
}

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

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

C++ 中构造函数可以声明为虚函数，从而实现运行时多态。

通过指向 Base 的指针删除 Derived 对象时，一定会先调用 Derived 的析构函数，再调用 Base 的析构函数。

在 C++ STL 中，stack 的 pop() 函数会返回栈顶元素并将其删除。

程序运行后会输出 2。

#include 
#include 
using namespace std;
int main() {
    stack s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.pop();
    s.pop();
    cout << s.top() << endl;
    return 0;
}

下列函数试图将整数 x 插入到一棵二叉搜索树中。假设二叉搜索树满足如下性质：对于任意结点，左子树中所有结点的值均小于该结点的值，右子树中所有结点的值均大于或等于该结点的值。判断该函数是否能够在插入 后保持二叉搜索树性质。

void insert(TreeNode* root, int x) {
    if (!root) { root = new TreeNode(x); return; }
    if (x < root->val) insert(root->left, x);
    else insert(root->right, x);
}

哈夫曼编码一定唯一，只要字符频率相同，得到的编码也一定完全相同。

若用数组按层序存储完全二叉树，且根节点下标为 0，则下标为 i 的节点左孩子下标为 2 * i + 1，右孩子下标为 2 * i + 2。

以下代码可以正确地按层换行输出二叉树的节点值。

void printByLevel(TreeNode* root) {
    if (!root) return;
    queue q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; ++i) {
            TreeNode* node = q.front(); q.pop();
            cout << node->val << " ";
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        cout << endl;
    }
}

使用栈非递归实现二叉树前序遍历时，若希望先访问左子树，通常应先将右孩子入栈，再将左孩子入栈。

动态规划问题通常要求具有最优子结构，并且常常存在重叠子问题。

. 条形蛋糕

试题名称：条形蛋糕
时间限制：1.0 s
内存限制：512.0 MB
寒假到了，小杨同学打算找一份兼职，顺便体验一下打工人的生活。
小杨同学给一家蛋糕店发送了一份自己的简历，希望可以在寒假来这里帮忙。店长最近正好遇到了一个难题：店里每天会做一条长条蛋糕，但是不同长度的蛋糕块卖出的价格不同，应该怎么分才能卖得最多呢？
有趣的是店长曾经学习过计算机专业。他最近对动态规划算法很感兴趣，于是打算用这个问题考一考小杨同学，问题如下：
给定一条长度为 n 的长条蛋糕和一个价格表，该价格表表示长度为 i（i = 1, 2, …, n）的蛋糕块的价格为 Pi。求蛋糕的分割方案，使得总销售价格最大，注意蛋糕块的长度必须为整数。

第一行一个正整数 n（1 ≤ n ≤ 10^3），表示长条蛋糕的总长度。
第二行 n 个正整数 P1, P2, …, Pn（1 ≤ Pi ≤ 10^5），表示不同长度蛋糕块的价格。

一行一个正整数，表示最大总销售价格。

4
1 5 8 9

10
1 5 8 9 10 17 17 20 24 30

10

30

. 满二叉树

试题名称：满二叉树
时间限制：1.0 s
内存限制：512.0 MB
给定一棵包含 n 个结点的有根二叉树，结点依次以 1, 2, …, n 编号，根结点编号为 1。
对于结点 i，其左儿子的编号记为 li，右儿子编号记为 ri。特别地，如果左儿子不存在则 li = 0，如果右儿子不存在则 ri = 0。
树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有 n 棵子树中，有多少棵子树是满二叉树。
满二叉树是指所有叶子深度均相同，且除叶子外均有两个儿子的二叉树。
对于 40% 的测试点，保证 1 ≤ n ≤ 500。
对于所有测试点，保证 1 ≤ n ≤ 10^5。

第一行，一个正整数 n，表示有根二叉树结点数量。
接下来 n 行，每行两个非负整数 li, ri，表示结点 i 的左儿子编号和右儿子编号，整数之间以空格分隔。

输出一行，一个整数，表示所有子树中满二叉树的数量。

3
2 3
0 0
0 0

5
2 3
4 5
0 0
0 0
0 0

3

4