2023年广东省数据总结深入

1、设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。

2、二部图（bipartite graph） g=（v，e）是一个能将其结点集v分为两不相交子集v 1和v2=v-v1的无向图，使得：v1中的任何两个结点在图g中均不相邻，v2中的任何结点在图g中也均不相邻。

1）．请各举一个结点个数为5的二部图和非二部图的例子。

2）．请用c或pascal编写一个函数bipartite判断一个连通无向图g是否是二部图，并分析程序的时间复杂度。设g用二维数组a来表示，大小为n*n（n为结点个数）。请在程序中加必要的注释。

若有必要可直接利用堆栈或队列操作。【

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。 /沿左分枝向下。

if(bt==p) /不失一般性，假定p在q的左侧，遇结点p时，栈中元素均为p的祖先结点//将栈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)

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);/p无公共祖先。

//结束ancestor