全部科目 > 软件设计师 >
2014年上半年 上午试卷 综合知识
第 64 题
知识点 生成树   最小生成树  
关键词 算法   无向连通网   最小生成树   生成树  
章/节 计算机软件知识  
 
 
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法，Prim算法从一个顶点开始，每次从剩余的顶点中加入一个顶点，该顶点与当前的生成树中的顶点的连边权重最小，直到得到一颗最小生成树；Kruscal算法从权重最小的边开始，每次从不在当前的生成树顶点中选择权重最小的边加入，直到得到一颗最小生成树，这两个算法都采用了 (64) 设计策略，且 （65） 。
 
  A.  分治
 
  B.  贪心
 
  C.  动态规划
 
  D.  回溯




 
 
相关试题     计算机软件知识 

  第53题    2013年下半年  
若有关系R(A,B,C,D,E)和S(B,C,F,G),则R与S自然联结运算后的属性列有(51)个，与表达式π1,3,6,7(σ3<6(RS))等价的SQL语句如下：..

  第62题    2023年下半年  
将高级语言源程序通过编译或解释方式进行翻译时，可以先生成与源程序等价的某种中间代码。以下关于中间代码的叙途中，正确的是（ ）。

  第54题    2012年下半年  
设有关系模式R (E，N，M, L, Q),其函数依赖集为F={ E—>N, EM—>Q,M—>L}。则关系模式R达到了（53)；该关系模式（54)。

 
知识点讲解
· 生成树
· 最小生成树
 
        生成树
        设图G=(V,E)是个连通图，当从图中任一个顶点出发遍历图G时，将边集E(G)分为两个集合，即A(G)和B(G)。其中A(G)是遍历时所经过的边的集合，B(G)是遍历时未经过的边的集合。G1=(V,A)是图G的子图，称子图G1为连通图G的生成树。
        图的生成树不是唯一的。选择不同的存储方式，从不同的顶点出发，可以得到不同的生成树。对于非连通图而言，每个连通分量中的顶点集和遍历时走过的边集一起构成若干棵生成树，把它们称为非连通图的生成树森林。
 
        最小生成树
        对于连通网来说，边是带权值的，生成树的各边也带权值，如果把生成树各边的权值总和称为生成树的权，则把权值最小的生成树称为最小生成树。
        构造生成树有多种算法，其中多数算法利用了最小生成树的MST性质：假设G=(V,E)是一个连通图，U是顶点集V的一个非空子集。若(u,v)是一条最小权值的边，其中u∈U,v∈V-U，则必存在一棵包含边(u,v)的最小生成树。
        ①普里姆算法。它的时间复杂度为O(n2)，与图中的边数无关，因此该算法适合于求边稠密的网中的最小生成树。
        ②克鲁斯卡尔算法。它的时间复杂度为O(elog2e)，与图中的顶点数无关，因此该算法适合于求边稀疏的网的最小生成树。



更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5
京公网安备 11010502032051号 | 营业执照
 Copyright ©2000-2025 All Rights Reserved
软考在线版权所有