《数据结构》习题汇编09 第九章 排序 试题.docx
12页
本文格式为Word版，下载可任意编辑《数据结构》习题汇编09 第九章 排序 试题 数据布局课程（本科）第九章试题 一、单项选择题 1. 若待排序对象序列在排序前已按其排序码递增依次排列，那么采用（ ）方法对比次数最少 A. 直接插入排序 B. 快速排序 C. 归并排序 D. 直接选择排序 2. 假设只想得到1024个元素组成的序列中的前5个最小元素，那么用（ ）方法最快 A. 起泡排序 B. 快速排序 C. 直接选择排序 D. 堆排序 3. 对待排序的元素序列举行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作， 直到子序列为空或只剩一个元素为止这样的排序方法是（ ） A. 直接选择排序 B. 直接插入排序 C. 快速排序 D. 起泡排序 4. 对5个不同的数据元素举行直接插入排序，最多需要举行（ ）次对比？ A. 8 B. 10 C. 15 D. 25 5. 假设输入序列是已经排好依次的，那么以下算法中（ ）算法最快终止？ A. 起泡排序 B. 直接插入排序 C. 直接选择排序 D. 快速排序 6. 假设输入序列是已经排好依次的，那么以下算法中（ ）算法最慢终止？ A. 起泡排序 B. 直接插入排序 C. 直接选择排序 D. 快速排序 7. 以下排序算法中（ ）算法是不稳定的。
A. 起泡排序 B. 直接插入排序 C. 基数排序 D. 快速排序 8. 假设某文件经过内部排序得到100个初始归并段，那么假设要求利用多路平衡归并在3 趟内完成排序，那么应取的归并路数至少是（ ） A. 3 B. 4 C. 5 D. 6 9. 采用任何基于排序码对比的算法，对5个互异的整数举行排序，至少需要（ ）次对比 A. 5 B. 6 C. 7 D. 8 10. 以下算法中（ ）算法不具有这样的特性：对某些输入序列，可能不需要移动数据对象即可完成 排序 A. 起泡排序 B. 希尔排序 C. 快速排序 D. 直接选择排序 11. 使用递归的归并排序算法时，为了保证排序过程的时间繁杂度不超过O(nlog2n)，务必做到（ ） A. 每次序列的划分理应性时间内完成 B. 每次归并的两个子序列长度接近 C. 每次归并性时间内完成 D. 以上全是 12. 在基于排序码对比的排序算法中，（ ）算法的最坏处境下的时间繁杂度不高于O(nlog2n)。
A. 起泡排序 B. 希尔排序 C. 归并排序 D. 快速排序 13. 在以下排序算法中，（ ）算法使用的附加空间与输入序列的长度及初始排列无关 A. 锦标赛排序 B. 快速排序 C. 基数排序 D. 归并排序 14. 一个对象序列的排序码为 { 46, 79, 56, 38, 40, 84 }，采用快速排序（以位于最左位置的对象为基准而） 得到的第一次划分结果为： A. { 38, 46, 79, 56, 40, 84 } B. { 38, 79, 56, 46, 40, 84 } C. { 40, 38, 46, 79, 56, 84 } D. { 38, 46, 56, 79, 40, 84 } 15. 假设将全体中国人按照生日（不考虑年份，只考虑月、日）来排序，那么使用以下排序算法中（ ） 算法最快 A. 归并排序 B. 希尔排序 C. 快速排序 D. 基数排序 参考答案： 1. A 6. D 11. D 2. D 7. D 12. C 3. C 8. C 13. C 4. B 9. C 14. C 5. A 10. C 15. D 二、填空题 1. 第i (i = 1, 2, …, n-1) 趟从加入排序的序列中取出第i个元素，把它插入到由第0个～第i-1个元素组 成的有序表中适当的位置，此种排序方法叫做________排序。
2. 第i (i = 0, 1, …, n-2) 趟从加入排序的序列中第i个～第n-1个元素中挑拣出一个最小（大）元素，把 它交换到第i个位置，此种排序方法叫做________排序 3. 每次直接或通过基准元素间接对比两个元素，若展现逆序排列，就交换它们的位置，这种排序方法叫 做________排序 4. 每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做________排序 5. 在直接选择排序中，排序码对比次数的时间繁杂度为O(________) 6. 在直接选择排序中，数据对象移动次数的时间繁杂度为O(________) 7. 在堆排序中，对n个对象建立初始堆需要调用________次调整算法 8. 在堆排序中，假设n个对象的初始堆已经建好，那么到排序终止，还需要从堆顶结点启程调用________ 次调整算法 9. 在堆排序中，对任一个分支结点举行调整运算的时间繁杂度为O(________) 10. 对n个数据对象举行堆排序，总的时间繁杂度为O(________) 11. 给定一组数据对象的排序码为 { 46, 79, 56, 38, 40, 84 }，那么利用堆排序方法建立的初始堆（最大堆）为 ________。
12. 快速排序在平均处境下的时间繁杂度为O(________) 13. 快速排序在最坏处境下的时间繁杂度为O(________) 14. 快速排序在平均处境下的空间繁杂度为O(________) 15. 快速排序在最坏处境下的空间繁杂度为O(________) 16. 给定一组数据对象的排序码为 {46, 79, 56, 38, 40, 84}，对其举行一趟快速排序，结果为________ 17. 在n个数据对象的二路归并排序中，每趟归并的时间繁杂度为O(________) 18. 在n个数据对象的二路归并排序中，整个归并的时间繁杂度为O(________) 参考答案： 1. 插入 2. 直接选择 3. 交换 4. 两路归并 5. n2 6. n 7. ?n/2? 10. nlog2n 13. n2 16. [40 38] 46 [79 56 84] 8. n-1 11. 84, 79, 56, 38, 40, 46 14. log2n 17. n 9. log2n 12. nlog2n 15. n 18. nlog2n 三、判断题 1. 直接选择排序是一种稳定的排序方法。
2. 若将一批杂乱无章的数据按堆布局组织起来, 那么堆中各数据是否必然按自小到大的依次排列起来 3. 当输入序列已经有序时，起泡排序需要的排序码对比次数比快速排序要少 4. 在任何处境下，快速排序需要举行的排序码对比的次数都是O(nlog2n) 5. 在2048 个互不一致的排序码中选择最小的5个排序码，用堆排序比用锦标赛排序更快 6. 若用m个初始归并段加入k路平衡归并排序，那么归并趟数应为 ?log2m? 7. 堆排序是一种稳定的排序算法 8. 对于某些输入序列，起泡排序算法可以通过线性次数的排序码对比且无需移动数据对象就可以完成排 序 9. 假设输入序列已经排好序，那么快速排序算法无需移动任何数据对象就可以完成排序 10. 希尔排序的结果一趟就是起泡排序 11. 任何基于排序码对比的算法，对n个数据对象举行排序时，最坏处境下的时间繁杂度不会低于 O(nlog2n) 12. 不存在这样一个基于排序码对比的算法：它只通过不超过9次排序码的对比，就可以对任何6个排序 码互异的数据对象实现排序。
参考答案： 1. 否 2. 否 3. 是 4. 否 5. 否 6. 否 7. 否 8. 是 9. 否 10. 是 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（以线性数组表示）； (2) 给出第一次取出堆顶后，重新调整HA后的结果（以线性数组表示）； (3) 给出其次次取出堆顶后，重新调整HA后的结果（以线性数组表示） 3. 希尔排序、直接选择排序、快速排序和堆排序是不稳定的排序方法, 试举例说明。
4. 给出12个初始归并段，其长度分别为19, 22, 17, 16, 11, 10, 12, 32, 26, 20, 28, 07现要做4路外归并排序， 试画出表示归并过程的最正确归并树，并计算该归并树的带权路径长度WPL 5. 设输入文件包含以下数据对象的排序码：14, 22, 7, 16, 11, 10, 12, 90, 26, 30, 28, 110现采用置换—选择 方法生成初始归并段，并假设内存工作区可同时容纳5个数据对象，请画出世成初始归并段的过程 6. 在利用置换—选择方法生成初始归并段时，可另开发一个与工作区容量一致的辅佐存储区（称为储蓄 库）当输入对象排序码小于刚输出的门槛LastKey对象的排序码时，不将它存入工作区，而暂存于 储蓄库中，接着输入下一对象的排序码，依次类推，直到储蓄库满时不再举行输入，而只是从工作区中选择对象输出直至工作区空为止，由此得到一个初始归并段。
