GESP 六级 · 2024 真题

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

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

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

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

01class Circle {
02private:
03    double radius;
04public:
05    Circle(double r) : radius(r) {}
06    double getArea() {
07        return 3.14 * radius * radius;
08    }
09};

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

01TreeNode* search(TreeNode* root, int target) {
02    if (root == NULL || root->val == target) {
03        return root;
04    }
05    if (____________) {
06        return search(root->left, target);
07    } else {
08        return search(root->right, target);
09    }
10}

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

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

01int function(vector<int>& nums) {
02    int n = nums.size();
03    if (n == 0)
04        return 0;
05    if (n == 1)
06        return nums[0];
07    vector<int> dp(n, 0);
08    dp[0] = nums[0];
09    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}

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

01void bfs(TreeNode* root) {
02    if (root == NULL) {
03        return;
04    }
05    queue<TreeNode*> q;
06    q.push(root);
07    while (!q.empty()) {
08        TreeNode* current = q.front();
09        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}

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

       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，它的后序遍历为（ ）。

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

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

01int gcd(int a, int b) {
02    while (b != 0) {
03        ____________
04    }
05    return a;
06}

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

01ListNode* reverseLinkedList(ListNode* head) {
02    ListNode* prev = nullptr;
03    ListNode* current = head;
04    while (current != nullptr) {
05        ListNode* next = current->next;
06        current->next = next;
07        prev = current;
08        current = next;
09    }
10    return prev;
11}

哈夫曼树是一种二叉树。

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

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

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

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

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

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

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

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

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