首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C函数,将应填入(n)处的字句写在对应栏内。 [说明] Kruskal算法是一种构造图的最小生成树的方法。设G为一无向连通图,令T是由G的顶点构成的于图,Kmskal算法的基本思想是为T添加适当的边使之成为最小生成树:初始时,T中的
阅读下列函数说明和C函数,将应填入(n)处的字句写在对应栏内。 [说明] Kruskal算法是一种构造图的最小生成树的方法。设G为一无向连通图,令T是由G的顶点构成的于图,Kmskal算法的基本思想是为T添加适当的边使之成为最小生成树:初始时,T中的
admin
2009-02-15
137
问题
阅读下列函数说明和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
程序员下午应用技术考试
软考初级
相关试题推荐
在Excel中,若A1单元格中的函数为"=IF("教授">"助教",TRUE,FALSE)",按回车键后,A1单元格中的显示内容为______。
若要查询成绩为70-80分之间(包括70分,不包括80分)的学生的信息,以下查询准则设置正确的是()。
某企业甲乙两个部门招聘职工中,男女应聘人数和录用人数情况如下表:从上表看出,各部门女性录用率都大于男性录用率。从该企业合计来看,()。
下面关于幻灯片打印的叙述中,正确的是______。
要使Word能自动提醒英文单词的字母拼写是否正确,应设置Word的(47)选项功能。
在Excel2003中,A1到E6单元格的值如下图所示,若在A7单元格中输入计算众数的函数“=MODE(A1:E6)”,按回车键后,则.A7单元格显示的值为(47)。
为在Exce1的A1单元格中生成一个60到100之间的随机数,则应在A1单元格中输入______
数据录入工作有两个指标:录入速度和错误率。一般而言,数据录入员在录入大批数据时,录入速度会(65),错误率会(66)。65
在Windows7中,若删除桌面上某个应用程序的快捷方式图标,则(31)。
PowerPoint可以通过插入(55)来完成统计、计算等功能。
随机试题
某投资人准备投资于A公司的股票,A公司没有发放优先股,2009年的有关数据如下:每股净资产为10元,每股盈余为1元,每股股利为0.4元,该公司预计未来不增发股票,并且保持经营效率和财务政策不变,现行A股票市价为15元,目前国库券利率为4%,证券市场平均收益
非特异性感染的典型症状是
咬肌间隙感染如未及时切开引流,最常引起的并发症是
患者头晕眼花,心悸多梦,手足麻,唇甲色淡,经诊断为血虚,补血药处方中,配以益气药物其依据是()。
对于患有职业病的职工变动工作后,当这个职工到新单位后,其职业病待遇应由()承担。
中国古代的科学著作大多是经验型的总结,而不是理论型的探讨,所记各项发明都是为了解决国家与社会生活中实际问题,而不是试图在某一研究领域获得重大突破。从研究方法上来说,中国科技重视综合性的整体研究,重视从总体上把握事物,而不是把研究对象从错综复杂的联系中分离出
如下图所示,梯形下底是上底的1.5倍,梯形中阴影面积等于空白面积,三角形OBC的面积是12,那么三角形AOD的面积是()。
关于疫苗,下列说法错误的是()。
在80x86微处理器系统中,从下列哪一种微处理器开始已经将浮点运算部件集成到CPU芯片内部?
ChristmasCandlesFranklyspeaking,Christmascandlesarenodifferent/fromanyotherdecorativecandle/thatyoumightf
最新回复
(
0
)