首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列算法说明和算法,将应填入(n)的字句写在对应的栏内。 [说明] 下列最短路径算法的具体流程如下:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去,直至该森林变成一棵树为止,这棵树便是
阅读下列算法说明和算法,将应填入(n)的字句写在对应的栏内。 [说明] 下列最短路径算法的具体流程如下:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去,直至该森林变成一棵树为止,这棵树便是
admin
2009-02-15
38
问题
阅读下列算法说明和算法,将应填入(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://kaotiyun.com/show/vrDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
给定关系模式R(A,B,C,D)、S(C,D,E),与π1,3,5等价的SQL语句如下:SELECT(22)FROMR,sWHERE(23);下列查询B=“信息”且E=“北京”的A、B、E的关系代数表达式中,查询效率
包过滤防火墙是一种通过软件检查数据包以实现系统安全防护的基本手段,以下叙述中,不正确的是()。
假设段页式存储管理系统中的地址结构如下图所示,则系统()。
在结构化分析中,用数据流图描述(42)。当采用数据流图对银行客户关系管理进行分析时,(43)是一个加工。(43)
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的数字表示活动的持续时间(天),则完成该项目的最少时间为(33)天。活动BC和BF分别最多可以晚开始(34)天而不会影响整个项目的进度。(33)
若某线性表长度为n且采用顺序存储方式,则运算速度最快的操作是_______。
在结构化分析方法中,依据______来进行接口设计。
若某计算机采用8位整数补码表示数据,则运算______将产生溢出。A.127+1B.-127-1C.-127+1D.127-1
在分层体系结构中,(41)实现与实体对象相关的业务逻辑。在基于Java,EE技术开发的软件系统中,常用(42)技术来实现该层。(42)
随机试题
女性,68岁。原有肺心病病史。受凉后发热伴咳脓痰,发绀加重,次日神志模糊,嗜睡,血压90/67.5mmHg(12.0/9.0kPa),无病理反射。患者最可能并发
OPs波下降或消失常见的眼病是:
患者,男性,21岁。因突发剑突下钻顶样剧烈疼痛而入院,自诉疼痛呈间歇性,发作时疼痛剧烈,辗转不安,大汗淋漓,可突然自行缓解,缓解期元任何症状。体检示剑突下有轻度深压痛。WBC11.5×109/L。应采取的处理方案是
货币的时间价值不是指现在的钱比将来的钱有更高的价值;或者说,现在的钱比将来的钱不值钱。()
( )既对项目投资控制进行管理,也对成本控制进行管理。
只有当证券投资的名义收益率( )时,投资者才有实际收益。
习近平总书记指出,人民政协在协商中促进广泛团结、推进多党合作、实践人民民主,既秉承历史传统,又反映时代特征,充分体现了我国社会主义民主有事多商量、遇事多商量、做事多商量的特点和优势。发展社会主义协商民主,要把民主集中制的优势运用好,发扬“团结—批评—团结”
Whichgame...issoldwell?【P1】______allowsgamerstoselectgameswithequal-caliberopponents?【P2】______isprobablyfright
EachofQuestions1to7presentstwoquantities.QuantityAandQuantityB.Comparethetwoquantities.Youmayuseadditional
A、Computersalesnegotiations.B、Apreliminaryinterview.C、AnInternetseminarmeeting.D、Computergames.B综合推断题。女士一开始就让男士介绍自己之
最新回复
(
0
)