大工15春《运筹学》在线作业3

大工15春《运筹学》在线作业3

单选题 判断题

一、单选题（共 5 道试题，共 40 分。）

1. 假设对于一个动态规划问题，应用顺推法及逆推解法得出的最优解分别为E和F，则有（ ）。 A. E>F B. E-----------------选择：C

2. 网络的最大流应（ ）最小割集容量。 A. 等于 B. 不大于 C. 不小于 D. 不一定

-----------------选择：A

3. 动态规划是用来解决（ ）决策过程最优化问题的一种方法。 A. 多阶段问题 B. 分配问题 C. 运输问题 D. 最短路问题

-----------------选择：A 4. 下列说法不正确的为（ ）。

A. 完成各个作业需要时间最长的路线称为关键路线 B. 关键路线上的作业称为关键作业 C. 所有关键作业的总时差为0 D. 以上说法均不正确

-----------------选择：D 5. 下列算法中，（ ）是用来计算两节点之间的最短路的。 A. 狄克斯特拉算法 B. 踏石法 C. 清华算法 D. 位势法

-----------------选择：A 大工15春《运筹学》在线作业3

单选题 判断题

二、判断题（共 15 道试题，共 60 分。）

谋学网www.mouxue.com

1. 应用狄克斯特拉算法n 次 ，可以求出所有点间的最短路。 A. 错误 B. 正确

-----------------选择：A

2. 割的容量是指所有割集中容量之和为最小的一个割集。 A. 错误 B. 正确

-----------------选择：A

3. 网络的最大流是指能够通过网络的最大可行流。 A. 错误 B. 正确

-----------------选择：B

4. 对于一个动态规划问题，应用顺推或是逆推解法求解可能会得出不同的最优解。 A. 错误 B. 正确

-----------------选择：A 5. 没有自环的图称为简单图。 A. 错误 B. 正确

-----------------选择：A

6. 树是无圈连通图中边数最多的，在树图上只要任意再加上一条边，一定会出现圈。 A. 错误 B. 正确

-----------------选择：B

7. 具有 n个节点的树的边恰好为n+1条。 A. 错误 B. 正确

-----------------选择：A

8. 最优化原理认为“无论初始状态和初始决策如何，对于前面决策所形成的状态而言，余下的决策序列必构成最优策略。” A. 错误 B. 正确

-----------------选择：B

9. 树的任意两点之间有且仅有一条路。 A. 错误 B. 正确

-----------------选择：B

10. 动态规划问题中，定义状态时应保证在各个阶段中所做决策的相互独立性。 A. 错误 B. 正确

-----------------选择：B

11. 当网络中不存在任何增广链时，网络达到最大流状态。 A. 错误

谋学网www.mouxue.com

B. 正确

-----------------选择：B

12. 一个有7个点的连通图至少有7条边。 A. 错误 B. 正确

-----------------选择：A

13. 假如一个线性规划问题含有7个变量和4个约束，则用动态规划方法求解时将划分为4个阶段，每个阶段的状态将由一个7维的向量组成。 A. 错误 B. 正确

-----------------选择：A

14. 作业的最迟开始时间是它的最迟结束时间减去该项作业的时间。 A. 错误 B. 正确

-----------------选择：B

15. 作业的最早结束时间为它的最早开始时间加上该项作业的计划时间。 A. 错误 B. 正确

-----------------选择：B