1、设一棵二叉树的结点结构为(LLINK,INFO,RLINK,ROOT为指向该二叉树根结点的指针,p和q分别为指向该二叉树中任意两个结点的指针,试编写一算法ANCESTOR(ROOT,p,q,r),该算法找到p和q的最近共同祖先结点r。
2、两棵空二叉树或仅有根结点的二叉树相似;对非空二叉树,可判左右子树是否相似,采用递归算法。
intSimilar(BiTreep,q//判断二叉树p和q是否相似{if(p==null&&q==nullreturn(1;elseif(!p&&q||p&&!qreturn(0;
elsereturn(Similar(p->lchild,q->lchild&&Similar(p->rchild,q->rchild}//结束Similar
3、约瑟夫环问题(Josephus问题)是指编号为1、2、„,n的n(n>0)个人按顺时针方向围坐成一圈,现从第s个人开始按顺时针方向报数,数到第m个人出列,然后从出列的下一个人重新开始报数,数到第m的人又出列,„,如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法,模拟此过程。
4、二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部(注:向量d可视为循环表),其原则为,先将r[l]赋给d[1],再从r[2]记录开始分二路插入。编写实现二路插入排序算法。
5、设一棵二叉树的结点结构为(LLINK,INFO,RLINK,ROOT为指向该二叉树根结点的指针,p和q分别为指向该二叉树中任意两个结点的指针,试编写一算法ANCESTOR(ROOT,p,q,r),该算法找到p和q的最近共同祖先结点r。
6、证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。29.①试找出满足下列条件的二叉树
1)先序序列与后序序列相同2)中序序列与后序序列相同
3)先序序列与中序序列相同4)中序序列与层次遍历序列相同
7、给出折半查找的递归算法,并给出算法时间复杂度性分析。
8、证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。当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时,Si把中序序列分成{S1,S2,„,Si-1}和{Si+1,Si+2,„,Sm}。由于后序遍历是“左子树—右子树—根结点”,所以{P1,P2,„,Pi-1}