《数据结构专科辅导八94615.doc》由会员分享，可在线阅读，更多相关《数据结构专科辅导八94615.doc（12页珍藏版）》请在金锄头文库上搜索。
1、数据结构专科辅导八94615敢于浪费哪怕一个钟头时间的人，说明他还不懂得珍惜生命的全部价值。 达尔文数据结构专科辅导八-排序的辅导练习题及解答 （一）单项选择题 1. 若对n个元素进行直接插入排序，则进行第i趟排序过程前，有序表中的元素个数为（ ）。 A n B n+1 C n-1 D 1 2. 若对n个元素进行直接插入排序，在进行第i趟排序时，为寻找插入位置最多需要进行（ ）次元素的比较，假定第0号元素放有待查的键值。 A n B n-1 C n+1 D 1 3. 若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素ri+1的插入位置为rj，则需要移动元素的次数为（ ）。 A j-i
2、B i-j-1 C i-j D i-j+1 4. 若对n个元素进行直接插入排序，则进行任一趟排序的过程中，为寻找插入位置而需要的时间复杂性为（ ）。 A O(1) B O(n) C O(n2) D O(log2n) 5. 在对n个元素进行直接插入排序的过程中，共需要进行（ ）趟。 A n B n+1 C n-1 D 2n 6. 对n个元素进行直接插入排序时间复杂性为（ ）。 A O(1) B O(n) C O(n2) D O(log2n) 7. 在对n个元素进行冒泡排序的过程中，第一趟排序至多需要进行（ ）对相邻元素之间的交换。 A n B n-1 C n+1 D n/2 8. 在对n个元素进
3、行冒泡排序的过程中，最好情况下的时间复杂性为（ ）。 A O(1) B O(log2n) C O(n2) D O(n) 9. 在对n个元素进行冒泡排序的过程中，至少需要（ ）趟完成。 A 1 B n C n-1 D n/2 10. 在对n个元素进行快速排序的过程中，若每次划分得到的左、右两个子区间中元素的个数相等或只差一个，则整个排序过程得到的含两个或两个元素的区间个数大致为（ ）。 A n B n/2 C log2n D 2n 11. 在对n个元素进行快速排序的过程中，第一次划分最多需要移动（ ）次元素，包括开始把基准元素移动到临时变量的一次在内。 A n/2 B n-1 C n D n+1
4、 12. 在对n个元素进行快速排序的过程中，最好情况下需要进行（ ）躺。 A n B n/2 C log2n D 2n 13. 在对n个元素进行快速排序的过程中，最坏情况下需要进行（ ）躺。 A n B n-1 C n/2 D log2n 14. 在对n个元素进行快速排序的过程中，平均情况下的时间复杂性为（ ）。 A O(1) B O(log2n) C O(n2) D O(nlog2n) 15. 在对n个元素进行快速排序的过程中，最坏情况下的时间复杂性为（ ）。 A O(1) B O(log2n) C O(n2) D O(nlog2n) 16. 在对n个元素进行快速排序的过程中，平均情况下的空
5、间复杂性为（ ）。 A O(1) B O(log2n) C O(n2) D O(nlog2n) 17. 在对n个元素进行快速排序的过程中，最坏情况下的空间复杂性为（ ）。 A O(1) B O(log2n) C O(n2) D O(nlog2n) 18. 在对n个元素进行直接插入排序的过程中，算法的空间复杂性为（ ）。 A O(1) B O(log2n) C O(n2) D O(nlog2n) 19. 假定对元素序列（3, 7, 5, 9, 1）进行快速排序，则进行第一次划分时需要移动元素的次数为（ ），假定不包括开始把基准元素移动到临时变量的一次计算在内。 A 1 B 2 C 3 D 4 2
6、0. 对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（ ）。 A 1, 3, 5, 7, 9 B 9, 7, 5, 3, 1 C 5, 3, 1, 7, 9 D 5, 7, 9, 1, 3 21. 假定对元素序列（7, 3, 5, 9, 1, 12, 8, 15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（ ）。 A 2 B 3 C 4 D 5 22在对n个元素进行直接选择排序的过程中，需要进行（ ）趟选择和交换。 A n B n+1 C n-1 D n/2 22在对n个元素进行直接选择排序的过程中，在第i趟需要
7、从（ ）个元素中选择出最小值元素。A A n-i+1 B n-i C i D i+1 23. 若对n个元素进行直接选择排序，则进行任一趟排序的过程中，为寻找最小值元素所需要的时间复杂性为（ ）。 A O(1) B O(log2n) C O(n2) D O(n) 24. 若对n个元素进行堆排序，则在构成初始堆的过程中需要进行（ ）次筛运算。 A 1 B n/2 C n D n-1 25. 若对n个元素进行堆排序，则在由初始堆进行每躺排序的的过程中，共需要进行（ ）次筛运算。 A n+1 B n/2 C n D n-1 26. 若对n个元素进行堆排序，则每次进行筛运算的时间复杂性为( )。 A O
8、(1) B O(log2n) C O(n2) D O(n) 27. 在对n个元素进行堆排序的过程中，时间复杂性为（ ）。 A O(1) B O(log2n) C O(n2) D O(nlog2n) 28. 在对n个元素进行堆排序的过程中，空间复杂性为（ ）。 A O(1) B O(log2n) C O(n2) D O(nlog2n) 29. 假定对元素序列（7, 3, 5, 9, 1, 12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为（ ）。 A 1, 3, 5, 7, 9, 12 B 1, 3, 5, 9, 7, 12 C 1, 5, 3, 7, 9, 12 D 1, 5, 3,
9、 9, 12, 7 30. 假定一个初始堆为(1, 5, 3, 9, 12, 7, 15, 10)，则进行第一趟堆排序后得到的结果为（ ）。 A 3, 5, 7, 9, 12, 10, 15, 1 B 3, 5, 9, 7, 12, 10, 15, 1 A 3, 7, 5, 9, 12, 10, 15, 1 B 3, 5, 7, 12, 9, 10, 15, 1 31. 若对n个元素进行归并排序，则进行归并的趟数为（ ）。 A n B n-1 C n/2 D ?log2n? 32. 若对n个元素进行归并排序，则进行每一趟归并的时间复杂性为（ ）。 A O(1) B O(log2n) C O(n
10、) D O(n2) 33. 若一个元素序列基本有序，则选用（ ）方法较快。 A 直接插入排序 B 直接选择排序 C 堆排序 D 快速排序 34. 若要从1000个元素中得到10个最小值元素，最好采用（ ）方法。 A 直接插入排序 B 直接选择排序 C 堆排序 D 快速排序 35. 若要对1000个元素排序，要求既快又稳定，则最好采用（ ）方法。 A 直接插入排序 B 归并排序 C 堆排序 D 快速排序 36. 若要对1000个元素排序，要求既快又节省存储空间，则最好采用（ ）方法。 A 直接插入排序 B 归并排序 C 堆排序 D 快速排序 37. 在下列排序方法中，空间复杂性为O(log2n)
11、的方法为（ ）。 A 直接选择排序 B 归并排序 C 堆排序 D 快速排序 38. 在平均情况下速度最快的排序方法为（ ）。 A 直接选择排序 B 归并排序 C 堆排序 D 快速排序 （二）填空题 1每次从无序子表中取出一个元素，把它插入到有序子表中的适当位置，此种排序方法叫做_排序；每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做_排序。 2每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做_排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做_排序。 3在直接选择排序中，记录比较次数的时间复杂性为_，记录移动次数的时间复杂性为_。 4. 在堆排序的过程中，对n个记录建立初始堆需要进行_次筛运算，由初始堆到堆排序结束，需要对树根结点进行_次筛运算。 5在堆排序的过程中，对任一分支结点进行筛运算的时间复杂性为_，整个堆排序过程的时间复杂性为_
