第二章 程序设计基本知识

第3节 排序算法

1.【NOIP2011】体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于( )算法。

{{ select(1) }}

• 快速排序
• 插入排序
• 冒泡排序
• 归并排序

2.【NOIP2018】以下排序算法中，不需要进行关键字比较操作的算法是( )。

{{ select(2) }}

• 基数排序
• 冒泡排序
• 堆排序
• 直接插入排序

3.【NOIP2009】排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排序算法是不稳定的：

{{ select(3) }}

• 冒泡排序
• 插入排序
• 归并排序
• 快速排序

4.【NOIP2009】快速排序最坏情况下的算法复杂度为：

{{ select(4) }}

• O(log₂n)
• O(n)
• O(nlogn)
• O(n²)

5.【NOIP2009】快速排序平均情况和最坏情况下的算法时间复杂度分别为：

{{ select(5) }}

• 平均情况O(nlog₂n),最坏情况O(n²)
• 平均情况O(n),最坏情况O(n²)
• 平均情况O(n),最坏情况O(nlog₂n)
• 平均情况O(log₂n),最坏情况O(n²)

6.【NOIP2012】如果不在快速排序中引入随机化，有可能导致的后果是( )。

{{ select(6) }}

• 数组访问越界
• 陷入死循环
• 排序结果错误
• 排序时间退化为平方级

7.【NOIP2010】基于比较的排序时间复杂度的下限是( ),其中n是待排的元素个数。

{{ select(7) }}

• O(n)
• O(n log n)
• O(log n)
• O(n²)

8.【NOIP2013】( )的平均时间复杂度为O(n log n),其中n是待排序的元素个数。

{{ select(8) }}

• 快速排序
• .插入排序
• 冒泡排序
• 基数排序

9.【NOIP2014】以下时间复杂度不是O(n²)的排序方法是( )。

{{ select(9) }}

• 插入排序
• 归并排序
• 冒泡排序
• 选择排序

10.【NOIP2017】对于给定的序列{$a_k$},我们把$(i,j)$称为逆序对当且仅当$i<j$且$a_i>a_j$。那么序列$1,7,2,3,5,4$的逆序对数为()个。

{{ select(10) }}

• 4
• 5
• 6
• 7

11.【NOIP2012】使用冒泡排序对序列进行升序排序，每执行一次交换操作将会减少1个逆序对，因此序列5,4,3,2,1需要执行($\ \ \ \$ )次交换操作，才能完成冒泡排序。

{{ select(11) }}

• 0
• 5
• 10
• 15

12.【NOIP2017】设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，任何以元素比较作为基本运算的归并算法在最坏情况下至少要做($\ \ \ \$)次比较。

{{ select(12) }}

• n²
• n log n
• 2n
• 2n-1

不定项选择题

1.【NOIP2009】排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪些排序算法是稳定的：

{{ multiselect(13) }}

• 插入排序
• 基数排序
• 归并排序
• 冒泡排序

2. NOIP2017】下列算法中，( )是稳定的排序算法。

{{ multiselect(14) }}

• 快速排序
• 堆排序
• 希尔排序
• 插入排序

3.【NOIP2010】原地排序是指在排序过程中(除了存储待排序元素以外的)辅助空间的大小与数据规模无关的排序算法。以下属于原地排序的有( )。

{{ multiselect(15) }}

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

4.【NOIP2016】下列算法中运用分治思想的有( )。

{{ multiselect(16) }}

• 快速排序
• 归并排序
• 冒泡排序
• 计数排序

5.【NOIP2013】( )的平均时间复杂度为0(n log n),其中n是待排序的元素个数。

{{ multiselect(17) }}

• 快速排序
• 插入排序
• 冒泡排序
• 归并排序

6.【NOIP2017】以下排序算法在最坏情况下时间复杂度最优的有( )。

{{ multiselect(18) }}

• 冒泡排序
• 快速排序
• 归并排序
• 堆排序

7.【NOIP2011】对于序列“7、5、1、9、3、6、8、4”,在不改变顺序的情况下，去掉( )会使逆序对的个数减少3。

{{ multiselect(19) }}

• 7
• 5
• 3
• 6