2011年辽宁省数据分析入门

发布时间：

1、设有一个数组中存放了一个无序的关键序列K1、K2、„、Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。51.借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“notfind”信息。请编写出算法并简要说明算法思想。

2、连通图的生成树包括图中的全部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].wedge[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(是测试图是否连通的函数，可用图的遍历实现，
3、假设K1，„，Kn是n个关键词，试解答：
试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，„，Kn时，用算法建立一棵以LLINK/RLINK链接表示的二叉查找树。
4、后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找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||top>0
{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;i<=top;i++s1[i]=s[i];top1=top;}//将栈s的元素转入辅助栈s1保存if(bt==q//找到q结点。
for(i=top;i>0;i--//；将栈中元素的树结点到s1去匹配{pp=s[i].t;
for(j=top1;j>0;j--
if(s1[j].t==pp{printf(“p和q的最近共同的祖先已找到”；return(pp;}｝
while(top!=0&&s[top].tag==1top--;//退栈
if(top!=0｛s[top].tag=1;bt=s[top].t->rchild;｝//沿右分枝向下遍历}//结束while(bt!=null||top>0return(null;//ｑ、p无公共祖先｝//结束Ancestor

2011年辽宁省数据分析入门

推荐内容

相关推荐