题目描述

一.冒泡排序

1. 对n个元素进行冒泡排序，最好情况下的时间复杂度为（），最坏情况下的时间复杂度为（）

• O(1),O(n)
• O(n),O(n^2)
• O(n),O(n)
• O(n^2),O(n^2)

2. 若用冒泡排序算法对序列{10、14、26、29、41、52}降序排序，则最少需要进行（）次比较。

• 3
• 10
• 15
• 25

3. 若用冒泡排序算法对序列{5，2，6，3，8}升序排序，则第一趟冒泡排序的结果为

• {2，5，3，6，8}
• {2，5，6，3，8}
• {2，3，5，6，8}
• {2，3，6，5，8}

4. 用冒泡排序对序列{4,2,8,7,1,5,3,6}升序排序，在每一轮结束之后，不可能出现以下哪种情况

• {2 4 1 5 3 6 7 8}
• {2 1 4 3 5 6 7 8}
• {2 4 7 1 5 3 6 8}
• {2 1 3 5 7 4 6 8}

5. 以下关于逆序对的说法哪个是错误的？

• 一个序列的逆序对越多，代表数组的无序程度越大
• 一个长度为n的序列，逆序对最多n^2对
• 一个序列的逆序对的数量等于使用冒泡排序所需要的交换次数
• 序列中不相邻的两个元素可以构成逆序对

6. 使用冒泡排序对序列进行从小到大的排序，在每一轮排序过程中，会：

• 将最大元素移到最后
• 将最大元素移到最前
• 将最小元素移到最后
• 将最小元素移到最前

7. 对一个已经有序的序列进行冒泡排序，以下哪个选项有可能会发生：

• 以O(1)时间复杂度结束
• 交换序列中的两个元素
• 以O(n^2)时间复杂度结束
• 比较操作的次数小于交换操作的次数

8. 在冒泡排序过程中，如果某一趟排序过程中没有发生交换，则可以确定

• 数组已经完全有序
• 数组还没有完全有序
• 数组只有一个元素
• 数组只有两个元素

9. 冒泡排序的交换操作发生在：

• 相邻元素之间
• 随机元素之间
• 最大元素和最小元素之间
• 任意两个元素之间

10. 以下关于冒泡排序的说法哪个是错误的

• 冒泡排序的运行过程中无论哪个步骤，都不可能产生新的逆序对
• 冒泡排序是稳定的排序
• 使用冒泡排序对序列进行升序排序比降序排序快
• 因为冒泡排序不需要开辟新数组，所以冒泡排序的空间复杂度是O(1)

---

二.选择排序

11. 以下关于选择排序的说法哪个是正确的

• 选择排序的时间复杂度和序列的无序程度有关
• 选择排序是稳定排序
• 对长度为n的序列使用选择排序，最多发生n次交换
• 对长度为n的序列使用选择排序，最少发生0次交换

12. 以下关于选择排序的说法哪个是正确的

• 逆序对越多，所需的交换次数越多
• 逆序对越多，所需的交换次数越少
• 逆序对越多，所需的比较次数越多
• 以上说法都不对

13. 以下关于选择排序的说法哪个是错误的？

• 选择排序在运行过程中有可能产生新的逆序对
• 虽然冒泡排序的最优时间复杂度是O(n),但是大多数情况下选择排序会比冒泡排序快一点
• 因为选择排序不需要开辟新数组，所以选择排序的空间复杂度是O(1)
• 选择排序发生的交换次数有可能少于逆序对个数

14. 对长度为n的序列使用选择排序，在第i轮选择中需要比较（）次

• n-1
• n-i
• n-i+1
• n-i-1

15. 选择排序的最快，平均，最慢时间复杂度分别是

• O(1),O(n),O(n^2)
• O(n),O(n^2),O(n^2)
• O(n^2),O(n^2),O(n^2)
• O(n),O(2*n),O(n^2)

16. 使用选择排序对序列进行降序排序，第i轮选择的目标是

• 把第i大元素与第i个元素交换
• 把第i小元素与第i个元素交换
• 把最大元素与最小元素交换
• 把第i大元素与第i小元素交换

17. 使用选择排序对序列{4，1，1，2，4，5，3}进行升序排序，最少需要（）次交换

• 0
• 4
• 5
• 6

18. 使用选择对序列{4,2,8,7,1,5,3,6}进行升序排序，在每一轮选择之后不可能出现下列哪个情况

• 1 2 3 4 5 7 8 6
• 1 2 3 7 4 5 8 6
• 1 2 8 7 4 5 3 6
• 1 2 3 4 8 5 7 6

19. 对一个已经有序的序列进行选择排序，以下哪个选项有可能发生

• 以O(n)时间复杂度结束
• 以O(n^2)时间复杂度结束
• 只发生1次元素交换
• 只发生n次元素比较

20. 在选择排序的过程中,如果某一轮选择没有发生元素交换,可以确定

• 序列已经有序
• 序列将会在下一轮选择有序
• 没有逆序对被消除
• 序列中有相等的元素

---

三.插入排序

21. 对一个长度为n的序列进行插入排序,需要多少轮插入

• n
• n/2(向上取整)
• n/2(向下取整)
• n-1

22. 对5个不同的元素进行插入排序,最多需要做多少次比较

• 8
• 10
• 15
• 25

23. 用插入排序对序列{7,4,8,2,1,3,6,5}升序排序,在每一轮插入后,不可能出现以下哪种情况?

• 1 2 3 4 7 8 6 5
• 4 7 8 2 1 3 6 5
• 2 4 7 8 1 3 6 5
• 3 1 4 7 8 2 6 5

24. 插入排序的最佳,平均,最坏时间复杂度分别是多少?

• O(1),O(n),O(n^2)
• O(n),O(2*n),O(n^2)
• O(n),O(n^2),O(n^2)
• O(n^2),O(n^2),O(n^2)

25.什么情况下插入排序的时间效率会显著提高

• 序列原本有序程度较高
• 序列中相等元素较多
• 序列中相等元素较少
• 序列的中的最大值和最小值差距较小

26. 以下关于插入排序的说法哪个是错误的

• 插入排序是稳定排序
• 对乱序的序列进行插入排序可以不交换元素
• 在插入排序的过程中,如果序列已经有序,可以提前结束
• 因为插入排序不需要开辟新数组,所以插入排序的空间复杂度是O(1)

27. 使用插入排序对以下4个序列做升序排序,哪一个的比较次数最少

• {6,3,2,4,1,5,8,7}
• {7,1,2,3,8,6,5,4}
• {3,6,8,2,1,4,5,7}
• {1,8,7,2,6,4,5,3}

28. 对n个元素进行插入排序,如果在第i轮插入时,待插入元素为a[i+1],插入位置为a[j],则需要移动元素的次数是

• j-i
• i-j-1
• i-j
• i-j+1

29.对n个元素进行插入排序,在第i轮插入前,无序区有多少个元素?

• i
• n-i
• n-i+1
• n-i-1

30. 用插入排序对序列{54,38,96,23,15,72,60,45,83}进行升序排序,在第6轮插入时,需要把60插入有序区,需要做()次比较

• 1
• 3
• 5
• 7

---

四.计数排序

31. 对n 个元素的序列使用计数排序,数据范围是[0,k],则时间复杂度为

• O(n)
• O(k)
• O(n+k)
• O(n*k)

32. 以下哪种序列使用计数排序的效率最差

• 全都是负数的整数序列
• 有正数也有负数的正数序列
• 全都是正数的浮点数序列
• 字符序列

33. 以下关于计数排序的说法哪个是错误的

• 计数排序是稳定排序
• 计数排序的效率与序列的混乱程度无关
• 计数排序适合数据个数多,数据范围小的情况
• 因为计数排序不需要开辟新数组,所以计数排序的空间复杂度是O(1)

34. 以下关于计数排序的说法哪个是正确的?

• 计数排序只能做升序排序,不能做降序排序
• 如果序列中相等的元素个数较多,会降低计数排序的效率
• 计数排序的代码中不会使用到嵌套循环
• 使用计数排序可以统计序列的逆序对数量

35.对序列{4,5,1,1,3,5,8,7,5,2}使用计数排序做升序排序,在排序的过程中,计数数组不可能出现以下哪种情况

• {0,2,1,1,1,3,0,1,1}
• {1,1,2,3,4,5,5,7,8}
• {0,2,0,1,1,0,0,0,0}
• {0,0,0,0,0,1,0,1,1}

36. 对序列{5,4,1,4,4,7,8,4,3,1,3,2,4,7}使用计数排序,计数数组中的最大值是多少

• 4
• 5
• 6
• 14

37. 对序列{8,4,3,9,8,7,7,5,5,4,4,9,4,4,6}使用计数排序,计数数组最少要开多大?

• 5
• 7
• 9
• 11

38. 以下哪个序列使用计数排序的效率最快

• {1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8}
• {8,7,6,5,4,3,2,1,8,7,6,5,4,3,2,1}
• {6,2,7,1,2,5,4,8,4,3,2,1,5,4,6,7}
• {4,5,2,3,4,4,1,2,3,3,5,4,6,2,1,3}

39.以下哪个过程最像计数排序

• 体育课学生按照从矮到高排队
• 根据积木的长度对积木分类
• 找到考试成绩最高分的学生
• 用大网眼捕鱼避免捉到小鱼

40. 序列中有n个元素,数据范围是[0,k],使用计数排序找到第m小的数据的时间复杂度是

• O(n+k)
• O(n+m)
• 计数排序法不能实现该功能
• 以上说法都不对

---

五.基础排序综合

41. 以下哪种排序算法是不稳定的

• 冒泡排序
• 插入排序
• 选择排序
• 计数排序

42. 对于元素个数少,有序程度高的序列,应该优先使用哪种排序算法?

• 冒泡排序
• 插入排序
• 选择排序
• 计数排序

43. 哪一种排序方法的时间复杂度与待排序序列的元素范围和无序程度无关

• 冒泡排序
• 插入排序
• 选择排序
• 计数排序

44. 从10万个数据中找出10个最小的数据,用哪种排序方法比较合适

• 冒泡排序
• 插入排序
• 选择排序
• 计数排序

45.每次只比较相邻两个元素的排序算法是哪一种?

• 冒泡排序
• 插入排序
• 选择排序
• 计数排序

46.哪一种排序方法不需要进行关键字比较

• 冒泡排序
• 插入排序
• 选择排序
• 计数排序

47. 哪一种排序方法在对浮点数进行排序时表现最差

• 冒泡排序
• 插入排序
• 选择排序
• 计数排序

48. 从未排序序列中依次取出元素与已排序序列中的元素依次进行比较,然后将其放在已排序序列的合适位置,该排序方法称为

• 冒泡排序
• 插入排序
• 选择排序
• 计数排序

49. 对序列{4,6,3,8,1,2,5,7,3}使用某种排序方法,呈现以下中间过程,可以判断使用的排序方法是

{ 4 6 3 8 1 2 5 7 }

{ 3 4 6 8 1 2 5 7 }

{ 3 4 6 8 1 2 5 7 }

{ 1 3 4 6 8 2 5 7 }

• 冒泡排序
• 插入排序
• 选择排序
• 计数排序

50. 以下关于排序算法的说法,哪个是错误的?

• 如果用交换元素操作替代移动元素操作,那么对于同一个序列来说,插入排序和冒泡排序的交换次数一样多
• 用冒泡排序和插入排序对任意相同序列排序,插入排序的比较次数不会大于冒泡排序的比较次数
• 虽然冒泡排序和插入排序的平均时间复杂度都是O(n^2),但是多数情况下冒泡排序的效率会高一点点
• 在插入排序的过程中使用二分查找可以减少比较次数

输入格式

本题为选择题，无输入。

输出格式

本题为选择题，无需输出。

样例输入

样例输出