2. 专升本
  3. 下列四个序列中，( )是堆。

下列四个序列中，( )是堆。

admin2014-10-20  47
问题 下列四个序列中，(    )是堆。
选项 A、75，65，30，15，25，45，20，10  
B、75，65，45，10，30，25，20，15
C、75，45，65，30，15，25，20，10  
D、75，45，65，10，25，30，20，15
答案C
解析 堆排序是另一种基于选择的排序方法。n个元素的序列{k1，k2，k3，…，kn)，当且仅当满足以下关系时，称之为堆：ki＜=k2i;ki＜=k2i+1  或者  ki＞=k2i;ki＞=k2i+1其中i=1，2，…，n／2。若将同以上序列对应的一维数组看成是一棵完全二叉树，则堆的含义表明：该完全二叉树的所有非终端结点均不大于(或不小于)其左、右孩子结点的值。由此，若{k1，k2，k3，…，kn)是堆，则堆顶元素(或完全二叉树的根结点)必定是该序列n个元素中的最小值(或者最大值)。若将堆看成是一棵以k1为根的完全二叉树，则这棵完全二叉树中的每个非终端结点的值均不大于(或不小于)其左、右孩子结点的值。由此可以看出，若一棵完全二叉树是堆，则根结点一定是这n个结点中的最小者(或最大者)。下面图给出的两个堆的示例。

从堆的定义可以看出，若将堆用一棵完全二叉树表示，则根结点是当前堆中所有结点的最小者(或最大者)。堆排序的基本思想是：首先将待排序的记录序列构造一个堆，此时，选出了堆中所有记录的最小者或最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小(或次大)的记录，以此类推，直到堆中只有一个记录为止，每个记录出堆的顺序就是一个有序序列。
转载请注明原文地址:https://kaotiyun.com/show/IqvR777K
本试题收录于： 计算机科学与技术题库普高专升本分类
0

计算机科学与技术

普高专升本

相关试题推荐
随机试题
最新回复(0)