一、单选题
1、在构建哈夫曼树时，每次应该选择（ ）合并。
A、 最小权值的节点
B、
最大权值的节点
C、
随机节点
D、
深度最深的节点
2、面向对象的编程思想主要包括以下哪些原则（ ）？
A、
贪心、动态规划、回溯
B、
并发、并行、异步
C、
递归、循环、分治
D、 封装、继承、多态
3、在队列中，元素的添加和删除是按照（ ）原则进行的。
A、 先进先出
B、
先进后出
C、
最小值先出
D、
随机进出
4、给定一个简单的类定义如下，（ ）语句在类的外部正确地创建了一个 Circle 对象并调用了 getArea 函数？
class Circle {
private:
double radius;
public:
Circle(double r) : radius(r) {}
double getArea() {
return 3.14 * radius * radius;
}
};A Circle c = Circle(5.0); c.getArea(c);
B Circle c(5.0); getArea(c);
C Circle c = new Circle(5.0); c.getArea();
D Circle c(5.0); c.getArea();
5、以下代码希望能在一棵二叉排序树中搜索特定的值，请在横线处填入（ ），使其能正确实现相应功能。
TreeNode* search(TreeNode* root, int target) {
if (root == NULL || root->val == target) {
return root;
}
if (_______________) {
return search(root->left, target);
} else {
return search(root->right, target);
}
}A target < root->left
B target < root->val
C target > root->val
D target > root->left
6、3 位格雷编码的正确顺序是（ ）。
A、
000, 001, 010, 011, 100, 101, 110, 111
B、
000, 001, 011, 010, 110, 111, 101, 100
C、 000, 010, 001, 011, 100, 110, 101, 111
D、
000, 010, 110, 100, 111, 101, 011, 001
7、以下动态规划算法的含义与目的是（ ）。
int function(vector<int>& nums) {
int n = nums.size();
if (n == 0)
return 0;
if (n == 1)
return nums[0];
vector<int> dp(n, 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < n; ++i) {
dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);
}
return dp[n - 1];
}A 计算数组 nums 中的所有元素的和
B 计算数组 nums 中相邻元素的最大和
C 计算数组 nums 中不相邻元素的最大和
D 计算数组 nums 中的最小元素
8、阅读以下广度优先搜索的代码：
void bfs(TreeNode* root) {
if (root == NULL) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* current = q.front();
q.pop();
cout << current->val << " ";
if (current->left) {
q.push(current->left);
}
if (current->right) {
q.push(current->right);
}
}
}
使用以上算法遍历以下这棵树，可能的输出是（ ）。
A 1 2 8 9 4 5 3 6 7 10 11
B 1 2 3 4 5 6 7 8 9 10 11
C 1 2 3 8 9 6 4 5 7 10 11
D 1 2 3 8 9 4 5 6 7 10 11
9、给定一个空栈，执行以下操作序列：
操作序列： push(1), push(2), push(3), pop(), pop(), push(4), push(5), pop()
最终栈中的元素是（ ）。
A 1, 2
B 1, 4, 5
C 1, 2, 5
D 1, 4
10、一个有 124 个叶子节点的完全二叉树，最多有（ ）个结点。
A 247
B 248
C 249
D 250
11、在求解最优化问题时，动态规划常常涉及到两个重要性质，即最优子结构和（ ）。
A 重叠子问题
B、
分治法
C、
贪心策略
D、
回溯算法
12、若一棵二叉树的先序遍历为：A, B, D, E, C, F、中序遍历为：D, B, E, A, F, C，它的后序遍历为（ ）。
A D, E, B, F, C, A
B E, D, B, F, C, A
C D, E, B, C, F, A
D E, D, B, C, F, A
13、线性筛法与埃氏筛法相比的优势是（ ）。
A 更容易实现
B 更节省内存
C 更快速
D 更准确
14、以下代码使用了辗转相除法求解最大公因数，请在横线处填入（ ），使其能正确实现相应功能。
int gcd(int a, int b) {
while (b != 0) {
______________________
}
return a;
}A int temp = b; b = a / b; a = temp;
B int temp = a; a = b / a; b = temp;
C int temp = b; b = a % b; a = temp;
D b = a % b; a = b;
15、下面的代码片段用于反转单链表，请进行（ ）修改，使其能正确实现相应功能。
ListNode* reverseLinkedList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* current = head;
while (current != nullptr) {
ListNode* next = current->next;
current->next = next;
prev = current;
current = next;
}
return prev;
}A current->next = next; 应该改为 current->next = prev;
B ListNode* next = current->next; 应该改为 ListNode* next = prev->next;
C current != nullptr 应该改为 current->next != nullptr
D ListNode* prev = nullptr; 应该改为 ListNode* prev = head;
二、判断题
16、哈夫曼树是一种二叉树。( )
A 正确
B 错误
17、在动态规划中，状态转移方程的作用是定义状态之间的关系。( )
A 正确
B 错误
18、继承是将已有类的属性和方法引入新类的过程。( )
A 正确
B 错误
19、完全二叉树的任意一层都可以不满。( )
A 正确
B 错误
20、删除单向链表中的节点，只需知道待删除节点的地址即可，无需访问前一个节点。( )
A 正确
B 错误
21、在宽度优先搜索中，通常使用队列来辅助实现。( )
A 正确
B 错误
22、哈夫曼编码的主要应用领域是有损数据压缩。( )
A 正确
B 错误
23、二叉搜索树的查找操作的时间复杂度是O(N)。( )
A 正确
B 错误
24、栈的基本操作包括入栈（push）和出栈（pop）。( )
A 正确
B 错误
25、使用哈夫曼编码对一些字符进行编码，如果两个字符的频率差异最大，则它们的编码可能出现相同的前缀。( )
A 正确
B 错误
三、实操题
26、游戏
题面描述
你有四个正整数n,a,b,c，并准备用它们玩一个简单的小游戏。
在一轮游戏操作中，你可以选择将n减去a，或是将n减去b。游戏将会进行多轮操作，直到当n≤c时游戏结束。
你想知道游戏结束时有多少种不同的游戏操作序列。两种游戏操作序列不同，当且仅当游戏操作轮数不同，或是某一轮游戏操作中，一种操作序列选择将n减去a，而另一种操作序列选择将n减去b。如果a=b，也认为将n减去a与将n减去b是不同的操作。
由于答案可能很大，你只需要求出答案对1000000007取模的结果。
输入格式
一行四个正整数n,a,b,c。保证1≤a,b,c≤n。
输出格式
一行一个整数，表示不同的游戏操作序列数量对1000000007取模的结果。
样例输入1
1 1 1 1
样例输出1
1
样例输入2
114 51 4 1
样例输出2
176
样例输入3
114514 191 9 810
样例输出3
384178446
数据范围
对于20的测试点，保证a=b=c=1，n≤30。
对于40的测试点，保证c=1，n≤103。
对于所有测试点，保证1≤n≤2×105。
参考答案：对于每个测试点，我们可以使用动态规划来解决这个问题。首先，我们定义一个二维数组dp[i][j]，其中dp[i][j]表示当n=i时，游戏结束于j的不同操作序列的数量。我们可以使用两个变量prev_a和prev_b来分别表示上一轮操作选择将n减去a和将n减去b时的操作序列数量。在每一轮操作中，我们有两种选择：将n减去a或者将n减去b。因此，我们可以得到以下状态转移方程：dp[i][j] = dp[i-a][j-1] + dp[i-b][j-1]其中，dp[i-a][j-1]表示上一轮操作选择将n减去a时的操作序列数量，dp[i-b][j-1]表示上一轮操作选择将n减去b时的操作序列数量。由于我们需要对答案取模，因此在进行状态转移时，我们需要对dp[i][j]取模。最后，我们只需要返回dp[n][c]即可，即当n=n时，游戏结束于c的不同操作序列的数量。
27、好斗的牛
问题描述
你有109个牛棚，从左到右一字排开。你希望把N头牛安置到牛棚里。麻烦的是，你的牛很好斗，如果他们附近有其他的牛，他们就会不安分地去挑事。其中，第i头牛的攻击范围是(ai,bi)，这意味着，如果他的左边ai个牛棚或右边bi个牛棚里有其他牛，他就会去挑事。
你想留下连续的一段牛棚，并把其他牛棚都卖掉。请问你最少需要留下多少牛棚，才能保证至少存在一种方案能够把所有的N头牛都安置进剩余的牛棚里，且没有牛会挑事？
输入描述
第一行 1 个正整数N。
接下来一行N个用空格隔开的正整数a1,...,aN。
接下来一行 个用空格隔开的正整数b1,...,bN。
输出描述
输出一行一个整数，表示你最少需要留下多少牛棚。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 1
2 1 2 1 2
样例输出 1
4
样例解释 1
你可以留下 个牛棚，并如此安排你的牛：
样例输入 2
3 1 2 3 3 2 1
样例输出 2
7
数据规模
对于20的测试点，保证N=2；
对于另外20的测试点，保证N=3；
对于80的测试点，保证N≤8；
对于所有测试点，保证N≤9，ai,bi≤1000。
参考答案：对于每个牛，我们可以尝试从它的右边开始向左扩展牛棚，直到遇到一个不能扩展的牛，即这个牛的攻击范围与已经选择的牛棚有冲突。我们可以同样地从左边开始向右扩展，直到遇到一个不能扩展的牛。然后，我们可以比较左右两个扩展的牛棚数，选择较大的那个作为当前牛的选择。我们可以使用贪心算法来解决这个问题。首先，我们按照a_i从大到小的顺序对牛进行排序。然后，我们从左到右遍历每个牛，对于每个牛，我们尝试从它的右边开始向左扩展牛棚，直到遇到一个不能扩展的牛。我们可以使用一个栈来记录当前已经选择的牛棚。对于每个牛，我们将其放入栈中，并更新栈顶牛的右边攻击范围。然后，我们尝试从栈顶牛的右边开始向左扩展牛棚，直到遇到一个不能扩展的牛。如果栈为空或者栈顶牛的右边攻击范围小于等于0，说明我们已经扩展到了最左边，此时我们可以将当前牛放入栈中，并更新栈顶牛的右边攻击范围。否则，我们需要将栈顶牛弹出，并更新栈顶牛的右边攻击范围，直到栈为空或者栈顶牛的右边攻击范围小于等于0。最后，我们返回栈中牛棚的数量，即为最少需要留下的牛棚数。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
