首页 › 试卷 › GESP编程能力等级认证 › GESP-C++七级 › 2024年6月CCF-GESP编程能力等级认证C++编程七级真题

2024年6月CCF-GESP编程能力等级认证C++编程七级真题 VIP

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

一、单选题

1. 单选题

下列C++代码的输出结果是( )。

#include <iostream>
#include <cmath>
using namespace std;
int main() {
	cout << sin(3.1415926 / 2);
	return 0;
}
  • A 0
  • B 1
  • C 0.5
  • D 0.7071
查看答案与解析
答案:B
解析:

计算机中的三角函数使用的是弧度,3.1415926可以看作Π,也就是求sin(Π/2)=1.

2. 单选题

对于如下图的二叉树,说法正确的是( )。

  • A 先序遍历是 132 。
  • B 中序遍历是 123 。
  • C 后序遍历是 312 。
  • D 先序遍历和后序遍历正好是相反的。
查看答案与解析
答案:D
解析:

先序遍历为123,中序遍历为132,后序遍历为321,答案选D

3. 单选题

已知两个序列s1= {1,3,4,5,6,7,7,8,1} 、s2= {3,5,7,4,8,2,9,5,1} ,则它们的最长公共子序列是()。

  • A {3,5,7,8,1}
  • B {3,4,5,7,8}
  • C {5,7,8}
  • D {3,5,7,9,1}
查看答案与解析
答案:A
解析:

最长公共子序列指最长的序列满足即是s1的子序列又是s2的子序列,选项A满足要求且是最长的

4. 单选题

关于序列 {2,7,1,5,6,4,3,8,9} ,以下说法错误的是( )。

  • A {2,5,6,8,9} 是它的最长上升子序列
  • B {1,5,6,8,9} 是它的最长上升子序列
  • C {7,5,4,3} 是它的最长下降子序列
  • D {1,5,6,8,9} 是它的唯一最长上升子序列
查看答案与解析
答案:D
解析:

{2,5,6,8,9}也是它的最长上升子序列,并不唯一

5. 单选题

关于图的深度优先搜索和广度优先搜索,下列说法错误的是( )。

  • A 二叉树是也是一种图。
  • B 二叉树的前序遍历和后序遍历都是深度优先搜索的一种。
  • C 深度优先搜索可以从任意根节点开始。
  • D 二叉树的后序遍历也是广度优先搜索的一种。
查看答案与解析
答案:D
解析:

广度优先搜索往往使用队列按照节点的深度有序的方式依次遍历,很容易发现,后序遍历中节点的深度并不有序。

6. 单选题

对于如下二叉树,下面访问顺序说法错误的是( )。

  • A HDEBFIGCA不是它的后序遍历序列
  • B ABCDEFGHI是它的广度优先遍历序列
  • C ABDHECFGI是它的深度优先遍历序列
  • D ABDHECFGI是它的先序遍历序列
查看答案与解析
答案:A
解析:

后序遍历可以记作左右根,上图的后序遍历为HDEBFIGCA,选项A错误

7. 单选题

以下哪个方案不能合理解决或缓解哈希表冲突( )。

  • A 丢弃发生冲突的新元素。
  • B 在每个哈希表项处,使用不同的哈希函数再建立一个哈希表,管理该表项的冲突元素。
  • C 在每个哈希表项处,建立二叉排序树,管理该表项的冲突元素。
  • D 使用不同的哈希函数建立额外的哈希表,用来管理所有发生冲突的元素。
查看答案与解析
答案:A
解析:

不能丢弃发生冲突的新元素

8. 单选题

在C++中,关于运算符&,下面说法正确的是( )。

  • A 2 & 3 的结果是 true
  • B 011 & 111 的结果是 3
  • C 3 & 6 的结果是 2
  • D 110 & 101 的结果是 4
查看答案与解析
答案:C
解析:

运算符&是按位与,结果类型为整类型,A错误。,数字3的二进制为11,6的二进制为110,所以3&6=。注意B和D选项中,011为八进制的9,而111、110、101则均为十进制。

9. 单选题

下面关于图的说法正确的是( )。

  • A 在无向图中,环是指至少包含三个不同顶点,并且第一个顶点和最后一个顶点是相同的路径。
  • B 在有向图中,环是指一个顶点经过至少另一个顶点到自身的路径。
  • C 在有向图中,如果任意两个顶点之间都存在一条边,则这个图一定是强连通图。
  • D 在有向图中,所有顶点的入度和出度的总和就是图的边数的两倍。
查看答案与解析
答案:D
解析:

每条有向边都会贡献一个入度和一个出度,所以所有顶点的⼊度和出度的总和就是图的边数的两倍,选项D正确。

10. 单选题

图的存储和遍历算法,下面说法错误的是( )。

  • A 图的深度优先搜索和广度优先搜索对有向图和无向图都适用。
  • B 图的深度优先搜索和二叉树的先序遍历道理是不一样的。
  • C 图的深度优先搜索需要借助栈来完成。
  • D 邻接表中,顶点 对应链表中的边结点数目正好是顶点 的度。
查看答案与解析
答案:B
解析:

图的深度优先搜索和⼆叉树的先序遍历都基于深度优先的原理。

11. 单选题

如下图所示的邻接表结构,表示的是下列哪个选项中的图?

  • A
  • B
  • C
  • D
查看答案与解析
答案:C
解析:

注意到存边方式是邻接表,0号点(V1)连向的是3号点(V4)和1号点(V2),1号点连向的是4,2,0号点,2号点连向的是4,3,1号点,依次类推,可以选出正确选项C。

12. 单选题

如下图所示的邻接矩阵(inf表示无穷大),表示的是下列哪个选项中的图?

  • A
  • B
  • C
  • D
查看答案与解析
答案:A
解析:

注意到存边方式是邻接矩阵,0连向2,3,距离分别是12和30,1不连向任何人,2连向4,距离是32,依次类推,可以选出正确答案A。

13. 单选题

下面程序的输出为( )。

#include <iostream>
using namespace std;
int fib(int n) {
	if (n <= 1)
		return n;
	return fib(n - 1) + fib(n - 2);
}
int main() {
	cout << fib(6) << endl;
	return 0;
}
  • A 5
  • B 8
  • C 13
  • D 无法正常结束。
查看答案与解析
答案:B
解析:

容易发现这是斐波那契数列,可以使用递推的方式,算出斐波那契数列的前6项分别是1,1,2,3,5,8,答案为B。

14. 单选题

下面 count_triple 函数的时间复杂度为( )。

int count_triple(int n) {
	int cnt = 0;
	for (int a = 1; a <= n; a++)
		for (int b = a; a + b <= n; b++) {
			int c = sqrt(a * a + b * b);
			if (a + b + c > n)
				break;
			if (a * a + b * b == c * c)
				cnt++;
		}
	return cnt;
}
  • A O(n)
  • B O(n2)
  • C O(n3)
  • D O(n4)
查看答案与解析
答案:B
解析:

两层for循环,每层for循环的上界均为n,总时间复杂度为%O(n^2)%

15. 单选题

下列选项中,哪个可能是下图的深度优先遍历序列( )。

  • A 1, 3, 7, 5, 4, 2, 6, 8, 9
  • B 9, 4, 2, 1, 3, 5, 7, 6, 8
  • C 1, 3, 4, 2, 7, 6, 8, 9, 5
  • D 9, 7, 6, 8, 4, 2, 1, 5, 3
查看答案与解析
答案:C
解析:

深度优先遍历需要按照能走就走的原则进行遍历,A选项5后面应该是6,B选项3后面应该是7,D选项8后面应该是5

二、判断题

16. 判断题

C++语言中,表达式 6 & 5 的结果类型为 int 、值为 1 。

  • A对
  • B错
查看答案与解析
答案:错
解析:

6的二进制位110,5二进制为101,6&5=4

17. 判断题

冒泡排序是稳定的排序算法。

  • A对
  • B错
查看答案与解析
答案:对
解析:

稳定的排序算法指值相同的元素在排序前后的相对顺序不变,冒泡排序是稳定的排序算法

18. 判断题

唯一分解定理(算术基本定理)指出,每个大于1的自然数都可以唯一地分解成若干个素数的乘积。因此,我们可以很容易的对给定的自然数 n 进行质因数分解,时间复杂度仅为O(log(n))。

  • A对
  • B错
查看答案与解析
答案:错
解析:

对n进行质因数分解的时间复杂度为O(sqrt(n)

19. 判断题

C++语言中,可以为同一个类定义多个构造函数。

  • A对
  • B错
查看答案与解析
答案:对
解析:

C++会根据参数的不同选择正确的构造函数。

20. 判断题

使用 math.h 或 cmath 头文件中的对数函数,表达式 log(128) 的结果类型为 double 、值约为 7.0 。

  • A对
  • B错
查看答案与解析
答案:错
解析:

log默认是以e为底。

21. 判断题

一颗 N 层的二叉树,至少有2N−1个节点。

  • A对
  • B错
查看答案与解析
答案:错
解析:

N层的二叉树,最少的节点数量为N。

22. 判断题

非连通图不能使用广度优先搜索算法进行遍历。

  • A对
  • B错
查看答案与解析
答案:错
解析:

非连通图需要进行多次广度优先搜索算法。

23. 判断题

现使用有 N 个表项的哈希表,从 M 个元素中进行查找。该哈希表为解决哈希函数冲突,为每个表项处建立单链表存储冲突元素。其查找操作的最坏情况时间复杂度为O(M)。

  • A对
  • B错
查看答案与解析
答案:对
解析:

如果M个元素全部冲突,则需要去单链表进行查询,时间复杂度为O(M).

24. 判断题

动态规划有递推实现和递归实现,对于很多问题,通过记录子问题的解,两种实现的时间复杂度是相同的。

  • A对
  • B错
查看答案与解析
答案:对
解析:

使用递归算法并记录子问题的解就是动态规划中的记忆化搜索,和递推算法实现动态规划的时间复杂度一致

25. 判断题

泛洪算法的递归方法容易造成溢出,因此大的二维地图算法中,一般不用递归方法。

  • A对
  • B错
查看答案与解析
答案:对
解析:

C++中栈空间一般比较小,递归层数过大容易造成栈溢出。

三、简答题

26. 简答题

黑白翻转

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一棵包含 n 个节点的树,这棵树上的任意一个节点要么是白色,要么是黑色。小杨认为一棵树是美丽树当且仅当在删除所有白色节点之后,剩余节点仍然组成一棵树。

小杨每次操作可以选择一个白色节点将它的颜色变为黑色,他想知道自己最少要执行多少次操作可以使得这棵树变为美丽树。

输入格式

第一行包含一个正整数n,代表树的节点数。

第二行包含 n 个非负整数a1,a2,...,an,其中如果 ai=0,则节点 i的颜色为白色,否则为黑色。

之后 n−1 行,每行包含两个正整数xi,yi,代表存在一条连接节点xi和yi的边。

输出格式

输出一个整数,代表最少执行的操作次数。


输入样例

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

输出样例

2

样例解释

将节点 1 和 3 变为黑色即可使这棵树变为美丽树,此时删除白色节点 5,剩余黑色节点仍然组成一棵树。

数据范围

对于全部数据,保证有1≤n≤105,0≤ai≤1。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; const int N = 1e5+10; vector&lt;int&gt; g[N]; int col[N],num[N]; int ans,sum; void calc(int x,int fa){ num[x]+=col[x]; for(auto i:g[x]){ if(i!=fa){ calc(i,x); num[x]+=num[i]; } } } void dfs(int x,int fa){ int fl=0; if(num[x]!=sum&amp;&amp;num[x]!=0)fl=1; for(auto i:g[x]){ if(i!=fa){ dfs(i,x); if(num[i]!=0&amp;&amp;num[i]!=num[x]-col[x]){ fl=1; } } } if(fl==1&amp;&amp;col[x]!=1)ans++; } int main(){ int n; cin&gt;&gt;n; for(int i=1;i&lt;=n;i++){ cin&gt;&gt;col[i]; sum+=col[i]; } for(int i=1;i&lt;n;i++){ int u,v; cin&gt;&gt;u&gt;&gt;v; g[u].push_back(v); g[v].push_back(u); } calc(1,0); dfs(1,0); cout&lt;&lt;ans&lt;&lt;"\n"; }</pre>
解析:

我们考虑一个树的哪些节点删除后,依然为一棵树。显然是所有叶子节点。在把所有叶子节点删去后,新的树的叶子节点依然可以继续删除。以此类推。也就是说,对于一个白点u,如果以u为根的子树中不存在黑点的话,那么这个白点就可以被删除,否则该白点需要被染为黑点,只需要一遍深度优先搜索,最终答案为n-黑色节点数量-以u为根的子树中不存在黑点的节点数量。还有一个特殊情况,即根节点也可能可以删除,解决方法是钦定一个黑色节点为根。

27. 简答题

区间乘积

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一个包含 n 个正整数的序列A=[a1,a2,...,an]。

小杨想知道有多少对<l,r>(1≤l≤r≤n) 满足al×al+1×...×ar为完全平方数。

一个正整数 x 为完全平方数当且仅当存在一个正整数 y 使得x=y×y。

输入格式

第一行包含一个正整数n,代表正整数个数。

第二行包含 n 个正整数a1,a2,...,an,代表序列A。

输出格式

输出一个整数,代表满足要求的 <l,r>数量。


输入样例

5
3 2 4 3 2

输出样例

2

样例解释

满足条件的 <l,r> 有<3,3> 和<1,5>。

数据范围

对于全部数据,保证有1≤n≤105,1≤ai≤30。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; map&lt;int,int&gt; mp; const int N = 1e5+10; int calc(int x) { int res = 0; for (int i = 2; i * i &lt;= x; i++) { if (x % i == 0) { while (x% i == 0){ x/= i; res^=(1&lt;&lt;(i-1)); } } } if (x != 1) { res^=(1&lt;&lt;(x-1)); } return res; } int a[N]; int main(){ int n; cin&gt;&gt;n; long long ans = 0; int pre = 0; for(int i=1;i&lt;=n;i++){ cin&gt;&gt;a[i]; int res = calc(a[i]); pre^=res; if(pre==0) ans++; ans+=mp[pre]; mp[pre]+=1; } cout&lt;&lt;ans&lt;&lt;"\n"; }</pre>
解析:

一段区间积的真实值很显然我们无法求出来,那么就要通过完全平方数的性质进行转化。我们有结论:一个数是完全平方数,当且仅当这个数质因数分解后,所有质因子的指数都为偶数。那么,判定一个数是否为完全平方数,可以等价于判定它的所有素因子的指数是否为偶数。注意到a[i]<=30,那么a[i]中质因子的个数只有2,3,5,7,11,13,17,19,23,29共10个,可以用十位的二进制数进行表示,若a[i]中含有奇数个第x个质因子,则让二进制表示的第x位为1,否则为0。设这个十位二进制数为b[i],则问题转变为找到[l,r]满足b[l]b[l+1]b[l+2]…b[r]=0,区间的xor和是满足做差的性质的,进一步转化为sum[r]^sum[l-1]=0(sum数组为b数组的xor前缀和),也就是找l和r,满足sum[r]=sum[l-1],这一步可以先统计出sumi等于某一定值k的数量cnt,根据乘法原理,最终答案为cnt*(cnt-1)/2,而k的取值范围为[0~],可以使用类似桶排的方式统计。