第10章内部排序.doc

习题十一、选择题1在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。A希尔排序 B冒泡排序 C。插入排序 D选择排序2设有1000个无序的记录，希望用最快的速度挑选出其中前10个最大的记录，最好选用( )排序法。A冒泡排序 B快速排序 C堆排序 D基数排序3，在待排序的记录序列基本有序的前提下，效率最高的排序方法是 )。A插入排序 B选择排序 C快速排序 D归并排序4不稳定的排序方法是指在排序中，关键字值相等的不同记录的前后相对位置( )。A保持不变 B保持相反 C不定 D无关5内部排序是指在排序的整个过程中，全部数据都在计算机的( )中完成的排序。A内存储器 B外存储器 C内存储器和外存储器 D寄存器6用冒泡排序的方法对n个数据进行排序，第一趟共比较( )对记录。A1 B2 Cn-1 Dn7直接插入排序的方法是从第( )个记录开始，插入前边适当位置的排序方法。A1 B2 C3 Dn8用堆排序的方法对n个数据进行排序，首先将n个记录分成( )组。A1 B2 Cn-1 Dn9归并排序的方法对n个数据进行排序，首先将n个记录分成( )组，两两归并。A1 B2 Cn-1 D，n10直接插入排序的方法要求被排序的数据( )存储。A必须是顺序 B必须是链表 C顺序或链表 D二叉树11冒泡排序的方法要求被排序的数据( )存储。A必须是顺序 B必须是链表 C顺序或链表 D二叉树12快速排序的方法要求被排序的数据( )存储。A必须是顺序 B必须是链表 C顺序或链表 D二叉树13排序方法中，从未排序序列中依次取出记录与已排序序列(初始时为空)中的记录进行比较，将其放入已排序序列的正确位置上的方法，称为( )。A希尔排序 B冒泡排序 C插入排序 D选择排序14每次把待排序的记录划分为左、右两个子序列，其中左序列中记录的关键字均小于等于基准记录的关键字，右序列中记录的关键字均大于基准记录的关键字，则此排序方法叫做( )。A堆排序 B快速排序 C冒泡排序 DShell排序15排序方法中，从未排序序列中挑选记录，并将其依次放入已排序序列(初始时为空)的一端的方法，称为( )。A希尔排序 B归并排序 C插入排序 D选择排序16用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时，记录序列的变化情况如下：(1)(25,84,21,47,15,27,68,35,40) (2)(20,15,21,25,47,27,68,35,84) (3)(15,20,21,25,35,27,47,68,84) (4)(15,20,21,25,27,35,47,68,84) 则所采用的排序方法是( )。A选择排序 B希尔排序 C归并排序 D快速排序17一组记录的关键字为(25,50,15,35,80,85,20,40,36,70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果为( )。A(15,25,35,50,20,40,80,85,36,70) B(15,25,35,50,80,20,85,40,70,36)C(15,25,50,35,80,85,20,36,40,70) D(15,25,35,50,80,20,36,40,70,85)18n个记录的直接插入排序所需记录关键码的最大比较次数为( )。Anlog2n Bn2/2 C(n+2)(n-1)/2 Dn-119n个记录的直接插入排序所需的记录最小移动次数为( )。A 2(n-1) Bn2/2 C(n+3)(n-2)/2 D2n20对以下关键字序列用快速排序法进行排序，( )的情况排序最慢。A19,23,3,15,7,21,28 B23,21,28,15，19,3,7C19，7，15,28,23,21，3 D3,7,15,19,21,23,2821快速排序在( )情况下最不利于发挥其长处，在( )情况下最易发挥其长处。A被排序的数据量很大 B被排序的数据已基本有序 C被排序的数据完全无序D被排序的数据中最大的值与最小值相差不大 E要排序的数据中含有多个相同值22一组记录的关键字为(45，80，55，40，42，85)，则利用快速排序的方法，以第一个记录为基准得到一次划分结果是( )。A(40,42,45,55,80,85) B(42,40,45,80,55,85)C(42,40,45,55,80,85) D(42,40,45,85,55,80)23对n个记录的线性表进行快速排序，为减少算法的递归深度，以下叙述正确的是( )。A每次分区后，先处理较短的部分 B每次分区后，先处理较长的部分C与算法每次分区后的处理顺序无关 D以上都不对24直接插入排序和冒泡排序的平均时间复杂度为( )，若初始数据有序(即正序)，则时间复杂度为( )。A O(n) B O(10g2n) C O(nlog2n) D O(n2)25一组记录的关键字为(45,80,55,40,42,85)，则利用堆排序的方法建立的初始堆为( )。A(80,45,55,40,42,85) B(85,80,55,40,42,45) C(85,80,55,45,42,40) D(85,55,80,42,45,40)26下列序列中是堆的有( )。A(12,70,33,65,24,56,48,92,86,33) B(100,86,48,73,35,39,42,57,66,21)C(103,56,97,33,66,23,42,52,30,12) D(5，56,20,23,40,38,29,61,35,76) 27设有1000个无序的记录，希望用最快的速度挑选出前20个最大的记录，最好选用( )算法。A冒泡排序 B归并排序 C堆排序 D基数排序28下列排序算法中，( )算法会出现下面情况：在最后一趟结束之前，所有记录不在其最终的位置上。A堆排序 B冒泡排序 C快速排序 D插入排序29在含有n个记录的小根堆(堆顶记录最小)中，关键字最大的记录可能存储在( )位置上。An/2 Bn/2-2 C1 Dn/2+330已知数据表A中每个记录距其最终位置不远，则采用( )算法最省时间。A堆排序 B插入排序 C直接选择排序 D快速排序31，下列排序算法中，某一趟(轮)结束后未必能选出一个记录放在其最终位置上的是A堆排序 B冒泡排序 C直接插入排序 D快速排32已知待排序的n个记录可分为n/k个组，每个组包含k个记录，且任一组内的各记录均分别大于前一组内的所有记录并小于后一组内的所有记录，若采用基于比较的排序，其时间下界应为( )。AO(nlog2n) BO(nlog2k) CO(klog2n) DO(klog2k)33若要尽可能地完成对实数数组的排序，且要求排序是稳定的，则应选( )。A快速排序 B堆排序 C归并排序 D基数排序34在含有n个记录的大根堆(堆顶记录最大)中，关键字最小的记录可能存储在( )位置上。An/2 Bn/2-1 C1 Dn/2+135对任意的7个关键字进行排序，至少要进行( )次关键字之间的两两比较。A13 B，14 C15 D，16二、填空题1排序是将一组任意排列的记录按_的值从小到大或从大到小重新排列成有序的序列。2，在排序前，关键字值相等的不同记录间的前后相对位置保持_的排序方法称为稳定的排序方法。3在排序前，关键字值相等的不同记录间的前后相对位置_的排序方法称为不稳定的排序方法。4，外部排序是指在排序前被排序的全部数据都存储在计算机的_存储器中。5写出一种不稳定的排序方法的名称_。6在直接插入排序的方法中，当需要将第f个数据插入时，此时前i-1个数据是_的。7对一个基本有序的数据进行排序，_排序方法运算次数最小。8在对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较_次。9在利用快速排序方法对一组记录(54，38，96，23，15，72，60，45，83)进行快速排序时，递归调用而使用的栈所能达到最大深度为_，共递归调用的次数为_，其中第二次递归调用是对_组进行快速排序。10在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取_方法，其次选取_，最后选取_方法；若只从排序结果的稳定性考虑，则应选取_：若只从平均情况下排序最快考虑，则应选取_；若只从最坏情况下排序最快并且要节省内存考虑，则应选取_方法。11在堆排序和快速排序中，若原始记录接近正序或反序，则选用_，若原始记录无序，则最好选用_。12在考虑如何选择排序中，若初始数据基本正序，则选用_：若初始数据基本反序，则选用_。13对n个记录的序列进行冒泡排序时，最少的比较次数是_。三、简答题1已知序列：17，18，60，40，7，32，73，65，85，请给出采用冒泡排序法对该序列作升序排序时每一趟的结果。2已知序列：503，87，512，61，908，170，897，275，653，462)，请给出采用快速排序法对该序列作升序排序时每一趟的结果。3已知序列：503，87，512，61，908，170，897，275，653，462，请给出采用基数排序法对该序列作升序排序时的每一趟的结果。4已知序列：503，17，5