问答题阅读下列说明和C代码，回答下面问题。 [说明] 采用归并排序对n个元素进行递增排序时，首先将n个元素的数组分成各含n/2个元素的两个子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排序的子数组得到排序结果。 下面的C代码是对上述归并算法的实现，其中的常量和变量说明如下。 ●art：待排序数组。 ●p，q，r：一个子数组的位置从p到q，另一个子数组的位置从q+1到r。 ●begin，end：待排序数组的起止位置。 ●left，right：临时存放待合并的两个子数组。 ●n1，n2：两个子数组的长度。 ●i，j，k：循环变量。 ●mid：临时变量。 [C代码] #inciude＜stdio.h＞ #inciude＜stdlib.h＞ Define MAX 65536 void merge(int art([],int p,int q,int r) { int*left,*right; int n1,n2,I,j,k; n1=q-p+1; n2=r-q; If(left=(int*)malloc((n1+1)*sizeof(int)))=NULL) { Perror("malloc error"); exit(1); } If((right=(int*)malloc((n2+1)*sizeof(int)))=NULL) { Perror("malloc error"); exit(1); } for(i=0;i＜n1;i++) { left[i]=art[p+i]; } left[i]=MAX; for(i=0;i＜n2;i++) { right[i]=arr[q+i+1] } right[i]=MAX; i=0;j=0; For(k=p;(1);k++) { If(left[i]＞right[j] { ______ j++; } else { arr[k1]=left[i]; i++; } } } Void merge Sort(int art(),int begin,int end) { int mid; if(______) { mid=(begin+end)/2; merge Sort(art,begin,mid); ______; Merge(arr,begin,mid,end); } }

问答题阅读下列说明和Java代码，在(n)处填入适当的字句。[说明]现欲构造一文件/目录树，采用组合(Composite)设计模式来设计，得到的类图如图10.17所示。[Java代码]importJava.util.ArrayList;importjava.util.List;(1)classAbstractFileprotectedStringname;publicvoidprintName()System.out.println(name);publicabstractbooleanaddChild(AbstractFilefile);publicabstractbooleanremoveChild(AbstractFilefile);publicabstractList＜AbstractFile＞getChildren();classFileextendsAbstractFilepublicFile(Stringname)this.name=name;publicbooleanaddChild(AbstractFilefile)returnfalse;publicbooleanremoveChild(AbstractFilefile)returnfalse;publicList＜AbstractFile＞getChildren()return(2);classFolderextendsAbstractFileprivateList＜AbstractFile＞childList;publicFolder(Stringname)this.name=name;this.childList=newArrayList＜AbstractFile＞();publicbooleanaddChild(AbstractFilefile)returnchildList.add(file);publicbooleanremoveChild(AbstractFilefile)returnchildList.remove(file);public(3)＜AbstractFile＞getChildren()return(4);publicclassClientpublicstaticvoidmain(String[]args)//构造-个树型的文件/目录结构AbstractFilerootFolder=newFolder("c://");AbstractFilecompositeFolder-newFolder("composite");AbstractFilewindowsFolder=newFolder("windows");AbstractFilefile=newFile("TestComposite.java");rootFolder.addChild(compositeFolder);rootFolder.addChild(windowsFolder);compositeFolder.addChild(file);//打印目录文件树printTree(rootFolder);privatestaticvoidprintTree(AbslractFileifile)ifile.printName();List＜AbslractFile＞children=ifile.getChildren;if(children==null)return;for(AbstractFileifile.children)(5);该程序运行后输出结果为:c:/compositeTestComposite.javaWindows

问答题【问题4】中缀表达式(A+B-C*D)*(E-F)/G经该流程图处理后的输出是什么?

问答题阅读下列说明和C++代码，在(n)处填入适当的字句。[说明]已知某企业欲开发一家用电器遥控系统，即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器如图10.30所示。该遥控器共有4个按钮，编号分别是0至3，按钮0和2能够遥控打开电器1和电器2，按钮1和3则能遥控关闭电器1和电器2。由于遥控系统需要支持形式多样的电器，因此，该遥控系统的设计要求具有较高的扩展性。现假设需要控制客厅电视和卧室电灯，对该遥控系统进行设计所得类图如10.31所示。图10.31中，类RomoteController的方法onPressButton(intbutton)表示当遥控器按键按下时调用的方法，参数为按键的编号；Command接口中on和off方法分别用于控制电器的开与关；Light中tumLight(intdegree)方法用于调整电灯光的强弱，参数degree值为0时表示关灯，值为100时表示开灯并且将灯光亮度调整到最大；TV中setChannel(intchannel)方法表示设置电视播放的频道，参数channel值为0时表示关闭电视，为1时表示开机并将频道切换为第1频道。[C++代码]classLight//电灯类public：voidturnLight(intdegree)//调整灯光亮度，0表示关灯，100表示亮度最大；classTV//电视机类public：voidsetChannel(intchannel)//调整电视频道，0表示关机，1表示开机并切换到1频道；classCommand//抽象命令类public：virtualvoidon()=0;virtualvoidoff()=0;；classRemoteController//遥控器类protected:Command*commands[4];//遥控器有4个按钮，按照编号分别对应4个conunand对象public：voidonPressButton(intbutton)//按钮被按下时执行命令对象中的命令if(button%2==0)commands[button]-＞on();elsecommands[button]-＞off();voidsetCommand(intbutton,Command*command)(1)=command;//设置每个按钮对应的命令对象；classLightCommand：publicCommand(//电灯命令类protected:Light*light;//指向要控制的电灯对象public：voidon()light-＞turnLight(100);voidoff()light-＞(2);LightCommand(Light*light)this-＞light=light;；classTVCommand：publicCommand//电视机命令类protected:TV*tv；//指向要控制的对象public：voidon()ty-＞(3)；)voidoff()tv-＞setChannel(0);TVCommand(TV*tv)this-＞tv=tv;；voidmain()Lightlight;TVtv;//创建电灯和电视对象LightCommandlightComrnand(＆light);TVCommandtvCommand(＆tv);RemoteControllerremoteController;remoteController.setCommand(0，(4))；//设置按钮0的命令对象…//此处省略设置按钮1、按钮2和按钮3的命令对象代码本题中，应用命令模式能够有效让类(5)和类(6)、类(7)之间的耦合性降至最小。

问答题阅读以下说明，回答问题1、问题2和问题3，将解答填入对应栏内。 [说明] 某单位正在使用一套C/S模式的应用软件系统，现在需要升级为B/S应用模式，但需要保持业务的连续性。开发人员提出用Web Service作为中间层的接口进行开发。

问答题【问题1】 数据流图如图1-9(住宅安全系统顶层图)所示中的A和B分别是什么?

问答题阅读以下说明和图，回答下面问题。[说明]某公司欲开发一个管理选民信息的软件系统，对系统的基本需求描述如下。(1)每个人(Person)可以是一个合法选民(Eligible)或者无效的选民(Ineligible)。(2)每个合法选民必须通过该系统对其投票所在区域(即选区，Riding)进行注册(Registration)，每个合法选民仅能注册一个选区。(3)选民所属选区由其居住地址(Address)决定。假设每个人只有一个地址，地址可以是镇(Town)或者城市(City)。(4)某些选区可能包含多个镇；而某些较大的城市也可能包含多个选区。现采用面向对象方法对该系统进行分析与设计，得到如下图所示的初始类图。类图

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

问答题【问题3】 类通常不会单独存在，因此当对系统建模时，不仅要识别出类，还必须对类之间的相互关系建模。在面向对象建模中，提供了4种关系：依赖(Dependency)、概括(Generalization)、关联(Association)和聚集(Aggregation)。请分别说明这4种关系的含义，并说明关联和聚集之间的主要区别。

问答题【说明】 假设需要将N个任务分配给N个工人同时去完成，每个人都能承担这N个任务，但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案，在该方案中，为每个人分配 1个不同的任务。 程序中，N个任务从0开始依次编号，N个工人也从。开始依次编号，主要的变量说明如下。 · c[i][j]：将任务i分配给工人j的费用。 · task[i]：值为0表示任务i未分配，值为j表示任务i分配给工人j。 · worker[k]：值为0表示工人k未分配任务，值为1表示工人k已分配任务。 · mincost：最小总费用。 【C程序】 #include＜stdio.h＞ #define N 8 /*N 表示任务数和工人数*/ int c[N][N]; unsigned int mincost=65535; /*设置的初始值，大于可能的费用*/ int task[N], temp[N], worker[N]; void plan(int k, unsigned int cost) { int i; if({{U}} (1) {{/U}} for(i=0; i＜N; i++)temp[i]=task[i]; }else{ for(i=0; i＜N;i++)/*分配任务 k*/ if(worker[i]==0 task[k]={{U}} (3) {{/U}}; plan({{U}} (4) {{/U}},cost+c[k][i]); {{U}}(5) {{/U}}; task[k]=0; }/*if*/ } }/*Plan*/ void main() { int i,j; for(i=0; i＜N; i++){ /*设置每个任务由不同工人承担时的费用及全局数组的初值*/ worker[i]=0; task[i]=0; temp[i]=0; for(j=0; j＜N; j++) scanf(%d", } plan(0,0);/*从任务0开始分配*/ printf("/n最小差用=%d/n", mincost); for(i=0;i＜N;i++) printf("Task%d is assigned to Worker%d/n",i,temp[i]); }/*main*/

问答题阅读下列说明，回答问题。[说明]假设某大型商业企业由商品配送中心和连锁超市组成，其中商品配送中心包括采购、财务、配送等部门。为实现高效管理，设计了商品配送中心信息管理系统，其主要功能描述如下。(1)系统接收由连锁超市提出的供货淆求，并将其记录到供货请求记录文件。(2)在接到供货请求后，从商品库存记录文件中进行商品库存信息查询。如果库存满足供货请求，则给配送处理发送配送通知；否则，向采购部门发出缺货通知。(3)配送处理接到配送通知后，查询供货请求记录文件，更新商品库存记录文件，并向配送部门发送配送单，在配送货品的同时记录配送信息至商品配送记录文件。(4)采购部门接到缺货通知后，与供货商洽谈，进行商品采购处理，合格商品入库，并记录采购清单至采购清单记录文件、向配送处理发出配送通知，同时通知财务部门给供货商支付货款。该系统采用结构化方法进行开发，得到待修改的数据流图，如图4.11所示。

问答题设有一个音像租赁管理数据库系统，需要对顾客、音像制品、租赁信息以及音像制品的供货商进行管理。 顾客(Cust)的信息包括：顾客号(CNO)、顾客姓名(CName)、顾客地址(CAdd)、顾客联系电话(CPhone)、账户余额(CBal)。 音像制品(AVP)的信息包括：音像制品编号(AVNO)、音像制品名称(AVName)、音像制品名称类别(AVType)。 供货商(Prov)的信息包括：供货商编号(PNO)、供货商名称(PName)、供货商地址(PAdd)。 租赁系统的管理规则如下： Ⅰ．顾客号是顾客的唯一标识；音像制品编号是音像制品的唯一标识；供货商编号是供货商的唯一杯识； Ⅱ．一个顾客可以租赁多个音像制品，一个音像制品只能被一个顾客租赁；租赁时标明租赁日期(RDate)，归还日期(GDate)和租金(Value)； Ⅲ．一个供货商可供应多个音像制品，一个音像制品只能由一个供应商供应。 请针对以上描述，完成下列设计内容： ①构建租赁系统的ER图。 ②根据构建的ER图，设计满足3NF的关系模式，并标出每个关系模式的主码和外码。

问答题试题四 阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 在一块电路板的上下两端分别有n个接线柱。根据电路设计，用(i,π(i))表示将上端接线柱i与下端接线柱π(i)相连，称其为该电路板上的第i条连线。如图4-1所示的π(i)排列为{8,7,4,2,5,1,9,3,10,6}。对于任何1≤iπ(j)。 在制作电路板时，要求将这n条连线分布到若干绝缘层上，在同一层上的连线不相交。现在要确定将哪些连线安排在一层上，使得该层上有尽可能多的连线，即确定连线集Nets={(i,π(i))，1≤i≤n}的最大不相交子集。 【分析问题】 记N(i,j)={t|(t,π(t))∈Nets,t≤i,π(t)≤j}。N(i,j)的最大不相交子集为MNS(i,j)，size(i,j)=|MNS(i,j)|。 经分析，该问题具有最优子结构性质。对规模为n的电路布线问题，可以构造如下递归式： 【C代码】 下面是算法的C语言实现。 （1）变量说明 size[i][j]：上下端分别有i个和j个接线柱的电路板的第一层最大不相交连接数 pi[i]：π(i)，下标从1开始 （2）C程序

问答题阅读下列说明和C函数，在(n)处填入适当的字句。[说明]已知集合A和B的元素分别用不含头节点的单链表存储，函数Difference()用于求解集合A与B的差集，并将结果保存在集合A的单链表中。例如，若集合A=5，10，20，15，25，30，集合B=5，15，35，25，如图8.13(a)所示，运算完成后的结果如图8.13(b)所示。链表节点的结构类型定义如下。typedefstructNodeElemTypeelem;structNode*next;NodeType;[C函数]voidDifference(NodeType**LA,NodeType*LB)NodeType*pa,*pb.*pre,*q;pre=NULL;(1);while(pa)pb=LB;while((2))pb=pb-＞next;if((3))if(!pre)*LA=(4);else(5)=pa-＞next;q=pa;pa=pa-＞next;free(q);else(6);pa=pa-＞nex七;

问答题阅读下列说明和C++代码，将应填入空白处的字句写在答题纸的对应栏内。[说明]某饭店在不同的时段提供多种不同的餐饮，其菜单的结构图如图1所示。图1菜单的结构图现在采用组合(Composition)模式来构造该饭店的菜单，使得饭店可以方便地在其中增加新的餐饮形式，得到如图2所示的类图。其中MenuComponent为抽象类，定义了添加(add)新菜单和打印饭店所有菜单信息(print)的方法接口。类Menu表示饭店提供的每种餐饮形式的菜单，如煎饼屋菜单、咖啡屋菜单等。每种菜单中都可以添加子菜单，例如图1中的甜点菜单。类MenuItem表示菜单中的菜式。图2类图[C++代码]#include＜iostream＞#include＜list＞#include＜string＞usingnamespacestd;classMenuComponent{protected:stringname;public:MenuComponent(Stringname){this-＞name=name;}stringgetName(){returnname;}______;//添加新菜单virtualvoidprint()=0;//打印菜单信息};classMenultem:publicMenuComponent{private:doubleprice;public:Menultem(stringname,doubleprice):MenuComponent(name){this-＞price=price;}doublegetPrice(){returnprice;}voidadd(MenuComponent*menuComponent){return;}//添加新菜单voidprint(){cout＜＜""＜＜getName()＜＜","＜＜getPrice()＜＜endl;}};classMenu:publicMenuComponent{private:list＜______＞menuComponents;public:Menu(stringname):MenuC0mponent(name){}voidadd(MenuComponent*menuComponent)//添加新菜单{______;}voidprint(){cout＜＜"\n"＜＜getName()＜＜"\n-----------------"＜＜endl;std::list＜MenuComponent*＞::iteratoriter;for(iter=menuComponents.begin();iter!=menuComponents.end();iter++)______-＞print();}}voidmain(){MenuComponent*allMenus=newMenu("ALLMENUS");MenuComponent*dinerMenu=newMenu("DINERMENU");……//创建更多的Menu对象，此处代码省略allMenus-＞add(dinerMenu);//将dinerMenu添加到餐厅菜单中……//为餐厅增加更多的菜单，此处代码省略______-＞print();//打印饭店所有菜单的信息}

问答题【问题2】 根据说明，结合问题1的解答，指出在该系统的顶层数据流图中应有哪些数据流。请采用说明中的词汇给出这些数据流的起点、终点及数据流名称，如表1-1所示给出了数据流的部分信息，请填充空缺处。 {{B}}表1-1 数据流信息{{/B}} 序 号 起 点 终 点 数据流名称 　1 　{{U}}(1){{/U}} 　网上作业提交与管理系统 　作业申请 　2 　{{U}}(2){{/U}} 　网上作业提交与管理系统 　提交的作业 　3 　网上作业提交与管理系统 　{{U}}(3){{/U}} 　需完成的作业 　4 　网上作业提交与管理系统 　{{U}}(4){{/U}} 　{{U}}(5){{/U}} 　5 　网上作业提交与管理系统 　{{U}}(6){{/U}} 　作业申请 　6 　网上作业提交与管理系统 　{{U}}(7){{/U}} 　{{U}}(8){{/U}} 　7 　{{U}}(9){{/U}} 　网上作业提交与管理系统 　选课学生名单 　8 　{{U}}(10){{/U}} 　网上作业提交与管理系统 　{{U}}(11){{/U}} 　9 　{{U}}(12){{/U}} 　网上作业提交与管理系统 　账号和密码 　10 　{{U}}(13){{/U}} 　网上作业提交与管理系统 　账号和密码

问答题阅读下列说明和C代码，在(n)处填入适当的子句。[说明]栈(Stack)结构是计算机语言实现中的一种重要数据结构。对于任意栈，进行插入和删除操作的一端称为栈顶(StackTop)，而另一端称为栈底(StackBottom)。栈的基本操作包括：创建栈(NewStack)、判断栈是否为空(IsEmpty)、判断栈是否己满(IsFull)、获取栈顶数据(Top)、压栈/入栈(Push)、弹栈/出栈(Pop)。当设计栈的存储结构时，可以采取多种方式。其中，采用链式存储结构实现的栈中各数据项不必连续存储，如图8.14所示。以下C代码采用链式存储结构实现一个整数栈操作。[C代码]typedefstructListintdata;//栈数据structList*next;//上次入栈的数据地址List;typedefstructStackList*pTop;//当前栈顶指针Stack;Stack*NewStack()return(Stack*)calloc(1,sizeof(Stack));intIsEmpty(Stack*s)(//判断栈s是否为空栈If((1))return1；return0；intTop(Stack*s)//获取栈顶数据。若栈为空，则返回机器可表示的最小整数if(IsEmpty(S))returnINT_MIN;return(2)；voidPush(Stack*s,inttheData)//将数据theData压栈List*newNode;newNode=(List*)calloc(1,sizeof(List));newNode-＞data=theData;newNode-＞next=S-＞pTop;S-＞pTop=(3);voidPop(Stack*s)//弹栈List*lastTop;If(IsEmpty(S))return;lastTop=S-＞pTop;S-＞pTop=(4);Free(lastTop);#defineMD(a)a＜＜2intmain()inti;Stack*myStack;myStack=NewStack();Push(myStack,MD(1));Push(myStack,MD(2));Pop(myStack);Push(myStack,MD(3)+1);while(!IsEmpty(myStack))printf("%d",Top(myStack));Pop(myStack);return0;以上程序运行时的输出结果为:(5)。

问答题【预备知识】①对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合{a，b，c，d}及其权值2、7、4、5，可构造如图5-6所示的最优二叉树和相应的结构数组Ht(数组元素Ht[0]不用)。结构数组Ht的类型定义如下：#defineMAXLEAFNUM20structnode{charch;/*当前节点表示的字符，对于非叶子节点，此域不用*/intweight;/*当前节点的权值*/intparent;/*当前节点的父节点的下标，为0时表示无父节点*/intlchild,rchild;/*当前节点的左、右孩子节点的下标，为0时表示无对应的孩子节点*/}Ht[2*MAXLEAFNUM];②用“0”或“1”标识最优二叉树中分支的规则是：从一个节点进入其左(右)孩子节点，就用“0”(“1”)标识该分支(示例见图5-6)。③若用上述规则标识最优二叉树的每条分支后，从根节点开始到叶子节点为止，按经过分支的次序，将相应标识依次排列，可得到由“0”、“1”组成的一个序列，称此序列为该叶子节点的前缀编码。例如图5-6所示的叶子节点a、b、c、d的前缀编码分别是110、0、111、10。【函数5-6说明】函数voidLeafCode(introot，intn)的功能是：采用非递归方法，遍历最优二叉树的全部叶子节点，为所有的叶子节点构造前缀编码。其中形参root为最优二叉树的根节点下标，形参n为叶子节点个数。在构造过程中，将Ht[P].weight域用做被遍历节点的遍历状态标志。【函数5-6】char**Hc;voidLeafCode(introot,intn)/*为最优二叉树中的n个叶子节点构造前缀编码，root是树的根节点下标*/{inti,p=root,cdlen=0;charcode[20];Hc=(char**)maloc((n+1)*sizeof(char*));/*申请字符指针数组*/for(i=1;i＜=p;++i)Ht[i].weight=0;/*遍历最优二叉树时用做被遍历节点的状态标志*/while(p){/*以非递归方法遍历最优二叉树，求树中每个叶子节点的编码*/if(Ht[p].weight==0){/*向左*/Ht[p].weight=1;if(Ht[p].lchild!=0){p=Ht[p].lchild;code[cdlen++]='0';}elseif(Ht[p].rchild==0){/*若是叶子节点，则保存其前缀编码*/Hc[p]=(char*)malloc((cdlen+1)*sizeof(char));{{U}}(1){{/U}};strcpy(Hc[p],code);}}elseif(Ht[p].weight==1)(/*向右*/Ht[p].weight=2;if(Ht[p].rchild!=0){p=Ht[p].rchild;code[edlen++]='1';}}else{/*Ht[p].weight==2，回退*/Ht[p].weight=0;p={{U}}(2){{/U}};{{U}}(3){{/U}};/*退回父节点*/}}/*while结束*/}【函数5-7说明】函数voidDecode(char*buff,introot)的功能是：将前缀编码序列翻译成叶子节点的字符序列，并输出。其中形参root为最优二叉树的根节点下标，形参buff指向前缀编码序列。【函数5-7】voidDecode(char*buff,introot){intpre=root,p;while(*buff!='/0'){p=root;while(p!=0){/*存在下标为p的节点*/pre=p;if({{U}}(4){{/U}})p=Ht[p].lchild;/*进入左子树*/elsep=Ht[p].rchild;/*进入右子树*/buff++;/*指向前缀编码序列的下一个字符*/}{{U}}(5){{/U}};printf("%c",Ht[pre].ch);}}

问答题试题三 阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。 【说明】 某软件公司欲设计实现一个虚拟世界仿真系统。系统中的虚拟世界用于模拟现实世界中的不同环境（由用户设置并创建），用户通过操作仿真系统中的1~2个机器人来探索虚拟世界。机器人维护着两个变量b1和b2，用来保存从虚拟世界中读取的字符。 该系统的主要功能描述如下： （1）机器人探索虚拟世界（Run Robots）。用户使用编辑器（Editor）编写文件以设置想要模拟的环境，将文件导入系统（Load File）从而在仿真系统中建立虚拟世界（Setup World）。机器人在虚拟世界中的行为也在文件中进行定义，建立机器人的探索行为程序（Setup Program）。机器人在虚拟世界中探索时（Run Program），有2种运行模式： ①自动控制（Run）：事先编排好机器人的动作序列（指令（Instruction）），执行指令，使机器人可以连续动作。若干条指令构成机器人的指令集（Instruction Set）。 ②单步控制（Step）：自动控制方式的一种特殊形式，只执行指定指令中的一个动作。 （2）手动控制机器人（Manipulate Robots）。选定1个机器人后（Select Robot），可以采用手动方式控制它。手动控制有4种方式： ①Move：机器人朝着正前方移动一个交叉点。 ②Left：机器人原地沿逆时针方向旋转90度。 ③Read：机器人读取其所在位置的字符，并将这个字符的值赋给b1；如果这个位置上没有字符，则不改变b1的当前值。 ④Write：将b1中的字符写入机器人当前所在的位置，如果这个位置上已经有字符，该字符的值将会被b1的值替代。如果这时b1没有值，即在执行Write动作之前没有执行过任何Read动作，那么需要提示用户相应的错误信息（Show Errors）。 手动控制与单步控制的区别在于，单步控制时执行的是指令中的动作，只有一种控制方式，即执行下个动作；而手动控制时有4种动作。 现采用面向对象方法设计并实现该仿真系统，得到如图3-1所示的用例图和图3-2所示的初始类图。图3-2中的类“Interpreter”和“Parser”用于解析描述虚拟世界的文件以及机器人行为文件中的指令集。

问答题【说明】 函数DeleteNode(Bitree*r，inte)的功能是：在树根节点指针为r的二叉查找(排序)树上删除键值为e的节点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树节点的类型定义为： typedef struct Tnode{ int data;/*节点的键值*/ struct Tnode *Lchild,*Rchiid;/*指向左、右子树的指针*/ }*Bitree; 在二叉查找树上删除一个节点时，要考虑3种情况。 ①若待删除的节点p是叶子节点，则直接删除该节点。 ②若待删除的节点p只有一个子节点，则将这个子节点与待删除节点的父节点直接连接，然后删除节点。 ③若待删除的节点p有两个子节点，则在其左子树上，用中序遍历寻找关键值最大的节点 s，用节点s的值代替节点p的值，然后删除节点s，节点s必属于上述①、②情况之一。 【函数5-5】 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-＞Rehild; } if(!p)retrn -1;/*查找失败*/ if(p-＞Lchild 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; }