首页 › 试卷 › GESP编程能力等级认证 › GESP-C++八级 › 2023年12月CCF-GESP编程能力等级认证C++编程八级真题

2023年12月CCF-GESP编程能力等级认证C++编程八级真题 VIP

GESP-C++八级 共 27 题 2023 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、单选题

1. 单选题

小杨要从A城到B城,又想顺路游览一番。他有两个选项:1、坐高铁路到C城游览,再坐高铁或飞机到B城;2、坐船到D城游览,再坐船、高铁或飞机到B城。请问小杨从A城到B城共有几种交通方案可以选择?(   )。

  • A

    2

  • B

    3

  • C

    5

  • D

    6

查看答案与解析
答案:C
这道题暂未补解析。
2. 单选题

以下哪个函数声明是符合语法的,且在调用时可以将二维数组的名字作为实际参数传递给形式参数 a ?(   )。

  • A

    void QuickSort(int a[][10], int n);

  • B

    void QuickSort(int a[5][], int m);

  • C

    void QuickSort(int a[][], int n, int m);

  • D

    void QuickSort(int ** a, int n, int m);

查看答案与解析
答案:A
这道题暂未补解析。
3. 单选题

下面有关C++类和对象的说法,错误的是(   )。

  • A

    对象的生命周期开始时,会执行构造函数。

  • B

    对象的生命周期结束时,会执行析构函数。

  • C

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

  • D

    类的构造函数可以为虚函数。

查看答案与解析
答案:D
这道题暂未补解析。
4. 单选题

使用邻接矩阵表达 n 个顶点的有向图,则该矩阵的大小为(   )。

  • A

    n×(n+1)

  • B

    n×n

  • C

    n×(n-1)

  • D

    n×(n-1)/2

查看答案与解析
答案:B
这道题暂未补解析。
5. 单选题

5 位同学排队,其中一位同学不能排在第一,则共有多少种可能的排队方式?(   )。

  • A

    5

  • B

    24

  • C

    96

  • D

    120

查看答案与解析
答案:C
这道题暂未补解析。
6. 单选题

一个无向图包含 n 个顶点,则其最小生成树包含多少条边?(   )。

  • A

    n-1

  • B

    n

  • C

    n+1

  • D

    最小生成树可能不存在。

查看答案与解析
答案:D
这道题暂未补解析。
7. 单选题

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

  • A

    a * b * sin(theta) / 2

  • B

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

  • C

    a * b * cos(theta) / 2

  • D

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

查看答案与解析
答案:A
这道题暂未补解析。
8. 单选题

对有 n 个元素的二叉排序树进行中序遍历,其时间复杂度是(   )。

  • A

    O(1)

  • B

    O(log(n))

  • C

    O(n)

  • D

    O(n2)

查看答案与解析
答案:C
这道题暂未补解析。
9. 单选题

假设输入参数 m 和 n 满足m≤n,则下面程序的最差情况的时间复杂度为(   )。

  • A

    O(log(n))

  • B

    O(n)

  • C

    O(n×m)

  • D

    O(m×log(n))

查看答案与解析
答案:A
这道题暂未补解析。
10. 单选题

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

  • A

    O(n)

  • B

    O(an)

  • C

    O(log(n))

  • D

    O(log(n)×a)

查看答案与解析
答案:C
这道题暂未补解析。
11. 单选题

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

  • A

    O(2n)

  • B

    O(2m×(n-m))

  • C

    O(C(n,m))

  • D

    O(m×(n-m))

查看答案与解析
答案:D
这道题暂未补解析。
12. 单选题

下面的程序使用出边的邻接表表达有向图,则下列选项中哪个是它表达的图?(   )。

  • A
  • B
  • C
  • D
查看答案与解析
答案:B
这道题暂未补解析。
13. 单选题

下面程序的输出为(   )。

  • A

    12

  • B

    18

  • C

    36

  • D

    42

查看答案与解析
答案:B
这道题暂未补解析。
14. 单选题

下面程序的输出为(   )。

  • A

    3

  • B

    6

  • C

    11

  • D

    22

查看答案与解析
答案:A
这道题暂未补解析。
15. 单选题

下面的程序中,二维数组 h 和 v 分别代表如下图所示的网格中的水平边的时间消耗和垂直边的时间消耗。

程序使用动态规划计算从左下角到右上角的最小时间消耗,则横线处应该填写下列哪个选项的代码?(   )。

  • A

    dis[i][j] = min(dis[i - 1][j] + v[i - 1][j], dis[i][j - 1] + h[i][j - 1]);

  • B

    dis[i][j] = min(dis[i - 1][j] + h[i - 1][j], dis[i][j - 1] + v[i][j - 1]);

  • C

    dis[i + 1][j + 1] = min(dis[i][j + 1] + v[i][j + 1], dis[i + 1][j] + h[i + 1][j]);

  • D

    dis[i + 1][j + 1] = min(dis[i][j + 1] + h[i][j + 1], dis[i + 1][j] + v[i + 1][j]);

查看答案与解析
答案:C
这道题暂未补解析。

二、判断题

16. 判断题

C++语言非常强大,可以用来求解方程的解。例如,如果变量 x 为 double 类型的变量,则执行语句 x * 2- 4 = 0; 后,变量 x 的值会变为 2.0 。

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
17. 判断题

一个袋子中有3个完全相同的红色小球、2个完全相同的蓝色小球。每次从中取出1个,且不放回袋子,这样进行3次后,将取出的小球依次排列,则可能的颜色顺序有7种。

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
18. 判断题

杨辉三角,是二项式系数的一种三角形排列,在中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现,是中国数学史上的一项伟大成就。

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
19. 判断题

N个顶点的有向完全图(不带自环)有N×(N-1)/2条边。

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
20. 判断题

如果待查找的元素确定,只要哈希表的大小不小于查找元素的个数,就一定存在不会产生冲突的哈希函数。

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
21. 判断题

动态规划算法的时间复杂度一般为:必要状态的数量,乘以计算一次状态转移方程的时间复杂度。

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
22. 判断题

已知 int 类型的变量 a 、 b 和 h 中分别存储着一个梯形的顶边长、底边长和高,则这个梯形的面积可以通过表达式 (a + b) * h / 2 求得。

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
23. 判断题

判断图是否连通只能用广度优先搜索算法实现。

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
24. 判断题

在 个元素的二叉排序树中查找一个元素,最好情况的时间复杂度是O(logN)。

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
25. 判断题

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

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。

三、简答题

26. 简答题

奖品分配

时间限制:1.0 s

内存限制:128.0 MB

问题描述

班上有N名同学,学号从0到N-1。有 种奖品要分给这些同学,其中,第M种奖品总共有ai个(i=0,1,…,M-1)。巧合的是,奖品的数量不多不少,每位同学都可以恰好分到一个奖品,且最后剩余的奖品不超过1个(即:N≤a0+a1+…+aM-1≤N+1)。

现在,请你求出每个班级礼物分配的方案数,所谓方案,指的是为每位同学都分配一个种类的奖品。只要有一位同学获得了不同种类的奖品,即视为不同的方案。方便起见,你只需要输出方案数对109+7取模后的结果即可。

共有T个班级都面临着奖品分配的问题,你需要依次为他们解答。

输入描述

第一行一个整数T,表示班级数量。

接下来 行,每行若干用单个空格隔开的正整数。首先是两个正整数N,M,接着是M个正整数a0,a1,…,aM-1。

保证N≤a0+a1+…+aM-1≤N+1。

输出描述

输出T行,每行一个整数,表示该班级分配奖品的方案数对109+7取模的结果。

特别提醒

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


样例输入 1

3
3 2 1 2
3 2 1 3
5 3 3 1 1

样例输出 1

3
4
20

样例解释 1

对于第 1 个班级,学号为0,1,2的同学可以依次分别获得奖品0,1,1,也可以依次分别获得奖品1,0,1,也可以依次分别获得奖品1,1,0,因此共有3种方案。

对于第 2 个班级,学号为0,1,2的同学可以依次分别获得奖品0,1,1,也可以依次分别获得奖品1,0,1,也可以依次分别获得奖品1,1,0,也可以依次分别获得奖品1,1,1,因此共有4种方案。

对于第 3 个班级,可以把编号为1的奖品分配给5名同学中的任意一名,共有5种方案;再把编号为2的奖品分配给剩余4名同学中的任意一名,共有4种方案;最后给剩余3名同学自然获得0号奖品。因此,方案数为5×4=20。


样例输入 2

5
100 1 100
100 1 101
20 2 12 8
123 4 80 20 21 3
999 5 101 234 499 66 99

样例输出 2

1
1
125970
895031741
307187590

数据规模

对于30%的测试点,保证N≤10。

对于另外30%的测试点,保证M=2。

对于所有测试点,保证N≤1000;保证T≤1000;保证M≤1000。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;cmath&gt; #include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;map&gt; #include &lt;string&gt; #include &lt;vector&gt; using namespace std; const int N = 1005; const int mod = 1e9 + 7; int C[N + 5][N + 5], a[N + 5]; void add(int &amp;a, int b) {   a += b;   if (a &gt;= mod)     a -= mod; } void init() {   C[0][0] = 1;   for (int i = 1; i &lt;= N; i++) {     C[i][0] = C[i][i] = 1;     for (int j = 1; j &lt; i; j++)       C[i][j] = C[i - 1][j - 1], add(C[i][j], C[i - 1][j]);   } } int main() {   // freopen("data/10.in", "r", stdin);   init();   int T;   scanf("%d", &amp;T);   while (T--) {     int n, m, sum = 0;     scanf("%d%d", &amp;n, &amp;m);     for (int i = 1; i &lt;= m; i++)       scanf("%d", &amp;a[i]), sum += a[i];     int ans = 1;     for (int i = 1; i &lt;= m; i++) {       ans = 1ll * ans * C[sum][a[i]] % mod;       sum -= a[i];     }     cout &lt;&lt; ans &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。
27. 简答题

大量的工作沟通

时间限制:2.0 s

内存限制:128.0 MB

问题描述

某公司有N名员工,编号从0至N-1。其中,除了0号员工是老板,其余每名员工都有一个直接领导。我们假设编号为i的员工的直接领导是fi。

该公司有严格的管理制度,每位员工只能受到本人或直接领导或间接领导的管理。具体来说,规定员工x可以管理员工y,当且仅当x=y,或f=fy,或x可以管理fy。特别地,0号员工老板只能自我管理,无法由其他任何员工管理。

现在,有一些同事要开展合作,他们希望找到一位同事来主持这场合作,这位同事必须能够管理参与合作的所有同事。如果有多名满足这一条件的员工,他们希望找到编号最大的员工。你能帮帮他们吗?

输入描述

第一行一个整数N,表示员工的数量。

第二行N-1个用空格隔开的正整数,依次为f1,f2…,fN-1。

第三行一个整数Q,表示共有Q场合作需要安排。

接下来Q行,每行描述一场合作:开头是一个整数m(2≤m≤N),表示参与本次合作的员工数量;接着是m个整数,依次表示参与本次合作的员工编号(保证编号合法且不重复)。

保证公司结构合法,即不存在任意一名员工,其本人是自己的直接或间接领导。

输出描述

输出Q行,每行一个整数,依次为每场合作的主持人选。

特别提醒

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


样例输入 1

5
0 0 2 2
3
2 3 4
3 2 3 4
2 1 4

样例输出 1

2
2
0

样例解释 1

对于第一场合作,员工3,4有共同领导2,可以主持合作。

对于第二场合作,员工2本人即可以管理所有参与者。

对于第三场合作,只有0号老板才能管理所有员工。


样例输入 2

7
0 1 0 2 1 2
5
2 4 6
2 4 5
3 4 5 6
4 2 4 5 6
2 3 4

样例输出 2

2
1
1
1
0

数据规模

对于25%的测试点,保证N≤50。

对于50%的测试点,保证N≤300。

对于所有测试点,保证3≤N≤105;保证Q≤100,保证m≤104。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;cmath&gt; #include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;map&gt; #include &lt;queue&gt; #include &lt;string&gt; #include &lt;vector&gt; using namespace std; const int N = 100005; int fa[N], sz[N], dep[N], son[N], tp[N], mxId[N]; int cnt, fir[N], tar[N], nxt[N]; void link(int a, int b) { tar[++cnt] = b, nxt[cnt] = fir[a], fir[a] = cnt; } void dfs(int x, int mxid) {   int Mx = 0;   sz[x] = 1;   mxId[x] = max(x, mxid);   for (int i = fir[x]; i; i = nxt[i]) {     dep[tar[i]] = dep[x] + 1;     dfs(tar[i], mxId[x]);     sz[x] += sz[tar[i]];     if (Mx &lt; sz[tar[i]])       Mx = sz[son[x] = tar[i]];   } } void gettp(int x) {   tp[x] = x;   if (son[fa[x]] == x)     tp[x] = tp[fa[x]];   for (int i = fir[x]; i; i = nxt[i])     gettp(tar[i]); } int lca(int x, int y) {   while (tp[x] != tp[y])     dep[tp[x]] &gt; dep[tp[y]] ? x = fa[tp[x]] : y = fa[tp[y]];   return dep[x] &lt; dep[y] ? x : y; } int main() {   int n;   scanf("%d", &amp;n);   for (int i = 2; i &lt;= n; i++)     scanf("%d", &amp;fa[i]), link(++fa[i], i);   dfs(1, 1), gettp(1);   int q;   scanf("%d", &amp;q);   while (q--) {     int m, x, y;     scanf("%d%d", &amp;m, &amp;x), x++;     for (int i = 2; i &lt;= m; i++)       scanf("%d", &amp;y), x = lca(x, ++y);     cout &lt;&lt; mxId[x] - 1 &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。