2015年内蒙古自治区数据结构理论与实践深入
发布时间：
1、设一棵二叉树的结点结构为(LLINK,INFO,RLINK,ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。
2、数组A和B的元素分别有序，欲将两数组合并到C数组，使C仍有序，应将A和B拷贝到C，只要注意A和B数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。
voidunion(intA[],B[],C[],m,n
//整型数组A和B各有m和n个元素，前者递增有序，后者递减有序，本算法将A和B归并为递增有序的数组C。
{i=0;j=n-1;k=0;//i，j，k分别是数组A,B和C的下标，因用C描述，下标从0开始while(i=0
if(a[i]while(iwhile(j>=0c[k++]=b[j--];}算法结束
4、要求二叉树按二叉链表形式存储。15分（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。BiTreeCreat(//建立二叉树的二叉链表形式的存储结构{ElemTypex；BiTreebt;
scanf(“%d”,&x;//本题假定结点数据域为整型if(x==0bt=null;elseif(x>0
{bt=(BiNode*malloc(sizeof(BiNode;
bt->data=x;bt->lchild=creat(;bt->rchild=creat(;}
elseerror(“输入错误”；return(bt;}//结束BiTree
intJudgeComplete(BiTreebt//判断二叉树是否是完全二叉树,如是，返回1，否则，返回0
{inttag=0;BiTreep=bt,Q[];//Q是队列，元素是二叉树结点指针，容量足够大if(p==nullreturn(1;
QueueInit(Q;QueueIn(Q,p;//初始化队列，根结点指针入队while(!QueueEmpty(Q
{p=QueueOut(Q;//出队
if(p->lchild&&!tagQueueIn(Q,p->lchild;//左子女入队
else{if(p->lchildreturn0;//前边已有结点为空，本结点不空elsetag=1;//首次出现结点为空if(p->rchild&&!tagQueueIn(Q,p->rchild;//右子女入队elseif(p->rchildreturn0;elsetag=1;}//while
return1;}//JudgeComplete
3、我们用l代表最长平台的长度，用k指示最长平台在数组b中的起始位置（下标）。用j
记住局部平台的起始位置，用i指示扫描b数组的下标，i从0开始，依次和后续元素比较，若局部平台长度（i-j）大于l时，则修改最长平台的长度k（l=i-j）和其在b中的起始位置（k=j），直到b数组结束，l即为所求。voidPlatform(intb[],intN
//求具有N个元素的整型数组b中最长平台的长度。{l=1;k=0;j=0;i=0;while(i
{while(i
if(i-j+1>l{l=i-j+1;k=j;}//局部最长平台i++;j=i;}//新平台起点
printf(“最长平台长度%d，在b数组中起始下标为%d”，l，k；}//Platform
