算法分析与设计第六章测试_智慧树知到答案2021年

第六章 分支限界法：本章主要讲授分支限界法的基本思想、实现方式、算法框架和算法特点，学习如何使用分支限界法求解装载问题，学习求解算法的设计与实现。6.1分支限界法概述:学习分支限界法的基本思想、实现方式、算法框架和算法特点。
6.2分支限界法之装载问题（上）:学习装载问题的描述以及使用队列式分支限界法求解该问题的算法设计。
6.3分支限界法之装载问题（下）:学习使用队列式分支限界法求解装载问题的算法实现和改进。

[单选题]分支限界法采用的搜索策略是( )。
深度优先搜索
递归搜索
启发式搜索
广度优先搜索
答案：广度优先搜索
[多选题]根据活结点表的组织方式不同，分支限界法包括( )等形式。
单调队列式分支限界法
优先队列式分支限界法
队列式分支限界法
二叉树式分支限界法
栈式分支限界法[多选题]关于回溯法和分支限界法，以下说法正确的是( )。
回溯法通常用于求满足约束条件的所有解
在回溯法中，活结点的所有可行子结点均被遍历后才从栈中弹出
在分支限界法中，每个结点只有一次成为扩展结点的机会
分支限界法通常用于求满足约束条件的一个解或特定意义下的最优解[多选题]应用分支限界法的三个关键问题包括( )。
如何限制搜索的层次
如何设计合适的剪枝函数
如何组织活结点表
如何确定最优解的解向量[多选题]关于分支限界法的基本思想，下列描述正确的是( )。
从活结点表中取下一结点成为当前扩展结点，并重复结点扩展过程
活结点一旦成为扩展结点，就一次性产生其所有子结点
那些导致不可行解或导致非最优解的子结点被舍弃，其余子结点被加入活结点表中
一直持续到找到所求的解或活结点表为空时为止
每一个活结点只有一次机会成为扩展结点[判断题]优先队列式分支限界法将活结点表组织成一个优先队列，按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。
对
错[单选题]队列具有( )的性质。
先进先出
先进后出
仅进不出
进出无序[判断题]使用队列式分支限界法求解装载问题时，每次从队列Q中取出队首元素作为当前扩展结点。取队首元素后，判断当前Q是否为空。如Q非空，则将尾部标记-1加入Q，算法开始处理下一层的活结点。
错
对[判断题]如果一个给定装载问题有解，则采用的装载策略为：首先将第一艘轮船尽可能装满；再将剩余的集装箱装上第二艘轮船。
错
对[单选题]在装载问题中，如果右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量，则当( )时，可将其右子树剪去。
r>=bestw
r