第7章_排序_考点8_二路归并排序_2016年考研核心考点命题思路解密_数据结构.pdfVIP

2016 年考研核心考点命题思路解密——数据结构 梦享团队主编 考点8 二路归并排序 一．选择题部分 1. 设一组初始记录关键字序列为(25 ，50，15，35，80，85，20 ，40 ，36，70) ，其中含有 5 个长度为2 的有序子表，则用归并排序的方法对该记录关键字序列进行2 趟归并后的 结果为 （ ）。 A. 15，25 ，35，50，20 ，40 ，80，85，36，70 B. 15，25 ，35，50，80，20 ，85，40 ，70，36 C. 15，25 ，35，50，80，85，20 ，36，40 ，70 D. 15，25 ，35，50，80，20 ，36，40 ，70，85 2. 二路归并排序的时间复杂度为 （ ）。 2 A. O(n) B. O(n ) C. O(nlog n) D. O(1og n) 2 2 3. 对长度为 10 的表作2_路归并排序,共需移动 （ ）次(个)记录。 A. 20 B. 45 C. 40 D. 30 4. 若有文件的关键字序列为：[265] [301] [751] [129] [937] [863] [742] [694] [076] [438]， 以下为二路归并排序过程。第1 趟为：（ ）。 A. [265 301] [129 751] [863 937] [694 742] [076 438] B. [076 129 265 301 438 694 742 751 863 937] C. [129 265 301 694 742 751 863 937] [076 438] D. [129 265 301 751] [694 742 863 937] [076 438] 5. 已知一组关键字为{25，48 ，36，72，79 ，82，23 ，40 ，16，35}，其中每相邻两个为 有序子序列。对这些子序列进行1 趟两两归并的结果是 （ ）。 A. {25，36，48 ，72，23 ，40 ，79，82，16，35} B. {25，36，48 ，72，16，23 ，40 ，79，82，35} C. {25，36，48 ，72，16，23 ，35，40 ，79，82} D. {16，23 ，25 ，35，36，40 ，48 ，72，79，82} 二．综合应用题部分 1. 对序列 21 、25 、49 、25* 、93、62、72、08、37、16、54 进行二路归并排序，并写出 详细的归并排序过程。 2. 对49 、38、65、97、73、13、27 进行二路归并排序，并写出详细的归并排序过程。 2016 年考研核心考点命题思路解密——数据结构 梦享团队主编 参 考 答 案 一．选择题部分 1. A 【解析】归并排序的基本思想为：将两个或两个以上的有序子序列“归并”为一个有 序序列。 在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列 归并为一个有序序列。 归并排序的过程为：假设初始序列含有n 个记录，则可看成n 个有序的子序列，每个 ⌈ ⌉ 子序列长度为1。然后两两归并，得到/2 个长度为2 或1 的有序子序列；再两两归并，…… 如此重复，直至得到一个长度为n 的有序序列为止。 对本题所给的序列进行二路归并排序，过程如图7.28 所示。 25 50 15 35 80 85 20 40 36 70