GESP第十次认证真题解析|C++八级真题回顾

C++ 八级

2025年06月

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

第1题 一间的机房要安排6名同学进行上机考试，座位共2行3列。考虑到在座位上很容易看到同一行的左右两侧的屏幕，安排中间一列的同学做A卷，左右两列的同学做B卷。请问共有多少种排座位 的方案？（）。

A.720

B.90

C.48

D.15

答案：A

考纲知识点：排列组合

解析：6位同学安排到6个座位上，共6!=720种方案。其他条件均为多余条件，并不能改变6位同学安排到6个座位上的要求。

第2题  又到了毕业季，学长学姐们都在开心地拍毕业照。现在有3位学长、3位学姐希望排成一排拍照，要求男生不相邻、女生不相邻。请问共有多少种拍照方案？（ ）。

A. 720

B.72

C.36

D.2

答案：B

考纲知识点：排列组合

解析：将男生和女生内部进行全排列，每个共A(3,3)=6种

交替排列的方式有：

男-女-男-女-男-女（首位为男生）；

女-男-女-男-女-男（首位为女生）。

共两种,因此总方案为：6*6*2=72种

第3题 下列关于C++类和对象的说法，错误的是（ ）。

A.通过语句const int x = 5; 定义了一个对象x。

B.通过语句std::string t = "12345"; 定义了一个对象t。

C.通过语句void (*fp)() = NULL; 定义了一个对象fp。

D.通过语句class MyClass; 定义了一个类MyClass。

答案：D

考纲知识点：类

解析：在C++中，class MyClass; 这种写法并不是完整定义一个类，而是对类MyClass进行前向声明。

第4题 关于生成树的说法，错误的是（ ）。

A.一个无向连通图，一定有生成树。

B.n个顶点的无向图，其生成树要么不存在，要么一定包含n-1条边。

C.n个顶点、n-1条边的无向图，不可能有多颗生成树。

D.n个顶点、n-1条边的无向图，它本身就是自己的生成树。

答案：D

考纲知识点：树与图基础

解析：如果不联通,那么就是森林,就无法构成生成树

第5题 一对夫妻生男生女的概率相同。这对夫妻希望儿女双全。请问这对夫妻生下两个孩子时，实现儿女双全的概率是多少？（）。

A.2/3

B.1/3

C.1/2

D.1/4

答案：C

考纲知识点：数学期望

解析：

（男男）,（男女）（女男）（女女）满足"儿女双全"（即既有男孩又有女孩）的情况是：男女,女男,总共有4种等概率的可能结果，其中2种符合条件，因此概率为：

符合条件的情况数÷总情况数= 2/4 = 1/2

第6题 已定义变量 double a, b; ，下列哪个表达式可以用来判断一元二次方程x²+ax+b是否有实根？（）。

A. 4 * b - a * a < 0

B. 4 * b <= a * a

C. a * a - 4 * b

D. b * 4 - a * a

答案：B

考纲知识点：数学函数

解析：对一元二次房称a*x²+b*x+c=0的实根判定公式为：b²-4*a*c>=0，带入题目中的符号，得到B选项;

第7题n个结点的二叉树，执行广度优先搜索的平均时间复杂度是（ ）。

A. O(logn)

B. O(nlogn)

C. O(n)

D. O(2ⁿ)

答案：C

考纲知识点：树与图遍历

解析：对树执行搜索的时间复杂度为O(n)

第8题 以下关于动态规划的说法中，错误的是（ ）。

A.动态规划方法通常能够列出递推公式。

B.动态规划方法的时间复杂度通常为状态的个数。

C.动态规划方法有递推和递归两种实现形式。

D.对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。

答案：B

考纲知识点：动态规划

解析：一般来说，动态规划的时间复杂度可以表示为O (状态数量×每个状态的转移操作数);

第9题 下面的 sum_digit函数试图求出从1到n（包含1和n）的数中，包含数字d的个数。该函数的时间复杂度为（ ）。

A.O(nlogn)

B.O(n)

C.O(logn)

D.O(n²)

答案：A

考纲知识点：

解析：count_digit()和位数相关,对n，位数为log10(n)，主函数为n次for循环，总体复杂度O(nlogn)

第10题 下面程序的输出为（ ）。

A.60   

B.20    

C.15   

D.10

答案：A

考纲知识点：动态规划,排列组合

解析：本题可以理解为计算从(0,0,0)到(1,2,3)的路径数量，每次只能沿x、y或z轴正方向移动一步。在6个位置中，安排1个x步、2个y步、3个z步，有多少种不同的排列方式,使用排列组合公式(1+2+3)!/1!/2!/3!得到答案为60，或者程序运行的方式。

第11题 下面 count_triple函数的时间复杂度为( )。

A.O(n)   

B.O(n²)   

C.O(nlogn)

D.O(n²logn)

答案：C

考纲知识点：复杂度

解析：

count_triple函数功能：

统计某种三元组的数量;两层嵌套循环遍历变量v和u,对每对(u, v)，调用gcd(u, v) 判断是否互质,若互质，则计算三元组并累加计数；

外层循环（v的范围）：条件为v * v * 4 <= n，即v <= sqrt(n/4)，因此v的遍历次数为O(√n)。

内层循环（u的范围）：条件为u * (u + v) * 2 <= n，且u从v+1开始、步长为2递增。当v固定时，u的最大值近似为 √(n/2),看作O(√n)。

gcd函数时间复杂度为O(log min(a, b))，在最坏情况下可视为O(log n)（因u和v均不超过 √n）。

4.总时间复杂度

外层循环：O (√n),内层循环：O (√n)（对每个v）,每次循环内的gcd操作：O (log n)

总时间复杂度为O(√n × √n × log n) = O(n log n)

第12题 下面quick_sort函数试图实现快速排序算法，两处横线分别应该填入的是（）。

A.B.C.D.

答案：D

考纲知识点：快速排序

解析：第一处：需要将基准值放到正确位置，即交换a[l]和a[j]（因为j是最后一个小于基准值的位置）,第二处：返回基准值的最终位置j。

第13题 下面 LIS函数试图求出最长上升子序列的长度，横线处应该填入的是（ ）。

A.

B.C.

D.

答案：D

考纲知识点：线性DP

解析：本题考察LIS的状态转移方程,DP[i]为以nums[i]为结尾的LIS的长度,对nums[i]，考虑前方的j，衔接某个nums[j],满足nums[j]<nums[i]，则i可以衔接到j结尾,组成长度+1的LIS;

第14题 下面 LIS函数试图求出最长上升子序列的长度，其时间复杂度为（ ）。

A.O(nlogn)   

B.O(n)   

C.O(nlogn)     

D.O(n²)

答案：C

考纲知识点：线性DP

解析：LIS可以贪心+二分答案求解,复杂度O(nlogn)

第15题 下面的程序使用邻接矩阵表达的带权无向图，则从顶点0到顶点3的最短距离为（ ）。

A. 9

B. 10

C. 11

D. 12

答案：A

考纲知识点：最短路

解析：根据题目画图，得到最短路0~3为0~1~2~3=9

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

第1题C++语言中，表达式9|12的结果类型为int、值为13。

答案：√

考纲知识点：表达式计算

解析：|运算规则，二进制中对应位有1个1，当前位的结果就是1，9的二进制1001,12的二进制为1100,计算结果为1101，十进制值为13

第2题C++语言中，访问数据发生下标越界时，总是会产生运行时错误，从而使程序异常退出。

答案：×

考纲知识点：程序运行

解析：如果程序运行过程中，越界访问的数据已经申请的数据范围内，有可能会正常退出。正因下标越界访问的结果的不确定性，使得该类错误更难发现，应尽量在设计过程中避免。

第3题 对n个元素的数组进行归并排序，最差情况的时间复杂度为O(nlog n)。

答案：√

考纲知识点：归并排序

解析：归并排序最好最坏复杂度均为O(nlogn)

第4题5个相同的红球和4个相同的蓝球排成一排，要求每个蓝球的两侧都必须至少有一个红球，则一共有15种排列方案。

答案：×

考纲知识点：排列组合

解析：只有1种排列方案,红蓝相间;

第5题 使用math.h或cmath头文件中的函数，表达式log(8)的结果为类型double值约为 3。

答案：×

考纲知识点：数学函数

解析：表达式log(8)的计算结果是ln(8)，即8的自然对数值。近似值约为2.079441

第6题C++是一种面向对象编程语言，C则不是。继承是面向对象三大特性之一，因此，使用C语言无法实现继承。

答案：×

考纲知识点：类

解析：尽管C语言没有类,但是可以使用C语言模拟实现类的继承;

第7题n个顶点的无向完全图，有nⁿ⁻²棵生成树。

答案：√

考纲知识点：生成树

解析：由凯莱公式即可求解;

第8题 已知三个double类型的变量A、B和C分别表示一个三角形的两条边长及二者的夹角（弧度），则三角形的周长可以通过表达式sqrt(a*a+b*b+2*a*b*cos(thea))求得。

答案：×

考纲知识点：数学函数

解析：周长为：A + B + sqrt(A*A + B*B - 2*A*B*cos(C))

第9题 有V个顶点、E条边的图的深度优先搜索遍历时间复杂度为O(V + E)。

答案：√

考纲知识点：图的遍历

解析：使用邻接表存储，DFS遍历复杂度为O(V+E)

第10题  从32名学生中选出4人分别担任班长、副班长、学习委员和组织委员，老师要求班级综合成绩排名最后的4名学生不得参选班长或学习委员（仍可以参选副班长和组织委员），则共有P (30, 4)种不同的选法。

答案：√

考纲知识点：排列组合

解析：分步乘法原理得证;

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

编程题1

试题名称：树上旅行

时间限制：1.0 s

内存限制：512.0 MB

题目描述

给定一棵有n个结点的有根树，结点依次以1, 2, … , n 编号，其中根结点的编号为1。

小A计划在这棵有根树上进行q次旅行。在第i次旅行中，小A首先会选定结点s_i作为起点，并移动若干次。移动分为以下两种：

1.移动至当前结点的父结点。特殊地，如果当前位于根结点，则不进行移动。

2.移动至当前结点的所有子结点中编号最小的结点。特殊地，如果当前位于叶子结点，则不进行移动。

由于移动次数可能很大，对于第i次旅行，旅行中的移动将以k_i个不为零的整数构成的序列a_i,1, a_i,2, … , a_i,ki表示。对于a_i,j，若a_i,j> 0 则代表进行a_i,j次第一种移动；若a_i,j< 0 则代表进行−a_i,j次第二种移动。根据给出的序列从左至右完成所有移动后，小A所在的结点即是旅行的终点。给定每次旅行的起点与移动序列，请你求出旅行终点的结点编号。

输入格式

第一行，两个正整数n, q，分别表示有根树的结点数量，以及旅行次数。第二行，n − 1 个整数p₂, p₃, … , p_n，其中p_i表示结点i的父结点编号。

接下来2q行中的第2i − 1 行（1 ≤ i ≤ q）包含两个正整数si, ki，分别表示第i次旅行的起点编号，以及移动序列的长度。第2i行包含k_i个整数a_i,1, a_i,2, … , a_i,ki，表示移动序列。

输出格式

输出共q行，第i行包含一个整数，表示第i次旅行终点的结点编号。

样例

输入样例1

输出样例1

输入样例2

输出样例2

数据范围

对于所有测试点，保证1≤n≤10⁵,1≤q≤2x10⁴,1≤p_i≤n，1≤s_i≤n，k_i≥1且∑k_i≤10⁵，1≤ |a_i,j|≤ n。

题目大意：给定一棵有根树（根为1号点），有 q 次查询。每次从某个起点 s 出发，按照指令 ai,j 移动：ai,j>0：向上走 ai,j 步（即走到 ai,j 级祖先）。ai,j<0：向下走 ai,j 步，每一步都选择当前点所有子节点中编号最小的那个继续走。输出每次操作后停在的最终结点编号。考纲知识点：倍增LCA解析：将题目转化一下，操作1就是从一个点向上跳x次，操作2就是从一个点向下跳x次。观察到x比较大，如果直接一步一步跳显然会超时。这时我们可以选择倍增。首先预处理出从一个点开始向上和向下跳2k步后会跳到哪里，然后用类似快速幂的方式跳，将x二进制分解，如果当前位是0就不跳，如果当前位是1就跳。时间复杂度O(klogn)。

写代码时注意一下边界情况的处理。

参考程序

编程题2

试题名称：遍历计数

时间限制：1.0 s

内存限制：512.0 MB

题目描述

给定一棵有n个结点的树T，结点依次以1, 2, … , n 标号。树T的深度优先遍历序可由以下过程得到：

1.选定深度优先遍历的起点s（1 ≤ s ≤ n），当前所在结点即是起点。

2.若当前结点存在未被遍历的相邻结点u则遍历u，也即令当前所在结点为u并重复这一步；否则回溯。

3.按照遍历结点的顺序依次写下结点编号，即可得到一组深度优先遍历序。

第一步中起点的选择是任意的，并且第二步中遍历相邻结点的顺序是任意的，因此对于同一棵树T可能有多组不同的深度优先遍历序。请你求出树T有多少组不同的深度优先遍历序。由于答案可能很大，你只需要求出答案对109取模之后的结果。

输入格式

第一行，一个整数n，表示树T的结点数。

接下来n − 1 行，每行两个正整数u_i, v_i，表示树T中的一条连接结点u_i, v_i的边。

输出格式

输出一行，一个整数，表示树T的不同的深度优先遍历序数量对10⁹取模的结果。

样例

输入样例1

输出样例1

输入样例2

输出样例2

数据范围

对于40%的测试点，保证1<=n<=8。

对于另外20%的测试点，保证给定的树是一条链。

对于所有测试点，保证1<=n<=100000。

题目大意:计算一棵树上所有不同的DFS序的数量。

考纲知识点:组合计数

解析:

将题目转化一下：计算在DFS的过程中，每一步有多少种选择，然后将所有选择数相乘。定义Count(s)为从节点s出发的不同DFS序的数量；起点s，可以按任意顺序访问相邻节点，也就是有deg(s)!种情况，剩下的点也可以按任意顺序访问相邻节点，但是不能访问父节点，所以有(deg(u)−1)!种情况。因为所有顶点的度数之和等于边数的两倍。所以在一棵有n个节点的树中：∑deg(s)!=2(n-1)

因此总方案为：π(deg(u)−1)!*2(n-1)

注意当n=1时，DFS序数量为1，需要特判。

参考代码：

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

技术支持：查昊昊