1.
在构建哈夫曼树时 ，每次应该选择（ ） 合并。
2.
⾯向对象的编程思想主要包括以下哪些原则 ( ) ?
3.
在队列中 ，元素的添加和删除是按照（ ）原则进⾏的。
4.
给定⼀个简单的类定义如下，（ ）语句在类的外部正确地创建了⼀个 Circle 对象并调⽤了 getArea 函数？
1 class Circle {
2 private:
3 double radius;
4 public:
5 Circle(double r) : radius(r) {}
6 double getArea() {
7 return 3.14 * radius * radius;
8 }
9 };
5.
以下代码希望能在⼀棵⼆叉排序树中搜索特定的值 ，请在横线处填⼊（ ） ，使其能正确实现相应功能。
1 TreeNode* search(TreeNode* root, int target) {
2 if (root == NULL || root->val == target) {
3 return root;
4 }
5 if (_______________) {
6 return search(root->left, target);
7 } else {
8 return search(root->right, target);
9 }
10 }
6.
3 位格雷编码的正确顺序是（ ） 。
7.
以下动态规划算法的含义与⽬的是（ ） 。
1 int function(vector<int>& nums) {
2 int n = nums.size();
3 if (n == 0)
4 return 0;
5 if (n == 1)
6 return nums[0];
7 vector<int> dp(n, 0);
8 dp[0] = nums[0];
9 dp[1] = max(nums[0], nums[1]);
10 for (int i = 2; i < n; ++i) {
11 dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);
12 }
13 return dp[n - 1];
14 }
8.
阅读以下广度优先搜索的代码：
1 void bfs(TreeNode* root) {
2 if (root == NULL) {
3 return;
4 }
5 queue<TreeNode*> q;
6 q.push(root);
7 while (!q.empty()) {
8 TreeNode* current = q.front();
9 q.pop();
10 cout << current->val << " ";
11 if (current->left) {
12 q.push(current->left);
13 }
14 if (current->right) {
15 q.push(current->right);
16 }
17 }
18 }使用以上算法遍历以下这棵树，可能的输出是（ ）。
9.
给定一个空栈，执行以下操作序列：
操作序列：push(1), push(2), push(3), pop( ), pop( ), push(4), push(5), pop( )
最终栈中的元素是（ ）。
10.
⼀个有 124 个叶⼦节点的完全⼆叉树 ，最多有（ ）个结点。
11.
在求解最优化问题时 ，动态规划常常涉及到两个重要性质， 即最优⼦结构和（ ） 。
12.
若⼀棵⼆叉树的先序遍历为：A, B, D, E, C, F 、 中序遍历为：D, B, E, A, F, C ，它的后序遍历为（ ） 。
13.
线性筛法与埃⽒筛法相⽐的优势是（ ） 。
14.
以下代码使⽤了辗转相除法求解最⼤公因数 ，请在横线处填⼊（ ） ，使其能正确实现相应功能。
1 int gcd(int a, int b) {
2 while (b != 0) {
3 _________________________
4 }
5 return a;
6 }
15.
下⾯的代码⽚段⽤于反转单链表 ，请进⾏（ ） 修改 ，使其能正确实现相应功能。
1 ListNode* reverseLinked List(ListNode* head) {
2 ListNode* prev = nullptr;
3 ListNode* current = head;
4 while (current != nullptr) {
5 ListNode* next = current->next;
6 current->next = next;
7 prev = current;
8 current = next;
9 }
10 return prev;
11 }
1.
哈夫曼树是一种二叉树。（ ）
2.
在动态规划中，状态转移方程的作用是定义状态之间的关系。
3.
继承是将已有类的属性和方法引入新类的过程。（ ）
4.
完全二叉树的任意一层都可以不满。（ ）
5.
删除单向链表中的节点，只需知道待删除节点的地址即可，无需访问前一个节点。
6.
在宽度优先搜索中，通常使用队列来辅助实现。
7.
哈夫曼编码的主要应用领域是有损数据压缩。（ ）
8.
二叉搜索树的查找操作的时间复杂度是O（N） 。
9.
栈的基本操作包括入栈（push）和出栈（pop）。
10.
使用哈夫曼编码对一些字符进行编码，如果两个字符的频率差异最大，则它们的编码可能出现相同的前缀。
1.
试题名称：游戏
3.1.1 题面描述
你有四个正整数n,a,b,c ，并准备用它们玩一个简单的小游戏。
在一轮游戏操作中，你可以选择将n减去a，或是将n减去b。游戏将会进行多轮操作，直到当n≤c时游戏结束。
你想知道游戏结束时有多少种不同的游戏操作序列。两种游戏操作序列不同，当且仅当游戏操作轮数不同，或是某一轮游戏操作中，一种操作序列选择将n减去a，而另一种操作序列选择将n减去b。如果a=b，也认为将n减去a与将n减去b是不同的操作。
由于答案可能很⼤，你只需要求出答案对1000000007 取模的结果。
3.1.2 输入格式
一行四个正整数n,a,b,c 。保证1≤a,b,c≤n 。
3.1.3 输出格式
一行一个整数，表示不同的游戏操作序列数量对1000000007取模的结果。
3.1.4 样例1
3.1.5 样例2
3.1.6 样例3
3.1.7 数据范围
对于20的测试点，保证a=b=c=1，n≤30 。
对于40的测试点，保证c=1，n≤103 。
对于所有测试点，保证1≤n≤2×105 。
2.
试题名称：好斗的牛
3.2.1 问题描述
你有 个牛棚，从左到右一字排开。你希望把N头牛安置到牛棚里。麻烦的是，你的牛很好斗，如果他们附近有其他的牛，他们就会不安分地去挑事。其中，第 i头牛的攻击范围是（ai,bi），这意味着，如果他的左边ai个牛棚或右边bi个牛棚里有其他牛，他就会去挑事。
你想留下连续的一段牛棚，并把其他牛棚都卖掉。请问你最少需要留下多少牛棚，才能保证至少存在一种方案能够把所有的N头牛都安置进剩余的牛棚里，且没有牛会挑事？
3.2.2 输入描述
第一行 1 个正整数N 。
接下来一行N个用空格隔开的正整数a1,……,an 。
接下来一行N个用空格隔开的正整数b1,……,bn 。
3.2.3 输出描述
输出一行一个整数，表示你最少需要留下多少牛棚。
3.2.4 特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
3.2.5 样例输入 1
3.2.6 样例输出 1
3.2.7 样例解释 1
你可以留下4个牛棚，并如此安排你的牛：
3.2.8 样例输入 2
3.2.9 样例输出 2
3.2.10 数据规模
对于20的测试点，保证N=2 ；
对于另外20的测试点，保证N=3 ；
对于80的测试点，保证N≤8 ；
对于所有测试点，保证N≤9，ai,bi≤1000 。