2012年宁夏回族自治区数据库入门要领
发布时间：
1、数组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
2、二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根”。确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右”三部分。若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中只有左子树或只有右子树，则在层次序列的根结点后也只有左子树的根或右子树的根。
这样，定义一个全局变量指针R，指向层次序列待处理元素。算法中先处理根结点，将根结点和左右子女的信息入队列。然后，在队列不空的条件下，循环处理二叉树的结点。队列中元素的数据结构定义如下：typedefstruct
{intlvl;//层次序列指针，总是指向当前“根结点”在层次序列中的位置intl,h;//中序序列的下上界
intf;//层次序列中当前“根结点”的双亲结点的指针intlr;//1—双亲的左子树2—双亲的右子树}qnode;
BiTreeCreat(datatypein[],level[],intn
//由二叉树的层次序列level[n]和中序序列in[n]生成二叉树。n是二叉树的结点数{if(n<1{printf(“参数错误\n”;exit(0;}
qnodes,Q[];//Q是元素为qnode类型的队列，容量足够大init(Q;intR=0;//R是层次序列指针，指向当前待处理的结点BiTreep=(BiTreemalloc(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;}
elseif(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;//右子树有关信息入队列}
