首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列算法说明和算法,将应填入(n)的字句写在对应的栏内。 [说明] 下列最短路径算法的具体流程如下:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去,直至该森林变成一棵树为止,这棵树便是
阅读下列算法说明和算法,将应填入(n)的字句写在对应的栏内。 [说明] 下列最短路径算法的具体流程如下:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去,直至该森林变成一棵树为止,这棵树便是
admin
2009-02-15
43
问题
阅读下列算法说明和算法,将应填入(n)的字句写在对应的栏内。
[说明]
下列最短路径算法的具体流程如下:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去,直至该森林变成一棵树为止,这棵树便是连通网的最小生成树。该算法的基本思想是:为使生成树上总的权值之和达到最小,则应使每一条边上的权值尽可能地小,自然应从权值最小的边选起,直至选出 n-1条互不构成回路的权值最小边为止。
[算法]
/*对图定义一种新的表示方法,以一维数组存放图中所有边,并在构建图的存储结构时将它构造为一个“有序表”。以顺序表MSTree返回生成树上各条边。*/
typedef struct{
VertexType vex1;
VertexType vex2;
VRType weight;
} EdgeType;
typedef ElemType EdgeType;
typedef struct { //有向网的定义
VertexType vexs [MAX_VERTEX_N U M ]; //顶点信息
EdgeType edge[ MAX_EDGE_NUM]; //边的信息
int vexnum, arcnum; //图中顶点的数目和边的数目
I ELGraph;
void MiniSpanTree_Kruskal( ELGraph G,SqList& MSTree) {
//G, edge 中依权值从小到大存放有向网中各边
//生成树的边存放在顺序表MSTree中
MFSetF;
InitSet( F, G. vexnum ); //将森林F初始化为N棵树的集合
InitList (MSTree, G. vexnum); //初始化生成树为空树
i=0;k=1;
while(k<(1)){
e = G. edge
; //取第i条权值最小的边
/*函数fix_mfset返回边的顶点所在树的树的根代号,如果边的两个顶点所在树的树根相同,则说明它们已落在同一棵树上。 */
ri = fix_mfset(F, LocateVex(e. vex1) );
r2=(2); //返回两个顶点所在树的树根
if(r1 (3) r2) { //选定生成树上第k条边
if(Listlnsert(MSTree,k,e){(4); //插入生成树
mix_mfset( E, r1,r2); //将两棵树归并为一棵树
}
(5); //继续考察下一条权值最小边
}
DestroySet (F); }
}
选项
答案
(1)G. vexnum(2)fix_mfset(F, LoeateVex(e. vex2)) (3)!=(4)k++。(5)i++
解析
本题考查的是克鲁斯卡尔(Kruskal)算法。理解该算法的关键在于:由于生成树上不允许有问路,因此并非每一条居当前权值最小的边都可选。例如,如图2所示的连通网G5,在依次选中了(e, f),(b, c),(e, d)和(f, s)的4条边之后,权值最小边为(s, d),由于g和d已经连通,若加上(s, d)这条边将使生成树上产生回路,显然这条边不可取。同理,边(f, d)也不可取,之后则依次取(a, s)和(a, b)两条边加入到生成树。
那么在算法中如何判别当前权值最小边的两个顶点之间是否已经连通?从生成树的构造过程可见,初始态为n个顶点分属n棵树,互不连通,每加入一条边,就将两棵树合并为一棵树,在同一棵树上的两个顶点之间自然相连通。由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。
转载请注明原文地址:https://jikaoti.com/ti/9Vi7FFFM
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
某指令流水线由4段组成,各段所需要的时间如下图所示。连续输入8条指令时的吞吐率(单位时间内流水线所完成的任务数或输出的结果数)为()。
已知函数f()、g()的定义如下所示,执行表达式“x=f(5)”的运算时,若函数调用g(a)是引用调用(callbyreference)方式,则执行“x:f(5)”后x的值为(7);若函数调用g(a)是值调用(callbyvalue)方式,
对于逻辑表达式((a‖(b&c))‖(C&&d)),需要___________个测试用例才能完成条件组合覆盖。
以下不属于系统测试的是___________。①单元测试②集成测试③安全性测试④可靠性测试⑤确认测试⑥验收测试
某教学管理数据库中,学生、课程关系模式和主键分别为:S(学号,姓名,性别,家庭住址,电话),关系S的主键为学号;C(课程号,课程名,学分),关系C的主键为课程号。假设一个学生可以选择多门课程,一门课程可以由多个学生选择。一旦学生选择某门课程必定有该课程的成
已知函数f()、g()的定义如下所示,调用函数f时传递给形参x的值是5。若g(a)采用引用调用(callbyreference)方式传递参数,则函数f的返回值为(12);若g(a)采用值调用(callbyvalue)的方式传递参数,则函数f
测试执行过程的阶段不包括______。
若某计算机采用8位整数补码表示数据,则运算______将产生溢出。A.127+1B.-127-1C.-127+1D.127-1
如果在查找路由表时发现有多个选项匹配,那么应该根据___________(25)原则进行选择。假设路由表有4个表项如下所示,那么与地址139.17.179.92匹配的表项是____________(26)。(26)
在分布式数据库中有分片透明、复制透明、位置透明和逻辑透明等基本概念,其中:___________(19)是指局部数据模型透明,即用户或应用程序无须知道局部使用的是哪种数据模型;___________(20)是指用户或应用程序不需要知道逻辑上访问的表具体是怎
随机试题
“蛮族法典”中最具代表性的一部是_______。
女孩,5岁。精神欠佳半个月,发热、头痛、呕吐10天。半个月前开始出现精神不佳,10天来每天发热,最高体温38,1℃,进食减少,伴头痛,呕吐。2个月前曾患“麻疹”。查体:精神差,消瘦,右眼外展受限,颈抵抗(+),Kernig征(+),Brudzinski征(
在建设工程材料采购合同条件下,采购方有权部分或全部拒付货款的情况大致包括()。
当产品A的价格上升,导致B的需求上升的原因最可能是()。
个体对自己存在状态的认知,称为()。
在本届羽毛球公开赛上,如果中国队的女子双打能够进入半决赛,同时混合双打失利,则男子单打或者女子单打无法夺冠。如果以上命题为真,再加上以下哪项前提,可以得出结论:中国队的女子双打没有进入半决赛?
A条件(1)充分,但条件(2)不充分B条件(2)充分,但条件(1)不充分C条件(1)和(2)单独都不充分,但条件(1)和(2)联合起来充分D条件(1)充分,条件(2)也充分E条件(1)和(2)单独都不充分,条件(1)和(2)联合起来也不充分如右
在SQLServer2008的某用户数据库中,设有T表,现要在T表的c1列和c2列上建立一个复合唯一聚集索引,其中c1列值重复率为20%,c2列为10%。请补全下列语句建立一个性能最优的索引:CREATEUNIQUECLUSTEREDI
若有以下程序#include#includetypedefstructstu{charname[10],gender;intscore;}STU;voidf(char*p){strcpy(p,"Qian");}main(){STUa={"
以下列出的6个软件中,属于系统软件的是①字处理软件②Linux③UNIX④学籍管理系统⑤Windows2000⑥office2000
最新回复
(
0
)