1单选(2分)?外排序和内排序的主要区别是（ ）。
A.内排序所需内存小，而外排序所需内存大
B.内排序不涉及内、外存数据交换，而外排序涉及内、外存数据交换
C.内排序的数据量小，而外排序的数据量大
D.内排序速度快，而外排序速度慢
正确答案：B
课本考据：
1、在排序过程中，若整个表都放在内存中处理，排序时不涉及数据的内、外存交换，则称为内排序；
2、在排序过程中，若要进行数据的内、外存交换，则称为外排序。
2单选(2分)?以下关于外排序的叙述中正确的是（ ）。
A.外排序把外存文件调入内存，再利用内排序方法进行排序，所以外排序所花时间完全由采用的内排序确定
B.外排序所花时间=内排序时间+外存数据读写时间+内部归并所花时间
C.外排序完全可以由内排序来替代
D.外排序并不涉及文件的读写操作
正确答案：B
解析： B、外排序过程主要分为两个阶段：生成初始归并段和对初始归并段进行归并，这两个步骤中都涉及文件的读写操作。
课本考据：外排序的基本方法是归并排序法，它分为两个步骤：
1、生成若干初始归并段（顺串）：将一个文件（含待排序的数据）中的数据分段读入内存中，在内存中对其进行内排序，并将经过排序的数据段（有序段）写到多个外存文件上。
2、多路并归：对这些初始归并段进行多遍归并，使得有序的归并段逐渐扩大，最后在外存上形成整个文件的单一归并段，完成这个文件的外排序。
3单选(2分)?多路平衡归并的目的是（ ）。?
A.以上都对
B.便于实现败者树
C.减少初始归并段的个数
D.减少归并趟数
正确答案：D
解析： D、多路平衡归并的目的是减少归并趟数，因为m个初始归并段采用k路平衡归并时，所需趟数s=logkm（取上界），如果不采用平衡归并，其趟数会大于s。
4单选(2分)?m个初始归并进行k路平衡归并时，所需趟数是（ ）。
A.[logmk]
B.[logkm]+1
C.[logkm]
D.[logk(m+1)]
正确答案：C
课本考据：当采用k路平衡归并时，相应的归并树有[logkm]+1层，要对数据进行s=[logkm]遍扫描，显然k越大，磁盘读写次数越少。
5单选(2分)?在由k路归并构建的的败者树中选取一个最小的关键字记录，则所需时间为（ ）（用“O”表示）。
A.O(log2k)
B.O(k)
C.O(1)
D.以上都不对
正确答案：A
课本考据：若初始归并段为m个，利用败者树在k个记录中选择最小者只需要进行[log2k]次关键字比较，则s=[logkm]趟归并。
6单选(2分)?m个初始归并段采用k路平衡归并时，构建的败者树中共有（ ）个节点（不计冠军节点）。
A.2m-1
B.2k
C.2k-1
D.2m
正确答案：C
课本考据：k路平衡归并败者树是一颗含有k个叶子结点，且没有单分支结点（这是构建k路平衡归并败者树的约定）的完全二叉树,即n1=0.有n2=n0-1=k-1,n=n0+n1+n2=2k-1,则h=[log2(n+1)]=[log2(2k)]=[log2k]+1。
7单选(2分)?采用败者树进行k路平衡归并的外排序算法中，总的关键字比较次数与k（ ）。
A.以上都不对
B.无关
C.成反比
D.成正比
正确答案：B
解析： B、采用败者树进行k路平衡归并的外排序算法中，总的关键字比较次数=(u-1)*log2m，其中u为归并的记录个数，m是初始归并段的个数，从而看出与k无关。
8单选(2分)?一个无序文件中的n个记录采用置换-选择算法产生m个有序段，则m和n的关系是（ ）。
A.m与n成反比
B.以上都不对
C.m=log2n
D.m与n成正比
正确答案：B
解析： B、如w=1时，记录序列（1，2，3，4，5）产生一个有序段，而（5，4，3，2，1）产生5个有序段，所以一般来讲，m与数据序列、内存工作区可容纳的记录个数w和n都有关，但并不是A、B、C选项所指的直接关系。
9单选(2分)?对于100个长度不等的初始归并段，构建5路最佳归并树时，需要增加（ ）个虚段。
A.0
B.1
C.2
D.3
正确答案：B
解析： B、u=(m-1)%(k-1)=3，需要增加k-1-u=1个虚段。
10单选(2分)?由m个初始归并段构建的k阶最佳归并树中，度为k的节点个数是（ ）。
A.无法确定
B.(m-1)/(k-1)
C.(m-1)/k
D.m/k
正确答案：B
解析： B、设树中节点个数为n，n0=m，n-1=knk，n=n0+nk，所以有knk=m+nk-1，则nk=(m-1)/(k-1)。
