2024年9月GESP编程能力认证C++等级考试七级真题(含答案和解析-在末尾)

2024年9月GESP编程能力认证C++等级考试七级真题(含答案和解析-在末尾)一、单选题（每题2分，共30分）。1.已知小写字母b的ASCII码为98，下列C++代码的输出结果是（）。#include<iostream>usingnamespacestd;intmain(){chara='b';a++;cout<<a;return0;}A.bB.cC.98D.992.已知a为int类型变量，下列表达式不符合语法的是（）。3.下列关于C++语言中指针的叙述，不正确的是（）。A.指针变量中存储的是内存地址。B.指针变量指向的内存地址不一定能够合法访问。C.结构类型中的指针成员不能指向该结构类型。D.定义指针变量时必须指定其指向的类型。4.下列关于C++类的说法，错误的是（）。A.将C++类对象通过值传递给函数参数时，会自动调用复制构造函数。B.将一个类的对象赋值给该类的另一个对象时，不会自动调用构造函数。C.定义C++类对象时，一定会调用默认构造函数。D.构造派生类的对象时，一定会调用基类的构造函数。5.某二叉树T的先序遍历序列为{ABDCEGHF}，中序遍历序列为{DBAHGECF}，则下列说法中正确的是（）。A.T的高为5B.T有4个叶节点C.T是平衡树D.以上说法都不对6.一棵完全二叉树有431个结点，则叶结点有多少个（）。A.176B.215C.216D.2557.下列关于树的说法，错误的是（）。A.二叉树的中序遍历与其深度优先遍历总是相同的。B.所有树都可以构造一颗二叉树与之一一对应。C.如果树的一个叶结点有两个不同的祖先结点，那么其中一个一定是另一个的祖先结点。D.树的结点不能有两个父结点。8.一个简单无向图有10个结点、30条边。再增加多少条边可以成为完全图（）。A.10B.15C.51D.609.以下哪个方案可以合理解决或缓解哈希表冲突（）。A.丢弃发生冲突的新元素。B.用新元素覆盖发生冲突的元素。C.用新元素覆盖在冲突位置的下一个位置。D.将新元素放置在冲突位置之后的第一个空位。10.一个迷宫，已知从起点不经过重复结点到达终点的路径有且仅有一条，则下面说法错误的是（）。A.可以使用深度优先搜索找到这条路径。B.可以使用广度优先搜索找到这条路径。C.该迷宫内与起点连通的结点，一定也与终点连通。D.该迷宫内与起点连通的结点及它们之间的路径可以抽象为无向无环图。11.下面程序的输出为（）。A.2B.3C.8D.无法通过编译。12.下面程序的输出为（）。#include<iostream>#defineN10usingnamespacestd;intpath[N][N];intmain(){for(inti=1;i<N;i++)path[i][0]=i;for(intj=1;j<N;j++)path[0][j]=j;for(inti=1;i<N;i++)for(intj=1;j<N;j++)path[i][j]=path[i-1][j]+path[i][j-1];cout<<path[8][4]<<endl;return0;}A.84B.495C.1012D.结果是随机的。13.上题中程序的时间复杂度为（）。14.下面fib函数的时间复杂度为（）。intfib_rcd[MAX_N];intfib(intn){if(n<=1)return1;if(fib_rcd[n]>0)returnfib_rcd[n];returnfib(n-1)+fib(n-2);}A.O(n)B.C.O(2n)D.无法正常结束。15.下列选项中，哪个可能是下图的广度优先遍历序列（）。二、判断题（每题2分，共20分）。16.表达式'a'<<1的结果为'a'。（）。A.正确B.错误17.在C++语言中，函数可以定义在另一个函数定义之内（）。A.正确B.错误18.选择排序一般是不稳定的（）。A.正确B.错误19.埃氏筛法和欧拉筛法都是使用筛法思想生成素数表的算法，欧拉筛法的时间复杂度更低（）。A.正确B.错误20.使用math.h或cmath头文件中的正弦函数，表达式sin(30)的结果类型为double、值约为0.5。（）。A.正确B.错误21.一颗N层的完全二叉树，一定有2N-1个结点（）。A.正确B.错误22.一个图，不管是否连通，都可以使用深度优先搜索算法进行遍历（）。A.正确B.错误23.某个哈希表键值x为整数，H(x)=x%p是常用的哈希函数之一，要求p选择素数是因为这样不会产生冲突（）。A.正确B.错误24.使用单链表实现队列时，链表头结点作为队首比链表头结点作为队尾更便于操作（）。A.正确B.错误25.一个图中，每个结点表达一个人，连接两个结点的边表达两个结点对应的人相互认识，则这个图可以用来表达社交网络（）。A.正确B.错误三、编程题（每题25分，共50分）。26.试题名称：小杨寻宝。时间限制：1.0s。内存限制：512.0MB。题面描述：小杨有一棵包含n个节点的树，树上的一些节点放置有宝物。小杨可以任意选择一个节点作为起点并在树上移动，但是小杨只能经过每条边至多一次，当小杨经过一条边后，这条边就会消失。小杨每经过一个放置有宝物的节点就会取得该宝物。小杨想请你帮他判断自己能否成功取得所有宝物。输入格式：第一行包含一个正整数t，代表测试用例组数。接下来是t组测试用例。对于每组测试用例，一共n+1行。第一行包含一个正整数n，代表树的节点数。第二行包含n个非负整数a1，a2，……，an，其中如果ai=1，则节点i放置有宝物，若ai=0，则节点i没有宝物。之后n-1行，每行包含两个正整数xi，yi，代表存在一条连接节点xi和yi的边。输出格式：对于每组测试数据，如果小杨能成功取得所有宝物，输出Yes，否则输出No。样例1。对于第一组测试用例，小杨从节点2出发，按照2-1-3-4的顺序即可成功取得所有宝物。对于全部数据，保证有1≤t≤10，1≤n≤105，0≤ai≤1，且保证树上一定有至少一个节点放置有宝物。27.试题名称：矩阵移动。时间限制：1.0s。内存限制：512.0MB。题面描述：小杨有一个有一个n×m的矩阵，仅包含01?三种字符。矩阵的行从上到下编号依次为1，2，……，n，列从左到右编号依次为1，2，……，m编号。小杨开始在矩阵的左上角(1，1)，小杨只能向下或者向右移动，最终到达右下角(n，m)时停止，在移动的过程中每经过一个字符1得分会增加一分(包括起点和终点)，经过其它字符则分数不变。小杨的初始分数为0分。小杨可以将矩阵中不超过x个字符?变为字符1。小杨在修改矩阵后，会以最优的策略从左上角移动到右下角。他想知道自己最多能获得多少分。输入格式：第一行包含一个正整数t，代表测试用例组数。接下来是t组测试用例。对于每组测试用例，一共n+1行。第一行包含三个正整数n，m，x，含义如题面所示。之后n行，每行包含一个长度为m且仅包含01?三种字符的字符串。输出格式：对于每组测试用例，输出一行一个整数，代表最优策略下小杨的得分最多是多少。样例1。对于第二组测试用例，将(1，1)或者(3，3)变成1均是最优策略。对于全部数据，保证有1≤t≤10，1≤n，m≤500，1≤x≤300，同时保证所有测试用例n×m的总和不超过2.5×105。答案如下。1.答案：B。解析：在C++中，字符在计算机中是整数存储，小写字母b的ASCII码为98，对a进行自增操作时，其ASCII码增加到99，程序输出的是ASCII码值为99的字符，即小写字母c。2.答案：D。解析：a++3是语法错误，因为a++作为一个整体，其结果不能直接与其它数值进行连接。3.答案：C。解析：结构体类型中的指针成员是可以指向该结构类型的，常见操作如链表。4.答案：C。解析：如果类中定义了其他构造函数（如有参数的构造函数）但没有定义默认构造函数，且在创建对象时没有提供初始化参数，则不会调用默认构造函数，甚至可能导致编译错误。5.答案：A。解析：先序可以确定根节点，中序可以确定左右子树节点，根据先序和中序可以构造一棵唯一的二叉树。如果根节点高度为1，则这棵二叉树的高度为5，有三个叶子节点。A选择对，B选项错。平衡树：一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。所以C选项错。6.答案：C。解析：深度为8的满二叉树共有28-1（255）个结点。深度为9的满二叉树共有29-1（511）个结点。一棵拥有431个结点的完全二叉树，深度为9。第9层结点数量431-255=176（都是叶结点）。第八层总结点数量2(8-1)=128，第8层中为叶结点的数量128-176/2=40，所以这棵二叉树叶结点176+40=216。7.答案：A。解析：深度优先搜索是一个更广泛概念，包括三种不同的遍历方式——前序遍历、中序遍历、后序遍历。虽然中序遍历是深度优先搜索的一种形式，所以不能说二叉树的中序遍与其深度优先搜索遍历总是相同的。8.答案：B。解析：n个结点的完全无向图，最多有n*(n-1)/2条边。10个结点最多：10*9/2=45条边，所以还需要15条边。9.答案：D。解析：在哈希表中，冲突（也称碰撞）是指两个不同的键被映射到哈希表的同一位置。A选项，这个方案显然不是一个好的解决策略，因为它会导致信息丢失。如果频繁发生冲突，大量新元素将被丢弃，哈希表将失去其存储和检索数据的能力。B选项，这个方案不可取，因为会导致旧元素被覆盖，从而丢失数据。哈希表应该能够可靠地存储和检索每个键对应的值。C选项，这个方案不合理，因为没有明确定义“下一个位置”是什么。在哈希表中，冲突位置之后的“下一个位置”可能仍然是一个冲突位置，或者可能是一个已经存储了其它元素的位置。此外这种策略也没有提供一种系统化的方法来遍历哈希表中的所有元素。D选项，这个方案合理，描述了一种称为开放地址法（OpenAddressing）的冲突解决策略。在这种方法中，当发生冲突时，哈希表会尝试在冲突位置的后续位置找到一个空位来存储新元素。10.答案：D。解析：通过深搜或广搜可以找到这条路径，所以A选项和B选项正确。C选项，根据题目条件，从起点不经过重复点到达终点的路径仅有一条，这意味着所有与起点连通的节点都在这条路径上，因此也必然与终点连通。D选项，尽管从起点不经过重复结点到达终点的路径有且仅有⼀条，但不在这条路径的“冗余”分支上还是可能有环的，因此不一定可以抽象为无向无环图。11.答案：A。解析：log函数通常返回的是自然对数。8的自然对数约为2.07944154167，然而将log(8)的结果转换为int类型时，仅保留整数部分。12.答案：C。解析：初始化第0行和第0列，从(1,1)点开始，等于上面值+左边值。13.答案：D。解析：代码的核心部分是一个双重循环，每个循环从1~n，所以时间复杂度为O(N2)。14.答案：B。解析：这个代码虽然创建了fib_rcd数组，像是要记忆化搜索，但是不是记忆化搜索代码，因为fib_rcd数组内的值没有发生过改变，没有办法去掉重复计算。如果是记忆化搜索解决斐波那契数列数列代码时间复杂度为O(N)，因此,该递归算法的时间复杂度等于递归树的节点总数,也就是斐波那契数列的前n项之和。(图片)n是斐波那契数列第n项的一个渐近表达式。15.答案：A。解析：根据广度优先搜索的概念，从1个点出发，首先搜索所有与该点相邻的点，再进一步搜索相邻点的相邻点。根据全面扩散，逐层递进。16.答案：错误。解析：'a'是字符常量，在C++中其ASCII码值为97。'a'<<1等同于将整数97左移1位，结果为194。17.答案：错误。解析：C++不支持函数嵌套定义。18.答案：正确。解析：选择排序在排序过程中，会选择最小（或最大）的元素与当前元素交换位置。这种交换可能改变相同元素的相对顺序，因此选择排序一般是不稳定的排序算法。19.答案：正确。解析：埃氏筛法的时间复杂度是O(nloglogn),欧拉筛法是O(n)。20.答案：错误。解析：sin函数输入的是弧度制的角度，角度制下的30度，转换为弧度制是π/6。21.答案：错误。解析：最后一层可能不满。22.答案：正确。解析：与连通性无关。对于非连通图，遍历完一个连通分量后，可以在未访问的节点中选择新的起点，继续进行DFS，直到所有节点都被访问。23.答案：错误。解析：当x是p的倍数是会发送冲突。选择素数作为模数p，可以使哈希函数的值分布更均匀，减少冲突的概率，但不能完全避免冲突。24.答案：正确。解析：如果头结点作为队首，当新元素入队时，通过尾指针来实现入队操作，时间复杂度O(1)；当删除元素时，删除链表头结点，更新头指针，时间复杂度O(1)。如果头结点作为队尾，当新新元素入队时，通过头指针实现入队，时间复杂度O(1)；当删除元素时，每次都需要遍历链表找到当前的队尾前一个元素（单链表），让尾指针指向这个元素，时间复杂度O(n)。25.答案：正确。解析：图属于网状结构可以表示社交网络。26.参考程序。#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;vector<int>g[N];intcol[N],dep[N],has[N];voiddfs(intx,intfa){dep[x]=dep[fa]+1;for(autoi:g[x]){if(i!=fa){dfs(i,x);}}}booldfs2(intx,intfa){for(autoi:g[x]){if(i!=fa){autores=dfs2(i,x);if(res==false)returnfalse;if(has[i]||col[i])has[x]++;}}if(has[x]>1)returnfalse;returntrue;}intmain(){intt;cin>>t;while(t--){intn;cin>>n;for(inti=1;i<=n;i++){dep[i]=0;g[i].clear();cin>>col[i];}for(inti=1;i<n;i++){intu,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}dfs(1,0);intmx=0,pos=0;for(inti=1;i<=n;i++){has[i]=0;if(col[i]){if(dep[i]>mx){mx=dep[i];pos=i;}}}boolres=dfs2(pos,0);if(res)cout<<"Yes\n";elsecout<<"No\n";}}27.参考程序。#include<bits/stdc++.h>usingnamespacestd;constintN=505;intdp[N][1005];chara[N][N];intn,m,x;intmain(){intt;scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&x);for(inti