1、计算机专业基础综合数据结构（排序）历年真题试卷汇编 9 及答案解析(总分：72.00，做题时间：90 分钟)一、综合题(总题数：21，分数：62.00)解答问题（分数：8.00）(1).设某文件中待排序记录的排序码为 72，73，71，23，94，1 6，05，68，试画图表示出树形选择排序(增序)过程的前三步。（分数：2.00）_(2).试说明树形选择排序的基本思想。（分数：2.00）_(3).树形选择排序与直接选择排序相比较，优缺点是什么?（分数：2.00）_(4).堆排序是如何改进树形排序方法的?优点是什么?【山东大学 1999 五(15 分)】【山东工业大学 1999五(15 分)】（
2、分数：2.00）_已知关键字序列 F=78，19，63，30，89，84，55，69，28，83。要求：（分数：4.00）(1).将该序列调整为“小顶”堆，并给出调整过程。请从时间和空间两方面对简单选择排序、树形选择排序和堆排序作一比较。（分数：2.00）_(2).若采用链式基数排序方法排序，请写出第一趟“分配”之后各队列的状态和第一趟“收集”之后的关键字序列。并请简要说出严蔚敏教材中所介绍的基数排序方法和其他排序方法有什么区别?【江苏大学2005 三、3(15 分)】（分数：2.00）_1.若有 N 个元素已构成一个小根堆，那么如果增加一个元素为 K n+1 请用文字简要说明你如何在 log
3、 2 n的时间内将其重新调整为一个堆?【中科院计算所 1999 三、2(5 分)】（分数：2.00）_2.按照大顶堆积的定义，对序列(26，5，77，1，61，11，59，15，48，19)进行堆积排序，第二趟排序结束时序列的状态是_。【北京航空航天大学 2006 一、10(1 分)】（分数：2.00）_回答问题：（分数：4.00）(1).设待排序的结点个数是 n。试问堆排序算法在完成一次 sift 建堆，并且取走找到的最小关键字后，是否还需要对于 n 一 1 个关键字从头开始建堆?为什么?（分数：2.00）_(2).假定采用 sift 建堆算法。试问堆排序算法采用了怎样的节省存储空间的措施?
4、堆排序完成后，heap中保存了关键字值的升序排列还是降序排列?【山东工业大学 1996 三、3(8 分)】（分数：2.00）_3.在多关键字排序时，LSD 和 MSD 两种方法的特点是什么?【北京邮电大学 2001 三、3(5 分)】（分数：2.00）_给出一组关键字 T=(12，2，16，30，8，28，4，10，20，6，18)，写出用下列算法从小到大排序时第一趟结束时的序列：（分数：6.00）(1).希尔排序(第一趟排序的增量为 5)（分数：2.00）_(2).快速排序(选第一个记录为枢轴(分隔)（分数：2.00）_(3).链式基数排序(基数为 10)【上海交通大学 1999 八(9 分
5、)】（分数：2.00）_给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：（分数：6.00）(1).归并排序 每归并一次书写一个次序。（分数：2.00）_(2).快速排序 每划分一次书写一个次序。（分数：2.00）_(3).堆排序 先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。【南开大学 1998 八(12 分)】（分数：2.00）_4.请写出应填入下列叙述中( )内的正确答案。【上海大学 2002 一(8 分)】排序有各种方法，如插入排序、快速排序、堆排序等。设一数组中原有数据如下：15，13，20，18，12，60。下
6、面是一组用不同排序方法进行一遍排序后的结果。()排序的结果为：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 个结点构成的序列生成的排序二叉树是“随机”的。试求出在成功查找的情况下，平均查找长度是多少?为了简单起见，最后得到的递推式可不予求解。【上海交通大学 2001 八(8 分)】（分数：2.00）_6.在使用 K 路平衡归并法，对外部文件进行排序时，K
7、是否越大越好?为什么? 【上海交通大学 2003 十(10 分)】（分数：2.00）_7.设某文件经内排序后得到 100 个初始归并段(初始顺串)，若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少?【山东大学 1992 一、4(3 分)】【东南大学 1999 一、3(5 分)】（分数：2.00）_8.证明：置换一选择排序法产生的初始归并段的长度至少为 m(m 是所用缓冲区的长度)。【西安电子科技大学 1996 二、5(5 分)】（分数：2.00）_9.给定 8 个权值集合(2，5，3，10，4，7，9，18)，画出含有 8 个叶子结点的最佳三叉归并树，并计算出wpl 为多少
8、?【东北大学 1996 一、2(5 分)】（分数：2.00）_10.设有 11 个长度(即包含记录的个数)不同的初始归并段，它们所包含的记录个数分别为25，40，16，38，77，64，53，88，9，48，98。试根据它们做 4 路平衡归并，要求：(1)指出总的归并趟数；(3 分)(2)构造最佳归并树；(8 分)(3)根据最佳归并树计算每一趟及总的读记录数。(5 分)【清华大学 1997 八(16 分)】（分数：2.00）_11.已知有 3 1 个长度不等的初始归并段，其中 8 段长度为 2；8 段长度为 3；7 段长度为 5；5 段长度为12；3 段长度为 20(单位均为物理块)，请为此设
9、计一个最佳 5 路归并方案，并计算总的(归并所需的)读写外存的次数。【清华大学 1994 四(10 分)】（分数：2.00）_12.以归并算法为例，比较内部排序和外部排序的不同，说明外部排序如何提高操作效率。【华南师范大学 1999 四(10 分)】（分数：2.00）_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 个初始归并段。（分
10、数：4.00）(1).试问在四台磁带机上分别用平衡归并和多步归并进行外部排序各需要多少趟归并? (6 分)（分数：2.00）_(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）_15.外排序中为何采用 k 路(k2)合并而不用 2 路合并?这种技术用于内排序有意义吗?为什么?【东南大学19
11、95 三(8 分)】（分数：2.00）_二、设计题(总题数：5，分数：10.00)16.一最小最大堆(min max heap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小 (或最大)。如图所示为一最小最大堆。 （分数：2.00）_17.数据结构 DEAP 的定义如下：DEAP 是一棵完全二叉树，它或者是一棵空树，或者满足下列特性：(1)树根不包含元素。(2)其左子树是一小堆(MIN HEAP)，其右子树是一大堆(MAX HEAP)。(3)若右子树非空，设i 是左子树的任一结点，j 是右子树中与 i 相应的结
12、点。若这样的 j 结点不存在，则取 j 为右子树中与 i的父结点相对应的结点；结点 i 的关键字值总是小于或等于结点 j 的关键字值。一个 DEAP 的例子如右图所示。 （分数：2.00）_18.叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。(179，208，93，306，55，859，984，9，271，33)【南京航空航天大学 2000 一】（分数：2.00）_19.实型二元序列 1，1)，(2，2)，(n，n)具有二元有序性是指：(1)a1a2an；(2)若 a i =a j ，必有 i j 。例如(17，21)，(23，04)，(23，12)，(35，02)，(47，10)
13、符合二元有序性。设计一个高效的二元序列排序算法，要求写出算法思想，数据类型说明，并分析二元序列排序算法的时间复杂度。【北京工业大学 1996 五(20 分)】（分数：2.00）_20.设记录 Ri的关键字为 RiKEY(1ik)，树结点 Ti(1ik-1)指向败者记录，T0为全胜记录下标。写一算法产生对应上述 Ri(1fk)的败者树，要求除 R1k和 T0 一 K-1以外，只用O(1)辅助空间。【东南大学 1995 九(15 分)】（分数：2.00）_计算机专业基础综合数据结构（排序）历年真题试卷汇编 9 答案解析(总分：72.00，做题时间：90 分钟)一、综合题(总题数：21，分数：62.
14、00)解答问题（分数：8.00）(1).设某文件中待排序记录的排序码为 72，73，71，23，94，1 6，05，68，试画图表示出树形选择排序(增序)过程的前三步。（分数：2.00）_正确答案：(正确答案： )解析：(2).试说明树形选择排序的基本思想。（分数：2.00）_正确答案：(正确答案：树形选择排序的基本思想：首先对 n 个待排序记录的关键字进行两两比较，从中选出 n2个较小者再两两比较，直到选出关键字最小的记录为止，此为一趟排序。我们将一趟选出的关键字最小的记录称为“冠军”，而“亚军”是从与“冠军”比较失败的记录中找出，具体做法为：输出“冠军”后，将其叶子结点关键字改为“最大值”
15、，然后从该叶子结点开始，和其左(或右)兄弟比较，修改从叶子结点到根结点路径上各结点的关键字，则根结点的关键字即为次小关键字。如此下去，可依次选出从小到大的全部关键字。其时间复杂度是 O(nlogn)，空间复杂度是 O(n)，由于使用空间较多，以及一些多余的比较，更主要由于堆排序的出现，使得很少再用树形排序。)解析：(3).树形选择排序与直接选择排序相比较，优缺点是什么?（分数：2.00）_正确答案：(正确答案：树形选择排序与直接选择排序相比较，其优点是从求第 2 个元素开始，从 n 一i+1 个元素中不必进行 ni 次比较，比较次数远小于直接选择排序；其缺点是辅助储存空间大。)解析：(4).堆
16、排序是如何改进树形排序方法的?优点是什么?【山东大学 1999 五(15 分)】【山东工业大学 1999五(15 分)】（分数：2.00）_正确答案：(正确答案：堆排序基本思想是：堆是 n 个元素的序列，先建堆，即先选得一个关键字最大或最小的记录，然后与序列中最后一个记录交换，之后将序列中前 n 一 1 记录重新调整为堆(调堆的过程称为 “筛选”)，再将堆顶记录和当前堆序列的最后一个记录交换，如此反复直至排序结束。优点是在时间性能与树形选择排序属同一量级的同时，堆排序只需要一个记录大小供交换用的辅助空间，调堆时子女只和双亲比较。避免了过多的辅助存储空间及和最大值的比较。)解析：已知关键字序列
17、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(1i 2)，平均时间复杂度是 O(n2)，空间复杂度是 O(1)。树形排序和堆排序的论述见上面第43 题。)解析：(2).若采用链式基数排序方法排序，请写出
18、第一趟“分配”之后各队列的状态和第一趟“收集”之后的关键字序列。并请简要说出严蔚敏教材中所介绍的基数排序方法和其他排序方法有什么区别?【江苏大学2005 三、3(15 分)】（分数：2.00）_正确答案：(正确答案：初始静态链表：78196330898455692883 第一次分配后各队列状态(B 是队列数组，f 指向队头，e 指向队尾)。 B0f30B0e; B3f6383B3e； B4f84B4e B5f55B5e； B8f7828B8e； B9f198969B9e 第一次收集得到：p30638384557828198969 基数排序过程如下：基数排序首先按关键字的组成设置若干队列。如果关
19、键字由字母组成，则设置 26 个队列，若由数字组成，则设置 10 个队列。按最低位(LSD)优先，进行“分配”和“收集”。因为本例关键字由数字组成，首先按其“个位数”的取值“分配”到 09 共 10 个队列中，之后按队列 09 的顺序将它们“收集”在一起，收集时上一队列的队尾与下一队列的队头相连。然后“十位数”，“百位数”，重复上述操作，便得到关键字的有序序列。为减少所需辅助存储空间，采用静态链表作存储结构，即链式基数排序。)解析：1.若有 N 个元素已构成一个小根堆，那么如果增加一个元素为 K n+1 请用文字简要说明你如何在 log 2 n的时间内将其重新调整为一个堆?【中科院计算所 19
20、99 三、2(5 分)】（分数：2.00）_正确答案：(正确答案：K 1 到 K n 是堆，在 K n+1 加入后，将 K 1 K n+1 调成堆。设 c=n+1，f=c2，若 K f K c ，则调整完成。否则，K f 与 K c 交换；之后，c=f，f=c2，继续比较，直到 K f K c ，或 f=0，即为根结点时，调整结束。算法可以参照下面五、31 等题。)解析：2.按照大顶堆积的定义，对序列(26，5，77，1，61，11，59，15，48，19)进行堆积排序，第二趟排序结束时序列的状态是_。【北京航空航天大学 2006 一、10(1 分)】（分数：2.00）_正确答案：(正确答案：
21、大顶堆：77，61，59，48，19，11，26，15，1，5 第 2 趟排序结束：61，48，59，15，19，11，26，5，1 7777 已到位)解析：回答问题：（分数：4.00）(1).设待排序的结点个数是 n。试问堆排序算法在完成一次 sift 建堆，并且取走找到的最小关键字后，是否还需要对于 n 一 1 个关键字从头开始建堆?为什么?（分数：2.00）_正确答案：(正确答案：不需要。因为建堆后 R1到 Rn是堆，将 R1与 Rn交换后，R2到 Rn1仍是堆，故对 R1到 Rn 一 1只需从 R1往下筛选即可。)解析：(2).假定采用 sift 建堆算法。试问堆排序算法采用了怎样的节
22、省存储空间的措施?堆排序完成后，heap中保存了关键字值的升序排列还是降序排列?【山东工业大学 1996 三、3(8 分)】（分数：2.00）_正确答案：(正确答案：堆是 n 个元素的序列，堆可以看作是 n 个结点的完全二叉树。而树形排序是 n 个元素作叶子结点的完全二叉树。因此堆占用的空间小。调堆时，利用堆本身就可以存放输出的有序数据，只需要一个供交换用的记录大小的辅助空间。排序后，heap 数组中的关键字序列与堆是大堆还是小堆有关，若利用大堆，则为升序；若利用小堆则为降序。)解析：3.在多关键字排序时，LSD 和 MSD 两种方法的特点是什么?【北京邮电大学 2001 三、3(5 分)】（
23、分数：2.00）_正确答案：(正确答案：最高位优先(MSD)法：先对最高位关键字 K 0 进行排序，将序列分成若干子序列，每个子序列中的记录都具有相同的 K 0 值，然后，分别就每个子序列对关键字 K 1 进行排序，按 K 1 值不同再分成若干更小的子序列，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序列。最低位优先(LSD)法：先对最低位关键字 K i-1 进行排序，然后对高一级关键字 K i-2 进行排序，依次重复，直至对最高位关键字 K 0 排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个序列参加排序，但对 K 1 (0i
24、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，
25、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).快速排序 每划分
26、一次书写一个次序。（分数：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，5
27、1，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，1
28、2，60()排序的结果为：12，13，20，1 8，15，60（分数：2.00）_正确答案：(正确答案：快速冒泡直接插入堆)解析：5.在排序二叉树上进行查找操作时，设对树中的每个结点查找概率相同。设由 n 个结点构成的序列生成的排序二叉树是“随机”的。试求出在成功查找的情况下，平均查找长度是多少?为了简单起见，最后得到的递推式可不予求解。【上海交通大学 2001 八(8 分)】（分数：2.00）_正确答案：(正确答案：假设在含有 n(n1)个关键字的序列中，i 个关键字小于或等于第一个关键字，n一 i 一 1 个关键字大于或等于第一个关键字，则由此构造的二叉排序树在各记录查找概率相同的前提下，
29、其平均查找长度为 P(n，i)=1/n1+i*(P(i)+1)+(ni 一 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 取平均值 )解析：6.在使用 K 路平衡归并法，对外部文件进行排序时，K 是否越大越好?为什么? 【上海交通大学 2003 十(10 分)】（分数：2.00
30、）_正确答案：(正确答案：否。 从归并次数的公式log 2 m(n 一 1)看，比较次数与归并路数 k 无关，似乎k 越大越好。但对于具体机器来说，内存是固定的，k 越大，缓冲区越多，每个缓冲区就越小，甚至小于一次 IO 读写空间。因而总的归并效率仍与尼有关。k 应取折中值，并非越大越好。)解析：7.设某文件经内排序后得到 100 个初始归并段(初始顺串)，若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少?【山东大学 1992 一、4(3 分)】【东南大学 1999 一、3(5 分)】（分数：2.00）_正确答案：(正确答案：设归并路数为 k，归并趟数为 s，则 s=log
31、 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）_正确答案：(正确答案：因(81)(31)=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
