堆排序分为两个阶段,其中第一阶段将给定的序列建成一个堆,第二阶段逐次输出堆顶元素。设给定序列{48,62,35,77,55,14,35,98},若在堆排序的第一阶段将该序列建成一个堆(大根堆),那么交换元素的次数为( )。

admin2021-08-17  33

问题 堆排序分为两个阶段,其中第一阶段将给定的序列建成一个堆,第二阶段逐次输出堆顶元素。设给定序列{48,62,35,77,55,14,35,98},若在堆排序的第一阶段将该序列建成一个堆(大根堆),那么交换元素的次数为(    )。

选项 A、5
B、6
C、7
D、8

答案B

解析 考查初始堆的构造过程。首先对以第「n/2」个结点为根的子树筛选,使该子树成为堆,之后向前依次对各结点为根的子树进行筛选,直到筛选到根结点。序列{48,62,35,77,55,14,35,98)建立初始堆的过程如下所示:

    如图所示,(a)调整结点77,交换1次;(b)调整结点35,不交换;(c)调整结点62,交换2次;(d)调整结点48,交换3次。所以上述序列建初始堆,共交换元素6次。
转载请注明原文地址:https://jikaoti.com/ti/jSDjFFFM
0

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