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

一、 单选题  (每题2分,共30分)

第1题 国家“以旧换新”政策仍在继续，小杨家决定在家里旧的冰箱、电视、洗衣机、微波炉中选两种换新。其中，冰箱有4种型号可选，电视有6种型号可选，洗衣机有3种型号可选，微波炉有5种型号可选。请问小杨家共有多少种换新的方案？（  ）。

A.18

B.119

C.238

D.360

答案:B

考纲知识点:排列组合

解析:

四选二共C(4,2)=6种,由于每种电器的数量不同，可以单独计算每种方案：

合计119种方案，选择B;

第2题 小杨和3位朋友约好一起去看电影“哪吒2”。打开购票软件，他们发现，已经没有同一排连续的四个座位了（图中每个方框代表一个座位，红色方框代表已经售出）。朋友们商量了一下，决定分为两组，每组两人在同一排的相邻两个座位，且两组之间至少有一对座位是前后相邻的。请问共有多少种购票方案？（  ）。

A.495

B.96

C.7

D.4

答案:C

考纲知识点:排列组合

解析:按照题目要求，共以下7种方案:

第3题 下面关于C++类构造和析构函数的说法，错误的是（  ）。

A.构造函数不能声明为虚函数。

B.析构函数必须声明为虚函数。

C.类的默认构造函数可以被声明为private。

D.类的析构函数可以被声明为private。

答案:B

考纲知识点:类的构造

解析:在C++中，以下类型的函数不能声明为虚函数‌：

‌构造函数‌：析构函数(也可以声明为虚函数 但是应用范围少，也不推荐)

‌静态成员函数‌：内联成员函数‌：普通函数（非成员函数）‌：友元函数‌。

第4题  下列关于树和图的说法，错误的是（  ）。

A.树是一种有向无环图，有向无环图都是一棵树。

B.如果把树看做有向图，每个节点指向其子节点，则该图是弱连通图。

C.N个顶点且连通的无向图，其最小生成树一定包含N-1个条边。

D.N+1个顶点、N条边的有向图，一定不是强连通的。

答案:A

考纲知识点:图论概念

解析:

A错误:树是无环连通图，可以是无向图也可以是有向图(有向树)。但并非所有有向无环图都是树，例如森林(多个不连通的树)或子节点有重复的情况（如A->B，A->C，B->D，C->D）。

B正确:弱连通图是指将有向图的所有的有向边替换为无向边之后，所得的图是连通的。

C正确:最小生成树包含所有顶点，且边数最少，因此对于n个顶点，边数为n-1。

D正确:强连通图是指图中任意两个顶点之间都存在路径。N+1个顶点要构成强连通图，至少需要N+1条边（此时，N+1个顶点依次指向下一个，形成一个大环）。

第5题 从1到2025这2025个数中，包含数字5的个数（  ）。

A.600

B.601

C. 602

D.603

答案:D

考纲知识点:组合计数

解析:

个位:每10个数出现一次5，共2025/10=202.5，取整为202次，再加上2025中的5，共203次。

十位:每100个数出现10次5(50-59)，共2025/100=20.25，取整为20组，每组10次，共200次

百位:500-599出现100次，共2组。

千位:无

第6题 已定义double类型的变量r和theta，分别表示图中圆半径和圆心角。下列表达式中可以求出弦长s的是（  ）。

A.r*cos(theta)

B.r*cos(theta/2)*2

C.r*sin(theta)

D.r*sin(theta/2)*2

答案:D

考纲知识点:数学,三角函数

解析:根据三角函数关系，弦长s=2*r*sin(theta/2)。

第7题N个节点的平衡二叉树的高为（  ）。

A.log2N」

B.「log2N

C.log2N」+1

D.无法确定。

答案:D

考纲知识点:平衡二叉树,复杂度。

解析:平衡二叉树的高度与节点数量有关，但不是一个确定的函数关系。因此，无法确定。

第8题 下列关于算法的说法，错误的是（ ）。

A.如果有足够的时间和空间，枚举法能解决一切有限的问题。

B.分治算法将原问题分多个子问题进行求解，且分解出的子问题必须相互独立。

C.如果能找到合理的贪心原则，贪心算法往往能够比其他方法更快求解。

D.倍增法在搜索未知长度的有序数组时，通过动态倍增或减半步长，快速定位目标范围。

答案:B

考纲知识点:各类算法基础

解析:

A正确:枚举法可以尝试所有可能的解，因此在时间和空间允许的情况下可以解决有限问题。

B错误:分治算法分解出的子问题可以相互重叠，例如动态规划。

C正确:贪心算法在每一步选择局部最优解，如果贪心原则合理，可以快速得到全局最优解。

D正确:倍增法通过指数级别的步长快速逼近目标范围。

第9题 2025是个神奇的数字，因为它是由两个数20和25拼接而成，而且2025=(20+25)²。小杨决定写个程序找找小于N的正整数中共有多少这样神奇的数字。下面程序横线处应填入的是（  ）。

A. nl + nr == n

B. nl + nr == n2

C. (nl + nr) * (nl + nr) == n

D. (nl + nr)²== n2

答案:A

考纲知识点:枚举

解析:根据题意，需要满足nl+nr ==n!,即拼接后的两个数之和等于n。

第10题 2025是个神奇的数字，因为它是由两个数20和25拼接而成，而且2025=(20+25)²。小杨决定写个程序找找小于N的正整数中共有多少这样神奇的数字。该函数的时间复杂度为（  ）。

A.O(nlogn)

B.O(sqrt(n))

C.O(sqrt(n)*logn)

D.O(sqrt(n)*(logn²)

答案:D

考纲知识点:时空复杂度

解析:

外层循环:n从1到sqrt(N),复杂度为sqrt(N)。

内层循环:字符串s的长度最多为1og10(N)，内层循环中substr、stoi函数均需要O(log(N))的计算时间

因此内层循环复杂度为0((log(N))²)。总复杂度:O(sqrt(N)(log(N))²)

第11题 下面欧式筛法程序中，横线处应该填入的是（ ）。

A.

B.  

C.

D.

答案:C

考纲知识点:质数筛法

解析:第一个空:n*primes[i]<= MAXN ，保证n*primes[i]不超过数组范围。第二个空:n% primes[i]==0，如果n可以被primes[i]整除，说明n的最小质因子是primes[i]，那么n*primes[i+1]的最小质因子也是primes[i]，应该在之前被筛掉。

第12题 下列Floyd算法中，横线处应该填入的是（ ）。

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

B.map[i][k] = map[i][j] - map[k][j]

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

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

答案:A

考纲知识点:Floyd算法

解析:Floyd算法的核心是松弛操作，如果经过k点的路径比直接从i到j的路径更短，则更新map[i][j]。

第13题下面Floyd算法程序的时间复杂度为（  ）。

A.O(N)

B.O(N²)

C.O(N³)

D.O(N²logN)

答案:C

考纲知识点:Floyd算法复杂度为O(n³)

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

A.a[j] += a[j + 1]

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

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

D.a[j + 1] += a[j]

答案:B

考纲知识点:杨辉三角

解析:杨辉三角形的递推公式是a[i][j]= a[i-1][j-1]+ a[i-1][j]。由于代码中只使用了一维数组，需要从后往前更新，因此a[j]+= a[j-1]。

第15题 下列程序实现了输出杨辉三角形，其时间复杂度为（  ）。

A.O(n)

B.O(nlogn)

C.O(n²)

D.O(n³)

答案:C

考纲知识点:时间复杂度

解析:外层循环:i从0到n-1，复杂度为O(n)。内层循环:j从i-1到1，复杂度为O(n)。总复杂度O(n²)

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

第1题 表达式'5' - 3.0的结果为2.0，类型为double。

答案:×

考纲知识点:字符类型,隐式类型转换。

解析:字符'5'的ASCII码值为53，53-3.0=50.0，类型为double。

第2题 在C++语言中，如果想要在一个函数内调用一个类的私有方法，可以在该类中将该函数声明为友元函数。

答案:√

考纲知识点:友元函数

解析:友元函数可以访问类的私有成员。

第3题 插入排序一般是稳定的。

答案:√

考纲知识点:排序

解析:基于比较的排序中，不稳定的排序有:希尔，选择，快速，堆，四种，其他的都是稳定的，插入排序在插入元素时，如果遇到相等的值，会插入到相等元素的后面，因此是稳定的

第4题5个相同的红球和4个相同的蓝球排成一排，要求蓝球不能相邻，则一共有15种排列方案。

答案:√

考纲知识点:排列组合

解析:先将5个红球排成一排，形成6个空位，然后将4个蓝球插入到这些空位中，共有C(6,4)= 15 种方案。

第5题 使用math.h或cmath头文件中的函数，表达式pow(2, 5)的结果类型为int、值为32。

答案:×

考纲知识点:数学函数

解析:pow函数的返回值类型为double,

第6题C++是一种面向对象编程语言，C则不是。多态是面向对象三大特性之一，虚函数是动态多态的代表特性。因此，使用C语言无法实现虚函数。

答案:×

考纲知识点:类

解析:C语言本身没有直接提供虚函数这种语言特性，但是可以通过手动建立虚函数表（vtable）结构体的方式实现虚函数。事实上，早在C++语言诞生之前，使用C语言编写UNIX操作系统的过程中就已广泛采用了类似的实践，甚至可以说，正是C语言中的相关实践促使C++语言设计了虚函数相关语法。

第7题 在N个节点的平衡二叉树中查找指定元素的最差时间复杂度为O(N)。

答案:×

考纲知识点:复杂度

解析:在N个节点的平衡二又树中查找指定元素的最差时间复杂度是O(log N)。

第8题 定义int类型的变量a和b，求二次函数y = x²+ a x + b取最小值时x的值，可以通过表达式-a/2.0求得。

答案:√

考纲知识点:数学函数

解析:正确

第9题 判断无向图中是否有环，可以通过广度优先搜索实现。

答案:√

考纲知识点:搜索

解析:可以通过BFS遍历图，如果遇到已经访问过的节点，且该节点不是父节点，则存在环。

第10题 从32名学生中选出4人分别担任班长、副班长、学习委员和组织委员，共有C(32, 4)种不同的选法。

答案:×

考纲知识点:排列组合

解析:本题组内有序，因此是个排列数，共有P(32,4)=32*31*30*29 =863040 种选法。

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

3.1编程题1-上学

时间限制:1.0S

内存限制:512.0MB

题目描述

C城可以视为由n个结点与m条边组成的无向图。

这些结点依次以1, 2, ……, n 标号，边依次以1, 2, …, m 标号。第i条边（1<= i <= m）连接编号为u_i与v_i的结点，长度为l_i米。

小A的学校坐落在C城中编号为s的结点。小A的同学们共有q位，他们想在保证不迟到的前提下，每天尽可能晚地出门上学。

但同学们并不会计算从家需要多久才能到学校，于是找到了聪明的小A。

第i位同学（1<= i <= q）告诉小A，他的家位于编号为h_i的结点，并且他每秒能行走1米。请你帮小A计算，每位同学从家出发需要多少秒才能到达学校呢？

输入格式

第一行，四个正整数n, m, s, q，分别表示C城的结点数与边数，学校所在的结点编号，以及小A同学们的数量。

接下来m行，每行三个正整数u_i, v_i, l_i，表示C城中的一条无向边。

接下来q行，每行一个正整数h_i，表示一位同学的情况。

输出格式

共q行，对于每位同学，输出一个整数，表示从家出发到学校的最短时间。

样例

输入样例1

输出样例1

【题目大意】给定n个点m条边的无向图，有q次询问，每次询问需要回答某地点x到达终点s的最短路径(s固定);

【考纲知识点】最短路

【解题思路】

本题是一个无向图，所有边权非负，数据范围为n,m,q均达到200000,优先考虑dijkstra,由于是一个无向图，且是一个单目的地的最短路，因此直接以终点S为起点，跑一遍dijkstra,对每次询问进行O(1)查询即可,一道比较偏模版的题目。注意数据dist[i]的上限为n*l=2*10¹¹，需要开long long。

【参考代码】

3.2编程题2-割裂

时间限制:1.0S

内存限制:512.0MB

题目描述

小杨有一棵包含n个节点的树，其中节点的编号从1到n。

小杨设置了a个好点对<u_1,v_1>,<u_2,v_2>,...,<u_a,v_a>和1个坏点对<b_u,b_v>。一个节点能够被删除，当且仅当：

-删除该节点后对于所有的i(1<= i <= a)，好点对u_i和v_i仍然连通；

-删除该节点后坏点对b_u和b_v不连通。

如果点对中的任意一个节点被删除，其视为不连通。

小杨想知道，有多少个节点能够被删除。

输入格式

第一行包含两个正整数n,a，含义如题面所示。

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

之后a行，每行包含两个正整数u_i,v_i，代表一个好点对<u_i,v_i>。

最后一行包含两个正整数b_u,b_v，代表坏点对<b_u,b_v>。

输出格式

输出一个正整数，代表能够删除的节点个数。

输入样例

输出样例

数据范围

对于全部数据，保证有1≤n≤10⁶,0≤a≤10⁵,ui≠vi,bu≠bi

【题目大意】

给定一棵树,有若干好节点，一对坏节点;若单独删除一个节点后，使得好节点继续联通而这一对坏节点不联通，则该节点可以删除，求解可以删除的节点数量。

【考纲知识点】树上差分

【解题思路】模拟题目样例，可以发现，好节点的简单路径上的点都不可以删除，可以用LCA和树上差分对所有的好节点进行vis[]标记;之后DFS自下而上对vis进行前缀和还原,即可得到每个点被好点对覆盖的次数,vis[]标记为0的点可以选择删除,对当前的坏节点对(x,y),遍历x~y的沿途所有简单路径节点w，如果vis[w]==0，则该节点可删除，最终输出统计的个数即可,复杂度O(nlogn)。

【参考代码】

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

技术支持：查昊昊