首页 › 题库 › GESP编程能力等级认证 › 6.1 冒泡排序

GESP-C++四级 题库

共 13 道题 · 按题型筛选,点「查看答案」核对解析
章节 6.1 冒泡排序 清除
1 单选题 适中 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。

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

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

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

A
冒泡排序基于元素交换实现,需借助临时变量,共涉及 3 个单元操作;而插入排序基于元素赋值实现,仅需 1 个单元操作。因此冒泡排序的计算开销通常比插入排序更高。
B
选择排序在任何情况下的时间复杂度都为 O(n2)。
C
冒泡排序在任何情况下的时间复杂度都为 O(n2)。
D
如果给定数据部分有序,插入排序通常比选择排序效率更高。
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
4 单选题 适中 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
这道题暂未补解析。
题目详情
5 单选题 适中 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 个元素,保证了在每一轮中较大的元素会逐步“冒泡”到末尾

题目详情
6 单选题 适中 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会被一直交换到数组末尾的位置。

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

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

A
O(n)
B
O(nlogn)
C
O(n2)
D
以上都不正确
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
8 判断题 偏易 GESP编程能力等级认证 ·GESP-C++四级 · 6.1 冒泡排序

冒泡排序和插入排序都是稳定排序算法。

A
对
B
错
答案与解析
正确答案:对
分析两种排序算法在相等元素间的相对位置变化情况。冒泡排序通过相邻元素比较和交换实现排序,相等元素不会发生交换,相对位置保持不变。插入排序将未排序元素逐个插入已排序部分的适当位置,相等元素插入时不会越过原有相同值元素,相对位置得以保留。两种算法均不改变相等元素的原始先后顺序。
题目详情
9 判断题 偏易 GESP编程能力等级认证 ·GESP-C++四级 · 6.1 冒泡排序

对整数数组 {4, 1, 3, 1, 5, 2} 进行冒泡排序(将最大元素放到最后),执行一轮之后是 {4, 1, 3, 1, 2, 5} 。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
10 判断题 偏易 GESP编程能力等级认证 ·GESP-C++四级 · 6.1 冒泡排序

考虑最坏情况下冒泡排序算法的时间复杂度,   T(n)为待排序数字的数目为 n的复杂度,则其递推关系式为 T(n) = T(n - 1) + n  ,T(0) = 1 。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
11 判断题 偏易 GESP编程能力等级认证 ·GESP-C++四级 · 6.1 冒泡排序

冒泡排序的平均时间复杂度为 O(n2),但最优情况下为 O(n)。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
12 判断题 偏易 GESP编程能力等级认证 ·GESP-C++四级 · 6.1 冒泡排序

冒泡排序和插入排序都是稳定的排序算法。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
13 判断题 偏易 GESP编程能力等级认证 ·GESP-C++四级 · 6.1 冒泡排序

插入排序的时间复杂度总是比冒泡排序低。

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

不完全正确。插入排序在最佳情况下(已经排序的数组)时间复杂度为O(n),而冒泡排序在最佳情况下也为O(n)。但在平均和最坏情况下,插入排序的时间复杂度为O(n^2),与冒泡排序相同。因此,不能说插入排序总是比冒泡排序低。

题目详情