C++　六级 2024 年 09 ⽉

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

第 1 题 以下（ ）没有涉及 C++ 语⾔的⾯向对象特性⽀持。

{{ select(1) }}

• C++ 中构造⼀个 class 或 struct
• C++ 中调⽤ printf 函数
• C++ 中调⽤⽤户定义的类成员函数
• C++ 中构造来源于同⼀基类的多个派⽣类

第 2 题 关于以下C++代码，（ ）⾏代码会引起编译错误。

#include <iostream>
using namespace std;
class Base {
private:
    int a;
protected:
    int b;
public:
    int c;
    Base() : a(1), b(2), c(3) {}
};
class Derived : public Base {
public:
    void show() {
        cout << a << endl;   // Line 1
        cout << b << endl;   // Line 2
        cout << c << endl;   // Line 3
    }
};

{{ select(2) }}

• Line 1
• Line 2
• Line 3
• 没有编译错误

第 3 题 有6个元素，按照 6,5,4,3,2,1 的顺序进⼊栈S，下列（ ）的出栈序列是不能出现的（ ）。

{{ select(3) }}

• 5,4,3,6,1,2
• 4,5,3,1,2,6
• 3,4,6,5,2,1
• 2,3,4,1,5,6

第 4 题 采⽤如下代码实现检查输⼊的字符串括号是否匹配，横线上应填⼊的代码为（ ）。

#include <iostream>
#include <stack>
#include <string>
using namespace std;
bool is_valid(string s) {
    stack<char> st;
    char top;
    for (char& ch : s) {
        if (ch == '(' || ch == '{' || ch == '[') {
            st.push(ch);    // 左括号入栈
        }
        else
        {
            if (st.empty())
                return false;
            ———————————————————————— // 在此处填入代码
            if ((ch == ')' && top != '(') ||
                (ch == '}' && top != '{') ||
                (ch == ']' && top != '[')) {
                return false;
            }
        }
    }
    return st.empty();      // 栈为空则说明所有括号匹配成功
}

{{ select(4) }}

• top = st.top(); st.pop();
• st.pop(); top = st.top();
• st.pop(); top = st.front();
• top = st.front(); st.pop();

第 5 题 下⾯代码判断队列的第⼀个元素是否等于 ，并删除该元素，横向上应填写（ ）。

#include <iostream>
#include <queue>
using namespace std;
bool is_front_equal(std::queue<int>& q, int a) {
    bool is_equal = false;
    if (!q.empty()) {
        ———————————————————————— // 在此处填入代码
    }
    return is_equal;
}

{{ select(5) }}

• is_equal = (q.front() == a);
• is_equal = (q.front() == a); q.pop();
• q.pop(); is_equal = (q.front() == a);
• q.pop(); is_equal = (q.top() == a);

第 6 题 假设字母表 {a,b,c,d,e} 在字符串出现的频率分别为 10%，15%，30%，16%，29%。若使⽤哈夫曼编码⽅式对字母进⾏⼆进制编码，则字符 abcdef 分别对应的⼀组哈夫曼编码的长度分别为（ ）。

{{ select(6) }}

• 4, 4, 1, 3, 2
• 3, 3, 2, 2, 2
• 3, 3, 1, 2, 1
• 4, 4, 1, 2, 2

第 7 题 以下C++代码实现 位的格雷码，则横线上应填写（ ）。

#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 生成 n 位的格雷码
vector<string> generate_graycode(int n) {
    vector<string> graycode_list;
    if (n <= 0) {
        return graycode_list;
    }
    // 初始1位格雷码
    graycode_list.push_back("0");
    graycode_list.push_back("1");
    // 迭代生成 n 位的格雷码
    for (int i = 2; i <= n; i++) {
        int current_size = graycode_list.size();

        for (int j = current_size - 1; j >= 0; j--) {
            graycode_list.push_back("1" + graycode_list[j]);
        }
        for (int j = 0; j < current_size; j++) {
            ———————————————————————— // 在此处填入代码
        }
    }

    return graycode_list;
}

{{ select(7) }}

• graycode_list.push_back("0" + graycode_list[j]);
• graycode_list[j] = "0" + graycode_list[j];
• graycode_list.push_back("1" + graycode_list[j]);
• graycode_list[j] = "1" + graycode_list[j];

第 8 题 给定⼀棵⼆叉树，其前序遍历结果为：ABDECFG,中序遍历结果为：DEBACFG，则这棵树的正确后序遍历结果是（ ）。

{{ select(8) }}

• EDBGFCA
• EDGBFCA
• DEBGFCA
• DBEGFCA

第 9 题 ⼀棵有 个结点的完全⼆叉树⽤数组进⾏存储与表⽰，已知根结点存储在数组的第 个位置。若存储在数组第个位置的结点存在兄弟结点和两个⼦结点，则它的兄弟结点和右⼦结点的位置分别是（ ）。

{{ select(9) }}

• 8, 18
• 10, 18
• 8, 19
• 10, 19

第 10 题 ⼆叉树的深度定义为从根结点到叶结点的最长路径上的结点数，则以下基于⼆叉树的深度优先搜索实现的深度计算函数中横线上应填写（ ）。

// 定义二叉树的结点结构
struct tree_node {
    int val;
    tree_node* left;
    tree_node* right;
    tree_node(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 计算二叉树的深度
int max_depth(tree_node* root) {
    if (root == nullptr) {
        return 0;  // 如果根结点为空，则深度为 0
    }

    int left_depth = max_depth(root->left);
    int right_depth = max_depth(root->right);
    ———————————————————————— // 在此处填入代码
}

{{ select(10) }}

• return left_depth + right_depth;
• return max(left_depth, right_depth);
• return max(left_depth, right_depth) + 1;
• return left_depth + right_depth + 1;

第 11 题 上⼀题的⼆叉树深度计算还可以采⽤⼆叉树的⼴度优先搜索来实现。以下基于⼆叉树的⼴度优先搜索实现的深度计算函数中横线上应填写（ ）。

#include <queue>
int max_depth_bfs(tree_node* root) {
    if (root == nullptr) {
        return 0; // 如果树为空，深度为 0
    }

    queue <tree_node*> q;
    q.push(root);
    int depth = 0;

    // 使用队列进行层序遍历
    while (!q.empty()) {
        ———————————————————————— // 在此处填入代码
        for (int i = 0; i < level_size; ++i) {
            tree_node* node = q.front();
            q.pop();
            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
    }

    return depth;
}

{{ select(11) }}

• int level_size = q.size(); depth++;
• int level_size = 2; depth++;
• int level_size = q.size(); depth += level_size;
• int level_size = 2; depth += level_size;

第 12 题 ⼆叉搜索树中的每个结点，其左⼦树的所有结点值都⼩于该结点值，右⼦树的所有结点值都⼤于该结点值。以下代码对给定的整数数组(假设数组中没有数值相等的元素)，构造⼀个对应的⼆叉搜索树，横线上应填写（ ）:

// 定义二叉树的结点结构
struct tree_node {
    int val;
    tree_node* left;
    tree_node* right;
    tree_node(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 插入结点到二叉搜索树中
tree_node* insert(tree_node* root, int val) {
    if (root == nullptr) {
        return new tree_node(val);
    }
    ———————————————————————— // 在此处填入代码
    return root;
}
// 根据给定数组构造二叉搜索树
tree_node* constructBST(const int arr[], int size) {
    tree_node* root = nullptr;
    for (int i = 0; i < size; ++i) {
        root = insert(root, arr[i]);
    }
    return root;
}

//A
if (val < root->val)
  root->left = insert(root->left, val);
else
  root->right = insert(root->right, val);

//B
if (val > root->val)
  root->left = insert(root->left, val);
else
  root->right = insert(root->right, val);

//C
if (val < root->val)
  root->left = insert(root, val);
else
  root->right = insert(root, val);

//D
if (val > root->val)
  root->left = insert(root, val);
else
  root->right = insert(root, val);

{{ select(12) }}

• A
• B
• C
• D

第 13 题 对上题中的⼆叉搜素树，当输⼊数组为 时，构建⼆叉搜索树，并采⽤如下代码实现的遍历⽅式，得到的输出是（ ）。

#include <iostream>
using namespace std;
// 遍历二叉搜索树，输出结点值
void traversal(tree_node* root) {
    if (root == nullptr) {
        return;
    }
    traversal(root->left);
    cout << root->val << " ";
    traversal(root->right);
}

{{ select(13) }}

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

第 14 题 动态规划通常⽤于解决（ ）。

{{ select(14) }}

• ⽆法分解的问题
• 可以分解成相互依赖的⼦问题的问题
• 可以通过贪⼼算法解决的问题
• 只能通过递归解决的问题

第 15 题 阅读以下⽤动态规划解决的0-1背包问题的函数，假设背包的容量 是10kg，假设输⼊4个物品的重量分别为 （单位为kg），每个物品对应的价值 分别为 ，则函数的输出为（ ）。

#include <iostream>
#include <vector>
using namespace std;
// 0/1背包问题
int knapsack(int W, const vector<int>& weights, const vector<int>& values, int n) {
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int w = 0; w <= W; ++w) {
            if (weights[i - 1] <= w) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + 
values[i - 1]);
            }
            else
            {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][W];
}

{{ select(15) }}

• 90
• 100
• 110
• 140

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

第 1 题 C++、Python和JAVA等都是⾯向对象的编程语⾔。

{{ select(16) }}

• 对

• 错

  第 2 题 在C++中，类的静态成员变量只能被该类对象的成员函数访问。

{{ select(17) }}

• 对

• 错

  第 3 题 栈是⼀种线性结构，可通过数组或链表来实现。⼆者相⽐，数组实现占⽤的内存较少，链表实现的⼊队和出队操作的时间复杂度较低。

{{ select(18) }}

• 对

• 错

  第 4 题 运⾏以下C++代码，屏幕将输出“derived class”。

#include <iostream>
using namespace std;
class base {
public:
    virtual void show() {
        cout << "base class" << endl;
    }
};
class derived : public base {
public:
    void show() override {
        cout << "derived class" << endl;
    }
};
int main() {
    base* b;
    derived d;
    b = &d;
    b->show();
    return 0;
}

{{ select(19) }}

• 对
• 错

第 5 题 如下列代码所⽰的基类（base）及其派⽣类（derived），则⽣成⼀个派⽣类的对象时，只调⽤派⽣类的构造函数。

#include <iostream>
using namespace std;

class base {
public:
    base() {
        cout << "base constructor" << endl;
    }
    ~base() {
        cout << "base destructor" << endl;
    }
};

class derived : public base {
 public:
    derived() {
        cout << "derived constructor" << endl;
    }
    ~derived() {
        cout << "derived destructor" << endl;
    }
};

{{ select(20) }}

• 对
• 错

第 6 题 哈夫曼编码本质上是⼀种贪⼼策略。

{{ select(21) }}

• 对
• 错

第 7 题 如果根结点的深度记为 1，则⼀棵恰有 2024 个叶结点的⼆叉树的深度最少是 。

{{ select(22) }}

• 对
• 错

第 8 题 在⾮递归实现的树的⼴度优先搜索中，通常使⽤栈来辅助实现。

{{ select(23) }}

• 对
• 错

第 9 题 状态转移⽅程是动态规划的核⼼，可以通过递推⽅式表⽰问题状态的变化。

{{ select(24) }}

• 对
• 错

第 10 题 应⽤动态规划算法时，识别并存储重叠⼦问题的解是必须的。

{{ select(25) }}

• 对
• 错