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

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

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

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

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

1、⼩杨要从A城到B城，⼜想顺路游览⼀番。他有两个选项：1、坐⾼铁路到C城游览，再坐⾼铁或飞机到B城；2、坐船到D城游览，再坐船、⾼铁或飞机到B城。请问⼩杨从A城到B城共有⼏种交通⽅案可以选择？（  ）。

A. 2

B. 3

C. 5

D. 6

2、以下哪个函数声明是符合语法的 ，且在调⽤时可以将⼆维数组的名字作为实际参数传递给形式参数 a ？  (    )  。

  A.  void QuickSort(int a[][10], int n);

  B.  void QuickSort(int a[5][], int m);

  C.  void QuickSort(int a[][], int n, int m);

  D.  void QuickSort(int ** a, int n, int m);

3、下⾯有关C++类和对象的说法 ，错误的是（  ）。

  A. 对象的⽣命周期开始时 ，会执⾏构造函数。

  B. 对象的⽣命周期结束时 ，会执⾏析构函数。

  C. 类的析构函数可以为虚函数。

  D. 类的构造函数可以为虚函数。

4、使⽤邻接矩阵表达 n 个顶点的有向图 ，则该矩阵的⼤⼩为（  ）。

A. n× (n+1 ) 

B. n×n

C. n× (n -1 )

D. n× (n - 1 )/2

5、5 位同学排队，其中⼀位同学不能排在第⼀，则共有多少种可能的排队⽅式？（  ）。

A.  5

B.  24

C.  96

D.  120

6、⼀个⽆向图包含 n 个顶点 ，则其最⼩⽣成树包含多少条边？（  ）。

A. n - 1

B. n

C. n + 1

D. 最⼩⽣成树可能不存在。

7、已知三个 double 类型的变量a、b和theta分别表⽰⼀个三角形的两条边长及⼆者的夹角（弧度），则下列哪个表达式可以计算这个三角形的⾯积？（  ）。

A.  a * b * s in(theta) / 2

B.  (a + b) * s in(theta) / 20 

C.  a * b * cos(theta) / 2

D.  sqrt(a * a + b * b - 2 * a * b * cos(theta))

8、对有 n 个元素的⼆叉排序树进⾏中序遍历，其时间复杂度是（  ）。

  A. O(1)

  B. O(log(n)) 

  C. O(n)

  D. O(n²)

9、假设输⼊参数m和n满⾜m≤n，则下⾯程序的最差情况的时间复杂度为（  ）。

A. O(log(n))

B. O(n)

C. O(n × m)

D. O(m × log(n)

10、下⾯程序的时间复杂度为（  ）。

A. O(n)

B. O(an)

C. O(log(n))

D. O(log(n) × a)

11、下⾯程序的时间复杂度为（  ）。

  A. O(2n)

  B. O(2m × (n - m))

  C. O(c(n, m))

  D. O(m × (n - m))

【答案】D

【解析】本题代码是在计算C[n][m],使用了递归的写法并加上了记忆化搜索，可以通过画图来看所有被访问到的二维数组个数，以n=6，m=2为例，

可以发现访问的元素个数为n*m-m*m，本题选D。

12、下⾯的程序使⽤出边的邻接表表达有向图，则下列选项中哪个是它表达的图？（  ）。

第 13 题  下⾯程序的输出为（  ）。

A. 12

B. 18

C. 36

D. 42

14、下⾯程序的输出为（  ）。

A. 3

B. 6

C. 11

D. 22

15、下⾯的程序中 ，⼆维数组 h 和 v 分别代表如下图所⽰的⽹格中的⽔平边的时间消耗和垂直边的时间消耗。 程序使⽤动态规划计算从左下角到右上角的最⼩时间消耗 ，则横线处应该填写下列哪个选项的代码？（  ）。

A.dis[i][j] = min(dis[i - 1][j] + v[i - 1][j], dis[i][j - 1] + h[i][j - 1]);

B.dis[i][j] = min(dis[i - 1][j] + h[i - 1][j], dis[i][j - 1] + v[i][j - 1]);

C.dis[i + 1][j + 1] = min(dis[i][j + 1] + v[i][j + 1], dis[i + 1][j] + h[i + 1][j]);

D.dis[i + 1][j + 1] = min(dis[i][j + 1] + h[i][j + 1], dis[i + 1][j] + v[i + 1][j]);

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

1、C++语⾔⾮常强⼤ ，可以⽤来求解⽅程的解 。例如 ，如果变量 x 为 double 类型的变量，则执⾏语句 x * 2 - 4 = 0; 后，变量 x 的值会变为 2.0。

2、⼀个袋⼦中有3个完全相同的红⾊⼩球、2个完全相同的蓝⾊⼩球 。每次从中取出1个 ，且不放回袋⼦ ，这样 进⾏3次后 ，将取出的⼩球依次排列 ，则可能的颜⾊顺序有7种。

3、杨辉三角 ，是⼆项式系数的⼀种三角形排列 ，在中国南宋数学家杨辉1261年所著的《详解九章算法》⼀书中出现 ，是中国数学史上的⼀项伟⼤成就。

4、N个顶点的有向完全图（不带⾃环）有N × (N-1)/2条边。

5、如果待查找的元素确定 ，只要哈希表的⼤⼩不⼩于查找元素的个数 ，就⼀定存在不会产⽣冲突的哈希函数。

6、动态规划算法的时间复杂度⼀般为：必要状态的数量 ，乘以计算⼀次状态转移⽅程的时间复杂度。

7、已知 int 类型的变量 a  、 b 和 h 中分别存储着⼀个梯形的顶边长、底边长和⾼ ，则这个梯形的⾯积可以通 过表达式 (a + b) * h / 2 求得。

8、判断图是否连通只能⽤⼴度优先搜索算法实现。

9、在N个元素的⼆叉排序树中查找⼀个元素 ，最好情况的时间复杂度是0(logN)。

10、给定 double 类型的变量x，且其值⼤于等于 ，我们可以通过⼆分法求出的 近似值。

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

1、奖品分配

问题描述

班上有N名同学 ，学号从0到N-1。有M种奖品要分给这些同学，其中，第i种奖品总共有ai个  (i = 0,1,...,M -1)。巧合的是，奖品的数量不多不少，每位同学都可以恰好分到⼀个奖品，且最后剩余的奖品不超过1个（即：N ≤ a₀ +a₁+....+a_M-1 ≤ N+1）。

现在，请你求出每个班级礼物分配的⽅案数，所谓⽅案，指的是为每位同学都分配⼀个种类的奖品。只要有⼀位同学获得了不同种类的奖品，即视为不同的⽅案。⽅便起见，你只需要输出⽅案数对109+7取模后的结果即可。

共有T个班级都⾯临着奖品分配的问题，你需要依次为他们解答。

输入描述

第一行一个整数 T，表示班级数量。

接下来工行，每行若千用单个空格隔开的正整数。首先是两个正整数 N,M，接着是 M 个正整数a₀ ,a₁,....,a_M-1 ,保证N ≤ a₀ +a₁+....+a_M-1 ≤ N+1。

输出描述

输出T行，每行一个整数，表示该班级分配奖品的方案数对 109+ 7取模的结果。

特别提醒 

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

样例输入1

样例输出1

样例解释1

对于第1个班级，学号为0,1,2的同学可以依次分别获得奖品 0,1,1,也可以依次分别获得奖品1,0,1,也可以依次分别获得奖品1,1,0,因此共有3种方案。

对于第2个班级，学号为0,1,2 的同学可以依次分别获得奖品0,1,1,也可以依次分别获得奖品 1,0,1,也可以依次分别获得奖品1,1,0,可以依次分别获得奖品1,1,1,因此共有4种方案。

对于第3个班级，可以把编号为1的奖品分配给5名同学中的任意一名，共有5种方案；再把编号为2的奖品分配给剩余4名同学中的任意一名，共有4种方案；最后给剩余3名同学自然获得0号奖品。因此，方案数为5x4=20。

样例输入2

样例输出2

数据规模

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

对于另外30%的测试点，保证 M =2。

对于所有测试点，保证 N ≤ 1,000; 保证T ≤ 1,000;保证 M ≤ 1,001。

【解题思路】首先考虑奖品总个数=人数的情况，设奖品数分别是a₀ ,a₁,....,a_M-1,则总方案数为，可以提前预处理排列数C数组的值，方便计算，接着考虑奖品总个数=人数+1的情况，我们可以额外虚设1个人，依然按照奖品总个人=人数的情况计算，并输出方案数，具体的方案为不考虑虚设人拿的奖品种类，把前n个人拿的奖品种类作为方案，考虑为什么这样是对的，对于两种方案，如果虚设人拿的奖品编号相同，那么说明前面n个人拿的奖品编号必然有不同，那么方案是不同的，如果虚设人拿的奖品编号不同，因为总共只有n+1个奖品，所以前面n个人拿的奖品编号必然也不同，方案也是不同的，说明我们在虚设人的情况下得到的任意两个方案都不会重复，所以直接按照人数=奖品总个数计算即可。

【参考程序】

2、大量的工作沟通 

问题描述

某公司有N名员工，编号从0至 N-1。其中，除了0 号员是老板，其余每名员工都有一个直接领导。我们假设编号为i的员工的直接领导是 fi。

该公司有严格的管理制度，每位员工只能受到本人或直接领导或间接领导的管理。具体来说，规定员工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

样例解释1

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

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

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

样例输入2

样例输出2

数据规模

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

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

对于所有测试点，保证3≤ N ≤ 10⁵;保证Q ≤ 100，保证m ≤ 10⁴

【解题思路】容易想到，能够管理员工a₁ ,a₂,...,a_m的人为lca(a₁ ,a₂,...,a_m)以及该lca的祖先节点，题目还要求编号最大，也就是从根到该lca路径上所有点的编号最大值，这个可以提前预处理，设mxID[u]表示从根到u路径上所有节点编号的最大值，对于每组询问，首先求出所有参与的员工的lca，接着输出mxID[lca]即可，求lca比较常用的有倍增法或树链剖分等。

【参考程序】

【联系我们】

1. GESP微信：关注“CCF GESP”公众号，将问题以文字方式留言即可得到回复。

2. GESP邮箱：[email protected]

注：请在邮件中详细描述咨询的问题并留下考生的联系方式及姓名、身份证号，以便及时有效处理。

3. GESP电话：0512-67656856

咨询时间：周一至周五(法定节假日除外）: 上午 8:30-12:00；下午 13:00-17:30

GESP第五期认证报名已启动，扫描下方二维码，关注GESP公众号即可报名

点击“阅读原文”，进入官网。