1.
在面向对象编程中，下列关于 虚函数 的描述中，错误的是（ ）。
2.
执行如下C++代码，会输出钢琴：叮咚叮咚 和 吉他：咚咚当当 。这体现了面向对象编程的（ ）特性。
3.
关于以下C++代码，说法正确的是（ ）。
4.
某文本编辑器把用户输入的字符依次压入栈 S。用户依次输入 A , B , C , D 后，用户按了两次撤销（每次撤销，弹出栈顶一个字符）。此时栈从栈底到栈顶的内容是：（ ）。
5.
假设循环队列数组长度为 N ，其中队空判断条件为： front == rear ，队满判断条件为： (rear + 1) % N == front ，出队对应的操作为： front = (front + 1) % N ，入队对于的操作为： rear = (rear + 1) % N 。循环队列长度 N = 6 ，初始 front = 1 , rear = 1 ，执行操作序列为：入队, 入队, 入队, 出队, 入队, 入队， 则最终 (front, rear) 的值是（ ）。
6.
以下函数 check() 用于判断一棵二叉树是否为（ ）。
7.
以下c++代码实现了二叉树的（ ）。
void traverse(TreeNode* root) {
if (!root) return;
traverse(root->left);
traverse(root->right);
cout << root->val << " ";
}
8.
下面C++代码实现了哈夫曼编码，则横线处应填写的代码是（ ）。
9.
以下关于哈夫曼编码的说法，正确的是（ ）。
10.
以下函数实现了二叉排序树（BST）的（ ）操作。
TreeNode* op(TreeNode* root, int x) {
if (!root) return new TreeNode(x);
if (x < root->val)
root->left = op(root->left, x);
else
root->right = op(root->right, x);
return root;
}
11.
下列C++代码实现了树的深度优先遍历，则横线处应填入（ ）。
12.
给定一棵普通二叉树（节点值没有大小规律），下面C++代码判断是否存在值为 x 的结点，则横线处应填入（ ）。
13.
在二叉排序树（Binary Search Tree, BST）中，假设节点值互不相同。给定如下搜索函数，以下说法一定正确的是（ ）。
bool find(Node* root, int x) {
while (root) {
if (root->val == x) return true;
root = (x < root->val) ? root->left : root->right;
}
return false;
}
14.
0/1 背包（每件物品最多选一次）问题通常可用一维动态规划求解，核心C++代码如下。则下面说法正确的是（ ）。
for each item (w, v): for (int j = W; j >= w; --j) dp[j] = max(dp[j], dp[j-w] + v);
15.
以下关于动态规划的说法中，错误的是
1.
以下C++代码中，构造函数被调用的次数是1次。
class Test {
public:
T est() { cout << "T "; }
};
int main() {
Test a;
Test b = a;
}
2.
面向对象编程中，封装是指将数据和操作数据的方法绑定在一起，并对外隐藏实现细节。
3.
以下C++代码能够正确统计二叉树中叶子结点的数量。
int countLeaf(TreeNode* root) {
if (!root) return 0;
if (!root->left && !root->right) return 1;
return countLeaf(root->left) + countLeaf(root->right);
}
4.
广度优先遍历二叉树可用栈来实现。
5.
函数调用管理可用栈来管理。
6.
在二叉排序树（BST）中，若某结点的左子树为空，则该结点一定是整棵树中的最小值结点。
7.
下面的函数能正确判断一棵树是不是二叉排序树（左边的数字要比当前数字小，右边的数字要比当前数字 大）。
bool isBST(TreeNode* root, int minVal, int maxVal) {
if (!root) return true;
if (root->val <= minVal || root->val >= maxVal)
return false;
return isBST(root->left, minVal, root->val) &&isBST(root->right, root->val, maxVal);
}
8.
格雷编码相邻两个编码之间必须有多位不同，以避免数据传输错误。
9.
小杨在玩一个闯关游戏，从第 1 关走到第 4 关。每一关的体力消耗如下（下标表示关卡编号）： cost = [ 0, 3, 5, 2, 4 ] ，其中 cost[i] 表示到达第 i 关需要消耗的体力， cost[0]=0 表示在开始状态，体力消耗为 0。小杨每次可以从当前关卡 前进 1 步或 2 步。按照上述规则，从第 1 关到第 4 关所需消耗的最小体力为 7。
10.
假定只有一个根节点的树的深度为1，则一棵有 n 个节点的完全二叉树，则树的深度为 
。
。
1.
试题名称：路径覆盖
时间限制：1.0 s
内存限制：512.0 MB
3.1.1 题目描述
给定一棵有 n 个结点的有根树 T ，结点依次以 1,2,...n编号，根结点编号为 1 。方便起见，编号为 i 的结点称为结点 i 。
初始时 T 中的结点均为白色。你需要将 T 中的若干个结点染为黑色，使得所有叶子到根的路径上至少有一个黑色结点。将结点 i 染为黑色需要代价 ci，你需要在满足以上条件的情况下，最小化染色代价之和。
叶子是指 T 中没有子结点的结点。
3.1.2 输入格式
第一行，一个正整数 n ，表示结点数量。
第二行， n-1个正整数 
，其中 fi表示结点 i 的父结点的编号，保证 fi<i。
第三行， n 个正整数 c1,c2,....,cn，其中 ci 表示将结点 染为黑色所需的代价。
3.1.3 输出格式
一行，一个整数，表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下，染色代价之和的最小值。
3.1.4 样例
3.1.4.1 输入样例 1
4 1 2 3 5 6 2 3
3.1.4.2 输出样例 1
2
3.1.4.3 输入样例 2
7 1 1 2 2 3 3 64 16 15 4 3 2 1
3.1.4.4 输出样例 2
10
3.1.5 数据范围
2.
试题名称：道具商店
时间限制：1.0 s
内存限制：512.0 MB
3.2.1 题目描述
道具商店里有 n 件道具可供挑选。第 i 件道具可为玩家提升 ai 点攻击力，需要 ci 枚金币才能购买，每件道具只能购买一次。现在你有 k 枚金币，请问你最多可以提升多少点攻击力？
3.2.2 输入格式
第一行，两个正整数 n,k，表示道具数量以及你所拥有的金币数量。
接下来 n 行，每行两个正整数 ai,ci，表示道具所提升的攻击力点数，以及购买所需的金币数量。
3.2.3 输出格式
输出一行，一个整数，表示最多可以提升的攻击力点数。
3.2.4 样例
3.2.4.1 输入样例 1
3 5 99 1 33 2 11 3
3.2.4.2 输出样例 1
132
3.2.4.3 输入样例 2
4 100 10 1 20 11 40 33 100 99
3.2.4.4 输出样例 2
110
3.2.5 数据范围
