《2012河南省数据库入门深入》由会员分享，可在线阅读，更多相关《2012河南省数据库入门深入（6页珍藏版）》请在金锄头文库上搜索。
1、1、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。void PreToPost(ElemType pre ,post,int l1,h1,l2,h2)/将满二叉树的先序序列转为后序序列，l1,h1,l2,h2是序列初始和最后结点的下标。if(h1=l1)posth2=prel1; /根结点half=(h1-l1)/2; /左或右子树的结点数PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1) /将
2、左子树先序序列转为后序序列PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) /将右子树先序序列转为后序序列 /PreToPost32. .叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。LinkedList head,pre=null; /全局变量LinkedList InOrder(BiTree bt)/中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为head if(bt)InO
3、rder(bt-lchild); /中序遍历左子树 if(bt-lchild=null & bt-rchild=null) /叶子结点 if(pre=null) head=bt; pre=bt; /处理第一个叶子结点 elsepre-rchild=bt; pre=bt; /将叶子结点链入链表 InOrder(bt-rchild); /中序遍历左子树 pre-rchild=null; /设置链表尾 return(head); /InOrder时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n)2、4、void LinkList_reverse(Linklist &L) /链表
4、的就地逆置;为简化算法,假设表长大于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_reverse3、本题要求建立有序的循环链表。从头到尾扫描数组A，取出Ai（0=inext=h; /形成空循环链表for(i=0;inext; while(p!=h & p-datanext; /查找Ai的插入位置 if(p=h | p-data!=Ai) /重复数据不再输入 s=(Link
5、edList)malloc(sizeof(LNode); s-data=Ai; pre-next=s; s-next=p;/将结点s链入链表中/for return(h);算法结束4、两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。 int Similar(BiTree p,q) /判断二叉树p和q是否相似 if(p=null & q=null) return (1);else if(!p & q | p & !q) return (0); else return(Similar(p-lchild,q-lchild) & Similar(p-rchild
6、,q-rchild)/结束Similar5、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。void PreToPost(ElemType pre ,post,int l1,h1,l2,h2)/将满二叉树的先序序列转为后序序列，l1,h1,l2,h2是序列初始和最后结点的下标。if(h1=l1)posth2=prel1; /根结点half=(h1-l1)/2; /左或右子树的结点数PreToPost(pre,post,l1+1,l1+h
7、alf,l2,l2+half-1) /将左子树先序序列转为后序序列PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) /将右子树先序序列转为后序序列 /PreToPost32. .叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。LinkedList head,pre=null; /全局变量LinkedList InOrder(BiTree bt)/中序遍历二叉树bt，将叶子结点从左到右链成一个单链表
8、，表头指针为head if(bt)InOrder(bt-lchild); /中序遍历左子树 if(bt-lchild=null & bt-rchild=null) /叶子结点 if(pre=null) head=bt; pre=bt; /处理第一个叶子结点 elsepre-rchild=bt; pre=bt; /将叶子结点链入链表 InOrder(bt-rchild); /中序遍历左子树 pre-rchild=null; /设置链表尾 return(head); /InOrder时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n)6、#define maxsize 栈空间容
9、量 void InOutS(int smaxsize) /s是元素为整数的栈，本算法进行入栈和退栈操作。 int top=0; /top为栈顶指针，定义top=0时为栈空。 for(i=1; i=n; i+) /n个整数序列作处理。 scanf(“%d”,&x); /从键盘读入整数序列。 if(x!=-1) / 读入的整数不等于-1时入栈。 if(top=maxsize-1)printf(“栈满n”);exit(0);else s+top=x; /x入栈。 else /读入的整数等于-1时退栈。 if(top=0)printf(“栈空n”);exit(0); else printf(“出栈元素
10、是%dn”,stop-)； /算法结7、编写一个过程，对一个nn矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。8、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧）有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0，1，2表示这三种状态。前面已提到，若dfs（v）结束前出现顶点u到v的回边，则图中必有包含顶点v和u的回路。对应程序中v的状态为1，而u是正访问的顶点，若我们找出u的下一邻
11、接点的状态为1，就可以输出回路了。void Print(int v,int start ) /输出从顶点start开始的回路。for(i=1;i=n;i+) if(gvi!=0 & visitedi=1 ) /若存在边（v,i），且顶点i的状态为1。 printf(“%d”,v); if(i=start) printf(“n”); else Print(i,start);break;/if /Printvoid dfs(int v) visitedv=1;for(j=1;j=n;j+ ) if (gvj!=0) /存在边(v,j) if (visitedj!=1) if (!visitedj)
12、 dfs(j); /if else cycle=1; Print(j,j); visitedv=2;/dfsvoid find_cycle() /判断是否有回路，有则输出邻接矩阵。visited数组为全局变量。 for (i=1;i=n;i+) visitedi=0; for (i=1;i=n;i+ ) if (!visitedi) dfs(i);/find_cycle9、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15分） （1）A和D是合法序列，B和C 是非法序列。 （2）设被判定的操作序列已存入一维数组A中。 int Judge(char A) /判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返回false。 i=0; /i为下标。 j=k=0;
