内部排序习题

1、第 10 章 内部排序 习题、单项选择题1. 若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（ ）方法比较次数最少。A. 直接插入排序B.快速排序C. 归并排序D.直接选择排序2. 如果只想得到 1024 个元素组成的序列中的前 5 个最小元素，那么用（）方法最快。A. 起泡排序B.快速排序C. 直接选择排序D.堆排序3. 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作， 直到子序列为空或只剩一个元素为止。这样的排序方法是（）。A. 直接选择排序B. 直接插入排序C. 快速排序D. 起泡排序4. 对 5 个不同的数据元素进行直接插入排序，最多需

2、要进行（）次比较？A. 8B. 10C. 15D. 255. 如果输入序列是已经排好顺序的，则下列算法中（ ）算法最快结束？A. 起泡排序B. 直接插入排序C. 直接选择排序D. 快速排序6. 如果输入序列是已经排好顺序的，则下列算法中（ ）算法最慢结束？ A. 起泡排序B.直接插入排序C. 直接选择排序D.快速排序7. 下列排序算法中（ ）算法是不稳定的。A. 起泡排序B.直接插入排序C. 基数排序D.快速排序8.9. 采用任何基于排序码比较的算法，对A. 5 B. 65 个互异的整数进行排序，至少需要（C. 7 D. 8）次比较。10. 下列算法中（）算法不具有这样的特性：对某些输入序列，

3、可能不需要移动数据对象即可完成排序。A. 起泡排序B.希尔排序C. 快速排序D.直接选择排序11.使用递归的归并排序算法时，为了保证排序过程的时间复杂度不超过O（nlog2n），必须做到（）。A. 每次序列的划分应该在线性时间内完成B. 每次归并的两个子序列长度接近C. 每次归并在线性时间内完成D. 以上全是12. 在基于排序码比较的排序算法中， (A. 起泡排序C. 归并排序)算法的最坏情况下的时间复杂度不高于O(nlog 2n)。B. 希尔排序D. 快速排序13. 一个对象序列的排序码为 46, 79, 56, 38, 40, 84 ，采用快速排序(以位于最左位置的对象为基准而) 得到的第

4、一次划分结果为：A. 38, 46, 79, 56, 40, 84 C. 40, 38, 46, 79, 56, 84 B. 38, 79, 56, 46, 40, 84 D. 38, 46, 56, 79, 40, 84 参考答案：1. A2. D3. C4. B5. A6. D7. D8. C9. C10. C11. D12. C13. C、填空题1.第i (i = 1,2,n1)趟从参加排序的序列中取出第的有序表中适当的位置，此种排序方法叫做 i 个元素，把它插入到由第 0 个第 i- 1 个元素组成 排序。2. 第i (i = 0, 1,-2)-趟从参加排序的序列中第i个第n-1个元素

5、中挑选出一个最小(大)元素，把它交换到第 i 个位置，此种排序方法叫做 排序。3. 每次直接或通过基准元素间接比较两个元素，若出现逆序排列，就交换它们的位置，这种排序方法叫做排序。4. 每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做排序。5. 在直接选择排序中，排序码比较次数的时间复杂度为 O() 。6. 在直接选择排序中，数据对象移动次数的时间复杂度为 O()。7. 在堆排序中，对 n 个对象建立初始堆需要调用 次调整算法。8. 在堆排序中， 如果 n 个对象的初始堆已经建好， 那么到排序结束， 还需要从堆顶结点出发调用 次调整算法。9. 在堆排序中，对任一个分支结点进行调整运算的

6、时间复杂度为O()。10. 对 n 个数据对象进行堆排序，总的时间复杂度为 O()。11. 给定一组数据对象的排序码为 46, 79, 56, 38, 40, 84 ，则利用堆排序方法建立的初始堆(最大堆)为o16. 给定一组数据对象的排序码为46, 79, 56, 38, 40, 84，对其进行一趟快速排序，结果为 17. 在n个数据对象的二路归并排序中，每趟归并的时间复杂度为0()。18. 在n个数据对象的二路归并排序中，整个归并的时间复杂度为0()。参考答案：1.插入2.直接选择3.交换4. 两路归并5. n26. n7. |lp/28. n-19. log 2n10. nlog 2n1

7、1.84, 79,56, 38, 40, 4612. nlog2n213. n14. log 2n15. n16. 40 38 46 79 56 8417. n18. nlog2n三、判断题1. 直接选择排序是一种稳定的排序方法。2. 若将一批杂乱无章的数据按堆结构组织起来，则堆中各数据是否必然按自小到大的顺序排列起来。3. 当输入序列已经有序时，起泡排序需要的排序码比较次数比快速排序要少。4. 在任何情况下，快速排序需要进行的排序码比较的次数都是0( nl og2 n)。5. 在2048个互不相同的排序码中选择最小的5个排序码，用堆排序比用锦标赛排序更快。6. 若用m个初始归并段参加 k路平

8、衡归并排序，则归并趟数应为logzm。7. 堆排序是一种稳定的排序算法。8. 对于某些输入序列，起泡排序算法可以通过线性次数的排序码比较且无需移动数据对象就可以完成排 序。9. 如果输入序列已经排好序，则快速排序算法无需移动任何数据对象就可以完成排序。10. 希尔排序的最后一趟就是起泡排序。11. 任何基于排序码比较的算法，对n个数据对象进行排序时，最坏情况下的时间复杂度不会低于0(n log 2n)。9次排序码的比较，就可以对任何6个排序12. 不存在这样一个基于排序码比较的算法：它只通过不超过 码互异的数据对象实现排序。参考答案：1.否2.否3.是4.否5.否6.否7.否8.是9.否10.

9、是11.是12.是四、运算题1. 判断以下序列是否是小根堆？如果不是，将它调整为小根堆。(1) 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 (2) 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 。2. 在不要求完全排序时，堆排序是一种高效的算法。这种算法的过程是：(Heapification )把待排序序列看作一棵完全二叉树，通过反复筛选将其调整为堆; (Re-heapification )依次取出堆顶，然后将剩余的记录重新调整为堆。现考虑序列 A = 23，41，7, 5，56 :(1) 给出对应于序列 A的小根堆Ha (以

10、线性数组表示)；(2) 给出第一次取出堆顶后，重新调整Ha后的结果(以线性数组表示)；(3) 给出第二次取出堆顶后，重新调整Ha后的结果(以线性数组表示)。3. 希尔排序、直接选择排序、快速排序和堆排序是不稳定的排序方法，试举例说明。参考答案:1.(1) 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 为最大堆。调整为小根堆后为 21,35, 39, 57, 86, 48, 42, 73, 66, 100 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 不是最小堆。调整为小根堆后为 12, 24, 33, 65, 33, 56, 48, 92, 86, 70 2.(1)建堆结果Ha =52374156(2)第一次取出堆顶，并重新调整后Ha =7 23 56 41(3) 第二次取出堆顶，并重新调整后Ha = 2341563.(1)希尔排序 512275275*061 增量为2 275*061512275 增量为1 061275*275512 直接选择排序 275275*512061 i=1 061275*512275 i = 2 061275*512275 i = 3 061275*275512 快速排序 512275275*