2025年12月 GESP C++ 6级

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

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

class Instrument {
    public:
    virtual void play() {
        cout << "乐器在演奏声音" << endl;
    }
    virtual ~Instrument() {}
};
class Piano : public Instrument {
    public:
    void play() override {
        cout << "钢琴：叮咚叮咚" << endl;
    }
};
class Guitar : public Instrument {
    public:
    void play() override {
        cout << "吉他：咚咚当当" << endl;
    }
};
int main() {
    Instrument* instruments[2];
    instruments[0] = new Piano();
    instruments[1] = new Guitar();
    for (int i = 0; i < 2; ++i) {
        instruments[i]->play();
    }
    for (int i = 0; i < 2; ++i) {
        delete instruments[i];
    }
    return 0;
}

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

class Instrument {
    public:
    void play() {
        cout << "乐器在演奏声音" << endl;
    }
    virtual ~Instrument() {}
};
class Piano : public Instrument {
    public:
    void play() override {
        cout << "钢琴：叮咚叮咚" << endl;
    }
};
class Guitar : public Instrument {
    public:
    void play() override {
        cout << "吉他：咚咚当当" << endl;
    }
};
int main() {
    Instrument* instruments[2];
    instruments[0] = new Piano();
    instruments[1] = new Guitar();
    for (int i = 0; i < 2; ++i) {
        instruments[i]->play();
    }
    for (int i = 0; i < 2; ++i) {
        delete instruments[i];
    }
    return 0;
}

某文本编辑器把用户输入的字符依次压入栈 $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() 用于判断一棵二叉树是否为（ ）。

bool check(TreeNode* root) {
    if (!root) return true;
    queue<TreeNode*> q;
    q.push(root);
    bool hasNull = false;
    while (!q.empty()) {
        TreeNode* cur = q.front(); q.pop();
        if (!cur) {
            hasNull = true;
        } else {
            if (hasNull) return false;
            q.push(cur->left);
            q.push(cur->right);
        }
    }
    return true;
}

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

void traverse(TreeNode* root) {
    if (!root) return;
    traverse(root->left);
    traverse(root->right);
    cout << root->val << " ";
}

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

struct Symbol {
    char ch; // 字符
    long long freq; // 频率
    string code; // 哈夫曼编码
};
struct Node {
    long long w; // 权值
    int l, r; // 左右孩子（节点下标），-1 表示空
    int sym; // 叶子对应符号下标；内部节点为 -1
    Node(long long _w=0, int _l=-1, int _r=-1, int _sym=-1)
    : w(_w), l(_l), r(_r), sym(_sym) {}
};
// 从 A(leafIdx) 和 B(internalIdx) 的队首取最小的一个节点下标
static int PopMinNode(const vector<Node>& nodes,
const vector<int>& leafIdx, int n, int& pA,
const vector<int>& internalIdx, int& pB) {
    if (pA < n && (pB >= (int)internalIdx.size() ||
    nodes[leafIdx[pA]].w <= nodes[internalIdx[pB]].w)) {
        return leafIdx[pA++];
    }
    else {
        return internalIdx[pB++];
    }
}
// DFS 生成编码（左 0，右 1）
static void DFSBuildCodes(int u, const vector<Node>& nodes, Symbol sym[], string& path) {
    if (u == -1) return;
    if (nodes[u].sym != -1) { // 叶子
        sym[nodes[u].sym].code = path;
        return;
    }
    path.push_back('0');
    DFSBuildCodes(nodes[u].l, nodes, sym, path);
    path.pop_back();
    path.push_back('1');
    DFSBuildCodes(nodes[u].r, nodes, sym, path);
    path.pop_back();
}
int BuildHuffmanCodes(Symbol sym[], int n) {
    for (int i = 0; i < n; i++) sym[i].code.clear();
    if (n <= 0) return -1;
    // 只有一个字符：约定编码为 "0"
    if (n == 1) {
        sym[0].code = "0";
        return 0;
    }
    vector<Node> nodes;
    nodes.reserve(2 * n);
    // 1) 建立叶子节点
    vector<int> leafIdx(n);
    for (int i = 0; i < n; i++) {
        leafIdx[i] = (int)nodes.size();
        nodes.push_back(Node(sym[i].freq, -1, -1, i));
    }

// 2) 叶子按权值排序（A 队列）
sort(leafIdx.begin(), leafIdx.end(),
[&](int a, int b) {
    if (nodes[a].w != nodes[b].w) return nodes[a].w < nodes[b].w;
    return nodes[a].sym < nodes[b].sym; // 稳定一下
});
// B 队列（内部节点下标队列）
vector<int> internalIdx;
internalIdx.reserve(n);
int pA = 0, pB = 0;
// 3) 合并 n-1 次
for (int k = 1; k < n; k++) {
    int x = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);
    int y = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);
    int z = (int)nodes.size();
    ________________________ // 在此处填写代码
}
int root = internalIdx.back();
// 4) DFS 生成编码
string path;
DFSBuildCodes(root, nodes, sym, path);
return root;
}

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

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

TreeNode* op(TreeNode* root, int x) {
    if (!root) return new TreeNode(x);
    if (x < root->val)
        root->left = op(root->left, x);
    else
        root->right = op(root->right, x);
    return root;
}

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

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
void dfs(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top(); st.pop();
        cout << node->val << " ";
        if (node->right) st.push(node->right);
        ________________________
    }
}

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

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
TreeNode* bfsFind(TreeNode* root, int x) {
    if (!root) return nullptr;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* cur = q.front(); q.pop();
        if (cur->val == x) return cur;
        ________________________
    }
    return nullptr;
}

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

bool find(Node* root, int x) {
    while (root) {
        if (root->val == x) return true;
        root = (x < root->val) ? root->left : root->right;
    }
    return false;
}

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

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

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

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

class Test {
    public:
    Test() { cout << "T "; }
};
int main() {
    Test a;
    Test b = a;
}

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

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

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

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

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

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

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

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

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

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

假定只有一个根节点的树的深度为 $1$，则一棵有 $n$ 个节点的完全二叉树，则树的深度为 ⌊log⁡2n⌋+1\lfloor \log_2 n \rfloor + 1⌊log2​n⌋+1。

试题名称：路径覆盖

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

给定一棵有 $n$ 结点的有根树 $T$，结点依次以 $1,2,\dots ,n$ 编号，根结点编号为 $1$。方便起见，编号为 $i$ 的结点称为结点 $i$。

初始时 $T$ 中的结点均为白色。你需要将 $T$ 中的若干个结点染为黑色，使得所有叶子到根的路径上至少有一个黑色结点。将结点 $i$ 染为黑色需要代价 cic_ici​，你需要在满足以上条件的情况下，最小化染色代价之和。

叶子是指 $T$ 中没有子结点的结点。

输入格式

第一行，一个正整数 $n$，表示结点数量。

第二行，$n-1$ 个正整数 f2,f3,…,fnf_2,f_3,\ldots,f_nf2​,f3​,…,fn​，其中 fif_ifi​ 表示结点 $i$ 的父结点的编号，保证 fi<if_i<ifi​<i。

第三行，$n$ 个正整数 c1,c2,…,cnc_1,c_2,\ldots,c_nc1​,c2​,…,cn​，其中 cic_ici​ 表示将结点 $i$ 染为黑色所需的代价。

输出格式

一行，一个整数，表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下，染色代价之和的最小值。

样例输入 #1

4
1 2 3
5 6 2 3

样例输出 #1

2

样例输入 #2

7
1 1 2 2 3 3
64 16 15 4 3 2 1

样例输出 #2

10

说明/提示

对于 $40\%$ 的测试点，保证 $2\le n\le 16$。

对于另外 $20\%$ 的测试点，保证 fi=i−1f_i=i-1fi​=i−1。

对于所有测试点，保证 2≤n≤1052\le n\le 10^52≤n≤105，1≤ci≤1091\le c_i\le 10^91≤ci​≤109。

试题名称：道具商店

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

道具商店里有 $n$ 件道具可供挑选。第 $i$ 件道具可为玩家提升 aia_iai​ 点攻击力，需要 cic_ici​ 枚金币才能购买，每件道具只能购买一次。现在你有 $k$ 枚金币，请问你最多可以提升多少点攻击力？

输入格式

第一行，两个正整数 $n,k$，表示道具数量以及你所拥有的金币数量。

接下来 $n$ 行，每行两个正整数 ai,cia_i,c_iai​,ci​，表示道具所提升的攻击力点数，以及购买所需的金币数量。

输出格式

输出一行，一个整数，表示最多可以提升的攻击力点数。

样例输入 #1

3 5
99 1
33 2
11 3

样例输出 #1

132

样例输入 #2

4 100
10 1
20 11
40 33
100 99

样例输出 #2

110

说明/提示

对于 $60\%$ 的测试点，保证 $1\le k\le 500$，1≤ci≤5001\le c_i\le 5001≤ci​≤500。

对于所有测试点，保证 $1\le n\le 500$，1≤k≤1091 \le k\le 10^91≤k≤109，1≤ai≤5001\le a_i\le 5001≤ai​≤500，1≤ci≤1091\le c_i\le 10^91≤ci​≤109。