超星 - 第6章分支限界法客观题 - 查题吧

单选题

分支限界法与回溯法的不同点体现在哪些方面？‍（1）求解目标不同，分支限界法可求最优解或满足条件的一个解，而回溯法可求最优解或满足条件的所有解‍（2）搜索方式不同，回溯法是以深度优先状态生成树法搜索解空间树，分支限界法则以广度优先或最小耗费（最大效益）优先的状态生成树法搜索解空间树。‍（3）同一个问题在使用回溯法或分支限界法时，该问题的解空间树的结构不同‍（4）回溯法与分支限界法，构造最优解的方式不同。‍从上述选项中找出答案。

A. （1）（2）（4）
B. （2）（3）（4）
C. （1）（3）（4）
D. （1）（2）（3）

单选题

分支限界法中，扩展出的孩子结点在入队时，存储该孩子结点的父结点的地址和左孩子标志。其目的是什么？

A. 为了方便判定是否已搜索到达叶子层
B. 为了构造最优解
C. 为了计算最优值
D. 为了确定其孩子结点在队列中的位置

单选题

在队列式分支限界法中，叶子结点不加入队列。而在优先队列式分支限界法中，叶子结点通常要加入到优先队列中。有下列2个解释：（1）队列式分支限界法，活结点在队列中的顺序是按照搜索解空间树时扩展出该结点的先后顺序存放，每次从队首取出一个活结点成为新的扩展结点。扩展结点扩展出的儿子结点是叶子结点时，会将该叶子结点的值同当前最优值比较，检查更新最优值，叶子结点并不进入队列，等队列为空时，搜索结束，记录的当前最优值就是问题最优值。（2）优先队列式分支限界法中，当优先级的定义是限界函数时，扩展出的叶子结点进入队列，这种做法主要是为了让搜索过程提前结束。也就是当从优先队列中取出一个活结点是叶子结点时，意味着现在优先队列中剩余的所有活结点其优先级都不大于该叶子结点的优先级，叶子结点的优先级等于最优值，算法结束，无论优先队列是否为空。根据其正确与否，给出答案

A. （1）正确，（2）错误
B. （1）错误，（2）错误
C. （1）正确，（2）正确
D. （1）错误，（2）正确

单选题

下面是优先队列式分支限界算法解0-1背包问题的部分主代码，分析代码将【】内的代码补齐。TempleteTypepknap::MaxKnapsack(){//优先队列分支限界法，返回最大价值，最优解bestxH=newMaxHeap>(1000);//定义最大堆的容量为1000bestx=newint[n+1];inti=1;E=0; cw=cp=0;Typepbestp=0;Typepup=Bound(1）；while(【1】){Typewwt=cw+w[i];if(wt<=c){ if(cp+p[i]>bestp) 【2】； AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}up=Bound(i+1);if(up>bestp)AddLiveNode(up,cp,cw,false,i+1);//从优先队列中取下一个扩展节点HeapNodeN;H->DeleteMax(N);E=N.ptr;cw=N.weight;cp=N.profit;up=N.upprofit;i=N.level;}//构造最优解for（intj=n;j>0;j--）{bestx[j]=E->lchild; E=E->parent;}returncp;}

A. 【1】i!=n+1 , 【2】cw=cw+w[i]
B. 【1】i<n , 【2】besp=cp+p[i]
C. 【1】i<n+1 , 【2】besp=cp+p[i]
D. 【1】i!=n , 【2】cw=cw+w[i]

判断题

回溯法与分支限界法的空间复杂度是相同的，都是O(h(n)), h(n)是解空间树的深度。

A. 对
B. 错

判断题

优先队列式分支限界法按照优先队列中规定的优先级，选取优先级最高的结点，成为当前扩展结点。

A. 对
B. 错

1