GESP 六级 · 2025 真题

在面向对象编程中，下列关于虚函数的描述中，错误的是（）。

执行如下代码，会输出 钢琴：叮咚叮咚 和 吉他：咚咚当当。这体现了面向对象编程的（ ）特性。

01class Instrument {
02public:
03    virtual void play() {
04        cout << "乐器在演奏声音" << endl;
05    }
06    virtual ~Instrument() {}
07};
08
09class Piano : public Instrument {
10public:
11    void play() override {
12        cout << "钢琴：叮咚叮咚" << endl;
13    }
14};
15
16class Guitar : public Instrument {
17public:
18    void play() override {
19        cout << "吉他：咚咚当当" << endl;
20    }
21};
22
23int main() {
24    Instrument* instruments[2];
25    instruments[0] = new Piano();
26    instruments[1] = new Guitar();
27
28    for (int i = 0; i < 2; ++i) {
29        instruments[i]->play();
30    }
31
32    for (int i = 0; i < 2; ++i) {
33        delete instruments[i];
34    }
35    return 0;
36}

关于以下代码，说法正确的是（）。

01class Instrument {
02public:
03    void play() {
04        cout << "乐器在演奏声音" << endl;
05    }
06    virtual ~Instrument() {}
07};
08
09class Piano : public Instrument {
10public:
11    void play() override {
12        cout << "钢琴：叮咚叮咚" << endl;
13    }
14};
15
16class Guitar : public Instrument {
17public:
18    void play() override {
19        cout << "吉他：咚咚当当" << endl;
20    }
21};
22
23int main() {
24    Instrument* instruments[2];
25    instruments[0] = new Piano();
26    instruments[1] = new Guitar();
27
28    for (int i = 0; i < 2; ++i) {
29        instruments[i]->play();
30    }
31
32    for (int i = 0; i < 2; ++i) {
33        delete instruments[i];
34    }
35    return 0;
36}

某文本编辑器把用户输入的字符依次压入栈 S。用户依次输入 A、B、C、D 后，用户按了两次撤销（每次撤销，弹出栈顶一个字符）。此时栈从栈底到栈顶的内容是（）。

假设循环队列数组长度为 $N$，其中队空判断条件为：front == rear，队满判断条件为：(rear + 1) % N == front，出队对应的操作为：front = (front + 1) % N，入队对应的操作为：rear = (rear + 1) % N。循环队列长度 $N = 6$，初始 front = 1，rear = 1，执行操作序列为：入队、入队、入队、出队、入队、入队，则最终 (front, rear) 的值是（）。

以下函数 check() 用于判断一棵二叉树是否为（）。

01bool check(TreeNode* root) {
02    if (!root) return true;
03
04    queue<TreeNode*> q;
05    q.push(root);
06    bool hasNull = false;
07    while (!q.empty()) {
08        TreeNode* cur = q.front(); q.pop();
09        if (!cur) {
10            hasNull = true;
11        } else {
12            if (hasNull) return false;
13            q.push(cur->left);
14            q.push(cur->right);
15        }
16    }
17    return true;
18}

以下代码实现了二叉树的（）。

01void traverse(TreeNode* root) {
02    if (!root) return;
03    traverse(root->left);
04    traverse(root->right);
05    cout << root->val << " ";
06}

下面代码实现了哈夫曼编码，则横线处应填写的代码是（）。

01struct Symbol {
02    char ch;          //字符
03    long long freq;   //频率
04    string code;      //哈夫曼编码
05};
06
07struct Node {
08    long long w;      //权值
09    int l, r;         //左右孩子（节点下标），-1 表示空
10    int sym;          // 叶子对应符号下标；内部节点为 -1
11    Node(long long _w = 0, int _l = -1, int _r = -1, int _sym = -1)
12        : w(_w), l(_l), r(_r), sym(_sym) {}
13};
14
15// 从 A(leafIdx) 和 B(internalIdx) 的队首取最小的一个节点下标
16static int PopMinNode(const vector<Node>& nodes,
17                       const vector<int>& leafIdx, int n, int& pA,
18                       const vector<int>& internalIdx, int& pB) {
19    if (pA < n && (pB >= (int)internalIdx.size() ||
20        nodes[leafIdx[pA]].w <= nodes[internalIdx[pB]].w)) {
21        return leafIdx[pA++];
22    } else {
23        return internalIdx[pB++];
24    }
25}
26
27// DFS 生成编码（左 0，右 1）
28static void DFSBuildCodes(int u, const vector<Node>& nodes,
29                          Symbol sym[], string& path) {
30    if (u == -1) return;
31
32    if (nodes[u].sym != -1) {          // 叶子
33        sym[nodes[u].sym].code = path;
34        return;
35    }
36
37    path.push_back('0');
38    DFSBuildCodes(nodes[u].l, nodes, sym, path);
39    path.pop_back();
40
41    path.push_back('1');
42    DFSBuildCodes(nodes[u].r, nodes, sym, path);
43    path.pop_back();
44}
45
46int BuildHuffmanCodes(Symbol sym[], int n) {
47    for (int i = 0; i < n; i++) sym[i].code.clear();
48    if (n <= 0) return -1;
49
50    // 只有一个字符：约定编码为 "0"
51    if (n == 1) {
52        sym[0].code = "0";
53        return 0;
54    }
55
56    vector<Node> nodes;
57    nodes.reserve(2 * n);
58
59    // 1) 建立叶子节点
60    vector<int> leafIdx(n);
61    for (int i = 0; i < n; i++) {
62        leafIdx[i] = (int)nodes.size();
63        nodes.push_back(Node(sym[i].freq, -1, -1, i));
64    }
65
66    // 2) 叶子按权值排序（A 队列）
67    sort(leafIdx.begin(), leafIdx.end(),
68        [&nodes](int a, int b) {
69            if (nodes[a].w != nodes[b].w) return nodes[a].w < nodes[b].w;
70            return nodes[a].sym < nodes[b].sym;  // 稳定一下
71        });
72
73    // B 队列（内部节点下标队列）
74    vector<int> internalIdx;
75    internalIdx.reserve(n);
76
77    int pA = 0, pB = 0;
78
79    // 3) 合并 n-1 次
80    for (int k = 1; k < n; k++) {
81        int x = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);
82        int y = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);
83
84        int z = (int)nodes.size();
85        ____________ // 在此处填写代码
86    }
87
88    int root = internalIdx.back();
89
90    // 4) DFS 生成编码
91    string path;
92    DFSBuildCodes(root, nodes, sym, path);
93    return root;
94}

以下关于哈夫曼编码的说法，正确的是（）。

以下函数实现了二叉排序树（BST）的（ ）操作。

01TreeNode* op(TreeNode* root, int x) {
02    if (!root) return new TreeNode(x);
03    if (x < root->val)
04        root->left = op(root->left, x);
05    else
06        root->right = op(root->right, x);
07    return root;
08}

下列代码实现了树的深度优先遍历，则横线处应填入（）。

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    stack<TreeNode*> st;
11    st.push(root);
12    while (!st.empty()) {
13        TreeNode* node = st.top(); st.pop();
14        cout << node->val << " ";
15        if (node->right) st.push(node->right);
16        ____________
17    }
18}

给定一棵普通二叉树（节点值没有大小规律），下面代码判断是否存在值为 $x$ 的结点，则横线处应填入（）。

01TreeNode* bfsFind(TreeNode* root, int x) {
02    if (!root) return nullptr;
03
04    queue<TreeNode*> q;
05    q.push(root);
06
07    while (!q.empty()) {
08        TreeNode* cur = q.front(); q.pop();
09        if (cur->val == x) return cur;
10        ____________
11    }
12    return nullptr;
13}

在二叉排序树（Binary Search Tree，BST）中，假设节点值互不相同。给定如下搜索函数，以下说法一定正确的是（）。

01bool find(Node* root, int x) {
02    while (root) {
03        if (root->val == x) return true;
04        root = (x < root->val) ? root->left : root->right;
05    }
06    return false;
07}

第 0/1 背包（每件物品最多选一次）问题通常可用一维动态规划求解，核心代码如下。则下面说法正确的是（）。

01for each item (w, v):
02    for (int j = W; j >= w; --j)
03        dp[j] = max(dp[j], dp[j-w] + v);

以下关于动态规划的说法中，错误的是（）。

以下代码中，构造函数被调用的次数是 $1$ 次。

01class Test {
02    public:
03    Test() { cout << "T "; }
04};
05
06int main() {
07    Test a;
08    Test b = a;
09}

面向对象编程中，封装是指将数据和操作数据的方法绑定在一起，并对外隐藏实现细节。

以下代码能够正确统计二叉树中叶子结点的数量。

01int countLeaf(TreeNode* root) {
02    if (!root) return 0;
03    if (!root->left && !root->right) return 1;
04    return countLeaf(root->left) + countLeaf(root->right);
05}

广度优先遍历二叉树可用栈来实现。

函数调用管理可用栈来管理。

在二叉排序树（BST）中，若某结点的左子树为空，则该结点一定是整棵树中的最小值结点。

下面的函数能正确判断一棵树是不是二叉排序树（左边的数字要比当前数字小，右边的数字要比当前数字大）。

01bool isBST(TreeNode* root, int minVal, int maxVal) {
02    if (!root) return true;
03    if (root->val <= minVal || root->val >= maxVal)
04        return false;
05    return isBST(root->left, minVal, root->val) &&
06           isBST(root->right, root->val, maxVal);
07}

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

小杨在玩一个闯关游戏，从第 $1$ 关走到第 $4$ 关。每一关的体力消耗如下（下标表示关卡编号）：cost = [0, 3, 5, 2, 4]，其中 cost[i] 表示到达第 $i$ 关需要消耗的体力，cost[0]=0 表示在开始状态，体力消耗为 $0$。小杨每次可以从当前关卡前进 $1$ 步或 $2$ 步。按照上述规则，从第 $1$ 关到第 $4$ 所需消耗的最小体力为 $7$。

假定只有一个根节点的树的深度为 $1$，则一棵有 $n$ 个节点的完全二叉树，树的深度为 floor(log2(n)) + 1。