计算机专业基础综合数据结构（排序）-试卷2(总分：56.00，做题时间：90分钟)一、单项选择题(总题数：16，分数：32.00)1.单项选择题1-40小题。

下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

（分数：2.00）__________________________________________________________________________________________解析：2.采用简单选择排序，比较次数与移动次数分别为( )。

（分数：2.00）A.O(n)，O(log 2 n)B.O(log 2 n)，O(n 2 )C.O(n 2 )，O(n) √D.O(nlog 2 n)，O(n)解析：解析：简单选择排序的关键字比较次数KCN与对象的初始排列无关。

第i趟选择具有最小关键字对象所需的比较次数总是n—i—1次(此处假定整个待排序对象序列有n个对象)。

因此，总的关键字比较次最坏情况是每一趟都要进行交换，总的对象移动次数为RMN=3(n一1)。

3.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是( )。

（分数：2.00）A.堆排序＜快速排序＜归并排序√B.堆排序＜归并排序＜快速排序C.堆排序＞归并排序＞快速排序D.堆排序＞快速排序＞归并排序解析：解析：此题考查的知识点为排序的空间复杂性。

堆排序辅助空间为O(1)，快速排序为O(log 2 n)，归并排序为O(n)。

应选A。

4.一组记录的关键码为(25，48，16，35，79，82，23，40，36，72)，其中，含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。

（分数：2.00）A.16，25，35，48，23，40，79，82，36，72 √B.16，25，35，48，79，82，23，36，40，72C.16，25，48，35，79，82，23，36，40，72D.16，25，35，48，79，23，36，40，72，82解析：解析：对于(25，48，16，35，79，82，23，40，36，72)，(25，48)和(16，35)归并的结果为(16，25，35，48)。

(79，82)和(23，40)归并后的结果为(23，40，79，82)，余下的两个记录不归并，所以一趟归并后的结果为(16，25，35，48，23，40，79，82，36，72)，本题答案为A。

5.已知10个数据元素为(54，28，16，34，73，62，95，60，26，43)，对该序列按从小到大排序，经过一趟冒泡排序后的序列为( )。

（分数：2.00）A.16，28，34，54，73，62，60，26，43，95B.28，16，34，54，62，73，60，26，43，95 √C.28，16，34，54，62，60，73，26，43，95D.16，28，34，54，62，60，73，26，43，95解析：解析：冒泡排序每趟经过比较、交换，从无序区中产生一个最大的元素，所以选B。

6.用某种排序方法对线性表(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 其所采用的排序方法是( )。

（分数：2.00）A.直接选择排序√B.希尔排序C.归并排序D.快速排序解析：解析：可以看到，每趟从无序区中找出一个最大的元素定位，所以答案为A。

7.在对一组记录(50，40，95，20，15，70，60，45，80)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较( )次。

（分数：2.00）A.1B.2C.3 √D.4解析：解析：第6趟的结果为(15，20，40，50，70，95，60，45，80)，此时插入60，要与95、70和50进行比较，共比较3次，本题答案为C。

8.将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是( )。

（分数：2.00）A.N √B.2N一1C.2ND.N一1解析：解析：此题考查的知识点是归并排序思想。

当第一个有序表中所有的元素都小于第二个表中元素，或者都大于第二个表中元素时，比较次数最少为N。

9.已知待排序的n个元素可分为n／k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。

（分数：2.00）A.O(nlog 2 n)B.O(nlog 2 k) √C.O(klog 2 n)D.O(klog 2 k)解析：解析：此题考查的知识点是分块排序的思想。

因组与组之间已有序，故将n／k个组分别排序即可，基于比较的排序方法每组的时间下界为O(klog 2k)。

可以用二叉树分治形式描述，最好的情况是树的高度为log 2 k。

全部时间下界为O(nlog 2 k)。

应选B。

10.已知关键序列5，8，12，19，28，20，15，22是小根堆(最小堆)，插入关键字3，调整后得到的小根堆是( )。

（分数：2.00）A.3，5，12，8，28，20，15，22，19 √B.3，5，12，19，20，15，22，8，28C.3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，19整后的小根堆为3，5，12，8，28，20，15，22，19。

11.归并排序中，归并的趟数是( )。

（分数：2.00）A.O(n)B.O(log 2 n) √C.O(nlog 2 n)D.O(n 2 )解析：解析：此题考查的知识点是归并排序。

第1遍归并的子序列长度为2 0，第2遍为2 1，…，第i 遍为2 i-1，所以由2 i-1≥n知，对n个记录的数据集合，总共需要归并log 2 n次。

应选B。

12.有一组数据(15，9，7，8，20，一1，7，4)，用堆排序的筛选方法建立的初始堆为( )。

（分数：2.00）A.一1，4，8，9，20，7，15，7B.一1，7，15，7，4，8，20，9C.一1，4，7，8，20，15，7，9 √D.A、B、C均不对解析：解析：此题考查的知识点是堆排序。

应选C。

13.基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。

（分数：2.00）A.O(nlog 2 n) √B.O(log 2 n)C.O(n)D.D(n 2 )解析：解析：此题考查的知识点是各类排序的效率。

理论上可以证明，对于基于关键字之间比较的分类，无论用什么方法都至少需要进行log 2 (n!)次比较。

由Stirling公式可知，log 2 (n!)=nlog 2 n一1．44n+O(log 2 n)。

所以基于关键字比较的分类时间的下界是O(nlog 2 n)。

因此不存在时间复杂性低于此下界的基于关键字比较的分类。

应选A。

14.以下排序方法中，稳定的排序方法是( )。

（分数：2.00）A.直接插入排序√B.直接选择排序C.堆排序D.基数排序解析：解析：下表为各种排序方法的性能比较。

由表可知，本题答案为A15.在对一组记录(50，40，95，20，15，70，60，45，80)进行希尔排序时，假定d 0=9，d 1=4，d 2=2，d 3 =1，则第二趟排序结束后前4条记录为( )。

（分数：2.00）A.(50，20，15，70)B.(60，45，80，50)C.(15，20，50，40) √D.(15，20，80，70)解析：解析：t=3，d 0 =9，d 1 =4，d 2 =2，d 3 =1，第1趟(d 1 =4)后的结果为(15，40，60，20，50，70，95，45，80)，第2趟(d 2=2)后的结果为(15，20，50，40，60，45，80，70，95)，本题答案为(15，20，50，40)。

16.在归并排序中，若待排序记录的个数为20，则共需要进行( )趟归并，在第三趟归并中，是把长度为( )的有序表归并为长度为( )的有序表。

（分数：2.00）A.5，4，8 √B.6，3，9C.7，4，3D.3，8，2解析：解析：n=20，共需进行[log 2 n]=5趟归并，第1趟归并后成为10个有序表，第2趟归并后成为5个有序表(每个长度为4)，第3趟归并将长度为4个的有序表归并为长度为8的有序表，本题答案为：5，4，8.二、综合应用题(总题数：12，分数：24.00)17.综合应用题41-47小题。

（分数：2.00）__________________________________________________________________________________________ 解析：18.已知关键字序列(K 1，K 2，K 3，…，K n-1 )是大根堆。

试写出一算法将(K 1，K 2，K 3，…，K n-1，K n )调整为大根堆，并利用调整算法写一个建大根堆的算法。

（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：void sift(RecType R[]，int n){ ／／把R[n]调成大堆int j=n；R[0]=R[j]；for(i=n ／2；i＞=1；i=i／2) if(R[0]．key＞R[i]．key){R[j]=R[i]；j=i；} else break；R[j]=R[0]；} void HeapBuilder(RecType R[]，int n){ for(i=2；i＜=n；i++)sift(R，i)； } 提示：此题考查的知识点是堆的插入算法。

从第n个记录开始依次与其双亲(n／2)比较，若大于双亲则交换，继而与其双亲的双亲比较，以此类推直到根为止。

)解析：19.最小最大堆(min max Heap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。

最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。

如图所示为一最小最(1)画出在图中插入关键字为5的结点后的最小最大堆。

(2)画出在图中插入关键字为80的结点后的最小最大堆。

(3)编写一算法实现最小最大堆的插入功能。

假定最小最大堆存放在数组中，关键字为整数。

（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：此题考查的知识点是堆的算法。