软考在线  |  计算机技术与软件专业技术资格(水平)考试   |   [请选择科目]
[ 成为 VIP会员 ]        登录  |  注册      我的  购物车
0
 
科目切换  联系我们 
    
  |   [请选择科目]

VIP:有效提升20分!  真题  历年真题 (可免费开通)/  分章知识真题/ 机考模拟平台/  最难真题榜/  自测/  攻打黄金十二宫/  真题检索/  真题下载/  真题词库
知识   必会知识榜/  最难知识榜/  知识点查询/      文档   学习计划/  精华笔记/  试题文档     纸质图书   《百科全书》HOT!!/         /        首页/  专区/  手机版/ 
免费智能真题库 > 历年试卷 > 系统分析师 > 2012年上半年 系统分析师 上午试卷 综合知识
  第59题      
  知识点:   管道   最小生成树
  关键词:   开发        章/节:   图论应用       
  错误率: 47%      难度系数:      

 
开发商需要在某小区9栋楼房之间敷设自来水管道,使各楼都能连通,又能使总成本最低。经勘察,各楼房之间敷设管道的路径和成本(单位:千元)如下图所示。

该项目的总成本至少需要(59)千元。
 
 
  A.  13
 
  B.  14
 
  C.  15
 
  D.  16
 
 
 确定 并 查看答案解析     知识点讲解  我要标记      有奖找茬      上一题        下一题 
 

 
  第57题    2011年上半年  
   52%
已知某山区六个乡镇C1,C2,…,C6之间的公路距离(公里数)如下表:

其中符号“表示两个乡镇之间没有直通公..
  第2题    2024年下半年  
   0%
开发商需要在某小区9栋楼房之间敷设自来水管道,使各楼都能连通,又能使总成本最低。经勘察,各楼房之间敷设管道的路径和成本(单..
  第56题    2011年上半年  
   75%
已知某项工程的作业明细表如下:

为了抢工期,.根据上表,该工程最快能完成的周数及其所需的项目总费用为(56)
   知识点讲解    
   · 管道    · 最小生成树
 
       管道
        管道是提供非结构化数据交换和实现任务同步的内核对象。每个管道有两个端口,一端用来读,另一端用来写。数据在管道中就像一个非结构的字节流,数据按照FIFO方式从管道中读出。一般EOS内核支持两类管道对象:
        (1)命名管道。具有一个类似于文件名的名字,像一个文件或设备出现在文件系统中,需要使用命名管道的任何任务或ISR都可以用误名字对其引用。
        (2)无名管道。一般动态创建,且必须使用创建时返回的描述符才可引用此类型的管道。
        通常,管道支持以下几种操作:创建和删除一个管道、读、写管道、管道控制、管道上的轮询。
 
       最小生成树
        一个连通且无回路的无向图称为树。在树中度数为1的节点称为树叶,度数大于1的节点称为分枝点或内节点。
        给定图T,以下关于树的定义是等价的:
        (1)无回路的连通图。
        (2)无回路且e=v-1,其中e为边数,v为节点数。
        (3)连通且e=v-1。
        (4)无回路且增加一条新边,得到一个且仅一个回路。
        (5)连通且删去任何一个边后不连通。
        (6)每一对节点之间有一条且仅一条路。
        在带权的图G的所有生成树中,树权最小的那棵生成树,称作最小生成树。
        求连通的带权无向图的最小生成树的算法有普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。
               普里姆算法
               设已知G=(VE)是一个带权连通无向图,顶点V={0,1,2,…,n-1}。设U是构造生成树过程中已被考虑在生成树上的顶点的集合。初始时,U只包含一个出发顶点。设T是构造生成树过程中已被考虑在生成树上的边的集合,初始时T为空。如果边(ij)具有最小代价,且iUjV-U,那么最小生成树应包含边(ij)。把j加到U中,把(ij)加到T中。重复上述过程,直到U等于V为止。这时,T即为要求的最小生成树的边的集合。
               普里姆算法的特点是当前形成的集合T始终是一棵树。因为每次添加的边是使树中的权尽可能小,因此这是一种贪心的策略。普里姆算法的时间复杂度为On2),与图中边数无关,所以适合于稠密图。
               克鲁斯卡尔算法
               设T的初始状态只有n个顶点而无边的森林T=(Vφ),按边长递增的顺序选择E中的n-1条安全边(uv)并加入T,生成最小生成树。所谓安全边是指两个端点分别是森林T里两棵树中的顶点的边。加入安全边,可将森林中的两棵树连接成一棵更大的树,因为每一次添加到T中的边均是当前权值最小的安全边,MST性质也能保证最终的T是一棵最小生成树。
               克鲁斯卡尔算法的特点是当前形成的集合T除最后的结果外,始终是一个森林。克鲁斯卡尔算法的时间复杂度为Oelog2e),与图中顶点数无关,所以较适合于稀疏图。
               
               求图的最小生成树
               例如,使用普里姆算法构造上图的最小生成树的过程如下5个图所示。
               
               使用普里姆算法构造最小生成树的过程(1)
               
               使用普里姆算法构造最小生成树的过程(2)
               
               使用普里姆算法构造最小生成树的过程(3)
               
               使用普里姆算法构造最小生成树的过程(4)
               
               使用普里姆算法构造最小生成树的过程(5)
   题号导航      2012年上半年 系统分析师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第59题    在手机中做本题
    在线人数   共计 9639人 在线 
    hahupaint@..     wlfzjj@yah..     zhangheqin..     dongjianta..     liangyun@g..     JIHN1985@1..
    mould-mast..     zhaoshen19..     leibaozhon..     xel790414@..     lishuangye..     404702028@..
    koujia2000..     qwert0804@..     shengzeng@..     lishuangye..     waiting_ou..     yutianlin1..
    jjfwolong@..     fxa2006@16..     SUNMDZJ@YA..     txdlcb@126..     zhangleiha..     sunshine-y..
    zhongqiang..     yhl@lit.ed..     704735462@..     css8000@16..     hans-wu@16..     420675445@..
    lingxiao02..     xuxiaolong..     yehong1986..     kingdomtow..     shepeng_ji..     lishunbook..
    liweijian1..     635097875@..     myshuangpi..     truelvoe19..     linsz.hn@1..     sjaiym@126..

本网站所有产品设计(包括造型,颜色,图案,观感,文字,产品,内容),功能及其展示形式,均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部,违者将依法追究责任,特此声明。
本站部分内容来自互联网或由会员上传,版权归原作者所有。如有问题,请及时联系我们。



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