GESP C++ 六 级 2025年6月真题（180 分钟，总分 100 分）

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

1. 下列哪一项不是面向对象编程的基本特征？

{{ select(1) }}

• 继承
• 封装
• 多态
• 链接

2. 为了让 Dog 类的构造函数能正确地调用其父类 Animal 的构造方法，横线线处应填入（   ）。

class Animal
{
public:
    std::string name;
    Animal(std::string str) : name(str)
    {
        std::cout << "Animal created\n";
    }
    virtual void speak()
    {
        cout << "Animal speaks" << endl;
    }
};
class Dog : public Animal
{
    std::string breed;

public:
    Dog(std::string name, std::string b) : _________________, breed(b)
    {
        std::cout << "Dog created\n";
    }
    void speak() override
    {
        cout << "Dog barks" << endl;
    }
};
int main()
{
    Animal *p = new Dog("Rex", "Labrador");
    p->speak();
    delete p;
    return 0;
}

{{ select(2) }}

• Animal(name)
• super(name)
• Animal::Animal(name)
• Animal()

3. 代码同上一题，代码执行结果是（  ）。

{{ select(3) }}

• 输出 Animal speaks
• 输出 Dog barks
• 编译错误
• 程序崩溃

4. 以下关于栈和队列的代码，执行后输出是（   ）。

stack<int> s;
queue<int> q;

for (int i = 1; i <= 3; ++i)
{
    s.push(i);
    q.push(i);
}
cout << s.top() << " " << q.front() << endl;

{{ select(4) }}

• 1 3
• 3 1
• 3 3
• 1 1

5. 在一个循环队列中，front是指向队头的指针， rear指向队尾的指针，队列最大容量为 maxSize。判断队列已满的条件是（  ）。

{{ select(5) }}

• rear == front
• (rear + 1) % maxSize == front
• (rear - 1 + maxSize) % maxSize == front
• (rear - 1) == front

6. （   ）只有最底层的节点未被填满，且最底层节点尽量靠左填充。

{{ select(6) }}

• 完美二叉树
• 完全二叉树
• 完满二叉树
• 平衡二叉树

7. 在使用数组表示完全二叉树时，如果一个节点的索引为 i（从开始计数），那么其左子节点的索引通常是（   ）。

{{ select(7) }}

• ( i-1 ) / 2
• i + 1
• i * 2
• 2 * i + 1

8. 已知一棵二叉树的前序遍历序列为 GDAFEMHZ，中序遍历序列为 ADFGEHMZ，则其后序遍历序列为（   ）。

{{ select(8) }}

• ADFGEHMZ
• ADFGHMEZ
• AFDGEMZH
• AFDHZMEG

9. 设有字符集 {a, b, c, d, e}，其出现频率分别为 {5, 8, 12, 15, 20}，得到的哈夫曼编码为（   ）。

{{ select(9) }}

• a: 010
b: 011
c: 00
d: 10
e: 11
• a: 00
b: 10
c: 011
d: 100
e: 111
• a: 10
b: 01
c: 011
d: 100
e: 111
• a: 100
b: 01
c: 011
d: 100
e: 00

10. 3位格雷编码中，编码 101 之后的下一个编码不可能是（   ）。

{{ select(10) }}

• 100
• 111
• 110
• 001

11. 请将下列 C++ 实现的深度优先搜索（DFS）代码补充完整，横线处应填入（   ）。

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void dfs(TreeNode *root, vector<int> &result)
{
    if (root == nullptr)
        return;
    __________________________
}

{{ select(11) }}

• result.push_back(root->val);
dfs(root->left);
dfs(root->right);
• result.push_back(root->left->val);
dfs(root->right);
dfs(root->left);
• result.push_back(root->left->val);
dfs(root->left);
dfs(root->right);
• result.push_back(root->right->val);
dfs(root->right);
dfs(root->left);

12. 给定一个二叉树，返回每一层中最大的节点值，结果以数组形式返回，横线处应填入（   ）。

#include <vector>
#include <queue>
#include <algorithm>

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<int> largestValues(TreeNode *root)
{
    vector<int> result;
    if (!root)
        return result;
    queue<TreeNode *> q;
    q.push(root);

    while (!q.empty())
    {
        int sz = q.size();
        int maxVal = INT_MIN;
        for (int i = 0; i < sz; ++i)
        {
            TreeNode *node;
            _______________________________
            maxVal = max(maxVal, node->val);
            if (node->left)
                q.push(node->left);
            if (node->right)
                q.push(node->right);
        }
        result.push_back(maxVal);
    }
    return result;
}

{{ select(12) }}

• node = q.end();
• node = q.front();
• q.pop();
node = q.front();
• node = q.front();
q.pop();

13. 下面代码实现一个二叉排序树的插入函数（没有相同的数值），横线处应填入（   ）。

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void insert(TreeNode *&root, int key)
{
    if (!root)
    {
        root = new TreeNode(key);
        return;
    }
    _______________________________
}

{{ select(13) }}

• if (key < root->val)
    insert(root->left, key);
else if (key > root->val)
    insert(root->right, key);
• if (key < root->val)
    insert(root->right, key);
else if (key > root->val)
    insert(root->left, key);
• insert(root->left, key);
insert(root->right, key);
• insert(root->right, key);
insert(root->left, key);

14. 以下关于动态规划算法特性的描述，正确的是（   ）。

{{ select(14) }}

• 子问题相互独立，不重叠
• 问题包含重叠子问题和最优子结构
• 只能从底至顶迭代求解
• 必须使用递归实现，不能使用迭代

15. 给定 n 个物品和一个最大承重为 W 的背包，每个物品有一个重量 wt[i] 和价值 val[i]，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过 W。关于下面代码，说法正确的是（   ）。

int knapsack1D(int W, vector<int> &wt, vector<int> &val, int n)
{
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; ++i)
    {
        for (int w = W; w >= wt[i]; --w)
        {
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[W];
}

{{ select(15) }}

• 该算法不能处理背包容量为 0 的情况
• 外层循环 i 遍历背包容量，内层遍历物品
• 从大到小遍历 w 是为了避免重复使用同一物品
• 这段代码计算的是最小重量而非最大价值