【单选题】在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（）。A．回溯法B．分支限界法C．回溯法和分支限界法D．回溯法求解子集树问题
【单选题】在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（）。
A．回溯法
B．分支限界法
C．回溯法和分支限界法
D．回溯法求解子集树问题
参考答案和解析
深度优先
相关考题：
下列关于 n个结点的m阶B树的说法中,正确的是_______。 A、树中每个结点最多有 m个关键字B、树中叶子结点的个数为 n+1C、在B树上进行查找的过程是顺指针找结点和在结点内找关键字交叉进行的过程。D、树中所有叶子结点都在同一层，并且不带任何信息E、树中每个结点最多有 m-1个关键字F、树中每个结点最多有 m+1个关键字
关于分支限界法的搜索策略描述错误的是() A.在扩展结点处，先生成其所有的儿子结点(分支)B.从当前的活结点表中选择上一个扩展结点。C.为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值(限界)D.根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。
考虑表6—1的实例，假设有3个物品，背包容量为22。图6—6中是根据上述算法构造的搜索树，其中结点的编号表示了搜索树生成的顺序，边上的数字I／O分别表示选择／不选择对应物品。除了根结点之外，每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解，应该选择物品 (5) ，获得的价值为 (6)。对于表6—1的实例，若采用穷举法搜索整个解空间，则搜索树的结点数为 (7) ，而用了上述回溯法，搜索树的结点数为 (8) .
【问题2】（7分）考虑表4-1的实例，假设有3个物品，背包容量为22。图4-1中是根据上述算法构造的搜索树，其中结点的编号表示了搜索树生成的顺序，边上的数字1/0分别表示选择／不选择对应物品。除了根结点之外，每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解，应该选择物品 （5） ，获得的价值为 （6） 。对于表4-1的实例，若采用穷举法搜索整个解空间，则搜索树的结点数为 （7） ，而用了上述回溯法，搜索树的结点数为 （8） 。
用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h（n），则回溯法所需的计算空间通常为（）
关于回溯算法和分支限界法，以下（）是不正确描述。A、回溯法中，每个活结点只有一次机会成为扩展结点B、分支限界法中，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子加入活结点表中C、回溯法采用深度优先的结点生成策略D、分支限界法采用广度优先或最小耗费优先（最大效益优先）的结点生成策略
关于回溯搜索法的介绍，下面（）是不正确描述。A、回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解B、回溯法是一种既带系统性又带有跳跃性的搜索算法C、回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯D、回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径
单选题关于回溯算法和分支限界法，以下（）是不正确描述。A回溯法中，每个活结点只有一次机会成为扩展结点B分支限界法中，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子加入活结点表中C回溯法采用深度优先的结点生成策略D分支限界法采用广度优先或最小耗费优先（最大效益优先）的结点生成策略
单选题关于回溯搜索法的介绍，下面（）是不正确描述。A回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解B回溯法是一种既带系统性又带有跳跃性的搜索算法C回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯D回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径
填空题用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h（n），则回溯法所需的计算空间通常为（）
填空题图的m着色问题可用（）法求解，其解空间树中叶子结点个数是（），解空间树中每个内结点的孩子数是（）。