#1588. GESP-C++六级(2025-12)

GESP-C++六级(2025-12)

CCF GESP C++ 六级 (2025 年 12 月)

一、单选题（每题 2 分，共 30 分）

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

{{ select(1) }}

  • 虚函数⽤于⽀持运⾏时多态
  • 通过基类指针调⽤虚函数时，会根据对象实际类型决定调⽤版本
  • 构造函数可以声明为虚函数以⽀持多态
  • 基类析构函数常声明为虚函数以避免资源泄漏

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

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 < 3; ++i) {
        delete instruments[i];
    }
    return 0;
}

{{ select(2) }}

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

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

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 < 3; ++i) {
        delete instruments[i];
    }
    return 0;
}
}

{{ select(3) }}

  • 执⾏代码会输出两⾏，内容分别为： 钢琴：叮咚叮咚 和 吉他：咚咚当当
  • 执⾏代码会输出两⾏，内容分别为： 乐器在演奏声音 和 乐器在演奏声音
  • 代码编译出现错误
  • 代码运⾏出现错误

4. 某⽂本编辑器把⽤户输⼊的字符依次压⼊栈 S。⽤户依次输⼊ A , B , C , D 后，⽤户按了两次撤销（每次 撤销，弹出栈顶⼀个字符）。此时栈从栈底到栈顶的内容是：（ ）。

{{ select(4) }}

  • A B
  • A B C
  • A B D
  • B C

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

{{ select(5) }}

  • (2, 5)
  • (2, 0)
  • (3, 5)
  • (3, 0)

6. 以下函数 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;
}

{{ select(6) }}

  • 满⼆叉树
  • 完全⼆叉树
  • ⼆叉搜索树
  • 平衡⼆叉树

7. 以下代码实现了⼆叉树的（ ）

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

{{ select(7) }}

  • 前序遍历
  • 中序遍历
  • 后序遍历
  • 层序遍历

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

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;
}

nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, -1));
internalIdx.push_back(z);

nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, -1));
leafIdx.push_back(z);

internalIdx.push_back(z);
nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, x+y));

nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, x+y));
leafIdx.push_back(z);

{{ select(8) }}

  • 1
  • 2
  • 3
  • 4

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

{{ select(9) }}

  • 哈夫曼编码是定长编码
  • 哈夫曼编码中，没有任何⼀个字符的编码是另⼀个字符编码的前缀
  • 哈夫曼编码⼀定唯⼀
  • 哈夫曼编码不能⽤于数据压缩

10. 以下函数实现了⼆叉排序树（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;
}

{{ select(10) }}

  • 查找
  • 插⼊
  • 删除
  • 遍历

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

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);
        _______________//此处填入代码
    }
}

{{ select(11) }}

  • if (node->left) st.push(node->left);
  • if (node->left) st.pop(node->left);
  • if (node->left) st.front(node->left);
  • if (node->left) st.push(node->right);

12. 给定⼀棵普通⼆叉树（节点值没有⼤⼩规律），下⾯代码判断是否存在值为 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;
}

q.push(cur);

if (cur->right) q.push(cur->right);

if (cur->left)
  q.push(cur->left);
if (cur->right)
  q.push(cur->right);

q.push(cur->left);
q.push(cur->right);

{{ select(12) }}

  • 1
  • 2
  • 3
  • 4

13. 在⼆叉排序树（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;
}

{{ select(13) }}

  • 最坏情况下，访问结点数是O(logn)
  • 最坏情况下，访问结点数是O(n)
  • ⽆论如何，访问结点数都不超过树⾼的⼀半
  • ⼀定⽐在普通⼆叉树中搜索快

14. 0/1 背包（每件物品最多选⼀次）问题通常可⽤⼀维动态规划求解，核⼼代码如下。则下⾯说法正确的是（ ）。

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

{{ select(14) }}

  • 内层 j 必须从⼩到⼤，否则会漏解
  • 内层 j 必须从⼤到⼩，否则同⼀件物品会被⽤多次
  • j 从⼤到⼩或从⼩到⼤都⼀样
  • 只要 dp 初始为 0 ，⽅向⽆所谓

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

{{ select(15) }}

  • 动态规划⽅法通常能够列出递推公式。
  • 动态规划⽅法的时间复杂度通常为状态的个数。
  • 动态规划⽅法有递推和递归两种实现形式。
  • 对很多问题，递推实现和递归实现动态规划⽅法的时间复杂度相当。

二、判断题（每题 2 分，共 20 分）

1. 以下代码中，构造函数被调⽤的次数是1次

class Test {
public:
    Test() { cout << "T"; }
};

int main() {
    Test a;
    Test b = a;
}

{{ select(16) }}

  • 对
  • 错

2. ⾯向对象编程中，封装是指将数据和操作数据的⽅法绑定在⼀起，并对外隐藏实现细节

{{ select(17) }}

  • 对
  • 错

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

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

{{ select(18) }}

  • 对
  • 错

4. ⼴度优先遍历⼆叉树可⽤栈来实现

{{ select(19) }}

  • 对
  • 错

5. 函数调⽤管理可⽤栈来管理

{{ select(20) }}

  • 对
  • 错

6. 在⼆叉排序树（BST）中，若某结点的左⼦树为空，则该结点⼀定是整棵树中的最⼩值结点

{{ select(21) }}

  • 对
  • 错

7. 下⾯的函数能正确判断⼀棵树是不是⼆叉排序树（左边的数字要⽐当前数字⼩，右边的数字要⽐当前数字 ⼤）。

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);
}

{{ select(22) }}

  • 对
  • 错

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

{{ select(23) }}

  • 对
  • 错

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

{{ select(24) }}

  • 对
  • 错

10. 假定只有⼀个根节点的树的深度为1，则⼀棵有 个节点的完全⼆叉树，则树的深度为一棵有 nn 个节点的完全二叉树，其高度为：⌊log⁡2(n)⌋+1\lfloor \log_2(n) \rfloor + 1

{{ select(25) }}

  • 对
  • 错
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  3. Worker 0, 259ms
  4. Powered by Hydro v4.13.3 Community