首页 > 2015年宁夏回族自治区数据要领要领

2015年宁夏回族自治区数据要领要领

发布时间：来源：文档文库

小中大

字号：

手机查看

1、假设K1，„，Kn是n个关键词，试解答：
试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，„，Kn时，用算法建立一棵以LLINK/RLINK链接表示的二叉查找树。
2、设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。3、连通图的生成树包括图中的全部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(是测试图是否连通的函数，可用图的遍历实现，
4、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。29.①试找出满足下列条件的二叉树
1）先序序列与后序序列相同2）中序序列与后序序列相同3）先序序列与中序序列相同4）中序序列与层次遍历序列相同5、连通图的生成树包括图中的全部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(是测试图是否连通的函数，可用图的遍历实现，

本文来源：https://www.2haoxitong.net/k/doc/2790867d1a37f111f0855bc5.html