计算机三级
设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建堆的结果?( )A．a，g，h，m，n，p，q，x，zB．a，S，m，h，q，n，p，x，zC．g，m，q，a，n，p，x，h，zD．h，g，m，p，a，n，q，x，z
题目
设有关键码序列(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
相似问题和答案
第1题：
B.A，G，M，H，Q，N，P，X，Z
C.G，M，Q，A，N，P，X，H，Z
D.H，0，M，P，A，N，Q.X.Z
第2题：
下列哪一个关键码序列不符合堆的定义?
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
解析：根据堆的定义：堆是一个关键码序列(K1，K2，……Kn)，它具有特征Ki≤K2i，Ki≤K2i+1，i=1，2，……，[n/2]根据这个特征，可知C选项不符合堆的定义：
第3题：
设有关键码序列(Q，G，M，Z，A，N，B，P，X，H，Y，S，T，L，K，E)，采用二路归并排序法进行排序，下面哪一个序列是第二趟归并后的结果?
A．G，Q，M，Z，A，N，B，P，H，X，S，Y，L，T，E，K
B．G，M，Q，Z，A，B，N，P，H，S，X，Y，E，K，L，T
C．G，M，Q，A，N，B，P，X，H，Y，S，T，L，K，E，Z
D．A，B，G，M，N，P，Q，Z，E，H，K，L，S，T，X，Y
解析：初始状态没有部分排序的文件中若有n个记录，可以把它看作n个子文件，每个子文件中只包含一个记录，因而是部分排序的。通常先将两个子文件归并，得到n/2个部分排序的较大的子文件，每个子文件中只包含2个记录。再将这些子文件归并，如此反复，直到归并到一个文件中，排序完成。上述每步归并都是将两个子文件合成一个文件，这种做法叫“二路归并排序”。按照上述指导思想，第一趟归并后为(G，Q，M，Z，A，N，B，P，H，X，S，Y，L，T，E，K)，第二趟归并后的结果为(G，Q，M，Z，A，N，B，P，H，X，S，Y，L，T，E，K)。所以本题正确答案为选项B。
第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
解析：本题考查建堆的过程。从一个无序序列建堆的过程是一个反复“筛选”的过程。若将此序列看成是一个完全二叉树，则最后一个非终端结点是第|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、0、R
C．A、D、P、R、C、Q、X、M、H、G
D．A、D、C、M、P、G、H、X、R、Q
解析：本题的解题思路是检查每个双亲节点与它的子女节点间是否满足堆的定义。如果双亲节点的位置为i,则子女位置分别为2i-1和2i。在选项C中，C是D的子女，但小于双亲节点D，这与小根堆的要求不符，所以C是错的。
第6题：
设有关键码序为(Q,G,M,Z,A,N,B,P,X,H,Y,S,T,L,K,E)，采用二路归并排序法进行排序，下面哪一个序列是第二趟归并后的结果？
A．G,Q,M,Z,A,N,B,P,H,X,S,Y,L,T,E,K
B．G,M,Q,Z,A,B,N,P,H,S,X,Y,E,K,L,T
C．G,M,Q,A,N,B,P,X,H,Y,S,T,L,K,E,Z
D．A,B,G,M,N,P,Q,Z,E,H,K,L,S,T,X,Y
解析：对于关键码序列[Q][G][M][Z][A][N][B][P][X][H][Y][S][T][L][K][E]第一趟：[G Q][M Z][A N][B P][H X][S Y][L T][K E]第二趟：[G M Q Z][A B N P][H S T Y][E K L T]
第7题：
设有关键码序列(Q ，G，M，Z，A，N，B，P，X，H ，Y，S，L，T，K，E)，采用二路归并排序法进行排序，下面哪一个序列是第二趟归并后的结果？
A．G，Q，M，Z，A，N，B，P，H，X，S，Y，L，T，E，K
B．G，M，Q，Z，A，B，N，P，H，S，X，Y，E，K，L，T
C．G，M，Q，A，N，B，P，X，H，Y，S，T，L，K，E，Z
D．A，B，G，M，N，P，Q，Z，E，H，K，L，S，T，X，Y
第8题：
设有关键码序列(Q, G, M, Z, A, N, B, P, X, H, Y, S, T, L, K, E)，采用二路归并排序法进行排序，下面哪一个序列是第二趟归并后的结果?( )
A) G, Q, M, Z, A, N, B, P, H, X, S, Y, L, T, B, K
B) G, M, Q, Z, A, B, N, P, H, S, X, Y, E, K, L, T
C) G, M, Q, A, N, B, P, X, H, Y, S, T, L, K, E, Z
D) A, B, G, M, N, P, Q, Z, E, H, K, L, S, T, X, Y
A．
B．
C．
D．
第9题：
设有关键码序为（Q,G,M,Z,A,N,B,P,X,H,Y,S,T,L,K,E），采用二路归并排序法进行排序，下面哪一个序列是第二趟归并后的结果？
A．G,Q,M,Z,A,N,B,P,H,X,S,Y,L,T,E,K
B．G,M,Q,Z,A,B,N,P,H,S,X,Y,E,K,L,T
C．G,M,Q,A,N,B,P,X,H,Y,S,T,L,K,E,Z
D．A,B,G,M,N,P,Q,Z,E,H,K,L,S,T,X,Y