《第0章内部排序习题》由会员分享，可在线阅读，更多相关《第0章内部排序习题（6页珍藏版）》请在金锄头文库上搜索。
1、页眉内容第10章内部排序习题1、单项选择题1. 若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（A.直接插入排序B.快速排序C.归并排序D.直接选择排序）方法比较次数最少。2. 如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。A.起泡排序B.快速排序C.直接选择排序D.堆排序3. 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（）。A.直接选择排序B.直接插入排序C.快速排序D.起泡排序4.对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较？A.8B.10
2、C.15D.255. 如果输入序列是已经排好顺序的，则下列算法中（A.起泡排序B.直接插入排序C.直接选择排序D.快速排序）算法最快结束？6.如果输入序列是已经排好顺序的，则下列算法中（）算法最慢结束？A.起泡排序C.直接选择排序B.直接插入排序D.快速排序7.下列排序算法中（A.起泡排序C.基数排序）算法是不稳定的。B.直接插入排序D.快速排序8.9. 采用任何基于排序码比较的算法，对5个互异的整数进行排序，至少需要（）次比较。A.5B.6C.7D.810. 下列算法中（）算法不具有这样的特性：对某些输入序列，可能不需要移动数据对象即可完成排序。A.起泡排序B.希尔排序C.快速排序D.直接选
3、择排序11.使用递归的归并排序算法时，为了保证排序过程的时间复杂度不超过O（nlog2n）,必须做到（）。A. 每次序列的划分应该在线性时间内完成B. 每次归并的两个子序列长度接近C.每次归并在线性时间内完成D.以上全是12. 在基于排序码比较的排序算法中，()算法的最坏情况下的时间复杂度不高于O(nlog2n)。A.起泡排序B.希尔排序C.归并排序D.快速排序13. 一个对象序列的排序码为46,79,56,38,40,84，采用快速排序(以位于最左位置的对象为基准而)得到的第一次划分结果为：A.38,46,79,56,40,84B.38,79,56,46,40,84C.40,38,46,79
4、,56,84D.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个元素中挑选出一个最小(大)元素，把它交换到第i个位置，此种排序方法叫做排序。3. 每次直接或通过基准元素间接比较两个元素，若出现逆序排列，就交换它们的位置，这种排序方法叫做排序。4. 每次使两个相邻的有序表合并成一个有序表，这种排
5、序方法叫做排序。5. 在直接选择排序中，排序码比较次数的时间复杂度为O()。6. 在直接选择排序中，数据对象移动次数的时间复杂度为O()。7. 在堆排序中，对n个对象建立初始堆需要调用次调整算法。8. 在堆排序中，如果n个对象的初始堆已经建好，那么到排序结束，还需要从堆顶结点出发调用次调整算法。9. 在堆排序中，对任一个分支结点进行调整运算的时间复杂度为O()。10. 对n个数据对象进行堆排序，总的时间复杂度为O()。11. 给定一组数据对象的排序码为46,79,56,38,40,84，则利用堆排序方法建立的初始堆(最大堆)为12.快速排序在平均情况下的时间复杂度为O()。13.快速排序在最坏
6、情况下的时间复杂度为O()14.快速排序在平均情况下的空间复杂度为O()15.快速排序在最坏情况下的空间复杂度为O()16. 给定一组数据对象的排序码为46,79,56,38,40,84，对其进行一趟快速排序，结果为。17. 在n个数据对象的二路归并排序中，每趟归并的时间复杂度为O()。18. 在n个数据对象的二路归并排序中，整个归并的时间复杂度为O()。参考答案：1.插入2.直接选择3.交换4.两路归并5.n26.n7. n/28.n-19.log2n12. nlog 2n10. nlog2n11.84,79,56,38,40,4613. n214.log2n15.n17. n18. nlo
7、g 2n16. 403846795684三、判断题1. 直接选择排序是一种稳定的排序方法。2. 若将一批杂乱无章的数据按堆结构组织起来,则堆中各数据是否必然按自小到大的顺序排列起来。3. 当输入序列已经有序时，起泡排序需要的排序码比较次数比快速排序要少。4. 在任何情况下，快速排序需要进行的排序码比较的次数都是O(nlog2n)。5. 在2048个互不相同的排序码中选择最小的5个排序码，用堆排序比用锦标赛排序更快。6. 若用m个初始归并段参加k路平衡归并排序，则归并趟数应为log2m。7. 堆排序是一种稳定的排序算法。8. 对于某些输入序列，起泡排序算法可以通过线性次数的排序码比较且无需移动数
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,6
9、6,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 .希尔排序、直接选择排序、快速排序和堆排序是不稳定的排
10、序方法，试举例说明。参考答案：1. (1)100,86,48,73,35,39,42,57,66,21为最大堆。调整为小根堆后为21,35,39,57,86,48,42,73,66,100(2)12,70,33,65,24,56,48,92,86,33不是最小堆。调整为小根堆后为12,24,33,65,33,56,48,92,86,702. (1)建堆结果Ha=52374156(2)第一次取出堆顶，并重新调整后Ha=7235641(3)第二次取出堆顶，并重新调整后Ha=2341563. (1)希尔排序512275275*061增量为2275*061512275增量为1061275*275512(2)直接选择排序275275*512061i=1061275*512275i=2061275*512275i=3061275*275512快速排序512275275*275*275512(4)堆排序275275*061170已经是最大堆，交换275与170170275*061275对前3个调整275*170061275前3个最大堆，交换275*与061061170275*275对前2个调整170061275*275前2个最大堆，交换170与061061170275*275#
