2024年3月 GESP C++ 6级

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

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

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

给定一个简单的类定义如下，（ ）语句在类的外部正确地创建了一个 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);
    }
}

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

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

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

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

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

使用以上算法遍历以下这棵树，可能的输出是（ ）。

1
/ \
2 3
/ \ \
8 9 6
/ \ \
4 5 7
/ \
10 11

给定一个空栈，执行以下操作序列： 操作序列：push(1), push(2), push(3), pop(), pop(), push(4), push(5), pop() 最终栈中的元素是（ ）。

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

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

若一棵二叉树的先序遍历为：A, B, D, E, C, F、中序遍历为：D, B, E, A, F, C，它的后序遍历为（ ）。

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

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

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

哈夫曼树是一种二叉树。

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

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

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

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

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

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

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

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

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

试题名称：游戏

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

你有四个正整数 $n,a,b,c$，并准备用它们玩一个简单的小游戏。

在一轮游戏操作中，你可以选择将 $n$ 减去 $a$，或是将 $n$ 减去 $b$。游戏将会进行多轮操作，直到当 $n\le c$ 时游戏结束。

你想知道游戏结束时有多少种不同的游戏操作序列。两种游戏操作序列不同，当且仅当游戏操作轮数不同，或是某一轮游戏操作中，一种操作序列选择将 $n$ 减去 $a$，而另一种操作序列选择将 $n$ 减去 $b$。如果 $a=b$，也认为将 $n$ 减去 $a$ 与将 $n$ 减去 $b$ 是不同的操作。

由于答案可能很大，你只需要求出答案对 109+710^9 + 7109+7 取模的结果。

输入格式

一行四个整数 $n,a,b,c$。

输出格式

输出一行一个整数表示答案。

样例输入 #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\le 30$。
• 对 $40\%$ 的数据，$c=1$，n≤103n \leq 10^3n≤103。
• 对全部的测试数据，保证 1≤a,b,c≤n≤2×1051 \leq a,b,c \leq n \leq 2 \times 10^51≤a,b,c≤n≤2×105。

试题名称：好斗的牛

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

你有 10910^9109 个牛棚，从左到右一字排开。你希望把 $n$ 头牛安置到牛棚里。麻烦的是，你的牛很好斗，如果他们附近有其他的牛，他们就会不安分地去挑事。其中，第 $i$ 头牛的攻击范围是 (ai,bi)(a_i, b_i)(ai​,bi​)，这意味着，如果他的左边 aia_iai​ 个牛棚或者右边 bib_ibi​ 个牛棚有其他牛，它就会去挑事。

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

输入格式

第一行一个正整数 $n$。
第二行 $n$ 个正整数 a1,a2,…ana_1, a_2, \dots a_na1​,a2​,…an​。
第三行 $n$ 个正整数 b1,b2,…bnb_1, b_2, \dots b_nb1​,b2​,…bn​。

输出格式

输出一行一个整数表示答案。

样例输入 #1

2
1 2
1 2

样例输出 #1

4

样例输入 #2

3
1 2 3
3 2 1

样例输出 #2

7

说明/提示

样例 1 解释

留下第 1、2、3、4 个牛棚，并在第 $1$、$4$ 两个牛棚分别放下两头牛。

数据规模与约定

• 对 $20\%$ 的数据，保证 $n=2$。
• 另有 $20\%$ 的数据，保证 $n=3$。
• 对 $80\%$ 的数据，保证 $n\le 8$。
• 对于所有的测试数据，保证 $1\le n\le 9$，1≤ai,bi≤1031 \leq a_i, b_i \leq 10^31≤ai​,bi​≤103。