数据结构教程李春葆课后答案第11章外排序

第11章外排序教材中练习题及参考答案1.外排序中两个相对独立的阶段是什么？答：外排序中两个相对独立的阶段是产生初始归并段和多路归并排序。2.给出一组关键字T=（12，2，16，30，8，28，4，10，20，6，18），设内存工作区可容纳4个记录，给出用置换-选择排序算法得到的全部初始归并段。答：置换-选择排序算法的执行过程如表11.1所示。共产生两个初始归并段，归并段1为（2，8，12，16，28，30），归并段2为（4，6，10，18，20）。表11.1初始归并段的生成过程读入记录内存工作区状态Rmin输出之后的初始归并段状态12，2，16，3012，2，16，302(i=1)归并段1:{2}812，8，16，308(i=1)归并段1:{2，8}2812，28，16，3012(i=1)归并段1:{2，8，12}44，28，16，3016(i=1)归并段1:{2，8，12，16}104，28，10，3028(i=1)归并段1:{2，8，12，16，28}204，20，10，3030(i=1)归并段1:{2，8，12，16，28，30}64，20，10，64(430，开始新归并段i=2)归并段1:{2，8，12，16，28，30}归并段2:{4}1818，20，10，66(i=2)归并段1:{2，8，12，16，28，30}归并段2:{4，6}18，20，10，10(i=2)归并段1:{2，8，12，16，28，30}归并段2:{4，6，10}18，20，，18(i=2)归并段1:{2，8，12，16，28，30}归并段2:{4，6，10，18}，20，，20(i=2)归并段1:{2，8，12，16，28，30}归并段2:{4，6，10，18，20}3.设输入的关键字满足k1k2…kn，缓冲区大小为m，用置换-选择排序方法可产生多少个初始归并段？答：可产生n/m个初始归并段。设记录Ri的关键字为ki（1≤i≤n），先读入m个记录R1、R2、…、Rm，采用败者树选择最小记录Rm，将其输出到到归并段1，Rmin=km，在该位置上读入Rm+1，采用败者树选择最小记录Rm-1，将其输出到到归并段1，Rmin=km-1，在该位2数据结构教程学习教程置上读入Rm+2，采用败者树选择最小记录Rm－2，将其输出到到归并段1，Rmin=km-2，…，以此类推，产生归并段1：（Rm，Rm-1，…，R1）。同样产生其他归并段（R2m，R2m-1，…，Rm+1），（R3m，R3m-1，…，R2m+1），…，一共有n/m个初始归并段。4.什么是多路平衡归并，多路平衡归并的目的是什么？答：归并过程可以用一棵归并树来表示。多路平衡归并对应的归并树中，每个结点都是平衡的，即每个结点的所有子树的高度相差不超过1。k路平衡归并的过程是：第一趟归并将m个初始归并段归并为m/k个归并段，以后每一趟归并将l个初始归并段归并为l/k个归并段，直到最后形成一个大的归并段为止。m个归并段采用k路平衡归并，总的归并趟数s=logkm。其趟数是所有归并方案中最少的，所以多路平衡归并的目的是减少归并趟数。5.什么是败者树？其主要作用是什么？用于k路归并的败者树中共有多少个结点（不计冠军结点）？答：败者树是一棵有k个叶子结点的完全二叉树，从叶子结点开始，两个结点进行比较，将它们中的败者（较大者）上升到双亲结点，胜者（较小者）参加更高一层的比较。败者树的主要作用是从k个记录中选取关键字最小的记录。败者树中有k个叶子结点，且没有度为1的结点，即n0=k，n1=0，n2=n0-1=k-1，所以n=n0+n1+n2=2k-1。6.如果某个文件经内排序得到80个初始归并段，试问：（1）若使用多路平衡归并执行3趟完成排序，那么应取的归并路数至少应为多少？（2）如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个，则按多路平衡归并至少需要几趟可以完成排序？如果限定这个趟数，可取的最低路数是多少？答：（1）设归并路数为k，初始归并段个数m=80，根据多路平衡归并趟数计算公式s=logkm=logk80=3，则k3≥80，即k≥5。也就是说，可取的最低路数是5。（2）设多路平衡归并的归并路数为k，需要k个输入缓冲区和1个输出缓冲区。l个缓冲区对应一个文件，有k+1=15，因此k=14，可做14路归并。由s=logkm=log1480=2。即至少需2趟归并可完成排序。若限定这个趟数，由s=logk80=2，有80≥k2，可取的最低路数为9。即要在2趟内完成排序，进行9路排序即可。7.若采用置换选择排序算法得到8个初始归并段，它们的记录个数分别为37、34、300、41、70、120、35和43。画出这些磁盘文件进行归并的4阶最佳归并树，计算出总的读写记录数。答：k=4，m=8，k-(m-1)mod(k-1)-1=2，则设两个虚段。4阶最佳归并树如图11.2所示。第11章外排序3图11.2一棵4阶最佳归并树第1趟读记录数：34+35=69。第2趟读记录数：69+37+41+43=190。第3趟读记录数：190+70+120+300=680。总的读记录数=69+190+680=939，总的读写记录数=939×2=1878。69190680归并段50T10T134T135T137T141T143T170T1120T1300T1