真题解析/GESP12月认证C++六级真题回顾

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

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

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

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

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

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

【答案】D

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

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

1. 有关下⾯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

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

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

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

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

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

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

4. 代码中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。

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

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

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

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

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

【答案】D

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

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

1. 有关下⾯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 ≤ 10⁴；保证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就退出了。符合最终答案。

【参考程序】