GESP 六级 · 2025 真题

下列关于类的说法，错误的是（）。

假设变量 veh 是 Car 的一个实例，我们可以调用 veh.move()，是因为面向对象编程有（ ）性质。

01class Vehicle {
02private:
03    string brand;
04
05public:
06    Vehicle(string b) : brand(b) {}
07
08    void setBrand(const string& b) { brand = b; }
09    string getBrand() const { return brand; }
10
11    void move() const {
12        cout << brand << " is moving..." << endl;
13    }
14};
15
16class Car : public Vehicle {
17private:
18    int seatCount;
19
20public:
21    Car(string b, int seats) : Vehicle(b), seatCount(seats) {}
22
23    void showInfo() const {
24        cout << "This car is a " << getBrand()
25             << " with " << seatCount << " seats." << endl;
26    }
27};

下面代码中 v1 和 v2 调用了相同接口 move()，但输出结果不同，这体现了面向对象编程的（ ）特性。

01class Vehicle {
02private:
03    string brand;
04
05public:
06    Vehicle(string b) : brand(b) {}
07
08    void setBrand(const string& b) { brand = b; }
09    string getBrand() const { return brand; }
10
11    virtual void move() const {
12        cout << brand << " is moving..." << endl;
13    }
14};
15
16class Car : public Vehicle {
17private:
18    int seatCount;
19
20public:
21    Car(string b, int seats) : Vehicle(b), seatCount(seats) {}
22
23    void showInfo() const {
24        cout << "This car is a " << getBrand()
25             << " with " << seatCount << " seats." << endl;
26    }
27
28    void move() const override {
29        cout << getBrand() << " car is driving on the road!" << endl;
30    }
31};
32
33class Bike : public Vehicle {
34public:
35    Bike(string b) : Vehicle(b) {}
36
37    void move() const override {
38        cout << getBrand() << " bike is cycling on the path!" << endl;
39    }
40};
41
42int main() {
43    Vehicle* v1 = new Car("Toyota", 5);
44    Vehicle* v2 = new Bike("Giant");
45
46    v1->move();
47    v2->move();
48
49    delete v1;
50    delete v2;
51    return 0;
52}

栈的操作特点是（）。

循环队列常用于实现数据缓冲。假设一个循环队列容量为 $5$（即最多存放 $4$ 个元素，留一个位置区分空与满），依次进行操作：入队数据 $1$、$2$、$3$，出队 $1$ 个数据，再入队数据 $4$，此时队首到队尾的元素顺序是（）。

以下函数 createTree() 构造的树是什么类型？

01struct TreeNode {
02    int val;
03    TreeNode* left;
04    TreeNode* right;
05    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
06};
07
08TreeNode* createTree() {
09    TreeNode* root = new TreeNode(1);
10    root->left = new TreeNode(2);
11    root->right = new TreeNode(3);
12    root->left->left = new TreeNode(4);
13    root->left->right = new TreeNode(5);
14    return root;
15}

已知二叉树的中序遍历是 [D, B, E, A, F, C]，先序遍历是 [A, B, D, E, C, F]。请问该二叉树的后序遍历结果是（）。

完全二叉树可以用数组连续高效存储，如果节点从 $1$ 开始编号，则对有两个孩子节点的节点 i，（）。

设有字符集 {a, b, c, d, e, f}，其出现频率分别为 {5, 9, 12, 13, 16, 45}。哈夫曼算法构造最优前缀编码，以下哪一组可能是对应的哈夫曼编码？（非叶子节点左边分支记作 $0$，右边分支记作 $1$，左右互换不影响正确性）。

下面代码生成格雷编码，则横线上应填写（）。

01vector<string> grayCode(int n) {
02    if (n == 0) return {"0"};
03    if (n == 1) return {"0", "1"};
04
05    vector<string> prev = grayCode(n - 1);
06    vector<string> result;
07    for (string s : prev) {
08        result.push_back("0" + s);
09    }
10    for (____________) { // 在此处填写代码
11        result.push_back("1" + prev[i]);
12    }
13    return result;
14}

请将下列树的深度优先遍历代码补充完整，横线处应填入（）。

01struct TreeNode {
02    int val;
03    TreeNode* left;
04    TreeNode* right;
05    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
06};
07
08void dfs(TreeNode* root) {
09    if (!root) return;
10    ____________<TreeNode*> temp; // 在此处填写代码
11    temp.push(root);
12    while (!temp.empty()) {
13        TreeNode* node = temp.top();
14        temp.pop();
15        cout << node->val << " ";
16        if (node->right) temp.push(node->right);
17        if (node->left) temp.push(node->left);
18    }
19}

令 $n$ 是树的节点数，下面代码实现了树的广度优先遍历，其时间复杂度是（）。

01void bfs(TreeNode* root) {
02    if (!root) return;
03    queue<TreeNode*> q;
04    q.push(root);
05    while (!q.empty()) {
06        TreeNode* node = q.front();
07        q.pop();
08        cout << node->val << " ";
09        if (node->left) q.push(node->left);
10        if (node->right) q.push(node->right);
11    }
12}

在二叉排序树（Binary Search Tree，BST）中查找元素 $50$，从根节点开始：若根值为 $60$，则下一步应去搜索：

删除二叉排序树中的节点时，如果节点有两个孩子，则横线处应填入（），其中 findMax 和 findMin 分别为寻找树的最大值和最小值的函数。

01struct TreeNode {
02    int val;
03    TreeNode* left;
04    TreeNode* right;
05    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
06};
07
08TreeNode* deleteNode(TreeNode* root, int key) {
09    if (!root) return nullptr;
10    if (key < root->val) {
11        root->left = deleteNode(root->left, key);
12    } else if (key > root->val) {
13        root->right = deleteNode(root->right, key);
14    } else {
15        if (!root->left) return root->right;
16        if (!root->right) return root->left;
17        TreeNode* temp = ____________; // 在此处填写代码
18        root->val = temp->val;
19        root->right = deleteNode(root->right, temp->val);
20    }
21    return root;
22}

给定 $n$ 个物品和一个最大承重为 $W$ 的背包，每个物品有一个重量 wt[i] 和价值 val[i]，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过 $W$，则横线上应填写（）。

01int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
02    vector<int> dp(W+1, 0);
03    for (int i = 0; i < n; ++i) {
04        for (int w = W; w >= wt[i]; --w) {
05            ____________ // 在此处填写代码
06        }
07    }
08    return dp[W];
09}

当基类可能被多态使用，其析构函数应该声明为虚函数。

哈夫曼编码是最优前缀码，且编码结果唯一。

一个含有 $100$ 个节点的完全二叉树，高度为 $8$。

在 C++ STL 中，栈（std::stack）的 pop 操作返回栈顶元素并移除它。

循环队列通过模运算循环使用空间。

一棵有 $n$ 个节点的二叉树一定有 $n-1$ 条边。

以下代码实现了二叉树的中序遍历。输入以下二叉树，中序遍历结果是 4 2 5 1 3 6。

01//     1
02//    / \
03//   2   3
04//  / \   \
05// 4   5   6
06
07struct TreeNode {
08    int val;
09    TreeNode* left;
10    TreeNode* right;
11    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12};
13
14void inorderIterative(TreeNode* root) {
15    stack<TreeNode*> st;
16    TreeNode* curr = root;
17    while (curr || !st.empty()) {
18        while (curr) {
19            st.push(curr);
20            curr = curr->left;
21        }
22        curr = st.top(); st.pop();
23        cout << curr->val << " ";
24        curr = curr->right;
25    }
26}

下面代码实现的二叉排序树的查找操作时间复杂度是 $O(h)$，其中 $h$ 为树高。

01TreeNode* searchBST(TreeNode* root, int val) {
02    while (root && root->val != val) {
03        root = (val < root->val) ? root->left : root->right;
04    }
05    return root;
06}

下面代码实现了动态规划版本的斐波那契数列计算，其时间复杂度是 $O(2^n)$。

01int fib_dp(int n) {
02    if (n <= 1) return n;
03    vector<int> dp(n+1);
04    dp[0] = 0;
05    dp[1] = 1;
06    for (int i = 2; i <= n; i++) {
07        dp[i] = dp[i-1] + dp[i-2];
08    }
09    return dp[n];
10}

有一排香蕉，每个香蕉有不同的甜度值。小猴子想吃香蕉，但不能吃相邻的香蕉。以下代码能找到小猴子吃到最甜的香蕉组合。

01// bananas: 香蕉的甜度
02void findSelectedBananas(vector<int>& bananas, vector<int>& dp) {
03    vector<int> selected;
04    int i = bananas.size() - 1;
05
06    while (i >= 0) {
07        if (i == 0) {
08            selected.push_back(0);
09            break;
10        }
11
12        if (dp[i] == dp[i-1]) {
13            i--;
14        } else {
15            selected.push_back(i);
16            i -= 2;
17        }
18    }
19
20    reverse(selected.begin(), selected.end());
21    cout << "小猴子吃了第：";
22    for (int idx : selected)
23        cout << idx+1 << " ";
24    cout << "个香蕉" << endl;
25}
26
27int main() {
28    vector<int> bananas = {1, 2, 3, 1}; // 每个香蕉的甜度
29
30    vector<int> dp(bananas.size());
31    dp[0] = bananas[0];
32    dp[1] = max(bananas[0], bananas[1]);
33    for (int i = 2; i < bananas.size(); i++) {
34        dp[i] = max(bananas[i] + dp[i-2], dp[i-1]);
35    }
36    findSelectedBananas(bananas, dp);
37    return 0;
38}