2012年江苏省学习数据库大纲.doc

2012年江苏省学习数据库大纲 导读：就爱阅读网友为您分享以下“2012年江苏省学习数据库大纲”的资讯，希望对您有所帮助，感谢您对92的支持! 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}唯一确定左子树，从而也确定了二叉树。最后，当1lt;ilt;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、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注：圈就是回路。3、两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。int Similar(BiTree p,q) //判断二叉树p和q是否相似{if(p==null amp;amp; q==null) return (1);else if(!p amp;amp; q || p amp;amp; !q) return (0);else return(Similar(p-gt;lchild,q-gt;lchild) amp;amp; Similar(p-gt;rchild,q-gt;rchild))}//结束Similar4、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。（20分）5、假设以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; //j和k分别为I和字母O的的个数。while(A[i]!=\0’) //当未到字符数组尾就作。{switch(A[i]){caseI’: j++; break; //入栈次数增1。caseO’: k++; if(kgt;j){printf(“序列非法\n”)；exit(0);}}i++; //不论A[i]是I’或O’，指针i均后移。}if(j!=k) {printf(“序列非法\n”)；return(false);}else {printf(“序列合法\n”)；return(true);}}//算法结束。6、对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(kgt;1) 层上叶子结点个数{if(bt==null |