2012河南省数据库入门深入

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) /PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) / /PreToPost32. . 叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针 pre ，初始为空。第一个叶子结点由指针head 指向，遍历到叶子结点时，就将它前驱的 rchild 指针指向它，最后叶子结点的 rchil

2、d 为空。LinkedList head,pre=null; / 全局变量LinkedList InOrder(BiTree bt)/ 中序遍历二叉树bt ，将叶子结点从左到右链成一个单链表，表头指针为 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) 2 、 4、 void LinkList_reverse(Linklist &L)/ 链表的就地逆置; 为简化算法, 假设表长大于2p=L-next;q=p-next;s=q-next;p-next=NULL;while(s-next)q-next=p

3、;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=(LinkedList)malloc(sizeof(LNode);s-data=Ai; pre-next=s; s-next=p;/将结点 s 链入链表中/forreturn(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-l

4、child) & Similar(p-rchild,q-rchild)/ 结束 Similar 5、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满 二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为 另一遍历序列(即任一遍历序列均可确定一棵二叉树)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) /将左子树先序序列转为后序序列将右子树先序序列转为后序序列PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) / /PreToPost32. . 叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针 pre始为空。第一个叶子结点由指针head 指

5、向，遍历到叶子结点时，就将它前驱的 rchild指向它，最后叶子结点的 rchild 为空。LinkedList head,pre=null; / 全局变量LinkedList InOrder(BiTree bt)采用，初指针/ 中序遍历二叉树bt ，将叶子结点从左到右链成一个单链表，表头指针为 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 栈空间容量本算法进行入栈和退栈操作。为栈顶指针，定义top=0 时为栈空。个整数序列作处理。从键盘读入整数序列。读入

6、的整数不等于-1 时入栈。“栈满 n ” );exit(0);-1 时退栈。n ” );exit(0);%dn” ,stop-)； void InOutS(int smaxsize)/s 是元素为整数的栈，本算法进行入栈和退栈操作。int top=0; /top for(i=1; i=n; i+) /n scanf(“ %d” ,&x); /if(x!=-1)/if(top=maxsize-1)printf( else s+top=x; /x 入栈。else / 读入的整数等于if(top=0)printf(else printf( “出栈元素是/ 算法结7、编写一个过程，对一个nxn矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。8 、 假设以邻接矩阵作为图的存储结构， 编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路(找到一条即可) 。 (注：图中不存在顶点到自己的弧)有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完 ; 已访问且其邻接点已访问完。 下面用 0， 1， 2 表示这三种状态

7、。 前面已提到，若dfs (v)结束前出现顶点 u至ij v的回边，则图中必有包含顶点v和u的回路。对应程序中v的状态为1,而u是正访问的顶点，若我们找出u的下一邻接点的状态为 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) dfs(j); /ifelse cycle=1; Print(j,j);visitedv=2;/dfsvoid find_cycle() / 判断是否有回路，有则输出邻接矩阵。 visited 数组为全局变量。for (i=1;i=n;i+) visitedi=0;for (i=1;ij)printf( “序列非法n ” ) ； exit(0);是 I 或O ，指针i 均后移。 if(j!=k) printf( “序列非法n ” ) ； return(false);else printf( “序列合法n ” ) ； return(true);/ 算法结束。10、 连通图的生成树包括图中的全部 n 个顶点和足以使图连通的 n-1 条边， 最小生成树是边上权值之和最小的生成树。故可按权值

《2012河南省数据库入门深入》由会员博****1分享，可在线阅读，更多相关《2012河南省数据库入门深入》请在金锄头文库上搜索。