设有关键码序列(Q,G,M,Z,A,N,B,P,X,H,Y,S,T,L,K,E),采用堆排序 法进行排序,经过初始建堆后关键码值B在序列中的序号是( )。

admin2020-06-30  29

问题 设有关键码序列(Q,G,M,Z,A,N,B,P,X,H,Y,S,T,L,K,E),采用堆排序    法进行排序,经过初始建堆后关键码值B在序列中的序号是(    )。

选项 A、1   
B、3   
C、7
D、9

答案B

解析 建堆的算法:首先将要排序的所有关键码放到一棵完全二叉树的各个结点中(这时的二叉树不具备堆的特性),然后,从i=[n/2](n为结点的个数)的结点K<sub>i</sub>开始,逐步把以K<sub>[n/2]</sub>,K<sub>[n/2]-1</sub>,K<sub>[n/2]-2</sub>,…为根的子树排成堆,直到以K<sub>1</sub>为根的树排成堆,就完成了建堆过程。此题中,n=16,i=[16/2]=8,即从第8个结点开始,建堆完成后如下图:所以经过初始建堆后关键码值B在序列中的序号是3。
转载请注明原文地址:https://kaotiyun.com/show/hLHp777K
0

最新回复(0)