GESP 六级 · 2024 真题

以下（ ）没有涉及C++语言的面向对象特性支持。

关于以下C++代码，（ ）行代码会引起编译错误。

01#include <iostream>
02using namespace std;
03
04class Base {
05private:
06    int a;
07protected:
08    int b;
09public:
10    int c;
11    Base() : a(1), b(2), c(3) {}
12};
13
14class Derived : public Base {
15public:
16    void show() {
17        cout << a << endl;    // Line 1
18        cout << b << endl;    // Line 2
19        cout << c << endl;    // Line 3
20    }
21};

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

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

01#include <iostream>
02#include <stack>
03#include <string>
04
05using namespace std;
06
07bool is_valid(string s) {
08    stack<char> st;
09    char top;
10
11    for (char& ch : s) {
12        if (ch == '(' || ch == '{' || ch == '[') {
13            st.push(ch);    // 左括号入栈
14        }
15        else
16        {
17            if (st.empty())
18                return false;
19            ____________ // 在此处填入代码
20            if ((ch == ')' && top != '(') ||
21                (ch == '}' && top != '{') ||
22                (ch == ']' && top != '[')) {
23                return false;
24            }
25        }
26    }
27
28    return st.empty();      // 栈为空则说明所有括号匹配成功
29}

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

01#include <iostream>
02#include <queue>
03using namespace std;
04
05bool is_front_equal(std::queue<int>& q, int a) {
06    bool is_equal = false;
07    if (!q.empty()) {
08        ____________ // 在此处填入代码
09    }
10    return is_equal;
11}

假设字母表{a,b,c,d,e}在字符串出现的频率分别为10%，15%，30%，16%，29%。若使用哈夫曼编码方式对字母进行二进制编码，则字符abcde分别对应的一组哈夫曼编码的长度分别为（ ）。

编者注：官方原题此处写作abcdef，但题目只给出了字母a至e及其五项频率；本题按题意修正为abcde。

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

01#include <iostream>
02#include <vector>
03#include <string>
04using namespace std;
05// 生成 n 位的格雷码
06vector<string> generate_graycode(int n) {
07    vector<string> graycode_list;
08    if (n <= 0) {
09        return graycode_list;
10    }
11
12    // 初始1位格雷码
13    graycode_list.push_back("0");
14    graycode_list.push_back("1");
15
16    // 迭代生成 n 位的格雷码
17    for (int i = 2; i <= n; i++) {
18        int current_size = graycode_list.size();
19
20        for (int j = current_size - 1; j >= 0; j--) {
21            graycode_list.push_back("1" + graycode_list[j]);
22        }
23
24        for (int j = 0; j < current_size; j++) {
25            ____________ // 在此处填入代码
26        }
27    }
28
29    return graycode_list;
30}

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

一棵有 $n$ 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第$1$个位置。若存储在数组第$9$个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ ）。

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

01// 定义二叉树的结点结构
02struct tree_node {
03    int val;
04    tree_node* left;
05    tree_node* right;
06
07    tree_node(int x) : val(x), left(nullptr), right(nullptr) {}
08};
09
10// 计算二叉树的深度
11int max_depth(tree_node* root) {
12    if (root == nullptr) {
13        return 0;  // 如果根结点为空，则深度为 0
14    }
15
16    int left_depth = max_depth(root->left);
17    int right_depth = max_depth(root->right);
18
19    ____________ // 在此处填入代码
20}

二叉树的深度计算可以采用广度优先搜索来实现，以下基于 BFS 的深度计算函数中横线上应填写（ ）。

01#include <queue>
02
03int max_depth_bfs(tree_node* root) {
04    if (root == nullptr) {
05        return 0; // 如果树为空，深度为 0
06    }
07
08    queue <tree_node*> q;
09    q.push(root);
10    int depth = 0;
11
12    // 使用队列进行层序遍历
13    while (!q.empty()) {
14        ____________ // 在此处填入代码
15        for (int i = 0; i < level_size; ++i) {
16            tree_node* node = q.front();
17            q.pop();
18
19            if (node->left) {
20                q.push(node->left);
21            }
22            if (node->right) {
23                q.push(node->right);
24            }
25        }
26    }
27
28    return depth;
29}

二叉搜索树中的每个结点，其左子树的所有结点值都小于该结点值，右子树的所有结点值都大于该结点值。以下代码对给定的整数数组(假设数组中没有数值相等的元素)，构造一个对应的二叉搜索树，横线上应填写（ ）：

01// 定义二叉树的结点结构
02struct tree_node {
03    int val;
04    tree_node* left;
05    tree_node* right;
06
07    tree_node(int x) : val(x), left(nullptr), right(nullptr) {}
08};
09
10// 插入结点到二叉搜索树中
11tree_node* insert(tree_node* root, int val) {
12    if (root == nullptr) {
13        return new tree_node(val);
14    }
15
16    ____________ // 在此处填入代码
17
18    return root;
19}
20
21// 根据给定数组构造二叉搜索树
22tree_node* constructBST(const int arr[], int size) {
23    tree_node* root = nullptr;
24
25    for (int i = 0; i < size; ++i) {
26        root = insert(root, arr[i]);
27    }
28    return root;
29}

当输入数组为[5,3,7,2,4,6,8]时，按二叉搜索树的插入规则依次构建二叉树，并采用如下代码实现的遍历方式，得到的输出是（ ）。

01#include <iostream>
02using namespace std;
03
04// 遍历二叉搜索树，输出结点值
05void traversal(tree_node* root) {
06    if (root == nullptr) {
07        return;
08    }
09
10    traversal(root->left);
11    cout << root->val << " ";
12    traversal(root->right);
13}

动态规划通常用于解决（ ）。

阅读以下用动态规划解决的$0$-$1$背包问题的函数，假设背包的容量 $W$ 是$10\text{kg}$，假设输入$4$个物品的重量weights分别为1,3,4,6（单位为 kg），每个物品对应的价值values分别为20,30,50,60，则函数的输出为（ ）。

01#include <iostream>
02#include <vector>
03using namespace std;
04
05// 0/1背包问题
06int knapsack(int W, const vector<int>& weights, const vector<int>& values, int n) {
07    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
08
09    for (int i = 1; i <= n; ++i) {
10        for (int w = 0; w <= W; ++w) {
11            if (weights[i - 1] <= w) {
12                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
13            }
14            else
15            {
16                dp[i][w] = dp[i - 1][w];
17            }
18        }
19    }
20
21    return dp[n][W];
22}

C++、Python和JAVA等都是面向对象的编程语言。

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

栈是一种线性结构，可通过数组或链表来实现。二者相比，数组实现占用的内存较少，链表实现的入队和出队操作的时间复杂度较低。

运行以下C++代码，屏幕将输出derived class。

01#include <iostream>
02using namespace std;
03
04class base {
05public:
06    virtual void show() {
07        cout << "base class" << endl;
08    }
09};
10
11class derived : public base {
12public:
13    void show() override {
14        cout << "derived class" << endl;
15    }
16};
17
18int main() {
19    base* b;
20    derived d;
21    b = &d;
22    b->show();
23    return 0;
24}

如下列代码所示的基类（base）及其派生类（derived），则生成一个派生类的对象时，只调用派生类的构造函数。

01#include <iostream>
02using namespace std;
03
04class base {
05public:
06    base() {
07        cout << "base constructor" << endl;
08    }
09    ~base() {
10        cout << "base destructor" << endl;
11    }
12};
13
14class derived : public base {
15public:
16    derived() {
17        cout << "derived constructor" << endl;
18    }
19    ~derived() {
20        cout << "derived destructor" << endl;
21    }
22};

哈夫曼编码本质上是一种贪心策略。

如果根结点的深度记为$1$，则一棵恰有$2024$个叶结点的二叉树的深度最少是$12$。

在非递归实现的树的广度优先搜索中，通常使用栈来辅助实现。

状态转移方程是动态规划的核心，可以通过递推方式表示问题状态的变化。

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