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

本是古典何须时尚 2022-04-13 14:14 189阅读 0赞

1-1

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

T F

1.F

1-2

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

T F

2.T

1-3

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

T F

3.F

1-4

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

T F

4.F

2-1

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

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

1. 3

2-2

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

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

2. 4

2-3

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

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

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(N2)
4.  O(N2logN)

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(N2), O(N)
2.  O(N), O(logN)
3.  O(logN), O(N2)
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(N2)

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个辅助存储空间，是稳定的排序；