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