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

第 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;
}

第 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;
}

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

第 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) 的值是（ ）。

第 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;
}

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

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

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

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

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

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

第 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;
}

第 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;
}

第 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];
}

第 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];
}

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

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

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

#include <iostream>
using namespace std;

class Base {
public:
	~Base() {
		cout << "Base destructor" << endl;
	}
};

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

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

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

第 4 题 程序运行后会输出 2 。

int main() {
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.pop();
	cout << q.front() << endl;
	return 0;
}

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

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

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

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

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

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

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

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

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

三、编程题（每题 25 分，共 50 分）

第 1 题 条形蛋糕

题面描述

寒假到了，小杨同学打算找一份兼职，顺便体验一下打工人的生活。

小杨同学给一家蛋糕店发送了一份自己的简历，希望可以在寒假来这里帮忙。店长最近正好遇到了一个难题：店里每天会做一条长条蛋糕，但是不同长度的蛋糕块卖出的价格不同，应该怎么分才能卖得最多呢？

有趣的是店长曾经学习过计算机专业。他最近对动态规划算法很感兴趣，于是打算用这个问题考一考小杨同学，问题如下：

- 给定一条长度为 的长条蛋糕和一个价格表，该价格表表示长度为 $i$（$i=1,2,3,\cdots,n$ ）的蛋糕块的价格为 $p_i$。求蛋糕的分割方案，使得总销售价格最大，注意蛋糕块的长度必须为整数。

输入格式

第一行一个正整数 $n$（$1 \le n \le 10^3$），表示长条蛋糕的总长度。

第二行 $n$ 个正整数 $p_1,p_2,\cdots,p_n$（$1 \le p_i \le 10^5$），表示不同长度蛋糕块的价格。

输出格式

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

4
1 5 8 9

10

10
1 5 8 9 10 17 17 20 24 30

30

数据要求

【样例解释】

第一个样例中，长度为 $1$ 的蛋糕价值为 $1$，长度为 $2$ 的蛋糕价值为 $5$，长度为 $3$ 的蛋糕价值为 $8$，长度为 $4$ 的蛋糕价值为 $9$；

总长度为 $4$ 的长条蛋糕，有{4},{1,4},{2,2},{1,1,2},{1,1,1,1} 五种本质不同的分法。

其对应的总销售价格分别为 $9,9,10,7,4$，故最大总销售价格为 $10$。

第二个样例中，长度为 $10$ 的长条蛋糕，销售价格最大的分法为 {10}，最大总销售价格为 $30$。

第 2 题 满二叉树

题面描述

给定一棵包含 $n$ 个结点的有根二叉树，结点依次以 $1,2,\cdots,n$ 编号，根结点编号为 $1$。

对于结点 $i$，其左儿子的编号记为 $l_i$，右儿子编号记为 $r_i$ 。特别地，如果左儿子不存在则 $l_i=0$，如果右儿子不存在则 $r_i=0$。

树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有 $n$ 棵子树中，有多少棵子树是满二叉树。

满二叉树是指所有叶子深度均相同，且除叶子外均有两个儿子的二叉树，例如以下三棵二叉树均是满二叉树：

()   ()    ()
    / \    / \
   () ()  ()  ()
         / \  / \
        () ()() ()

例如，

  ()
 / \
() ()

在上面这棵有 $3$个节点的二叉树中，有$3$ 个子树是满二叉树（包括整个树本身，及所有的单个叶子节点）；

又例如，

    (1)
    / \
  (2) (3)
      / \
    (4) (5)

在上面这棵有 $5$个节点的二叉树中，有 $4$个子树是满二叉树（包括节点$3$ 的子树，以及所有单个叶子节点）。

输入格式

第一行，一个正整数 $n$，表示有根二叉树结点数量。

接下来 $n$行，每行两个非负整数 $l_i,r_i$，表示结点$i$ 的左儿子编号和右儿子编号，整数之间以空格分隔。

输出格式

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

4
2 3
4 0
0 0
0 0

2

3
2 3
0 0
0 0

3

数据要求

对于 $40\%$ 的测试点，保证 $1 \le n \le 500$。

对于所有测试点，保证 $1 \le n \le 10^5$。