1、计算机专业基础综合数据结构（排序）历年真题试卷汇编 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 将该序列调整为“ 小顶”堆，并给出调整过程。请从时间和空间两方面对
2、简单选择排序、树形选择排序和堆排序作一比较。6 若采用链式基数排序方法排序，请写出第一趟“分配” 之后各队列的状态和第一趟“收集”之后的关键字序列。并请简要说出严蔚敏教材中所介绍的基数排序方法和其他排序方法有什么区别? 【 江苏大学 2005 三、3(15 分)】7 若有 N 个元素已构成一个小根堆，那么如果增加一个元素为 Kn+1 请用文字简要说明你如何在 log2n 的时间内将其重新调整为一个堆 ?【中科院计算所 1999 三、2(5分)】8 按照大顶堆积的定义，对序列(26，5，77，1，61，11，59，15，48，19)进行堆积排序，第二趟排序结束时序列的状态是_。【北京航空航天大学
3、 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)，写出用
4、下列算法从小到大排序时第一趟结束时的序列：12 希尔排序(第一趟排序的增量为 5)13 快速排序(选第一个记录为枢轴(分隔)14 链式基数排序(基数为 10)【上海交通大学 1999 八(9 分)】14 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：15 归并排序 每归并一次书写一个次序。16 快速排序 每划分一次书写一个次序。17 堆排序 先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。【南开大学 1998 八(12 分) 】18 请写出应填入下列叙述中( )内的正确答案。【上海大学 2002 一(8 分)】排序有各种
5、方法，如插入排序、快速排序、堆排序等。设一数组中原有数据如下：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，6019 在排序二叉树上进行查找操作时，设对树中的每个结点查找概率相同。设由 n个结点构成的序列生成的排序二叉树是“随机” 的。试求出在成功查找的情况下，平均查找长度是多少? 为了简单起见，最后得到的递推式可不予求解。【上海交通大学 2001 八(8
6、 分) 】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 个叶子结点的最佳三叉归并树，并
7、计算出 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
8、路归并方案，并计算总的(归并所需的)读写外存的次数。【清华大学 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 试问在四台磁带机上分别用平衡归并和多步归并进行外部排序各需要多少趟归
9、并? (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 路(k2)合并而不用 2 路合并?这种技术用于内排序有意义吗?为什么?【东南大学 1995 三(8 分)】二、设计题32 一最小最大堆(min max heap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中
10、的任一结点的关键字值总是在以它为根的子树中的所有元素中最小 (或最大)。如图所示为一最小最大堆。(1)画出在上图中插入关键字为 5 的结点后的最小最大堆。(2)画出在上图中插入关键字为 80 的结点后的最小最大堆。(3)编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关键字为整数。(4)用 C 实现上述算法。【浙江大学 1996 八(26 分)】33 数据结构 DEAP 的定义如下：DEAP 是一棵完全二叉树，它或者是一棵空树，或者满足下列特性：(1)树根不包含元素。(2) 其左子树是一小堆(MIN HEAP)，其右子树是一大堆(MAX HEAP)。(3)若右子树非空，设 i
11、是左子树的任一结点，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
12、，9，271，33)【南京航空航天大学 2000 一】35 实型二元序列 1，1)，(2 ，2)，(n，n)具有二元有序性是指：(1)a1a2an；(2)若 ai=aj，必有 ij。例如(17，21)，(23，04)，(23，12)，(35，02)，(47，10)符合二元有序性。设计一个高效的二元序列排序算法，要求写出算法思想，数据类型说明，并分析二元序列排序算法的时间复杂度。【北京工业大学 1996 五(20 分) 】36 设记录 Ri的关键字为 RiKEY(1ik)，树结点 Ti(1ik-1)指向败者记录，T0为全胜记录下标。写一算法产生对应上述 Ri(1fk)的败者树，要求除R1k 和
13、T0 一 K-1以外，只用 O(1)辅助空间。【东南大学 1995 九(15 分)】计算机专业基础综合数据结构（排序）历年真题试卷汇编 10 答案与解析一、综合题1 【正确答案】 2 【正确答案】 树形选择排序的基本思想：首先对 n 个待排序记录的关键字进行两两比较，从中选出 n2个较小者再两两比较，直到选出关键字最小的记录为止，此为一趟排序。我们将一趟选出的关键字最小的记录称为“冠军” ，而“亚军”是从与“冠军”比较失败的记录中找出，具体做法为：输出“冠军”后，将其叶子结点关键字改为“最大值 ”，然后从该叶子结点开始，和其左 (或右)兄弟比较，修改从叶子结点到根结点路径上各结点的关键字，则根
14、结点的关键字即为次小关键字。如此下去，可依次选出从小到大的全部关键字。其时间复杂度是 O(nlogn)，空间复杂度是O(n)，由于使用空间较多，以及一些多余的比较，更主要由于堆排序的出现，使得很少再用树形排序。3 【正确答案】 树形选择排序与直接选择排序相比较，其优点是从求第 2 个元素开始，从 n 一 i+1 个元素中不必进行 ni 次比较，比较次数远小于直接选择排序；其缺点是辅助储存空间大。4 【正确答案】 堆排序基本思想是：堆是 n 个元素的序列，先建堆，即先选得一个关键字最大或最小的记录，然后与序列中最后一个记录交换，之后将序列中前 n一 1 记录重新调整为堆(调堆的过程称为 “筛选”
15、) ，再将堆顶记录和当前堆序列的最后一个记录交换，如此反复直至排序结束。优点是在时间性能与树形选择排序属同一量级的同时，堆排序只需要一个记录大小供交换用的辅助空间，调堆时子女只和双亲比较。避免了过多的辅助存储空间及和最大值的比较。5 【正确答案】 小顶堆：19，28，55，30，83，84，63，69，78，89 简单选择排序、树形选择排序和堆排序都属于选择排序，都是不稳定排序。简单选择排序的基本思想是基于选择，开始有序序列长度为零，第 i(1i2)，平均时间复杂度是 O(n2)，空间复杂度是 O(1)。树形排序和堆排序的论述见上面第 43 题。6 【正确答案】 初始静态链表：78196330
16、898455692883 第一次分配后各队列状态(B 是队列数组，f 指向队头，e 指向队尾)。B0 f30B0e; B3f6383B3 e ； B4f84B4eB5 f55B5e ； B8f7828B8e； B9 f198969B9 e第一次收集得到：p30638384557828198969基数排序过程如下：基数排序首先按关键字的组成设置若干队列。如果关键字由字母组成，则设置 26 个队列，若由数字组成，则设置 10 个队列。按最低位(LSD)优先，进行“分配 ”和“收集”。因为本例关键字由数字组成，首先按其 “个位数”的取值“分配”到 09 共 10 个队列中，之后按队列 09 的顺序将
17、它们“收集”在一起，收集时上一队列的队尾与下一队列的队头相连。然后“十位数” ，“百位数”，重复上述操作，便得到关键字的有序序列。为减少所需辅助存储空间，采用静态链表作存储结构，即链式基数排序。7 【正确答案】 K 1 到 Kn 是堆，在 Kn+1 加入后，将 K1Kn+1 调成堆。设c=n+1，f=c2，若 KfKc，则调整完成。否则，K f 与 Kc 交换；之后，c=f，f=c 2，继续比较，直到 KfKc，或 f=0，即为根结点时，调整结束。算法可以参照下面五、31 等题。8 【正确答案】 大顶堆：77，61，59，48，19，11，26，15，1，5 第 2 趟排序结束：61，48，5
18、9，15，19，11，26，5，1 7777 已到位9 【正确答案】 不需要。因为建堆后 R1到 Rn是堆，将 R1与 Rn交换后，R2到 Rn1仍是堆，故对 R1到 Rn 一 1只需从 R1往下筛选即可。10 【正确答案】 堆是 n 个元素的序列，堆可以看作是 n 个结点的完全二叉树。而树形排序是 n 个元素作叶子结点的完全二叉树。因此堆占用的空间小。调堆时，利用堆本身就可以存放输出的有序数据，只需要一个供交换用的记录大小的辅助空间。排序后，heap 数组中的关键字序列与堆是大堆还是小堆有关，若利用大堆，则为升序；若利用小堆则为降序。11 【正确答案】 最高位优先(MSD)法：先对最高位关键
19、字 K0 进行排序，将序列分成若干子序列，每个子序列中的记录都具有相同的 K0 值，然后，分别就每个子序列对关键字 K1 进行排序，按 K1 值不同再分成若干更小的子序列，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序列。最低位优先(LSD)法：先对最低位关键字 Ki-1 进行排序，然后对高一级关键字Ki-2 进行排序，依次重复，直至对最高位关键字 K0 排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个序列参加排序，但对K1(0id 一 1)排序时，只能用稳定的排序方法。另一方面，按 LSD 进行排序时，可以不通过关键字比较实现
20、排序，而是通过若干次“分配” 和“收集”来实现排序。12 【正确答案】 一趟希尔排序：12，2，10，20，6，1 8，4，16，30，8，28(D=5)13 【正确答案】 一趟快速排序：6，2，10，4，8，12，28，30，20，16，1814 【正确答案】 15 【正确答案】 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，5816 【正确答案】 快速排序第一趟：10，18，25，12，29，58，51，47；第二趟：10，18，25，12，29，47，51，5
21、8；第三趟：10，12，18，25，29，47，51，5817 【正确答案】 堆排序建大堆：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，5818 【正确答案】 快速冒泡直接插入堆19 【正确答案】 假设在含有 n(n1)个关键字的序列中，
22、i 个关键字小于或等于第一个关键字，n 一 i 一 1 个关键字大于或等于第一个关键字，则由此构造的二叉排序树在各记录查找概率相同的前提下，其平均查找长度为 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 取平均值 显
23、然，式中两项对称，i=0 时 iP(i)=0，又 P(0)=0，P(1)=1，由归纳法可证明 P(n)1+4logn (n2)20 【正确答案】 否。 从归并次数的公式log 2m(n 一 1)看，比较次数与归并路数 k无关，似乎 k 越大越好。但对于具体机器来说，内存是固定的，k 越大，缓冲区越多，每个缓冲区就越小，甚至小于一次 IO 读写空间。因而总的归并效率仍与尼有关。k 应取折中值，并非越大越好。21 【正确答案】 设归并路数为 k，归并趟数为 s，则 s=logk100，因log k100=3，且 k 为整数，故 k=5，即最少 5 路归并可以完成排序。22 【正确答案】 证明：由置
24、换选择排序思想，第一个归并段中第一个元素是缓冲区中最小的元素，以后每选一个元素都不应小于前一个选出的元素，故当产生第一个归并段时(即初始归并段)，缓冲区中 m 个元素中除最小元素之外，其他 m 一 1个元素均大于第一个选出的元素，即当以后读入元素均小于输出元素时，初始归并段中也至少能有原有的 m 个元素。证毕。23 【正确答案】 因(81)(31)=1 ，故第一次归并时加一个“虚段”。WPL=5*3+(4+5+7+9+10)*2+18*1=10324 【正确答案】 因(111)(4 一 1)=1，所以加“虚段”，第一次由两个段合并。 (1)三趟归并。 (2) 最佳归并树如图。 (3)设每次读写
25、一个记录。第一趟 50 次读写总的读写次数：1902(9+16)*3+(25+38+40)*2+(48+53+64+77)*2+(88+98)*2 第二趟 740 次读写，第三趟 1112 次读写。若“一趟”定义是所有记录参与归并，则归并趟数为：19021112=171 趟。25 【正确答案】 加 5 一(31 一 1)(51) 一 1=2 个虚段。26 【正确答案】 内部排序中的归并排序是在内存中进行的归并排序，辅助空间为O(n)。外部归并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即
26、归并的趟数。减少归并趟数就可以减少读写次数，提高效率。因为归并的趟数 s=logkm，其中，m 是归并段个数，k 是归并路数。增大k 和减少 m 都可减少归并趟数。应用中通过败者树进行多 (k)路平衡归并，用置换一选择排序减少 m，从而提高外部排序的效率。27 【正确答案】 初始败者树28 【正确答案】 4 台磁带机：平衡归并只能用 2 路平衡归并，需归并log 2650=10趟。多步归并进行 3 路归并，按 3 阶广义斐波那契序列。F 1112=653，即应补 3 个虚段。进行：122=10 趟归并。 t 1=f11+f10+f9=149+81+44=274 t2=f10=149+81=23
27、0 t3=f11=14929 【正确答案】 多步归并排序前五趟归并的情况如下：30 【正确答案】 R 1：19，48，65，74，101 R 2：3，17，20，21，21，33，53，9931 【正确答案】 外排序用 k 路归并(k2)，因为 k 越小，归并趟数越多，读写外存次数越多，时间效率越低，故一般应大于最少的 2 路归并。若将 k 路归并的败者树思想单纯用于内排序，因其辅助空间大，不如堆排序好，故将其用于内排序效率并不高。二、设计题32 【正确答案】 (1)加入 5 后 (2)加入 80 后(3)从插入位置进行调整，调整过程由下到上。首先根据元素个数求出插入元素所在层次 数，以确定其
28、插入层是最大层还是最小层。若插入元素在最大层，则先比较插入元素是否比双亲小，如是，则先交换，之后，将小堆与祖先调堆，直到满足小堆定义或到达根结点；若插入元素不小于双亲，则调大堆，直到满足大堆定义。若插入结点在最小层，则先比较插入元素是否比双亲大，如是，则先交换，之后，将大堆与祖先调堆；若插入结点在最小层且小于双亲，则将小堆与祖先调堆，直到满足小堆定义或到达根结点。(4)void MinMaxHeapIns(RecType R，int n) 假设 R1n 一 1是最小最大堆，插入第 n 个元素，把 R1n调成最小最大堆 j=n； R0=Rj； h=log 2nj+1； 求高度 if(h 2=0)
29、 插入元素在偶数层，是最大层 i=n2； if(R0key0f=c 2; 1c=x； else)if else 在大堆插入 x n+； n 增 1 if(x0&1fx) 1c=1f；c=f；f=c2；调小堆 1c=x； 结束调小堆 else 调大堆 c=n；f=c 2； while(f0&rf34 【正确答案】 在计算机上实现基数排序时，为减少所需辅助存储空间，应采用静态链表作存储结构，即链式基数排序，具体做法如下。(1)待排序记录以指针相链接，构成一个链表。(2)“分配”时，按当前“关键字位”的取值，将记录分配到不同的 “链队列”中，每个队列中记录的“ 关键字位” 相同。本题是整数序列的基数
30、排序，所以设置 0-9 共 10 个队列。(3)“收集”时，按当前关键字位取值从小到大将各队列首尾相链接成一个链表。(4)对每个关键字位均重复(2) 和(3)两步，直至排序结束。核心语句段如下：for(i=1；i=0 一一一) 进行 d 趟排序for(i=0；i0)if(RskeyR ITtkey) sTt ； s 指示新的胜者t=t2； whileT0=s； Adjustvoid CreateL08erTree(int T) R0到 Rk 一 1为完全二叉树 T 的叶子结点，本算法建立败者树Rkkey=MINKEY； MINKEY 是与题中要求的关键字类型相同的机器最小数for(i=0；i=0 ； i-) Adjust(T，i) ； createL0serTree
