[考研类试卷]计算机专业基础综合数据结构（排序）历年真题试卷汇编
10
一、综合题
0  解答问题
1  设某文件中待排序记录的排序码为72，73，71，23，94，1 6，05，68，试画图表示出树形选择排序(增序)过程的前三步。
2  试说明树形选择排序的基本思想。
3  树形选择排序与直接选择排序相比较，优缺点是什么?
4  堆排序是如何改进树形排序方法的?优点是什么?【山东大学1999五(15分)】【山东工业大学1999五(15分)】
4  已知关键字序列F={78，19，63，30，89，84，55，69，28，83}。要求：
5  将该序列调整为“小顶”堆，并给出调整过程。请从时间和空间两方面对简单选择排序、树形选择排序和
数据结构与算法考研真题堆排序作一比较。
6  若采用链式基数排序方法排序，请写出第一趟“分配”之后各队列的状态和第一趟“收集”之后的关键字序列。并请简要说出严蔚敏教材中所介绍的基数排序方法和其他排序方法有什么区别?【江苏大学2005三、3(15分)】
7 若有N个元素已构成一个小根堆，那么如果增加一个元素为K n+1请用文字简要说明你如何在log2n的时间内将其重新调整为一个堆?【中科院计算所1999三、2(5分)】
8  按照大顶堆积的定义，对序列(26，5，77，1，61，11，59，15，48，19)进行堆积排序，第二趟排序结束时序列的状态是__________。【北京航空航天大学2006一、10(1分)】
8  回答问题：
9  设待排序的结点个数是n。试问堆排序算法在完成一次sift建堆，并且取走到的最小关键字后，是否还需要对于n一1个关键字从头开始建堆?为什么?
10  假定采用sift建堆算法。试问堆排序算法采用了怎样的节省存储空间的措施?堆排序完成后，heap中保存了关键字值的升序排列还是降序排列?【山东工业大学1996三、3(8分)】
11  在多关键字排序时，LSD和MSD两种方法的特点是什么?【北京邮电大学2001
三、3(5分)】
11  给出一组关键字T=(12，2，16，30，8，28，4，10，20，6，18)，写出用下列算法从小到大排序时第一趟结束时的序列：
12  希尔排序(第一趟排序的增量为5)
13  快速排序(选第一个记录为枢轴(分隔))
14  链式基数排序(基数为10)【上海交通大学1999八(9分)】
14  给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：
15  归并排序每归并一次书写一个次序。
16  快速排序每划分一次书写一个次序。
17  堆排序先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。【南开大学1998八(12分)】
18  请写出应填入下列叙述中(    )内的正确答案。【上海大学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
19  在排序二叉树上进行查操作时，设对树中的每个结点查概率相同。设由n 个结点构成的序列生成的排序二叉树是“随机”的。试求出在成功查的情况下，平均查长度是多少?为了简单起见，最后得到的递推式可不予求解。【上海交通大学2001八(8分)】
20  在使用K路平衡归并法，对外部文件进行排序时，K是否越大越好?为什么?  【上海交通大学2003十(10分)】
21  设某文件经内排序后得到100个初始归并段(初始顺串)，若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少?【山东大学1992一、4(3分)】【东南大学1999一、3(5分)】
22  证明：置换一选择排序法产生的初始归并段的长度至少为m(m是所用缓冲区的长度)。【西安电子科技大学1996二、5(5分)】
23  给定8个权值集合(2，5，3，10，4，7，9，18)，画出含有8个叶子结点的最佳三叉归并树，并计算出wpl为多少?【东北大学1996一、2(5分)】
24  设有11个长度(即包含记录的个数)不同的初始归并段，它们所包含的记录个数分别为25，40，16，38，77，64，53，88，9，48，98。试根据它们做4路平衡归并，要求：
(1)指出总的归并趟数；(3分)
(2)构造最佳归并树；(8分)
(3)根据最佳归并树计算每一趟及总的读记录数。(5分)【清华大学1997八(16分)】
25  已知有3 1个长度不等的初始归并段，其中8段长度为2；8段长度为3；7段长度为5；5段长度为12；3段长度为20(单位均为物理块)，请为此设计一个最佳5路归并方案，并计算总的(归并所需的)读／写外存的次数。【清华大学1994四(10分)】
26  以归并算法为例，比较内部排序和外部排序的不同，说明外部排序如何提高操作效率。【华南师范大学1999四(10分)】
27  对输入文件(101，51，19，61，3，71，31，17，19，100，55，20，9，30，50，6，90)；当k=6时，使用置换一选择算法，写出建立的初始败者树及生成的初始归并段。【北方交通大学1999四(12分)】
27  设有N个记录的一个文件，经内部排序后得到650个初始归并段。
28  试问在四台磁带机上分别用平衡归并和多步归并进行外部排序各需要多少趟归并?  (6分)
29  给出多步归并排序前五趟归并的情况。(10分)【北方交通大学1997六(16分)】
30  给定输入文件：101，48，19，65，3，74，33，17，2l，20，99，53，21，并设记录缓冲区个数k=-4，写出基于败者树的外排序顺串生成算法runs输出的顺串。【东南大学1996一、6(6分)】
31  外排序中为何采用k路(k>2)合并而不用2路合并?这种技术用于内排序有意义吗?为什么?【东南大学1995三(8分)】
二、设计题
32 一最小最大堆(min max heap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小 (或最大)。如图所示为一最小最大堆。
(1)画出在上图中插入关键字为5的结点后的最小最大堆。(2)画出在上图中插入关键字为80的结点后的最小最大堆。(3)编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关键字为整数。(4)用C实现上述算法。【浙江大学1996八(26分)】
33 数据结构DEAP的定义如下：DEAP是一棵完全二叉树，它或者是一棵空树，或者满足下列特性：(1)树根不包含元素。(2)其左子树是一小堆(MIN HEAP)，其右子树是一大堆(MAX HEAP)。(3)若右子树非空，设i是左子树的任一结点，j是右
子树中与i相应的结点。若这样的j结点不存在，则取j为右子树中与i的父结点相对应的结点；结点i的关键字值总是小于或等于结点j的关键字值。一个DEAP的
例子如右图所示。与结点15相对应的结点为20，与结点19对应的结点为25。(1)给出在该DEAP中插入结点4后的结果。(2)写出在DEAP中插入新结点的算法。(3)用C或：Pascal语言编写实现上述算法的程序。【浙江大学1997 7(20分)】
34  叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。(179，208，93，306，55，859，984，9，271，33)【南京航空航天大学2000一】
35 实型二元序列α1，β1)，(α2，β2)，…，(αn，βn)具有二元有序性是指：
(1)a1≤a2≤…≤an；(2)若a i=a j，必有βi≤βj。例如(17，21)，(23，04)，(23，12)，(35，02)，(47，10)符合二元有序性。设计一个高效的二元序列排序算法，要求写出算法思想，数据类型说明，并分析二元序列排序算法的时间复杂度。【北京工业大学1996五(20分)】
36  设记录R[i]的关键字为R[i]．KEY(1≤i≤k)，树结点T[i](1≤i≤k-1)指向败者记录，T[0]为全胜记录下标。写一算法产生对应上述R[i](1≤f≤k)的败者树，要求除
R[1．．k]和T[0一K-1]以外，只用O(1)辅助空间。【东南大学1995九(15分)】