首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C函数,将应填入(n)处的字句写在对应栏内。 [说明] Kruskal算法是一种构造图的最小生成树的方法。设G为一无向连通图,令T是由G的顶点构成的于图,Kmskal算法的基本思想是为T添加适当的边使之成为最小生成树:初始时,T中的
阅读下列函数说明和C函数,将应填入(n)处的字句写在对应栏内。 [说明] Kruskal算法是一种构造图的最小生成树的方法。设G为一无向连通图,令T是由G的顶点构成的于图,Kmskal算法的基本思想是为T添加适当的边使之成为最小生成树:初始时,T中的
admin
2009-02-15
136
问题
阅读下列函数说明和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
程序员下午应用技术考试
软考初级
相关试题推荐
若要查询成绩为70-80分之间(包括70分,不包括80分)的学生的信息,以下查询准则设置正确的是()。
可以将数据划分成有序数据和无序数据两类。以下几种数据中属于无序数据的是______。
数据清洗工作不包括(10)。
计算机处理的数字数据有数值数据和字符数据之分。对信息处理技术员来说,它们的主要区别是______。
在Excel2010中,C3:C7单元格中的值分别为10、OK、20、YES和48,在。D7单元格中输入函数“=COUNT(C3:C7)”,按回车键后,D7单元格中显示的值为________________。
将四个元素a,b,c,d分成非空的两组,不计组内顺序和组间顺序,共有()种分组方法。
西部某省考试机构工作人员统计了去年下半年三个地区四种资格的报考人数,将统计表抄录如下(其中有一个数据抄错了): 信息处理技术员小王很快就找出了错误的数据,并进行了纠正。错误的数据是(32),该数据应纠正为(33)。33.
为在Exce1的A1单元格中生成一个60到100之间的随机数,则应在A1单元格中输入______
数据录入工作有两个指标:录入速度和错误率。一般而言,数据录入员在录入大批数据时,录入速度会(65),错误率会(66)。65
(1)是固化在主板ROM内的程序,为计算机提供最底层、最直接的硬件访问和控制。
随机试题
饮料酒标签日期的标示应按()顺序。
在理财产品销售文件中应包含专页风险揭示书,风险揭示书至少包括下列()内容。
识别出超出正常经营过程的重大关联方交易时,以下说法中,不正确的是()。
依据我国宪法,下列不具备选举权和被选举权的情形有()。
饥饿营销是指商品提供者有意调低产量,以期达到调控供求关系、制造供不应求假象、维持商品较高售价和利润,以达到维护品牌形象、提高产品附加值的目的。根据上述定义,下列属于饥饿营销的是:
被代理人死亡后,委托代理人实施的代理行为仍然有效的有()。(2010一法专一32)
某辩论赛结束后七个评委投票决定一名最佳辩手。对任一评委,他或她投辩手小孙的票,这是可能的。因此,所有的评委都投小孙的票,这也是可能的。以下哪项对上述论证的评价最为恰当?
表示关系式x≤y≤z的C语言表达式的是
下列选项不属于“计算机安全设置”的是()。
【S1】【S10】
最新回复
(
0
)