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

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

第 1 题面向对象编程 (OOP) 是一种特殊的程序设计方法｡下面 ( ) 不是重要的 OOP 特性｡

{{ select(1) }}

• 抽象
• 封装
• 继承
• 模块化

第 2 题 以下关于 C++ 中类的说法，哪一项是正确的？

{{ select(2) }}

• 类中定义的所有成员变量和成员函数默认是 public 访问权限｡
• 类的构造函数必须显式声明返回类型为 void｡
• 在 C++ 中，类的数据一般设置为私有，其公有成员函数提供访问私有数据的唯一途径｡
• 同一个类的实例有各自的成员数据和成员函数｡

第 3 题以下 C++ 代码段中存在语法错误或逻辑错误，( ) 是正确的｡

#include <iostream>  
using namespace std;  
class MyClass {  
public:  
    MyClass() { cout << "Constructor called!" << endl; }  
    void display() { cout << "Display function called!" << endl; }  
};  
int main() {  
    MyClass* obj = NULL;  
    obj->display();  
    return 0;  
}  

{{ select(3) }}

• NULL 在 C++ 中无法用于指针初始化，应使用 nullptr｡
• obj 的定义应该是 MyClass obj; 而不是指针类型｡
• obj->display () 语句存在空指针访问错误，obj 应该初始化为一个有效的对象｡
• obj->display () 语句会调用 display () 函数，但它没有输出任何内容｡

第 4 题阅读以下代码，下面哪一项是正确的？

void processData() {  
    stack<int> s;  
    queue<int> q;  
    for (int i = 1; i <= 5; ++i) {  
        s.push(i);  
        q.push(i);  
    }  
    while (!s.empty()) {  
        cout << "Stack pop: " << s.top() << endl;  
        s.pop();  
    }  
    while (!q.empty()) {  
        cout << "Queue pop: " << q.front() << endl;  
        q.pop();  
    }  
}  

{{ select(4) }}

• 栈 s 的输出顺序是 1 2 3 4 5 ，队列 q 的输出顺序是 5 4 3 2 1 。
• 栈 s 的输出顺序是 5 4 3 2 1 ，队列 q 的输出顺序是 1 2 3 4 5 。
• 栈 s 的输出顺序是 1 2 3 4 5 ，队列 q 的输出顺序是 1 2 3 4 5 。
• 栈 s 的输出顺序是 1 2 3 4 5 ，队列 q 的输出顺序是 1 2 3 4 5 ，程序不会正常执行。

第 5 题n 个节点的双向循环链，在其中查找某个节点的平均时间复杂度是 ( )。

{{ select(5) }}

• O(1)
• O(n)
• O(log n)
• O($n^2$)

第 6 题以下关于树的说法，（ ）是正确的。

{{ select(6) }}

• 在一棵二叉树中，叶子结点的度一定是 2。
• 满二叉树中每一层的结点数等于 ($2^{\text{层数}-1}$)。
• 在一棵树中，所有结点的度之和等于所有叶子结点的度之和。
• 一棵二叉树的先序遍历结果和中序遍历结果一定相同。

第 7 题已知字符集 {A, B, C, D} 的出现频率如下表所示：字符频率A(8) B(3) C(1) D(6)根据哈夫曼编码法，下面（ ）是正确的哈夫曼树。

A.

    ABCD  
    / \  
   A  BCD  
      / \  
     D  BC  
        / \  
        B  C  

B.

   ABCD  
   / \  
  A  BCD  
     / \  
    B  CD  
      / \  
      C  D  

C.

   ABCD  
   / \  
  D  ABC  
     / \  
    A  BC  
      / \  
      B  C  

D.

   ABCD  
   / \  
  C  ABC  
     / \  
    B  AD  
       / \  
       A  D  

{{ select(7) }}

• A
• B
• C
• D

第 8 题上一题中各字符的哈夫曼编码是（ ）。

{{ select(8) }}

• A: 0, B: 10, C: 110, D: 111
• A: 0, B: 10, C: 11, D: 10
• A: 0, B: 101, C: 100, D: 11
• A: 11, B: 10, C: 01, D: 00.

第 9 题( ) 是 3 位格雷编码。

{{ select(9) }}

• 000 001 011 010 110 111 101 100
• 000 001 010 011 100 101 110 111
• 000 001 100 101 011 010 111 110
• 000 010 001 011 100 110 101 111

第 10 题根据下面二叉树和给定的代码，调用函数 search(root,7) 时，输出的结果是（ ）。

struct TreeNode {  
    int val;  
    TreeNode* left;  
    TreeNode* right;  
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
};  
TreeNode* search(TreeNode* root, int val) {  
    cout << root->val << " ";  
    if (root == NULL || root->val == val) return root;  
    if (val < root->val)  
        return search(root->left, val);  
    else  
        return search(root->right, val);  
}  

二叉搜索树结构：

    5  
   / \  
  3   7  
 / \ / \  
2  4 6  8  

{{ select(10) }}

• 5 3 7
• 5 7
• 2 3 4 5 6 7
• 8 7

第 11 题阅读以下二叉树的深度优先搜索算法，横线上应填写（ ）。

void dfs(TreeNode* root) {  
    if (root == nullptr)  
        return;  
    stack<TreeNode*> s;  
    s.push(root);  
    while (!s.empty()) {  
        ___________________// 在此处填入代码  
        cout << node->value << " ";  
        if (node->right) s.push(node->right);  
        if (node->left) s.push(node->left);  
    }  
}  

{{ select(11) }}

• TreeNode* node = s.top();
• TreeNode* node = s.top(); s.pop();
• TreeNode* node = s.front();
• TreeNode* node = s.front(); s.pop();

第 12 题阅读以下二叉树的广度优先搜索的代码，横线上应填写（ ）。

void bfs(TreeNode* root) {  
    if (root == NULL) return;  
    queue<TreeNode*> q;  
    q.push(root);  
    while (!q.empty()) {  
        ___________________// 在此处填入代码  
        cout << node->val << " ";  
        if (node->left) q.push(node->left);  
        if (node->right) q.push(node->right);  
    }  
}  

{{ select(12) }}

• TreeNode* node = q.top();
• TreeNode* node = q.top(); q.pop();
• TreeNode* node = q.front();
• TreeNode* node = q.front(); q.pop();

第 13 题使用上题中的宽度优先搜索算法遍历以下这棵树，可能的输出是 ( )。

树结构：

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

{{ select(13) }}

• 1 2 8 9 4 5 3 6 7
• 1 2 3 4 5 6 6 8 9
• 1 2 3 8 9 6 4 5 7
• 8 4 5 9 2 1 3 6 7

第 14 题以下关于动态规划的描述，（ ）是正确的。

{{ select(14) }}

• 动态规划适用于没有重叠子问题的优化问题。
• 动态规划要求问题具有最优子结构和无后效性。
• 动态规划通常通过递归来实现。
• 动态规划与贪心算法不同，贪心算法不适用于有重叠子问题的问题。

第 15 题假设背包的最大容量 (W=8 \text{kg})，4 个物品的重量分别为 ([2,3,5,7])，对应价值分别为 ([30,40,60,80])，则该 0/1 背包问题中，背包的最大价值为（ ）。

{{ select(15) }}

• 70
• 90
• 100
• 120

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

第 1 题构造函数是一种特殊的类成员函数，构造函数的名称和类名相同。但通过函数重载，可以创建多个同名的构造函数，条件是每个构造函数的参数列表不同。

{{ select(16) }}

• 对
• 错

第 2 题类的静态成员函数既能访问类的静态数据成员，也能访问非静态数据成员。

{{ select(17) }}

• 对
• 错

第 3 题栈中元素的插入和删除操作都在栈的顶端进行，所以方便用单向链表实现。

{{ select(18) }}

• 对
• 错

第 4 题下面代码构建的树一定是完全二叉树：

struct TreeNode {  
    int value;  
    TreeNode* left;  
    TreeNode* right;  
};  
TreeNode* buildCompleteBinaryTree() {  
    TreeNode* root = new TreeNode{1};  
    root->left = new TreeNode{2};  
    root->right = new TreeNode{3};  
    root->left->left = new TreeNode{4};  
    root->left->right = new TreeNode{5};  
    root->right->left = new TreeNode{6};  
    return root;  
} 

{{ select(19) }}

• 对
• 错

第 5 题在二叉排序树中，左子树所有节点的值都大于根节点的值，右子树所有节点的值都小于根节点的值。

{{ select(20) }}

• 对
• 错

第 6 题在生成一个派生类的对象时，只调用派生类的构造函数。

{{ select(21) }}

• 对
• 错

第 7 题下面的代码实现了二叉树的前序遍历，它通过递归方法访问每个节点并打印节点值。

void preorder(TreeNode* root) {  
    if (root == NULL) return;  
    cout << root->val << " ";  
    preorder(root->left);  
    preorder(root->right);  
}  

{{ select(22) }}

• 对
• 错

第 8 题宽度优先搜索算法（BFS）保证了每个节点在最短路径的情况下被访问。

{{ select(23) }}

• 对
• 错

第 9 题在解决简单背包问题时，动态规划的状态转移方程如下：该方程表示：在考虑第 i 个物品时，当前背包容量为 w ，如果不放物品 i ，则最大价值是 dp[i-1][w]；如果放入物品 i ，则最大价值是 dp[i-1][w - weights[i-1]] + values[i-1]，其中数组 weights 和 values 分别表示所有物品的重量和价值，数组下标从 0 开始。

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);  

{{ select(24) }}

• 对
• 错

第 10 题栈中元素的插入和删除操作都在栈的顶端进行，所以用双向链表比单向链表更合适实现。

{{ select(25) }}

• 对
• 错