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

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

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

一、单选题

1. 单选题

已知小写字母 b 的ASCII码为98,下列C++代码的输出结果是( )。

#include <iostream>
using namespace std;
int main() {
	char a = 'b';
	a++;
	cout << a;
	return 0;
}
  • A b
  • B c
  • C 98
  • D 99
查看答案与解析
答案:C
解析:

在C++中,字符在计算机中是整数存储,小写字母b的ASCII码为98,对a进行自增操作时,其ASCII码增加到99,程序输出的是ASCII码值为99的字符,即小写字母c

2. 单选题

已知 a 为 int 类型变量,下列表达式不符合语法的是( )。

  • A &a + 3
  • B +a & 3
  • C a - - 4
  • D a++3
查看答案与解析
答案:D
解析:

a++3是语法错误,因为a++作为一个整体,其结果不能直接与其它数值进行连接。

3. 单选题

下列关于C++语言中指针的叙述,不正确的是( )。

  • A 指针变量中存储的是内存地址。
  • B 指针变量指向的内存地址不一定能够合法访问。
  • C 结构类型中的指针成员不能指向该结构类型。
  • D 定义指针变量时必须指定其指向的类型。
查看答案与解析
答案:C
解析:

结构体类型中的指针成员是可以指向该结构类型的,常见操作如链表。

4. 单选题

下列关于C++类的说法,错误的是( )。

  • A 将C++类对象通过值传递给函数参数时,会自动调用复制构造函数。
  • B 将一个类的对象赋值给该类的另一个对象时,不会自动调用构造函数。
  • C 定义C++类对象时,一定会调用默认构造函数。
  • D 构造派生类的对象时,一定会调用基类的构造函数。
查看答案与解析
答案:C
解析:

如果类中定义了其他构造函数(如有参数的构造函数)但没有定义默认构造函数,且在创建对象时没有提供初始化参数,则不会调用默认构造函数,甚至可能导致编译错误。

例如:

class MyClass {
public:
   MyClass(int value) : m_value(value) {}
private:
   int m_value;
};

在这个例子中,MyClass有一个接受一个整数参数的构造函数。如果尝试创建一个MyClass对象而不提供初始化参数,如下所示:

MyClass obj;

这将导致编译错误,因为编译器找不到一个无参数的默认构造函数。

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 以上说法都不对
查看答案与解析
答案:A
解析:

先序可以确定根节点,中序可以确定左右子树节点,根据先序和中序可以构造一棵唯一的二叉树。

如果根节点高度为1,则这棵二叉树的高度为5, 有三个叶子节点。A选择对,B选项错。

平衡树:一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。 所以C选项错。

6. 单选题

一棵完全二叉树有431个结点,则叶结点有多少个?( )

  • A 176
  • B 215
  • C 216
  • D 255
查看答案与解析
答案: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 二叉树的中序遍历与其深度优先遍历总是相同的。
  • B 所有树都可以构造一颗二叉树与之一一对应。
  • C 如果树的一个叶结点有两个不同的祖先结点,那么其中一个一定是另一个的祖先结点。
  • D 树的结点不能有两个父结点。
查看答案与解析
答案:A
解析:

深度优先搜索是一个更广泛概念,包括三种不同的遍历方式:前序遍历、中序遍历、后序遍历,虽然中序遍 历是深度优先搜索的一种形式,所以不能说二叉树的中序遍与其深度优先搜索遍历总是相同的。

8. 单选题

一个简单无向图有10个结点、30条边。再增加多少条边可以成为完全图。( )

  • A 10
  • B 15
  • C 51
  • D 60
查看答案与解析
答案:B
解析:

n个结点的完全无向图,最多有n*(n-1)/2条边。10个结点最多:10*9/2=45条边,所以还需要15条边。

9. 单选题

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

  • A 丢弃发生冲突的新元素。
  • B 用新元素覆盖发生冲突的元素。
  • C 用新元素覆盖在冲突位置的下一个位置。
  • D 将新元素放置在冲突位置之后的第一个空位。
查看答案与解析
答案:D
解析:

在哈希表中,冲突(也称碰撞)是指两个不同的键被映射到哈希表的同一位置。

A选项,这个方案显然不是一个好的解决策略,因为它会导致信息丢失。如果频繁发生冲突,大量新元素将被丢弃, 哈希表将失去其存储和检索数据的能力。

B选项,这个方案不可取,因为会导致旧元素被覆盖,从而丢失数据。哈希表应该能够可靠地存储和检索每个键对应 的值。

C选项,这个方案不合理,因为没有明确定义“下一个位置”是什么。在哈希表中,冲突位置之后的“下一个位置” 可能仍然是一个冲突位置,或者可能是一个已经存储了其它元素的位置。此外这种策略也没有提供一种系统化的方法 来遍历哈希表中的所有元素。

D选项,这个方案合理,描述了一种称为开放地址法(Open Addressing)的冲突解决策略。在这种方法中,当发生 冲突时,哈希表会尝试在冲突位置的后续位置找到一个空位来存储新元素。

10. 单选题

一个迷宫,已知从起点不经过重复结点到达终点的路径有且仅有一条,则下面说法错误的是( )。

  • A 可以使用深度优先搜索找到这条路径。
  • B 可以使用广度优先搜索找到这条路径。
  • C 该迷宫内与起点连通的结点,一定也与终点连通。
  • D 该迷宫内与起点连通的结点及它们之间的路径可以抽象为无向无环图。
查看答案与解析
答案:D
解析:

通过深搜或广搜可以找到这条路径,所以A选项和B选项正确。

C选项,根据题目条件,从起点不经过重复点到达终点的路径仅有一条,这意味着所有与起点连通的节点都在这条路 径上,因此也必然与终点连通。

D选项,尽管从起点不经过重复结点到达终点的路径有且仅有⼀条,但不在这条路径的“冗余”分支上还是可能有环的,比如下图所示的迷宫。因此不一定可以抽象为无向无环图。

11. 单选题

下面程序的输出为( )。

#include <iostream>
#include <cmath>
using namespace std;
int main() {
	cout << (int)log(8) << endl;
	return 0;
}
  • A 2
  • B 3
  • C 8
  • D 无法通过编译。
查看答案与解析
答案:A
解析:

log函数通常返回的是自然对数。8的自然对数约为2.07944154167,然而将log(8)的结果转换为int类型时,仅保留整数部分。

12. 单选题

下面程序的输出为( )。

#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;
}
  • A 84
  • B 495
  • C 1012
  • D 结果是随机的。
查看答案与解析
答案:C
解析:

初始化第0行和第0列,从(1,1)点开始,等于上面值+左边值。

13. 单选题

上题中程序的时间复杂度为( )。

  • A O(1)
  • B O(N)
  • C O(NlogN)
  • D O(N2)
查看答案与解析
答案:D
解析:

代码的核心部分是一个双重循环,每个循环从1~n,所以时间复杂度为O(N2)

14. 单选题

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

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);
}
  • A O(n)
  • B
  • C O(2n)
  • D 无法正常结束。
查看答案与解析
答案:B
这道题暂未补解析。
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

查看答案与解析
答案:A
解析:

根据广度优先搜索的概念,从1个点出发,首先搜索所有与该点相邻的点,再进一步搜索相邻点的相邻点。 根据全面扩散,逐层递进。

二、判断题

16. 判断题

表达式 ‘a’ << 1 的结果为 'a ’ 。

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

'a’是字符常量,在C++中其ASCII码值为97。‘a’ << 1 等同于将整数97左移1位,结果为194。

17. 判断题

在C++语言中,函数可以定义在另一个函数定义之内。

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

C++不支持函数嵌套定义。

18. 判断题

选择排序一般是不稳定的。

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

选择排序在排序过程中,会选择最小(或最大)的元素与当前元素交换位置。这种交换可能改变相同元素的相对顺序,因此选择排序一般是不稳定的排序算法。

19. 判断题

埃氏筛法和欧拉筛法都是使用筛法思想生成素数表的算法,欧拉筛法的时间复杂度更低。

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

埃氏筛法的时间复杂度是O(n log logn),欧拉筛法是O(n)。

20. 判断题

使用 math.h 或 cmath 头文件中的正弦函数,表达式 sin(30) 的结果类型为 double 、值约为 0.5 。

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

sin函数输入的是弧度制的角度,角度制下的30度,转换为弧度制是π/6。

21. 判断题

一颗 N 层的完全二叉树,一定有 2N−1 个结点。

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

最后一层可能不满。

22. 判断题

一个图,不管是否连通,都可以使用深度优先搜索算法进行遍历。

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

与连通性无关。对于非连通图,遍历完一个连通分量后,可以在未访问的节点中选择新的起点,继续进行DFS,直到所有节点都被访问。

23. 判断题

某个哈希表键值 x 为整数, H(x) = x % p 是常用的哈希函数之一,要求 p 选择素数是因为这样不会产生冲突。( )

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

当x是p的倍数是会发送冲突。选择素数作为模数p,可以使哈希函数的值分布更均匀,减少冲突的概率,但不能完全避免冲突。

24. 判断题

使用单链表实现队列时,链表头结点作为队首比链表头结点作为队尾更便于操作。

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

如果头结点作为队首,当新元素入队时,通过尾指针来实现入队操作,时间复杂度O(1);当删除元素时, 删除链表头结点,更新头指针,时间复杂度O(1)

如果头结点作为队尾,当新新元素入队时,通过头指针实现入队,时间复杂度O(1);当删除元素时,每次都需要遍历链表找到当前的队尾前一个元素(单链表),让尾指针指向这个元素,时间复杂度O(n)。

25. 判断题

一个图中,每个结点表达一个人,连接两个结点的边表达两个结点对应的人相互认识,则这个图可以用来表达社交网络

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

图属于网状结构可以表示社交网络。

三、简答题

26. 简答题

小杨寻宝

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一棵包含 n 个节点的树,树上的一些节点放置有宝物。

小杨可以任意选择一个节点作为起点并在树上移动,但是小杨只能经过每条边至多一次,当小杨经过一条边后,这条边就会消失。小杨每经过一个放置有宝物的节点就会取得该宝物。

小杨想请你帮他判断自己能否成功取得所有宝物。

输入格式

第一行包含一个正整数 t ,代表测试用例组数。

接下来是 t 组测试用例。对于每组测试用例,一共 n+1 行。

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

第二行包含 n 个非负整数a1,a2,...,an,其中如果 ai=1,则节点 i 放置有宝物,若ai=0,则节点 i 没有宝物。

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

输出格式

对于每组测试数据,如果小杨能成功取得所有宝物,输出 Yes,否则输出 No。


输入样例

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

输出样例

Yes
No

对于第一组测试用例,小杨从节点 2 出发,按照2−1−3−4 的顺序即可成功取得所有宝物。

对于全部数据,保证有1≤t≤10,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],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]&gt;1)return false; return true; } int main(){ int t; cin&gt;&gt;t; while(t--){ int n; cin&gt;&gt;n; for(int i=1;i&lt;=n;i++){ dep[i]=0;g[i].clear(); cin&gt;&gt;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); } dfs(1,0); int mx=0,pos=0; for(int i=1;i&lt;=n;i++){ has[i]=0; if(col[i]){ if(dep[i]&gt;mx){ mx=dep[i]; pos=i; } } } bool res= dfs2(pos,0); if(res)cout&lt;&lt;"Yes\n"; else cout&lt;&lt;"No\n"; } }</pre>
解析:

通过题意初步可以想到以每一个点作为起点进行搜索,再搜索过程中记录搜到的ai=1的点,搜索结束后比较和1的总数是否相同。由于数据范围较大,因此明显会超时。

由于每个节点只能走一次,所以可以从最深的宝物开始收集可以确保小杨在返回时不会重复经过已经消失的边(因为边会在经过一次后消失)。然后从这个节点回到根节点,如果是1那么就标记走了一次,如果这里被标记两次那么肯定是不满足题目要求。

27. 简答题

矩阵移动

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一个有一个 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? 三种字符的字符串。

输出格式

对于每组测试用例,输出一行一个整数,代表最优策略下小杨的得分最多是多少。


输入样例

2
3 3 1
000
111
01?
3 3 1
000
?0?
01?

输出样例

4
2

对于第二组测试用例,将(1,1)或者 (3,3)变成 1 均是最优策略。

对于全部数据,保证有1≤t≤10,1≤n,m≤500,1≤x≤300,同时保证所有测试用例 n×m 的总和不超过 2.5×105。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; 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", &amp;t); while(t--){ scanf("%d%d%d", &amp;n, &amp;m, &amp;x); for(int i = 1; i &lt;= m; i++) for(int j = 0; j &lt;= x; j++) dp[i][j] = 0; for(int i = 1; i &lt;= n; i++) scanf("%s", a[i] + 1); for(int i = 1; i &lt;= n; i++){ for(int j = 1; j &lt;= m; j++){ for(int k = x; k&gt;=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]); 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 &lt;= x; k++) ans = max(ans, dp[m][k]); printf("%d\n", ans); } }</pre>
解析:

如果不考虑x,问题转换成为从(1,1)到(n,m)只能向下或者向右移动最多拿到多少个1。对于矩阵中的任意一点(i,j)只可能从(i-1,j)或者(i,j-1)移动过来。

状态设计:dp[i][j]表示到达位置(i,j)时可以获得的最大分数。

不难得到状态转移方程dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + (a[i][j] == ‘1’?1:0)。

考了加入x,还是只能向下或者向右移动,之前只有1对结果有贡献,现在?也对结果有贡献。由于x的限制,?不能无限制的修改成1,所以需要记录修改次数。设计状态时增加一维表示修改次数。

状态设计:dp[i][j][k]表示到达位置(i,j)时,已经修改了k个字符所能获得的最大分数。

如果a[i][j]是0或者1,正常转移,和不考虑x时的转移过程一致,如果a[i][j]是?,先考虑当前有没有修改次数,如果没有当前阶段拿到和1和上一阶段比较求最大值,如果有修改次数,,需要看之前修改转移的值是多少,求最大值。

当a[i][j] == 1时,dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k])+1,

当a[i][j] == 0时,dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k]),

当a[i][j] == ?时,如果没有修改次数,dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k]),

如果有修改次数,再考虑改或不改。

若修改当前节点为1,则有dp[i][j][k]=max(dp[i-1][j][k-1],dp[i][j-1][k-1])+1,

若不修改,则有dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k]),

取以上情况的最大值即可,同时需要考虑,若k==x,则不可增加修改次数。

可以观察到每一行的计算只依赖于上一行的信息,第一维可以优化,故可以使用滚动数组对数组进行降维。