交换类排序与选择类排序 —选择填空

时间：2025-03-14 07:12:45

1-1

对N个记录进行堆排序，需要的额外空间为O(N)。 (1分)

T         F

 

1-2

对N个记录进行简单选择排序，比较次数和移动次数分别为O(N​2​​)和O(N)。 (1分)

T         F

1-3

希尔排序是稳定的算法。 (1分)

T         F

1-4

对N个不同的数据采用冒泡排序进行从大到小的排序，当元素基本有序时交换元素次数肯定最多。 (1分)

T         F

2-1

在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左右指针都会停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？(2分)

  1. O(logN)
  2. O(N)
  3. O(NlogN)
  4. O(N​2​​)

1.  3

2-2

在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左右指针都不停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？(2分)

  1. O(logN)
  2. O(N)
  3. O(NlogN)
  4. O(N​2​​)

2.   4

2-3

在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左指针停止移动，而右指针在同样情况下却不停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？(2分)

  1. O(logN)
  2. O(N)
  3. O(NlogN)
  4. O(N​2​​)

3.  4

2-4

对N个不同的数据采用冒泡算法进行从大到小的排序，下面哪种情况下肯定交换元素次数最多？ (1分)

  1. 从小到大排好的
  2. 从大到小排好的
  3. 元素无序
  4. 元素基本有序

4.   1

2-5

对于7个数进行冒泡排序，需要进行的比较次数为： (2分)

  1. 7
  2. 14
  3. 21
  4. 49

5.   3

2-6

有组记录的排序码为{ 46，79，56，38，40，84 }，则利用堆排序的方法建立的初始堆为： (2分)

  1. 79，46，56，38，40，80
  2. 84，79，56，46，40，38
  3. 84，56，79，40，46，38
  4. 84，79，56，38，40，46

6.    4

2-7

采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是： (2分)

  1. 每次划分后，先处理较长的分区可以减少递归次数
  2. 每次划分后，先处理较短的分区可以减少递归次数
  3. 递归次数与每次划分后得到的分区处理顺序无关
  4. 递归次数与初始数据的排列次序无关

7.    3

2-8

对N个记录进行快速排序，在最坏的情况下，其时间复杂度是： (1分)

  1. O(N)
  2. O(NlogN)
  3. O(N​2​​)
  4. O(N​2​​logN)

8.   3

2-9

有组记录的排序码为{46，79，56，38，40，84 }，采用快速排序（以位于最左位置的对象为基准而）得到的第一次划分结果为： (2分)

  1. {38,46,79,56,40,84}
  2. {38,79,56,46,40,84}
  3. {38,46,56,79,40,84}
  4. {40,38,46,56,79,84}

9.     4

2-10

对于序列{ 49，38，65，97，76，13，27，50 }，按由小到大进行排序，下面哪一个是初始步长为4的希尔排序法第一趟的结果？ (2分)

  1. 13,27,38,49,50,65,76,97
  2. 49,13,27,50,76,38,65,97
  3. 49,76,65,13,27,50,97,38
  4. 97,76,65,50,49,38,27,13

10.    2

2-11

给定初始待排序列{ 15，9，7，8，20，-1，4 }。如果希尔排序第一趟结束后得到序列为{ 15，-1，4，8，20，9，7 }，则该趟增量为： (2分)

  1. 1
  2. 2
  3. 3
  4. 4

11.   4

2-12

对N个元素采用简单选择排序，比较次数和移动次数分别为： (1分)

  1. O(N​2​​), O(N)
  2. O(N), O(logN)
  3. O(logN), O(N​2​​)
  4. O(NlogN), O(NlogN)

12.    1

2-13

对于10个数的简单选择排序，最坏情况下需要交换元素的次数为： (2分)

  1. 9
  2. 36
  3. 45
  4. 100

13.    1

2-14

对N个记录进行堆排序，最坏的情况下时间复杂度是： (1分)

  1. O(logN)
  2. O(N)
  3. O(NlogN)
  4. O(N​2​​)

14.    3

2-15

对N个记录进行堆排序，需要的额外空间为： (1分)

  1. O(1)
  2. O(logN)
  3. O(N)
  4. O(NlogN)

15.    1

各种排序算法所需辅助空间

1、 所有的简单排序方法（包括：直接插入、起泡和简单选择）和堆排序的空间复杂度为O(1)；


2、 快速排序为O(logn )，为栈所需的辅助空间；


3、 归并排序所需辅助空间最多，其空间复杂度为O(n )；


4、链式基数排序需附设队列首尾指针，则空间复杂度为O(rd )。


1 、直接插入排序：比较次数 最少n-1次；最多(n-1)(n+2)/2
移动次数 最少0； 最多(n-1)(n+4)/2
使用一个辅助存储空间，是稳定的排序；


2 、折半插入排序：比较次数 最少与最多同，都是n*log2n（其中2为底，下边表示同），
移动次数 最少0，最多时间复杂度为O(n2);(n的平方，以下也如此表示)；
使用一个辅助存储空间，是稳定的排序；

3 、冒泡排序： 比较最少为：n-1次，最多时间复杂度表示为o(n2);
移动次数最少为0，最多时间复杂度表示为O(n2);
使用一个辅存空间，是稳定的排序；

4 、简单选择排序： 比较次数没有多少之分，均是n(n-1)/2;
移动次数最少为0，最多为3(n-1);
使用一个辅存空间，是稳定的排序；


5 、快速排序：比较和移动次数最少时间复杂度表示为O(n*log2n);
比较和移动次数最多的时间复杂度表示为O(n2);
使用的辅助存储空间最少为log2n，最多为n的平方；是不稳定的排序；

6、 堆排序： 比较和移动次数没有好坏之分，都是O(n*log2n);
使用一个辅存空间，是不稳定的排序；

7、2-路归并排序：比较和移动次数没有好坏之分，都是O(n*log2n);
需要n个辅助存储空间，是稳定的排序；

相关文章