资源描述：
《第10章 内部排序习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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.采用任何基于排序码比较的算法，对5个互异的整数进行排序，至少需要（）次比较。A.5B.6C.7D.810.下列算
3、法中（）算法不具有这样的特性：对某些输入序列，可能不需要移动数据对象即可完成排序。A.起泡排序B.希尔排序C.快速排序D.直接选择排序11.使用递归的归并排序算法时，为了保证排序过程的时间复杂度不超过O(nlog2n)，必须做到（）。A.每次序列的划分应该在线性时间内完成B.每次归并的两个子序列长度接近C.每次归并在线性时间内完成D.以上全是1.在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于O(nlog2n)。A.起泡排序B.希尔排序C.归并排序D.快速排序2.一个对象序列的排序码为{46,79,5
4、6,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}参考答案：1.A2.D3.C4.B5.A 6.D7.D8.C9.C10.C11.D12.C13.C一、填空题1.第i(i=1,2,…,n-1)趟从参加排序的序列中取出第i个元素，把它插入到由第0个~第i-1个元素组成的有序表中适当的位置，此种排序方法叫做______
5、__排序。2.第i(i=0,1,…,n-2)趟从参加排序的序列中第i个～第n-1个元素中挑选出一个最小（大）元素，把它交换到第i个位置，此种排序方法叫做________排序。3.每次直接或通过基准元素间接比较两个元素，若出现逆序排列，就交换它们的位置，这种排序方法叫做________排序。4.每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做________排序。5.在直接选择排序中，排序码比较次数的时间复杂度为O(________)。6.在直接选择排序中，数据对象移动次数的时间复杂度为O(________)。7.
6、在堆排序中，对n个对象建立初始堆需要调用________次调整算法。8.在堆排序中，如果n个对象的初始堆已经建好，那么到排序结束，还需要从堆顶结点出发调用________次调整算法。9.在堆排序中，对任一个分支结点进行调整运算的时间复杂度为O(________)。10.对n个数据对象进行堆排序，总的时间复杂度为O(________)。11.给定一组数据对象的排序码为{46,79,56,38,40,84}，则利用堆排序方法建立的初始堆（最大堆）为________。1.快速排序在平均情况下的时间复杂度为O(________)
7、。2.快速排序在最坏情况下的时间复杂度为O(________)。3.快速排序在平均情况下的空间复杂度为O(________)。4.快速排序在最坏情况下的空间复杂度为O(________)。5.给定一组数据对象的排序码为{46,79,56,38,40,84}，对其进行一趟快速排序，结果为________。6.在n个数据对象的二路归并排序中，每趟归并的时间复杂度为O(________)。7.在n个数据对象的二路归并排序中，整个归并的时间复杂度为O(________)。参考答案：1.插入2.直接选择3.交换4.两路归并5.n2
8、6.n7.ën/2û8.n-19.log2n10.nlog2n11.84,79,56,38,40,4612.nlog2n13.n214.log2n15.n16.[4038]46[795684]17.n18.nlog2n三、判断题1.直接选择排序是一种稳定的排序方法。2.若将一批杂乱无章的数据按堆结构组织起来,则堆中各
