计算机专业基础综合数据结构（排序）历年真题试卷汇编9
(总分：72.00，做题时间：90分钟)
一、 综合题(总题数：21，分数：62.00)
解答问题（分数：8.00）
(1).设某文件中待排序记录的排序码为72，73，71，23，94，1 6，05，68，试画图表示出树形选择排序(增序)过程的前三步。（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：解析：
(2).试说明树形选择排序的基本思想。（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：树形选择排序的基本思想：首先对n个待排序记录的关键字进行两两比较，从中选出 [n／2]个较小者再两两比较，直到选出关键字最小的记录为止，此为一趟排序。我们将一趟选出的关键字最小的记录称为“冠军”，而“亚军”是从与“冠军”比较失败的记录中找出，具体做法为：输出“冠军”后，将其叶子结点关键字改为“最大值”，然后从该叶子结点开始，和其左(或右)兄弟比较，修改从叶子结点到根结点路径上各结点的关键字，则根结点的关键字即为次小关键字。如此下去，可依次选出从小到大的全部关键字。其时间复杂度是O(nlogn)，空间复杂度是O(n)，由于使用空间较多，以及一些多余的比较，更主要由于堆排序的出现，使得很少再用树形排序。) 解析：
(3).树形选择排序与直接选择排序相比较，优缺点是什么?（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：树形选择排序与直接选择排序相比较，其优点是从求第2个元素开始，从n一i+1个元素中不必进行n—i次比较，比较次数远小于直接选择排序；其缺点是辅助储存空间大。) 解析：
(4).堆排序是如何改进树形排序方法的?优点是什么?【山东大学1999五(15分)】【山东工业大学1999五(15分)】（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：堆排序基本思想是：堆是n个元素的序列，先建堆，即先选得一个关键字最大或最小的记录，然后与序列中最后一个记录交换，之后将序列中前n一1记录重新调整为堆(调堆的过程称为 “筛选”)，再将堆顶记录和当前堆序列的最后一个记录交换，如此反复直至排序结束。优点是在时间性能与树形选择排序属同一量级的同时，堆排序只需要一个记录大小供交换用的辅助空间，调堆时子女只和双亲比较。避免了过多的辅助存储空间及和最大值的比较。) 解析：
已知关键字序列F={78，19，63，30，89，84，55，69，28，83}。要求：（分数：4.00）
(1).将该序列调整为“小顶”堆，并给出调整过程。请从时间和空间两方面对简单选择排序、树形选择排序和堆排序作一比较。（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：小顶堆：19，28，55，30，83，84，63，69，78，89简单选择排序、树形选择排序和堆排序都属于选择排序，都是不稳定排序。简单选择排序的基本思想是基于选择，开始有序序列长度为零，第i(1≤i 2)，平均时间复杂度是O(n)，空间复杂度是O(1)。树形排序和堆排序的论述见上面第43题。) 解析：
(2).若采用链式基数排序方法排序，请写出第一趟“分配”之后各队列的状态和第一趟“收集”之后的关键字序列。并请简要说出严蔚敏教材中所介绍的基数排序方法和其他排序方法有什么区别?【江苏大学2005三、3(15分)】（分数：2.00）
2
) __________________________________________________________________________________________ 正确答案：(正确答案：初始静态链表：78→19→63→30→89→84→55→69→28→83第一次分配后各队列状态(B是队列数组，f指向队头，e指向队尾)。 B[0]．f→30←B[0]．e; B[3]．f→63→83←B[3]．e； B[4]．f→84←B[4]．e B[5]．f→55←B[5]．e； B[8]．f→78→28←B[8]．e； B[9]．f→19→89→69←B[9]．e 第一次收集得到：p→30→63→83→84→55→78→28→19→89→69 基数排序过程如下：基数排序首先按关键字的组成设置若干队列。如果关键字由字母组成，则设置26个队列，若由数字组成，则设置10个队列。按最低位(LSD)优先，进行“分配”和“收集”。因为本例关键字由数字组成，首先按其“个位数”的取值“分配”到0～9共10个队列中，之后按队列0～9的顺序将它们“收集”在一起，收集时上一队列的队尾与下一队列的队头相连。然后“十位数”，“百位数”，……，重复上述操作，便得到关键字的有序序列。为减少所需辅助存储空间，采用静态链表作存储结构，即链式基数排序。) 解析：
1.若有N个元素已构成一个小根堆，那么如果增加一个元素为K n+1 请用文字简要说明你如何在log 2 n的时间内将其重新调整为一个堆?【中科院计算所1999三、2(5分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：K 1 到K n 是堆，在K n+1 加入后，将K 1 ..K n+1 调成堆。设c=n+1，f=[c／2]，若K f ≤K c ，则调整完成。否则，K f 与K c 交换；之后，c=f，f=[c／2]，继续比较，直到K f ≤K c ，或f=0，即为根结点时，调整结束。算法可以参照下面五、31等题。) 解析：
2.按照大顶堆积的定义，对序列(26，5，77，1，61，11，59，15，48，19)进行堆积排序，第二趟排序结束时序列的状态是__________。【北京航空航天大学2006一、10(1分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：大顶堆：77，61，59，48，19，11，26，15，1，5第2趟排序结束：61，48，59，15，19，11，26，5，1 [77]／／77已到位) 解析：
回答问题：（分数：4.00）
(1).设待排序的结点个数是n。试问堆排序算法在完成一次sift建堆，并且取走找到的最小关键字后，是否还需要对于n一1个关键字从头开始建堆?为什么?（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：不需要。因为建堆后R[1]到R[n]是堆，将R[1]与R[n]交换后，R[2]到R[n—1]仍是堆，故对R[1]到R[n一1]只需从R[1]往下筛选即可。) 解析：
(2).假定采用sift建堆算法。试问堆排序算法采用了怎样的节省存储空间的措施?堆排序完成后，heap中保存了关键字值的升序排列还是降序排列?【山东工业大学1996三、3(8分)】（分数：2.00） __________________________________________________________________________________________ 正确答案：(正确答案：堆是n个元素的序列，堆可以看作是n个结点的完全二叉树。而树形排序是n个元素作叶子结点的完全二叉树。因此堆占用的空间小。调堆时，利用堆本身就可以存放输出的有序数据，只需要一个供交换用的记录大小的辅助空间。排序后，heap数组中的关键字序列与堆是大堆还是小堆有关，若利用大堆，则为升序；若利用小堆则为降序。) 解析：
3.在多关键字排序时，LSD和MSD两种方法的特点是什么?【北京邮电大学2001三、3(5分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：最高位优先(MSD)法：先对最高位关键字K 进行排序，将序列分成若干子序列，每个子序列中的记录都具有相同的K 值，然后，分别就每个子序列对关键字K 进行排序，按K 值不同再分成若干更小的子序列，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序列。最低位优先(LSD)法：先对最低位关键字K 进行排序，然后对高一级关键字K 进行排序，依次重复，直至对最高位关键字K 排序后便成为一个有序序列。进行排序时，不必分成
i-2
0
i-1
0
1
1
0
子序列，对每个关键字都是整个序列参加排序，但对K (0≤i＜d一1)排序时，只能用稳定的排序方法。另一方面，按LSD进行排序时，可以不通过关键字比较实现排序，而是通过若干次“分配”和“收集”来实现排序。) 解析：
给出一组关键字T=(12，2，16，30，8，28，4，10，20，6，18)，写出用下列算法从小到大排序时第一趟结束时的序列：（分数：6.00）
(1).希尔排序(第一趟排序的增量为5)（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：一趟希尔排序：12，2，10，20，6，1 8，4，16，30，8，28(D=5)) 解析：
(2).快速排序(选第一个记录为枢轴(分隔))（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：一趟快速排序：6，2，10，4，8，12，28，30，20，16，18) 解析：
(3).链式基数排序(基数为10)【上海交通大学1999八(9分)】（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：解析：
给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：（分数：6.00）
(1).归并排序 每归并一次书写一个次序。（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：2路归并第一趟：1 8，29，25，47，12，58，10，5 1； 第二趟：18，25，29，47，10，12，51，58； 第三趟：10，12，18，25，29，47，51，58) 解析：
(2).快速排序 每划分一次书写一个次序。（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：快速排序第一趟：10，18，25，12，29，58，51，47； 第二趟：10，18，25，12，29，47，51，58； 第三趟：10，12，18，25，29，47，51，58) 解析：
(3).堆排序 先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。【南开大学1998八(12分)】（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：堆排序建大堆：58，47，51，29，18，12，25，10; ①51，47，25，29，18，12，10，58； ②47，29，25，10，18，12，51，58； ③29，18，25，10，12，47，51，58； ④25，18，12，10，29，47，51，58； ⑤18，10，12，25，29，47，51，58； ⑥12，10，18，25，29，47，51，58； ⑦10，12，18，25，29，47，51，58) 解析：
4.请写出应填入下列叙述中( )内的正确答案。【上海大学2002一(8分)】排序有各种方法，如插入排序、快速排序、堆排序等。设一数组中原有数据如下：15，13，20，18，12，60。下面是一组用不同排序方法进行一遍排序后的结果。()排序的结果为：12，13，15，18，20，60()排序的结果为：13，15，18，12，20，60()排序的结果为：13，15，20，18，12，60()排序的结果为：12，13，20，1 8，15，60 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：快速冒泡直接插入堆) 解析：
5.在排序二叉树上进行查找操作时，设对树中的每个结点查找概率相同。设由n个结点构成的序列生成的排序二叉树是“随机”的。试求出在成功查找的情况下，平均查找长度是多少?为了简单起见，最后得到的
) 1
递推式可不予求解。【上海交通大学2001八(8分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：假设在含有n(n≥1)个关键字的序列中，i个关键字小于或等于第一个关键字，n一i一1个关键字大于或等于第一个关键字，则由此构造的二叉排序树在各记录查找概率相同的前提下，其平均查找长度为P(n，i)=1/n[1+i*(P(i)+1)+(n—i一1)(P(n一i一1)+1)] (1)其中P(k)为含有k个结点的二叉排序树的平均查找长度，则P(i)+1为查找左子树每个关键字时比较次数的平均值，P(n一i一1)+1为查找右子树每个关键字时比较次数的平均值。又假设表中关键字的排列是“随机”的，即任一关键字在序列1到n各位置上的概率相同，则对(1)式从i等于0到n一1取平均值时iP(i)=0，又P(0)=0，P(1)=1，由归纳法可证明 P(n)≤1+4logn (n≥2)) 解析：
6.在使用K路平衡归并法，对外部文件进行排序时，K是否越大越好?为什么? 【上海交通大学2003十(10分)】
（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：否。 从归并次数的公式[log 2 m](n一1)看，比较次数与归并路数k无关，似乎k越大越好。但对于具体机器来说，内存是固定的，k越大，缓冲区越多，每个缓冲区就越小，甚至小于一次I／O读写空间。因而总的归并效率仍与尼有关。k应取折中值，并非越大越好。) 解析：
7.设某文件经内排序后得到100个初始归并段(初始顺串)，若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少?【山东大学1992一、4(3分)】【东南大学1999一、3(5分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：设归并路数为k，归并趟数为s，则s=[log k 100]，因[log k 100]=3，且k为整数，故k=5，即最少5路归并可以完成排序。) 解析：
8.证明：置换一选择排序法产生的初始归并段的长度至少为m(m是所用缓冲区的长度)。【西安电子科技大学1996二、5(5分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：证明：由置换选择排序思想，第一个归并段中第一个元素是缓冲区中最小的元素，以后每选一个元素都不应小于前一个选出的元素，故当产生第一个归并段时(即初始归并段)，缓冲区中m个元素中除最小元素之外，其他m一1个元素均大于第一个选出的元素，即当以后读入元素均小于输出元素时，初始归并段中也至少能有原有的m个元素。证毕。解析：
9.给定8个权值集合(2，5，3，10，4，7，9，18)，画出含有8个叶子结点的最佳三叉归并树，并计算出wpl为多少?【东北大学1996一、2(5分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：因(8—1)％(3—1)=1，故第一次归并时加一个“虚段”。WPL=5*3+(4+5+7+9+10)*2+18*1=103) 解析：
10.设有11个长度(即包含记录的个数)不同的初始归并段，它们所包含的记录个数分别为25，40，16，38，77，64，53，88，9，48，98。试根据它们做4路平衡归并，要求：(1)指出总的归并趟数；(3分)(2)构造最佳归并树；(8分)(3)根据最佳归并树计算每一趟及总的读记录数。(5分)【清华大学1997八(16分)】 （分数：2.00）
) 显然，式中两项对称，i=0
__________________________________________________________________________________________ 正确答案：(正确答案：因(11—1)％(4一1)=1，所以加“虚段”，第一次由两个段合并。 (1)三趟归并。 (2)最佳归并树如图。(3)设每次读写一个记录。 第一趟50次读写总的读写次数：1902
[(9+16)*3+(25+38+40)*2+(48+53+64+77)*2+(88+98)]*2 第二趟740次读写，第三趟1112次读写。 若“一趟”定义是所有记录参与归并，则归并趟数为：1902／1112=1．71趟。) 解析：
11.已知有3 1个长度不等的初始归并段，其中8段长度为2；8段长度为3；7段长度为5；5段长度为12；3段长度为20(单位均为物理块)，请为此设计一个最佳5路归并方案，并计算总的(归并所需的)读／写外存的次数。【清华大学1994四(10分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：加5一(31一1)％(5—1)一1=2个虚段。解析：
12.以归并算法为例，比较内部排序和外部排序的不同，说明外部排序如何提高操作效率。【华南师范大学1999四(10分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：内部排序中的归并排序是在内存中进行的归并排序，辅助空间为O(n)。外部归并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即归并的趟数。减少归并趟数就可以减少读写次数，提高效率。因为归并的趟数s=[log k m]，其中，m是归并段个数，k是归并路数。增大k和减少m都可减少归并趟数。应用中通过败者树进行多(k)路平衡归并，用置换一选择排序减少m，从而提高外部排序的效率。) 解析：
13.对输入文件(101，51，19，61，3，71，31，17，19，100，55，20，9，30，50，6，90)；当k=6时，使用置换一选择算法，写出建立的初始败者树及生成的初始归并段。【北方交通大学1999四(12分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：初始败者树解析：
设有N个记录的一个文件，经内部排序后得到650个初始归并段。（分数：4.00）
(1).试问在四台磁带机上分别用平衡归并和多步归并进行外部排序各需要多少趟归并? (6分)（分数：2.00） __________________________________________________________________________________________ 正确答案：(正确答案：4台磁带机：平衡归并只能用2路平衡归并，需归并[log 2 650]=10趟。多步归并进行3路归并，按3阶广义斐波那契序列。F 11 12=653，即应补3个虚段。进行：12—2=10趟归并。 t1=f11+f10+f9=149+81+44=274 t2=f10=149+81=230 t3=f11=149) 解析：
(2).给出多步归并排序前五趟归并的情况。(10分)【北方交通大学1997六(16分)】（分数：2.00） __________________________________________________________________________________________ 正确答案：(正确答案：多步归并排序前五趟归并的情况如下：解析：
14.给定输入文件：101，48，19，65，3，74，33，17，2l，20，99，53，21，并设记录缓冲区个数k=-4，写出基于败者树的外排序顺串生成算法runs输出的顺串。【东南大学1996一、6(6分)】 （分数：2.00）
) ) )
计算机专业基础综合数据结构(排序)历年真题试卷汇编9
