CCF GESP C++ 六级 (2024 年 03 月)

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

第 1 题 在构建哈夫曼树时，每次应该选择 ( ) 合并｡

{{ select(1) }}

• 最小权值的节点
• 最大权值的节点
• 随机节点
• 深度最深的节点

第 2 题面向对象的编程思想主要包括以下哪些原则 ( )?

{{ select(2) }}

• 贪心､动态规划､回溯
• 并发､并行､异步
• 递归､循环､分治
• 封装､继承､多态

第 3 题在队列中，元素的添加和删除是按照 ( ) 原则进行的｡

{{ select(3) }}

• 先进先出
• 先进后出
• 最小值先出
• 随机进出

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

class Circle {
private:
    double radius;
public:
    Circle(double r) : radius(r) {}
    double getArea() {
        return 3.14 * radius * radius;
    }
};

{{ select(4) }}

• Circle c = Circle(5.0); c.getArea(c);
• Circle c(5.0); getArea(c);
• Circle c = new Circle(5.0); c.getArea();
• 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);  
    }  
}  

{{ select(5) }}

• target < root->left
• target < root->val
• target > root->val
• target > root->left

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

{{ select(6) }}

• 000, 001, 010, 011, 100, 101, 110, 111
• 000, 001, 011, 010, 110, 111, 101, 100
• 000, 010, 001, 011, 100, 110, 101, 111
• 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];  
}  

{{ select(7) }}

• 计算数组 nums 中的所有元素的和
• 计算数组 nums 中相邻元素的最大和
• 计算数组 nums 中不相邻元素的最大和
• 计算数组 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);  
    }  
}  

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

{{ select(8) }}

• 1 2 8 9 4 5 3 6 7 10 11
• 1 2 3 4 5 6 7 8 9 10 11
• 1 2 3 8 9 6 4 5 7 10 11
• 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()

{{ select(9) }}

• 1, 2
• 1, 4, 5
• 1, 2, 5
• 1, 4

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

{{ select(10) }}

• 247
• 248
• 249
• 250

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

{{ select(11) }}

• 重叠子问题
• 分治法
• 贪心策略
• 回溯算法

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

{{ select(12) }}

• D, E, B, F, C, A
• E, D, B, F, C, A
• D, E, B, C, F, A
• E, D, B, C, F, A

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

{{ select(13) }}

• 更容易实现
• 更节省内存
• 更快速
• 更准确

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

int gcd(int a, int b) {  
    while (b != 0) {  
        ______________________  
    }  
    return a;  
}  

{{ select(14) }}

• int temp = b; b = a / b; a = temp;
• int temp = a; a = b / a; b = temp;
• int temp = b; b = a % b; a = temp;
• 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;  
}  

{{ select(15) }}

• current->next = next; 应该改为 current->next = prev;
• ListNode* next = current->next; 应该改为 ListNode* next = prev->next;
• current != nullptr 应该改为 current->next != nullptr
• ListNode* prev = nullptr; 应该改为 ListNode* prev = head;

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

第1 题：哈夫曼树是一种二叉树｡

{{ select(16) }}

• 对
• 错

第2 题：在动态规划中，状态转移方程的作用是定义状态之间的关系｡

{{ select(17) }}

• 对
• 错

第3 题：继承是将已有类的属性和方法引入新类的过程｡

{{ select(18) }}

• 对
• 错

第4 题：完全二叉树的任意一层都可以不满｡

{{ select(19) }}

• 对
• 错

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

{{ select(20) }}

• 对
• 错

第6 题：在宽度优先搜索中，通常使用队列来辅助实现｡

{{ select(21) }}

• 对
• 错

第7 题：哈夫曼编码的主要应用领域是有损数据压缩｡

{{ select(22) }}

• 对
• 错

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

{{ select(23) }}

• 对
• 错

。

第9 题：栈的基本操作包括入栈 (push) 和出栈 (pop)｡

{{ select(24) }}

• 对
• 错

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

{{ select(25) }}

• 对
• 错