2023年12月GESP认证C++六级试卷解析

今天为大家带来的是2023年12月认证C++ 六级真题解析回顾。

CCF编程能力等级认证，英文名Grade Examination of Software Programming（以下简称GESP），由中国计算机学会发起并主办，是为青少年计算机和编程学习者提供学业能力验证的平台。GESP覆盖中小学全学段，符合条件的青少年均可参加认证。GESP旨在提升青少年计算机和编程教育水平，推广和普及青少年计算机和编程教育。

GESP考察语言为图形化编程、Python编程及C++编程，主要考察学生掌握相关编程知识和操作能力，熟悉编程各项基础知识和理论框架，通过设定不同等级的考试目标，让学生具备编程从简单的程序到复杂程序设计的编程能力，为后期专业化编程学习打下良好基础。

本次为大家带来的是2023年12月份C++ 六级认证真题解析。

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

1、关于C++类和对象的说法，错误的是( )。

A. 在C++中，⼀切皆对象，即便是字⾯量如整数5等也是对象

B. 在C++中，可以⾃定义新的类，并实例化为新的对象

C. 在C++中，内置函数和⾃定义函数，都是类或者对象

D. 在C++中，可以在⾃定义函数中嵌套定义新的函数

【答案】D

【考纲知识点】语法知识点

【解析】自定义函数中不能嵌套定义新函数。

2、有关下⾯C++代码的说法，错误的是( )。

A. C++中类内部可以嵌套定义类

B. 在类中定义的类被称为内部类，定义类的类被称为外部类

C. 内部类可以随便访问，不需要通过外部类来访问

D. 代码中 Point 被称为内部类，可以通过外部类Rectangle来访问Rectangle::Point

【答案】C

【考纲知识点】语法知识点

【解析】内部类是需要通过外部类访问的。

3、有关下面C++代码的说法，正确的是( )。

A. 第14⾏代码错误，第15⾏正确

B. 第15⾏代码错误，第14⾏代码正确

C. 第14、15两⾏代码都正确

D. 第6⾏代码可修改为 objCounter += 1

【答案】C

【考纲知识点】语法知识点

【解析】objCounter是静态成员，2种方式都可以访问。

4、有关下⾯C++代码的说法，错误的是( )。

A. 上列C++代码适⽤于构造各种⼆叉树

B. 代码 struct BiNode ⽤于构造⼆叉树的节点

C. 代码 BiTree(){root=Creat();} ⽤于构造⼆叉树

D. 析构函数不可以省略

【答案】D

【考纲知识点】语法知识点

【解析】析构函数可以省略。系统可以默认一个析构函数。

5、基于第4题的定义，有关下⾯C++代码的说法正确的是（）。

A. 代码中Order( )函数是中序遍历⼆叉树的⽅法

B. 代码中Order( )先访问根节点，然后对左⼦树进⾏前序遍历，再对右⼦树前序遍历

C. 代码中Order( )先访问中序遍历左⼦树，然后访问根节点，最后则是中序遍历右⼦树

D. 代码中Order( )先后序遍历左⼦树，然后后序遍历右⼦树，最后访问根节点

【答案】B

【考纲知识点】数据结构知识点

【解析】对二叉树的先序遍历，根左右。

6、有关下⾯C++代码的说法正确的是（）。

A. 上述代码构成单向链表

B. 上述代码构成双向链表

C. 上述代码构成循环链表

D. 上述代码构成指针链表

【答案】B

【考纲知识点】数据结构知识点

【解析】实现一个链表，指向前面和后面的元素。

7、对hello world使⽤霍夫曼编码（Huffman Coding），最少bit（⽐特）为（）。

A. 4

B. 32

C. 64

D. 88

【答案】B

【考纲知识点】数据结构知识点

【解析】赫夫曼编码。按照出现次数进行赫夫曼编码，如下图。共32bit。

8、下⾯的 fiboA() 和 fiboB() 两个函数分别实现斐波那契数列，该数列第1、第2项值为1，其余各项分别为前两项之和。下⾯有关说法错误的是（）。

A. fiboA() 采⽤递归⽅式实现斐波那契数列

B. fiboB() 采⽤动态规划算法实现斐波那契数列

C. 当N值较⼤时， fiboA() 存在⼤量重复计算

D. 由于 fiboA() 代码较短，其执⾏效率较⾼

【答案】D

【考纲知识点】算法知识点

【解析】fiboA函数会存在重复计算，执行效率不高。

9、有关下⾯C++代码不正确的说法是（）。

A. 该代码可⽤于求解⼆叉树的深度

B. 代码中函数Depth( ) 的参数T表⽰根节点，⾮根节点不可以作为参数

C. 代码中函数Depth( ) 采⽤了递归⽅法

D. 代码中函数Depth( ) 可⽤于求解各种形式的⼆叉树深度，要求该⼆叉树节点⾄少有left和right 属性

【答案】B

【考纲知识点】数据结构知识点

【解析】左右孩子也可以作为参数，不一定只有根节点。

10、下⾯有关树的存储，错误的是（）.

A. 完全⼆叉树可以⽤ list 存储

B. ⼀般⼆叉树都可以⽤ list 存储，空⼦树位置可以⽤ None 表⽰

C. 满⼆叉树可以⽤ list 存储

D. 树数据结构，都可以⽤ list 存储

【答案】D

【考纲知识点】数据结构知识点

【解析】完全二叉树和满二叉树的节点下标是连续的，其他类型的节点数不确定，下标不一定连续，就不宜用list存储。

11、构造⼆叉树 [1,2,3,null,4] （）。

A. 1(2()(4))(3)

B. 1(2(3)())(4)

C. (1,2(3),(4))

D. (1,(2)(3),(4))

【答案】A

【考纲知识点】数据结构知识点

【解析】构造二叉树，用括号表示法。1是根结点，其左右孩子为2，3，写成1(2)(3)。用同样的思路构建左子树和右子树，选A。

12、下⾯有关布尔类型的函数的说法，正确的是（）。

A. bool 类型函数只能返回0或者1两种值

B. bool 类型函数可以返回任何整数值

C. bool 类型函数必须有参数传递

D. bool 类型函数没有返回值

【答案】A

【考纲知识点】语言函数知识点

【解析】bool类型函数只能返回布尔类型，布尔值只有0或者1。

13、通讯卫星在通信⽹络系统中主要起到（）的作⽤。

A. 信息过滤

B. 信号中继

C. 避免攻击

D. 数据加密

【答案】B

【考纲知识点】计算机基础知识

【解析】本题考察计算机基础知识。通信卫星可以转发无线电信号，实现通信地球站间或地球站与航天器间的无线电通信，因此具有信号中继作用。选B。

14、⼩杨想编写⼀个判断任意输⼊的整数N是否为素数的程序，下⾯哪个⽅法不合适？ ( )

A. 埃⽒筛法

B. 线性筛法

C. ⼆分答案

D. 枚举法

【答案】C

【考纲知识点】数学知识

【解析】本题考察数学知识。线筛和埃筛都可以判断素数，枚举也可以，二分规模减半，不能合理判断。

15、内排序有不同的类别，下⾯哪种排序算法和冒泡排序是同⼀类？ ( )

A. 希尔排序

B. 快速排序

C. 堆排序

D. 插⼊排序

【答案】B

【考纲知识点】排序知识

【解析】冒泡排序和快速排序，都属于交换排序。

交换排序：冒泡排序、快速排序

选择排序：简单选择排序、堆排序

插入排序：直接插入排序、希尔排序

归并排序

基数排序

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

1、在⾯向对象中，⽅法在C++的class中表现为class内定义的函数。( )

【答案】正确

【考纲知识点】c++语言知识

【解析】方法在c++中也就是类内的函数。

2、C++类的定义中，可以没有构造函数，会给出默认的构造函数 ( )

【答案】正确

【考纲知识点】c++语言知识

【解析】构造函数没有，系统会给一个默认的构造函数。

3、如果某个C++对象（object）⽀持下标运算符（⽅括号运算符），则该对象在所对应class中以成员函数的形式进⾏了重载。( )

【答案】正确

【考纲知识点】c++语言知识

【解析】标准库类型vector和string都重载了下标运算符。

4、深度优先搜索（DFS，Depth First Search的简写）属于图算法，其过程是对每⼀个可能的分⽀路径深⼊到不能再深⼊为⽌，⽽且每个节点只能访问⼀次。( )

【答案】正确

【考纲知识点】算法知识

【解析】深搜就是“能深则深、不能深则退”。

5、哈夫曼编码（Huffman Coding）具有唯⼀性，因此有确定的压缩率。( )

【答案】错误

【考纲知识点】算法知识

【解析】哈夫曼编码确实是唯一的。但是，这并不意味着它总是有确定的压缩率。压缩率通常定义为压缩后数据大小与原始数据大小的比值。对于哈夫曼编码来说，压缩率会受到输入数据的特性（如字符频率分布）的影响。不同的输入数据，即使使用相同的哈夫曼编码算法，也可能得到不同的压缩率。

6、在下⾯C++代码中，由于删除了变量ptr，因此ptr 所对应的数据也随之删除，故第8⾏代码被执⾏时，将报错。 ( )

【答案】错误

【考纲知识点】语法知识

【解析】一个指针的指向对象已被删除，那么就成了悬空指针。指针本身仍然存在，但它的指向变得不确定，因为原来的内存已经被释放并可能被重新分配给其他用途。可能会导致程序崩溃，但是可能正常执行。

7、⼆叉搜索树查找的平均时间复杂度为。 ( )

【答案】正确

【考纲知识点】数据结构知识

【解析】若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。平均情况下是一分为二。

8、⼆叉搜索树可以是空树（没有任何节点）或者单节点树（只有⼀个节点），或者多节点。如果是多节点，则左节点的值⼩于⽗节点的值，右节点的值⼤于⽗节点的值，由此推理，右节点树的值都⼤于根节点的值，左节点树的值都⼩于根节点的值。 ( )

【答案】正确

【考纲知识点】数据结构知识

9、⼩杨想写⼀个程序来算出正整数N有多少个因数，经过思考他写出了⼀个重复没有超过N/2次的循环就能够算

出来了。 ( )

【答案】正确

【考纲知识点】算法知识

【解析】可以的。N 除了自身，只能有1个大于等于n/2的因子。

10、同样的整数序列分别保存在单链表和双向链中，这两种链表上的简单冒泡排序的复杂度相同。 ( )

【答案】正确

【考纲知识点】算法知识

【解析】都是相邻的数字交换。

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

1、闯关游戏

问题描述

你来到了⼀个闯关游戏。

这个游戏总共有N关，每关都有M个通道，你需要选择⼀个通道并通往后续关卡。其中，第i个通道可以让你前进a_i关，也就是说，如果你现在在第x关，那么选择第i个通道后，你将直接来到第x＋a_i关（特别地，如果x + a_i≥ N，那么你就通关了）。此外，当你顺利离开第S关时，你还将获得b_s分。

游戏开始时，你在第0关。请问，你通关时最多能获得多少总分？

输入描述

第⼀⾏两个整数 N, M ，分别表⽰关卡数量和每关的通道数量。

接下来⼀⾏ M 个⽤单个空格隔开的整数 a₀ , a₁, … ,a_M-1 。保证 1 ≤ a_i≤ N 。

接下来⼀⾏ N 个⽤单个空格隔开的整数b₀ , b₁, … ,b_N-1 。保证｜b_i｜≤ 10⁵ 。

输出描述

一行一个整数，表示你通关时最多能够获得的分数。

特别提醒

在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。

样例输入 1

样例输出1

样例解释1

你可以在第 0关选择第1个通道，获得 1分并来到第 3 关;随后再选择第 0个通道，获得 100 分并来到第 5关;最后任选一个通道，都可以获得 30 分并通关。如此，总得分为 1+ 100 + 30 = 131。

样例输入2

样例输出2

样例解释2

请注意，一些关卡的得分可能是负数。

数据规模

对于20%的测试点，保证 M = 1 。

对于40%的测试点，保证N ≤ 20 ；保证 M ≤ 2。

对于所有测试点，保证 N ≤ 104 ；保证 M ≤ 100。

【题目大意】从0关出发，每次都有m种选择，选的的第i个关卡，到达的下一个关卡是0+ mi。当关卡的总和大于等于N的时候，便停止游戏。注意，离开第i个关卡，可以获得关卡的分数。

【考纲知识点】循环知识，动态规划

【解题思路】可以考虑动态规划。每关都是一个阶段，每关增加的都是一个正数，关数增加是单向的。保存好某个阶段的状态，因为是离开才能获得分数，因此不能加上当前关卡的分数。可求出所有阶段的最值，因为可能存在某关是负值，要求出所有状态的最大值。

【参考程序】

2、工作沟通

问题描述

某公司有N名员⼯，编号从0⾄N - 1 。其中，除了0号员⼯是⽼板，其余每名员⼯都有⼀个直接领导。我们假设编号为i的员⼯的直接领导是f_i。

该公司有严格的管理制度，每位员⼯只能受到本⼈或本⼈直接领导或间接领导的管理。具体来说，规定员⼯x可以管理员⼯y，当且仅当x=y，或x = f_y，或x可以管理f_y。特别地，0号员⼯⽼板只能⾃我管理，⽆法由其他任何员⼯管理。现在，有⼀些同事要开展合作，他们希望找到⼀位同事来主持这场合作，这位同事必须能够管理参与合作的所有同事。如果有多名满⾜这⼀条件的员⼯，他们希望找到编号最⼤的员⼯。你能帮帮他们吗？

输入描述

第⼀⾏⼀个整数N，表⽰员⼯的数量。

第⼆⾏N-1个⽤空格隔开的正整数，依次为f₁, f₂ ，...， f_N-1。

第三⾏⼀个整数Q ，表⽰共有Q 场合作需要安排。

接下来Q ⾏，每⾏描述⼀场合作：开头是⼀个整数 m（2 ≤ m ≤ N），表⽰参与本次合作的员⼯数量；接着是m个整数，依次表⽰参与本次合作的员⼯编号（保证编号合法且不重复）。

保证公司结构合法，即不存在任意⼀名员⼯，其本⼈是⾃⼰的直接或间接领导。

输出描述

输出Q⾏，每⾏⼀个整数，依次为每场合作的主持⼈选。

特别提醒

在常规程序中，输⼊、输出时提供提⽰是好习惯。但在本场考试中，由于系统限定，请不要在输⼊、输出中附带任何提⽰信息。

样例输入 1

样例输出 1

样例解释

对于第一场合作，员工3，4 有共同领导2，可以主持合作。

对于第二场合作，员工2本人即可以管理所有参与者。

对于第三场合作，只有0号老板才能管理所有员工。

样例输入 2

样例输出 2

数据规模

对于50%的测试点，保证N ≤ 50。

对于所有测试点，保证 3 ≤ N ≤ 300 ；Q ≤ 100。

【题目大意】0号是老板，一个人可以管理自己，管理直接下属，管理下属的下属。可以根据关系建立起树结构。现在要求有m个人自己组织会议，要找一个人主持会议。如果m个人中能主持就从m个人中选，不能就找上级领导，有多个选择，就求出最大的编号。注意，参会和主持的角色不一样。

【考纲知识点】循环知识，树结构，深搜，有根树

【解题思路】首先要建立树结构，根据父子关系，求出节点的结构，并求出对应的层数。针对每次查询，先看一下m个人中，层数最低的能不能主持会议，不能就从上级中选取，结果最小就是0号来主持。注意，要编号最大的，因此在筛选的时候从大到小去筛选。根据层中的第i个节点去判断能否访问到m中的每个孩子，如果是，那就可以主持。假设3和1都符合，也在同一层，但是倒序查找，找到3就退出了。符合最终答案。

【参考程序】