首页 › 题库 › GESP编程能力等级认证 › GESP-C++七级

GESP-C++七级 题库

共 270 道题 ,第 5 / 14 页 · 按题型筛选,点「查看答案」核对解析
81 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 综合练习

一棵完全二叉树有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

题目详情
82 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 综合练习

下列关于树的说法,错误的是( )。

A
二叉树的中序遍历与其深度优先遍历总是相同的。
B
所有树都可以构造一颗二叉树与之一一对应。
C
如果树的一个叶结点有两个不同的祖先结点,那么其中一个一定是另一个的祖先结点。
D
树的结点不能有两个父结点。
答案与解析
正确答案:A

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

题目详情
83 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

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

A
10
B
15
C
51
D
60
答案与解析
正确答案:B

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

题目详情
84 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

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

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

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

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

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

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

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

题目详情
85 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 综合练习

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

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

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

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

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

题目详情
86 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 1.1 三角函数

下面程序的输出为( )。

#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类型时,仅保留整数部分。

题目详情
87 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 1.1 三角函数

下面程序的输出为( )。

#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)点开始,等于上面值+左边值。

题目详情
88 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

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

A
O(1)
B
O(N)
C
O(NlogN)
D
O(N2)
答案与解析
正确答案:D

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

题目详情
89 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

下面 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
这道题暂未补解析。
题目详情
90 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

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

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个点出发,首先搜索所有与该点相邻的点,再进一步搜索相邻点的相邻点。 根据全面扩散,逐层递进。

题目详情
91 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 1.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.

题目详情
92 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

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

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

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

题目详情
93 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 2.3 LIS与LCS

已知两个序列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满足要求且是最长的

题目详情
94 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 综合练习

关于序列 {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}也是它的最长上升子序列,并不唯一

题目详情
95 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

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

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

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

题目详情
96 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 综合练习

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

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

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

题目详情
97 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

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

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

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

题目详情
98 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 综合练习

在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则均为十进制。

题目详情
99 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

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

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

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

题目详情
100 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

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

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

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

题目详情