首页 › 题库 › GESP编程能力等级认证 › 6.4 复杂度与稳定性

GESP-C++四级 题库

共 8 道题 · 按题型筛选,点「查看答案」核对解析
章节 6.4 复杂度与稳定性 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.4 复杂度与稳定性

关于排序算法的稳定性,以下说法错误的是( )

A

稳定的排序算法不改变相等元素的相对位置

B

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

C

选择排序是稳定的排序算法

D

插入排序是稳定的排序算法

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.4 复杂度与稳定性

下述斐波那契数列计算的时间复杂度是?( )

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}
A
O(n)
B
C
D
答案与解析
正确答案:D

斐波那契数列的递归存在 重复计算,每个 fibonacci(n) 调用会进一步分解为 fibonacci(n-1) 和 fibonacci(n-2),调用次数和2^n有关,时间复杂度为O(2^n)。

题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.4 复杂度与稳定性

下面关于排序稳定性的描述,正确的是( )。

A
稳定性指算法的时间复杂度恒定
B
稳定排序保证相同元素的相对顺序不变
C
选择排序是稳定排序
D
插入排序不是稳定排序
答案与解析
正确答案:B

排序算法的稳定性指:若原始序列中存在多个相等元素,排序后它们的相对顺序保持不变。所以A选项错 误,选择排序不是稳定排序,插入排序是稳定排序,选择B 。

题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.4 复杂度与稳定性

给定如下代码,其时间复杂度为( )。

int cellRecur(int n) {
	if (n == 1)
		return 1;
	return cellRecur(n - 1) + cellRecur(n - 1) + 1;
}
A
O(n2)
B
O(2n)
C
O(1)
D
O(n)
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.4 复杂度与稳定性

在排序算法中,稳定性指的是( )。

A
排序后数据不会丢失
B
排序后相同元素的相对顺序保持不变
C
排序后数据不会被修改
D
排序后数据的时间复杂度不变
答案与解析
正确答案:B

解析:稳定排序算法在排序时,如果有两个相等的元素,排序后这两个元素的相对顺序保持不变。

其他选项的解释不符合稳定性的定义:

A错误,排序后的数据是否丢失与稳定性无关。

C错误,排序后数据可能会被修改(如位置改变)。

D错误,时间复杂度是排序算法的性能指标,与稳定性无关。

因此,正确答案是B

题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.4 复杂度与稳定性

上一题算法的时间复杂度为( )。

A
O(n2)
B
O(2n)
C
O(1)
D
O(n)
答案与解析
正确答案:A

冒泡排序的时间复杂度是O(n²)

题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.4 复杂度与稳定性

排序算法是稳定的(Stable Sorting),就是指排序算法可以保证,在待排序数据中有两个相等记录的关键字 R 和 S(R 出现在 S 之前),在排序后的列表中 R 也一定在 S 前。下面关于排序稳定性的描述,正确的是()。

A
冒泡排序是不稳定的。
B
插入排序是不稳定的。
C
选择排序是不稳定的。
D
以上都不正确。
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
8 判断题 偏易 GESP编程能力等级认证 ·GESP-C++四级 · 6.4 复杂度与稳定性

用递归法求 的阶乘,时间复杂度是O(n)。(    )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情