第7章_排序_考点11_外部排序算法及其应用_2016年考研核心考点命题思路解密_数据结构.pdfVIP

2016 年考研核心考点命题思路解密——数据结构 梦享团队主编 考点11 外部排序算法及其应用 一．选择题部分 1. 不定长文件是指 （ ）。 A. 文件的长度不固定 B. 记录的长度不固定 C. 字段的长度不固定 D. 关键字项的长度不固定 2. 对于大文件的排序要研究在外设上的排序技术，即（ ）。 A. 快速排序法 B. 内排序法 C. 外排序法 D. 交叉排序法 二．综合应用题部分 1. 假设有12 个初始归并段，其长度分别为85，68，62，9，18，60，20 ，3，6，8，44 ， 2016 年考研核心考点命题思路解密——数据结构 梦享团队主编 30 ；现要作4 路外部归并排序，试画出表示归并过程的最佳归并树，并计算树的wpl 。 2. 设已有 12 个不等长的初始归并段，各归并段的长度（包含记录数）分别 为 RUN1 (25), RUN2 (13), RUN3 (04), RUN4 (55), RUN5 (30), RUN6 (47), RUN7 (19 ), RUN8 (80), RUN9 (76), RUN10 (92), RUN11 (55), RUN12 (89) 若采用的是4 路平衡 归并排序，试画出其最佳归并树，并计算每趟归并时的读记录数。（括号内即为该归并 段包含的记录数） 3. 设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试写出胜者树排序方法 每趟排序后的结果，并说明做了多少次排序码比较。 参 考 答 案 一．选择题部分 1. B 【解析】若文件中记录含有的信息长度相同，则称这类记录为定长记录。由这种定长 记录组成的文件称为定长文件。若文件中记录含有的信息长度不等，则称为不定长文件。 2. C 【解析】内排序是排序过程中参与排序的数据全部在内存中所做的排序，排序过程中 无需进行内外存数据传送，决定排序方法时间性能的主要因素是数据排序码的比较次数和 数据对象的移动次数。 外排序是在排序的过程中参与排序的数据太多，在内存中容纳不下，因此在排序过程 中需要不断进行内外存的信息传送的排序。 二．综合应用题部分 1. 【解析】归并段的个数为n=12 ，归并路数k=4 。(n-1)%(k-1)=11%3=2，不为0 。因 此必须附加(k-1)-(n-1)%(k-1)=3-2=1 个长度为0 的虚段，才能构成4 路归并树。该4 路归并 树的构建过程如图7.52~7.55 所示。 0 3 6 8 9 18 20 30 44 60 62 68 85 图 7.52 2016 年考研核心考点命题思路解密——数据结构 梦享团队主编 0 3 6 8 9 17 18 20 30 44 60 62 68 85 图 7.53 0 3 6 8 9 17 18 20 30 44 60 62 68 85 44 68 图 7.54 0 3 6 8 9 17 18 20 30 44 60 62