2024年3月CCF-GESP编程能力等级认证C++编程八级真题

为丰富食堂菜谱，炒菜部进行头脑风暴。肉类有鸡肉、牛肉、羊肉、猪肉4种，切法有肉排、肉块、肉末3种，配菜有圆白菜、油菜、豆腐3种，辣度有麻辣、微辣、不辣3种。不考虑口感的情况下，选1种肉、1种切法、1种配菜、1种辣度产生一道菜（例如：麻辣牛肉片炒豆腐），这样能产生多少道菜？（ ）。

已知袋中有2个相同的红球、3个相同的绿球、5个相同的黄球。每次取出一个不放回，全部取出。可能产生多少种序列？（ ）。

以下二维数组的初始化，哪个是符合语法的？（ ）。

下面有关C 拷贝构造函数的说法，错误的是（ ）。

使用邻接表表达一个无向简单图，图中包含 v 个顶点、 e 条边，则该表中边节点的个数为（ ）。

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

已知三个 double 类型的变量 a 、 b 和 theta 分别表示一个三角形的两条边长及二者的夹角（弧度），则下列哪个表达式可以计算这个三角形的周长？（ ）。

在有 n 个元素的二叉排序树中进行查找，其最好、最差时间复杂度分别为（ ）。

如下图所示，半径为 r 、圆心角为 t （弧度）的扇形，下面哪个表达式能够求出顶部阴影部分的面积？（ ）。

下面程序的时间复杂度为（ ）。

int fib(int n) {\tif (n <= 1)\t\treturn 1;\treturn fib(n - 1)   fib(n - 2);}

下面程序的时间复杂度为（ ）。

int choose(int n, int m) {\tif (m == 0 || m == n)\t\treturn 1;\treturn choose(n - 1, m - 1)   choose(n - 1, m);}

下面程序的时间复杂度为（ ）。

int primes[MAXP], num = 0;bool isPrime[MAXN] = {false};void sieve() {\tfor (int n = 2; n <= MAXN; n  ) {\t\tif (!isPrime[n])\t\t\tprimes[num  ] = n;\t\tfor (int i = 0; i < num && n * primes[i] <= MAXN; i  ) {\t\t\tisPrime[n * primes[i]] = true;\t\t\tif (n % primes[i] == 0)\t\t\t\tbreak;\t\t}\t}}

下面程序的输出为（ ）。

#include using namespace std;int a[10][10];int main() {\tint m = 5, n = 4;\tfor (int x = 0; x <= m; x  )\t\ta[x][0] = 1;\tfor (int y = 1; y <= n; y  )\t\ta[0][y] = 1;\tfor (int x = 1; x <= m; x  )\t\tfor (int y = 1; y <= n; y  )\t\t\ta[x][y] = a[x - 1][y]   a[x][y - 1];\tcout << a[m][n] << endl;\treturn 0;}

下面程序的输出为（ ）。

#include using namespace std;int main() {\tint cnt = 0;\tfor (int x = 0; x <= 10; x  )\t\tfor (int y = 0; y <= 10; y  )\t\t\tfor (int z = 0; z <= 10; z  )\t\t\t\tif (x   y   z == 15)\t\t\t\t\tcnt  ;\tcout << cnt << endl;\treturn 0;}

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

int weight[4][4] = {\t{ 0, 1, 7, 100},\t{ 1, 0, 5, 15},\t{ 7, 5, 0, 6},\t{100, 15, 6, 0}}

已知 int 类型的变量 a 和 b ，则执行语句 a, b = b, a; 后，变量 a 和 b 的值会互换。（ ）

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

孙子定理是求解一次同余方程组的方法，最早见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》。又称中国余数定理，是中国数学史上的一项伟大成就。（ ）

N个顶点的无向完全图有N×(N-1)条边。（ ）

为解决哈希函数冲突，在哈希表项内设置链表存储该项内的所有冲突元素，则该哈希表内查找元素的最差时间复杂度为O(1)。（ ）

求一个包含 v 个顶点、 e 条边的带权连通无向图的最小生成树，Prim算法的时间复杂度为O(v×e)。（ ）

已知 int 类型的变量 a 、 b 和 c 中分别存储着一个三角形的三条边长，则这个三角形的面积可以通过表达式 sqrt((a b c) * (b c - a) * (a c - b) * (a b - c)) / 4 求得。（ ）

可以使用深度优先搜索算法判断图的连通性。（ ）

在N个元素的二叉排序树中查找一个元素，平均情况的时间复杂度是O(logN)。（ ）

给定 double 类型的变量 x ，且其值大于等于 ，我们可以通过二分法求出logx的近似值。（ ）

公倍数问题

问题描述

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

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

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

输入描述

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

输出描述

输出一行，即。

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

特别提醒

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

样例输入 1

2 5 2

样例输出 1

9

样例解释 1

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

A_1,1,A_1,2,A_2,1,A_2,2都可以是2，而其余不行。

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

样例输入 2

100 100 100

样例输出 2

185233

数据规模

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

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

对于100的测试点，保证N,M≤10⁵，K≤10⁶。

接竹竿

题面描述

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

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

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

输入格式

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

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

第二行包含n个正整数A₁,A₂,...A_n,，表示卡牌的点数A。

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

接下来q行，每行两个正整数l_i,r_i，表示一组询问。

输出格式

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

样例输入

161 2 2 3 1 341 31 61 55 6

样例输入

1102

样例解释

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

对于第二次询问，队列变化情况为：

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

数据范围