首页 › 题库 › GESP编程能力等级认证 › 6 排序算法

GESP-C++四级 题库

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

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

A

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

B

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

C

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

D

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

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.3 选择排序

下面代码试图实现选择排序,使其能对数组 nums 排序为升序,则横线上应分别填写( )

A

nums[j] < nums[minIndex]

swap(nums[i], nums[minIndex])

B

nums[j] > nums[minIndex]

swap(nums[i], nums[minIndex])

C

nums[j] <= nums[minIndex]

swap(nums[j], nums[minIndex])

D

nums[j] <= nums[minIndex]

swap(nums[i], nums[j])

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.2 插入排序

下面程序实现插入排序(升序排序),则横线上应分别填写( )

A

arr[j] > key

arr[j + 1] = key

B

arr[j] < key

arr[j + 1] = key

C

arr[j] > key

arr[j] = key

D

arr[j] < key

arr[j] = key

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.2 插入排序

关于插入排序的时间复杂度,下列说法正确的是( )。

A

最好情况和最坏情况的时间复杂度都是

B

最好情况是 ,最坏情况是

C

最好情况是 ,最坏情况是

D

最好情况是 ,最坏情况是

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.2 插入排序

以下哪种情况是使用插入排序的合适场景?( )

A
数据量非常大,且乱序严重
B
希望获得稳定排序,但不要求实时性
C
数据几乎有序,只需少量调整
D
想在交换次数最少的前提下排好大数组
答案与解析
正确答案:C

插入排序将待排序元素逐个插入到已排序部分的正确位置。

最适合:数据几乎有序(只需少量调整),此时接近最优时间复杂度 O(n),不适合数据量大且完全乱序,性能退化为 O(n^2)。

题目详情
6 单选题 适中 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)。

题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.1 冒泡排序

为了提高冒泡排序的效率,如果某轮“冒泡”中没有执行任何交换操作,说明数组已经完成排序,可直接返回结果,则两条横线上分别应该填写?( )

void bubbleSortWithFlag(vector<int> &nums) {
    for (int i = nums.size() - 1; i > 0; i--) {
        bool flag;
        ________________ // 在此处填入代码
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums[j], nums[j + 1]);
                ___________________________ // 在此处填入代码
            }
        }
        if (!flag)
            break;
    }
}
A
flag = false;flag = false;
B
flag = false;flag = true;
C
flag = true;flag = false;
D
flag = true;flag = true;
答案与解析
正确答案:B

填空1,初始化 flag为false,填空2,如果发生交换,将flag置位true。

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

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

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

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

题目详情
9 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.1 冒泡排序

对数组 arr[]={5, 3, 8, 1} 进行升序排序,执行第—轮冒泡排序后数组 arr 中的内容为( )。

A
3, 5, 1, 8
B
3, 1, 5, 8
C
3, 5, 8, 1 
D
5, 3, 8, 1
答案与解析
正确答案:A

根据冒泡排序的逻辑,本题选择A 。

题目详情
10 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.1 冒泡排序

下面关于排序算法(冒泡排序、插入排序和选择排序)的描述中,不正确的是( )。

A
冒泡排序基于元素交换实现,需借助临时变量,共涉及 3 个单元操作;而插入排序基于元素赋值实现,仅需 1 个单元操作。因此冒泡排序的计算开销通常比插入排序更高。
B
选择排序在任何情况下的时间复杂度都为 O(n2)。
C
冒泡排序在任何情况下的时间复杂度都为 O(n2)。
D
如果给定数据部分有序,插入排序通常比选择排序效率更高。
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
11 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.1 冒泡排序

冒泡排序的第一轮操作是从左到右遍历数组,通过两两比较相邻元素,将当前最大的元素移动到末尾。给定数组 arr[]={4, 1, 3, 1, 5, 2} ,执行第一轮冒泡排序后数组 arr 中的内容为( )。

A
1, 4, 3, 1, 5, 2
B
1, 3, 1, 4, 2, 5
C
1, 4, 3, 1, 2, 5
D
4, 1, 3, 1, 5, 2
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
12 单选题 适中 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
这道题暂未补解析。
题目详情
13 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.4 复杂度与稳定性

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

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

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

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

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

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

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

因此,正确答案是B

题目详情
14 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.1 冒泡排序

下面代码实现了冒泡排序函数,则横线上应填写( )。

//交换数组arr的第i个元素和第j个元素
void swap(vector<int> &arr, int i, int j) {
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}

int bubble_sort(vector<int> &arr) {
	for (int i = arr.size() - 1; i > 0; i--) {
		bool flag = false; // 标志位
		________________________________ { // 在此处填入代码
			if (arr[j] > arr[j + 1]) {
				swap(arr, i, j);
				flag = true;
			}
		}
		if (!flag)
			break; // 此轮“冒泡”未交换任何元素
	}
}
A
for (int j = 0; j < arr.size() - 1; j++)
B
for (int j = arr.size() - 1; j > 0; j–)
C
for (int j = 0; j < i; j++)
D
for (int j = i-1; j <=0; j–)
答案与解析
正确答案:C

冒泡排序的外层循环遍历数组,从后向前控制需要比较的元素范围。

内层循环for (int j = 0; j < i; j++) 则确保在当前遍历中比较到第i 个元素,保证了在每一轮中较大的元素会逐步“冒泡”到末尾

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

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

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

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

题目详情
16 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.2 插入排序

关于直接插入排序,下列说法错误的是()

A
插入排序的最好情况是数组已经有序,此时只需要进行 次比较,时间复杂度为
B
最坏情况是数组逆序排序,此时需要进行 次比较以及 次赋值操作(插入)
C
平均来说插入排序算法的复杂度为
D
空间复杂度上,直接插入法是就地排序,空间复杂度为
答案与解析
正确答案:D

就地排序只需要O(1)的额外空间。

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

关于几种排序算法的说法,下面说法错误的是( )。

A
选择排序不是一个稳定的排序算法
B
冒泡排序算法不是一种稳定的排序算法
C
`插入排序是一种稳定的排序算法
D
如果排序前2个相等的数在序列中的前后位置顺序和排序后它们2个的前后位置顺序相同,则称为一种稳定的排序算法
答案与解析
正确答案:B

在冒泡排序中,两个元素交换的条件是a[j]>a[j+1],如果两个元素的值相等,他们并不会发生交换,因此是一种稳定的排序算法。

题目详情
18 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.1 冒泡排序

数组{45,66,23,1,10,97,52,88,5,33}进行从小到大冒泡排序过程中,第一遍冒泡过后的序列是( )。

A
{45,23,1,10,66,52,88,5,33,97}
B
{45,66,1,23,10,97,52,88,5,33}
C
{45,66,23,1,10,52,88,5,33,97}
D
{45,66,23,1,10,97,52,88,33,5}
答案与解析
正确答案:A

按照冒泡排序的过程模拟一遍即可,66会被一直交换到97的前面的位置,97会被一直交换到数组末尾的位置。

题目详情
19 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.2 插入排序

插入排序在最好情况下的时间复杂度是(   )。

A
O(1)
B
O(N/2)
C
O(N)
D
O(N2)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
20 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 6.1 冒泡排序

对包含 n 个元素的数组进行冒泡排序,平均时间复杂度一般为(     )。

A
O(n)
B
O(nlogn)
C
O(n2)
D
以上都不正确
答案与解析
正确答案:C
这道题暂未补解析。
题目详情