Relax1000 数据结构 · 第8章 排序 · 解析¶
第8章 排序¶
本章 78 题；解析册印刷页 66–77。
速对答案（原书）： D A C B B B D A C A B B C D A B B D B D B A C B A D B C C B A C A C C C D A B B A A A D A D D C B B D C (DC) C (DA) C C D A B B D B A D D A D B B C B C B B C C C
Q1¶
速对表原值： D
详细解析标注： D
直接插入排序从第二个元素开始，前面的序列为有序序列，后面的序列为待排序序列。每次都要需要将待排序序列第一个元素，在有序序列找到他插入的位置，进行元素移动和插入。最坏的情况是每轮待插入元素的位置都是有序序列的第一个，这样比较次数为 1+2+3+...+(n-1)=n(n-1)/2。举例：{n, n-1, ...2, 1}排序成升序序列。补充：最少比较次数是(n-1)次，即每次插入的元素都在最后面。如：{1, 2, ..., n-1, n}。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q2¶
速对表原值： A
详细解析标注： A
A 正确，直接插入排序最优的时间复杂度是 O(n)，最坏和平均时间复杂度是〔公式/符号见原页版面片段〕2。
B 错误，折半插入排序相较于直接插入排序，仅仅减少了每次比较的数量级（〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 ），平均时间复杂度是〔公式/符号见原页版面片段〕2，最好的情况〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 。
C 错误，希尔排序不稳定。考纲内不稳定的排序算法有：简单选择排序、希尔排序、堆排序、快速排序。
D 错误，初始序列不同，折半插入排序比较的次数是有差异的，因为折半查找判定树失败结点不一定在同一层。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q3¶
速对表原值： C
详细解析标注： C
A 错误，简单选择排序，最后两个元素一定是最大值和次大值。
B 错误，同 A。
C 正确。直接插入排序第二趟排序后，前面三个元素应局部有序，20，26，40 符合要求。
D 错误，两趟堆排序后，末尾两个元素一定是最大值（大根堆）或者最小值（小根堆），题目序列不符合要求。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q4¶
速对表原值： B
详细解析标注： B
越接近正序的序列，直接插入排序的比较次数就越少。选项 B 和 C 是比较接近正序的，然后分别判断两个序列的比较次数，以选项 B 为例：第一趟，插入 32，比较 1 次；第二趟，插入 46，比较 1 次：第三趟，插入 40，因为 40 比 46 小但比 2 大，所以比较 2 次；第四趟，插入 80，比较 1 次；第五趟，插入 69，比较 2 次；以此类推，共比较 9 次。同理求出选项 C 的比较次数为 11 次。所以选择选项 B。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q5¶
速对表原值： B
详细解析标注： B
增量 d=4，于是序列 50、40、95、20、15、70、60、45 中，50、15 是一组，40、70 是一组，95、60 是一组，20、45 是一组，经过组内排序后变为：15、40、60、20、50、70、95、45。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q6¶
速对表原值： B
详细解析标注： B
希尔排序将序列根据增量分成若干组，在组内进行简单插入排序。由观察可知，经过一趟后 9 和-1 交换，7 和 4 交换，可知增量为 4。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q7¶
速对表原值： D
详细解析标注： D
A 选项的排序过程为：[49₁, 38, 65,49₂, 76,13]→[49₁, 38,13, 49₂, 76,65]→[13, 38,49₁, 49₂, 65, 76]，整个过程没有破坏稳定性。B 选项的排序过程为：[49₁, 38, 49₂, 65, 13, 76]→[49₁, 13, 49₂, 65, 38, 76]→[13, 38, 49₁, 49₂, 65, 76]，同样没有破坏稳定性。C 选项的排序过程为：[49₁, 49₂, 13, 65, 76, 38]→[49₁, 49₂, 13, 65, 76, 38]→[13，49₁, 49₂, , 65, 76, 38]，同样没有破坏稳定性。D 选项的排序过程为：[49₁, 13, 65, 38, 76, 49₂]→[38, 13, 49₂, 49₁, 76, 65]→[13, 38, 49₂, 49₁, 65, 76]，破坏了稳定性。答案选 D。
Q8¶
速对表原值： A
详细解析标注： A
冒泡排序最少进行1趟冒泡，最多进行n-1趟冒泡。初始序列为逆序时，需进行 n-1 趟冒泡，并且元素交换的次数最多。初始序列为正序时，进行 1 趟冒泡(无交换)就可结束算法。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q9¶
速对表原值： C
详细解析标注： C
给出的初始待排序列为完全逆序序列，当记录个数为 n 时，冒泡排序需要进行 n－1趟，每一趟的比较次数分别为 n－1，n－2，…，1，此题中 n=6，因此总的比较次数是 5+4+3+2+1=15。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q10¶
速对表原值： A
详细解析标注： A
这题没说明排序的方向是从前往后还是从后往前，如果是从前往后排序，那么至少需要８趟，反之最少需要 6 趟，A 正确；由排序过程可知，元素的交换次数是 22 次，选项 B 排除；无论从前往后还是从后往前，序列的逆序数不变，交换的次数不变，都是 22 次，但是选项中说的是移动次数，每交换一次（swap）需要移动 3 次，所以移动次数是 66 次，选项 D错误；从后往前进行冒泡排序，第三趟的结果是 {1，2，4，5，9，10，8，6，20}，选项 C 错误。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q11¶
速对表原值： B
详细解析标注： B
第一趟排序结果为 4, 7, 3, 5, 6, 8, 9, 1, 2, [10], [10]表示已经排好的序列，下同；第二趟排序结果为[1], 4, 7, 3, 5, 6, 8, 9, 2，[10]；第三趟排序结果为[1], 4, 3, 5, 6, 7, 8, 2, [9, 10]；第四趟排序结果为[1, 2], 4, 3, 5, 6, 7, 8, [9, 10]；第五趟排序结果为[1, 2], 3, 4, 5, 6, 7, [8, 9, 10]，此时已有序，但仍需要一趟无交换的排序才能判断已经有序。所以总共需要 6 趟排序，答案为 B。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q12¶
速对表原值： B
详细解析标注： B
I 错误，最坏的时间复杂度是〔公式/符号见原页版面片段〕2。II 错误，快速排序的空间复杂度为递归深度，最大可达〔公式/符号见原页版面片段〕 。III 正确，每趟划分越均分，比较次数就越少，性能越佳。IV 正确，快速排序是不稳定的排序算法。不稳定的还有简单选择，堆排序，希尔排序。V 正确，左边区间的元素比基准元素小，右边区间的元素比基准元素大，所以左右区间相对有序。区间内无序。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q13¶
速对表原值： C
详细解析标注： C
C 选项(20，20，30，10，40)根据快排原理，当比对到 10，则 10 与第一个 20 交换位置，则相对于第二个 20 发生了位置变化。所以不稳定。
Q14¶
速对表原值： D
详细解析标注： D
每趟划分都会在区间中选择一个基准元素，使其左边的元素都比他小，右边的元素都比他大，应逐个观察每个元素的左右区间的元素，如果左边出现比他大的，或者右边出现比他小的，就不符合基准元素的要求，符合条件的只有 81。
Q15¶
速对表原值： A
详细解析标注： A
每次枢轴元素将区间划分得越均匀，排序速度越快。选择第一个元素为枢轴，那么 A、C 选项的 21 正好是序列的正中，所以排除 B、D。A 经过一次排序后结果为 9、17、5、（21）、25、23、30.C经过一次排序后结果为5、9、17、（21）、25、23、30.对于序列9、17、5和5、9、17，后者在有序状态下用快速排序方法的速度没有前者快，故本题选 A。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q16¶
速对表原值： B
详细解析标注： B
因为C、D选项基本有序，所以递归深度一定比较深。我们来比较A、B选项。A选项每趟划分如下：[4, 2, 6, 1, 5, 3, 8, 7]→[3, 2, 1, 4, 5, 6, 8, 7]→[1, 2, 3, 4, 5, 6, 8, 7]→[1, 2, 3, 4, 5, 6, 8, 7]→[1, 2, 3, 4, 5, 6, 7, 8]→[1, 2, 3, 4, 5, 6, 7, 8]，递归深度为 5。B 选项每趟划分如下：[5, 2, 6, 1, 4, 3, 8, 7]→[3, 2, 4, 1, 5, 6, 8, 7]→[1, 2, 3, 4, 5, 6, 8, 7]→[1, 2, 3, 4, 5, 6, 7, 8]→[1, 2, 3, 4, 5, 6, 7, 8]，递归深度为 4类比，B 选项的递归深度为 4，本题答案选 B。
Q17¶
速对表原值： B
详细解析标注： B
对各序列分别执行一趟快速排序，可做如下分析(以选项 A 为例)：枢轴值为92，因此 35 移动到第一个位置，96 移动到第六个位置，30 移动到第二个位置，再将枢轴值移动到 30所在的单元，即第五个位置，所以选项 A 中序列移动的次数为 4。同样，可以分析出选项 B 中序列的移动次数为 8，选项 C 中序列的移动次数为 4，选项 D 中序列的移动次数为 2。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q18¶
速对表原值： D
详细解析标注： D
对 n 个元素进行第一趟快速排序后，会确定一个基准元素，在这个基准元素的左边的元素（如果有）全部比他小，右边的元素（如果有）都比他大。A 选项中，第一轮可以选取 28 或者 72 作为基准元素，我们只要找一种符合的就可以，所以我们任选一种往后推进，这里我们选 72。第二轮我们对 72 的左区间进行第二轮排序，我们可以找到 28 作为基准元素，因此选项 A 可以是第二趟结果。对于 B 选项，第一轮可以选取 2，第二轮选取 72 作为基准元素。对于 C 选项，第一趟，我们可以选取 2，第二轮选择 28 作为基准元素。对于 D 选项，第一趟可选择 12 或者 32，若选 12，此时有左右两个区间，第二趟左区间没有符合的基准元素。若选 32，右边区间没有符合的，因此答案选 D。
Q19¶
速对表原值： B
详细解析标注： B
A 错误，每趟把未排序的元素中选择最小的元素加入已排序序列的尾部，移动的次数固定为每趟一次，n 趟 n 次。
B 正确，每趟确定一个元素的最终位置。
C 错误，简单选择排序，每轮都要从未排序序列选择最小的元素，需要比较当前剩余未排序元素个数-1 次。比较次数固定为(n-1) + (n-2) + ... + 1 = n(n-1)/2，所以比较次数是〔公式/符号见原页版面片段〕2，D 错误。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q20¶
速对表原值： D
详细解析标注： D
A 选项，设 5(A)为原序列在前的，5(B)为原序列在后的。初始：[4, 3, 5(A), 7, 6, 5(B), 2]找最小值 2 → 与 4 交换 → [2, 3, 5(A), 7, 6, 5(B), 4]找次小 3 → 与 3 本身交换（不变）→ [2, 3, 5(A), 7, 6, 5(B), 4]找次小 4 → 与 5(A) 交换 → [2, 3, 4, 7, 6, 5(B), 5(A)]找次小 5(B) → 与 7 交换→ [2, 3, 4, 5(B), 6, 7, 5(A)]找次小 5(A) → 与 6 交换→ [2, 3, 4, 5(B), 5(A), 7, 6]找次小 6 → 与 7 交换→ [2, 3, 4, 5(B), 5(A), 6, 7]同理 B、C 也是不稳定的，D 选项两个元素 5 的位置先后次序始终不变，并没有说明不稳定，答案选 D。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q21¶
速对表原值： B
详细解析标注： B
第一趟选择 1，将 1 和 12 交换位置，序列变为 1，15，12，18，2，35，30，11；第二趟选择 2，将 2 和 15 交换位置，序列变为 1，2，12，18，15，35，30，11。故 B 正确，A、C、D错误。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q22¶
速对表原值： A
详细解析标注： A
堆数据结构是一种数组对象，它可以被视为一颗完全二叉树结构。它的特点是父节点的值大于（小于）两个子节点的值（分别称为大顶堆和小顶堆）。判断方法：将序列转换成一棵完全二叉树，再看各个子树是否都满足最大堆或者最小堆的要求。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q23¶
速对表原值： C
详细解析标注： C
题目所给序列是无序的，且要进行降序排列，因此每次换到堆尾的是最小的元素，因此要先构建初始小根堆。构建完后堆为{1, 2, 5, 16, 20, 19, 34}，第一趟调整后为{2, 16, 5, 34, 20, 19, 1}，第二趟调整后为{5, 16, 19, 34, 20, 2, 1}，因此答案选 C。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q24¶
速对表原值： B
详细解析标注： B
使用堆排序时，初始堆需要一个大根堆，建堆时先画出完全二叉树，然后从(heap_size-1)/2号元素，即57开始从后往前调整，每次调整i号元素时将i号元素、i* 2+1号元素、i*2+2号元素中的最大元素和 i 号元素交换位置，模拟此过程最终可以得到初始堆为 89，78，57，25，41，45。
Q25¶
速对表原值： A
详细解析标注： A
注意区分题目的信息，如果题目说的是将关键字进行堆排序或者构建一个小根堆，那么需要进行建堆（调整）的操作。但此题已经是一个小根堆，需要一个个插进去，每次将关键字查到堆尾，向上调整。然后下一次插入，直到所有的关键字都插入到小根堆为止。过程如下：
原页版面片段（用于核对图表、公式、矩阵或代码）
Q26¶
速对表原值： D
详细解析标注： D
本题考查堆排序的执行过程。筛选法初始建堆为{8，17，23，52，25，72，68，71，60}，输出 8 后重建的堆为{17，25，23，52，60，72，68，71}，输出 17 后重建的堆为{23,25,68, 52, 60, 72, 71}。
Q27¶
速对表原值： B
详细解析标注： B
首先对以第[n/2]个结点为根的子树筛选，使该子树成为堆，之后向前依次对各结点为根的子树进行选，直到选到根结点。序列(48.62.35.77.55.14.35.98}建立初始堆的过程如下所示。如图所示，(a)调整结点 77，交换 1 次； (b)调整结点 35，不交换；(c)调整结点 62，交换 2 次：(d)调整结点 48，交换 3 次。所以上述序列建初始堆，共交换元素 6 次。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q28¶
速对表原值： C
详细解析标注： C
建大根堆后，序列为{94, 80, 90, 46, 69, 21, 32, 40}。如下左图；插入 66，应放在堆尾，然后向上调整，遇到比他小的，就交换。调整结束后的序列为{94, 80, 90, 66, 69, 21, 32, 40, 46}，如下右图。所以 66 在第 3 层。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q29¶
速对表原值： C
详细解析标注： C
建成小根堆后，序列为{21, 40, 32, 46, 69, 94, 90, 80}。如下左图；删除 21，将堆尾元素放到删除位置，然后向下调整，调整结束后的序列为{32, 40, 80, 46, 69, 94, 90}，如下图所示。堆顶元素的两个孩子为 40, 80，答案选 C。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q30¶
速对表原值： B
详细解析标注： B
堆并不是一棵二叉排序树，他满足根节点大于孩子结点即可，不需要保证左<根<右。
Q31¶
速对表原值： A
详细解析标注： A
采用空间 k=10 的小根堆，遍历剩余的 9990 个元素：
①当前元素>堆顶：说明它有资格成为 “前 10 大”，替换堆顶并调整堆（确保新堆顶仍是堆内最小值）；
②当前元素≤堆顶：说明它不可能是前 10 大，直接跳过；遍历结束后，堆内 10 个元素就是前 10 大（堆顶是第 10 大，堆内是 “从小到大” 的前 10大）。时间复杂度：O(k + (n-k)log k)，建堆 O(k)，后续插入调整 O((n-k)logk)。本题答案为 A。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q32¶
速对表原值： C
详细解析标注： C
归并趟数 S=⌈〔公式/符号见原页版面片段〕⌉ = ⌈〔公式/符号见原页版面片段〕64⌉ = 3，解得 k=4。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q33¶
速对表原值： A
详细解析标注： A
对于{25，48，16，35，79，82，23，40，36，72}，{25，48}和{16，35}两个子序列归并的结果为{16，25，35，48}，{79，82}和{23，40}两个子序列归并后的结果为{23，40，79，82}，余下的两个记录本趟不归并，所以一趟归并后的结果为{16，25，35，48，23，40，79，82，36，72}。本题答案为 A。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q34¶
速对表原值： C
详细解析标注： C
A 选项正确，如果是第一趟后的结果，那么每个小区间内的 2 个元素应该是局部有序的。而题干的序列 49, 38 无序，所以有序的区间大小只能是 1，也就是初始状态。
B 正确，趟数 S=⌈〔公式/符号见原页版面片段〕27 = 3⌉。
C 错误，第一趟，两两归并，2 个元素归并，只需要比较一次即可，落单的 27 无需比较，所以比较次数为 3 次。
D 正确，排序过程如下图所示：
原页版面片段（用于核对图表、公式、矩阵或代码）
Q35¶
速对表原值： C
详细解析标注： C
基数排序有 MSD 和 LSD 两种，第一种是最高位优先(MSD)法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列；第二种是最低位优先(LSD)法，按关键字位权重递增依次进行排序，最后形成一个有序序列。基数排序是稳定的。对于选项 A，不符合 LSD 和 MSD；对于选项 B，符合 MSD，但关键字 42、46 的相对位置发生了变化；对于选项 D，不符合 LSD 和 MSD。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q36¶
速对表原值： C
详细解析标注： C
关键字有 m 位，则要进行 m 趟的分配和收集，一趟中，分配是指把 n 个关键字放到对应队列(有 r 个队列)里，然后再对每个队列进行收集，分配的时间复杂度为 O(n)，收集的时间复杂度为 O(r)，所以总的时间复杂度为〔公式/符号见原页版面片段〕 + 〔公式/符号见原页版面片段〕 。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q37¶
速对表原值： D
详细解析标注： D
临时建立的队列个数为进制数大小，应选 D。
Q38¶
速对表原值： A
详细解析标注： A
冒泡排序、堆排序和快速排序的每一趟都能使至少一个记录元素到达最终在有序序列中的位置上，但是作为直接插入排序，如果整个初始记录序列的最后一个记录有最小关键字，那么就会出现题中描述的情况。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q39¶
速对表原值： B
详细解析标注： B
快速排序是不稳定排序，冒泡排序是稳定排序，堆排序是不稳定排序，归并排序是稳定排序，插入排序是稳定排序，因此上述排序算法中有三种是稳定排序算法。
Q40¶
速对表原值： B
详细解析标注： B
例如对于序列[4，3，2，1]（反序）和[3，4，2，1]（非反序），使用简单选择排序，前者需要交换元素 2 次，后者需要交换元素 3 次。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q41¶
速对表原值： A
详细解析标注： A
A.直接选择排序由于每次都需要遍历整个序列选出最大（最小）值，所以平均、最好、最坏都是〔公式/符号见原页版面片段〕2 B．直接插入排序最好情况下复杂度为 O(n) C．冒泡排序最好情况下复杂度为 O(n) D．归并排序每次进行都需要进行分组、合并，复杂度都为〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
原页版面片段（用于核对图表、公式、矩阵或代码）
Q42¶
速对表原值： A
详细解析标注： A
I 错误，I 还是 O(n²)，比较操作的复杂度降为 O（logn）移动操作的次数不变，总体不变。II 正确； III 正确，相对有序情况下，插入排序的时间复杂度接近 O（n）；IV 错误，若每次都是查找第一个元素，顺序查找为 O(1)，折半查找 O（logn）。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q43¶
速对表原值： A
详细解析标注： A
堆排序每趟结束都能将一个最值放在根节点；冒泡排序进行两两比较，每趟选出最大值或最小值；快速排序一趟可以选出比关键值大的和比关键值小的，从而确定位置；直接插入排序插入的时候不能确定一个元素的最终位置。
Q44¶
速对表原值： D
详细解析标注： D
归并排序需要创建新数组来完成新的顺序存储，需要辅助空间〔公式/符号见原页版面片段〕 ，简单选择排序和堆排序的辅助空间为〔公式/符号见原页版面片段〕(1)，快排的为〔公式/符号见原页版面片段〕 。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q45¶
速对表原值： A
详细解析标注： A
归并排序：基于分治的思想，其时间复杂度总是：〔公式/符号见原页版面片段〕快速排序：平均时间复杂度是：〔公式/符号见原页版面片段〕 ，最坏时间复杂度为：〔公式/符号见原页版面片段〕2冒泡排序：平均时间复杂度是：〔公式/符号见原页版面片段〕2，最坏时间复杂度为：〔公式/符号见原页版面片段〕2插入排序：平均时间复杂度是：〔公式/符号见原页版面片段〕2，最坏时间复杂度为：〔公式/符号见原页版面片段〕2
原页版面片段（用于核对图表、公式、矩阵或代码）
Q46¶
速对表原值： D
详细解析标注： D
题目的排序可类比 2 位整数排序，k1 是十位，k2 是个位回忆基数排序，我们是先由低位向高位排序，所以应该先排序 k2，再排序 k1。排除 A、C。B、D 区别在于直接排序是稳定的，简单选择是不稳定的，我们举例讨论：21、22、13先按 k2 排序：21、22、13。再按 k1 排序，如果不稳定，比如简单选择：第一趟：13 21 22；第二趟：13 22 21；第三趟：13 22 21，不符合题意。
Q47¶
速对表原值： D
详细解析标注： D
以上全部需要考虑。
Q48¶
速对表原值： C
详细解析标注： C
简单选择排序在最好、最坏、平均情况下的时间性能均为 〔公式/符号见原页版面片段〕(〔公式/符号见原页版面片段〕2)，归并排序在最好、最坏、平均情况下的时间性能均为〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 。。快速排序在原序列本身有序的时候达到最坏的时间复杂度，直接插入排序在原序列本身有序的时候达到最好的时间复杂度
原页版面片段（用于核对图表、公式、矩阵或代码）
Q49¶
速对表原值： B
详细解析标注： B
排序算法的性能取决于多种因素，如序列初始状态、数据规模等等，A 错误。基数排序和归并排序是稳定的排序方法，B 正确。快速排序是一种交换排序，C 错误。堆排序的空间复杂度为 O(1)，其所用的辅助空间较小，D 错误。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q50¶
速对表原值： B
详细解析标注： B
基数排序每趟需要利用前一趟已排好的序列，无法并行执行。快速排序每趟划分的子序列互不影响，可以并行执行。冒泡排序每趟对未排序的所有元素进行一趟处理，无法并行执行。堆排序可以并行执行，因为根结点的左右子树构成的子堆在执行过程中是互不影响的。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q51¶
速对表原值： D
详细解析标注： D
I 正确，简单选择排序，无论待排序序列初始状态如何，比较的次数始终是 〔公式/符号见原页版面片段〕 − 1 + 〔公式/符号见原页版面片段〕 − 2 + ... + 2 + 1 = 〔公式/符号见原页版面片段〕 − 1 〔公式/符号见原页版面片段〕/2。冒泡排序，元素基本有序的情况下，比较次数接近 O(1)。II 错误，两者的空间复杂度都是 O（1）III 正确，冒泡排序稳定，简单选择排序不稳定。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q52¶
速对表原值： C
详细解析标注： C
基数排序是基于关键字各位的大小进行收集排序的，而不是基于关键字的比较进行的
Q53¶
速对表原值： (DC)
详细解析标注： D、C
归并排序在平均情况和最坏情况下的空间复杂度都是 〔公式/符号见原页版面片段〕 ，快速排序只在最坏情况下才是〔公式/符号见原页版面片段〕 ，平均情况是〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q54¶
速对表原值： C
详细解析标注： C
采用败者树进行 k 路平衡归并时，内部归并过程中记录关键字的比较总次数将与k 无关，但是，总的归并效率与 k 有关，当 k 较大时，归并趟数减少，因此可以减少内外存信息交换次数从而提高总的归并效率。不过，k 值的选择会受到内存缓冲区大小等因素限制。另外，初始归并段个数减少也是减少归并趟数即减少内外存交换的一个方法。
Q55¶
速对表原值： (DA)
详细解析标注： D、A
相比普通的 m 路归并：需增加一个输出缓冲区，当一个输出缓冲区满时，输出一个缓冲区的同时归并程序可向另一个输出缓冲区填充数据，这就实现了内部归并和输出的并行。需增加 m 个输入缓冲区，当 m 个输入缓冲区正在运行时，外部可向新增的 m 个缓冲区写入数据，这就实现了输入和内部归并的并行。综上，需设置 2 个输出缓冲区，2m 个输入缓冲区。
Q56¶
速对表原值： C
详细解析标注： C
每次让计算机内存填满 400，3110400 个记录要填 3110400/400 = 7776 次，对于 n路归并排序，m 个归并段，需要归并排序的次数为⌈〔公式/符号见原页版面片段〕⌉次，代入数据得到答案为 5。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q57¶
速对表原值： C
详细解析标注： C
首先要用内部排序生成局部有序的初始归并段，每个初始归并段段长和内部排序的工作区容量相等，为 250 个记录。那么内部排序需要进行 8 次，生成 8 个初始归并段。每次读写 2 个磁盘块，每读/写一个磁盘块为一次 I/O，总计 822=32 次 I/O。在二路平衡归并排序中，初始归并段共8 段，归并趟数〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕28 = 3 趟，每趟读 16 次(2000/125=16 块)，写 16 次，归并排序 I/O 次数为1623=96 次。所以整个过程为 32+96=128 次。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q58¶
速对表原值： D
详细解析标注： D
败者树是一种用于多路归并的完全二叉树，由于每个叶子需要决出胜负（比较），故没有度为 1 的节点。其中每个非叶子节点表示输掉比较的元素，叶子节点对应于归并路数 k。二叉树叶子节点数为 k，那么度为 2 的结点数为 k-1，总节点数为 2k-1，D 为正确选项。
Q59¶
速对表原值： A
详细解析标注： A
败者树是一种特殊的二叉树，用于进行多路归并排序。败者树的特点如下。对于A 选项，在败者树中，非叶子结点存储的是败者的标号，即从子结点中选出的较大值所对应的标号。这是败者树的核心特点，故选 A。B 选项说法不准确，败者树的叶子结点存储的是归并排序中各个路的当前记录的索引值，而不是原始输入数据。
C 选项错误。败者树主要用于外部排序，尤其是多路归并排序。
D 选项错误。败者树的根结点存储的是最后一次竞争败者所对应的标号。最小值存储在败者树的另一个额外的结点中，称为“最终胜者”。
Q60¶
速对表原值： B
详细解析标注： B
I 错误，分支结点存储的内容是失败记录所在缓冲区的编号，叶子结点存储的是每个缓冲区（归并段）当前参加比较的第一个记录的关键字的值，要注意区分。II 正确，上个冠军结点所在缓冲区的记录被选择后，补充该缓冲区后续一个记录的关键字进对应叶子结点，一直跟到根节点路径上的上一轮失败结点进行比较，胜者继续往上比较，直到选出新的冠军结点为止。III 错误，败者树（除冠军节点外）是一棵完全二叉树，且只有度为 2 和 0 的结点（因为要两两比较）。根据二叉树性质：叶子节点个数=度为 2 的个数+1，所以总结点个数是 2〔公式/符号见原页版面片段〕0 − 1，〔公式/符号见原页版面片段〕0即归并段的个数，空间开销即二叉树的容量，因此是〔公式/符号见原页版面片段〕 。补充：败者树每次比较的时间开销是〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 。IV 正确，如果不加最大值的记录，那么一个归并段的记录消耗完后，没法继续进行败者树的运行了。综上 I、III 错误，答案选 B。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q61¶
速对表原值： B
详细解析标注： B
构建的败者树如左图所示，第二轮比较后，如右图所示，可知根节点是归并段 0的编号。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q62¶
速对表原值： D
详细解析标注： D
首先要判断是否要补充虚段，计算 t=(n-1)%(k-1)是否为 0，本题中，t=(n-1)%(k-1)=(9-1)%(3-2)=0，不需要补充；若不为 0，需要补充的虚段数为 n-1-n=t。最佳归并树如下。每个结点再 归 并 排 序 中 需 要 读 出 和 写 入 磁 盘 各 一 次 ， 所 以 I/O 次 数 为 WPL2 。 经 计 算 I/0 次 数=2(23+33+63+92+122+172+182+242+30*1)=446。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q63¶
速对表原值： B
详细解析标注： B
得到了 3 个初始归并段：(04, 12, 15, 19, 25, 27, 34, 83)，(07, 10, 11, 16, 26, 90)和(06)。
Q64¶
速对表原值： A
详细解析标注： A
此题答案选 A。初始化过程，以及第一个归并段形成过程如下图所示：（图 j 是输出 6 个记录后选得 MINIMAX 记录为 wa[1]的败者树，图 k 为得到第一个初始归并段后的状态。）
原页版面片段（用于核对图表、公式、矩阵或代码）
Q65¶
速对表原值： D
详细解析标注： D
置换-选择排序算法主要用于外部排序，当内存空间有限时，需要将大量数据分段进行排序。在算法中首先将输入数据流的前 k 个记录读入内存作为候选区。然后，执行以下操作。（1）从候选区中选择最小记录（2）将最小记录输出到当前归并段（3）从输入数据流中读取下一个记录，如果该记录大于或等于已输出的最后一个记录，将其插入到候选区中适当的位置。否则，将该记录存入适当的归并段。重复步骤(1)～(3)，直到输入数据流中的所有记录都被处理完毕。因此，选项 D 正确描述了置换-选择排序算法如何处理候选区和输入数据流的关系。
Q66¶
速对表原值： D
详细解析标注： D
败者树每次选择一个 MINIMAX 记录的时间复杂度是〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 ，一共要选择 n-1轮，所以整体的时间复杂度是〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 。本题细节应结合上一题理解。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q67¶
速对表原值： A
详细解析标注： A
选择置换排序工作流程如下：
①从输入文件 FI 输出 w 个记录到工作区 WA。
②从 WA 中选出其中关键字取最小值的记录，记为 MINIMAX 记录。
③将 MINIMAX 记录输入到输出文件 FO。（FI 和 FO 一般是外部文件物理块—缓冲区—内存工作区 WA 交互）
④若 FI 不空，则从 H 输出下一个记录到 WA。
⑤从 WA 中所有关键字比 MINIMAX 记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX 记录。
⑥ 重复➂～
⑤，直至 WA 中选不出新的 MINIMAX 记录为止，由此得到一个初始归并段，输入一个归并段的结束标志到 FO。
⑦重复
②～
⑥，直至 WA 为空。由此得到所有初始归并段。所以，Ⅰ、Ⅲ 都是选择 - 置换算法选择下一个符合条件的 MINMAX 的具体流程。
Ⅱ错误，当进行关键字比较时，先比较序号，应该选择段号小的为胜者，因为段号大的是后来新加入的一批的元素，新一批添加的元素的比当前 MINMAX 更小的数值（段号更大）是不应该被选取的。
Q68¶
速对表原值： D
详细解析标注： D
I 正确：外部归并排序先要产生初始归并段，通常是在内存工作区中用内部排序算法得到有序段。且在多路平衡归并中，初始归并段的大小相等，通常为内存工作区的大小。II 正确：置换-选择排序可以生成比内存工作区更长的初始归并段，从而减少初始归并段个数，进而减少归并趟数和磁盘 I/O。III 正确：败者树用于多路归并时，可以减少从各归并段当前元素中选出最小关键字所需的比较次数。IV 正确：置换-选择排序中也可用败者树优化，减少选择 MINIMAX 的比较次数。V 基本正确：最佳归并树采用哈夫曼树思想，用于在初始归并段长度不等时安排归并顺序，使总归并代价最小，主要减少磁盘 I/O 次数。
Q69¶
速对表原值： B
详细解析标注： B
因为每次都是 8 个归并段合并，所以归并树是度为 m 的正则树，只有度为 m 和叶子结点，由公式：度数之和+1=结点总数可以得到，〔公式/符号见原页版面片段〕 + 1 = 〔公式/符号见原页版面片段〕 + 〔公式/符号见原页版面片段〕0 → 〔公式/符号见原页版面片段〕 − 1 〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕0 − 1 → 〔公式/符号见原页版面片段〕 =〔公式/符号见原页版面片段〕 − 1 / 〔公式/符号见原页版面片段〕 − 1 ，但我们要注意到，当 〔公式/符号见原页版面片段〕 − 1 % 〔公式/符号见原页版面片段〕 − 1 = 0，不需要补充虚结点；当 〔公式/符号见原页版面片段〕 − 1 % 〔公式/符号见原页版面片段〕 − 1 ≠ 0，我们要补充虚结点，补充的虚结点个数为 〔公式/符号见原页版面片段〕 − 1 − 〔公式/符号见原页版面片段〕 − 1 % 〔公式/符号见原页版面片段〕 − 1 。补充的目的其实就是使〔公式/符号见原页版面片段〕是个整数，即补充后的段数是(m-1)的倍数。将 n=80，m=8 代入，补充的虚段数是 8 − 1 − 80 − 1 % 8 − 1 = 5。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q70¶
速对表原值： B
详细解析标注： B
I/O 次数为形成初始归并段的内部排序和归并排序的磁盘 I/O 次数和归并排序的I/O 次数之和。归并排序趟数 S=log_k，其中 k 为归并路数，r 为初始归并段数，归并排序的 I/O 次数=S（记录总数/单个磁盘块所能容纳记录数） *2（2 是因为读入和写出各一次）所以要减少 I/O 次数就要减少 S，由〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕，减少 S 可以增大 k 或者减少 r。A 选项选择置换排序是减少初始归并段数 r，但此时每个初始归并段大小不一样，所以需要 C 选项最佳归并树得到最小的 wpl（I/O 次数）。D 选项是增大 k，同样可以减小 S，但由于内存缓冲区资源有限 k，k 路归并需要至少 k 个缓冲区，所以 k 不可无限增大。B 选项，败者树是为了减少归并排序每次选取 k 个缓冲区中的最小的记录的比较次数，使得每次从k 个缓冲区的首元素选出最小的数，比较次数 k-1 降为〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕，与 I/O 次数无关，故此题选 B。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q71¶
速对表原值： C
详细解析标注： C
插入 38：1 次；插入 65：2 次；插入 97：2 次；插入 76：3 次；插入 13：2次；插入 27：3 次。1 + 2 + 2 + 3 + 2 + 3 = 13 次，答案选 C。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q72¶
速对表原值： B
详细解析标注： B
间 隔 为 d 的 元 素 作 为 一 组 ， 组 内 有 序 。 当 d=3 ， 三 组 元 素 依 次 是{7,12,40},{15,18,34},{3,9,25}，每组内的元素皆有序，所以 d=3 符合。其他选项的间隔下都不符合。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q73¶
速对表原值： C
详细解析标注： C
第一趟：49 38，移动 49，1 次 第二趟：38 49 65，0 次 第三趟：38 49 65 97，0 次 第四趟：38 49 65 97 76，移动 97，1 次 第五趟：38 49 65 76 97 13，移动 97、76、65、49、38，5 次 第六趟：13 38 49 65 76 97 27，移动 97、76、65、49、38，5 次 一共 1+0+0+1+5+5=12 次。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q74¶
速对表原值： B
详细解析标注： B
冒泡排序的交换次数等于序列中的逆序对个数。下面统计逆序对个数： 5 > 1，5 > 4，5 > 2，5 > 3，共 4 个 4 > 2，4 > 3，共 2 个 8 > 3，共 1 个 一共 4 + 2 + 1 = 7，所以交换次数为 7 次。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q75¶
速对表原值： B
详细解析标注： B
第一趟按个位排序：930，063，184，505，278，109，589 第二趟按按十位从小到大收集，并保持稳定性：505，109，930，063，278，184，589，答案选 B。
Q76¶
速对表原值： C
详细解析标注： C
原序列为：49，38，65，97，76，13，27 从最后一个非叶子结点开始调整。调整结点 65：比较 13 和 27，1 次，比较 65 和 27，1 次，共 2 次。 调整结点 38：比较 97 和76，1 次；比较 38 和 97，1 次，共 2 次。 调整结点 49：比较 97 和 65，1 次，比较 49 和 97，1 次，交换后继续调整：比较 38 和 76，1 次，比较 49 和 76，1 次，共 4 次。 总比较次数：2 + 2 + 4 = 8，答案选 C。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q77¶
速对表原值： C
详细解析标注： C
链表不支持随机访问，因此希尔排序、堆排序、折半插入排序不适合链表结构。归并排序只需要顺序访问，并且链表合并时不需要大量移动元素，因此较适合链表存储结构。
Q78¶
速对表原值： C
详细解析标注： C
A 错误，冒泡排序平均时间复杂度为 O(n2)，不属于先进的排序算法。B、C、D中，只有归并排序是稳定的，所以答案选 C。
原页版面片段（用于核对图表、公式、矩阵或代码）
