1、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。

2、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。

当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。

设当n=m-1时结论成立，现证明当n=m时结论成立。

设中序序列为S1，S2， ，Sm,后序序列是P1,P2, ，Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2， ，Si-1是左子树的中序序列，而Si+1,Si+2, ,Sm是右子树的中序序列。

若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2，S3， ，Sm}和{P1，P2， ，Pm-1}可以唯一确定右子树，从而也确定了二叉树。

若i=m,则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1，S2， ，Sm-1}和{P1，P2， ，Pm-1}唯一确定左子树，从而也确定了二叉树。

最后，当1<i<m时，Si把中序序列分成{S1，S2， ，Si-1}和{Si+1,Si+2, ，Sm}。由于后序遍历是“左子树—右子树—根结点”，所以{P1,P2, ,Pi-1}和{Pi,Pi+1, Pm-1}是二叉树的左子树和右子树的后序遍历序列。因而由{S1，S2， ，Si-1}和{P1，P2， ，Pi-1} 可唯一确定二叉树的左子树，由{Si+1,Si+2, ，Sm}和

{Pi,Pi+1, ，Pm-1}可唯一确定二叉树的右子树。

3、设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。

4、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。

当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。

设当n=m-1时结论成立，现证明当n=m时结论成立。

设中序序列为S1，S2， ，Sm,后序序列是P1,P2, ，Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2， ，Si-1是左子树的中序序列，而Si+1,Si+2, ,Sm是右子树的中序序列。

若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2，S3， ，Sm}和{P1，P2， ，Pm-1}可以唯一确定右子树，从而也确定了二叉树。

若i=m,则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1，S2， ，Sm-1}和{P1，P2， ，Pm-1}唯一确定左子树，从而也确定了二叉树。

最后，当1<i<m时，Si把中序序列分成{S1，S2， ，Si-1}和{Si+1,Si+2, ，Sm}。由于后序遍历是“左子树—右子树—根结点”，所以{P1,P2, ,Pi-1}和{Pi,Pi+1, Pm-1}是二叉树的左子树和右子树的后序遍历序列。因而由{S1，S2， ，Si-1}和{P1，P2， ，Pi-1} 可唯一确定二叉树的左子树，由{Si+1,Si+2, ，Sm}和

{Pi,Pi+1, ，Pm-1}可唯一确定二叉树的右子树。

5、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>} 写出G的拓扑排序的结果。

G拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V7