数据结构11章习题

第十一章

一、单项选择题

1、对任意的七个关键字进行排序，至少要进行（ ）次关键字之间的两两比较。 A、13 B、14 C、15 D、16 E、17

2、排序方法中，从未排序序列中依次取出元素与已排列序列(初始时为空)中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ ）。 A希尔排序 B冒泡排序 C插入排序 D选择排序

3、在文件“局部有序”或文件长度较小的情况下，最佳内排序方法是（ ）。 A直接插入排序 B冒泡排序 C直接选择排序 D归并排序 4、在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ ）。 A插入排序 B选择排序 C快速排序 D归并排序

5、在下列算法中，（ ）算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。

A堆排序 B冒泡排序 C插入排序 D快速排序

6、对记录的关键字为{50,26,38,80,70,90,8,30,40,20}进行排序，各趟排序结束时的结果是： 50 26 38 80 70 90 8 30 40 20 50 8 30 40 20 90 26 38 80 70 26 8 30 40 20 80 50 38 90 70 8 20 26 30 38 40 50 70 80 90 其使用的排序方法是（ ）。

A快速排序 B基数排序 C希尔排序 D归并排序

7、对给出的一组关键字{14,5,19,20,11,19}。若按关键字非递减排序，第一趟排序结果是{14,5,19,20,11,19}，问采用的排序方法是（ ）。

A简单选择排序 B快速排序 C希尔排序 D二路归并排序

8、在对n各元素进行冒泡排序的过程中，最好情况下的时间复杂度为（ ）。 A 、O(1) B、O（log2n） C、O(n2) D、 O(n)

9、一组记录的关键码为（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

10、用某种排序方法对线性表（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 所采用的排序方法是（ ）。

A选择排序 B希尔排序 C归并排序 D快速排序 11、快速排序方法在（ ）情况下嘴不利于发挥其长处。 A要排序的数据量太大 B要排序的数据中含有多个相同值 C要排序的数据已基本有序 D要排序的数据个数为奇数

12、快速排序在最坏的情况下时间复杂度是O(n2)，比（ ）的性能差。 A堆排序 B冒泡排序 C选择排序

13、采用直接选择排序，比较的次数与移动次数分别是（ ）。 A 、O(n)，O（log2n） B、 O（log2n），O(n2) C、O(n2)，O(n) D、O（nlog2n），O(n)

14、如果对你n各元素进行直接选择排序，则进行任一趟排序的过程中，为寻找最小值元素所需要的时间复杂度为（ ）。

A、O（1） B、O（log2n） C、O(n2) D、O(n)

15、在所有的排序方法中，关键字比较的次数与记录德尔初始排列次序无关的是（ ）。 A希尔排序 B冒泡排序 C插入排序 D选择排序

16、排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ ）。

A希尔排序 B归并排序 C插入排序 D选择排序

17、在对n各元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。 A 、O（log2n） B、O（1） C、O（n） D、O（nlog2n）

18、一组记录的排序码为（46,79,56,38,40,84,），则利用堆排序（建立大根堆）的方法建立的初始堆为（ ）。

A、79,46,56,38,40,80 ,B、84,79,56,38,40,46, C、84,79,56,46,40,38 D、84,56,79,40,46,38

19、设有1000各无序的元素，希望用最快的速度挑选出其中的前10各最大的元素，最好选用（ ）排序的方法。

A冒泡排序 B快速排序 C堆排序 D基数排序 20、以下序列不是堆的是（ ）。

A（100,85,98,77,80,60,82,40,20,10,66,） B（100,98,85,82,80,77,66,60,40,20,10） C（10,20,40,60,66,77,80,82,85,98,100） D（100,85,40,77,80,60,66,98,82,10,20） 21、一组记录的排序码为（25,48,16,35,79,82,23,40,36,72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（ ）。

A16 25 35 48 23 40 79 82 36 72 B16 25 35 48 79 82 23 36 40 72 C16 25 48 35 79 82 23 36 40 72 D16 25 35 48 79 23 36 40 72 82

22、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。 A、n B、2n-1 C、2n D、n-1

23、就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是（ ）。 A堆排序<快速排序<归并排序 B堆排序<归并排序<快速排序 C堆排序>归并排序>快速排序 D堆排序>快速排序>归并排序 E以上答案都不对

24、下述几种排序方法中，要求内存最大的是（ ）。 A插入排序 B选择排序 C快速排序 D归并排序 25、外排序是指（ ）。 A在外存上进行的排序方法 B不需要使用内存的排序方法 C数据很大，需要人工干预的排序方法

D排序前后数据在外存，排序时数据调入内存的排序方法

26、堆外排序的k路平衡归并，采用败方树时，归并效率与k（ ）。 A有关 B无关

27、有m个初始归并段，采用k路归并时，所需归并遍数是（ ）。 A log2k ??logKm?? B log2m C logKm D ??logKm??

二简答题

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、已知序列{70,83,100,65,10,32,7,9}，请给出采用插入排序法对该序列作升序排序时的每一趟结果。

5、已知序列{10,18,4,3,6,12,1,9,18,8}，请给出采用希尔排序法对该序列作升序排序时的每一趟的结果。

6、已知序列{10,18,4,3,6,12,1,9,18,8}，请给出采用归并排序法对该序列作升序排序时的每一趟的结果。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数据结构11章习题在线全文阅读。