GESP2024年6月认证C++八级

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

1、GESP活动期间，举办?从获胜者ABCDE五个?中选出三个?排成?队升国旗，其中A不能排在队?，请问有多少种排法？

A. 24

B. 48

C. 32

D. 12

【答案】B

【考纲知识点】数学知识

【解析】排列组合问题。A不能排队首，因此第一位有4种选法；第二位不能与第一位相同，因此有4种选法；第三位不能与前两位相同，有3种选法；共计4*4*3=48种。

2、7进制数235转换成3进制数是（ ）。

A. 11121

B. 11122

C. 11211

D. 11112

【答案】A

【考纲知识点】进制转换

【解析】先将235转换成十进制124，然后再转换成3进制即可。

3、0,1,2,3,4,5这些数字组成?个三位数，请问没有重复数字的情况下，有多少种组法（ ）。

A. 180

B. 120

C. 80

D. 100

【答案】D

【考纲知识点】数学知识

【解析】一共6个数字，百位不能为0，因此有5种可能；然后再选2个数字排列，就是P(5,2)，答案是5*P(5,2)=100

4、有V个顶点、E条边的图的深度优先搜索遍历时间复杂度为（ ）。

A. O(v)

B. O(E)

C. O(V+E)

D.O(log(V + E))

【答案】C

【考纲知识点】图的知识

【解析】每个顶点每条边都会被访问一次，所有时间复杂度是C。

5、?对夫妻生男生女的概率相同。已知这对夫妻有两个孩?，其中?个是女孩，另?个是男孩的概率是多少？

A.?

B.?

C.?

D.?

【答案】C

【考纲知识点】数学知识

【解析】概率知识。每次男孩和女孩的概率都是1/2。

6、从1到2024这2024个数中，共有（ ）个包含数字6的数。

A. 544

B. 546

C. 564

D. 602

【答案】A

【考纲知识点】数学知识

【解析】

1位数字，只有1个6。

2位数字，有6的情况是6*，*表示0到9，共10种；*6，*表示1-9（除掉6），共8种，所以两位数有6的共18种。

3位数字，有6的情况，1位数字6，十位补0，*06，*表示1-9（除掉6），有8种；两位数前面加数字1-9（除掉6），

*（含6），8*18=144，百位是6的有600-699，共100个数字，总计100+144+8=252种。

同理1000-1999,1位数补成4位数，1006；2位数补成10（含6），3位数前面加1，有1+18+252=271种。

2000-2024有2个含数字6的数字，总数是1+18+252+271+2=544.

7、二进制数100.001转换成十进制数是（ ）。

A. 4.25

B. 4.125

C. 4.5

D. 4.75

【答案】B

【考纲知识点】数学知识

【解析】进制转换知识，100=1*22；0.001=1*2-3。

8、以下函数声明，哪个是符合C++语法的？（ ）。

A. void BubbleSort(char a[][], int n);

B. void BubbleSort(char a[][20], int n);

C. void BubbleSort(char a[10][], int n);

D. void BubbleSort(char[,] a, int n);

【答案】B

【考纲知识点】语法知识

【解析】考察的是二维数组定义的知识。二维数组第二维长度必须确定。

9、下?有关C++重载的说法，错误的是（ ）。

A.两个参数个数不同的函数可以重名。

B.两个参数类型不同的函数可以重名。

C.两个类的?法可以重名。

D.所有C++运算符均可以重载。

【答案】D

【考纲知识点】语法知识

【解析】不能重载的运算符还是挺多的。“::”、“.”、“?:”等。

10、小于或等于给定正整数n的数中，与n互质的数的个数，我们称为欧拉函数，记作。下?说法错误的是（ ） 。

A.如果n是质数，那么?(n)=n-1。

B.两个质数?定是互质数。

C.两个相邻的数?定是互质数。

D.相邻的两个质数不?定是互质数。

【答案】D

【考纲知识点】数学知识

【解析】两个不同的质数是互质数。

11、已知?棵?叉树有10个节点，则其中至多有（ ）个节点有2个子节点。

A. 4

B. 5

C. 6

D. 3

【答案】A

【考纲知识点】树的知识

【解析】可以画图模拟一下，最多是4个。设度为0的结点数为n0，度为1的结点数为n1，度为2的结点数为n2，由题意：

n0+n1+n2=10。在二叉树中有：n0=n2+1；所以有2*n2+n1=9;所以n1的值为奇数，最小的值为1，所以n2=4。

12、?项展开式

的系数，正好满?杨辉三角的规律。当n=10时，?项式展开式中xy9项的系数（ ）。

A. 5

B. 9

C. 10

D. 8

【答案】C

【考纲知识点】组合数

【解析】该项系数应为C(10, 1)=10。

13、下?程序的时间复杂度为（ ）。

A. O(N)

B. O(N x log N)

C. O(N x loglog N)

D.O(N2)

【答案】C

【考纲知识点】数学知识

【解析】代码是求欧拉筛，参数有些优化，时间复杂度是C。

14、下?程序的最差时间复杂度为（ ）。

A.

B. O(log(n))

C. O(n)

D. O(1)

【答案】B

【考纲知识点】数学知识

【解析】欧几里得算法的最坏时间复杂度。在最坏的情况，m和n为菲波那切数列中相邻的两项，所以时间复杂度是O（logn）。

15. 下?程序的输出为（ ）。

A. 90

B. 91

C. 710

D. 711

【答案】D

【考纲知识点】数学知识

【解析】x=0,y=0时，z的取值是[0,10]；x=0时，y=1到5,z的取值是[0,10];依次递推，x=0时，y最大等于10，的结果是11+11+…+6=106。同样枚举x=1时y和z的情况，累加得到结果。

2. 判断题 (每题 2 分,共 20 分)

1、ABCDE五个?朋友，排成?队跑步，其中AB两?必须排在?起，?共有48种排法。

【答案】对

【考纲知识点】数学知识

【解析】排列组合捆绑法。AB在一起，看成1个人，AB和BA共2中情况，所以是排队是：2*A(4,4)=48。

2、已知double类型的变量a和b，则执行语句a = a + b; b = a - b; a = a - b; 后，变量a和b的值会互换。

【答案】错

【考纲知识点】语法知识

【解析】a和b是double类型，加减会造成精度的损失，导致2个变量值不能互换。

3、?个袋子中有3个完全相同的红?小球、2个完全相同的蓝?小球。每次从中取出1个，再放回袋?，这样进行3次后，可能的颜?顺序有8种。

【答案】对

【考纲知识点】数学知识

【解析】0代表红色，1代表蓝色，情况是：000 001 010 011 100 101 110 111 。每个位置都有2种选择，所以是2*2*2=8.

4、已知int类型的变量a和b中分别存储着?个直角三角形的两条直角边的长度，则斜边的长度可以通过表达式sqrt(a * a + b * b) 求得。

【答案】对

【考纲知识点】数学知识

【解析】根据勾股定理求出。

5、在?个包含v个顶点、e条边的带权连通简单有向图上使?Dijkstra算法求最短路径，时间复杂度为O(v2)，可进?步优化?O(e+vlog(v))。

【答案】对

【考纲知识点】最短路径知识

【解析】暴力枚举每个点，时间复杂度是O（v2）；用优先队列每次找到距离最短的点，优先队列时间复杂度是O(logn)，每个点和边都访问一次，所以时间复杂度是O(e+vlogv)。

6、在N个元素的?叉排序树中查找?个元素，最差情况的时间复杂度是O(logN)。

【答案】错

【考纲知识点】树的知识

【解析】二叉排序树最坏的情况退化成1条链，时间复杂度是O(n)。

7、C++语?中，可以为同?个类定义多个析构函数。

【答案】错

【考纲知识点】面向对象知识

【解析】析构函数只能有1个。

8、使?单链表和使用双向链表，查找元素的时间复杂度相同。

【答案】对

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

【解析】查找的时间复杂度不变。都是从某个方向开始一直遍历查找。

9、为解决哈希函数冲突，可以使?不同的哈希函数为每个表项各建??个?哈希表，用来管理该表项的所有冲突元素。这些?哈希表?定不会发?冲突。

【答案】错

【考纲知识点】算法知识

【解析】子哈希表仍然可能产生冲突。

10、要判断?向图的连通性，在深度优先搜索和?度优先搜索中选择，深度优先的平均时间复杂度更低。

【答案】错

【考纲知识点】图的知识

【解析】都需要对每个点遍历一次，总时间复杂度不会有差距。可能在其他方面开销有区别，例如辅助空间等方面。

三、编程题(每题25分,共50分)

1、最远点对

题面描述

小杨有?棵包含n个节点的树，这棵树上的任意?个节点要么是??，要么是黑色。

小杨想知道相距最远的?对不同颜?节点的距离是多少。

输入格式

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

第二行包含几个非负整数a1,a2,……,an(对于所有的1≤i ≤n，均有a等于0或1)，其中如果ai= 0，则节点i的颜色为白色;如果ai=1，则节点的颜色为黑色。

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

保证输入的树中存在不同颜色的点。

输出格式

输出一个整数，代表相距最远的一对不同颜色节点的距离。

样例1

样例解释

数据范围

对于全部数据，保证有1≤n≤105，0≤ai≤1。

【题目大意】

这是一个树结构，从树中选2个颜色不同的点，颜色分为黑色和白色。求最远的距离。分析样例。1、先建立树；2、选2个颜色不同的点，求最远距离。例如1是白色，2是黑色，距离是1.通过枚举，发现2是黑色，5是白色，距离是3，是答案。

【考纲知识点】

建树知识，深搜知识

【解题思路】

每个结点要么黑色要么白色，需要保存结点的颜色信息。选2个颜色不同的点，可以先枚举第1个点和第2个点，求他们的距离，再求最大值。任意2点都是连通的，能够相互访问，能求出最大值。根据数据范围，能得到部分分。另一种思路就是根据树的性质，答案的2个点假设是a和b，路径会经过他们的公共祖先，距离=公共祖先到a的距离+公共祖先到b的距离。每个点视为公共祖先的话，有可能是左孩子的黑色和右孩子的白色组合，也可能是左孩子的白色和右孩子的黑色组成，也可能只在左孩子或者右孩子中。所以，每个结点应该保留2种颜色的最远值。一次深搜即可。每个点访问1次，时间复杂度是O(n)。

参考程序

2、空间跳跃

题面描述

小杨在二维空间中有n个水平挡板，并且挡板之间彼此不重叠，其中第i个挡板处于水平高度hi，左右端点分别位于li与ri。

小杨可以在挡板上左右移动，当小杨移动到右端点时，如果再向右移动会竖直掉落，从而落到下方第一个挡板上，移动到左端点时同理。小杨在挡板上每移动1个单位长度会耗费1个单位时间，掉落时每掉落1个单位高度也会耗费1个单位时间。

小杨想知道，从第s个挡板上的左端点出发到第t个挡板需要耗费的最少时间是多少?

注意:可能无法从第s个挡板到达到第t个挡板。

输入格式

第一行包含一个正整数n，代表挡板数量。

第二行包含两个正整数s,t，含义如题面所示。

之后n行，每行包含三个正整数li，ri，hi，代表第i个挡板的左右端点位置与高度。

输出格式

输出一个整数代表需要耗费的最少时间，如果无法到达则输出-1。

样例1

样例解释

耗费时间最少的移动方案为，从第3个挡板左端点移动到右端点，耗费3个单位时间，然后向右移动掉落到第2个挡板上，耗费100000-6=99994个单位时间，之后再向右移动1个单位长度，耗费1个单位时间，最后向右移动掉落到第1个挡板上，耗费3个单位时间。共耗费3+99994+1+3=100001个单位时间。

数据范围

对于全部数据，保证有1≤n ≤1000,1 ≤li≤ri≤105,1≤hi≤105。

【题目大意】

在二维空间里描述每个挡板有3个信息，左右端点和高度。根据测试样例，画出3个挡板的信息。1号挡板不一定在最上面，根据数据判断。3号挡板从1移到4，不能直接掉到1号挡板。先掉到2号挡板，再掉到1号挡板。

【考纲知识点】

建图知识，最短路径

【解题思路】

发现n的数据范围是1000，求的是从1个挡板到另外1个挡板。注意，掉到目标挡板中的某个位置即可。同时1个挡板左端到右端或者右端到左端算距离，其他挡板的2个端点只要能垂直相交到下一个挡板（中间没有其他挡板阻碍），也算相连。将这些端点和相交点看成结点，相连看成边，整个结构就成为一张图的结构。起点是固定的，终点也是固定的（只要是目标挡板的某个点即可），求的就是最短路径。数据都是正整数，可以用dijkstra算法实现。

难点1在于建图。一个挡板左右算2个结点，要连边；一个挡板的左右两端能够垂直到其他挡板，中间不能有间隔，要连边。

难度2就是dijkstra算法的完成。按照优先队列的模板完成即可。

参考程序