GESP 2024年 9月认证 C++ 七级真题

题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 答案 B D C C A C A B D D A C D B A C++　七级 2024 年 09 ⽉ 1 单选题（每题 2 分，共 30 分） 第 1 题 已知⼩写字母 b 的ASCII码为98，下列C++代码的输出结果是（ ）。 A. b B. c C. 98 D. 99 第 2 题 已知 a 为 int 类型变量，下列表达式不符合语法的是（ ）。 A. &a + 3 B. +a & 3 C. a - - 4 D. a++3 第 3 题 下列关于C++语⾔中指针的叙述，不正确的是（ ）。 A. 指针变量中存储的是内存地址。 B. 指针变量指向的内存地址不⼀定能够合法访问。 C. 结构类型中的指针成员不能指向该结构类型。 D. 定义指针变量时必须指定其指向的类型。 第 4 题 下列关于C++类的说法，错误的是( )。 #include <iostream> using namespace std; int main() { char a = 'b'; a++; cout << a; return 0; } 1 2 3 4 5 6 7 8 A. 将C++类对象通过值传递给函数参数时，会⾃动调⽤复制构造函数。 B. 将⼀个类的对象赋值给该类的另⼀个对象时，不会⾃动调⽤构造函数。 C. 定义C++类对象时，⼀定会调⽤默认构造函数。 D. 构造派⽣类的对象时，⼀定会调⽤基类的构造函数。 第 5 题 某⼆叉树T的先序遍历序列为：{A B D C E G H F}，中序遍历序列为：{D B A H G E C F}，则下列说法中正 确的是( )。 A. T的⾼为5 B. T有4个叶节点 C. T是平衡树 D. 以上说法都不对 第 6 题 ⼀棵完全⼆叉树有431个结点，则叶结点有多少个？( ) A. 176 B. 215 C. 216 D. 255 第 7 题 下列关于树的说法，错误的是（ ）。 A. ⼆叉树的中序遍历与其深度优先遍历总是相同的。 B. 所有树都可以构造⼀颗⼆叉树与之⼀⼀对应。 C. 如果树的⼀个叶结点有两个不同的祖先结点，那么其中⼀个⼀定是另⼀个的祖先结点。 D. 树的结点不能有两个⽗结点。 第 8 题 ⼀个简单⽆向图有10个结点、30条边。再增加多少条边可以成为完全图。（ ） A. 10 B. 15 C. 51 D. 60 第 9 题 以下哪个⽅案可以合理解决或缓解哈希表冲突（ ）。 A. 丢弃发⽣冲突的新元素。 B. ⽤新元素覆盖发⽣冲突的元素。 C. ⽤新元素覆盖在冲突位置的下⼀个位置。 D. 将新元素放置在冲突位置之后的第⼀个空位。 第 10 题 ⼀个迷宫，已知从起点不经过重复结点到达终点的路径有且仅有⼀条，则下⾯说法错误的是（ ）。 A. 可以使⽤深度优先搜索找到这条路径。 B. 可以使⽤⼴度优先搜索找到这条路径。 C. 该迷宫内与起点连通的结点，⼀定也与终点连通。 D. 该迷宫内与起点连通的结点及它们之间的路径可以抽象为⽆向⽆环图。 第 11 题 下⾯程序的输出为（ ）。 A. 2 B. 3 C. 8 D. ⽆法通过编译。 第 12 题 下⾯程序的输出为（ ）。 A. 84 B. 495 C. 1012 D. 结果是随机的。 第 13 题 上题中程序的时间复杂度为（ ）。 A. B. #include <iostream> #include <cmath> using namespace std; int main() { cout << (int)log(8) << endl; return 0; } 1 2 3 4 5 6 7 #include <iostream> #define N 10 using namespace std; int path[N][N]; int main() { for (int i = 1; i < N; i++) path[i][0] = i; for (int j = 1; j < N; j++) path[0][j] = j; for (int i = 1; i < N; i++) for (int j = 1; j < N; j++) path[i][j] = path[i - 1][j] + path[i][j - 1]; cout << path[8][4] << endl; return 0; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 题号 1 2 3 4 5 6 7 8 9 10 答案 C. D. 第 14 题 下⾯ fib 函数的时间复杂度为( )。 A. B. , C. D. ⽆法正常结束。 第 15 题 下列选项中，哪个可能是下图的⼴度优先遍历序列（ ）。 A. 1, 3, 5, 7, 4, 2, 6, 8, 9 B. 9, 4, 2, 1, 3, 7, 5, 6, 8 C. 1, 3, 5, 7, 6, 8, 9, 4, 2 D. 9, 4, 7, 2, 1, 3, 5, 6, 8 2 判断题（每题 2 分，共 20 分） 第 1 题 表达式 'a' << 1 的结果为 'a ' 。 第 2 题 在C++语⾔中，函数可以定义在另⼀个函数定义之内。 第 3 题 选择排序⼀般是不稳定的。 第 4 题 埃⽒筛法和欧拉筛法都是使⽤筛法思想⽣成素数表的算法，欧拉筛法的时间复杂度更低。 第 5 题 使⽤ math.h 或 cmath 头⽂件中的正弦函数，表达式 sin(30) 的结果类型为 double 、值约为 0.5 。 int fib_rcd[MAX_N]; int fib(int n) { if (n <= 1) return 1; if (fib_rcd[n] > 0) return fib_rcd[n]; return fib(n - 1) + fib(n - 2); } 1 2 3 4 5 6 7 8 第 6 题 ⼀颗 层的完全⼆叉树，⼀定有 个结点。 第 7 题 ⼀个图，不管是否连通，都可以使⽤深度优先搜索算法进⾏遍历。 第 8 题 某个哈希表键值 x 为整数， H(x) = x % p 是常⽤的哈希函数之⼀，要求 p 选择素数是因为这样不会产⽣ 冲突。( ) 第 9 题 使⽤单链表实现队列时，链表头结点作为队⾸⽐链表头结点作为队尾更便于操作。 第 10 题 ⼀个图中，每个结点表达⼀个⼈，连接两个结点的边表达两个结点对应的⼈相互认识，则这个图可以⽤来 表达社交⽹络。 3 编程题（每题 25 分，共 50 分） 3.1 编程题 1 试题名称：⼩杨寻宝 时间限制：1.0 s 内存限制：512.0 MB 3.1.1 题面描述 ⼩杨有⼀棵包含 个节点的树，树上的⼀些节点放置有宝物。 ⼩杨可以任意选择⼀个节点作为起点并在树上移动，但是⼩杨只能经过每条边⾄多⼀次，当⼩杨经过⼀条边后，这 条边就会消失。⼩杨每经过⼀个放置有宝物的节点就会取得该宝物。 ⼩杨想请你帮他判断⾃⼰能否成功取得所有宝物。 3.1.2 输入格式 第⼀⾏包含⼀个正整数 ，代表测试⽤例组数。 接下来是 组测试⽤例。对于每组测试⽤例，⼀共 ⾏。 第⼀⾏包含⼀个正整数 ，代表树的节点数。 第⼆⾏包含 个⾮负整数 ，其中如果 ，则节点 放置有宝物，若 ，则节点 没有宝物。 之后 ⾏，每⾏包含两个正整数 ，代表存在⼀条连接节点 和 的边。 3.1.3 输出格式 对于每组测试数据，如果⼩杨能成功取得所有宝物，输出 Yes，否则输出 No。 子任务编号 数据点占比 1 20% 2 20% 3 60% 3.1.4 样例1 对于第⼀组测试⽤例，⼩杨从节点 出发，按照 的顺序即可成功取得所有宝物。 对于全部数据，保证有 ，且保证树上⼀定有⾄少⼀个节点放置有宝物。， 3.1.5 参考程序 2 5 0 1 0 1 0 1 2 1 3 3 4 3 5 5 1 1 1 1 1 1 2 1 3 3 4 3 5 1 2 3 4 5 6 7 8 9 10 11 12 13 Yes No 1 2 #include<bits/stdc++.h> using namespace std; const int N = 1e5+10; vector<int> g[N]; int col[N],dep[N],has[N]; void dfs(int x,int fa){ dep[x]=dep[fa]+1; for(auto i:g[x]){ if(i!=fa){ dfs(i,x); } } } bool dfs2(int x,int fa){ for(auto i:g[x]){ if(i!=fa){ auto res = dfs2(i,x); if(res==false)return false; if(has[i]||col[i])has[x]++; } } if(has[x]>1)return false; return true; } int main(){ 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 3.2 编程题 2 试题名称：矩阵移动 时间限制：1.0 s 内存限制：512.0 MB 3.2.1 题面描述 ⼩杨有⼀个有⼀个 的矩阵，仅包含 01? 三种字符。矩阵的⾏从上到下编号依次为 ，列从左到右编号 依次为 编号。⼩杨开始在矩阵的左上角（ ），⼩杨只能向下或者向右移动，最终到达右下角（ ） 时停⽌，在移动的过程中每经过⼀个字符 1 得分会增加⼀分（包括起点和终点），经过其它字符则分数不变。⼩杨 的初始分数为 分。 ⼩杨可以将矩阵中不超过 个字符 ? 变为字符 1。⼩杨在修改矩阵后，会以最优的策略从左上角移动到右下角。他想 知道⾃⼰最多能获得多少分。 3.2.2 输入格式 第⼀⾏包含⼀个正整数 ，代表测试⽤例组数。 接下来是 组测试⽤例。对于每组测试⽤例，⼀共 ⾏。 第⼀⾏包含三个正整数 ，含义如题⾯所⽰。 int t; cin>>t; while(t--){ int n; cin>>n; for(int i=1;i<=n;i++){ dep[i]=0;g[i].clear(); cin>>col[i]; } for(int i=1;i<n;i++){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } dfs(1,0); int mx=0,pos=0; for(int i=1;i<=n;i++){ has[i]=0; if(col[i]){ if(dep[i]>mx){ mx=dep[i]; pos=i; } } } bool res= dfs2(pos,0); if(res)cout<<"Yes "; else cout<<"No "; } } 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 子任务编号 数据点占比 1 30% 2 30% 3 40% 之后 ⾏，每⾏包含⼀个长度为 且仅包含 01? 三种字符的字符串。 3.2.3 输出格式 对于每组测试⽤例，输出⼀⾏⼀个整数，代表最优策略下⼩杨的得分最多是多少。 3.2.4 样例1 对于第⼆组测试⽤例，将（ ）或者 （ ）变成 均是最优策略。 对于全部数据，保证有 ，同时保证所有测试⽤例 的总和不超过 。 ， 3.2.5 参考程序 2 3 3 1 000 111 01? 3 3 1 000 ?0? 01? 1 2 3 4 5 6 7 8 9 4 2 1 2 #include<bits/stdc++.h> using namespace std; const int N = 505; int dp[N][1005]; char a[N][N]; int n, m, x; int main(){ int t; scanf("%d", &t); while(t--){ scanf("%d%d%d", &n, &m, &x); for(int i = 1; i <= m; i++) for(int j = 0; j <= x; j++) dp[i][j] = 0; for(int i = 1; i <= n; i++) scanf("%s", a[i] + 1); for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ for(int k = x; k>=0; k--){ if(a[i][j] == '1') dp[j][k] = max(dp[j][k], dp[j - 1][k]) + 1; if(a[i][j] == '0') dp[j][k] = max(dp[j][k], dp[j - 1][k]); if(a[i][j] == '?') { if(!k) dp[j][k] = max(dp[j][k], dp[j - 1][k]); 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 else dp[j][k] = max(max(dp[j][k], dp[j - 1][k]), max(dp[j][k - 1], dp[j - 1][k - 1]) + 1); } } } } int ans = 0; for(int k = 0; k <= x; k++) ans = max(ans, dp[m][k]); printf("%d ", ans); } } 23 24 25 26 27 28 29 30 31 32 33