首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列算法说明和算法,将应填入(n)的字句写在答题纸的对应栏内。 【说明】 下列最短路径算法的具体流程如下:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去,直至该森林变成一棵树为止,这棵树
阅读下列算法说明和算法,将应填入(n)的字句写在答题纸的对应栏内。 【说明】 下列最短路径算法的具体流程如下:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去,直至该森林变成一棵树为止,这棵树
admin
2009-02-15
78
问题
阅读下列算法说明和算法,将应填入(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为布尔变量,对于逻辑表达式(A&&B||C),需要______个测试用例才能完成判定覆盖(DC)。A.2B.3C.4D.5
在安全测试中,模拟攻击试验以模拟攻击来验证软件或信息系统的安全防护能力,其中拒绝服务(DoS)攻击是一种在安全测试中经常模拟的攻击行为,以下模拟攻击不属于拒绝服务攻击的是()。
软件可靠性管理把软件可靠性活动贯穿于软件开发的全过程,成为软件工程管理的一部分。确定软件可靠性度量活动属于()阶段。
以下关于用例图的叙述中,不正确的是(44)。图书馆管理系统需求中包含“还书”用例和“到书通知”用例,对于“还书”用例,应先查询该书是否有人预定,若有则执行“到书通知”。“还书”用例和“到书通知”用例是(45)关系,以下用例图中,(46)是正确的。管理员处
结构化开发方法中,(35)主要包含对数据结构和算法的设计。对算法设计时,其主要依据来自(36)。描述算法时,(37)不是理想的表达方式。(36)
下面的协议中属于应用层协议的是(26),该协议的报文封装在(27)中传送。(26)
以下对用户口令进行限定的措施中,(66)对提高安全性来说是无用的。
______是当前自动化测试技术不能解决的问题。A.保证测试质量B.提高测试效率C.排除手工操作错误D.降低测试用例设计的难度
堆是一种数据结构,分为大顶堆和小顶堆两种类型。大(小)顶堆要求父元素大于等于(小于等于)其左右孩子元素。则___________(41)是一个大项堆结构,该堆结构用二叉树表示,其高度(或层数)为___________(42)。(41)
如果在查找路由表时发现有多个选项匹配,那么应该根据___________(25)原则进行选择。假设路由表有4个表项如下所示,那么与地址139.17.179.92匹配的表项是____________(26)。(25)
随机试题
根据单位工程项目划分原则,()按招标标段或加固内容,并结合工程量划分单位工程。
A、肘内翻畸形B、餐叉样畸形C、爪形手畸形D、刺刀样畸形E、动脉损伤桡骨下端骨折侧面呈()
有机磷农药中毒引起中毒症状的原因是体内大量堆积了
A、治愈率,显效率,好转率等B、适当的用药时间C、风险/效果比D、成本/效果比E、适当的途径、剂量和疗程反映了用药经济性()
在国际竞争性招标的评标过程中,主要的工作步骤包括()。
某施工企业在2017年2月1日办理了安全生产许可证,则其向原发证机关办理延期手续的期间为()。
评估某写字楼在建工程的价值,其土地是3年前通过挂牌方式取得的50年建设用地使用权,预计该写字楼2年后建设出租的月毛租金为50元/平方米,空置率为10%。运营费用为毛租金的40%,报酬率为8%。根据以上资料,回答下列问题:该写字楼建成后的价值为(
培训前对培训师的基本要求包括()。
复制文件操作完成之后(无错误),存放文件的磁盘其空闲块将()。
又聋又哑的人或者盲人犯罪,可以_______、减轻或者________。
最新回复
(
0
)