p[x][y][k]=0； } }

for（k=1；k=0） （2） ；

if（ （3） ）p[x][y][k]=(p[x][y][k] ||p[x][y-b[k-1]][k-1]); } } } }

void write(){ /*确定最优解并输出*/ int x，y，temp，max=m; for（x=0；x<=m；x++）{ for（y=0;y<=m;y++）{ if( （4） ）{ temp=（5） ；

if（temp< max）max = temp; } } }

printf(\，max）, }

void main(){read();schedule();write();} 【问题1】 （9分）

根据以上说明和C代码，填充C代码中的空（1）～（5）。 【问题2】（2分）

根据以上C代码，算法的时间复杂度为（6）（用O符号表示）。 【问题3】（4分）

考虑6个作业的实例，各个作业在两台处理机上的处理时间如表4-1所示。该实例的最优解为（7），最优解的值（即最短处理时间）为（8）。最优解用（x1,x2,x3,x4,x5,x6）表示，其中若第i个作业在A上赴理，则xi=l，否则xi=2。如（1，1，1，1，2，2）表示作业1，2，3和4在A上处理，作业5和6在B上处理。

试题五

（共15分，在试题五和试题六中任选1题解答，如果两题都解答，则视试题五的解答有效。）

阅读下列说明和C++代码，将应填入（n）处的字句写在答题纸的对应栏内。 【说明】

某咖啡店当卖咖啡时，可以根据顾客的要求在其中加入各种配料，咖啡店会根据所加入的配料来计算费用。咖啡店所供应的咖啡及配料的种类和价格如下表所示。

【C++代码】 #include #include using namespace std;

const int ESPRESSO_PRICE = 25; const int DRAKROAST_PRICE = 20; const int MOCHA_PRICE = 10;

const int WHIP_PRICE = 8; class Beverage { //饮料 （1） ：string description; public:

（2） (){ return description; } （3） ; };

class CondimentDecorator : public Beverage { //配料 protected: （4） ; };

class Espresso : public Beverage { /／蒸馏咖啡 public:

Espresso () {description=\int cost（）{return ESPRESSO_PRICE; } };

class DarkRoast : public Beverage { //深度烘焙咖啡 public:

DarkRoast(){ description = \int cost(){ return DRAKROAST_PRICE; } };

class Mocha : public CondimentDecorator { ／／摩卡 public:

Mocha（Beverage*beverage）{ this->beverage=beverage; }

string getDescription(){ return beverage->getDescription()+\int cost(){ return MOCHA_PRICE+beverage->cost(); } };

class Whip :public CondimentDecorator { //奶泡 public:

Whip（Beverage*beverage） { this->beverage=beverage; }

string getDescription() {return beverage->getDescription()+\int cost() { return WHIP_PRICE+beverage->cost(); } };

int main() {

Beverage* beverage = new DarkRoast(); beverage=new Mocha( （5） ）; beverage=new Whip（ （6） ）;

cout<getDescription()<<\￥\return 0; }

编译运行上述程序，其输出结果为： DarkRoast, Mocha, Whip ￥38

试题六（共15分）

阅读下列说明和Java代码，将应填入（n）处的字句写在答题纸的对应栏内。

【说明】

某咖啡店当卖咖啡时，可以根据顾客的要求在其中加入各种配料，咖啡店会根据所加入的配料来计算费用。咖啡店所供应的咖啡及配料的种类和价格如下表所示。