首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列算法说明和算法,将应填入(n)的字句写在答题纸的对应栏内。 【说明】 下列最短路径算法的具体流程如下:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去,直至该森林变成一棵树为止,这棵树
阅读下列算法说明和算法,将应填入(n)的字句写在答题纸的对应栏内。 【说明】 下列最短路径算法的具体流程如下:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去,直至该森林变成一棵树为止,这棵树
admin
2009-02-15
77
问题
阅读下列算法说明和算法,将应填入(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
软件设计师下午应用技术考试
软考中级
相关试题推荐
黑盒测试中,(59)是根据输出对输入的依赖关系设计测试用例。
对需求说明书评测的内容包括______。①系统定义的目标是否与用户的要求一致②被开发项目的数据流与数据结构是否足够、确定③与所有其他系统交互的重要接口是否都已经描述④主要功能是否已包含在规定的软件范围之内,是否都已充分说明
若有关系R(A,B,C,D,E)和S(B,C,F,G),则R与S自然联结运算后的属性列有(17)个,与表达式π1,3,6,7(σ3<6(RS))等价的SQL语句如下:SELECT(18)FROM(19)WHERE(20);
对于防病毒系统的测试是系统安全测试的重要内容,下列不属于防病毒系统安全测试基本测试点的是____________。
兼容性测试的测试范围包括___________。①硬件兼容性测试②软件兼容性测试③数据兼容性测试④平台兼容性测试
在数据库逻辑设计阶段,若实体中存在多值属性,那么将E-R图转换为关系模式时,___________,得到的关系模式属于4NF。
以下关于用例图的叙述中,不正确的是(44)。图书馆管理系统需求中包含“还书”用例和“到书通知”用例,对于“还书”用例,应先查询该书是否有人预定,若有则执行“到书通知”。“还书”用例和“到书通知”用例是(45)关系,以下用例图中,(46)是正确的。管理员处
以下关于用例图的叙述中,不正确的是(44)。图书馆管理系统需求中包含“还书”用例和“到书通知”用例,对于“还书”用例,应先查询该书是否有人预定,若有则执行“到书通知”。“还书”用例和“到书通知”用例是(45)关系,以下用例图中,(46)是正确的。管理员处
在结构化分析方法中,利用分层数据流图对系统功能建模。以下关于分层数据流图的叙述中,不正确的是___________(32)。采用数据字典为数据流图中的每个数据流、文件、加工以及组成数据流或文件的数据项进行说明,其条目不包括____________(33)。
在结构化分析方法中,数据流图描述数据在系统中如何被传送或变换,反映系统必须完成的逻辑功能,用于(38)建模。在绘制数据流图时,(39)。(39)
随机试题
试述咽鼓管有哪两个开口?各开口的部位?小儿为什么易患中耳炎?
白细胞:分析仪法(+),镜检法(-),出现这种化学法分析结果与镜检结果不相符的情形可能的解释
AcTnBCK—MbCMbDLDECK早期诊断AMI最好的心肌标志物是
患者,男性,30岁,因需拔除右下:智齿行局部麻醉,采用含肾普鲁卡因5ml行局部麻醉注射后,患者即感到心悸、头晕、头痛、脉搏快而有力、血压升高、口唇苍白,此情况是发生了
背景某城市南郊雨水泵站工程邻近大治河,大治河常水位为+3.00m,雨水泵站与进水管道连接处的管内底标高-4.00m。雨水泵房地下部分采用沉井法施工,进水管为3m×2m×10m(宽×高×长)现浇钢筋混凝土箱涵,基坑采用拉森钢板桩围护。设计
党的领导是行政领导,政府的领导是政治领导。()
现在大学里开展创业教育课程,你怎么看?
软件开发过程中为确保软件质量所采取的措施中,不包括______。
目前普及型彩色喷墨打印机一般都有4种颜色的墨盒,除了使用青、黄、品红(洋红)之外,还有一种颜色是______色。
神户没有大阪那么繁华。
最新回复
(
0
)