问答题


从下列的3道题（试题五至试题七）中任选1道解答。如果解答的试题超过1道，则题号小的1道解答有效。
试题五
阅读下列说明和C++代码，将应填入（n）处的字句写在答题纸的对应栏内。
【说明】
现欲构造一文/目录树，采用组合(Composite)设计模式来设计，得到的类图如5-1 所示：


图 5-1 类图



【参考答案】

（1）this->name （2）list* （3）NULL （4）this->name （5）&childList

<上一题 目录 下一题>
热门 试题

问答题
用回溯法求解此0-1 背包问题，请填充下面伪代码中(1)~(4)处空缺。 回溯法是一种系统的搜索方法，在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点已经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往假设已经设计了界函数，判断并剪枝那些即扩展了也不能得到最优解的结点。现在假设已经设计了BOUND（v,w,k,W）函数，其中v,w,k 和W 分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得最大的价值，若该价值小于等于当前已经得到的最优解，则该结点无需再扩展。 下面给出0-1 背包问题的回溯法伪代码。 函数参数说明如下： W：背包容量；n:物品个数；w:重量数组；v:价值数组；fw:获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。 变量说明如下： cw:当前的背包重量；cp:当前获得的价值;k:当前考虑的物品编号；Y:当前已获得的部分解。 BKNAP（W,n,w,v,fw,fp,X） 1 cw←cp←0 2 (1) 3 fp←-1 4 while true 5 while k≤n and cw+w[k] ≤W do 6 (2) 7 cp←cp+v[k] 8 Y[k] ←1 9 k←k+1 10 if k>n then 11 if fp12 fp←cp 13 fw←cw 14 k←n 15 X←Y 16 else Y(k) ←0 17 while BOUND(cp,cw,k,W) ≤fp do 18 while k≠0 and Y(k) ≠1 do 19 (3) 20 if k=0 then return 21 Y[k] ←0 22 cw←cw-w[k] 23 cp←cp-v[k 24 (4)
问答题
根据【说明】中的描述，给出图3-1 中A1 和A2 所对应的参与者。
相关试题