运筹学2023章节测试答案

我的答案：×

4 【判断题】任意一个图都是自身的子图。

我的答案：√

第二十五讲 最小支撑树与最短路问题

1 【单选题】以下叙述中不正确的是（ ）。

A、树的点数等于边数加1

B、树的任意两点间只有一条链

C、任何不连通图都不是树

D、树是边数最少的图

我的答案：D

2 【单选题】n 个结点的树，共有( )条边（ ）。

A、n 条边

B、n-1 条边

C、n+1 条边

D、2n 条边

我的答案：B

3 【单选题】下图中的最小树所有边的权数之和为（ ）。

A、26

B、24

C、23

D、20

我的答案：C

4 【多选题】求图的最小支撑树，主要有哪些方法

A、“避圈法”Kruskal算法

B、 “破圈法”(管梅谷算法)

C、Dijkstra标号法

D、 Warshall- Floyd算法

我的答案：AB

5 【判断题】Dijkstra标号法可以求任意两点之间的最短路。

我的答案：×

6 【判断题】图的最小支撑树一定唯一。

我的答案：×

第二十六讲 最大流问题

1 【单选题】下列说法正确的是

A、割集是子图

B、割量等于割集中弧的流量之和

C、割量大于等于最大流量

D、割量小于等于最大流量

我的答案：排除D

2 【单选题】下列说法错误的是

A、容量不超过流量

B、流量非负

C、容量非负

D、发点流出的合流等于收点流入的合流

我的答案：排除D

3 【单选题】甲乙两城市之间存在一公路网络，为了判断两小时内能否有9000辆车从甲城到乙城，应借助( )。

A、树的生成法

B、求最大流法

C、求最小生成树法

D、求最短路法

我的答案：B

4 【单选题】求最大流的方法有

A、 “避圈法”Kruskal算法

B、Ford—Fulkerson法

C、Dijkstra标号法

D、Warshall- Floyd算法

我的答案：B

5 【判断题】可行流是最大流的充要条件是不存在发点到收点的增广链。

我的答案：√

6 【判断题】最大流等于最大流量。

我的答案：X

第二十七讲 最小费用最大流问题

1 【单选题】下列说法正确的是

A、最大流量等于最大割量

B、最大流量等于最小割量

C、任意流量不小于最小割量

D、最大流量不小于任意割量

我的答案：D

2 【单选题】关于最大流量问题，以下叙述( )正确。

A、一个容量网络的最大流是唯一确定的

B、达到最大流的方案是唯一的

C、当用标号法求最大流时，可能得到不同的最大流方案

D、当最大流方案不唯一时，得到的最大流量相同。

我的答案：D

3 【多选题】关于增广链，以下叙述( )正确。

A、 增广链是一条从发点到收点的有向链，这条链上各条边的方向必一致。

B、 增广链是一条从发点到收点的有向链，这条链上各条边的方向可不一致。

C、 增广链上与发点到收点方向一致的边必须是非饱和边，方向相反的边必须是流量大于零的边。

D、 增广链上与发点到收点方向一致的边必须是流量小于容量的边，方向相反的边必须是流量等于零的边。

我的答案：BC

4 【判断题】计算最小费用最大流，要同时将最短路问题与最大流问题的算法结合起来。

我的答案：√

5 【判断题】某个网络最小费用最大流与这个网络的最大流相比较，它们的最大流量值相等，但流量不相同。

我的答案：√

★《布宫号》提醒您：民俗信仰仅供参考，请勿过度迷信！