在构建哈夫曼树时，每次应该选择（     ）合并。

3 位格雷编码的正确顺序是（     ）。

在队列中，元素的添加和删除是按照（     ）原则进行的。

给定一个简单的类定义如下，（ ）语句在类的外部正确地创建了一个 Circle 对象并调用了 getArea 函数？

class Circle {

private:

double radius;

public:

Circle(double r) : radius(r) {}

double getArea() {

return 3.14 * radius * radius;

}

};

面向对象的编程思想主要包括以下哪些原则（     ）？

以下代码希望能在一棵二叉排序树中搜索特定的值，请在横线处填入（     ），使其能正确实现相应功能。

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);

}

}

一个有 124 个叶子节点的完全二叉树，最多有（     ）个结点。

在求解最优化问题时，动态规划常常涉及到两个重要性质，即最优子结构和（     ）。

给定一个空栈，执行以下操作序列：

操作序列： push(1), push(2), push(3), pop(), pop(), push(4), push(5), pop()

最终栈中的元素是（     ）。

阅读以下广度优先搜索的代码：

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, B, D, E, C, F、中序遍历为：D, B, E, A, F, C，它的后序遍历为（     ）。

以下动态规划算法的含义与目的是（     ）。

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

}

线性筛法与埃氏筛法相比的优势是（     ）。

以下代码使用了辗转相除法求解最大公因数，请在横线处填入（ ），使其能正确实现相应功能。

int gcd(int a, int b) {

while (b != 0) {

      _____________________

}

return a;

}

下面的代码片段用于反转单链表，请进行（     ）修改，使其能正确实现相应功能。

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;

}

哈夫曼树是一种二叉树。

继承是将已有类的属性和方法引入新类的过程。

在动态规划中，状态转移方程的作用是定义状态之间的关系。

完全二叉树的任意一层都可以不满。

在宽度优先搜索中，通常使用队列来辅助实现。

删除单向链表中的节点，只需知道待删除节点的地址即可，无需访问前一个节点。

哈夫曼编码的主要应用领域是有损数据压缩。

二叉搜索树的查找操作的时间复杂度是 O(N)。

使用哈夫曼编码对一些字符进行编码，如果两个字符的频率差异最大，则它们的编码可能出现相同的前缀。

栈的基本操作包括入栈（push）和出栈（pop）。

游戏

题目描述

你有四个正整数 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

样例2

114 51 4 1

176

样例3

114514 191 9 810

384178446

数据范围

对于 20 的测试点，保证 a=b=c=1，n ≤ 30 。

对于 40 的测试点，保证 c=1， n ≤ 1000。

对于所有测试点，保证1 ≤n ≤ 2*100000 。

好斗的牛

问题描述

你有 10⁹ 个牛棚，从左到右一字排开。你希望把 N 头牛安置到牛棚里。麻烦的是，你的牛很好斗，如果他们附近有其他的牛，他们就会不安分地去挑事。其中，第 i 头牛的攻击范围是 （a_i , b_i），这意味着，如果他的左边 a_i 个牛棚或右边 b_i 个牛棚里有其他牛，他就会去挑事。

你想留下连续的一段牛棚，并把其他牛棚都卖掉。请问你最少需要留下多少牛棚，才能保证至少存在一种方案能够把所有的 N 头牛都安置进剩余的牛棚里，且没有牛会挑事？

输入描述

第一行 1 个正整数 N。

接下来一行 N 个用空格隔开的正整数 a_i,,,, a_N。

接下来一行 N 个用空格隔开的正整数 b_i,,,,b_N。

输出描述

输出一行一个整数，表示你最少需要留下多少牛棚。

特别提醒

在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。

样例输入 1

2
1 2
1 2

样例输出 1

4

样例输入 2

3
1 2 3
3 2 1

样例输出 2

7

数据规模

对于 20的测试点，保证N=2；

对于另外 20的测试点，保证 N=3；

对于 80 的测试点，保证 N≤8；

对于所有测试点，保证 N≤9， a_i,b_i≤1000。