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