在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（）

A.在扩展结点处，先生成其所有的儿子结点(分支)

B.从当前的活结点表中选择上一个扩展结点。

C.为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值(限界)

D.根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。

此题为判断题(对，错)。

A、树中每个结点最多有 m个关键字

B、树中叶子结点的个数为 n+1

C、在B树上进行查找的过程是顺指针找结点和在结点内找关键字交叉进行的过程。

D、树中所有叶子结点都在同一层，并且不带任何信息

E、树中每个结点最多有 m-1个关键字

F、树中每个结点最多有 m+1个关键字

考虑表6—1的实例，假设有3个物品，背包容量为22。图6—6中是根据上述算法构造的搜索树，其中结点的编号表示了搜索树生成的顺序，边上的数字I／O分别表示选择／不选择对应物品。除了根结点之外，每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解，应该选择物品 (5) ，获得的价值为 (6)。

对于表6—1的实例，若采用穷举法搜索整个解空间，则搜索树的结点数为 (7) ，而用了上述回溯法，搜索树的结点数为 (8) .

此题为判断题(对，错)。

此题为判断题(对，错)。

A.求解目标相同

B.搜索方式相同

C.对扩展结点的扩展方式相同

D.都是一种在问题的解空间树T中搜索问题解的算法

【问题2】（7分）

考虑表4-1的实例，假设有3个物品，背包容量为22。图4-1中是根据上述算法构造的搜索树，其中结点的编号表示了搜索树生成的顺序，边上的数字1/0分别表示选择／不选择对应物品。除了根结点之外，每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解，应该选择物品 （5） ，获得的价值为 （6） 。

对于表4-1的实例，若采用穷举法搜索整个解空间，则搜索树的结点数为 （7） ，而用了上述回溯法，搜索树的结点数为 （8） 。