图的m着色问题可用（）法求解，其解空间树中叶子结点个数是（），解空间树中每个内结点的孩子数是（）。

题目

如果没有搜索结果或未解决您的问题，请直接联系老师获取答案。

相似问题和答案

第1题：

分支限界法在问题的解空间树中,按广度优先策略,从根结点出发搜索解空间树。()

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

正确答案:√

第2题：

输出二叉树中从每个叶子结点到根结点的路径。

参考答案：采用先序遍历的递归方法，当找到叶子结点*b时，由于*b叶子结点尚未添加到path中，因此在输出路径时还需输出b->data值。
　　[算法描述]
　　void AllPath(BTNode *b,ElemType path[],int pathlen)
　　{int i;
　　if (b!=NULL)
　　{if (b->lchild==NULL && b->rchild==NULL) //*b为叶子结点
　　{cout << " " << b->data << "到根结点路径:" << b->data;
　　for (i=pathlen-1;i>=0;i--)
　　cout << endl;
　　}
　　else
　　{path[pathlen]=b->data; //将当前结点放入路径中
　　pathlen++; //路径长度增1
　　AllPath(b->lchild,path,pathlen); //递归扫描左子树
　　AllPath(b->rchild,path,pathlen); //递归扫描右子树
　　pathlen--; //恢复环境
　　}
　　}// if (b!=NULL)
　　}//算法结束

第3题：

下列关于 n个结点的m阶B树的说法中,正确的是_______。

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

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

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

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

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

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

正确答案：CDE

第4题：

设T是正则二叉树，有6个叶子结点，那么树T的高度最多可以是(22)；最小可以是(23)；树T的内结点数是(24)。如果T又是Huffman最优树，且每个叶子结点的权分别是1，2，3，45，5，6，则最优树T的非叶子结点的权之和是(25)；权为1的叶子结点的高度是(26)。(注：树的根结点高度为1)

A．7

B．6

C．5

D．4

正确答案：B

第5题：

m阶B-树中的m是指(44)。

A．每个结点至少具有m棵子树

B．每个结点最多具有m棵子树

C．分支结点中包含的关键字的个数

D．m阶B-树的深度

正确答案：B
解析：m阶B-树中的m是指B-树中的每个结点最多具有m棵子树，应选择B。

第6题：

回溯法在问题的解空间树中,按扩展结点优先策略,从根结点出发搜索解空间树。()

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

正确答案:×

第7题：

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

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

正确答案：(5)2与3(6) 35(7) 15(8) 8
(5)2与3(6) 35(7) 15(8) 8 解析：本题实质上是一个0-1背包问题，该问题最优化的目标函数是
max∑vixi(xi=0，1)；
约束函数是：
∑pixi≤M(xi=0，1)。
0-1背包问题可用动态规划策略求得最优解，求解的递归式为
[*]
其中，nv[i][j]表示由前i项物品组合且价格不超过i的背包的总价值。问题最终要求的背包的总价值为nv[n][M]，根据上述递归式，可以很容易以自底向上的方式编写伪代码。
[问题1]中伪代码的第1行到第12行计算数组nv的元素值，第1行到第4行计算i为0或者j为0时nv[i]的值，对应递归式的第一种情况；第7行和第8行计算当j<pi时即不能选择mi时nv[i][j]的值，对应递归式的第二种倩况；第9行到第12行对应递归式的第三种情况，故根据递归式，空(1)的答案为nv[i-1][j]；nv[i-1][j-p[i]]+v[i]。伪代码的第13行到第19行求解哪些物品放入到背包中，物品项从后向前考虑，若nv[i][j]：nv[i-1][j]，表示物品mj没有放入背包中，即x[i]=0，故空(2)的答案为nv[i][j]=nv[i-1][j]。相反，若物品mj放入背包中，则x[i]=l，同时背包还能选择不超过l-p[i]的价格的物品，故空(3)的答案为j=j-p[i]。

第8题：

分支限界法与回溯法的相同点是()

A.求解目标相同

B.搜索方式相同

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

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

参考答案：D

第9题：

树的度是指( )。

A．数中结点的最大层次数

B．树内结点拥有子树的最人值

C．树的结点个数

D．叶子结点个数

正确答案：B
解析：树中结点拥有的子树个数称为结点的度，树的度是树内各结点的度的最大值，也就是树内结点拥有子树的最大值。

第10题：

M阶B树中的M是指(52)。

A．每个结点至少具有M棵子树

B．每个结点最多具有M棵子树

C．分支结点中包含的关键字的个数

D．M阶B树的深度

正确答案：B
解析：M阶B-树中的M是指B-树中每个结点至多具有M棵子树。

图的m着色问题可用（）法求解，其解空间树中叶子结点个数是（），解空间树中每个内结点的孩子数是（）。

题目

相似问题和答案

更多相关问题

相关内容