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

admin2021-08-17 30

问题堆排序分为两个阶段，其中第一阶段将给定的序列建成一个堆，第二阶段逐次输出堆顶元素。设给定序列{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

计算机408

相关试题推荐

随机试题

最新回复(0)