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

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

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

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

 
  第56题    2022年上半年  
   59%
某乡有7个小山村A~G,村与村之间原有小路可加宽修建公路的线路如下图所示(路边的数字表示路长的公里数)。为实现村村通公路,修..
  第55题    2022年上半年  
   31%
某乡有7个小山村A~G,村与村之间原有小路可加宽修建公路的线路如下图所示(路边的数字表示路长的公里数)。为实现村村通公路,修..
  第2题    2024年下半年  
   0%
开发商需要在某小区9栋楼房之间敷设自来水管道,使各楼都能连通,又能使总成本最低。经勘察,各楼房之间敷设管道的路径和成本(单..
   知识点讲解    
   · 管道    · 最小生成树
 
       管道
        管道是提供非结构化数据交换和实现任务同步的内核对象。每个管道有两个端口,一端用来读,另一端用来写。数据在管道中就像一个非结构的字节流,数据按照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题    在手机中做本题
    在线人数   共计 15245人 在线 
    kingman_we..     lxxhhss@ya..     ievtao@soh..     qibingshan..     liuch_1126..     szromeo@16..
    zhandl@263..     caohzou@12..     yzyingze@1..     zzx9920@ya..     sdwfr1973@..     54zephyrsu..
    xgf-1@263...     yxq2007417..     lhb_freehe..     azyzb@126...     xy98988@16..     rnchen_200..
    jmsiti163@..     zhoulingsu..     yaofan7097..     haiqin28@h..     luhaibin00..     cxqchen@ho..
    guoshibo@1..     jinlanzi85..     6fw1@163.c..     xuexiuli12..     juan815@sh..     vvvd9681@t..
    mei222@QQ...     baoynky@16..     zoujie@mai..     Joanlodge@..     xueyanghua..     dzzz0305@1..
    gzjinding@..     jxncfengti..     andrelwei@..     malumitsu@..     domgfangru..     junhong044..

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



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