2021年.维吾尔自治区数据库入门加强

2021年.维吾尔自治区数据库入门加强1、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。（20分）2、后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q的最近共同祖先结点r,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p和q的最近公共祖先。typedefstruct{BiTreet;inttag;//tag=0表示结点的左子女已被访问，tag=1表示结点的右子女已被访问}stack;stacks[],s1[];//栈，容量够大BiTreeAncestor(BiTreeROOT,p,q,r)//求二叉树上结点p和q的最近的共同祖先结点r。{top=0;bt=ROOT;while(bt!=null||top0){while(bt!=null&&bt!=p&&bt!=q)//结点入栈{s[++top].t=bt;s[top].tag=0;bt=bt-lchild;}//沿左分枝向下if(bt==p)//不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点{for(i=1;iif(bt==q)//找到q结点。for(i=top;i0;i--)//；将栈中元素的树结点到s1去匹配{pp=s[i].t;for(j=top1;j0;j--)if(s1[j].t==pp){printf(“p和q的最近共同的祖先已找到”)；return(pp);}｝while(top!=0&&s[top].tag==1)top--;//退栈if(top!=0)｛s[top].tag=1;bt=s[top].t-rchild;｝//沿右分枝向下遍历}//结束while(bt!=null||top0)return(null);//ｑ、p无公共祖先｝//结束Ancestor3、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0.typedefstructnode{intdata;structnode*lchild,*rchild;}node;intN2,NL,NR,N0;voidcount(node*t){if(t-lchild!=NULL)if(1)___N2++;elseNL++;elseif(2)___NR++;else(3)__;if(t-lchild!=NULL)(4)____;if(t-rchild!=NULL)(5)____;}26.树的先序非递归算法。voidexample(b)btree*b;{btree*stack[20],*p；inttop;if(b!=null){top=1;stack[top]=b;while(top0){p=stack[top];top--;printf(“%d”,p-data);if(p-rchild!=null){(1)___;(2)___;}if(p-lchild!=null)(3)___;(4)__;}}}}4、设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。