当前位置: 首页 > >

2015年浙江省数据理论高级

发布时间:

1、 连通图的生成树包括图中的全部 n 个顶点和足以使图连通的 n-1 条边,最小生成树是边 上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每 删除一条当前权值最大的边后,就去测试图是否仍连通,若不再连通,则将该边恢复。若仍 连通,继续向下删;直到剩 n-1 条边为止。 void SpnTree (AdjList g) //用“破圈法”求解带权连通无向图的一棵最小代价生成树。 {typedef struct {int i,j,w}node; //设顶点信息就是顶点编号,权是整型数 node edge[]; 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].w<edge[0].w) edge[j+1]=edge[j--]; edge[j+1]=edge[0]; }//for k=1; eg=e; while (eg>=n) //破圈,直到边数 e=n-1. {if (connect(k)) //删除第 k 条边若仍连通。 {edge[k].w=0; eg--; }//测试下一条边 edge[k],权值置 0 表示该边被删除 k++; //下条边 }//while }//算法结束。 connect()是测试图是否连通的函数,可用图的遍历实现, 2、给定 n 个村庄之间的交通图,若村庄 i 和 j 之间有道路,则将顶点 i 和 j 用边连接,边上 的 Wij 表示这条道路的长度,现在要从这 n 个村庄中选择一个村庄建一所医院,问这所医院 应建在哪个村庄, 才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算 法,并应用该算法解答如图所示的实例。 (20 分) 3、设有两个集合 A 和集合 B,要求设计生成集合 C=A∩B 的算法,其中集合 A、B 和 C 用链式 存储结构表示。 typedef struct node {int data; struct node *next;}lklist; void intersection(lklist *ha,lklist *hb,lklist *&hc) { lklist *p,*q,*t; for(p=ha,hc=0;p!=0;p=p->next) { for(q=hb;q!=0;q=q->next) if (q->data==p->data) break; if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;} } } 4、给出折半查找的递归算法,并给出算法时间复杂度性分析。




友情链接: