排序NoAnswer

一、选择题

1、用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时，无序序列的变化情况如下：

25 84 21 47 15 27 68 35 20 20 15 21 25 47 27 68 35 84 15 20 21 25 35 27 47 68 84 15 20 21 25 27 35 47 68 84

则所采用的排序方法是（ D ）

A.选择排序 B.C.归并排序 D.快速排序

2、下列排序算法中 C 排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 选择 B. 冒泡 C. 归并 D. 堆

3、在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为 D 。

A.n B.log2n C.(h+1)/2 D.h

4、有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为 （ C） A．-1，4，8，9，20，7，15，7 B．-1，7，15，7，4，8，20，9 C．-1，4，7，8，20，15，7，9 D．A，B，C 均不对。

5、快速排序在某些情况下其优点不能发挥，这种情况是（ C）。

A.待排序的数据量大 B. 待排序的数据相同值过多 C. 待排序的数据已基本有序 D. 待排序的数据值差过大

6、 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ C ）。

A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序

7、对记录的关键码{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为：C

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.归并排序 8、堆的形状是一棵_C______。

A.二叉排序树 B.满二叉树 C.完全二叉树 D.平衡二叉树

9、以下序列不是堆的是（D ）

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 10、 稳定的排序方法是（ B ）。

A．快速排序 B．起泡排序 C．简单选择排序 D． shell排序

11、一组记录的关键字为{45，80，55，42，40，85}，利用快速排序法并以第一个记录为基准得到的第一趟划分结果是（ A ）。

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

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

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

二、选择题

1、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为（ n2-n/2 ）。

2、对关键字序列（50，34，92，19，11，68，56，41，79）进行直接插入排序，当将第7个关键字56插入到当前的有序子表中，为寻找插入位置需进行（ 3 ）次比较。 3、每一趟排序时从排好序的元素中挑出一个值最小的元素与这些未排小序的元素的第一个元素交换位置，这种排序方法成为________简单_____排序法。

4、分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是（ 冒泡 ）算法，最费时间的是（ 快速排序 ）算法。

5、 在堆排序、快速排序和归并排序中，若只从最坏情况下排序最快并且要节省内存考虑，则应选取（ 堆 ）方法。

6、若对顺序存储在A[l]～A[9]的记录(76，38，62，53，80，74，83，65，85)进行堆排序，已知除第一个元素76外，以其余元素为根的结点都已是堆，则对第一个元素进行筛运算时，它将最终被筛到A数组下标为（ 98 ）的位置上。

7、 对关键字序列（47，55，24，96，13，87，65，38，17）取增量为3，进行一趟希尔排序之后得到的结果为 47、13、24、96、55、87、65、13、96、38、87、 。

三、应用题

1、对关键字序列（72，87，61，23，94，16，5，58）进行直接插入排序，使之关键字递增有序，请写出每趟结果。 2、有一随机数组(25,84,21,46,13,27,68,35,20),现采用某种方法对它们进行排序,其每趟排序结果如下, 则该排序方法是什么？并给出该方法的基本思想。

初 始:25,84,21,46,13,27,68,35,20 第一趟:20,13,21,25,46,27,68,35,84 第二趟:13,20,21,25,35,27,46,68,84 第三趟:13,20,21,25,27,35,46,68,843、判3、判断下面的序列是否是堆？如果不是，则把它调整为堆：

（5，56，20，23，40，38，29，61，35，76，28，100）

4、若对序列(49,38,27,13,97,76,50,65)采用起泡排序法(按照值的大小从小到大)进行排序，请

分别在下表中写出每一趟排序的结果。

原始序列 49 38 27 13 97 76 50 65 第1趟的结果： 第2趟的结果： 第3趟的结果： 第4趟的结果：

5、已知一组键值序列为(41，66，73，52，40，37，65，43)，试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。

本文来源：https://www.bwwdw.com/article/scph.html