山区某乡的6个村之间有山路如下图所示，其中的数字标明了各条山路（公里）。
乡政府决定沿山路架设电话线。为实现村村通电话，电话线总长至少为（ ）公里。
- A.11
- B.14
- C.18
- D.33
正确答案及解析
正确答案
解析
本题需要在给定的图上寻找最小支撑树。
图由若干个结点以及结点之间的连线组成，每条连线上标记了权数（本题为长度）。
最小支撑树实际上是其中的一个子图，它包括所有的结点以及部分连线，这些连线需要连接所有的结点，但其总权数（长度）最小。
从本题应用看，就是要在上述山路图中确定部分山路，使其能连接6个村，又能使总长度最短。
最小支撑树的求解方法：先选择最短的一条线（如有多条，可以任选一条），它已经连接了2个点。从这2点出发，再找出能连接其他一个点的最短线（如有多条，可以任选一条）。这样，就已经用2条线连接了3个点。依此类推，逐步做下去，连线也逐步增多，连接的点也逐步增多，直到所有的点都连上为止。这样求出的若干条连线以及所有结点就组成了最小支撑树。
本题求出的一种最小支撑树如下：
其连线的总长度等于14公里，连接了6个村。
在同一个图中，最小支撑树的方案可能有多个，但其连线的总长度是相等的。
这是运筹学求解最优问题的普遍原则：最优值如果有，则必是唯一的，但达到最优值的方案可能不止一个。
包含此试题的试卷
你可能感兴趣的试题
E-mail地址由分隔符“（）”分为前后两部分，分别指明用户名及邮件
-
- A.//
- B.\\
- C.@
- 查看答案
某 html 文档中有如下代码，则在浏览器中打开该文档时显示为（ ）。
＜form>
Listl:
＜input type="text" name="List1" />
＜br / >
List2:
＜input type="text" name="List 2 " />
＜ /form>
-
- A.见图A
- B.见图B
- C.见图C
- D.见图D
- 查看答案
设有商品关系P（商品名，条形码，供应商号，价格，数量）， “条形码”唯一标识关系P中的每一个元组，商品名不能为空，供应商号是关系P的外键。另有供应商关系S（供应商号，供应商名，地址，电话）。关系 P 中的商品名是唯一的。建立商品关系 P 的 SQL语句如下所示：
CREATE TABLE P( 商品名CHAR(30)（ ），
条形码CHAR(30) （ ） ，
供应商号 CHAR(5) ，
价格 CHAR(20) ，
数量CHAR(20)
（ ）(供应商号) REFERENCES S(供应商号));
查询供应商及价格小于等于 2500 元且大于等于 1280 元的“电冰箱”的数量的SQL语句为：
SELECT商品名，供应商名，价格，数量
FROM P
WHERE商品名= ’电冰箱’ AND （ ） ;
将供应商号“12021”所供应的商品价格上涨3％的SQL语句为：
UPDATE P
（ ）
WHERE 供应商号= ’12021’;
查询供应商地址包含“西安”的供应商名及电话的SQL语句为：
SELECT供应商名，电话
FROM S
WHERE （ ）;
-
- A.NULL
- B.UNIQUE
- C.NOT NULL
- D.NOT NULL UNIQUE
- 查看答案
函数f()、g()的定义如下所示。已知调用f时传递给其形参x的值是1，若以传值方式调用g，则函数f的返回值为（ ）；若以传引用方式调用g，则函数f的返回值为（ ）。
-
- A.3
- B.4
- C.6
- D.7
- 查看答案
-
- A.见图A
- B.见图B
- C.见图C
- D.见图D
- 查看答案