一棵树的存储结构可以采用父结点表示法，即父指针数组表示法。试给出相应的类定义。其中，每个树

父结点指针数组的最大结点个数。树中各个结点按先根遍历次序存放，根结点存于parent[0].试编写一个函数，计算p厨指结点和q所指结点的最近公共祖先结点。

设一棵树的存储表示为父指针数组表示（双亲表示)，编写一个算法计算树的深度。

的指针，用data存储结点的值。如果我们采用静态二叉链表作为森林的存储表示，同时按森林的先根次序依次安放森林的所有结点，则可以在它们的结点中用只有一个二进位的标志Itag代替Ilink，用rtag代替rlink。并设定若Itag=0，则该结点没有子女，若Itag≠0.则该结点有子女;若rtag=0，则该结点没有下一个兄弟，若rtag不等于0.则该结点有下一个兄弟。试给出这种表示的结构定义，并设计一个算法，将用这种表示存储的森林转换成用Ilink-rIlink表示的森林。

设以二元组（f，c)的形式输人一棵树的各条边（其中f是父结点的标识，c是子女结点的标识)，且在输人

的二元组序列中，c是按层次顺序出现的，时，c为根结点的标识，若c也为^'，则表示输人结束。例如图5-27所示树的输人序列为：^A，AB，AC，AD，CE，CF，^^.编写一个算法，由输入的二元组序列建立树的子女兄弟链表。

链式存储的存储结构所占存储空间（)。

A.分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针

B.只有一部分，存放结点的值

C.只有一部分，存储表示结点间关系的指针

D.分两部分，一部分存放结点的值，另一部分存放结点所占单元素

用顺序存储的方法，将有n个结点的完全二叉树中所有结点按层逐个顺序存放在一维数组R[n]中，若结点R[i]有双亲（即父结点)，则其双亲是（);该树中编号最大的非叶结点是（)。

A、R[(i-1)/2]

B、R[i/2]

C、R[n/2-1]

D、R[n/2]