己知A[1…N]是一棵顺序存储的完全三叉树，9号结点和11号结点共同的祖先是( )。

admin2022-06-07 38

问题己知A[1…N]是一棵顺序存储的完全三叉树，9号结点和11号结点共同的祖先是( )。

选项 A、4
B、6
C、2
D、8

答案C

解析考察完全二叉树顺序存储的性质。根据顺序存储的完全二叉树子结点与父结点之间的倍数关系推导。K号结点的祖先为[k／2]，计算两个结点i，j共同的祖先算法可归结如下：
1)若i!=j，则执行2，否则寻找结束，共同父节点为i(或j)。
2)取max{i,j}执行操作(以i为例)，i=[i／2]，然后跳回1)。
根据算法即可算出答案为2，选C。

转载请注明原文地址:https://kaotiyun.com/show/0x3i777K

本试题收录于：计算机408题库学硕统考专业分类