问答题阅读下列说明和算法，回答问题1和问题2。 【说明】 算法2-1是用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号，则给出相应的提示信息，如下所示： 文件 提示信息 (1+2) abc) 缺少对应左括号：第2行，第4列 ((def)gx) 缺少对应左括号：第3行，第10列 (((h) ij)(k (1ml) 缺少对应右括号：第5行，第4列；第4行，第1列 在算法2-1中，stack为一整数栈。算法中各函数的说明见表4。 {{B}}表4{{/B}} 函数名 函数功能 push (int i) 将整数i压人栈stack中 pop( ) stack的栈顶元素出栈 empty( ) 判断stack栈是否为空。若为空，函数返回1，否则函数返回0 nextch( ) 读取文本文件中的下—个字符，井返回该字符的ASCII值，将字符所在的行号以及字符在行中的位置分别存储到变量row和col中，若遇到文件结束符，则将变量EOF置为true kind (char ch) 判断字符ch是左括号还是右括号，若是左括号，函数返回1，若是右括号，函数返回2，若两者都不是，函数返回。【算法2-1】将栈stack 置空，置EOF为false ch ＜ - nextch(); while( not EOF) k ＜ - kind(CH); if(k=={{U}} (1) {{/U}}) push({{U}} (2) {{/U}});push({{U}} (3) {{/U}}); elseif(k=={{U}} (4) {{/U}}) if(not empty()) pop( ) ;pop( ); else 显示错误信息(缺少对应左括号或右括号)； 显示行号row；显示列号col； endif endif ch ＜ - nextch( ); endwhile if(not empty()) 显示错误信息(缺少对应左括号或右括号)； while(not empty()) row ＜ - pop() ; col ＜- pop(); 显示行号row; 显示列号col; endwhile endif 为了识别更多种类的括号，对算法2-1加以改进后得到算法2-2。算法2-2能够识别圆括号、方括号和花括号(不同类型的括号不能互相匹配)。改进后，函数kind(char ch)的参数及其对应的返回值见表5。　　　　　　　　　　　　　　　{{B}}表五{{/B}} ch ( ) { } ［ ］ 其他 返回值 1 2 3 4 5 6 0 【算法2-2】 将栈stack置空，置EOF为false ch＜ -nextch()； while(not EOF) k ＜-kind(ch)； if( k ＞0) if({{U}} 判断条件1 {{/U}}) push({{U}} (5) {{/U}});push({{U}} (6) {{/U}});push({{U}} (7) {{/U}}); elseif({{U}} 判断条件2 {{/U}}and{{U}} 判断条件3 {{/U}}) pop() ;pop() ;pop(); else 显示行号row； 显示列号col； endif endif ch ＜ - nextch();endwhileif(not empty( ) ) 显示错误信息(缺少对应左括号或右括号)； while( not empty( ) ) pop( ); row←pop( ); col←pop( ); 显示行号row；显示列号col； endwhileendif

问答题阅读下列说明，根据要求回答下列问题。[说明]某地区举行篮球比赛，需要开发一个比赛信息管理系统来记录比赛的相关信息。[需求分析结果]1．登记参赛球队的信息。记录球队的名称、代表地区、成立时间等信息。系统记录球队的每个队员的姓名、年龄、身高、体重等信息。每个球队有一个教练负责管理球队，一个教练仅负责一个球队。系统记录教练的姓名、年龄等信息。2．安排球队的训练信息。比赛组织者为球队提供了若干个场地，供球队进行适应性训练。系统记录现有的场地信息，包括场地名称、场地规模、位置等信息。系统可为每个球队安排不同的训练场地，如表8-6所示。系统记录训练场地安排的信息。表8-6训练安排表球队名称场地名称训练时间解放军一号球场2008-06-0914:00～18:00解放军一号球场2008-06-1209:00～12:00解放军二号球场2008-06-1114:00～18:00山西一号球场2008-06-1009:00～12:003．安排比赛。该赛事聘请了专职裁判，每场比赛只安排一个裁判。系统记录裁判的姓名、年龄、级别等信息。系统按照一定的规则，首先分组，然后根据球队、场地和裁判情况，安排比赛(每场比赛的对阵双方分别称为甲队和乙队)。记录参赛球队、比赛时间、比分、场地名称等信息，如表8-7所示。表8-7　比赛安排表　　　　　　　　　　　　　　　　　　　　　　　A组：甲队——乙队场地名称比赛时间裁判比分解放军—北京一号球场2008-06-1715:00李大明天津—山西一号球场2008-06-1719:00胡学梅　　　　　　　　　　　　　　　　　　　　　　　B组：甲队——乙队场地名称比赛时间裁判比分上海—安徽二号球场2008-06-1715:00丁鸿平山东—辽宁二号球场2008-06-1719:00郭爱琪4．所有球员、教练和裁判可能出现重名情况。[概念模型设计]根据需求阶段收集的信息，设计的实体联系图和关系模式(不完整)如下。1．实体联系图(如图8-17所示)2．关系模式●教练(教练编号，姓名，年龄)●队员(队员编号，姓名，年龄，身高，体重，(a))●球队(球队名称，代表地区，成立时间，(b))●场地(场地名称，场地规模，位置)●训练记录((c))●裁判(裁判编号，姓名，年龄，级别)●比赛记录((d))

问答题[说明][算法4-1]的功能是：用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号，则给出相应的提示信息，如图4-18所示。在[算法4-1]中，stack为一整数栈。算法中各函数的说明如表4-16所示。{{B}}表4-16各函数的功能说明表{{/B}}{{B}}函数名{{/B}}{{B}}函数功能{{/B}}push(inti)将整数i压入栈stack中pop()stack的栈顶元素出栈empty()判断stack栈是否为空．若为空，函数返回1，否则函数返回0nextch()读取文本文件中的下一个字符，并返回该字符的ASCII值，将字符所在的行号以及字符在行中的位置分别存储到变量row和col中，若遇到文件结束符，则将变量EOF置为truekind(charch)判断字符ch是左括号还是右括号，若是左括号，函数返回1；若是右括号，函数返回2；若两者都不是，函数返回0[算法4-1]将栈stack置空，置EOF为false为了识别更多种类的括号，对[算法4-1]加以改进后得到[算法4-2]。[算法4-2]能够识别圆括号、方括号和花括号(不同类型的括号不能互相匹配)。改进后，函数kind(charch)的参数及其对应的返回值如表4-17所示。{{B}}表4-17函数Kind(charch)的参数及其对应的返回值{{/B}}ch(){}[]其他返回值1234560[算法4-2][问题1]请将[算法4-1]和[算法4-2]中，(1)～(7)空缺处的内容补充完整。[问题2]请从以下选项中选择相应的判断逻辑填补[算法4-2]中的“判断条件1”至“判断条件3”。注意，若“判断条件2”的逻辑判断结果为假，就无需对“判断条件3”进行判断。判断条件1：{{U}}(8){{/U}}判断条件2：{{U}}(9){{/U}}判断条件3：{{U}}(10){{/U}}[供选择的答案]A．栈顶元素表示的是与当前字符匹配的左括号B．栈顶元素表示的是与当前字符匹配的右括号C．字符是左括号D．字符是右括号E．栈不空F．栈空G．字符是括号

问答题[说明]现欲构造一文件/目录树，采用组合(Composite)设计模式来设计，得到的类图如下图所示。[Java程序]importJava.util.ArrayList;importJava.util.List;______classAbstractFile{protectedStringname;publicvoidprintName(){System.out.println(name);}publicabstractbooleanaddChiid(AbstractFilefile);publicabstractbooleanremoveChild(AbstractFilefile);publicabstractList＜AbstractFile＞getChildren();}classFileextendsAbstractFile{publicFile(Stringname){this.name=name;}publicbooleanaddChild(AbstractFilefile){returnfalse;}publicbooleanremoveChild(AbstractFilefile){returnfalse;}publicList＜AbstractFile＞getChildren(){return______;}}classFolderextendsAbstractFile{privateList＜AbstractFile＞childList;publicFolder(Stringname){this.name=name;this.childList=newArrayList＜AbstractFile＞();}publicbooleanaddChild(AbstractFilefile){returnchildList.add(file);}publicbooleanremoveChild(AbstractFilefile){returnchildList.remove(file);}public______＜AbstractFile＞getChildren(){return______;}}publicclassClient{publicstaticvoidmain(String[]args){//构造一个树型的文件/目录结构AbstractFilerootFolder=newFolder("c:\");AbstractFilecompositeFolder=newFolder("composite");AbstractFilewindowsFolder=newFolder("windows");AbstractFilefile=newFile("TestComposire.java");rootFolder.addChiid(compositeFolder);rootFolder.addChiid(windowsFoider);compositeFolder.addChild(file);//打印目录文件树printTree(rootFolder);}privatestaticvoidprintTree(AbslractFileifile){ifile.printName();List＜AbsiractFile＞children=ifile.getChildren;if(chiidren==null)return;for(AbstractFileifile.children){______;}}}该程序运行后输出结果为：c:compositeTestComposite.javaWindows

问答题假定SP表存储供应情况，如下的SQL语句是用于查询“产地为‘Beijing’、零件号为‘P101’的零件的所供应的总数(包括所有供应商)”的不完整语句，请在空缺处填入正确的内容。 SELECT SUM(Qty) FROM SP WHERE PNo=”P101’ (1) PNo (2) (SELECT PNo FROM (3) WHERE city="Beijing") (4) PNo;

问答题【函数3说明】 函数DeleteNode(Bitree * r，int e)的功能是：在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树结点的类型定义为： typedef struct Tnode{ int data； /*结点的键值*/ struct Tnode * Lchild，*Rchild； /*指向左、右子树的指针*/ } * Bitree； 在二叉查找树上删除一个结点时，要考虑三种情况： ①若待删除的结点p是叶子结点，则直接删除该结点； ②若待删除的结点p只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，然后删除结点P； ③若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s，用结点s的值代替结点p的值，然后删除结点s，结点s必属于上述①、②情况之一。 【函数3】 int DeleteNode(Bitree * r，int e){ Bitree p=*r，pp，s，c； while({{U}} (1) {{/U}}){ /*从树根结点出发查找键值为e的结点*/ pp=p； if(e＜p-＞data)p=p-＞Lchild； else p=p-＞Rchild； { if(!p)return-1； /*查找失败*/ if(p-＞Lchild &&p-＞Rchild){/*处理情况③*/ s= {{U}}(2) {{/U}}； pp=p； while({{U}} (3) {{/U}}){pp=s；s=s-＞Rchild；} p-＞data=s-＞data；p=s； } /*处理情况①、②*/ if({{U}} (4) {{/U}})c=p-＞Lchild； else c=p-＞Rchild； if(p==*r)*r=c； else if({{U}} (5) {{/U}})pp-＞Lchild＝c； else pp-＞Rchild＝c； free(p)； return 0； }

问答题[程序6] #include＜ioStream.h＞ template＜class T＞class Array； template＜class T＞class ArrayBody{ friend{{U}} (1) {{/U}}； T* tpBody； int iRows，iCurrentRow； ArrayBOdy(int iRsz，int iCsz){ tpBody={{U}} (2) {{/U}}； iRows=iRsz，iColumns=iCsz；iCurrentRow=-1； } public： T& operator[](int j) { bool row_error，column_error； row_error=column_error=false； try{ if(iCurrentRow＜0||iCurrentRow≥iRows) row_error=； if(j＜0|| j≥iColumns column_error=； if(row_error==true || column_error==true) {{U}} (3) {{/U}}； } eatch(char) { if(row error==true) cerr＜＜“行下标越界[“＜＜iCurrentRow＜＜”]”； if(column error==true) cerr＜＜“列下标越界[“＜＜j＜＜”]”； cout＜＜“/n”； } return tpBody[iCurrentRow * iColumns+j]； } ～ArrayBody(){delere[]tpBody；} }； template＜class T＞class Array { ArrayBody＜T＞ tBody； public： ArrayBody＜T＞ & operator[](int i){ {{U}}(4) {{/U}}； return tBody； }； void main() { Array＜int＞ a1(10，20)； Array＜double＞ a2(3，5)； int b1； double b2； b1=a1[-5][10]； / * 有越界提示：行下标越界[-5] * / b1=a1[10][15]； / * 有越界提示：行下标越界[10] * / b1=a1[1][4]； / * 没有越界提示 * / b2=a2[2][6]； / * 有越界提示：列下标越界[6] * / b2=a2[10][20]； / * 有越界提示：行下标越界[10]列下标越界[20] * / b2=a2[1][4]； / * 没有越界提示 * / }

问答题【说明】 ①在类体中添加函数move(double ax，double ay)的定义，使得点的坐标x和y分别移动 ax和ay个单位。 ②在类定义外完成重载的两个构造函数CPosition()和CPosition(double dx，double dy)，其中前者为不带参数的构造函数，使CPosition对象的默认值为x=0，y=0，后者为带参数的构造函数，把数据成员x和y分别初始化为参数dx和dy的值。 ③完成函数double distance(double bx，double by)的定义，该函数返回*this和点(bx， by)的距离。 注意：除在指定的位置添加语句外，请不要改动程序中的其他语句。 源程序文件test5.cpp清单如下： #include＜iostream.h＞ #include＜math.h＞ class CPosition { public： CPosition()； CPosition(double dx，double dy)； double getx()； double gety()； {{U}} (1) {{/U}} double distance(double bx，double by)； private： double x； double y； }； {{U}} (2) {{/U}} { x=0；y=0； } CPosition：：CPosition(doub，e dx，doub，e dy) { x=dx； y=dy； } double CPosition：：getx() { return x； } double CPosition：：gety() { return y； } double CPosition：：distance(double bx，double by) { {{U}} (3) {{/U}} } vold main() { double a，b； cout＜＜"|nput x，y position of a point："； cin ＞＞ a ＞＞ b； CPosition psA(a，b)； cout＜＜"Input x，y position of another point："； cin ＞＞a ＞＞ b； cout ＜＜"The　distance is" ＜＜psA.distance(a，b) ＜＜end1； }

问答题【说明】某供销系统接受顾客的订货单。当库存中某配件的数量小于订购量或库存量低于一定数量时，向供应商发出采货单；当某配件的库存量大于或等于订购量时，或者收到供应商的送货单并更新了库存后，向顾客发㈩提货单。该系统还可随时向总经理提供销售和库存情况表。该供销系统的分层数据流图中部分数据流和文件的组成如下：【文件】配件库存=配件名+规格+数量+允许的最低率库存量【数据流】订货单＝配件号+配件名+规格+数量+顾客名+地址提供单=订货单+金额采货单＝配件号+配件名+规格+数量+供应商名十地址送货单=配件号+配件名+规格+数量+金额假定顶层图是正确的，“供应商”文件已由其他系统生成。【数据流图】假定题中提供的顶层图是正确的，请回答下列问题：1.【问题1】指出哪张图中缺少了哪些文件。

问答题阅读下列说明和图，回答问题1至问题4，将解答填入对应栏内。【说明】某汽车停车场欲建立一个信息系统，已经调查到的需求如下：1．在停车场的入口和出口分别安装一个自动栏杆、一台停车卡打印机、一台读卡器和一个车辆通过传感器，示意图如下：2．当汽车到达入口时，驾驶员按下停车卡打印机的按钮获取停车卡。当驾驶员拿走停车卡后，系统命令栏杆自动抬起；汽车通过入口后，入口处的传感器通知系统发出命令，栏杆自动放下。3．在停车场内分布着若干个付款机器。驾驶员将在入口处获取的停车卡插入付款机器，并缴纳停车费。付清停车费之后，将获得一张出场卡，用于离开停车场。4．当汽车到达出口时，驾驶员将出场卡插入出口处的读卡器。如果这张卡是有效的，系统命令栏杆自动抬起；汽车通过出口后，出口传感器通知系统发出命令，栏杆自动放下。若这张卡是无效的，系统不发出栏杆抬起命令而发出告警信号。5．系统自动记录停车场内空闲的停车位的数量。若停车场当前没有车位，系统将在入口处显示“车位已满”信息。这时，停车卡打印机将不再出卡，只允许场内汽车出场。根据上述描述，采用面向对象方法对其进行分析与设计，得到了如下表所示的类/用例/状态列表、下图(a)所示的用例图、图(b)所示的初始类图以及图(c)所示的描述入口自动栏杆行为的UML状态图。{{B}}类/用例/状态列表{{/B}}

问答题【说明】 以下C++程序的功能是计算三角形、矩形和正方形的面积并输出。程序由4个类组成：类 Triangle、Rectangle和Square分别表示三角形、矩形和正方形：抽象类Figure提供了一个纯虚函数getAxea()，作为计算上述3种图形面积的通用接口。 【C++代码】 #include＜iostream＞ #include＜cmath＞ using namespace std; class Figure{ public: virtual double getArea()=0;//纯虚函数 }; class Rectangle ：{{U}} (1) {{/U}}{ protected: double height; double width; public: Rectangle(){} Rectangle(double height, double width){ this-＞height=height; this-＞width=width; } double getArea(){ return{{U}} (2) {{/U}}; } }; class Square：{{U}} (3) {{/U}}{ public: Square(double width){ 　{{U}} (4) {{/U}}; } }; class Triangle：{{U}} (5) {{/U}}{ private: double la,lb,lc; public: Triangle(double la,double lb,double lc){ this-＞la=la;this-＞1b=1b;this-＞lc=lc; } double getArea(){ double s=(la+lb+lc)/2.0; return sqrt(s*(s-la)*(s-lb)*(s-lc)); } int main() { Figure *figures[3]={new Triangle(2,3,3),new Rectangle(5,8), new Square(5)}; for(int i=0;i＜3;i++){ cout＜＜"figures["＜＜i＜＜"]area="＜＜(figures[i])-＞getArea()＜＜endl; } return 0; }

问答题【说明】装饰者模式动态地给一个对象添加一些额外的职责，就扩展功能而言，该模式比生成子类方式更加灵活。装饰模式的提出有助于解决滥用继承的问题。例如，一个名叫星巴兹(Starbuzz)的咖啡连锁店提供多种多样的咖啡，最朴素的设计就是采用继承，即设计一个饮料抽象基类Beverage，让不同种类的咖啡HouseBlend、Decaf、Espresso、DarkRoast继承Beverage类，如图13-23所示。Beverage类的cost()方法是抽象方法，每个子类的cost()方法实现即返回具体咖啡种类的价钱，Beverage类的description实例变量由每个子类设置，用来描述该类饮料，Beverage类的getDescription()方法用来返回此描述。客户在点咖啡时还可以要求添加各种各样的调料(Condiment)，加入的调料不同所收取的费用也是不同的，让各种加了调料的不同咖啡都继承基类Beverage，当咖啡种类和调料种类很多时，组合种类的数量就会急剧增长，就会发生“类数量爆炸”现象，如图13-24所示。显然，采用这种设计方式会使得代码的维护变得十分困难，可以采用装饰者模式来解决这个问题。软件设计师蝴蝶飞根据装饰者模式的思想设计了如图13-25所示的类图。在图13-25中，将各种调料Milk、Mocha、Soy、Whip作为装饰者来装饰House-Blend、Decal、Espresso、DarkRoast等各种咖啡。下面的Java程序(代码13-6)对应其具体实现。【代码13-6】importjava.io．*；abstractclassBeverage{Stringdescription="UnknownBeverage"；publicStringgetDescription(){returndescription；}public{{U}}(1){{/U}}doublecost()；}abstractclassCondimentDecorator{{U}}(2){{/U}}Beverage{publicabstractStrmggetDescription()；}classDecafextendsBeverage{publicDecaf(){description="DecafCoffee"；}publicdoublecost(){return1.05；}}classEspressoextendsBeverage{publicEspresso(){description="Espresso"；}publicdoublecost(){return1.99；}}classHouseBlendextendsBeverage{publicHouseBlend(){description="HouseBlendCoffee"；}publicdoublecost(){return.89；}}classDarkRoastextendsBeverage{publicDarkRoast(){description="DarkRoastCoffee"；}publicdoublecost(){return.99；}}classMochaextendsCondtmentDecorator{Beverage{{U}}(3){{/U}}；publicMocha(Beveragebeverage){this.beverage=beverage；}publicStringgetDescription(){returnbeverage.getDescription()+",Mocha"；}publicdoublecost(){return.20+beverage.cost()；}}ClassSoyextendsCondimentDecorator{Beveragebeverage；publicSoy(Beveragebeverage){this.beverage＝beverage；}publicStrillggetDescription(){returnbeverage.getDescription()+"，Soy"；}publicdoublecost(){return.15+beverage.cost()；}}classWhipextendsCondimentDecorator{BeveragebeverageipublicWhip(Beveragebeverage){this.beverage=beverage；}publicStringgetDescrlption(){returnbeverage.getDescription()+",Whip"；}publicdoublecost(){return.10+beverage.cost()；}}classMilkextendsCondlmentDecorator{Beverligebeverage；publicMilk(Beveragebeverage){this.beverage=beverage；}publicStringgetDescription(){returnbeverage．getDescription()+",Milk"；}publicdoublecost(){return.10+beverage.cost()；}}publicclassStarbuzzCoffee{publicstaticvoidmain(Sttingargs[]){//订一杯Espresso咖啡，不需要任何调料，打印出它的描述和价钱Beveragebeverage＝newEspresso()；System.out.println(beverage.getDescription()+"$"+beverage.cost())；//订一杯加了两份Macha调料、一份Whip调料的DarkRoast咖啡//并打印出它的描述和价钱Beveragebeverage2=newDarkRoast()；beverage2=newMocha(beverage2)：beverage2=new{{U}}(4){{/U}}(beverage2)；beverage2=newWhip(beverage2)；System.out.println(beverage2.getDescription()+"$"+beverage2.cost())；//订一杯加了一份Soy调料、一份Mocha调料、一份Whip调料//的HouseBlend咖啡，并打印出它的描述和价钱Beveragebeverage3＝newHouseBlend()；beverage3＝newSoy(beverage3)；beverage3＝newMocha(beverage3)；beverage3＝newWhip(beverage3)；System.out.println(beverage3.getDescription()+"$"+beverage3.cost())；}}【问题1】根据题目叙述，请将上述Java程序代码13-6中的(1)～(4)空填充完整。【问题2】请写出上述程序的输出结果。

问答题现要求实现一个能够自动生成求职简历的程序，简历的基本内容包括求职者的姓名、性别、年龄及工作经历。希望每份简历中的工作经历有所不同，并尽量减少程序中的重复代码。现采用原型模式(Prototype)来实现上述要求，得到如图所示的类图。[Java代码]ClassWorkExperience______Cloneable//工作简历PrivateStringworkDate;PrivateStringcompany;PublicObjectClone()______;obj.workDate=this.workDate;Obj.company-this.company;Returnobj;ClassResume______Cloneable//简历PrivateStringname;PrivateStringsex;PrivateStringage;PrivateWorkExperiencework;PublicResume(Stringname)This.name=name;work=newWorkExperience();PrivateResume(WorkExperiencework)This.woek=______;PublicvoidSetPersonallnfo(Stringsex,Stringage)/*代码略*/PublicvoidSetWorkExperience(StringworkDate,Stringcompany)/*代码省略*/PublicObjectClone()Resumeobj=______;//其余代码省略Returnobj;ClassWorkResumePublicstaticvoidmain(String[]args)Resumea=newResume("张三");a.SetPersonallnfo("男","29");a.SetWorkExperience("1998～2000","XXX公司");Resumeb=______;b.SetWorkExperience("2001～2006","YYY公司");

问答题[说明]一个新的音像商店准备向比较广泛的人群出租录像带和光碟。该商店的管理决定在计算机系统的支持下来运作。音像商店在货架上存放着题材广泛的当前流行的电影库。由于同一个电影片名可能有于不同的导演而有不同的版本，因此电影用电影代码区分，而不用电影片名；同一个版本有多份拷贝，因此音像制品用一个唯一的编号标识。某个特定的电影可以存放在录像带或光碟上，录像带和光碟的租金不同。录像带要么是Beta格式要么是VHS格式；光碟为DVD格式，容量比较大，一张光碟可以存储同一电影片名的不同版本。每个电影都有特定的租用期(用天表示)，并带有在租用期内的租金。音像商店必须能够立即回答关于某个电影的库存和有多少供租用的带子或光碟。音像商店的店员负责定购音像、联系客户、音像上架，并对客户的询问给出答复。该系统采用面向对象方法开发，系统中的类以及类之间的关系用UML类图表示，图1-1是该系统的用例图，图1-2是该系统的类图的一部分。[图1-1][图1-2]

问答题[说明]有一种游戏，其规则如下：有一个3×3的方格，每个方格中只可画“+”符号或“-”符号，表示该方格的值。图1(a)定义了各方格的位置，下表为每个方格位置定义了与其相关联的位置集，各方格的初值如图1(b)所示。游戏开始后，每次可选一个值为“+”的方格位置，然后根据表中将该位置所对应的每个相关联的位置上的符号重画成与其不同的符号，即将“+”重画成“-”，将“-”重画成“+”。重画操作可用所选的位置编号来描述。例如，在如图1(b)所示的情况下，选择位置4时，重画结果如图1(c)所示。经过连续的若干次这样的操作后，当3×3方格呈现出如图1(d)所示的图形时，表示获胜；当呈现出如图1(e)所示的图形时，表示失败。图2所示的流程图旨在输出从初始状态出发直至获胜的重画操作(即所选的位置编号)序列。图中假定数组A[0..8]存放3×3方格的值，数组c[0..8][1..5]存放表中所示的各方格位置的相关联的位置集、数组d[0..8]存放各方格位置的相关联的位置个数，数组元素S[1]～S[k]存放各次重画操作所对应的位置编号，变量N存放3×3方格中当前的“+”符号的个数。方格位置及其相关位置集对照表方格位置相关位置001341012212453036413457525863467767884578

问答题【程序5说明】 设M叉树采用列表法表示，即每棵子树对应一个列表，列表的结构为：子树根结点的值部分(设为一个字符)和用“()”括起来的各子树的列表(如有子树的话)，各子列表间用“，”分隔。例如下面的三叉树可用列表a(b(c，d)，e，f(g，h，i))表示。 本程序输入列表，生成一棵M叉树，并由M叉树输出列表。假定输入无错误。 【程序5】 #include＜Stdio.h＞ #include＜Stdlib.h＞ #define M 3 typedef struct node{char val； struct node，subTree[M]； }NODE； char buf[255]，*Str=buf； NODE * d=NULL NODE*makeTree()/*由列表生成M叉树*/ {int k；NODE*s； s={{U}} (1) {{/U}}； s-＞val= *Str++； for(k=0；k＜M；k++)s-＞subTree[k]＝NULL； if(* str＝'('){ k＝0； do{str++； s-＞sub Tree[k]＝{{U}} (2) {{/U}}； if(*Str==')'){Str++；break；} k=k+1； }while({{U}} (3) {{/U}})； } return s； } void walkTree(NODE*t)/*由M又树输出列表*/ {int i； if(t!=NULL){ {{U}} (4) {{/U}} if(t-＞subTree[0]==NULL)return； putchar('(')； for(i=0；i＜M；i++){ {{U}}(5) {{/U}}； if(i!＝M-1&&t-＞subTree[i+1]!=NULL) putchar('，')； } putchar(')')； } } void main() {printf("Enter exp：")； scanf("%s"，str)； d=makeTree()； walkTree(d)；putchar('/n")； }

问答题阅读下列说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。 [说明] 设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量Wij和价格Cij。设计一个算法，求解总价格不超过上限cc的最小重量的机器组成。 采用回溯法来求解该问题： 首先定义解空间。解空间由长度为n的向量组成，其中每个分量取值来自集合{1，2，…，m}，将解空间用树形结构表示。 接着从根结点开始，以深度优先的方式搜索整个解空间。从根结点开始，根结点成为活结点，同时也成为当前的扩展结点。向纵深方向考虑第一个部件从第一个供应商处购买，得到一个新结点。判断当前的机器价格(C11)是否超过上限(cc)，重量(W11)是否比当前已知的解(最小重量)大，若是，应回溯至最近的一个活结点；若否，则该新结点成为活结点，同时也成为当前的扩展结点，根结点不再是扩展结点。继续向纵深方向考虑第二个部件从第一个供应商处购买，得到一个新结点。同样判断当前的机器价格(C11+C21)是否超过上限(cc)，重量(W11+W21)是否比当前已知的解(最小重量)大。若是，应回溯至最近的一个活结点；若否，则该新结点成为活结点，同时也成为当前的扩展结点，原来的结点不再是扩展结点。以这种方式递归地在解空间中搜索，直到找到所要求的解或者解空间中已无活结点为止。 [C代码] 下面是该算法的C语言实现。 {{U}} {{/U}}变量说明。 n：机器的部件数。 m：供应商数。 cc：价格上限。 w[][]：二维数组，w[i][j]表示第j个供应商供应的第i个部件的重量。 c[][]：二维数组，c[i][j]表示第j个供应商供应的第i个部件的价格。 best1W：满足价格上限约束条件的最小机器重量。 bestC：最小重量机器的价格。 bestX[]：最优解，一维数组，bestX|[i]表示第i个部件来自哪个供应商。 cw：搜索过程中机器的重量。 cp：搜索过程中机器的价格。 x[]：搜索过程中产生的解，x[i]表示第i个部件来自哪个供应商。 i：当前考虑的部件，从0～n-1。 j：循环变量。 {{U}} {{/U}}函数backtrack。 int n=3; int m=3; int cc=4; int w[3][3]={{1,2,3},{3,2,1},{2,2,2}}; int c[3][3]={{1,2,3},{3,2,1},{2,2,2}}; int bestW=8; int bestC=0; int bestX[3]={0,0,0); int cw=0; int cp=0; int x[3]={0,0,0}; int backtrack(int i){ int j=0; int found=0; if(i＞n-1){/*得到问题解*/ bestW=cw; bestC=cp; for(j=0;j＜n;j++){ {{U}} {{U}} {{/U}} {{/U}}; } return 1; } if(cp＜=cc){/*有解*/ found=1; } for(j=0;{{U}} {{U}} {{/U}} {{/U}};j++){ /*第i个部件从第j个供应商购买*/ {{U}} {{U}} {{/U}} {{/U}}; cw=cw+w[i][j]; cp=cp+c[i][i][j]; if(cp＜=cc＆＆{{U}} {{U}} {{/U}} {{/U}}{/*深度搜索，扩展当前结点*/ if(backtrack(i+1)){found=1;} } /*回溯*/ cw=cw-w[i][j]; {{U}} {{U}} {{/U}} {{/U}}; } return found; }

问答题[说明] 以下C++代码使用虚函数实现了同一基类shape派生出来的Class rectangle、Class triangle、Class circle实现了计算矩形、圆形面积的计算。仔细阅读以下代码，将 (n) 处语句补充完整。 [代码5-1]#include＜iostream.h＞ #define PI 3.14159 class shape //基类 protected： (1) ； public： (2) ； (3) ； ； [代码5-2] class rectangle: public shape public: rectangle (int x2,int y2,int r2): (4) ; double area ( ) return x*y; ; ; class circle: public shape public: circle (int x3,int y3,int r3): (5) ; double area ( ) return r*r*PI; ; ; [代码5-3] void main ( ) rectangle r (10,20,0); circle c (0,0,30); shape (6) ； cout＜＜"长方形面积="＜＜s1-＞area ( ) ＜＜endl； cout＜＜"圆形面积="＜＜s2-＞area ( ) ＜＜endl； [运行结果] 长方形面积=200 圆形面积=2827.43

问答题【函数1说明】 函数compare(SqList A, SqList B)的功能是：设A=(al，…，am)和B=(b1，…，bn)均为顺序表，“比较”，两个顺序表A和B的大小。设A’ 和B’ 分别为A和B中除去最大共同前缀后的子表(例如，A=(y，x，x，z，x，z)，B=(y，x，x，2，y，x，x，z)，则两者中最大的共同前缀为 (y，x，x，z)，在两表中除去最大共同前缀后的子表分别为A'=(x，z)和B'=(y，x，x，z))。若 A'=B'=空表，则A=B；若A'=空表，而B'≠空表，或者两者均不为空表，且A'的首元小于 B'首元，则A＜B：否则A＞B。 提示：算法的基本思想为：若相等，则j+1，之后继续比较后继元素；否则即可得出比较结果。显然，j的初值应为0，循环的条件是j不超出其中任何一个表的范围。若在循环内不能得出比较结果，则循环结束时有3种可能出现的情况需要区分。 【函数1】 int compare ( SqListA, SqList B) //若A＜B，则返回-1；若A=B，则返回0：若A＞B，则返回1 j =0; while(i＜ (1) else (2) ; if(A. length == B. length) return(0); else if(A. length＜B. length)return(-1); else return(1)//compare //函数1的时间复杂度是 (3) 。 【函数2说明】 函数exchanse_L(SLnk＆L，int m)的功能是：用尽可能少的辅助空间将单链表中前m个结点和后n个结点的互换。即将单链表(a1、a2…，am，b1，b2，…，bn)改变成(b1，b2，…，bn，a1， a2，…，am，)。【函数2】void exchange_L(SLink k=1； while( k ＜ m++k; if( (6) //以指针ha记a1结点的位置 L -＞ next = p -＞ next; //将B1结点链接在头结点之后 p -＞ next = NULL; //设am的后继为空 q= (7) ; //令q指向b1结点 while(q-＞next)q = (8) ; //查找bn结点 q-＞＞next= (9) ; //将a1结点链接到bn结点之后 //函数2的时间复杂度是 (10) 。

问答题快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的三个步骤如下： 分解：选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空)A[p..q-1]和A[q+1..r]，使得A[q]大于等于A[p..q-1]中的每个元素，小于A[q+1..r]中的每个元素。q的值在划分过程中计算。 递归求解：通过递归的调用快速排序，对子数组A[p..q-1]和A[q+1..r]分别排序。 合并：快速排序在原地排序，故不需合并操作。