首页 › 题库 › 信息学奥赛 › 5.1 冒泡排序

信息学奥赛-入门级 题库

共 4 道题 · 按题型筛选,点「查看答案」核对解析
章节 5.1 冒泡排序 清除
1 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 5.1 冒泡排序

某同学用冒泡排序对数组{6,1,5,2,4}进行升序排序,请问需要进行多少次元素交换?()

A
5
B
6
C
7
D
8
答案与解析
正确答案:B

冒泡排序过程如下(数组初始:{6,1,5,2,4}):

第一趟:交换4次,数组变为{1,5,2,4,6}。

第二趟:交换2次,数组变为{1,2,4,5,6}。

第三趟及以后:无交换。

总交换次数为6。

题目详情
2 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 5.1 冒泡排序

冒泡排序算法的伪代码如卜:

输入:数组L, n ≥ 1。输出:按非递减顺序排序的L

算法 BubbleSort:

   1. FLAG ← n //标记被交换的最后元素位置

   2. while FLAG > 1 do

   3.     k ← FLAG -1

   4.     FLAG ← 1

   5.     for j=1 to k do

   6.         if L(j) > L(j+1) then do

   7.              L(j)  ↔ L(j+1)

   8.              FLAG ← j

对n个数用以上冒泡排抒算法进行排序 最少需要比较多少次?()。

A
n
B
n-2
C
n^2
D
n-1
答案与解析
正确答案:D

考察冒泡排序的时间复杂度 。题目要求的是最少时间,我们可以发现,当数组本身是有序的时候,flag的值会一直是1,不会改变,所以j是从1到n-1,一共比较了n-1次,所以选D。

题目详情
3 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 5.1 冒泡排序

使用冒泡排序对序列进行升序排序,列每执行一次交换操作将会减少1个逆序对,  因此序5, 4, 3, 2, 1

需要执行( )次交换操作,才能完成冒泡排序。

A
0
B
5
C
10
D

15

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
4 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 5.1 冒泡排序

冒泡排序算法的伪代码如卜:

输入:数组L, n ≥ 1。输出:按非递减顺序排序的L

算法 BubbleSort:

   1. FLAG ← n //标记被交换的最后元素位置

   2. while FLAG > 1 do

   3.     k ← FLAG -1

   4.     FLAG ← 1

   5.     for j=1 to k do

   6.         if L(j) > L(j+1) then do

   7.              L(j)  ↔ L(j+1)

   8.              FLAG ← j

对n个数用以上冒泡排抒算法进行排序 最少需要比较多少次?()。

A
n
B
n-2
C
n^2
D
n-1
答案与解析
正确答案:D

考察冒泡排序的时间复杂度 。题目要求的是最少时间,我们可以发现,当数组本身是有序的时候,flag的值会一直是1,不会改变,所以j是从1到n-1,一共比较了n-1次,所以选D。

题目详情