2010吉林省学习数据库加强

1、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。设当n=m-1时结论成立，现证明当n=m时结论成立。设中序序列为S1，S2，…，Sm,后序序列是P1,P2,…，Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，…，Si-1是左子树的中序序列，而Si+1,Si+2,…,Sm是右子树的中序序列。若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2，S3，…，Sm}和{P1，P2，…，Pm-1}可以唯一确定右子树，从而也确定了二叉树。若i=m,则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1，S2，…，Sm-1}和{P1，P2，…，Pm-1}唯一确定左子树，从而也确定了二叉树。最后，当1<i<m时，Si把中序序列分成{S1，S2，…，Si-1}和{Si+1,Si+2,…，Sm}。由于后序遍历是“左子树—右子树—根结点”，所以{P1,P2,…,Pi-1}和{Pi,Pi+1,…Pm-1}是二叉树的左子树和右子树的后序遍历序列。因而由{S1，S2，…，Si-1}和{P1，P2，…，Pi-1}可唯一确定二叉树的左子树，由{Si+1,Si+2,…，Sm}和{Pi,Pi+1,…，Pm-1}可唯一确定二叉树的右子树。2、设一棵二叉树的结点结构为(LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。3、二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部（注:向量d可视为循环表），其原则为，先将r[l]赋给d[1]，再从r[2]记录开始分二路插入。编写实现二路插入排序算法。4、4、 voidLinkList_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_reverse5、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15分）（1）下面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。6、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注：圈就是回路。7、连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。voidSpnTree(AdjListg)//用“破圈法”求解带权连通无向图的一棵最小代价生成树。{typedefstruct{inti,j,w}node;//设顶点信息就是顶点编号，权是整型数nodeedge[];scanf("%d%d",&e,&n);//输入边数和顶点数。for(i=1;i<=e;i++)//输入e条边：顶点，权值。scanf("%d%d%d",&edge[i].i,&edge[i].j,&edge[i].w);for(i=2;i<=e;i++)//按边上的权值大小，对边进行逆序排序。{edge[0]=edge[i];j=i-1;while(edge[j].w<edge[0].w)edge[j+1]=edge[j--];edge[j+1]=edge[0];}//fork=1;eg=e;while(eg>=n)//破圈，直到边数e=n-1.{if(connect(k))//删除第k条边若仍连通。{edge[k].w=0;eg--;}//测试下一条边edge[k]，权值置0表示该边被删除k++;//下条边}//while}//算法结束。connect()是测试图是否连通的函数，可用图的遍历实现，8、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15分）（1）A和D是合法序列，B和C是非法序列。（2）设被判定的操作序列已存入一维数组A中。intJudge(charA[])//判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返回false。{i=0;//i为下标。j=k=0;//j和k分别为I和字母O的的个数。while(A[i]!=‘\0’)//当未到字符数组尾就作。{switch(A[i]){case‘I’:j++;break;//入栈次数增1。case‘O’:k++;if(k>j){printf(“序列非法\n”)；exit(0);}}i++;//不论A[i]是‘I’或‘O’，指针i均后移。}if(j!=k){printf(“序列非法\n”)；return(false);}15、数组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<m&&j>=0)if(a[i]<b[j])c[k++]=a[i++]elsec[k++]=b[j--];while(i<m)c[k++]=a[i++];while(j>=0)c[k++]=b[j--];}算法结束4、要求二叉树按二叉链表形式存储。15分（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。BiTreeCreat()//建立二叉树的二叉链表形式的存储结构{ElemTypex；BiTreebt;scanf(“%d”,&x);//本题假定结点数据域为整型if(x==0)bt=null;elseif(x>0){bt=(BiNode*)malloc(sizeof(BiNode));bt->data=x;bt->lchild=creat();bt->rchild=creat();}elseerror(“输入错误”)；return(bt);}//结束BiTreeintJudgeComplete(BiTreebt)//判断二叉树是否是完全二叉树,如是，返回1，否则，返回0{inttag=0;BiTreep=bt,Q[];//Q是队列，元素是二叉树结点指针，容量足够大if(p==null)return(1);QueueInit(Q);QueueIn(Q,p);//初始化队列，根结点指针入队while(!QueueEmpty(Q)){p=QueueOut(Q);//出队if(p->lchild&&!tag)QueueIn(Q,p->lchild);//左子女入队else{if(p->lchild)return0;//