GESP第九次认证真题解析|C++六级真题回顾

一、单选题(每题2分,共30分)

第1题  在面向对象编程中 ，类是一种重要的概念 。下面关于类的描述中 ，不正确的是（  ）。

A.类是一个抽象的概念 ，用于描述具有相同属性和行为的对象集合。

B.类可以包含属性和方法 ，属性用于描述对象的状态 ，方法用于描述对象的行为。

C.类可以被实例化 ，生成具体的对象。

D.类一旦定义后 ，其属性和方法不能被修改或扩展。

答案：D

考纲知识点：面向对象的思想

解析：在面向对象编程领域，类的核心特征主要包括封装、继承与多态性。继承特性指的是一个类能够获取另一个类的属性与方法，被获取的类通常被称为基类或父类，而获取这些属性与方法的类则被称为派生类或子类。子类能够利用父类的代码，并且可以在其基础上扩展新的属性和方法，或者对父类的方法进行重写。

第2题  哈夫曼编码是一种数据压缩算法 。以下关于哈夫曼编码的描述中 ，不正确的是（  ）。

A.哈夫曼编码是一种变长编码 ，频率高的字符使用较短的编码 ，频率低的字符使用较长的编码。

B.在构造哈夫曼树时 ，频率越低的字符离根节点越近 ，频率越高的字符离根节点越远。

C.哈夫曼编码的生成过程基于贪心算法 ，每次选择频率最低的两个节点进行合并。

D.哈夫曼编码是一种前缀编码 ，任何一个字符的编码都不会是另一个字符编码的前缀， 因此可以实现唯一解 码。

答案：B

考纲知识点：哈夫曼树

解析：在构建哈夫曼编码的过程中，较低频率的字符会被更早地合并，从而位于树结构的较深层级，即距离根节点较远；相对地，较高频率的字符则会在较晚的阶段被合并，因此它们处于树结构的较浅层级，更接近根节点。

第3题  以下代码实现了树的哪种遍历方式？

A.前序遍历

B.中序遍历

C.后序遍历

D.层次遍历

答案：A

考纲知识点：二叉树知识

分析：通过分析代码，可以发现其首先访问根节点，随后递归地访问左子树，最终递归地访问右子树，这一过程体现了先序遍历的顺序。

第4题  以下关于完全二叉树的代码描述 ，正确的是（  ）。

B.该代码用于判断一棵树是否为完全二叉树

C.该代码用于判断一棵树是否为二叉搜索树

D.该代码用于计算树的高度

答案：B

考纲知识点：二叉树知识

分析：分析代码，可以发现代码采用了queue队列结构，该结构通常用于实现广度优先搜索算法。程序首先对根节点进行访问，随后依次访问左子树和右子树。函数的返回类型为布尔值，即true或false，基于此可以排除选项D。二叉搜索树的特性与节点上的权值相关，在函数中并未设置记录节点数值的变量，因此选项C亦被排除。至于满二叉树，其定义要求除叶子节点外，每个节点都必须拥有左右两个子节点，但当前代码并未反映出这一特性，故选项A也不符合。综上所述，正确答案应为选项B。

第5题  以下代码实现了⼆叉排序树的哪种操作？

A.查找

B.插入

C.删除

C遍历

答案：B

考纲知识点：二叉树知识

解析：分析代码，root为空，会新建一个结点；root不为空，会根据val的大小，插入到左子树或者右子树，因此是插入操作，选B。

第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

考纲知识点：哈夫曼树

分析：通过构建哈夫曼树，依据字符集出现频率的不同赋予相应的权重，权重较低的节点一般位于左侧，并将其对应边的编码定为0，而右侧则为1。根据此方法生成的字符集哈夫曼编码，选择方案B。

第7题 关于动态规划的描述 ，正确的是（  ）。

A.动态规划算法的时间复杂度总是低于贪心算法。

B.动态规划要求问题必须具有最优子结构和重叠子问题两个性质。

C.动态规划通过递归实现时不需要存储中间结果。

D.动态规划的核心思想是将问题分解为互不重叠的子问题。

答案：B

考纲知识点：动态规划

解析：动态规划的基础知识，动态规划必须有最优⼦结构和重叠⼦问题两个性质。

第8题  以下代码中 ，类的构造函数被调用了（  ）次。

A. 1

B. 2

C. 3

D. 0

答案：A

考纲知识点：面向对象

解析：MyClass obj2 = obj1; 这行代码运用了拷贝初始化来创建对象，调用的是拷贝构造函数，而非重写默认构造函数。

第9题  以下代码实现了循环队列的哪种操作？

A.入队

B.出队

C.查看队首元素

D 判断队列是否为空

答案：A

考纲知识点：队列知识

解析：分析第13和14行代码，rear增加，是队尾增加新元素，选A。

第10题  以下代码实现了二叉树的深度优先搜索（DFS） ，并统计叶子结点的数量 ，则横线上应填写（ ）。

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

考纲知识点：二叉树知识

分析：参照第15行代码，选择A项。第15行代码表明若存在右子节点，则将其加入队列；紧接着的下一行代码则意味着若存在左子节点，亦应将其加入队列。

第11题  以下代码实现了二叉树的广度优先搜索（BFS） ，并查找特定值的节点 ，则横线上应填写（ ）。

D.

答案：A

考纲知识点：二叉树知识

解析：根据题意，左右子节点若是存在，则先入队，再判断值是否为答案，选A。

第12题  以下代码用于⽣成 n位格雷编码 。横线上应填写（ ）。

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

考纲知识点：格雷编码

解析：在一组数字的编码过程中，若任意两个相邻的代码仅有一位二进制数存在差异，则该编码被定义为格雷码。编码的生成步骤如下所述：首先，生成两个基本字符串，即“0”和“1”。其次，在这两个字符串的基础上，于每个字符串的前端分别添加“0”和“1”。通过在第八行的循环中添加“0”，以及后续循环中添加“1”，从而完成了格雷码的生成过程。因此，正确选项为A。

第13题  以下代码实现了0/1背包问题的动态规划解法 。假设物品重量为 weights[]，价值为values[]，背包容 量为 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

考纲知识点：动态规划知识

解析：动态规划中的背包问题。else里完成的是当前物品能装下，能装下也分2种选择：装的时候和不装的时候哪种情况值最大。dp[i-1][j]表示不装该物品，dp[i-1][j - weights[i-1]] + values[i-1]表示装该物品，求最大值即可。选B。

第14题  以下代码用于检查字符串中的括号是否匹配 ，横线上应填写（ ）。

A.  true  

B.  false

C.  st.empty()

D.  !st.empty()

答案：C

考纲知识点：栈知识

分析：根据函数的定义，横线处应当返回“true”，但选项A并不正确。例如，字符串“(()”未能得到正确的匹配结果，原因是栈中尚有剩余元素。只有当栈为空时，才能表明匹配成功。因此，正确答案应为C。

第15题  关于下面代码 ，说法错误的是（  ）。

A.语句Shape* shapePtr = &circle; 和shapePtr = &rectangle; 出现编译错误

B. Shape 为基类，Circle和Rectangle是派生类

C.通过继承，Circle和Rectangle复用了Shape的属性和方法 ，并扩展了新的功能

D.Circle 和 Rectangle通过重写（override）基类的虚函数area和基类指针 ，实现了运行时多态

答案：A

考纲知识点：面向对象知识

解析：A选项中的2个赋值不会出现编译错误。Circle类和Rectangle类都继承自Shape类，基于面向对象编程中的多态特性，派生类对象的指针或引用可以转换为基类对象的指针或引用，这种转换是安全的。

二、判断题 (每题2分, 共20分)

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

答案：正确

考纲知识点：哈夫曼树

解析：构建哈夫曼树时，每次合并的都是权值最小的2个节点，这样最终树的带权路径长度最小。

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

答案：错误

考纲知识点：格雷码知识

解析：在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码。

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

答案：错误

考纲知识点：栈知识

解析：深搜中，通常使用栈实现“后进先出”访问。

第4题  以下代码实现的是⼆叉树的中序遍历：

答案：正确

考纲知识点：二叉树知识

解析：中序遍历是：左根右。该代码先访问左子树，再访问根节点，最后访问右子树。

第5题 C++支持构造函数重载 ，但默认无参数的构造函数只能有一个。

答案：正确

考纲知识点：面向对象知识

解析：默认⽆参数的构造函数只能有⼀个。

第6题 二叉排序树（BST） 中 ，若某节点的左子树为空 ，则该节点一定是树中的最小值节点。

答案：错误

考纲知识点：二叉排序树知识

解析：例如，右子树中，有个节点左子树为空，该节点不是树中最小值节点。

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

答案：正确

考纲知识点：动态规划

解析：6可以由1 1 4、3 3构成，最小需要2枚3的硬币。

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

答案：正确

考纲知识点：面向对象知识

解析：在面向对象编程里，封装就是把数据（属性）和操作这些数据的方法（行为）捆绑到一个单元（类）中，同时对外部隐藏对象的内部实现细节，只提供公共的接口来与对象进行交互。

第9题  以下代码创建的树是一棵完全二叉树：

答案：正确

考纲知识点：二叉树知识

解析：前2层是满二叉树，最后1层节点从左到右连续排列，无间隔。

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

答案：正确

考纲知识点：数据结构知识

解析：栈和队列均可以⽤双向链表实现，栈的插入和删除只在栈顶，队列的插入在队首，删除在队尾，只需要1次操作，时间复杂度是O（1）。

三、编程题 (每题25分,共50分)

3.1    编程题1

时间限制：1.0 s

内存限制：512.0 MB

3.1.1    树上漫步

3.1.2    题目描述

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

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

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

3.1.3    输入格式

第一行，一个正整数n。

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

3.1.4    输出格式

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

3.1.5    样例

3.1.5.1    输入样例1

3.1.5.2    输出样例1

3.1.5.3    输入样例2

3.1.5.4    输出样例2

3.1.6    数据范围

对于40%的测试点 ，保证 1≤ n ≤10³。

对于所有测试点 ，保证 1≤ n ≤2 × 10⁵。

题目大意：给定一棵树，对于每个节点，要求该节点走偶数步最多能走到多少个节点。

考纲知识点：深搜、树知识

解析：要求两个点偶数步相互到达，例如点a偶数步到达点b，点b也能偶数步到达点a。获得偶数的方法只能是：偶数+偶数；奇数+奇数。我们以任意一点为根做一次dfs，求出每个点的深度，深度为奇数的点到深度为奇数的任意点，要走偶数步，偶数同理。求这2个集合即可。

3.1.7    参考程序

3.2    编程题2

时间限制：1.0 s

内存限制：512.0 MB

3.2.8    环线

3.2.9    题目描述

小A喜欢坐地铁。地铁环线有n个车站，依次以1 , 2,..., n 标号。车站i（1≤ i < n） 的下一个车站是车站 i + 1 。

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

小A会从某个车站出发，乘坐地铁环线到某个车站结束行程，这意味着小A⾄少会经过一个车站 。小A不会经过一个车站多次。当小A乘坐地铁环线经过车站i时 ，小A会获得a_i点快乐值。请你安排小A的行程，选择出发车站与结束车站，使得获得的快乐值总和最⼤ 。

3.2.10    输入格式

第一行，一个正整数n，表⽰车站的数量。

第⼆行，n个整数a₁, a₂ , ...,a_n，分别表示经过每个车站时获得的快乐值。

3.2.11    输出格式

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

3.2.12    样例

3.2.12.5    输入样例1

3.2.12.6    输出样例1

3.2.12.7    输入样例2

3.2.12.8    输出样例2

3.2.13    数据范围

对于20%的测试点 ，保证 1≤ n ≤200。

对于40%的测试点 ，保证 1≤ n ≤2000。

对于所有测试点 ，保证 1≤ n ≤2 × 10⁵，-10⁹≤ a_i≤10⁹。

题目大意：n个点构成一个环，每个点有一个权值，权值可能为正数，也可能为负数。要求取出其中连续的一段，长度≥1，求获得的最大权值和是多少。

考纲知识点：双指针、动态规划、前缀和知识

解析：首先将环破环成链，然后求前缀和。注意有可能所有点权值都是负数，所以ans初始化成最小值。其次尝试每个点i出发，求得区间最大子段和，可以用同向的双指针做法求得区间最大子段和。

3.2.14    参考程序

策划：GESP技术委员会副主席 刘晓庆

技术支持：GESP技术委员会委员 赵晨泽