2011河南省数据库入门基础

1、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根”。确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右”三部分。若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中只有左子树或只有右子树，则在层次序列的根结点后也只有左子树的根或右子树的根。这样，定义一个全局变量指针R，指向层次序列待处理元素。算法中先处理根结点，将根结点和左右子女的信息入队列。然后，在队列不空的条件下，循环处理二叉树的结点。队列中元素的数据结构定义如下：

typedef struct

{ int lvl;         //层次序列指针，总是指向当前“根结点”在层次序列中的位置

int l,h;         //中序序列的下上界

int f;           //层次序列中当前“根结点”的双亲结点的指针

int lr;          // 1—双亲的左子树  2—双亲的右子树

}qnode; 

  BiTree Creat(datatype in[],level[],int n)

//由二叉树的层次序列level[n]和中序序列in[n]生成二叉树。 n是二叉树的结点数

{if (n<1) {printf(“参数错误\\n”); exit(0);}

qnode s,Q[];       //Q是元素为qnode类型的队列，容量足够大

 init(Q); int R=0;  //R是层次序列指针，指向当前待处理的结点

 BiTree p=(BiTree)malloc(sizeof(BiNode));          //生成根结点

p->data=level[0]; p->lchild=null; p->rchild=null; //填写该结点数据

for (i=0; i   if (in[i]==level[0]) break;

if (i==0)  //根结点无左子树，遍历序列的1—n-1是右子树

{p->lchild=null;

s.lvl=++R; s.l=i+1; s.h=n-1; s.f=p; s.lr=2;  enqueue(Q,s);

 }

else if (i==n-1) //根结点无右子树，遍历序列的1—n-1是左子树

{p->rchild=null;

    s.lvl=++R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);

 }

     else   //根结点有左子树和右子树

{s.lvl=++R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);//左子树有关信息入队列

s.lvl=++R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(Q,s);//右子树有关信息入队列

}

while (!empty(Q))  //当队列不空，进行循环，构造二叉树的左右子树

 { s=delqueue(Q); father=s.f;

for (i=s.l; i<=s.h; i++)

 if (in[i]==level[s.lvl]) break;

p=(bitreptr)malloc(sizeof(binode));                    //申请结点空间

p->data=level[s.lvl]; p->lchild=null; p->rchild=null;   //填写该结点数据

if (s.lr==1) father->lchild=p;

else father->rchild=p； //让双亲的子女指针指向该结点

   if (i==s.l)

{p->lchild=null; //处理无左子女

s.lvl=++R; s.l=i+1; s.f=p; s.lr=2;  enqueue(Q,s); 

}

   else if (i==s.h)

{p->rchild=null; //处理无右子女

              s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); 

}

        else{s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);//左子树有关信息入队列

       s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); //右子树有关信息入队列

}

   }//结束while (!empty(Q))

return(p);

}//算法结束

2、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相应的行中各元素也必须做相应变动。

void Translation（float *matrix，int n）

//本算法对n×n的矩阵matrix，通过行变换，使其各行元素的平均值按递增排列。

{int i,j,k,l；

float sum，min；     //sum暂存各行元素之和  

float *p, *pi, *pk;

for(i=0; i  {sum=0.0; pk=matrix+i*n;  //pk指向矩阵各行第1个元素.

for (j=0; j*(p+i)=sum;           //将一行元素之和存入一维数组.

      }//for i

for(i=0; i   {min=*(p+i); k=i;     //初始设第i行元素之和最小.

for(j=i+1;jif(i!=k)            //若最小行不是当前行,要进行交换(行元素及行元素之和)

  {pk=matrix+n*k;   //pk指向第k行第1个元素.

   pi=matrix+n*i;   //pi指向第i行第1个元素.

for(j=0;j     {sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum;}

   sum=p[i]; p[i]=p[k]; p[k]=sum;  //交换一维数组中元素之和.

  }//if

}//for i

  free(p); //释放p数组.

}// Translation

[算法分析] 算法中使用选择法排序,比较次数较多,但数据交换(移动)较少.若用其它排序方法,虽可减少比较次数,但数据移动会增多.算法时间复杂度为O(n2).

3、编写一个过程，对一个n×n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。

4、假设K1，…，Kn是n个关键词，试解答：

试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，Kn时，用算法建立一棵以LLINK / RLINK 链接表示的二叉查找树。

5、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。

6、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根”。确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右”三部分。若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中只有左子树或只有右子树，则在层次序列的根结点后也只有左子树的根或右子树的根。这样，定义一个全局变量指针R，指向层次序列待处理元素。算法中先处理根结点，将根结点和左右子女的信息入队列。然后，在队列不空的条件下，循环处理二叉树的结点。队列中元素的数据结构定义如下：

typedef struct

{ int lvl;         //层次序列指针，总是指向当前“根结点”在层次序列中的位置

int l,h;         //中序序列的下上界

int f;           //层次序列中当前“根结点”的双亲结点的指针

int lr;          // 1—双亲的左子树  2—双亲的右子树

}qnode; 

  BiTree Creat(datatype in[],level[],int n)

//由二叉树的层次序列level[n]和中序序列in[n]生成二叉树。 n是二叉树的结点数

{if (n<1) {printf(“参数错误\\n”); exit(0);}

qnode s,Q[];       //Q是元素为qnode类型的队列，容量足够大

 init(Q); int R=0;  //R是层次序列指针，指向当前待处理的结点

 BiTree p=(BiTree)malloc(sizeof(BiNode));          //生成根结点

p->data=level[0]; p->lchild=null; p->rchild=null; //填写该结点数据

for (i=0; i   if (in[i]==level[0]) break;

if (i==0)  //根结点无左子树，遍历序列的1—n-1是右子树

{p->lchild=null;

s.lvl=++R; s.l=i+1; s.h=n-1; s.f=p; s.lr=2;  enqueue(Q,s);

 }

else if (i==n-1) //根结点无右子树，遍历序列的1—n-1是左子树

{p->rchild=null;

    s.lvl=++R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);

 }

     else   //根结点有左子树和右子树

{s.lvl=++R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);//左子树有关信息入队列

s.lvl=++R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(Q,s);//右子树有关信息入队列

}

while (!empty(Q))  //当队列不空，进行循环，构造二叉树的左右子树

 { s=delqueue(Q); father=s.f;

for (i=s.l; i<=s.h; i++)

 if (in[i]==level[s.lvl]) break;

p=(bitreptr)malloc(sizeof(binode));                    //申请结点空间

p->data=level[s.lvl]; p->lchild=null; p->rchild=null; //填写该结点数据

if (s.lr==1) father->lchild=p;

 else father->rchild=p； //让双亲的子女指针指向该结点

   if (i==s.l)

{p->lchild=null; //处理无左子女

s.lvl=++R; s.l=i+1; s.f=p; s.lr=2;  enqueue(Q,s); 

}

   else if (i==s.h)

{p->rchild=null; //处理无右子女

              s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); 

}

        else{s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);//左子树有关信息入队列

       s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); //右子树有关信息入队列

}

   }//结束while (!empty(Q))

return(p);

}//算法结束

7、我们用l代表最长平台的长度，用k指示最长平台在数组b中的起始位置（下标）。用j记住局部平台的起始位置，用i指示扫描b数组的下标，i从0开始，依次和后续元素比较，若局部平台长度（i-j）大于l时，则修改最长平台的长度k（l=i-j）和其在b中的起始位置（k=j），直到b数组结束，l即为所求。

void Platform (int b[ ], int N)

 //求具有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

8、4、    void LinkList_reverse(Linklist &L)  

//链表的就地逆置;为简化算法,假设表长大于2        

{

p=L->next;q=p->next;s=q->next;p->next=NULL;

while(s->next)

  {

q->next=p;p=q;

q=s;s=s->next; //把L的元素逐个插入新表表头

  }

q->next=p;s->next=q;L->next=s;

}//LinkList_reverse

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

29. ① 试找出满足下列条件的二叉树

1）先序序列与后序序列相同  2）中序序列与后序序列相同

3）先序序列与中序序列相同  4）中序序列与层次遍历序列相同