首页 › 题库 › GESP编程能力等级认证 › 7 算法效率分析

GESP-C++八级 题库

共 46 道题 ,第 2 / 3 页 · 按题型筛选,点「查看答案」核对解析
章节 7 算法效率分析 清除
21 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

在有 n 个元素的二叉排序树中进行查找,其最好、最差时间复杂度分别为(   )。

A
O(1)、O(n)
B
O(1)、O(logn)
C
O(logn)、O(logn)
D
O(logn)、O(n)
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
22 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

下面程序的时间复杂度为(   )。

int fib(int n) {
	if (n <= 1)
		return 1;
	return fib(n - 1) + fib(n - 2);
}
A
O(2n)
B
C
O(n)
D
O(1)
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
23 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

下面程序的时间复杂度为(   )。

int choose(int n, int m) {
	if (m == 0 || m == n)
		return 1;
	return choose(n - 1, m - 1) + choose(n - 1, m);
}
A
O(2n)
B
O(2m×(n-m))
C
O(C(n,m))
D
O(m×(n-m))
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
24 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

下面程序的时间复杂度为(   )。

int primes[MAXP], num = 0;
bool isPrime[MAXN] = {false};
void sieve() {
	for (int n = 2; n <= MAXN; n++) {
		if (!isPrime[n])
			primes[num++] = n;
		for (int i = 0; i < num && n * primes[i] <= MAXN; i++) {
			isPrime[n * primes[i]] = true;
			if (n % primes[i] == 0)
				break;
		}
	}
}
A
O(n)
B
O(n×logn)
C
O(n×loglogn)
D
O(n2)
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
25 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

对有 n 个元素的二叉排序树进行中序遍历,其时间复杂度是(   )。

A

O(1)

B

O(log(n))

C

O(n)

D

O(n2)

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
26 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

假设输入参数 m 和 n 满足m≤n,则下面程序的最差情况的时间复杂度为(   )。

A

O(log(n))

B

O(n)

C

O(n×m)

D

O(m×log(n))

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
27 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

下面程序的时间复杂度为(   )。

A

O(n)

B

O(an)

C

O(log(n))

D

O(log(n)×a)

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
28 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

下面程序的时间复杂度为(   )。

A

O(2n)

B

O(2m×(n-m))

C

O(C(n,m))

D

O(m×(n-m))

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
29 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

快速排序和归并排序的平均时间复杂度都是O(n log n),但快速排序是不稳定的排序算法,归并排序是稳定的排序算法。

A
对
B
错
答案与解析
正确答案:对
比较快速排序与归并排序的时间复杂度机制,分析两者在元素交换过程中的相对位置保持特性。快速排序通过基准元素划分区间并递归排序,元素可能在不同递归层中跨区间交换,导致相同值的相对顺序改变。归并排序将数组分割至最小单位后逐层合并,在合并过程中相同值按原序列顺序依次选入结果,维持了相等元素的原有次序。两种算法的平均时间复杂度均由分治策略的递归深度与每层处理规模决定,表现为O(n log n)。
题目详情
30 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

快速排序在最坏情况下的时间复杂度为O(n log n),可以通过随机化选择基准值(pivot)的方法完全避免退化。

A
对
B
错
答案与解析
正确答案:错
快速排序的时间复杂度取决于递归划分的平衡性。每次划分由基准值的选择决定,若基准值始终为最大或最小元素,将导致每层仅减少一个元素,形成n层递归,每层处理n、n-1、…个元素,时间复杂度为O(n²)。随机化选择基准值可改变划分结果的概率分布,使最坏情况发生的概率降低,但无法排除所有非均衡划分的可能性。因此,随机化影响划分的期望平衡性,不保证每次递归深度为O(log n)。算法复杂度分析包含最坏、平均与最好情况,随机化改变的是期望性能而非最坏情况的理论上界。
题目详情
31 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

对n个元素的数组进行排序,最差情况的时间复杂度为O(n2)。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
32 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

Dijkstra算法的时间复杂度为O(V2),其中V为图中顶点的数量。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
33 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

对 个元素的数组进行归并排序,最差情况的时间复杂度为 O(n log n)。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
34 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

有 V 个顶点、E 条边的图的深度优先搜索遍历时间复杂度为 O(V+E)。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
35 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

在 N 个节点的平衡二叉树中查找指定元素的最差时间复杂度为  O(N) 。( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
36 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

对 n 个元素的数组进行排序,快速排序和归并排序的平均时间复杂度都为 O(nlogn)。但快速排序存在退化情况,使得时间复杂度升高至 O(n2);归并排序需要额外的空间开销。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
37 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

二叉排序树的查找操作的平均时间复杂度,正比于树的高度。

A
对
B
错
答案与解析
正确答案:对

二叉排序树查找的时间复杂度为树的高度。

题目详情
38 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

已知等差数列的通项公式an=a1+(n−1)⋅d,则前 n nn 项和的求和公式为Sn=n⋅(a1+an)/2。使用这一公式计算Sn的时间复杂度是O(1)。

A
对
B
错
答案与解析
正确答案:对

公式计算一步到位,和规模无关,复杂度O(1).

题目详情
39 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

在N个元素的二叉排序树中查找一个元素,最差情况的时间复杂度是O(logN)。

A
对
B
错
答案与解析
正确答案:错

二叉排序树最坏的情况退化成1条链,时间复杂度是O(n)。

题目详情
40 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

使用单链表和使用双向链表,查找元素的时间复杂度相同。

A
对
B
错
答案与解析
正确答案:对

查找的时间复杂度不变。都是从某个方向开始一直遍历查找。

题目详情