首页 › 试卷 › GESP编程能力等级认证 › GESP-C++六级 › 2025年3月CCF-GESP编程能力等级认证C++编程六级真题

2025年3月CCF-GESP编程能力等级认证C++编程六级真题 VIP

GESP-C++六级 共 27 题 2025 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、单选题

1. 单选题

在面向对象编程中,类是一种重要的概念。下面关于类的描述中,【不正确】的是?( )

  • A 类是一个抽象的概念,用于描述具有相同属性和行为的对象集合。
  • B 类可以包含属性和方法,属性用于描述对象的状态,方法用于描述对象的行为。
  • C 类可以被实例化,生成具体的对象。
  • D 类一旦定义后,其属性和方法不能被修改或扩展。
查看答案与解析
答案:D
解析:

选项D错误,类的属性和方法可以修改或扩展(如通过继承、补丁等)。

2. 单选题

哈夫曼编码是一种数据压缩算法。以下关于哈夫曼编码的描述中,【不正确】的是?( )

  • A 哈夫曼编码是一种变长编码,频率高的字符使用较短的编码,频率低的字符使用较长的编码。
  • B 在构造哈夫曼树时,频率越低的字符离根节点越近,频率越高的字符离根节点越远。
  • C 哈夫曼编码的生成过程基于贪心算法,每次选择频率最低的两个节点进行合并。
  • D 哈夫曼编码是一种前缀编码,任何一个字符的编码都不会是另一个字符编码的前缀,因此可以实现唯一解码。
查看答案与解析
答案:B
解析:

哈夫曼编码是一种基于字符出现频率的无损数据压缩算法,其核心思想是:

变长编码:频率高的字符用较短的编码,频率低的字符用较长的编码。

前缀编码:任何字符的编码都不是其他字符编码的前缀,确保解码唯一性。

贪心算法:通过合并频率最低的节点构建哈夫曼树。

选项B错误,哈夫曼树的构造规则是:频率越低的字符离根节点越远(路径更长),频率越高的字符离根节点越近(路径更短)。

3. 单选题

以下代码实现了树的哪种遍历方式?( )

void traverse(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << " ";
    traverse(root->left);
    traverse(root->right);
}
  • A 前序遍历
  • B 中序遍历
  • C 后序遍历
  • D 层次遍历
查看答案与解析
答案:A
解析:

树的遍历主要方式:

前序遍历:访问顺序:根节点 → 左子树 → 右子树。

中序遍历:访问顺序:左子树 → 根节点 → 右子树。

后序遍历:访问顺序:左子树 → 右子树 → 根节点。

这段代码实现了树的 前序遍历(根→左→右)。

4. 单选题

以下关于完全二叉树的代码描述,正确的是?( )

bool isCompleteTree(TreeNode* root) {
    if (root == nullptr) return true;
    queue<TreeNode*> q;
    q.push(root);
    bool hasNull = false;
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        if (node == nullptr) {
            hasNull = true;
        } else {
            if (hasNull) return false;
            q.push(node->left);
            q.push(node->right);
        }
    }
    return true;
}
  • A 该代码用于判断一棵树是否为满二叉树
  • B 该代码用于判断一棵树是否为完全二叉树
  • C 该代码用于判断一棵树是否为二叉搜索树
  • D 该代码用于计算树的高度
查看答案与解析
答案:B
解析:

使用队列 q 进行层序遍历,hasNull 标记是否遇到过空节点(初始为 false)。

遍历过程:

每次从队列中取出一个节点 node。

如果 node 是 nullptr:设置 hasNull = true。

如果 node 非空:若之前已遇到空节点(hasNull == true),则直接返回 false(违反完全二叉树的定义)。

否则,将 node 的左右子节点(无论是否为空)加入队列。

代码实现了 完全二叉树的判断逻辑。

5. 单选题

以下代码实现了二叉排序树的哪种操作?( )

TreeNode* op(TreeNode* root, int val) {
    if (root == nullptr) return new TreeNode(val);
    if (val < root->val) {
        root->left = op(root->left, val);
    } else {
        root->right = op(root->right, val);
    }
    return root;
}
  • A 查找
  • B 插入
  • C 删除
  • D 遍历
查看答案与解析
答案:B
解析:

程序中:

if (root == nullptr) return new TreeNode(val)

若目标值不存在,则在叶子节点位置创建新节点。

若目标值更小,递归查找左子树;若目标值更大,递归查找右子树。

这段代码通过递归查找插入位置并动态创建新节点,实现了 二叉排序树的插入操作。

6. 单选题

给定字符集 {A, B, C, D} 的出现频率分别为 {5, 1, 6, 2} ,则正确的哈夫曼编码是?( )

  • A A: 0, B: 100, C: 11, D: 101
  • B A: 11, B: 100, C: 0, D: 101
  • C A: 0, B: 101, C: 11, D: 100
  • D A: 10, B: 101, C: 0, D: 100
查看答案与解析
答案:B
这道题暂未补解析。
7. 单选题

关于动态规划的描述,正确的是?( )

  • A 动态规划算法的时间复杂度总是低于贪心算法。
  • B 动态规划要求问题必须具有最优子结构和重叠子问题两个性质。
  • C 动态规划通过递归实现时不需要存储中间结果。
  • D 动态规划的核心思想是将问题分解为互不重叠的子问题。
查看答案与解析
答案:B
解析:

选项B正确,动态规划问题的两个必要条件:

最优子结构确保问题可分解,重叠子问题使得记忆化有意义。

8. 单选题

以下代码中,类的构造函数被调用了( )次?

class MyClass {
    public:
        MyClass() {
            cout << "Constructor called!" << endl;
        }
};
int main() {
    MyClass obj1;
    MyClass obj2 = obj1;
    return 0;
}
  • A 1
  • B 2
  • C 3
  • D 0
查看答案与解析
答案:A
解析:

MyClass obj1:调用 默认构造函数,输出 "Constructor called!"。

MyClass obj2 = obj1,调用的是隐式拷贝构造函数,不会触发默认构造函数。

因此 构造函数仅被调用 1 次。

9. 单选题

以下代码实现了循环队列的哪种操作?( )

class CircularQueue {
        int* arr;
        int front, rear, size;
    public:
        CircularQueue(int k) {
            size = k;
            arr = new int[k];
            front = rear = -1;
        }
        bool enQueue(int value) {
            if (isFull()) return false;
            if (isEmpty()) front = 0;
            rear = (rear + 1) % size;
            arr[rear] = value;
            return true;
        }
};
  • A 入队
  • B 出队
  • C 查看队首元素
  • D 判断队列是否为空
查看答案与解析
答案:A
解析:

enQueue()函数(入队):

首先检查队列是否已满,如果已满则返回 false,表示入队失败。

如果队列为空(isEmpty()),初始化 front 为 0。

更新 rear 指针:rear = (rear + 1) % size,循环队列利用取模实现环形移动。

将新值 value 存入 arr[rear]。

返回 true 表示入队成功。

10. 单选题

以下代码实现了二叉树的深度优先搜索(DFS),并统计叶子结点的数量,则横线上应填写?( )

int countLeafNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    stack<TreeNode*> s;
    s.push(root);
    int count = 0;
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        if (node->left == nullptr && node->right == nullptr) {
            count++;
        }
        if (node->right) s.push(node->right);
        _____________________________________ // 在此处填入代码
    }
    return count;
}
  • A if (node->left) s.push(node->left);
  • B if (node->left) s.pop(node->left);
  • C if (node->left) s.front(node->left);
  • D if (node->left) s.push(node->right);
查看答案与解析
答案:A
解析:

空缺的位置在 while 循环的末尾,当前代码已经处理了右子树的压栈操作,需要补充左子树的处理逻辑。

程序使用栈(stack<TreeNode*>)来实现 DFS,空缺部分应该是一个类似的逻辑:如果 node 有左子节点,则将其压入栈。

本题答案为选项A。

11. 单选题

以下代码实现了二叉树的广度优先搜索(BFS),并查找特定值的节点,则横线上应填写?( )

TreeNode* findNode(TreeNode* root, int target) {
    if (root == nullptr) return nullptr;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* current = q.front();
        q.pop();
        if (current->val == target) {
            return current; // 找到目标节点
        }
        ___________________________________ // 在此处填入代码
    }
    return nullptr; // 未找到目标节点
}
  • A if (current->left) q.push(current->left);if (current->right) q.push(current->right);
  • B if (current->left) q.pop(current->left);if (current->right) q.pop(current->right);
  • C if (current->left) q.front(current->left);if (current->right) q.front(current->right);
  • D if (current->left) q.push(current->right);if (current->right) q.push(current->left);
查看答案与解析
答案:A
解析:

BFS 遍历:使用队列(queue)来实现 BFS。

初始时,将根节点 root 入队。

在 while 循环中,取出队首节点 current:

如果 current->val == target,则返回 current(找到目标节点)。

空缺部分需要将 current 的子节点(左子节点和右子节点)入队。

本题答案为选项A。

12. 单选题

以下代码用于生成 n 位格雷编码。横线上应填写?( )

vector<string> generateGrayCode(int n) {
    if (n == 0) return {"0"};
    if (n == 1) return {"0", "1"};
    vector<string> prev = generateGrayCode(n - 1);
    vector<string> result;
    for (string s : prev) {
        result.push_back("0" + s); // 在前缀添加 0
    }
    for (int i = prev.size() - 1; i >= 0; i--) {
        __________________________________ // 在此处填入代码
    }
    return result;
}
  • A result.push_back("1" + prev[i]);
  • B result.push_back("0" + prev[i]);
  • C result.push_back(prev[i] + "1");
  • D result.push_back(prev[i] + "0");
查看答案与解析
答案:A
解析:

格雷码的特点是:

相邻两个编码只有 1 位不同。

可以通过递归方式生成:n 位格雷码 = "0" + (n-1 位格雷码) + "1" + (n-1 位格雷码的逆序)。

前半部分:在 prev 的每个编码前加 "0"("0" + s)。

后半部分:在 prev 的 逆序 每个编码前加 "1"("1" + prev[i])。

本题答案为选项A。

13. 单选题

以下代码实现了0/1背包问题的动态规划解法。假设物品重量为 weights[] ,价值为 values[] ,背包容量为 W ,横线上应填写?( )

int knapsack(int W, vector<int>& weights, vector<int>& values) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            if (weights[i-1] > j) {
                dp[i][j] = dp[i-1][j]; // 当前物品装不下
            } else {
                dp[i][j] = max(_________________________); // 在此处填入代码
            }
        }
    }
    return dp[n][W];
}
  • A dp[i-1][j], values[i-1]
  • B dp[i-1][j], dp[i-1][j - weights[i-1]] + values[i-1]
  • C dp[i][j-1], values[i-1]
  • D dp[i-1][j - weights[i-1]] + values[i-1], dp[i][j-1]
查看答案与解析
答案:B
这道题暂未补解析。
14. 单选题

以下代码用于检查字符串中的括号是否匹配,横线上应填写?( )

bool isBalanced(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false; // 无左括号匹配
            char top = st.top();
            st.pop();
            if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return ________________; //在此处填入代码
}
  • A true
  • B false
  • C st.empty()
  • D !st.empty()
查看答案与解析
答案:C
这道题暂未补解析。
15. 单选题

关于下面代码,说法【错误】的是?( )

class Shape {
    protected:
        string name;
    public:
        Shape(const string& n) : name(n) {}
        virtual double area() const {
            return 0.0;
        }
};
class Circle : public Shape {
    private:
        double radius; // 半径
    public:
        Circle(const string& n, double r) : Shape(n), radius(r) {}
        double area() const override {
            return 3.14159 * radius * radius;
        }
};
class Rectangle : public Shape {
    private:
        double width; // 宽度
        double height; // 高度
    public:
        Rectangle(const string& n, double w, double h) : Shape(n), width(w), height(h) {
        }
        double area() const override {
            return width * height;
        }
};
int main() {
    Circle circle("MyCircle", 5.0);
    Rectangle rectangle("MyRectangle", 4.0, 6.0);
    Shape* shapePtr = &circle;
    cout << "Area: " << shapePtr->area() << endl;
    shapePtr = &rectangle;
    cout << "Area: " << shapePtr->area() << endl;
    return 0;
}
  • A 语句 Shape* shapePtr = &circle; 和 shapePtr = &rectangle; 出现编译错误
  • B Shape 为基类, Circle 和 Rectangle 是派生类
  • C 通过继承, Circle 和 Rectangle 复用了 Shape 的属性和方法,并扩展了新的功能
  • D Circle 和 Rectangle 通过重写(override)基类的虚函数 area 和基类指针,实现了运行时多态
查看答案与解析
答案:A
这道题暂未补解析。

二、判断题

16. 判断题

哈夫曼树在构造过程中,每次合并权值最小的两个节点,最终生成的树带权路径长度最小。( )

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
17. 判断题

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

  • A对
  • B错
查看答案与解析
答案:错
解析:

格雷码定义:相邻的两个格雷码之间仅一位不同。

18. 判断题

在树的深度优先搜索(DFS)中,使用队列作为辅助数据结构以实现“先进后出”的访问顺序。( )

  • A对
  • B错
查看答案与解析
答案:错
解析:

说法错误,在树的深度优先搜索(DFS)中,使用栈作为辅助数据结构以实现“先进后出”的访问顺序。

19. 判断题

以下代码实现的是二叉树的中序遍历。( )

void traverse(TreeNode* root) {
    if (root == nullptr) return;
    traverse(root->left);
    cout << root->val << " ";
    traverse(root->right);
}
  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
20. 判断题

C++ 支持构造函数重载,但默认无参数的构造函数只能有一个。( )

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
21. 判断题

二叉排序树(BST)中,若某节点的左子树为空,则该节点一定是树中的最小值节点。( )

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
22. 判断题

在动态规划解决一维硬币找零问题时,若硬币面额为 [1, 3, 4] ,目标金额为 6 ,则最少需要 2 枚硬币(3+3)。( )

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
23. 判断题

面向对象编程中,封装是指将数据和行为绑定在一起,并对外隐藏实现细节。( )

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
24. 判断题

以下代码创建的树是一棵完全二叉树。( )

TreeNode* root = new TreeNode{1};

root->left = new TreeNode{2};

root->right = new TreeNode{3};

root->left->left = new TreeNode{4};

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
25. 判断题

栈和队列均可以用双向链表实现,插入和删除操作的时间复杂度为 O(1) 。( )

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。

三、简答题

26. 简答题

树上漫步

时间限制:1 s,内存限制:512 MB

【问题描述】

小 A 有一棵 n 个结点的树,这些结点依次以 1、2、……、n标号。

小 A 想在这棵树上漫步。具体来说,小 A 会从树上的某个结点出发,每一步可以移动到与当前结点相邻的结点,并且小 A 只会在偶数步(可以是零步)后结束漫步。

现在小 A 想知道,对于树上的每个结点,从这个结点出发开始漫步,经过偶数步能结束漫步的结点有多少个(可以经过重复的节点)。

【输入描述】

第一行,一个正整数 n。

接下来 n - 1 行,每行两个整数 ui、vi,表示树上有一条连接结点 ui 和结点 vi 的边。

【输出描述】

一行, n 个整数,第 i 个整数表示从结点 i 出发开始漫步,能结束漫步的结点数量。

【样例输入1】

3
1 3
2 3

【样例输出1】

2 2 1

【样例输入2】

4
1 3
3 2
4 3

【样例输出2】

3 3 1 3

【数据范围】

对于 20% 的测试点,保证 1<=n<=1000。

对于所有测试点,保证 1<=n<=200000。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; #include &lt;algorithm&gt; using namespace std; const int N = 2e5 + 5; const int E = N &lt;&lt; 1; int n; int h[N], to[E], nx[E], et; int cnt[N], bel[N]; void ae(int u, int v) {     et++;     to[et] = v;     nx[et] = h[u];     h[u] = et; } void dfs(int u, int c, int f) {     bel[u] = c;     cnt[c]++;     for (int i = h[u]; i; i = nx[i])         if (to[i] != f)             dfs(to[i], c ^ 1, u); } int main() {     scanf("%d", &amp;n);     for (int i = 1; i &lt; n; i++) {         int u, v;         scanf("%d%d", &amp;u, &amp;v);         ae(u, v);         ae(v, u);     }     dfs(1, 0, 0);     for (int i = 1; i &lt;= n; i++)         printf("%d%c", cnt[bel[i]], " \n"[i == n]);     return 0; }</pre>
这道题暂未补解析。
27. 简答题

环线

时间限制:1 s,内存限制:512 MB

【问题描述】

小 A 喜欢坐地铁。地铁环线有 n 个车站,依次以 1、2、……、n标号。车站 i(1<=i<n )的下一个车站是车站 i+1。

特殊地,车站 n 的下一个车站是车站 1。

小 A 会从某个车站出发,乘坐地铁环线到某个车站结束行程,这意味着小 A 至少会经过一个车站。小 A 不会经过一个车站多次。

当小 A 乘坐地铁环线经过车站 i 时,小 A 会获得 ai 点快乐值。请你安排小 A 的行程,选择出发车站与结束车站,使得获得的快乐值总和最大。

【输入描述】

第一行,一个正整数 n,表示车站的数量。

第二行, n 个整数 a1、a2、……、an,分别表示经过每个车站时获得的快乐值。

【输出描述】

一行,一个整数,表示小 A 能获得的最大快乐值。

【样例输入1】

4
-1 2 3 0

【样例输出1】

5

【样例输入2】

5
-3 4 -5 1 3

【样例输出2】

5

【数据范围】

对于 20% 的测试点,保证 1<=n<=200。

对于 40% 的测试点,保证 1<=n<=2000。

对于所有测试点,保证 1<=n<=200000, -10^9<=ai<=10^9。

正确答案: 暂无(答题 0次,答对 0次,正确率:0%)

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; #include &lt;algorithm&gt; using namespace std; const int N = 4e5 + 5; int n; long long a[N], pre[N]; int q[N], ql, qr; long long ans; int main() {     scanf("%d", &amp;n);     for (int i = 1; i &lt;= n; i++) {         scanf("%lld", &amp;a[i]);         a[n + i] = a[i];     }     for (int i = 1; i &lt;= 2 * n; i++)         pre[i] = pre[i - 1] + a[i];     ql = qr = 1;     ans = -1e18;     for (int i = 1; i &lt;= 2 * n; i++) {         while (ql &lt;= qr &amp;&amp; q[ql] &lt; i - n)             ql++;         ans = max(ans, pre[i] - pre[q[ql]]);         while (ql &lt;= qr &amp;&amp; pre[i] &lt; pre[q[qr]])             qr--;         q[++qr] = i;     }     printf("%lld\n", ans);     return 0; }</pre>
这道题暂未补解析。