C++ 六级

2025 年 03 月

1 单选题（每题 2 分，共 30 分）

第 1 题 在面向对象编程中，类是一种重要的概念。下面关于类的描述中，不正确的是（ ）。

A. 类是一个抽象的概念，用于描述具有相同属性和行为的对象集合。 B. 类可以包含属性和方法，属性用于描述对象的状态，方法用于描述对象的行为。 C. 类可以被实例化，生成具体的对象。 D. 类一旦定义后，其属性和方法不能被修改或扩展。

第 2 题 哈夫曼编码是一种数据压缩算法。以下关于哈夫曼编码的描述中，不正确的是（ ）。

A. 哈夫曼编码是一种变长编码，频率高的字符使用较短的编码，频率低的字符使用较长的编码。 B. 在构造哈夫曼树时，频率越低的字符离根节点越近，频率越高的字符离根节点越远。 C. 哈夫曼编码的生成过程基于贪心算法，每次选择频率最低的两个节点进行合并。 D. 哈夫曼编码是一种前缀编码，任何一个字符的编码都不会是另一个字符编码的前缀，因此可以实现唯一解码。

第 3 题 以下代码实现了树的哪种遍历方式？

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

A. 前序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历

第 4 题 以下关于完全二叉树的代码描述，正确的是（ ）。

bool isCompleteTree(TreeNode *root)
{
    if (root == nullptr)
        return true;
    queue<TreeNode *> q;
    q.push(root);
    bool hasNull = false;
    while (!q.empty())
    {
        TreeNode *node = q.front();
        q.pop();
        if (node == nullptr)
        {
            hasNull = true;
        }
        else
        {
            if (hasNull)
                return false;
            q.push(node->left);
            q.push(node->right);
        }
    }
    return true;
}

A. 该代码用于判断一棵树是否为满二叉树 B. 该代码用于判断一棵树是否为完全二叉树 C. 该代码用于判断一棵树是否为二叉搜索树 D. 该代码用于计算树的高度

第 5 题 以下代码实现了二叉排序树的哪种操作？

TreeNode *op(TreeNode *root, int val)
{
    if (root == nullptr)
        return new TreeNode(val);
    if (val < root->val)
    {
        root->left = op(root->left, val);
    }
    else
    {
        root->right = op(root->right, val);
    }
    return root;
}

A. 查找 B. 插入 C. 删除 D. 遍历

第 6 题 给定字符集 {A, B, C, D} 的出现频率分别为 {5, 1, 6, 2} ，则正确的哈夫曼编码是（ ）。

A. A: 0, B: 100, C: 11, D: 101 B. A: 11, B: 100, C: 0, D: 101 C. A: 0, B: 101, C: 11, D: 100 D. A: 10, B: 101, C: 0, D: 100

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

A. 动态规划算法的时间复杂度总是低于贪心算法。 B. 动态规划要求问题必须具有最优子结构和重叠子问题两个性质。 C. 动态规划通过递归实现时不需要存储中间结果。 D. 动态规划的核心思想是将问题分解为互不重叠的子问题。

第 8 题 以下代码中，类的构造函数被调用了（ ）次。

class MyClass
{
public:
    MyClass()
    {
        cout << "Constructor called!" << endl;
    }
};
int main()
{
    MyClass obj1;
    MyClass obj2 = obj1;
    return 0;
}

A. 1 B. 2 C. 3 D. 0

第 9 题 以下代码实现了循环队列的哪种操作？

class CircularQueue
{
    int *arr;
    int front, rear, size;

public:
    CircularQueue(int k)
    {
        size = k;
        arr = new int[k];
        front = rear = -1;
    }
    bool enQueue(int value)
    {
        if (isFull())
            return false;
        if (isEmpty())
            front = 0;
        rear = (rear + 1) % size;
        arr[rear] = value;
        return true;
    }
};

A. 入队 B. 出队 C. 查看队首元素 D. 判断队列是否为空

第 10 题 以下代码实现了二叉树的深度优先搜索（DFS），并统计叶子结点的数量，则横线上应填写（ ）。

int countLeafNodes(TreeNode *root)
{
    if (root == nullptr)
        return 0;
    stack<TreeNode *> s;
    s.push(root);
    int count = 0;
    while (!s.empty())
    {
        TreeNode *node = s.top();
        s.pop();
        if (node->left == nullptr && node->right == nullptr)
        {
            count++;
        }
        if (node->right)
            s.push(node->right);
        ———————————————————————— // 在此处填入代码
    }
    return count;
}

A. if (node->left) s.push(node->left); B. if (node->left) s.pop(node->left); C. if (node->left) s.front(node->left); D. if (node->left) s.push(node->right);

第 11 题 以下代码实现了二叉树的广度优先搜索（BFS），并查找特定值的节点，则横线上应填写（ ）。

TreeNode *findNode(TreeNode *root, int target)
{
    if (root == nullptr)
        return nullptr;
    queue<TreeNode *> q;
    q.push(root);
    while (!q.empty())
    {
        TreeNode *current = q.front();
        q.pop();
        if (current->val == target)
        {
            return current; // 找到目标节点
        }
        ———————————————————————— // 在此处填入代码
    }
    return nullptr; // 未找到目标节点
}

// A:
if (current->left)
    q.push(current->left);
if (current->right)
    q.push(current->right);

// B:
if (current->left)
    q.pop(current->left);
if (current->right)
    q.pop(current->right);

// C:
if (current->left)
    q.front(current->left);
if (current->right)
    q.front(current->right);

// D:
if (current->left)
    q.push(current->right);
if (current->right)
    q.push(current->left);

A. A B. B C. C D. D

第 12 题 以下代码用于生成 位格雷编码。横线上应填写（ ）。

vector<string> generateGrayCode(int n)
{
    if (n == 0)
        return {"0"};
    if (n == 1)
        return {"0", "1"};
    vector<string> prev = generateGrayCode(n - 1);
    vector<string> result;
    for (string s : prev)
    {
        result.push_back("0" + s); // 在前缀添加 0
    }
    for (int i = prev.size() - 1; i >= 0; i--)
    {
        ———————————— // 在此处填入代码
    }
    return result;
}

A. result.push_back("1" + prev[i]); B. result.push_back("0" + prev[i]); C. result.push_back(prev[i] + "1"); D. result.push_back(prev[i] + "0");

第 13 题 以下代码实现了0/1背包问题的动态规划解法。假设物品重量为 weights[] ，价值为 values[] ，背包容量为 W ，横线上应填写（ ）。

int knapsack(int W, vector<int> &weights, vector<int> &values)
{
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            if (weights[i - 1] > j)
            {
                dp[i][j] = dp[i - 1][j]; // 当前物品装不下
            }
            else
            {
                dp[i][j] = max(_________________________); // 在此处填入代码
            }
        }
    }
    return dp[n][W];
}

A. dp[i-1][j], values[i-1] B. dp[i-1][j], dp[i-1][j - weights[i-1]] + values[i-1] C. dp[i][j-1], values[i-1] D. dp[i-1][j - weights[i-1]] + values[i-1], dp[i][j-1]

第 14 题 以下代码用于检查字符串中的括号是否匹配，横线上应填写（ ）。

bool isBalanced(string s)
{
    stack<char> st;
    for (char c : s)
    {
        if (c == '(' || c == '[' || c == '{')
        {
            st.push(c);
        }
        else
        {
            if (st.empty())
                return false; // 无左括号匹配
            char top = st.top();
            st.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{'))
            {
                return false;
            }
        }
    }
    return ________________; // 在此处填入代码
}

A. true B. false C. st.empty() D. !st.empty()

第 15 题 关于下面代码，说法错误的是（ ）。

class Shape
{
protected:
    string name;

public:
    Shape(const string &n) : name(n) {}
    virtual double area() const
    {
        return 0.0;
    }
};

class Circle : public Shape
{
private:
    double radius; // 半径
public:
    Circle(const string &n, double r) : Shape(n), radius(r) {}
    double area() const override
    {
        return 3.14159 * radius * radius;
    }
};

class Rectangle : public Shape
{
private:
    double width;  // 宽度
    double height; // 高度

public:
    Rectangle(const string &n, double w, double h) : Shape(n), width(w), height(h)
    {
    }
    double area() const override
    {
        return width * height;
    }
};

int main()
{
    Circle circle("MyCircle", 5.0);
    Rectangle rectangle("MyRectangle", 4.0, 6.0);
    Shape *shapePtr = &circle;
    cout << "Area: " << shapePtr->area() << endl;
    shapePtr = &rectangle;
    cout << "Area: " << shapePtr->area() << endl;
    return 0;
}

A. 语句 Shape* shapePtr = &circle; 和 shapePtr = &rectangle; 出现编译错误 B. Shape 为基类， Circle 和 Rectangle 是派生类 C. 通过继承， Circle 和 Rectangle 复用了 Shape 的属性和方法，并扩展了新的功能 D. Circle 和 Rectangle 通过重写（override）基类的虚函数 area 和基类指针，实现了运行时多态

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

第 1 题 哈夫曼树在构造过程中，每次合并权值最小的两个节点，最终生成的树带权路径长度最小。

A. 对 B. 错

第 2 题 格雷编码的相邻两个编码之间必须有多位不同，以避免数据传输错误。

A. 对 B. 错

第 3 题 在树的深度优先搜索（DFS）中，使用队列作为辅助数据结构以实现“先进后出”的访问顺序。

A. 对 B. 错

第 4 题 以下代码实现的是二叉树的中序遍历：

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

A. 对 B. 错

第 5 题 C++ 支持构造函数重载，但默认无参数的构造函数只能有一个。

A. 对 B. 错

第 6 题 二叉排序树（BST）中，若某节点的左子树为空，则该节点一定是树中的最小值节点。

A. 对 B. 错

第 7 题 在动态规划解决一维硬币找零问题时，若硬币面额为 [1, 3, 4] ，目标金额为 6 ，则最少需要 2 枚硬币（3+3）。

A. 对 B. 错

第 8 题 面向对象编程中，封装是指将数据和行为绑定在一起，并对外隐藏实现细节。

A. 对 B. 错

第 9 题 以下代码创建的树是一棵完全二叉树：

TreeNode* root = new TreeNode{1};
root->left = new TreeNode{2};
root->right = new TreeNode{3};
root->left->left = new TreeNode{4};

A. 对 B. 错

第 10 题 栈和队列均可以用双向链表实现，插入和删除操作的时间复杂度为 O(1) 。

A. 对 B. 错