A.4
B.5
C.6
D.7
A ) 4
B ) 5
C ) 6
D ) 7
A. 编译时将产生错误;
B. 编译时正确,运行时将产生错误;
C. 输出0;
D. 输出null。
0-1背包问题可以描述为:有n个物品,对i=1,2,…,n,第i个物品价值为vi ,重量为wi(vi,和wi为非负数),背包容量为W(W为非负数),选择其中一些物品装入背包,使装入背包物品的总价值最大,,且总重量不超过背包容量,即,其中,xi∈{0,1},xi=0表示第i个物品不放入背包,xi=1表示第i个物品 放入背包。
【问题1】(8分)
用回溯法求解此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 fp<cp then
12 fp ← cp
13 fw ← ew
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)
某跑车36s内(0.01h)速度从0加速到228km/h的数据如下表所示
用矩形法估算该跑车在36s内速度达到228km/h时行进的路程.
下面程序的执行结果是()。 #include<iostream> using namespace std; class building { public: building() {} building(unsigned stories, float breadths, float lengths) { story = stories; breadth = breadths; length = lengths;} void getstory(void) { cout<<"story is:"<<story<<endl;} void getarea(void) { area = length*breadth*story;cout<<"area is:"<<area<<endl;} private: unsigned story; float length; float breadth; float area; }; void main(void) { building b1,b2;building b3(10u,16.6,58.8); b1.getstory(); b1.getarea(); b2.getstory(); b2.getarea(); b3.getstory(); b3.getarea();}
A.story is:0 area is:0 story is:0 area is:0 story is:10 area is:9760.8
B.story is:null area is:null story is:null area is:null story is:10 area is:9760.8
C.前两个对象输出的结果是不定的,后一个对象的结果正确
D.前两个对象没有初值,因此程序编译时出错
阅读下列说明,回答问题1至问题3,将解答填入的对应栏内。
[说明]
场景法是黑盒测试中重要的测试用例设计方法。目前多数软件系统都是用事件触发来控制业务流程,事件触发时的情景便形成了场景,场景的不同触发顺序构成用例。场景法通过场景描述业务流程(包括基本流(基本流程)和备选流(分支流程)),设计用例遍历软件系统功能,验证其正确性。
下面是对网上银行支付交易系统的基本流和备选流的描述:
基本流A:
备选流:
注:假定输入的银行卡号是正确的:不考虑备选流内循环情况。
使用场景法设计测试用例,指出所涉及到的基本流和备选流。基本流用字母A表示,备选流用题干中描述对应编号表示。
请针对问题1设计的测试用例,依次将银行卡号、初次输入密码、最终输入密码、卡内余额、银行卡可支付额度等信息填入下述测试用例表中。表中行代表各个测试甩例,列代表测试用例的输入值,用V表示有效数据元素,I表示无效数据元素,n/a表示不适用,例如C01表示“成功支付”用例。
测试用例表
在上述系统中,假设银行卡号只能输入0~9的数字,请参考下表,给出用边界值法检查卡号字符合法性的关键测试数据(字符或ASCⅡ值)。
请帮忙给出每个问题的正确答案和分析,谢谢!
阅读下列说明,回答问题1至问题3,将解答填入的对应栏内。
[说明]
场景法是黑盒测试中重要的测试用例设计方法。目前多数软件系统都是用事件触发来控制业务流程,事件触发时的情景便形成了场景,场景的不同触发顺序构成用例。场景法通过场景描述业务流程(包括基本流(基本流程)和备选流(分支流程)),设计用例遍历软件系统功能,验证其正确性。
下面是对网上银行支付交易系统的基本流和备选流的描述:
基本流A:
备选流:
注:假定输入的银行卡号是正确的:不考虑备选流内循环情况。
使用场景法设计测试用例,指出所涉及到的基本流和备选流。基本流用字母A表示,备选流用题干中描述对应编号表示。
请针对问题1设计的测试用例,依次将银行卡号、初次输入密码、最终输入密码、卡内余额、银行卡可支付额度等信息填入下述测试用例表中。表中行代表各个测试甩例,列代表测试用例的输入值,用V表示有效数据元素,I表示无效数据元素,n/a表示不适用,例如C01表示“成功支付”用例。
测试用例表
在上述系统中,假设银行卡号只能输入0~9的数字,请参考下表,给出用边界值法检查卡号字符合法性的关键测试数据(字符或ASCⅡ值)。
请帮忙给出每个问题的正确答案和分析,谢谢!