首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C函数,将应填入(n)处的字句写在对应栏内。 [说明] Kruskal算法是一种构造图的最小生成树的方法。设G为一无向连通图,令T是由G的顶点构成的于图,Kmskal算法的基本思想是为T添加适当的边使之成为最小生成树:初始时,T中的
阅读下列函数说明和C函数,将应填入(n)处的字句写在对应栏内。 [说明] Kruskal算法是一种构造图的最小生成树的方法。设G为一无向连通图,令T是由G的顶点构成的于图,Kmskal算法的基本思想是为T添加适当的边使之成为最小生成树:初始时,T中的
admin
2009-02-15
62
问题
阅读下列函数说明和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单元格中的显示内容为______。
下列关于数据库系统的说法中,(62)是错误的。
在调查某地区各类用户所喜欢的电视栏目时,信息处理技术员小王制作了用户类(U)与电视栏目(V)关系图。下面的示意图描述了五类用户(从上到下U1~U5)与四个电视栏目(从上到下V1~V4)之间的关系:如果某类用户大多喜欢某个电视栏目,则在它们之间画一条连线。从
在Excel2010的A1单元格中输入函数“=ABS(ROUND(-1.478,2))”,按回车键后,A1单元格中的值为________________。
下列关于Windows7屏幕保护程序的叙述中,不正确的是__________。
上级要求信息处理技术员做a、b、c、d、e五件工作。先做什么,后做什么,如何安排呢?根据工作性质以及紧急程度,他列出了如下几条规则:a应在b前 c应在a前 d应在a前 a应在e前d应在b前 b应在e前 c应在d前 c应在
西部某省考试机构工作人员统计了去年下半年三个地区四种资格的报考人数,将统计表抄录如下(其中有一个数据抄错了): 信息处理技术员小王很快就找出了错误的数据,并进行了纠正。错误的数据是(32),该数据应纠正为(33)。33.
在Excel2003中,A1到E6单元格的值如下图所示,若在A7单元格中输入计算众数的函数“=MODE(A1:E6)”,按回车键后,则.A7单元格显示的值为(47)。
在Windows7中,若删除桌面上某个应用程序的快捷方式图标,则(31)。
随机试题
(13—04)欧洲货币贷款协议中贷款人增订的保护自己利益的特殊条款是______。
水痘风热轻证的治疗原则是:
光学密度值的数学表达式为
以下哪些与磷酸氯喹相符
法律发展的两种类型
根据我国现行建筑安装工程费用组成,下列各费用项目中属于措施费的是()。
请按照要求完成相应的教学设计。要求:为检测教学目标是否达成,设计一道选项为四项的单项选择题和一道简答题,并给出答案和解析。
企业对会计政策变更采用追溯调整法时,应当按照会计政策变更的累积影响数调整当期期初的留存收益。()
拥挤的居住条件导致的市民健康状况明显下降,是A城面临的重大问题。因为A城和B城两个城市的面积和人口相当,所以A城所面临的上述问题必定会在B城出现。以下哪项最能反驳上述结论?()
有苹果若干个,若把其换成桔子,则多换5个;若把其换成菠萝,则少掉7个。已知每个桔子4角9分钱,每个菠萝7角钱,每个苹果的单价是多少?
最新回复
(
0
)