首页 › 题库 › GESP编程能力等级认证 › 3 图的定义及遍历

GESP-C++七级 题库

共 80 道题 ,第 2 / 4 页 · 按题型筛选,点「查看答案」核对解析
章节 3 图的定义及遍历 清除
21 单选题 适中 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条边。

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

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

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

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

题目详情
23 单选题 适中 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
这道题暂未补解析。
题目详情
24 单选题 适中 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个点出发,首先搜索所有与该点相邻的点,再进一步搜索相邻点的相邻点。 根据全面扩散,逐层递进。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A
B
C
D
答案与解析
正确答案:C

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

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

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

A
B
C
D
答案与解析
正确答案:A

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

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

下面 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)%

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

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

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

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

一个连通的简单无向图,共有28条边,则该图至少有(   )个顶点。

A
6
B
7
C
8
D
9
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
34 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

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

A

60

B

70

C

15

D

20

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
35 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

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

A
8, 6, 1, 5, 3, 4, 2, 10, 7, 12, 11, 9
B
7, 8, 6, 4, 2, 1, 5, 3, 12, 9, 11, 10。
C
8, 10, 12, 9, 11, 4, 5, 3, 2, 1, 6, 7
D
7, 8, 10, 9, 11, 12, 4, 5, 1, 2, 3, 6。
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
36 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

下面 search 函数的平均时间复杂度为(   )。

int search(int n, int * p, int target) {
	int low = 0, high = n;
	while (low <= high) {
		int middle = (low + high) / 2;
		if (target == p[middle]) {
			return middle;
		} else if (target > p[middle]) {
			low = middle + 1;
		} else {
			high = middle - 1;
		}
	}
	return -1;
}
A
O(n)
B
O(log(n))
C
O(1)
D
可能无法返回
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
37 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

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

nt count_triple(int n) {
	int cnt = 0;
	for (int a = 1; a <= n; a++)
		for (int b = a; a + b <= n; b++)
			for (int c = b; a + b + c <= n; c++)
				if (a * a + b * b == c * c)
					cnt++;
	return cnt;
}
A
O(N)
B
O(N2)
C
O(N3)
D
O(N4)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
38 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

下面的程序使用邻接矩阵表达的带权无向图,则从顶点0到顶点3的最短距离为(   )

int weight[4][4] = {
	{0, 2, 5, 8},
	{2, 0, 1, 7},
	{5, 1, 0, 4},
	{8, 7, 4, 0}};
A
6
B
7
C
8
D
9
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
39 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

下面代码可以用来求最长上升子序列(LIS)的长度,如果输入是: 5 1 7 3 5 9 ,则输出是(   )。

A

9 7 5 1 1 9

B

1 2 2 3 4 4

C

1 3 5 7 9 9

D

1 1 1 1 1 1

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
40 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

G 是一个非连通无向图,共有 28 条边,则该图至少有(   )个顶点。

A

6

B

7

C

8

D

9

答案与解析
正确答案:D
这道题暂未补解析。
题目详情