大工14秋《运筹学》在线作业3作业及答案
一、单选题（共 5 道试题，共 40 分。） 得分：40
V
1. 一个有8个点的连通图至少有（ ）条边。
A. 4
B. 5
C. 6
D. 7
满分：8 分 得分：8
2. 假设对于一个动态规划问题，应用顺推法及逆推解法得出的最优解分别为E和F，则有（ ）。
A. E>F
B. E C. E=F D. 不确定 满分：8 分 得分：8 3. 下列算法中，（ ）是用来计算两节点之间的最短路的。 A. 狄克斯特拉算法 B. 踏石法 C. 清华算法 D. 位势法 满分：8 分 得分：8 4. 动态规划是用来解决（ ）决策过程最优化问题的一种方法。 A. 多阶段问题 B. 分配问题 C. 运输问题 D. 最短路问题 满分：8 分 得分：8 5. 下列说法不正确的为（ ）。 A. 完成各个作业需要时间最长的路线称为关键路线 B. 关键路线上的作业称为关键作业 C. 所有关键作业的总时差为0 D. 以上说法均不正确 满分：8 分 得分：8 二、判断题（共 15 道试题，共 60 分。） 得分：60 V 1. 总时差是指在不影响到各项紧后作业最迟开工的条件下，该作业可以推迟开工的最大限度。 A. 错误 B. 正确 满分：4 分 得分：4 2. 当网络中不存在任何增广链时，网络达到最大流状态。 A. 错误 B. 正确 满分：4 分 得分：4 3. 动态规划问题的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段决策问题。 A. 错误 B. 正确 满分：4 分 得分：4 4. 狄克斯特拉算法可以用来求解一个节点到所有节点之间的最短路。 A. 错误 B. 正确 满分：4 分 得分：4 5. 应用狄克斯特拉算法n 次 ，可以求出所有点间的最短路。 A. 错误 B. 正确 满分：4 分 得分：4 6. 具有 n个节点的树的边恰好为n+1条。 A. 错误 B. 正确 满分：4 分 得分：4 7. 一个动态规划问题若能用网络表达，则节点代表各阶段的状态值，各条弧代表了可行的方案选择。 A. 错误 B. 正确 满分：4 分 得分：4 8. 动态规划问题的计算中较多采用逆序算法。 A. 错误 B. 正确 满分：4 分 得分：4 9. 作业的最早结束时间为它的最早开始时间加上该项作业的计划时间。 A. 错误 B. 正确 满分：4 分 得分：4 10. 割的容量是指所有割集中容量之和为最小的一个割集。 A. 错误 B. 正确 满分：4 分 得分：4 11. 最优化原理认为“无论初始状态和初始决策如何，对于前面决策所形成的状态而言，余下的决策序列必构成最优策略。” A. 错误 B. 正确 满分：4 分 得分：4 12. 求网络最大流的标号算法的基本思想是指寻找增广链，改善流量分布；再重复，直到不存在任何增广链为止。 A. 错误 B. 正确 满分：4 分 得分：4 13. 树是无圈连通图中边数最多的，在树图上只要任意再加上一条边，一定会出现圈。 A. 错误 B. 正确 满分：4 分 得分：4 14. 网络的最大流是指能够通过网络的最大可行流。 A. 错误 B. 正确 满分：4 分 得分：4 15. 在狄克斯特拉算法中，每次迭代可以使多个节点同时获得永久标记。 A. 错误 B. 正确 满分：4 分 得分：4
大工14秋《运筹学》在线作业3作业及答案
