6.5 选择排序--考研乐学帮

6.5 选择排序

6.5 选择排序

　　考试大纲涉及本节的知识点有：直接选择排序和堆排序。

选择题

　　1．选择题题目部分
　　● 以下序列中不符合堆定义的是（1）。
　　（1）A．(102,87,100,79,82,62,84,42,22,12,68)
　　　　 B．(102,100,87,84,82,79,68,62,42,22,12)
　　　　 C．(12,22,42,62,68,79,82,84,87,100,102)
　　　　 D．(102,87,42,79,82,62,68,100,84,12,22)
　　● 一组记录的排序码为{46,79,56,38,40,84}，则利用堆排序的方法建立的初始堆为（2）。
　　（2）A．79,46,56,38,40,84 B．84,79,56,38,40,46
　　　　 C．84,79,56,46,40,38 D．84,56,79,40,46,38
　　● 堆排序是一种（3）排序，m个元素进行堆排序时，其时间复杂性为（4）。
　　（3）A．归并 B．交换 C．选择 D．插入
　　（4）A．O(m) B．O(m²) C．O(log₂^m) D．O(mlog₂^m)
　　2．选择题练习的答案与分析
　　题号（1）
　　答案　D
　　习题分析：
　　根据堆的定义：n个元素的序列{K₁,K₂,…,K_n}当满足下列关系时，称为堆：K_i≤K_2i且K_i≤K_2i+1，或者K_i≥K_2i且K_i≥K_2i+1。
　　套用上面的这个规则，我们可以知道D不是堆。
　　题号（2）
　　答案　B
　　习题分析：
　　首先对这些数据建立完全二叉树，填充的规则是按层次遍历将数据一一填入，如图6-6所示。
　　下面要把此二叉树调整为堆，首先看最后一个节点84，它比其父节点56大，所以应该把84和56的位置对调，得图6-7。
　　接下来看倒数第二个节点40，它比其父节点小，所以不用调整；再看节点38，它也比父节点小，所以仍然不要调整；再看节点84，它比父节点46大，所以把它们对调，如图6-8所示。
　　此时的节点46所处的位置不正确，因为它比其子节点56小，所以要把46与56对调，如图6-9所示。

　　图6-6 初建堆第一步　　　　　　图6-7 初建堆第二步

　　　图6-8 初建堆第三步　　　　　　图6-9 初建堆完成

　　这样，初建堆也就形成了。按层次遍历下来，得到初建堆：84,79,56,38,40,46。所以此题选答案B。
　　题号（3）（4）
　　答案　C　　 D
　　习题分析：
　　堆排序是利用堆这一特殊的树形结构进行的选择排序，它有效地改进了直接选择排序，提高了算法的效率。堆排序的整个过程是：构造初始堆，将堆的根节点和最后一个节点交换，重新调整成堆，再交换，再调整，直到完成排序。其时间复杂度是O(nlog₂ⁿ)。
　　3．训练自测表（如表6-5所示）