资源描述：
《《数据结构》习题汇编09 第九章 排序 试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构课程（本科）第九章试题一、单项选择题1.若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（）方法比较次数最少。A.直接插入排序B.快速排序C.归并排序D.直接选择排序2.如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。A.起泡排序B.快速排序C.直接选择排序D.堆排序3.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（）。A.直接选择排序B.直接插入排序C.快速排序D.
2、起泡排序4.对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较？A.8B.10C.15D.255.如果输入序列是已经排好顺序的，则下列算法中（）算法最快结束？A.起泡排序B.直接插入排序C.直接选择排序D.快速排序6.如果输入序列是已经排好顺序的，则下列算法中（）算法最慢结束？A.起泡排序B.直接插入排序C.直接选择排序D.快速排序7.下列排序算法中（）算法是不稳定的。A.起泡排序B.直接插入排序C.基数排序D.快速排序8.假设某文件经过内部排序得到100个初始归并段，那么如果要求利用多路平衡
3、归并在3趟内完成排序，则应取的归并路数至少是（）。A.3B.4C.5D.69.采用任何基于排序码比较的算法，对5个互异的整数进行排序，至少需要（）次比较。A.5B.6C.7D.810.下列算法中（）算法不具有这样的特性：对某些输入序列，可能不需要移动数据对象即可完成排序。A.起泡排序B.希尔排序C.快速排序D.直接选择排序1.使用递归的归并排序算法时，为了保证排序过程的时间复杂度不超过O(nlog2n)，必须做到（）。A.每次序列的划分应该在线性时间内完成B.每次归并的两个子序列长度接近C.每次归并在线
4、性时间内完成D.以上全是2.在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于O(nlog2n)。A.起泡排序B.希尔排序C.归并排序D.快速排序3.在下列排序算法中，（）算法使用的附加空间与输入序列的长度及初始排列无关。A.锦标赛排序B.快速排序C.基数排序D.归并排序4.一个对象序列的排序码为{46,79,56,38,40,84}，采用快速排序（以位于最左位置的对象为基准而）得到的第一次划分结果为：A.{38,46,79,56,40,84}B.{38,79,56,46,40,84}
5、C.{40,38,46,79,56,84}D.{38,46,56,79,40,84}5.如果将所有中国人按照生日（不考虑年份，只考虑月、日）来排序，那么使用下列排序算法中（）算法最快。A.归并排序B.希尔排序C.快速排序D.基数排序参考答案：1.A2.D3.C4.B5.A 6.D7.D8.C9.C10.C11.D12.C13.C14.C15.D一、填空题1.第i(i=1,2,…,n-1)趟从参加排序的序列中取出第i个元素，把它插入到由第0个～第i-1个元素组成的有序表中适当的位置，此种排序方法叫做___
6、_____排序。2.第i(i=0,1,…,n-2)趟从参加排序的序列中第i个～第n-1个元素中挑选出一个最小（大）元素，把它交换到第i个位置，此种排序方法叫做________排序。3.每次直接或通过基准元素间接比较两个元素，若出现逆序排列，就交换它们的位置，这种排序方法叫做________排序。4.每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做________排序。5.在直接选择排序中，排序码比较次数的时间复杂度为O(________)。6.在直接选择排序中，数据对象移动次数的时间复杂度为O(
7、________)。1.在堆排序中，对n个对象建立初始堆需要调用________次调整算法。2.在堆排序中，如果n个对象的初始堆已经建好，那么到排序结束，还需要从堆顶结点出发调用________次调整算法。3.在堆排序中，对任一个分支结点进行调整运算的时间复杂度为O(________)。4.对n个数据对象进行堆排序，总的时间复杂度为O(________)。5.给定一组数据对象的排序码为{46,79,56,38,40,84}，则利用堆排序方法建立的初始堆（最大堆）为________。6.快速排序在平均情况
8、下的时间复杂度为O(________)。7.快速排序在最坏情况下的时间复杂度为O(________)。8.快速排序在平均情况下的空间复杂度为O(________)。9.快速排序在最坏情况下的空间复杂度为O(________)。10.给定一组数据对象的排序码为{46,79,56,38,40,84}，对其进行一趟快速排序，结果为________。11.在n个数据对象的二路归并排序中，每趟归并的时间复杂度为O(________)。12.在n个数据
