计算机专业基础综合数据结构（排序）历年真题试卷汇编

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）_正确答案：(正确答案：树形选择排序的基本思想：首先对n个待排序记录的

2、关键字进行两两比较，从中选出 n2个较小者再两两比较，直到选出关键字最小的记录为止，此为一趟排序。我们将一趟选出的关键字最小的记录称为“冠军”，而“亚军”是从与“冠军”比较失败的记录中找出，具体做法为：输出“冠军”后，将其叶子结点关键字改为“最大值”，然后从该叶子结点开始，和其左(或右)兄弟比较，修改从叶子结点到根结点路径上各结点的关键字，则根结点的关键字即为次小关键字。如此下去，可依次选出从小到大的全部关键字。其时间复杂度是O(nlogn)，空间复杂度是O(n)，由于使用空间较多，以及一些多余的比较，更主要由于堆排序的出现，使得很少再用树形排序。)解析：(3).树形选择排序与直接选择排序相比

3、较，优缺点是什么?（分数：2.00）_正确答案：(正确答案：树形选择排序与直接选择排序相比较，其优点是从求第2个元素开始，从n一i+1个元素中不必进行ni次比较，比较次数远小于直接选择排序；其缺点是辅助储存空间大。)解析：(4).堆排序是如何改进树形排序方法的?优点是什么?【山东大学1999五(15分)】【山东工业大学1999五(15分)】（分数：2.00）_正确答案：(正确答案：堆排序基本思想是：堆是n个元素的序列，先建堆，即先选得一个关键字最大或最小的记录，然后与序列中最后一个记录交换，之后将序列中前n一1记录重新调整为堆(调堆的过程称为 “筛选”)，再将堆顶记录和当前堆序列的最后一个记录

4、交换，如此反复直至排序结束。优点是在时间性能与树形选择排序属同一量级的同时，堆排序只需要一个记录大小供交换用的辅助空间，调堆时子女只和双亲比较。避免了过多的辅助存储空间及和最大值的比较。)解析：已知关键字序列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简单选择排序、树形选择排序和堆排序都属于选择排序，都是不稳定排序。简单选择排序的

5、基本思想是基于选择，开始有序序列长度为零，第i(1i 2)，平均时间复杂度是O(n2)，空间复杂度是O(1)。树形排序和堆排序的论述见上面第43题。)解析：(2).若采用链式基数排序方法排序，请写出第一趟“分配”之后各队列的状态和第一趟“收集”之后的关键字序列。并请简要说出严蔚敏教材中所介绍的基数排序方法和其他排序方法有什么区别?【江苏大学2005三、3(15分)】（分数：2.00）_正确答案：(正确答案：初始静态链表：78196330898455692883第一次分配后各队列状态(B是队列数组，f指向队头，e指向队尾)。 B0f30B0e; B3f6383B3e； B4f84B4e B5f5

6、5B5e； B8f7828B8e； B9f198969B9e 第一次收集得到：p30638384557828198969 基数排序过程如下：基数排序首先按关键字的组成设置若干队列。如果关键字由字母组成，则设置26个队列，若由数字组成，则设置10个队列。按最低位(LSD)优先，进行“分配”和“收集”。因为本例关键字由数字组成，首先按其“个位数”的取值“分配”到09共10个队列中，之后按队列09的顺序将它们“收集”在一起，收集时上一队列的队尾与下一队列的队头相连。然后“十位数”，“百位数”，重复上述操作，便得到关键字的有序序列。为减少所需辅助存储空间，采用静态链表作存储结构，即链式基数排序。)解析

7、：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=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)进

8、行堆积排序，第二趟排序结束时序列的状态是_。【北京航空航天大学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 7777已到位)解析：回答问题：（分数：4.00）(1).设待排序的结点个数是n。试问堆排序算法在完成一次sift建堆，并且取走找到的最小关键字后，是否还需要对于n一1个关键字从头开始建堆?为什么?（分数：2.00）_正确答案：(正确答案：不需要。因为建堆后R1到Rn是堆，将R1与Rn交换后，R2到Rn1仍是堆，故对R1到Rn一1只需从R1

9、往下筛选即可。)解析：(2).假定采用sift建堆算法。试问堆排序算法采用了怎样的节省存储空间的措施?堆排序完成后，heap中保存了关键字值的升序排列还是降序排列?【山东工业大学1996三、3(8分)】（分数：2.00）_正确答案：(正确答案：堆是n个元素的序列，堆可以看作是n个结点的完全二叉树。而树形排序是n个元素作叶子结点的完全二叉树。因此堆占用的空间小。调堆时，利用堆本身就可以存放输出的有序数据，只需要一个供交换用的记录大小的辅助空间。排序后，heap数组中的关键字序列与堆是大堆还是小堆有关，若利用大堆，则为升序；若利用小堆则为降序。)解析：3.在多关键字排序时，LSD和MSD两种方法的

10、特点是什么?【北京邮电大学2001三、3(5分)】（分数：2.00）_正确答案：(正确答案：最高位优先(MSD)法：先对最高位关键字K 0 进行排序，将序列分成若干子序列，每个子序列中的记录都具有相同的K 0 值，然后，分别就每个子序列对关键字K 1 进行排序，按K 1 值不同再分成若干更小的子序列，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序列。最低位优先(LSD)法：先对最低位关键字K i-1 进行排序，然后对高一级关键字K i-2 进行排序，依次重复，直至对最高位关键字K 0 排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是

11、整个序列参加排序，但对K 1 (0id一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）_正确答案：(正确答案：一趟快速排序

12、：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).快速

13、排序 每划分一次书写一个次序。（分数：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，4

14、7，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，1

15、2，60()排序的结果为：12，13，20，1 8，15，60（分数：2.00）_正确答案：(正确答案：快速冒泡直接插入堆)解析：5.在排序二叉树上进行查找操作时，设对树中的每个结点查找概率相同。设由n个结点构成的序列生成的排序二叉树是“随机”的。试求出在成功查找的情况下，平均查找长度是多少?为了简单起见，最后得到的递推式可不予求解。【上海交通大学2001八(8分)】（分数：2.00）_正确答案：(正确答案：假设在含有n(n1)个关键字的序列中，i个关键字小于或等于第一个关键字，n一i一1个关键字大于或等于第一个关键字，则由此构造的二叉排序树在各记录查找概率相同的前提下，其平均查找长度为P(n

16、，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取平均值显然，式中两项对称，i=0时iP(i)=0，又P(0)=0，P(1)=1，由归纳法可证明 P(n)1+4logn (n2)解析：6.在使用K路平衡归并法，对外部文件进行排序时，K是否越大越好?为什么? 【上海交通大学2003十

17、(10分)】（分数：2.00）_正确答案：(正确答案：否。 从归并次数的公式log 2 m(n一1)看，比较次数与归并路数k无关，似乎k越大越好。但对于具体机器来说，内存是固定的，k越大，缓冲区越多，每个缓冲区就越小，甚至小于一次IO读写空间。因而总的归并效率仍与尼有关。k应取折中值，并非越大越好。)解析：7.设某文件经内排序后得到100个初始归并段(初始顺串)，若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少?【山东大学1992一、4(3分)】【东南大学1999一、3(5分)】（分数：2.00）_正确答案：(正确答案：设归并路数为k，归并趟数为s，则s=log k 100

18、，因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

19、，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，98。试根据它们做4路平衡归并，要求：(1)指出总的归并趟数；(3分)(2)构造最佳归并树；(8分)(3)根据最佳归并树计算每一趟及总的读记录数。(5分)【清华大学199

20、7八(16分)】（分数：2.00）_正确答案：(正确答案：因(111)(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次读写。 若“一趟”定义是所有记录参与归并，则归并趟数为：19021112=171趟。)解析：11.已知有3 1个长度不等的初始归并段，其中8段长度为2；8段长度为3；7段长度为5；5段长度为12；3段长度为20(单位均为物理块)，请为此

21、设计一个最佳5路归并方案，并计算总的(归并所需的)读写外存的次数。【清华大学1994四(10分)】（分数：2.00）_正确答案：(正确答案：加5一(31一1)(51)一1=2个虚段。)解析：12.以归并算法为例，比较内部排序和外部排序的不同，说明外部排序如何提高操作效率。【华南师范大学1999四(10分)】（分数：2.00）_正确答案：(正确答案：内部排序中的归并排序是在内存中进行的归并排序，辅助空间为O(n)。外部归并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即归并的趟数。减少归并趟

22、数就可以减少读写次数，提高效率。因为归并的趟数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

23、).试问在四台磁带机上分别用平衡归并和多步归并进行外部排序各需要多少趟归并? (6分)（分数：2.00）_正确答案：(正确答案：4台磁带机：平衡归并只能用2路平衡归并，需归并log 2 650=10趟。多步归并进行3路归并，按3阶广义斐波那契序列。F 11 2)合并而不用2路合并?这种技术用于内排序有意义吗?为什么?【东南大学1995三(8分)】（分数：2.00）_正确答案：(正确答案：外排序用k路归并(k2)，因为k越小，归并趟数越多，读写外存次数越多，时间效率越低，故一般应大于最少的2路归并。若将k路归并的败者树思想单纯用于内排序，因其辅助空间大，不如堆排序好，故将其用于内排序效率并不高。

24、)解析：二、 设计题(总题数：5，分数：10.00)16.一最小最大堆(min max heap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小 (或最大)。如图所示为一最小最大堆。(1)画出在上图中插入关键字为5的结点后的最小最大堆。(2)画出在上图中插入关键字为80的结点后的最小最大堆。(3)编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关键字为整数。(4)用C实现上述算法。【浙江大学1996八(26分)】（分数：2.00）_正确答案：(正确答案：(1)加入5后 (2)加入80后 (3)从

25、插入位置进行调整，调整过程由下到上。首先根据元素个数求出插入元素所在层次 数，以确定其插入层是最大层还是最小层。若插入元素在最大层，则先比较插入元素是否比双亲小，如是，则先交换，之后，将小堆与祖先调堆，直到满足小堆定义或到达根结点；若插入元素不小于双亲，则调大堆，直到满足大堆定义。若插入结点在最小层，则先比较插入元素是否比双亲大，如是，则先交换，之后，将大堆与祖先调堆；若插入结点在最小层且小于双亲，则将小堆与祖先调堆，直到满足小堆定义或到达根结点。 (4)void MinMaxHeapIns(RecType R，int n) 假设R1n一1是最小最大堆，插入第n个元素，把R1n调成最小最大堆

26、j=n； R0=Rj； h=log 2 nj+1； 求高度 if(h2=0) 插入元素在偶数层，是最大层 i=n2； if(R0key 0&RjRi) 调小堆 (Ri=Rj；i=j ； j=i4； Ri=R0； else 插入元素大于双亲，调大堆 i=n；j=i4； while(j0&RjRikey) 插入元素大于双亲，先与双亲交换，然后调大堆 Rj=Ri； j=i4； while(j0&Rj0Rj)Ri) fRi=Rj；i=j；j=i4； Ri=R0； MinMaxHeapIns)解析：17.数据结构DEAP的定义如下：DEAP是一棵完全二叉树，它或者是一棵空树，或者满足下列特性：(1)树根

27、不包含元素。(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分)】（分数：2.00）_正确答案：(正确答案：根据定义，DEAP是

28、一棵完全二叉树，树根不包含元素，其左子树是一小堆(MINHEAP，下称小堆)，其右子树是一大堆(MAXHEAP，下称大堆)，故左右子树可分别用一维数组 r和r存储，用m和n分别表示当前两完全二叉树的结点数，左右子树的高度差至多为1，且左子树的高度始终大于等于右子树的高度。我们再分析插入情况：当均为空二叉树或满二叉树(m=2 h 1)时，应在小堆插入；小堆满(二叉树)后在大堆插入。即当mn且m2 k 一1且log 2 m-log 2 n1在小堆插入，否则在大堆插入。最后分析调堆情况：在小堆m处插入结点x后，若x的值不大于大堆的m2结点的值，则在小堆调堆；否则，结点x与大堆的m2结点交换，然后进行

29、大堆调堆。在大堆n处插入结点x后，若x不小于小堆的n结点，则在大堆调堆；否则，结点x与小堆的n结点交换，然后进行小堆调堆。(1)在DEAP中插入结点4后的结果如图。 4先插入大堆，因为4小于小堆中对应位置的19，所以和19交换。交换后只需调整小堆，从叶子到根结点。这时，大堆不需调整，因为插入小堆19时，要求19必须小于对应大堆双亲位置的25，否则，要进行交换。 Void InsertDEAP(int 1，r，m，n，x) 在DEAP中插入元素x1是小堆，r是大堆，m和n分别是两堆的元素个数，x是待插入元素 if(m=nmn&m2 h 一&Llog 2 mlog 2 n0&rf o&1fx) 1c=1f；c=f;f=c2; 1c=x； else)if else 在大堆插入x n+； n增1 if(x0&1fx) 1c=1f；c=f；f=c2；调小堆 1c=x； 结束调小堆 else 调大堆 c=n；f=c2； while(f0&rf)解析：18.叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。(179，208，93，306，55，859，984，9，2