2013河南省数据结构考试入门

发布于:2021-11-27 12:25:51

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

2、假设以 I 和 O 分别表示入栈和出栈操作。栈的初态和终态均为空, 入栈和出栈的操作序列可表示为仅由 I 和 O 组成的序列,称可以操作的序列为合法序列,否 则称为非法序列。 (15 分)

(1)下面所示的序列中哪些是合法的?

A. IOIIOIOO

B. IOOIOIIO

C. IIIOIOIO

D. IIIOOIOO

(2) 通过对 (1) 的分析, 写出一个算法, 判定所给的操作序列是否合法。 若合法, 返回 true, 否则返回 false(假定被判定的操作序列已存入一维数组中) 。

3、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采 用后序非递归算法,栈中存放二叉树结点的指针,当访问到某结点时,栈中所有元素均为该 结点的祖先。本题要找 p 和 q 的最*共同祖先结点 r ,不失一般性,设 p 在 q 的左边。后序 遍历必然先遍历到结点 p,栈中元素均为 p 的祖先。将栈拷入另一辅助栈中。再继续遍历到 结点 q 时,将栈中元素从栈顶开始逐个到辅助栈中去匹配,第一个匹配(即相等)的元素就 是结点 p 和 q 的最*公共祖先。

typedef struct

{BiTree t;int tag;//tag=0 表示结点的左子女已被访问,tag=1 表 示结点的右子女已被访问

}stack;

stack s[],s1[];//栈,容量够大

BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉树上结点 p 和 q 的最 *的共同祖先结点 r。 {top=0; bt=ROOT;

while(bt!=null ||top>0)

{while(bt!=null //结点入栈

&&

bt!=p

&&

bt!=q)

{s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} //沿左分枝向 下

if(bt==p) //不失一般性,假定 p 在 q 的左侧,遇结点 p 时,栈中元 素均为 p 的祖先结点 {for(i=1;i<=top;i++) s1[i]=s[i]; top1=top; }//将栈 s 的元素 转入辅助栈 s1 保存 if(bt==q) //找到 q 结点。

for(i=top;i>0;i--)//;将栈中元素的树结点到 s1 去匹配

{pp=s[i].t;

for (j=top1;j>0;j--)

if(s1[j].t==pp) {printf(“p 和 q 的最*共同的祖先已找到”); return (pp);} }

while(top!=0 && s[top].tag==1) top--;

//退栈

if (top!=0){s[top].tag=1;bt=s[top].t->rchild;} //沿右分 枝向下遍历

}//结束 while(bt!=null ||top>0)

return(null);//q、p 无公共祖先

}//结束 Ancestor

4、 我们用 l 代表最长*台的长度, 用 k 指示最长*台在数组 b 中的起 始位置(下标) 。用 j 记住局部*台的起始位置,用 i 指示扫描 b 数组的下标,i 从 0 开始, 依次和后续元素比较,若局部*台长度(i-j)大于 l 时,则修改最长*台的长度 k(l=i-j) 和其在 b 中的起始位


相关推荐

最新更新

猜你喜欢