下列________关键码序列不符合堆的定义。A．A、C、D、G、H、M、P、Q、R、XB．A、C、M、D、H、P、X、G、Q、RC．A、D、P、R、C、Q、X、M、H、GD．A、D、C、G、P、H、M、Q、R、X
题目
下列________关键码序列不符合堆的定义。
A．A、C、D、G、H、M、P、Q、R、X
B．A、C、M、D、H、P、X、G、Q、R
C．A、D、P、R、C、Q、X、M、H、G
D．A、D、C、G、P、H、M、Q、R、X
相似考题
参考答案和解析
解析：若一棵完全二叉树中任一非叶子结点的关键字都不大于（或不小于）其左、右孩子结点的值，则层次遍历此二叉树就可以得到一个堆序列。堆的特点是：堆顶元素（或完全二叉树的根）必为序列中所有元素的最大者(或最小者)。C选项中所构成的二叉树为：
由于D＞C，不符合堆的定义。
更多“下列________关键码序列不符合堆的定义。A.A、C、D、G、H、M、P、Q、R、XB.A、C、M、D、H、P、X、G、Q、RC.A、D、P、R、C ”相关问题
-
第1题：
下列关键码序列不符合堆定义的是( )。
A．A、C、D、G、H、M、P、Q、R、X
B．A、C、M、D、H、P、X、G、Q、R
C．A、D、P、R、C、Q、X、M、H、G
D．A、D、C、G、P、H、M、Q、R、X
正确答案：C
解析：根据堆的定义：堆是一个关键码序列(K1,K2,……Kn)，它具有如下特征：Ki≤K2i，Ki≤K2i+1，i=1，2，……，[n/2]堆实质上是一棵完全二叉树结点的层次序列，此完全二叉树的每个结点对应于一个关键码，根结点对应于关键码K1。堆的特性在此完全二叉树里解释为：完全二叉树中任一结点的关键码值都小于或等于它的两个子女结点的关键码值。根据这个特征，选项C)中的K2>K5(即D>C)、K4>K8(即R>M)、K4>K9(即R>H)，因此选项C)不符合堆的定义。 -
第2题：
设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建堆的结果?( )
A．a，g，h，m，n，p，q，x，z
B．a，S，m，h，q，n，p，x，z
C．g，m，q，a，n，p，x，h，z
D．h，g，m，p，a，n，q，x，z
正确答案：B
解析：堆的定义是对每个层次的树(子树)都存在双亲节点小于(大于)其子女节点。因此要么是小根堆，要么是大根堆，小根堆堆顶元素肯定是a，大根堆堆顶元素肯定是z，因此首先可以排除C和D选项。对A、B如果是堆，肯定是小根堆。再根据建初堆后，进行筛运算的结果可得应为B。 -
第3题：
（14）下列哪一个关键码序列不符合堆的定义？
A）A、C、D、G、H、M、P、Q、R、X
B）A、C、M、D、H、P、X、G、Q、R
C ) A、D、P、R、C、Q、X、M、H、G
D）A、 D、 C、 G、 P、H、 M、 Q、 R、 X
正确答案：C
-
第4题：
设有关键码序列(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)。 -
第5题：
下列哪一个关键码序列不符合堆的定义?
A．A、C、D、G、H、M、P、Q、R、X
B．A、C、M、D、H、P、X、G、Q、R
C．A、D、P、R、C、Q、X、M、H、G
D．A、D、C、G、P、H、M、Q、R、X
正确答案：C
解析：根据堆的定义：堆是一个关键码序列(K1，K2，……Kn)，它具有特征Ki≤K2i，Ki≤K2i+1，i=1，2，……，[n/2]根据这个特征，可知C选项不符合堆的定义：