第十章内排习题

《第十章内排习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第十章内部排序一，选择1.基于比较方法的n个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是（）。A.O(nlogn)B.O(logn)C.O(n)D.O(n*n)2．下列排序算法中，其中（）是稳定的。A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序3．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。A．直接插入B．直接选择C．堆D．快速4．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。A.快速排序B.堆排序C.归并排序D.直

2、接插入排序5.有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（）A．-1，4，8，9，20，7，15，7B．-1，7，15，7，4，8，20，9C．-1，4，7，8，20，15，7，9D．A，B，C均不对。6．在排序算法中每一项都与其它各项进行比较，计算出小于该项的项的个数，以确定该项的位置叫()A．插入排序B．枚举排序C．选择排序D．交换排序7．就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（）A．堆排序〈　快速排序〈归并排序B．堆排序〈　归并排序〈快速排序C．堆排序〉归并排序〉快速排序D

3、．堆排序>快速排序>归并排序8．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（）。A．直接插入排序B.气泡排序C.快速排序D.直接选择排序9．将两个各有N个元素的有序表归并成一个有序表,其最少的比较次数是()A．NB．2N-1C．2ND．N-110．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。A．(38,40,46,56,79,84)B.(40,38,46,79,56,84)C．(40,38,46,56,79,84)D.(40,38,46,84,56,79)

4、11.在下面的排序方法中，辅助空间为O（n）的是()。A．希尔排序B.堆排序C.选择排序D.归并排序12．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是()排序。A．冒泡B.希尔C.快速D.堆13.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（）。A.直接插入排序B.快速排序C.直接选择排序D.堆排序14.以下序列不是堆的是()。A.(100,85,98,77,80,60,82,40,20,10,66)B.B.(100,98,85,82,80,77,66,60,40,20,10)C.

5、(10,20,40,60,66,77,80,82,85,98,100)3A.D.(100,85,40,77,80,60,66,98,82,10,20)15．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。A．起泡排序B．快速排列C．Shell排序D．堆排序E．简单选择排序1.A2.D3.A4.C5.C6.B7.A8.D9.A10.C11.D12.C13.B14.D15.D二，判断1．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（）2．内排序要求数据一定

6、要以顺序方式存储。（）3．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（）4．直接选择排序算法在最好情况下的时间复杂度为O（N）。（）5．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（）6．在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n)。（）7．快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。（）8．堆肯定是一棵平衡二叉树。（）9．堆是满二叉树。（）10．（101，88，46，70，34，39，45，58，66，10）是堆。（）1.√2.×3.×4.

7、×5.×6.×7.×8.×9.×10.√三，应用题1.对下面数据表，写出采用SHELL排序算法排序的每一趟的结果，并标出数据移动情况。（125，11，22，34，15，44，76，66，100，8，14，20，2，5，1）。2.给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：(1)归并排序每归并一次书写一个次序。(2)快速排序每划分一次书写一个次序。(3)堆排序先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。1.125，11，22，34，15，44，76，66，100，8，1

8、4，20，2，5，1设D=71，11，8，14，15，2，5，66，100，22，34，20，44，76，125D=31，11，2，5，