首页 > 试题广场 >

设有关键码序列(Q,G,M,Z,A,N,B,P,X,H,Y,

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

  • 1
  • 4
  • 8
  • 12
推荐
A
堆排序的基本思想:对二组待排序的关键码,首先把它们按堆的定义排列成一个序列,找到其中最小的关键码,接着将最小的关键码取出,然后将剩下的关键码再建堆排序,依次进行,直到将全部关键码排好为止。
建堆的算法:首先将要排序的所有关键码放到一棵完全二叉树的各个结点中(这时的二叉树不具备堆的特性),然后,从i=[n/2](n为结点的个数)的结点Ki开始,逐步把以K[n/2],K[n/2]-1,K[n/2]-2,…为根的子树排成堆,直到以K1为根的树排成堆,就完成了建堆过程。
此题中,n=16,i=[16/2]=8,即从第8个结点开始,建堆完成后如下图所示:

经过初始建堆后关键码值A在序列中的序号是1。
综上,本题选A

编辑于 2020-01-21 15:40:09 回复(3)
题目没说按升序排还是降序排。我按升序排建堆,发现A在11号位,没答案。。。。。
发表于 2020-06-06 23:27:18 回复(5)
A。考察的是堆构建。
  1. 根据给定的序列构成一个初始完全二叉树,按照层序将序列添加到完全二叉树节点上。
  2. 然后从n/2个节点(最后一个分支点)p开始进行构建。字母顺序排列进行节点的下沉和上浮
  3. 最终构成A节点成为根节点,所以序号为1

发表于 2020-01-19 20:22:09 回复(4)
为什么不说一下是大顶堆还是小顶堆呢
发表于 2020-09-25 14:38:57 回复(0)
A是最小的,还是最大的哦?
A是最大的:大顶堆,A在堆顶,在数组中是第一个。
A是最小的:小顶堆,A在堆顶,在数组中是第一个。
发表于 2020-08-07 10:09:08 回复(0)
建立小堆,A肯定在一开始的位置
发表于 2020-03-26 08:54:16 回复(0)
题目也不说明白是最大堆还是最小堆
发表于 2020-03-06 13:23:05 回复(0)