首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列算法说明和算法,将应填入(n)的字句写在答题纸的对应栏内。 【说明】 下列最短路径算法的具体流程如下:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去,直至该森林变成一棵树为止,这棵树
阅读下列算法说明和算法,将应填入(n)的字句写在答题纸的对应栏内。 【说明】 下列最短路径算法的具体流程如下:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去,直至该森林变成一棵树为止,这棵树
admin
2009-02-15
43
问题
阅读下列算法说明和算法,将应填入(n)的字句写在答题纸的对应栏内。
【说明】
下列最短路径算法的具体流程如下:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去,直至该森林变成一棵树为止,这棵树便是连通网的最小生成树。该算法的基本思想是:为使生成树上总的权值之和达 到最小,则应使每一条边上的权值尽可能地小,自然应从权值最小的边选起,直至选出n-1条互不构成回路的权值最小边为止。
【算法】
/*对图定义一种新的表示方法,以一维数组存放图中所有边,并在构建图的存储结构时将它构造为一个“有序表”。以顺序表MSTree返回生成树上各条边。*/
typedef strnct{
VertexType vex 1;
VertexType vex2;
VRType weight;
}EdgeType;
typedef ElemType EdgeType;
typedefstruct { // 有向网的定义
VertexType vexs[MAX_VERTEX_NUM]; // 顶点信息
EdgeType edge[MAX_EDGE_NUM]; // 边的信息
Mt vexnum,arcnum; // 图中顶点的数目和边的数目
}ELGraph;
void MiniSpanTree_Kruskal(ELGraph G, SqList& MSTree){
//G.edge 中依权值从小到大存放有向网中各边
// 生成树的边存放在顺序表 MSTree 中
MFSet F;
InitSet(F, G.vexnum); // 将森林 F 初始化为 n 棵树的集合
InitList(MSTree, G.vexaum); // 初始化生成树为空树
i=O; k=l;
while( k<(1)) {
e = G.edge
; // 取第i条权值最小的边
rl = fix_mfset(F, LocateVex(e.vexl));
r2 =(2) // 返回两个顶点所在树的树根
if(ri (3) r2){ // 选定生成树上第k条边
if (Listlnsert(MSTree, k, e)) (4); // 插入生成树
mix_mfset(F, ri, r2); // 将两棵树归并为一棵树
}
(5); //继续考察下一条权值最小边
}
Destroy Set(F);
}
选项
答案
(1)G.vexnum (2)fix_mfset(F,Locate Vex(e.vex2)) (3) != (4)k++ (5)i++
解析
本题考查的是克鲁斯卡尔(Kmskal)算法。理解该算法的关键在于:由于生成树上不允许有回路,因此并非每一条居当前权值最小的边都可选。例如,如图7-1所示的连通网G5,在依次选中了(e,f),(b,c),(e,d)和(f,g)的4条边之后,权值最小边为(g,d),由于g和 d已经连通,若加上(g,d)这条边将使生成树上产生回路,显然这条边不可取。同理,边(f,d)也不可取,之后则依次取(a,g)和(a,b)两条边加入到生成树。
那么在算法中如何判别当前权值最小边的两个顶点之间是否已经连通?从生成树的构造过程可见,初始态为n个顶点分属n棵树,互不连通,每加入一条边,就将两棵树合并为一棵树,在同一棵树上的两个顶点之间自然相连通。由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。
转载请注明原文地址:https://kaotiyun.com/show/3wDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
设计功能测试用例的根本依据是______。A.用户需求规格说明书B.用户手册C.被测产品的用户界面D.概要设计说明书
程序描述语言(PDL)是软件开发过程中用于______阶段的描述工具。A.需求分析B.概要设计C.详细设计D.编程
若内存容量为4GB,字长为32,则______。A.地址总线和数据总线的宽度都为32B.地址总线的宽度为30,数据总线的宽度为32C.地址总线的宽度为30,数据总线的宽度为8D.地址总线的宽度为32,数据总线的宽度为8
对于逻辑表达式((a&b)||c,需要______个测试用例才能完成条件组合覆盖。
软件评价过程的特性不包括()。
()模型吸收了软件工程“演化”的概念,使用原型及其他方法来尽量降低风险,适合于大型复杂软件系统的开发。
集成测试关注的问题不包括()。
以下所示程序控制流程图中有(59)条线性无关的基本路径。
在计算机系统中,系统的______可以用MTTF/(1+MTTF)来度量,其中MTTF为平均无故障时间。
随机试题
A.完全肯定性诊断B.不完全肯定性诊断C.描述性诊断D.阴性诊断E.否定诊断创伤后形成的肉芽组织属于
《安全生产法》在总结我国安全生产管理经验的基础上,将()规定为我国安全生产工作的基本方针。
自动化仪表工程施工的原则是()。
企业所有者权益变动表中“其他综合收益”项目列示金额应当与资产负债表中“其他综合收益”列示金额相等。()
汪某和范某是邻居,某天,双方因生活琐事发生争吵,范某怒而挥刀砍向汪某,致汪某死亡。事后,范某与汪某的妻子在中间人的主持下,达成“私了”。后汪某父母得知儿子身亡,坚决不同意私了,遂向当地公安部门告发。公安部门立案侦查之后,移送检察院。最后,法院判处范某无期徒
1937年,马思聪创作的小提琴独奏曲《第一回旋曲》和(),不仅是他个人的成名作,也是我国小提琴创作的力作。
【2015云南玉溪】个人身心发展的动因有()。
小王和小赵分别站在正方形操场的两个对角A、C上(如图),同时以相同的速度逆时针沿操场散步。用M、N分别代表小赵、小王所在位置,以下哪个坐标图能准确描述△DMN的面积与时间的关系?(横轴为时间,纵轴为面积)
如果企业一定期间内的固定成本和固定财务费用均不为零,则由上述因素共同作用而导致杠杆效应属于()。
设f(x)=x(x-1)(x-2)…(x-100),求f′(50).
最新回复
(
0
)