大工15春《运筹学》在线作业3
大工 15 春《运筹学》在线作业 3
二、判断题（共 15 道试题，共 60 分。 ）
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. 错误 B. 正确 正确答案：B
12. 一个有 7 个点的连通图至少有 7 条边。 A. 错误 B. 正确 正确答案：A
13. 假如一个线性规划问题含有 7 个变量和 4 个约束， 则用动态规划方法求解时将划分为 4 个阶段，每个阶段的状态将由一个 7 维的向量组成。 A. 错误 B. 正确 正确答案：A
14. 作业的最迟开始时间是它的最迟结束时间减去该项作业的时间。 A. 错误 B. 正确 正确答案：B
15. 作业的最早结束时间为它的最早开始时间加上该项作业的计划时间。 A. 错误
B. 正确 正确答案：B
大工15春《运筹学》在线作业 3答案
