2. 计算机
  3. 设有关键码序列(Q，G，M，Z，A，N，P，X，H)，下面(44)是从上述序列出发建堆的结果。

设有关键码序列(Q，G，M，Z，A，N，P，X，H)，下面(44)是从上述序列出发建堆的结果。

admin2010-01-17  43
问题 设有关键码序列(Q，G，M，Z，A，N，P，X，H)，下面(44)是从上述序列出发建堆的结果。
选项 A、H，G，M，P，A，N，Q，X，Z
B、G，M，Q，A，N，P，X，H，Z
C、A，G，M，H，Q，N，P，X，Z
D、A，G，H，M，N，P，Q，X，Z
答案C
解析 本题考查建堆的过程。从一个无序序列建堆的过程是一个反复“筛选”的过程。若将此序列看成是一个完全二叉树，则最后一个非终端结点是第|n/2|，因此“筛选”只需要从这个元素开始就可以了。关键码序列(Q，G，M，Z，A，N，P，X，H)的|n/2|等于4，对应的元素是Z，根据与这个关键码序列对应的完全二叉树可以知道，Z＞H，则交换。接着是对第3个元素M进行“筛选”，由于它不大于其左、右孩子结点的值，则筛选后序列不变。再接下来是对第2个元素G进行“筛选”，由于它大于右孩子结点A的值，则交换。最后是对第1个元素Q进行“筛选”，它此时大于其左孩子结点A的值，则交换之，后又大于其右孩子结点G的值，再交换后得到建堆的结果是(A，G，M，H，Q，N，P，X，Z)。
转载请注明原文地址:https://kaotiyun.com/show/2YjZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

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