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

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

1、下面关于C++类和对象的说法，错误的是（ ）。

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

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

C. class中成员的默认访问权限为private。

D. struct中成员的默认访问权限为private。

答案:D

考纲知识点:C++结构体 类的创建

解析:在C++中，struct默认的访问权限是public，而class的默认访问权限是private。如果你想改变这一默认行为，可以在struct中显式地声明成员为private。

解决方案：

在这个例子中，x和y是私有成员，只能被MyStruct类的成员函数访问。

2、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小为（ ）。

A. n×n/2

B. n×n

C. (n-1)×(n-1)
D. (n+1)×(n+1)

答案:B

考纲知识点:图的定义和遍历

解析:n个顶点对的无向图，需要n行n列的矩阵(对称)，可以用数组下标0~n-1对应，选B。

3、设有编号为A、B、C、D、E的5个球和编号为A、B、C、D、E的5个盒子。现将这5个球投入5个盒子，要求每个盒子放一个球，并且恰好有两个球的编号与盒子编号相同，问有多少种不同的方法？

A. 5

B. 120

C. 20

D. 60

答案:C

考纲知识点:排列与组合

解析:先从5个球中选择2个球放到对应的盒子中，有种，剩余的3个球不能和盒子编号相同，因此第3个球有2种盒子可以选择，第4个球和第5个球只有1种选择。

共10*2=20种，选C。

4、从甲地到乙地，可以乘高铁，也可以乘汽车，还可以乘轮船。一天中，高铁有10班，汽车有5班，轮船有2班。那么一天中乘坐这些交通工具从甲地到乙地共有多少种不同的走法？（ ）。

A. 100

B. 60

C. 30

D. 17

答案:D

考纲知识点:计数原理

解析:由加法原理，ans=10+5+2=17种。

5、个结点的二叉树，执行释放全部结点操作的时间复杂度是（ ）。

A.O(n)

B.O(nlogn)

C.O(logn)

D.O(2ⁿ)

答案:A

考纲知识点:二叉树

解析:对二叉树执行DFS，在回溯阶段依次释放每个节点，复杂度O(n)。

6、在一个单位圆上，随机分布n个点，求这n个点能被一个单位半圆周全部覆盖的概率（ ）。

A.n/(2^n-1)

B.1/n²

C.1/n

D.1/2ⁿ

答案:A

考纲知识点:概率统计(代数)

解析:可以特殊值，取n=2,则概率为1，选A，更严格的证明:

在一个圆中，假设选择A点，做A在圆中的对称点A’，连接A和A’并将圆四等分，如图所示，绿色区域可以认为是A的半圆区域。对n个点，都作出其对称点，这样一共有2n个点，这样问题从“在圆内随机取n个点”转为：在2n个点中取n个点，其中对于每个点和它的对称点，只能选一个出来。一共有2ⁿ种选法。

n个点在一个半球，等价于任意两个点他们的公共领地有交集。显然这种方式有2n种(可以考虑3个点的情况->2种,更多的点也是同理)。

概率为:2n/2ⁿ，化简后选A。

7、下面 pailie 函数是一个实现排列的程序，横线处可以填入的是（ ）。

A.

B.

C.

D.

答案:C

考纲知识点:排列与组合

解析:函数作用:在0~n-1的区间，对A[0~n-1]的元素进行全排列。

全排列可以这么理解，每个元素都有尝试在开头的机会，之后其他的元素在这个前提之下，继续在该元素后方继续尝试。当然在尝试完成后，还需要将排列还原，方便后续尝试，符合该要求的只有C选项。

8、上一题中，如果主函数为如下的程序，则最后的排列数是多少个？（ ）。

A. 120

B. 60

C. 240

D. 180

答案:A

考纲知识点:排列与组合

解析:5的全排列5!=120。

9、下列程序实现了输出杨辉三角形，代码中横线部分应该填入的是（ ）。

A. a[i][j] = a[i - 1][j - 1] + a[i - 1][j];

B. a[i][j] = a[i][j - 1] + a[i - 1][j];

C. a[i][j] = a[i - 1][j] + a[i - 1][j];

D. a[i][j] = a[i - 1][j - 1] + a[i][j];

答案:A

考纲知识点:杨辉三角

解析:如图所示，选A。

10、下面最小生成树的Kruskal算法程序中，横线处应该填入的是（ ）。

A. uParent == vParent

B. uParent >= vParent

C. uParent != vParent

D. uParent <= vParent

答案:C

考纲知识点:最小生成树

解析:Kruskal基于避圈法和贪心思想，先按照边权升序，依次考虑每条边(x,y,z),如果x和y已经处于同一个生成树中，则过滤掉当前的边，否则将x和y的生成树通过z边连接，同时用并查集维护x和y(联接x和y的集合)，组成更大的生成树。

横线处为判断x和y是否处于同一个集合，不是则链接，并更新最小生成树的边权和。答案选C。

11、下面Prim算法程序中，横线处应该填入的是（ ）。

A. graph[u][v] >= 0 && key[v] > graph[u][v]

B. graph[u][v] <= 0 && key[v] > graph[u][v]

C. graph[u][v] == 0 && key[v] > graph[u][v]

D. graph[u][v] != 0 && key[v] > graph[u][v]

答案:D

考纲知识点:最小生成树

解析:最小生成树的Prim算法思想：选择圈内的一个点x(一开始随便选一个点作为x)，遍历x的所有出边y，从中选取一个边权z最小的y，该(x,y,z)一定是最小生成树的生成边(因为最小生成树的点之间相互连通)，程序中key数组就是用来记录过程中每个节点距离圈的距离的最小值，parent数组是记录节点和边权依次加入圈的具体路径(最终形成一棵生成树)，横线处是比较圈外距离u最小的边权v，因此答案选D。

12、下列Dijkstra算法中，横线处应该填入的是（ ）。

A. dis[j] > minn && cheak[j] == 0

B. dis[j] < minn && cheak[j] == 0

C. dis[j] >= minn && cheak[j] == 0

D. dis[j] < minn && cheak[j] != 0

答案:B

考纲知识点:单源最短路

解析:朴素dijkstra算法，在非负权图中，用cheak[]标记已经求得最短路的点(因为已经求得，所以后续不会再更新)，每次选择距离起点S的未求得最短路(cheak[]==0)的,且最近的节点minx,由非负权图的原因，该节点minxj将加入已经求得最短路的点的集合，同时用minx尝试是否能更新S到其他待球节点的最短路。横线处就是求解距离起点S的未求得最短路(cheak[]==0)的,且最近的节点minx的，因此选B。

13、下面Floyd算法中，横线处应该填入的是（ ）。

A. map[i][j] < map[i][k] + map[k][j]

B. map[i][j] > map[i][k] + map[k][j]

C. map[i][j] > map[i][k] - map[k][j]

D. map[i][j] < map[i][k] - map[k][j]

答案:B

解析:Floyd算法本质是个DP，或者可以理解为松弛操作：
i和j的最短路如果可以通过中间节点k做更新：

则需要map[i][j]>map[i][k]+map[k][j];选B。

14、下面程序的Merge_Sort 函数时间复杂度为（ ）。

A.O(nlogn)

B.O(n²)

C.O(2ⁿ)

D.O(logn)

答案:A

考纲知识点:归并排序

解析:归并排序基于分治

时间复杂度为O(nlogn)。空间复杂度O(n);

15、下面fibonacci函数的时间复杂度为（ ）。

A.O(1)

B. O(()ⁿ)

C.O(n)

D.O(nlogn)

答案:B

考纲知识点:较复杂算法的空间复杂度和时间复杂度

解析:结合递归搜索树，以最坏的情况考虑，f(n)每次减少1的问题规模需要变为两个分支，记为f(n)=2¹f(n-1)=2²f(n-2)=…=2^n-1f(1)=2^n-1，因此复杂度接近O(2ⁿ)。指数级别。最接近的选择B。

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

1、表达式'3' & 1 的结果为'1'。

答案:×

考纲知识点:ASCII码

解析:ASCII码’3’为51，是奇数，&1操作是取51的最低位2进制。结果为1，而非字符’1’。

2、在C++语言中，变量定义必须在某一个函数定义之内。

答案:×

考纲知识点:变量

解析:变量可以为全局变量。

3、冒泡排序一般是不稳定的。

答案:×

考纲知识点:排序

解析:基于比较的排序中不稳定的有四个：希尔，选择，快速，堆，其余都稳定。

4、二叉排序树的查找操作的平均时间复杂度，正比于树的高度。

答案:√

考纲知识点:二叉排序树

解析:二叉排序树查找的时间复杂度为树的高度。

5、使用math.h或cmath头文件中的余弦函数，表达式cos(60)的结果类型为double、值约为0.5。

答案:×

考纲知识点:数学库常用函数(三角函数)

解析:，cos函数接受的角度参数是以弧度为单位的。因此，如果要用角度（如60度）作为参数，需要先将其转换为弧度。在C或C++中，可以使用M_PI（在math.h或cmath中定义）来表示π，从而将60度转换为弧度，即60 * M_PI / 180。

6、你有三种硬币，分别面值2元、5元和7元，每种硬币都有足够多。买一本书需要27元，则最少可以用5个硬币组合起来正好付清，且不需要对方找钱。

答案:√

考纲知识点:排列与组合

解析:7+5+5+5+5=27共5枚，且没有更优方案。

7、现有n个完全相同的元素，要将其分为k组，允许每组可以有0个元素，则一共有 种分组方案。

答案:×

考纲知识点:排列与组合

解析:‌插板法‌：首先，我们有n个球排成一列，然后在这n个球之间以及两端共n+1个空位中选择k-1个位置插入隔板。这样，隔板将球分成了k组，每组中的球数即为该组的元素数（包括0个）。

‌组合计算‌：从n+1个空位中选择k-1个位置插入隔板，即组合数C(n+1, k-1)。但注意到，由于我们实际上是在n个球和k-1个板之间做选择，且板的数量是固定的k-1，所以更准确的组合应该是从n+k-1个“位置”（n个球和k-1个“潜在隔板位置”的总和）中选择k个“实体”（k-1个实际隔板和1个“虚拟”的起始或结束位置，用于确定组的边界），即C(n+k-1, k)。

8、已知int类型的变量a和b中分别存储着一个直角三角形的两条直角边的长度，则该三角形的面积可以通过表达式a / 2.0 * b 求得。

答案:√

考纲知识点:自动类型转换

解析:a/2.0会自动隐式转换为double，从而保证结果的正确性。

9、已知等差数列的通项公式an=a1+(n-1)d，则前n项和的求和公式为Sn=n*(a1+an)/2。使用这一公式计算Sn的时间复杂度是O(1)。

答案:√

考纲知识点:代数

解析:公式计算一步到位，和规模无关，复杂度O(1).

10、诚实国公民只说实话，说谎国公民只说谎话。你来到一处分岔口，一条通往诚实国，一条通往说谎国，但不知是哪一条通往哪里。正在为难之际，走来两位路人，他们都自称是诚实国公民，都说对方是说谎国公民。你想去说谎国，可以这样问其中一位路人：“我要去说谎国，如果我去问另一个路人，他会指向哪一条路？”。

答案:√

解析:数学思维

说谎的人回答的是去诚实国的路，诚实的人回答的是去诚实国的路，故而分辨出来。

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

1、手套配对

题面描述

小杨有n对不同的手套，每对手套由左右各一只组成。

小杨想知道从中取出m只手套，m只手套恰好包含k对手套的情况有多少种。

小杨认为两种取出的情况不同，当且仅当两种情况取出的手套中存在不同的手套（同一对手套的左右手也视为不同的手套）

输入格式

第一行包含一个正整数t，代表测试用例组数。

接下来是t组测试用例。对于每组测试用例，一共一行。

第一行包含三个正整数n,m,k，代表手套数量，取出的手套数和目标对数。

输出格式

对于每组测试数据，输出一个整数，代表可能的情况数量对10⁹+7取模的结果。

样例1

对于全部数据，保证有1≤t≤10⁵,1≤n≤1000，1≤m≤2×n,l≤k≤n。

【题目大意】从n对手套中(左右手不同)选择m只，恰好有k只的方案数。

【考纲知识点】数论:排列组合

【解题思路】考虑从n对手套中选出k对手套，有种选择，此时已经用掉了2k的次数，还剩下m-2k次，这些次数考虑从剩余的n-k双手套中，每个手套选一只，每种手套有2种选择，因此有种情况。

因此答案ans=

由于数据量只有10三次方，因此可以杨辉三角，2的次幂取模可以直接递推求解，如果数据范围达到百万级别，则需要用逆元求解。

参考代码：

杨辉三角：

n,m,k百万级别数据范围的

参考代码(逆元):

2、美丽路径

题面描述

小杨有一棵包含n个节点的树，节点从1到n编号，并且每个节点要么是白色，要么是黑色。

对于树上的一条简单路径（不经过重复节点的路径），小杨认为它是美丽的当且仅当路径上相邻节点的颜色均不相同。例如下图，其中节点1和节点4是黑色，其余节点是白色，路径2-1-3-4是美丽路径，而 路径2-1-3-5不是美丽路径（相邻节点3和5颜色相同）。

对于树上的一条简单路径，小杨认为它的长度是路径包含节点的数量。小杨想知道最长的美丽路径的长度是多少。

输入格式

第一行包含一个正整数n，代表节点数量。

第二行包含n个整数 ，c₁,c₂,...,c_n代表每个节点的颜色，如果c_i=0，代表节点i为白色，如果c_i，代表节点为黑色。

之后n-1行，每行包含两个正整数u_i，v_i，代表存在一条连接节点u_i和节点v_i的边。

输出格式

输出一个整数，代表最长美丽路径的长度。

样例1

样例2

对于全部数据，保证有1 ≤ n ≤ 10⁵,0 ≤c_i≤ 1，同时保证给出的数据构成一棵树。

【题目大意】给定一棵树和节点颜色(黑白)，找出最长的一条黑白相间的链路对应的节点数量。

【考纲知识点】树形DP

【解题思路】对于30%的数据，直接建图暴力，可以得到30分

满分解：

1.定义DP[x][0/1]:x以x为根的,x颜色为(0白1黑)的最长链路节点数量初始化:DP[x][A[x]]=1 ,DP[x][1-A[x]]=0;

2.定义Fx:穿过x的满足题目要求的最长节点数量，则Fx由以x为端点的最长链和次长链组成。

状态转移方程：对(父亲x->孩子y A[x]为x的节点颜色)

①若A[x]=0：DP[x][0]=max(DP[x][0],DP[y][1]+1);

②若A[x]=1：DP[x][1]=max(DP[x][1],DP[y][0]+1);

在此基础上，Fx因为由最长和次长组成，因此需要在DP[x]更新前完成更新，因此：
①若A[x]=0

Fx=max(Fx,DP[x][0]+DP[y][1]);

DP[x][0]=max(DP[x][0],DP[y][1]+1);

②若A[x]=1;

Fx=max(Fx,DP[x][1]+DP[y][0]);

DP[x][1]=max(DP[x][1],DP[y][0]+1);

目标状态:Fx

参考代码

技术支持：查昊昊

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