[GESP202403] 六级客观题

一、单选题（每题 2 分，共 30 分）

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. 已知字符 0 的ASCII编码的十进制表示为48，则执行下面C++代码后，输出是（ ）

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;

二、判断题（每题 2 分，共 20 分）

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. 错误