《《内部排序练习》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《内部排序练习》PPT课件.ppt（63页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、内部排序练习内部排序练习一、选择题一、选择题1.下述几种排序方法中，平均查找长度最小的下述几种排序方法中，平均查找长度最小的是（）。是（）。A插入排序插入排序B选择排序选择排序C快速排序快速排序D归并排序归并排序 C2.设设关关键键字字序序列列为为（3，7，6，9，7，1，4，5，20），对其进行排序的最小交换次数是），对其进行排序的最小交换次数是（）。（）。A6 B7 C8D20 A3.将将5个不同的数据进行排序，至少需要比较个不同的数据进行排序，至少需要比较（）次，至多需要比较（）次。）次，至多需要比较（）次。A4 B5 C6 D7E8 F9 G10 H11 AG4.下列排序算法中不稳定的
2、有（下列排序算法中不稳定的有（）。）。A直接选择排序直接选择排序 B直接插入排序直接插入排序C冒泡排序冒泡排序D二叉排序二叉排序EShell排序排序F快速排序快速排序G归并排序归并排序H堆排序堆排序I基数排序基数排序 A,E,F,H5.内部排序多个关键字的文件，最坏情况内部排序多个关键字的文件，最坏情况下最块的排序方法是（），相应的下最块的排序方法是（），相应的时间复杂度为（），该算法是时间复杂度为（），该算法是（）排序方法。（）排序方法。A快快速速排排序序B插插入入排排序序C归并排序归并排序 D简单选择排序简单选择排序EO(nlog2 n)FO(n2)GO(n2log2 n)HO(n)I稳定
3、稳定 J不稳定不稳定 CEI6.在在文文件件“局局部部有有序序”（待待排排序序元元素素序序列列基基本本有有序序）的的情情况况下下，最最佳佳内内部部排排序序算算法法是（）。是（）。A直直接接插插入入排排序序B冒泡排序冒泡排序C直直接接选选择择排排序序D基数排序基数排序 A7.对对初初始始状状态态为为递递增增的的表表按按递递增增顺顺序序排排序序，最最省省时时间间的的是是（）算算法法，最费时间的是（）算法。最费时间的是（）算法。A堆堆排排序序B快快速速排排序序C插入排序插入排序D归并排序归并排序 CB8.下述几种排序方法中，要求内存量最大的下述几种排序方法中，要求内存量最大的是（）。是（）。A插入排
4、序插入排序B选择排序选择排序C快速排序快速排序D归并排序归并排序 D9.在在下下面面的的排排序序方方法法中中，关关键键字字比比较较的的次次数与记录的初始排列次序无关的是数与记录的初始排列次序无关的是（）。（）。A希尔排序希尔排序 B冒泡排序冒泡排序 C插入排序插入排序 D选择排序选择排序 D10.下下列列排排序序中中，排排序序速速度度与与数数据据的的初初始始排排列状态没有关系的有（）。列状态没有关系的有（）。A直直接接选选择择排排序序B基基数数排排序序C堆排序堆排序D直接插入排序直接插入排序 B11.排排序序趟趟数数与与数数据据的的原原始始状状态态无无关关的的排排序序方法是（）排序法。方法是（
5、）排序法。A希希尔尔B选选择择C冒泡冒泡D快速快速 B12.若需在若需在O(nlog2 n)的时间内完成对的时间内完成对数组的排序，且要求排序是稳定的，数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。则可选择的排序方法是（）。A快速排序快速排序B堆排序堆排序C归并排序归并排序D直接插入排序直接插入排序 C13.排序方法中，从未排序序列中依次取出排序方法中，从未排序序列中依次取出元素与已排序序列（初始为空元素与已排序序列（初始为空）中的元素中的元素进行比较，将其放入已排序序列的正确位进行比较，将其放入已排序序列的正确位置上的方法，称为（）。置上的方法，称为（）。A希尔排序希尔排序B冒泡
6、排序冒泡排序C插入排序插入排序D选择排序选择排序 C14.每次把待排序的元素划分为左、右两个每次把待排序的元素划分为左、右两个子区间，其中左区间中元素的关键字均小子区间，其中左区间中元素的关键字均小于等于基准元素的关键字，右区间元素的于等于基准元素的关键字，右区间元素的关键字均大于基准元素的关键字，则此排关键字均大于基准元素的关键字，则此排序方法叫做（）。序方法叫做（）。A堆排序堆排序B快速排序快速排序C冒泡排序冒泡排序DShell排序排序 B15.排序方法中，从未排序序列中挑选元素，排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）并将其依次放入已排序序列（初始时为空
7、）的一端的方法，称为（）。的一端的方法，称为（）。A希尔排序希尔排序B归并排序归并排序C插入排序插入排序D选择排序选择排序 D16.用某种排序方法对线性表（用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序）进行排序时，元素序列的变化情况如下：列的变化情况如下：（1）（）（25，84，21，47，15，27，68，35，20）（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）则所采用的排序方法是（）。则
8、所采用的排序方法是（）。A选择排序选择排序B希尔排序希尔排序C归并排序归并排序D快速排序快速排序 D17.从未排序序列中依次取出元素与已排序从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序序列中的元素作比较，将其放入已排序序列中的正确位置上，此方法称为（）；列中的正确位置上，此方法称为（）；从未排序序列中挑选元素，并将其放入已从未排序序列中挑选元素，并将其放入已排序序列的一端，此方法称为（）；排序序列的一端，此方法称为（）；依次将每两个相邻的有序表合并成一个有依次将每两个相邻的有序表合并成一个有序表的排序方法叫做（）；当两个序表的排序方法叫做（）；当两个元素比较出现反序时
9、（即逆序）就相互交元素比较出现反序时（即逆序）就相互交换位置的排序方法叫做（）。换位置的排序方法叫做（）。A归并排序归并排序 B选择排序选择排序C交换排序交换排序 D插入排序插入排序 DBAC18.一组记录的关键字为（一组记录的关键字为（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，2
10、5，50，35，80，85，20，36，40，70）D（15，25，35，50，80，20，36，40，70，85）A19.n个记录的直接插入排序所需记录个记录的直接插入排序所需记录的关键码的最大比较次数为（）。的关键码的最大比较次数为（）。Anlog2 n Bn2/2 C(n+2)(n-1)/2 Dn-1 C20.n个记录的直接插入排序所需记录个记录的直接插入排序所需记录最小移动次数为（）。最小移动次数为（）。A2(n-1)Bn2/2 C(n+3)(n-2)/2 D2n A21.对以下关键字序列用快速排序法进行排对以下关键字序列用快速排序法进行排序，（）的情况排序最慢。序，（）的情况排序最慢
11、。A19，23，3，15，7，21，28B23，21，28，15，19，3，7C19，7，15，28，23，21，3D3，7，15，19，21，23，28 D22.快速排序在（）情况下最不利于发挥快速排序在（）情况下最不利于发挥其长处，在（）情况下最易发挥其长处。其长处，在（）情况下最易发挥其长处。A被排序的数据量很大被排序的数据量很大B被排序的数据已基本有序被排序的数据已基本有序C被排序的数据完全无序被排序的数据完全无序D被排序的数据中最大的值与最小值相差不大被排序的数据中最大的值与最小值相差不大E要排序的数据中含有多个相同值要排序的数据中含有多个相同值 BC23.在平均情况下，快速排序时间
12、复杂度为在平均情况下，快速排序时间复杂度为（），空间复杂度为（）；（），空间复杂度为（）；在最坏情况下（如初始记录已有序），快在最坏情况下（如初始记录已有序），快速排序的时间复杂度为（），空间速排序的时间复杂度为（），空间复杂度为（）。复杂度为（）。AO(n)BO(log2 n)CO(nlog2 n)DO(n2)CBDA24.一组记录的关键字为（一组记录的关键字为（45，80，55，40，42，85），则利用快速排序的方法，以第一个记），则利用快速排序的方法，以第一个记录为基准得到一次划分结果是录为基准得到一次划分结果是（）。（）。A（40，42，45，55，80，85）B（42，40，45，
13、80，55，85）C（42，40，45，55，80，85）D（42，40，45，85，55，80）C25.对对n个记录的线性表进行快速排序，为个记录的线性表进行快速排序，为减少算法的递归深度，以下途述正确的是减少算法的递归深度，以下途述正确的是（）。（）。A每次分区后，先处埋较短的部分每次分区后，先处埋较短的部分B每次分区后，先处埋较长的部分每次分区后，先处埋较长的部分C与算法每次分区后的处埋顺序无关与算法每次分区后的处埋顺序无关D以上都不对以上都不对 A26.直接插入排序和冒泡排序的平均时间复直接插入排序和冒泡排序的平均时间复杂度为（），若初始数据有序（即杂度为（），若初始数据有序（即正序）
14、，则时间复杂度为（）。正序），则时间复杂度为（）。AO(n)BO(log2 n)CO(nlog2 n)DO(n2)DA27.在直接选择排序中，记录比较次数为（在直接选择排序中，记录比较次数为（）数量级，记录的移动次数为（）数量级，记录的移动次数为（）数量级。数量级。AO(n)BO(log2 n)CO(n2)DO(nlog2 n)CA28.在堆排序过程中，由在堆排序过程中，由n个待排序的记录建成初个待排序的记录建成初始需要（）次筛选；由初始堆到堆排序始需要（）次筛选；由初始堆到堆排序结束需要进行（）次筛选；在每次筛运结束需要进行（）次筛选；在每次筛运算过程中，记录的比较和移动次数的数量级为算过程
15、中，记录的比较和移动次数的数量级为（），堆排序算法的时间复杂度为（），堆排序算法的时间复杂度为（）。）。AnBn/2Clog2 nDn-1EO(log2 n)FO(n)GO(nlog2 n)HO(n2)BDEG29.一组记录的关键字为（一组记录的关键字为（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）B30.下列序列中是堆的有（）。下列序列中是堆的有（）。A（12，
16、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）B,D31.设有设有1000个无序的元素，希望用个无序的元素，希望用最快的速度挑选出前最快的速度挑选出前20个最大的元素，个最大的元素，最好选用（）算法。最好选用（）算法。A冒泡排序冒泡排序B归并排序归并排序C堆排序堆排序D基数排序基数排序 C32.下列排序算法中，（）算下列排序算法中，（）算法会出现下面情况：在最后一趟结束法会出现下面情况：在最后一
17、趟结束之前，所有元素不在其最终的位置上。之前，所有元素不在其最终的位置上。A堆排序堆排序B冒泡排序冒泡排序C快速排序快速排序D插入排序插入排序 D33.在含有在含有n个元素的小根堆（堆顶元素最个元素的小根堆（堆顶元素最小）中，关键字最大的记录可能存储在小）中，关键字最大的记录可能存储在（）位置上。（）位置上。A BC 1 D D34.在归并排序中，归并趟数的数量级表在归并排序中，归并趟数的数量级表示为（），每趟需要进行记录的示为（），每趟需要进行记录的比较和移动次数的数量级表示为（比较和移动次数的数量级表示为（），归并排序算法的时间复杂度为（），归并排序算法的时间复杂度为（）。）。AO(n)B
18、O(log2 n)CO(nlog2 n)DO(n2)BAC35.在归并排序过程中，需归并的趟在归并排序过程中，需归并的趟数为（）。数为（）。AnBCD C36.已知数据表已知数据表A中每个元素距其最终的中每个元素距其最终的位置不远，则采用（）排序算法位置不远，则采用（）排序算法最省时间。最省时间。A堆排序堆排序B插入排序插入排序C直接选择排序直接选择排序D快速排序快速排序 B37.下列排序算法中，某一趟（轮）结束下列排序算法中，某一趟（轮）结束后未必能选出一个元素放在其最终位置后未必能选出一个元素放在其最终位置上的是（）。上的是（）。A堆排序堆排序B冒泡排序冒泡排序C直接插入排序直接插入排序D
19、快速排序快速排序 C38.快速排序算法在最好情况下的时快速排序算法在最好情况下的时间复杂度为（）。间复杂度为（）。AO(n)BO(n2)CO(nlog2 n)DO(log2 n)C39.快速排序方法在（）情况快速排序方法在（）情况下最不利于发挥其长处。下最不利于发挥其长处。A.要要排排序序的的数数据据量量太太大大 B要排序的数据中含有多个相同值要排序的数据中含有多个相同值C要排序的数据已基本有序要排序的数据已基本有序 D要排序的数据个数为奇数要排序的数据个数为奇数 C二、填空题二、填空题1.在在对对一一组组记记录录（50，40，95，20，15，70，60，45，80）进行希尔排序时，假定取）
20、进行希尔排序时，假定取 ,00it-1it-1，其其 中中 t=t=、d d0 0=n=n、d dt t=1=1，n n为为待待排排序序记记录录的的个个数数，则则第第二二趟排序结束后前趟排序结束后前4 4条记录为。条记录为。（1515，2020，5050，4040）2.在对一组记录在对一组记录（50,40,95,20,15,70,60,45,8050,40,95,20,15,70,60,45,80）进进行行直直接接插插排排序序时时，当当把把第第7 7个个记记录录6060插插入入到到有有序序表表时时，为为寻寻找插入位置需比较次。找插入位置需比较次。3 33.在在直直接接插插入入和和直直接接选选择
21、择排排序序中中，若若初初始始数数据据基基本本有有序序，则则选选用用，若若初初始始数数据据基基本反序，则选用。本反序，则选用。直接插入排序直接插入排序 直接选择排序直接选择排序 4.在对一组记录（在对一组记录（5050，4040，9595，2020，1515，7070，6060，4545，8080）进行直接选择排序时，第）进行直接选择排序时，第4 4次交换和次交换和选择后，未排序记录（即无序表）为选择后，未排序记录（即无序表）为。（5050，7070，6060，9595，8080）5.在对一组记录（在对一组记录（50，40，95，20，15，70，60，45，80）进行冒泡排序时，第一趟需进行相
22、）进行冒泡排序时，第一趟需进行相邻记录的交换的次数为，在整个邻记录的交换的次数为，在整个排序过程中共需进行趟才可完成。排序过程中共需进行趟才可完成。6 67 76.n个个记记录录的的冒冒泡泡排排序序算算法法所所需需最最大大移移动动次次数数为为，最小移动次数为。，最小移动次数为。3 3n(n-1)/2n(n-1)/2 0 0 7.如如果果n个个记记录录的的被被排排序序文文件件的的初初始始状状态态是是逆逆序序时时，采采用用冒冒泡泡排排序序算算法法，则则所所需需记记录录关关键键码码的的比比较较次次数数为为，记录移动次数为。记录移动次数为。n(n-1)/2n(n-1)/2 3n(n-1)/23n(n-
23、1)/2 8.对对n n个个元元素素的的序序列列进进行行冒冒泡泡排排序序，最最小小的的比比较较次次数数是是，此此时时元元素素的的排排列列情情况况，在在的的情情况况下下比比较较次次数最多，其比较次数为。数最多，其比较次数为。n-1 n-1 已从小到大排列已从小到大排列 元素从大到小排列元素从大到小排列 n(n-1)/2 n(n-1)/2 9.设设有有字字符符序序列列（Q Q，H H，C C，Y Y，P P，A A，M M，S S，E E，D D，F F，X X）要求按字符升序排列，则：要求按字符升序排列，则：（1 1）采采用用初初始始步步长长为为4 4的的ShellShell排排序序，一一趟扫描
24、的结果是：。趟扫描的结果是：。（2 2）采采用用以以首首元元素素为为分分界界元元素素的的快快速速排排序，一趟扫描的结果是：。序，一趟扫描的结果是：。(E(E，A A，C C，S S，P P，D D，F F，X X，Q Q，H H，M M，Y)Y)(F(F，H H，C C，D D，P P，A A，M M，E E，Q Q，S S，Y Y，X)X)10.对对n n个个结结点点进进行行快快速速排排序序，最最大大比比较较次次数是。数是。n(n-1)/2n(n-1)/2 11.利利用用快快速速排排序序方方法法记记录录（50，40，95，20，15，70，60，45，80）进进行行快快速速排排序序，其其需需
25、递递归归调调用用的的次次数数为为，其其中中第第二二次次次次递递归归调调用用是是对对一一组组记记录录进行快速排序。进行快速排序。6 6 （4545，4040，1515，2020）12.从从时时间间上上看看，快快速速排排序序的的平平均均性性能能好好于于其其他他排排序序方方法法，但但从从空空间间上上看看，快快速速排排序序需需要要一一个个栈栈空空间间来来实实现现递递归归，若若每每一一趟趟快快速速排排序序都都将将记记录录序序列列均均匀匀地地分分割割成成长长度度相相接接近近的的两两个个序序列列，则则栈栈的的最最大大深深度度（含含最最外外层层也也进进栈栈）为为；在在最最坏坏情情况况下下，栈栈的的深深度度为为
26、；如如果果每每次次先先对对较较短短的的子子序序列列进进行行快快速速排排序序，则则栈栈的的最最大大深深度度降降为为；所所需需要要的的附附加加空空间间为为。O(n)O(n)O(logO(log2 2 n)n)O(logO(log2 2 n)n)13.在在对对一一组组记记录录（50，40，95，20，15，70，60，45，80）进进行行（大大根根）堆堆排排序序时时，根根据据初初始始记录构成初始堆后，最后记录构成初始堆后，最后4条记录为条记录为 。;(50(50，6060，4040，20)20)14.在在堆堆排排序序和和快快速速排排序序中中，若若原原始始状状态态记记录录接接近近正正序序或或反反序序，
27、则则选选用用，若若原原始始记记录无序，则最好选用。录无序，则最好选用。堆排序堆排序 快速排序快速排序 15.对对于于直直接接插插入入排排序序，冒冒泡泡排排序序，简简单单选选择择排排序，堆排序，快速排序有：序，堆排序，快速排序有：（1 1）当当文文件件“局局部部有有序序”或或文文件件长长度度较较小小的的情情况下，最佳的内部排序方法是。况下，最佳的内部排序方法是。（2 2）快快速速排排序序在在最最坏坏情情况况下下时时间间复复杂杂度度是是比性能差。比性能差。（3 3）就平均时间而言，最佳。）就平均时间而言，最佳。直接插入排序直接插入排序 O(nO(n2 2)，堆排序堆排序 快速排序快速排序 16.在
28、在插插入入排排序序、希希尔尔排排序序、选选择择排排序序、快快速速排排序序、堆堆排排序序、归归并并排排序序和和基基数数排排序序中中，排排序序是是不不稳定的有。稳定的有。希尔排序、选择排序、快速排序和堆排序希尔排序、选择排序、快速排序和堆排序 17.在在内内部部排排序序中中，平平均均比比较较次次数数最最少少的的是是，要要求求附附加加的的内内存存容容量量最最大大的的是是，排排序序时时不不稳稳定定的的有有等等几几种种方法。方法。快速排序快速排序 归并排序归并排序 希尔排序，堆排序，快速排序，选择排序希尔排序，堆排序，快速排序，选择排序 18.在在归归并并排排序序中中，若若待待排排序序记记录录的的个个数
29、数为为20，则则共共需需要要进进行行趟趟归归并并，在在第第三三趟趟归归并并中中是是把把长长度度为为的的有有序序表表归归并并为为长长度为的序表。度为的序表。5 5 4 4 8 8 19.在在堆堆排排序序，快快速速排排序序和和归归并并排排序序中中，若若只只从从存存储储空空间间考考虑虑，则则应应首首先先选选取取方方法法，其其次次选选用用方方法法，最最后后选选取取方方法法；若若只只从从排排序序结结果果的的稳稳定定性性考考虑虑，则则应应选选取取 方方法法；若若只只从从平平均均情情况况下下排排序序最最快快考考虑虑，则则应应选选取取方方法法；若若只只从从最最坏坏情情况况下下排排序序最最快快并并且且要要节节省
30、省内内存存考考虑虑，则则应应选选取取方法。方法。堆排序，快速排序，归并排序，归并排序，快速排序，堆排序堆排序，快速排序，归并排序，归并排序，快速排序，堆排序20.目目前前以以比比较较操操作作为为基基础础的的内内部部排排序序的的时时间间复复杂杂度度T（m）的的范范围围是是；其其比比较较次次数与待排序记录的初始状态无关的是。数与待排序记录的初始状态无关的是。O(nlogO(nlog2 2 n n)O(nO(n2 2)直接选择排序直接选择排序 21.设设有有一一个个n n个个元元素素的的堆堆R R，有有R(iR(i)R(2i)R(2i)且且R(iR(i)R(2i+1)R(2i+1)，取取出出堆堆中中最最大大元元素素后后，将将它它重重新调整成堆所需时间复杂度为。新调整成堆所需时间复杂度为。O(logO(log2 2 n)n)22.在在插插入入排排序序、希希尔尔排排序序、选选择择排排序序、快快速速排排序序、堆堆排排序序、归归并并排排序序和和基基数数排排序序中中，平平均均比比较较次次数数最最少少的的是是，需需要要内内存存容容量量最最多多的是。的是。快速排序快速排序基数排序基数排序