问题
单项选择题
设有关键码序列(Ｑ, Ｇ, Ｍ, Ｚ, Ａ, Ｎ, Ｂ, Ｐ, Ｘ, Ｈ, Ｙ, Ｓ, Ｔ, Ｌ, Ｋ, Ｅ)，采用堆排序法进行排序，经过初始建堆后关键码值A在序列中的序号是( )。
A．1
B．4
C．8
D．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。