这次给大家带来的是2024年6月C++ Level 6认证真题解析。

2024 年6 月获得GESP 认证C++ 6 级

1.选择题（每题2分，共30分）

问题编号

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

回答

D

乙

一个

乙

乙

一个

一个

C

一个

一个

一个

D

C

一个

C

1、面向对象编程思想主要包括（ ）原则。

A. 贪心、动态规划、回溯

B. 并发、并行、异步

C. 递归、循环、分而治之

D.封装、继承、多态

【答案】D

【考试知识点】面向对象思维

【分析】面向对象编程思想（OOP）主要包括多态性、继承性和封装性原则。

多态性：多态性允许程序在运行时根据对象的实际类型选择执行方法，增加了代码的灵活性和可扩展性。

继承：通过继承，子类可以扩展父类的功能，而无需重写现有代码，提高代码的可重用性和可维护性。

封装：封装隐藏了对象的内部状态，仅提供必要的操作接口，保护对象数据不被外部直接访问，保证数据的安全性和完整性。

这些原则共同构成了面向对象编程的核心，使代码更加模块化、可重用、可维护和可扩展。

2. 运行以下代码，屏幕上将输出( )。

A.1 1 1

B.1 2 3

C.1 1 2

D.1 2 2

【答案】B

【考试大纲知识点】静态变量和类的创建（析构函数）

3. 运行以下代码并在屏幕上输出( )。

A.矩形面积： 三角形面积：

B. 父类区域： 父类区域：

C.运行时出现错误

D.编译时出错

【答案】A

【考试大纲知识点】类方法调用

【分析】main函数实例化了两个对象，矩形rec和三角形tri。 pshape调用rec的area()方法并输出矩形area:然后pshape调用tri的area()方法并输出三角形area:

4. 当将指针为s的节点插入到栈顶为hs的链栈时，应执行( )。

一个。 hs-下一个=s;

B.s-next=hs； hs=s；

C. s-下一个=hs-下一个； hs-下一个=s;

D. s-next=hs; hs=hs-下一个；

【答案】B

【考试大纲知识点】堆栈

【分析】指针之间的赋值：A=B可以理解为A指向B，栈的结构是先进后出，所以S需要作为栈顶存在，hs需要指向S ，即hs=s；但在此之前，需要将S链接到hs，即S的next指针指向S，且S-next=hs；

5、栈数据结构中，添加和删除元素遵循什么原则？

A、先进先出

B、先进后出

C. 最小值先出

D、随机顺序

【答案】B

【考试大纲知识点】堆栈

【分析】向栈添加元素的原则是先进先出（后进先出）。

6. 要将输入的十进制正整数转换为二进制表示形式，下面横线上应填写的代码是（ ）。

a.cout bin.top(); bin.pop();

B.bin.pop(); cout bin.top();

C.cout bin.back(); bin.pop();

D.cout bin.front(); bin.pop();

【答案】B

【考试大纲知识点】堆栈

【分析】如果将十进制拆分为每一位，这个过程可以理解为将十进制转换为二进制。如果%10/10改为%2/2，那么这相当于将十进制转换为二进制。

代码中的ten2bin()将每一位进行拆分并返回到堆栈st。 bin接收到值后，可以按照栈的弹出规则依次输出，所以答案为B。

7. 循环队列类定义如下。请完成判断队列是否已满的函数。 ( )应横填。

A.return(后+1)%容量==前；

B.返回后部%容量==前部；

C.返回后部==前部；

D、return(后+1)==前；

【答案】A

【考试知识点】循环队列

【分析】判断循环队列是否已满，可以将队列的rear指针加1，然后对等于front指针的容量取模结果。这表明队列已满，否则未满。

8. 对“classmycls”使用霍夫曼编码，至少需要( ) 位。

一个

.10

B.20

C.25

D.30

【答案】C

【考试知识点】霍夫曼编码

【分析】按照哈夫曼编码规则创建一棵树，如图，按照左0右1的二进制格式进行编码，可以得到每个字符的编码：

长度(C)=长度(S)=长度(L)=2,长度(A)=3,长度(Y)=长度(M)=4

经过计算，可以得到classmycls的总长度=2+2+3+2+2+4+4+2+2+2=25。

9. 二叉树中第一个访问的节点( ) 是根节点。

A. 前序遍历

B、中序遍历

C.后序遍历

D.以上所有

【答案】A

【考试知识点】二叉树搜索算法

【分析】前序遍历是从根开始，然后是左子树，然后是右子树，中序遍历是从左子树开始，然后是根，然后是右子树，后序遍历是从左子树开始子树，然后是右子树，然后是根。

10. 五层满二叉树的节点数为（ ）。

A.31

B.32

C.33

D.16

【答案】A

【考试知识点】完全二叉树

【分析】K级满二叉树的节点数为1+2+4+.+2k-1=2k-1（等比数列/二叉）。

11.在解决优化问题时，动态规划常常涉及到两个重要的性质，即最优子结构和（）。

A. 重叠子问题

B、分而治之

C. 贪婪策略

D.回溯算法

【答案】A

【考试知识点】动态规划

【分析】动态规划的性质主要包括最优子结构、无后效应和重叠子问题。

最优子结构：如果一个问题的最优解包含的子问题的解也是最优的，则称该问题具有最优子结构，即满足优化原理。这意味着问题的最优解可以从其子问题的最优解构造出来。

无后遗症：即某一阶段的状态一旦确定，就不会受到该状态下后续决策的影响。也就是说，某个状态之后的过程不会影响之前的状态，而只与当前状态相关。这个属性保证了动态规划方法的有效性，因为当前阶段的选择不会影响前一阶段的状态。

存在重叠子问题：子问题不是独立的，一个子问题在下一阶段的决策中可能会被多次使用。此属性是动态编程算法通过存储和重用子问题的解决方案来提高效率的能力的关键。

12.青蛙一次可以跳1或2步。下面的代码计算青蛙有多少种不同的方式可以跳到第n步。则下列说法错误的是（ ）。

A. 函数jump_recur()使用递归。

B. 函数jump_dp()采用动态规划方法。

C、当n较大时，函数jump_recur()重复计算次数较多，执行效率较低。

D、函数jump_recur()代码量小，执行效率高

【答案】D

【考试知识点】一维动态规划

【分析】

状态表示：dp[i]表示青蛙到达第i步的跳跃方法。

状态转移方程：第i步从两个状态转移i-2级跳两级i-1级跳一级，所以状态转移方程为：dp[i]=dp[i-1]+ dp[i -2]

目标状态：dp[n]

int Jump_recur(int n) 使用递归（斐波那契）并且没有内存，因此复杂度呈指数级增长。

int Jump_dp(int n) 采用动态规则（递归）方法，复杂度为O(n)。

13.阅读以下二叉树广度优先搜索代码：

使用上面的算法，当在下面的树中搜索值20时，可能的输出是（ ）

A.5 2 -4 3 17 9

B.-4 2 3 5 9 17

C.5 2 17 -4 3 9

D.以上都不正确

【答案】C

【考试知识点】二叉树搜索算法（层序遍历）

【分析】该程序采用的是广搜索法，因此是二叉树的层次顺序遍历。答案是C

14、与上题二叉树相同，阅读下面二叉树的深度优先搜索代码

使用上述算法，在二叉树中搜索值20 时，可能的输出为( )。

A.5 2 -4 3 17 9

B.-4 2 3 5 9 17

C.5 2 17 -4 3 9

D.以上都不正确

【答案】A

【考试知识点】二叉树搜索算法（前序遍历）

【解析】这题用的是栈，而不是DFS的递归形式。从输出和推送的顺序可知，本题是前序遍历，所以答案为A。

15、上题中在树中搜索值3时，使用深度优先搜索比较的节点总数为（ ）

A.2

B.3

C.4

D.5

【答案】C

【考试知识点】二叉树搜索算法（前序遍历）

【分析】这棵二叉树是通过中序遍历来排序的。同时，从结构上来说，它是一棵二叉排序树。然而，该程序不遵循二叉排序树的规则。问题是前序遍历比较，所以比较的节点是有序的。5, 2, -4, 3, 4 次共。

如图所示，比较分支为5-2-3

2.判断题（每题2分，共20分）

问题编号

1

2

3

4

5

6

7

8

9

10

回答

1.哈夫曼编码本质上是一种贪心策略。

【答案】正确

【考试知识点】霍夫曼编码

【分析】哈夫曼编码的原理是贪心的。

2、创建对象时，会自动调用该对象所属类的构造函数。如果没有定义构造函数，编译器会自动生成一个默认构造函数。

【答案】正确

【考试大纲知识点】创建班级

默认成员函数实际上相当于默认成员函数。如果你不写，编译器会默认生成它。如果你写了它，编译器不会生成它。

3、定义类时，必须手动定义析构函数，以释放对象占用的资源。

【答案】错误

【考试大纲知识点】创建班级

【分析】从上一个问题来看，析构函数编译器会默认生成。

4. 在C++中，类可以嵌套在类中。

【答案】正确

【考试大纲知识点】创建班级

【分析】在C++中，一个类可以定义在另一个类的内部。这种类型的类称为嵌套类或内部类。内部类可以访问外部类的所有成员，包括私有成员。

5. 000、001、011、010、110、111、101、100 是一组格雷码。

【答案】正确

【考试知识点】格雷码

【分析】格雷码的特点是：相邻的两个格雷码只有一位二进制位不同。第一个和最后一个元素也随之而来。

6、对于n个节点的双向循环链表，查找节点的平均时间复杂度为O(logn)。

【答案】错误

【考试知识点】双向循环链表

【解析】考察数据结构中链表的知识。查找数据的平均时间复杂度为O(n)。

7、完全二叉树可以使用数组来存储数据。

【答案】正确

【考试知识点】完全二叉树

【分析】完全二叉树是相对平衡的，因此可以从1开始编号作为根。对于每个后续节点i，其左右两个子节点的下标分别为2*i 和2*i+1。

8.在C++中，静态成员函数只能访问静态成员变量。

【答案】正确

【考试大纲知识点】

【分析】C++中，静态成员函数只能访问静态成员变量。这是因为非静态成员变量属于类的对象，而静态成员变量属于类本身。当类的实例未创建时，非静态成员变量不存在，因此静态成员函数无法访问它们。

9. 在深度优先搜索中，通常使用队列来辅助实现。

【答案】错误

【考试大纲知识点】深度优先搜索算法（DFS）

【分析】深度优先搜索通常是递归实现的，可以用栈代替递归。

10、对于0-1背包问题，贪心算法一定能得到最优解。

【答案】错误

【考试大纲知识点】动态规划（简单背包问题）

【分析】贪心无法得到0-1背包的最优解。这是因为一些闲置空间降低了整体价值。

3、编程题（每题25分，共50分）

问题编号

1

2

回答

1. 计算分数

问题描述

小杨想要计算一个由m个小写字母组成的字符串的分数。

小杨建立了一个包含n个正整数的评分序列A=[a1,a2,a3.an]。如果字符串的一个子串由k(1kn)个abc首尾相连组成，则可以得到分数ak，并且字符串中包含的字符不能重复计算。整个字符串的得分是得分子字符串的总和。

例如，假设n=3，则字符串dabcabcabcabzabc所有可能的评分方法如下：

• d+abc+abcabc+abz+abc 或d+abcabc+abc+abz+abc，其中d 和abz 不计分，总分为a1+a2+a1

• d+abc+abc+abc+abz+abc，总分为a1+a1+a1+a1

• d+abcabcabc+abz+abc，总分是a3+a1

小杨想知道给定字符串的最大总分是多少。

输入格式

第一行包含一个正整数n，表示评分序列A的长度。

第二行包含n个正整数，代表评分序列A。

第三行包含一个正整数m，表示字符串的长度。

第四行包含一个由m 个小写字母组成的字符串。

输出格式

输出一个整数，表示给定字符串的最大总分。

样品1

示例说明

最佳评分方法为d+abc+abc+abc+abz，总分为a1+a1+a1，共9分。

数据范围

对于所有数据，保证1n20、1m105、1a11000。

【标题的主要思想】

给定一个字符串m，将其与abc 字符串进行匹配。连续abc连接的次数会有不同的分数。求字符串m 的最大分数。

【考试大纲知识点】

一维动态规划

【解决问题思路】

20点思考。考虑到ai=ai+1，此时单独abc就被认为是最大的，答案就是A[1]*abc的个数。

创意满分

状态表示：DP[i]表示由前i个字符组成的最大分数。

状态转移方程：

对于第i个字符，有两种情况：不作为答案的一部分。 作为abc的一部分贡献答案；

对于:DP[i]=DP[i-1]（也可以理解为将i-1的答案扩展到i），这就保证了答案是DP[m]

对于:的前i个字符，最后一个位置是“abc”，可以考虑使用j个连续的abc连接来更新答案；

此时i-3*j+1~i的范围是j个连续的abc，成本为A[j]

转移方程为：

DP[i]=DP[i-3*j]+A[j]

和 构成答案的所有解决方案

有：个DP[i]=max(DP[i-1],max(DP[i-3*j]+A[j]); i-3*j+1=1

参考流程

2、二叉树

问题描述

小杨有一棵包含n个节点的二叉树，根节点数为1。这棵二叉树中的任何节点要么是白的，要么是黑的。之后，小杨会对这棵二叉树进行q操作。小杨每次都会选择一个节点，并将以此节点为根的子树中所有节点的颜色反转，即黑色变成白色，白色变成黑色。

小杨想知道所有q操作完成后每个节点的颜色。

输入格式

第一行包含一个正整数n，表示二叉树的节点数。

第二行包含n-1个正整数，第i（1-in-1）个数字表示编号为i+1的节点的父节点编号。数据保证是二叉树。

第三行是长度为n的01字符串。如果从左到右第i(1in)位为0，则表示编号为i的节点的颜色为白色，否则为黑色。第四行是正整数q，表示操作次数

接下来的q行每行包含一个正整数a_i（1ain），表示第i次操作中选择的节点号。

输出格式

一行输出长度为n的01字符串，表示所有操作完成后每个节点的颜色。如果从左到右第i(1in)位为0，则表示编号为i的节点的颜色为白色，否则为黑色。

样品1

示例说明

第一次运行后，节点颜色为：011010

第二次操作后，节点颜色为：000000

第三次操作后，节点颜色为：010000

数据范围

对于所有数据，保证1 n,q 105。

【标题的主要思想】

给定一个有向树和q 操作，每个操作都会反转x 所在子树中每个节点的颜色。求q运算后每个节点的颜色。数据范围为105。

【考试大纲知识点】

树上的DFS，树上的DP

【解决问题思路】

一个比较简单的想法就是建一棵树。每次操作都会执行DFS，处理操作的结果，最终输出每个节点的颜色。极端情况下，如果每个操作都遍历整棵树，复杂度为O(nq)，只能求解。 40%的数据。

考虑到程序只需要最终结果，不需要完全得到中间结果。反转运算的周期为2，具有奇偶校验。因此，每次操作X时，都会标记X的位置，表示会影响X下面的位置。 的每个节点都会翻转一次。当所有操作都被标记后，就执行DFS。从root=1开始，统计到达每个节点颜色时标记cnt的数量。这仅需要O(n+q) 复杂度。

参考流程

用户评论

安之若素

终于找到GESP C++ 6级真题分析了！这个复习资料简直是救命稻草！

    有5位网友表示赞同！

话扎心

GESP 第六级认证真题分析C++，简直是刷题神器！

    有7位网友表示赞同！

青山暮雪

看了GESP C++ 6级真题分析，感觉考试内容并不难，但我还是会认真复习。

    有20位网友表示赞同！

呆萌

这个GESP 第六级认证真题分析C++资料质量不错，推荐给所有要考C++ 6级的同学！

    有9位网友表示赞同！

毒舌妖后

GESP C++ 6级认证真题分析，帮助我更好地了解考试方向！

    有15位网友表示赞同！

岁岁年年

GESP 第六级认证真题分析C++，希望能让我顺利通过考试！

    有17位网友表示赞同！

孤独症

感觉GESP 第六级认证真题分析C++对考试内容分析得很透彻！

    有19位网友表示赞同！

烟花巷陌

GESP 第六级认证真题分析C++太棒了！

    有11位网友表示赞同！

眉黛如画

GESP C++ 6级真题分析，让我对考试更有信心！

    有17位网友表示赞同！

秒淘你心窝

感谢GESP 第六级认证真题分析C++，让我更好地备考！

    有9位网友表示赞同！

淡抹烟熏妆丶

GESP C++ 6级真题分析，真是太实用了！

    有6位网友表示赞同！

桃洛憬

GESP 第六级认证真题分析C++，强烈推荐！

    有7位网友表示赞同！

服从

GESP C++ 6级真题分析，我感觉这次考试稳了！

    有18位网友表示赞同！

掉眼泪

有了GESP 第六级认证真题分析C++，复习更有针对性！

    有11位网友表示赞同！

汐颜兮梦ヘ

GESP 第六级认证真题分析C++，真是考前必备！

    有14位网友表示赞同！

败类

GESP C++ 6级真题分析，让我对考试内容有了更深的理解！

    有13位网友表示赞同！

∞◆暯小萱◆

这个GESP 第六级认证真题分析C++资料，简直是神级资料！

    有7位网友表示赞同！

人心叵测i

GESP C++ 6级真题分析，对考试内容的分析很到位！

    有13位网友表示赞同！

温柔腔

有了GESP 第六级认证真题分析C++，我相信我可以顺利通过考试！

    有7位网友表示赞同！

蹂躏少女

GESP 第六级认证真题分析C++，真是太赞了！

    有16位网友表示赞同！