试卷 2024年3月GESP认证C++编程八级真题试卷
2024年3月GESP认证C++编程八级真题试卷
选择题
第 1 题    单选题
为丰富食堂菜谱,炒菜部进行头脑风暴。肉类有鸡肉、牛肉、羊肉、猪肉4种,切法有肉排、肉块、肉末3种,配菜有圆白菜、油菜、豆腐3种,辣度有麻辣、微辣、不辣3种。不考虑口感的情况下,选1种肉、1种切法、1种配菜、1种辣度产生一道菜(例如:麻辣牛肉片炒豆腐),这样能产生多少道菜?( )。
A.

13

B.

42

C.

63

D.

108

第 2 题    单选题
已知袋中有2个相同的红球、3个相同的绿球、5个相同的黄球。每次取出一个不放回,全部取出。可能产生多少种序列?( )。
A.

6

B.

1440

C.

2520

D.

3628800

第 3 题    单选题
以下二维数组的初始化,哪个是符合语法的?( )。
A.
int a[][] = {{1, 2}, {3, 4}};
B.

int a[][2] = {};

C.
int a[2][2] = {{1, 2, 3}, {4, 5, 6}};
D.
int a[2][] = {{1, 2, 3}, {4, 5, 6}};
第 4 题    单选题
下面有关C++拷贝构造函数的说法,错误的是( )。
A.
必须实现拷贝构造函数,否则一定会出现编译错误。
B.
对象作为函数参数、以值传递方式传入函数时,会自动调用拷贝构造函数。
C.
对象作为函数返回值、以值传递方式从函数返回时,会自动调用拷贝构造函数。
D.
使用一个对象初始化另一个对象时,会自动调用拷贝构造函数。
第 5 题    单选题
使用邻接表表达一个无向简单图,图中包含v个顶点、e条边,则该表中边节点的个数为( )。
A.

u×(u-1

B.

u×u

C.

2×e

D.

e

第 6 题    单选题
关于生成树的说法,错误的是( )。
A.
一个无向连通图可以有多个生成树。
B.
一个无向图,只要连通,就一定有生成树。
C.
n个顶点的无向完全图,有nn-2棵生成树。
D.

n个顶点的无向图,生成树包含n-1条边。

第 7 题    单选题
已知三个double类型的变量a 、b和theta分别表示一个三角形的两条边长及二者的夹角(弧度),则下列哪个表达式可以计算这个三角形的周长?( )。
A.

a*b*sin(theta)/2

B.

a+b+(a+b)*sin(theta)/2

C.

a*b*cos(theta)/2

D.

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

第 8 题    单选题
在有n个元素的二叉排序树中进行查找,其最好、最差时间复杂度分别为( )。
A.

O⑴ 、O(n)

B.

O⑴ 、O(log n)

C.

O(log n) 、O(log n)

D.

O(log n) 、O(n)

第 9 题    单选题

如下图所示,半径为r、圆心角为t(弧度)的扇形,下面哪个表达式能够求出顶部阴影部分的面积?( )

A.
r*r*sin(t)/2
B.
r*r*t/2
C.
r*r*(t-sin(t))
D.
r*r*(t-sin(t))/2
第 10 题    单选题

下面程序的时间复杂度为( )。

1 int fib(int n) {
2  if (n <= 1)
3   return 1;
4  return fib(n - 1) + fib(n - 2);
5 }
A.

O(2n

B.

C.

O(n

D.

O(1

第 11 题    单选题

下面程序的时间复杂度为( )。

1 int choose(int n, int m) {
2  if (m == 0 || m == n)
3   return 1;
4  return choose(n - 1, m - 1) + choose(n - 1, m);
5 }
A.

O(2n)

B.

O(2m×(n-m))

C.

O(C(n,m))

D.

O(m×(n-m))

第 12 题    单选题

下面程序的时间复杂度为( )。

1 int primes[MAXP], num = 0;
2 bool isPrime[MAXN] = {false};
3 void sieve() {
4  for (int n = 2; n <= MAXN; n++) {
5   if (!isPrime[n])
6    primes[num++] = n;
7   for (int i = 0; i < num && n * primes[i] <= MAXN; i++) {
8    isPrime[n * primes[i]] = true;
9    if (n % primes[i] == 0)
10     break;
11   }
12  }
13 }
A.

O(n)

B.

O(n×log n)

C.

O(n×loglog n)

D.

O(n2)

第 13 题    单选题

下面程序的输出为( )。

1 #include <iostream>
2 using namespace std;
3
4 int a[10][10];
5 int main() {
6  int m = 5, n = 4;
7  for (int x = 0; x <= m; x++)
8   a[x][0] = 1;
9  for (int y = 1; y <= n; y++)
10   a[0][y] = 1;
11  for (int x = 1; x <= m; x++)
12   for (int y = 1; y <= n; y++)
13    a[x][y] = a[x - 1][y] + a[x][y - 1];
14  cout << a[m][n] << endl;
15  return 0;
16 }
A.

4

B.

5

C.

126

D.

3024

第 14 题    单选题

下面程序的输出为( )。

1 #include <iostream>
2 using namespace std;
3
4 int main() {
5  int cnt = 0;
6  for (int x = 0; x <= 10; x++)
7   for (int y = 0; y <= 10; y++)
8    for (int z = 0; z <= 10; z++)
9     if (x + y + z == 15)
10      cnt++;
11  cout << cnt << endl;
12  return 0;
13 }
A.

90

B.

91

C.

96

D.

100

第 15 题    单选题

下面的程序使用邻接矩阵表达的带权无向图,则从顶点0到顶点3的最短距离为( )。

1 int weight[4][4] = {
2  { 0, 1, 7, 100},
3  { 1, 0, 5, 15},
4  { 7, 5, 0, 6},
5  {100, 15, 6, 0}};
A.

100

B.

16

C.

12

D.

13

判断题
第 16 题    判断题
已知int类型的变量a和b,则执行语句a,b=b,a;后,变量a和b的值会互换。
A.
正确
B.
错误
第 17 题    判断题
一个袋子中有3个完全相同的红色小球、2个完全相同的蓝色小球。每次从中取出1个,再放回袋子,这样进行3次后,可能的颜色顺序有7种。
A.
正确
B.
错误
第 18 题    判断题
孙子定理是求解一次同余方程组的方法,最早见于中国南北朝时期(公元5世纪)的数学著作《孙子算经》。又称中国余数定理,是中国数学史上的一项伟大成就。
A.
正确
B.
错误
第 19 题    判断题
N个顶点的无向完全图有N×(N-1)条边。
A.
正确
B.
错误
第 20 题    判断题
为解决哈希函数冲突,在哈希表项内设置链表存储该项内的所有冲突元素,则该哈希表内查找元素的最差时间复杂度为O(1)。
A.
正确
B.
错误
第 21 题    判断题
求一个包含v个顶点、e条边的带权连通无向图的最小生成树,Prim算法的时间复杂度为O(u×e) 。
A.
正确
B.
错误
第 22 题    判断题
已知int类型的变量a、b和c中分别存储着一个三角形的三条边长,则这个三角形的面积可以通过表达式sqrt((a+b+c)*(b+c-a)*(a+c-b)*(a+b-c))/4求得。
A.
正确
B.
错误
第 23 题    判断题
可以使用深度优先搜索算法判断图的连通性。
A.
正确
B.
错误
第 24 题    判断题
在N个元素的二叉排序树中查找一个元素,平均情况的时间复杂度是O(logN)。
A.
正确
B.
错误
第 25 题    判断题
给定double类型的变量x,且其值大于等于 ,我们可以通过二分法求出log x的近似值。
A.
正确
B.
错误
编程题
第 26 题    问答题

试题名称:公倍数问题

3.1.1 问题描述 

小A写了一个 的矩阵 ,我们看不到这个矩阵,但我们可以知道,其中第i行第j列的元素Ai,j是i和j的公倍数( i=1,.....,N,j=1, ,.....,M)。现在有K个小朋友,其中第k个小朋友想知道,矩阵A中最多有多少个元素可以是k(k=1,2,.....,K )。请你帮助这些小朋友求解。 

注意:每位小朋友的答案互不相关,例如,有些位置既可能是x,又可能是y,则它同可以时满足x,y两名小朋友的要求。 

方便起见,你只需要输出即可,其中ansk表示第k名小朋友感兴趣的答案。 

3.1.2 输入描述 

第一行三个正整数N,M,K。 

3.1.3 输出描述 

输出一行,即。 

请注意,这个数可能很大,使用C++语言的选手请酌情使用long long等数据类型存储答案。 

3.1.4 特别提醒 

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

3.1.5 样例输入1

3.1.6 样例输出1

3.1.7 样例解释1 

只有A1,1可以是1,其余都不行。 

A1,1A1,2A2,1A2,2都可以是2,而其余不行。 

因此答案是1×1+2×4=9。 

3.1.8 样例输入2

3.1.9 样例输出2

3.1.10 数据规模 

对于30的测试点,保证N,M,K≤10;

对于60的测试点,保证N,M,K≤500; 

对于100的测试点,保证N,M≤105K≤106

第 27 题    问答题

试题名称:接竹竿 

3.2.1 题面描述 

小杨同学想用卡牌玩一种叫做“接竹竿”的游戏。 

游戏规则是:每张牌上有一个点数u,将给定的牌依次放入一列牌的末端。若放入之前这列牌中已有与这张牌点数相同的牌,则小杨同学会将这张牌和点数相同的牌之间的所有牌全部取出队列(包括这两张牌本身)。 

小杨同学现在有一个长度为n的卡牌序列A,其中每张牌的点数为Ai(1≤i≤n )。小杨同学有q次询问。第i次( 1≤i≤q)询问时,小杨同学会给出li,ri,小杨同学想知道如果用下标在[li,ri]的所有卡牌按照下标顺序玩“接竹竿”的游戏,最后队列中剩余的牌数。 

3.2.2 输入格式 

第一行包含一个正整数T,表示测试数据组数。 

对于每组测试数据,第一行包含一个正整数 ,表示卡牌序列A的长度。 

第二行包含n个正整数A1,A2,......,An,表示卡牌的点数A 。

第三行包含一个正整数q,表示询问次数。 

接下来q行,每行两个正整数li,ri,表示一组询问。 

3.2.3 输出格式 

对于每组数据,输出q行。第i行(1≤i≤q)输出一个非负整数,表示第i次询问的答案。 

3.2.4 样例1

3.2.5 样例解释 

对于第一次询问,小杨同学会按照1,2,2的顺序放置卡牌,在放置最后一张卡牌时,两张点数为2的卡牌会被收走,因此最后队列中只剩余一张点数为1的卡牌。

 对于第二次询问,队列变化情况为:

{}→{1}{1,2}{1,2,2}{1}{1,3}{1,3,1} {}{3} 。因此最后队列中只剩余一张点数为3的卡牌。 

3.2.6 数据范围

对于全部数据,保证有1≤T≤5,1≤n≤1.5×1041≤q≤1.5×1041≤Ai≤13

答题卡
选择题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
判断题
编程题
26 27
题目总数:27
总分数:100
时间:120分钟