2023.12中国计算机学会GESP等级考试c++八级

题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 答案 C A D B C D A C A C D B B A C C++　八级 2023 年 12 ⽉ 1 单选题（每题 2 分，共 30 分） 第 1 题 ⼩杨要从A城到B城，⼜想顺路游览⼀番。他有两个选项：1、坐⾼铁路到C城游览，再坐⾼铁或飞机到B城； 2、坐船到D城游览，再坐船、⾼铁或飞机到B城。请问⼩杨从A城到B城共有⼏种交通⽅案可以选择？（ ）。 A. 2 B. 3 C. 5 D. 6 第 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); 第 3 题 下⾯有关C++类和对象的说法，错误的是（ ）。 A. 对象的⽣命周期开始时，会执⾏构造函数。 B. 对象的⽣命周期结束时，会执⾏析构函数。 C. 类的析构函数可以为虚函数。 D. 类的构造函数可以为虚函数。 第 4 题 使⽤邻接矩阵表达 n 个顶点的有向图，则该矩阵的⼤⼩为（ ）。 A. B. C. D. 第 5 题 5 位同学排队，其中⼀位同学不能排在第⼀，则共有多少种可能的排队⽅式？（ ）。 A. 5 B. 24 C. 96 D. 120 第 6 题 ⼀个⽆向图包含 n 个顶点，则其最⼩⽣成树包含多少条边？（ ）。 A. B. C. 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)) 第 8 题 对有 n 个元素的⼆叉排序树进⾏中序遍历，其时间复杂度是（ ）。 A. B. C. D. 第 9 题 假设输⼊参数 m 和 n 满⾜ ，则下⾯程序的最差情况的时间复杂度为（ ）。 A. B. C. D. 第 10 题 下⾯程序的时间复杂度为（ ）。 A. B. C. D. 第 11 题 下⾯程序的时间复杂度为（ ）。 A. B. C. D. 第 12 题 下⾯的程序使⽤出边的邻接表表达有向图，则下列选项中哪个是它表达的图？（ ）。 A. B. C. D. 第 13 题 下⾯程序的输出为（ ）。 A. 12 B. 18 C. 36 D. 42 第 14 题 下⾯程序的输出为（ ）。 A. 3 B. 6 C. 11 D. 22 第 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]); 题号 1 2 3 4 5 6 7 8 9 10 答案 D. dis[i + 1][j + 1] = min(dis[i][j + 1] + h[i][j + 1], dis[i + 1][j] + v[i + 1][j]); 2 判断题（每题 2 分，共 20 分） 第 1 题 C++语⾔⾮常强⼤，可以⽤来求解⽅程的解。例如，如果变量 x 为 double 类型的变量，则执⾏语句 x * 2 - 4 = 0; 后，变量 x 的值会变为 2.0 。 第 2 题 ⼀个袋⼦中有3个完全相同的红⾊⼩球、2个完全相同的蓝⾊⼩球。每次从中取出1个，且不放回袋⼦，这样 进⾏3次后，将取出的⼩球依次排列，则可能的颜⾊顺序有7种。 第 3 题 杨辉三角，是⼆项式系数的⼀种三角形排列，在中国南宋数学家杨辉1261年所著的《详解九章算法》⼀书中 出现，是中国数学史上的⼀项伟⼤成就。 第 4 题 个顶点的有向完全图（不带⾃环）有 条边。 第 5 题 如果待查找的元素确定，只要哈希表的⼤⼩不⼩于查找元素的个数，就⼀定存在不会产⽣冲突的哈希函数。 第 6 题 动态规划算法的时间复杂度⼀般为：必要状态的数量，乘以计算⼀次状态转移⽅程的时间复杂度。 第 7 题 已知 int 类型的变量 a 、 b 和 h 中分别存储着⼀个梯形的顶边长、底边长和⾼，则这个梯形的⾯积可以通 过表达式 (a + b) * h / 2 求得。 第 8 题 判断图是否连通只能⽤⼴度优先搜索算法实现。 第 9 题 在 个元素的⼆叉排序树中查找⼀个元素，最好情况的时间复杂度是 。 第 10 题 给定 double 类型的变量 x ，且其值⼤于等于 ，我们可以通过⼆分法求出 的近似值。 3 编程题（每题 25 分，共 50 分） 3.1 编程题 1 试题名称：奖品分配 时间限制：1.0 s 内存限制：128.0 MB 3.1.1 问题描述 班上有 名同学，学号从 到 。有 种奖品要分给这些同学，其中，第 种奖品总共有 个（ ）。巧合的是，奖品的数量不多不少，每位同学都可以恰好分到⼀个奖品，且最后剩余的奖品不 超过 个（即： ）。 现在，请你求出每个班级礼物分配的⽅案数，所谓⽅案，指的是为每位同学都分配⼀个种类的奖品。只要有⼀位同 学获得了不同种类的奖品，即视为不同的⽅案。⽅便起见，你只需要输出⽅案数对 取模后的结果即可。 共有 个班级都⾯临着奖品分配的问题，你需要依次为他们解答。 3.1.2 输入描述 第⼀⾏⼀个整数 ，表⽰班级数量。 接下来 ⾏，每⾏若⼲⽤单个空格隔开的正整数。⾸先是两个正整数 ，接着是 个正整数 。 保证 。 3.1.3 输出描述 输出 ⾏，每⾏⼀个整数，表⽰该班级分配奖品的⽅案数对 取模的结果。 3.1.4 特别提醒 在常规程序中，输⼊、输出时提供提⽰是好习惯。但在本场考试中，由于系统限定，请不要在输⼊、输出中附带任 何提⽰信息。 3.1.5 样例输入 1 3.1.6 样例输出 1 3.1.7 样例解释 1 对于第 1 个班级，学号为 的同学可以依次分别获得奖品 ，也可以依次分别获得奖品 ，也可以依次 分别获得奖品 ，因此共有 种⽅案。 对于第 2 个班级，学号为 的同学可以依次分别获得奖品 ，也可以依次分别获得奖品 ，也可以依次 分别获得奖品 ，也可以依次分别获得奖品 ，因此共有 种⽅案。 对于第 3 个班级，可以把编号为 的奖品分配给 名同学中的任意⼀名，共有 种⽅案；再把编号为 的奖品分配 给剩余 名同学中的任意⼀名，共有 种⽅案；最后给剩余 名同学⾃然获得 号奖品。因此，⽅案数为 。 3.1.8 样例输入 2 3 3 2 1 2 3 2 1 3 5 3 3 1 1 1 2 3 4 3 4 20 1 2 3 5 100 1 100 100 1 101 20 2 12 8 123 4 80 20 21 3 999 5 101 234 499 66 99 1 2 3 4 5 6 3.1.9 样例输出 2 3.1.10 数据规模 对于30%的测试点，保证 。 对于另外30%的测试点，保证 。 对于所有测试点，保证 ；保证 ；保证 。 3.1.11 参考程序 1 1 125970 895031741 307187590 1 2 3 4 5 #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <string> #include <map> #include <iostream> #include <cmath> #include <vector> using namespace std; const int N = 1005; const int mod = 1e9 + 7; int C[N + 5][N + 5], a[N + 5]; void add(int &a, int b) { a += b; if(a >= mod) a -= mod; } void init() { C[0][0] = 1; for(int i = 1; i <= N; i ++) { C[i][0] = C[i][i] = 1; for(int j = 1; j < 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", &T); while(T --) { int n, m, sum = 0; scanf("%d%d", &n, &m); for(int i = 1; i <= m; i ++) scanf("%d", &a[i]), sum += a[i]; int ans = 1; for(int i = 1; i <= m; i ++) { ans = 1ll * ans * C[sum][a[i]] % mod; 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 3.2 编程题 2 试题名称：⼤量的⼯作沟通 时间限制：2.0 s 内存限制：128.0 MB 3.2.1 问题描述 某公司有 名员⼯，编号从 ⾄ 。其中，除了 号员⼯是⽼板，其余每名员⼯都有⼀个直接领导。我们假设 编号为 的员⼯的直接领导是 。 该公司有严格的管理制度，每位员⼯只能受到本⼈或直接领导或间接领导的管理。具体来说，规定员⼯ 可以管理 员⼯ ，当且仅当 ，或 ，或 可以管理 。特别地， 号员⼯⽼板只能⾃我管理，⽆法由其他任何员⼯ 管理。 现在，有⼀些同事要开展合作，他们希望找到⼀位同事来主持这场合作，这位同事必须能够管理参与合作的所有同 事。如果有多名满⾜这⼀条件的员⼯，他们希望找到编号最⼤的员⼯。你能帮帮他们吗？ 3.2.2 输入描述 第⼀⾏⼀个整数 ，表⽰员⼯的数量。 第⼆⾏ 个⽤空格隔开的正整数，依次为 。 第三⾏⼀个整数 ，表⽰共有 场合作需要安排。 接下来 ⾏，每⾏描述⼀场合作：开头是⼀个整数 （ ），表⽰参与本次合作的员⼯数量；接着是 个整数，依次表⽰参与本次合作的员⼯编号（保证编号合法且不重复）。 保证公司结构合法，即不存在任意⼀名员⼯，其本⼈是⾃⼰的直接或间接领导。 3.2.3 输出描述 输出 ⾏，每⾏⼀个整数，依次为每场合作的主持⼈选。 3.2.4 特别提醒 在常规程序中，输⼊、输出时提供提⽰是好习惯。但在本场考试中，由于系统限定，请不要在输⼊、输出中附带任 何提⽰信息。 3.2.5 样例输入 1 sum -= a[i]; } cout << ans << endl; } return 0; } 39 40 41 42 43 44 5 0 0 2 2 3 2 3 4 3 2 3 4 2 1 4 1 2 3 4 5 6 3.2.6 样例输出 1 3.2.7 样例解释 1 对于第⼀场合作，员⼯ 有共同领导 ，可以主持合作。 对于第⼆场合作，员⼯ 本⼈即可以管理所有参与者。 对于第三场合作，只有 号⽼板才能管理所有员⼯。 3.2.8 样例输入 2 3.2.9 样例输出 2 3.2.10 数据规模 对于25%的测试点，保证 。 对于50%的测试点，保证 。 对于所有测试点，保证 ；保证 ，保证 。 3.2.11 参考程序 2 2 0 1 2 3 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 1 2 3 4 5 6 7 8 2 1 1 1 0 1 2 3 4 5 #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <string> #include <map> #include <iostream> #include <cmath> #include <vector> #include <queue> 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]; 1 2 3 4 5 6 7 8 9 10 11 12 13 14 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 < 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]] > dep[tp[y]] ? x = fa[tp[x]] : y = fa[tp[y]]; return dep[x] < dep[y] ? x : y; } int main() { int n; scanf("%d", &n); for(int i = 2; i <= n; i ++) scanf("%d", &fa[i]), link(++ fa[i], i); dfs(1, 1), gettp(1); int q; scanf("%d", &q); while(q --) { int m, x, y; scanf("%d%d", &m, &x), x ++; for(int i = 2; i <= m; i ++) scanf("%d", &y), x = lca(x, ++ y); cout << mxId[x] - 1 << endl; } return 0; } 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59