首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C函数,将应填入(n)处的字句写在对应栏内。 [说明] Kruskal算法是一种构造图的最小生成树的方法。设G为一无向连通图,令T是由G的顶点构成的于图,Kmskal算法的基本思想是为T添加适当的边使之成为最小生成树:初始时,T中的
阅读下列函数说明和C函数,将应填入(n)处的字句写在对应栏内。 [说明] Kruskal算法是一种构造图的最小生成树的方法。设G为一无向连通图,令T是由G的顶点构成的于图,Kmskal算法的基本思想是为T添加适当的边使之成为最小生成树:初始时,T中的
admin
2009-02-15
58
问题
阅读下列函数说明和C函数,将应填入(n)处的字句写在对应栏内。
[说明]
Kruskal算法是一种构造图的最小生成树的方法。设G为一无向连通图,令T是由G的顶点构成的于图,Kmskal算法的基本思想是为T添加适当的边使之成为最小生成树:初始时,T中的点互相不连通;考察G的边集E中的每条边,若它的两个顶点在T中不连通,则将此边添加到T中,同时合并其两顶点所在的连通分量,如此下去,当添加了n-1条边时,T的连通分量个数为1,T便是G的一棵最小生成树。
下面的函数void Kruskal(EdgeType edges[],int n)利用Kruskal算法,构造了有n个顶点的图 edges的最小生成树。其中数组father[]用于记录T中顶点的连通性质:其初值为father
=-1 (i=0,1,…,n-1),表示各个顶点在不同的连通分量上;若有father
=j,j>-1,则顶点i,j连通;函数int Find(int father[],int v)用于返回顶点v所在树形连通分支的根结点。
[函数]
#define MAXEDGE 1000
typedef struct
{ int v1;
int v2;
}EdgeType;
void Kruskal(EdgeType edges[],int n)
{ int father[MAXEDGE];
int i,j,vf1,vt2;
for(i=0;i<n;i+ +) father
=-1;
i=0;
j=0;
while(i<MAXEDGE && j<(1))
{ vf1=Find(father,edges
.v1);
vf2=Find(father,edges
.v2);
if((2))
{(3)=vf1;
(4);
printf("%3d%3d\n",edges
.v1,edges
.v2);
}
(5);
}
}
int Find(int father[],int v)
{ int t;
t=v;
while(father[t]>=0) t=father[t];
return(t);
}
选项
答案
(1) n-1 (2) vf1! =vf2 (3) father[vf2] (4) j++ (5) i++
解析
(1)由上下文可知,变量j记录了添加进最小生成树的边数,当j超出n-1时循环终止,构造过程结束;
(2)此处的判别条件应该是:v1和V2连通。由于Vf1和 vf2分别是边edges
两顶点v1、v2所在连通分支的根,v1和v2连通当且仅当vf1和vf2相等;
(3)~(4)根据程序说明,当v1和v2不连通时,需添加 edges
进最小生成树且合并v1和v2所在连通分支。后者就是令j自增1;后者即连接vf1和vf2。
(5)对图中的边循环,继续考虑下一条边。
转载请注明原文地址:https://kaotiyun.com/show/objZ777K
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
撰写数据分析报告时,如何用图正确地展现数据,需要考虑的问题中,不包括______。
计算机网络有多种分类方法,下列叙述中不正确的是(15)。
数据展现常需要图表化。美化图表的原则不包括()。
根据某机构的统计与推测,我国人口中男性和女性各个年龄段的百分比如下图。根据该图,以下叙述中正确的是________________。
某企业甲乙两个部门招聘职工中,男女应聘人数和录用人数情况如下表:从上表看出,各部门女性录用率都大于男性录用率。从该企业合计来看,()。
在Excel的A1单元格中输入函数“=ROUND(3.1415,2)”,则A1单元格中显示的值为(57)。
图文混排是Word的特色功能之一,下列叙述中,不正确的是(46)。
随机试题
甲状腺功能亢进症患者的饮食宜给予
恶性肿瘤骨转移,检查可发现
下列关于石膏说法错误的是
患者胃痛隐隐,喜温喜按,空腹痛甚,得食痛减,神疲乏力,大便溏薄。舌淡苔白,脉虚弱。其治法是()
现行的外汇挂钩类理财产品基本上都只有一个触及点。()
下列各项中,应当征收消费税的有()。
下列选项中正确的说法是________。
-36π
将文档的一部分文本内容复制到别处,首先要进行的操作是()。
为了暂时关闭计时器,应把它的一个属性设置为False。这个属性是
最新回复
(
0
)