问答题【问题1】 识别关联的多重度是面向对象建模过程中的一个重要步骤。根据说明中给出的描述，完成图10-4中的(1)～(6)。

问答题[说明]某工程计算中要完成多个矩阵相乘(链乘)的计算任务。两个矩阵相乘要求第一个矩阵的列数等于第二个矩阵的行数，计算量主要由进行乘法运算的次数决定。采用标准的矩阵相乘算法，计算Am×n×Bn×p，需要m×n×p次乘法运算。矩阵相乘满足结合律，多个矩阵相乘，不同的计算顺序会产生不同的计算量。以矩阵A110×100，A2100×5，A35×50三个矩阵相乘为例，若按(A1×A2)×A3计算，则需要进行10×100×5+10×5×50=7500次乘法运算；若按A1×(A2×A3)计算，则需要进行100×5×50+10×100×50=75000次乘法运算。可见不同的计算顺序对计算量有很大的影响。矩阵链乘问题可描述为：给定n个矩阵＜A1，A2，…，An＞，矩阵A：的维数为pi-l×pi，其中i=1，2，…，n。确定一种乘法顺序，使得这n个矩阵相乘时进行乘法的运算次数最少。由于可能的计算顺序数量非常庞大，对较大的n，用蛮力法确定计算顺序是不实际的。经过对问题进行分析，发现矩阵链乘问题具有最优子结构，即若A1×A2×…×An的一个最优计算顺序从第k个矩阵处断开，即分为A1×A2×…×Ak和Ak+1×Ak+2×…×An两个子问题，则该最优解应该包含A1×A2×…×Ak的一个最优计算顺序和Ak+1×Ak+2×…×An，的一个最优计算顺序。据此构造递归式，其中，cost[i][j]表示Ai+1×Ai+2×…×Aj+1的最优计算的计算代价。最终需要求解cost[0][n-1]。[C代码]算法实现采用自底向上的计算过程。首先计算两个矩阵相乘的计算量，然后依次计算3个矩阵、4个矩阵……n个矩阵相乘的最小计算量及最优计算顺序。下面是该算法的C语言实现。(1)主要变量说明n：矩阵数seq[]：矩阵维数序列cost[][]：二维数组，长度为n×n，其中元素cost[i][j]表示Ai+1×Ai+2×…×Aj+1的最优计算的计算代价trace[][]：二维数组，长度为n×n，其中元素trace[i][j]表示Ai+1×Ai+2×…×Aj+1的最优计算对应的划分位置，即k(2)函数cmm#defineN100intcost[N][N];inttraee[N][N];intcmm(intn,intseq[]){inttempCost;inttempTrace;inti,j,k,p;inttemp;for(i=0;i＜n;i++){cost[i][i]=0;}for(p=1;p＜n;p++){for(i=0;______;i++){______;tempCost=-1;for(k=i;k＜j;k++){temp=______;if(tempCost==-1||tempCost＞temp){tempCost=temp;______;cost[i][j]=tempCost;trace[i][j]=tempTrace;}}returncost[0][n-1];}

问答题【问题2】（8 分） 根据【说明】中的描述，给出图3-1 中缺少的四个用例及其所对应的参与者。

问答题阅读以下说明，将应填入{{U}}(n){{/U}}处的字句写在答卷纸的对应栏内。【说明】下面的程序为堆排序程序，其中函数adjust(i,n)是把以R[i](1≤i≤┕i/2┙)为根的二叉树调整成堆的函数，假定R[i]的左、右子树已经是堆，程序中的，是在主函数中说明的结构数组，它含有要排序的n个记录。【程序】Voidadjust(i，n)Inti，n；{ihtk,j;elementextr;extr=r[i];k=i;j=2*i;while(j＜=n){if((j＜n)if(extr.key＜r[j].key){r[k]=r[j];k=j;{{U}}(2){{/U}};}else{{U}}(3){{/U}};}r[k]=extr;}/*让i从┗i/2┛逐步减到1,反复调用函数adjust,便完成建立初始堆的过程。*/voidheapsort(r,n)listr;intn;{inti,1;elementextr;for(i=n/2;i＞=1;--i){{U}}(4){{/U}};/*建立初始堆*/for(k--n;k＞=2;k--){extr=r[1];r[1]=r[k];r[k]=extr;{{U}}(5){{/U}};}}

问答题 【说明】 中国教育科研网受理了许多用户(高校和研究机构)中请在指定IP上开设网络访问业务。网络访问包括国内流量和国际流量。教育科研网管理中心保存了网络访问用户档案和网络访问业务档案。 网络访问用户档案的记录格式为： 用户编码 用户名 用户地址网络访问业务档案的记录格式为： IP地址 用户编码 国内流量许可标志 国际流量许可标志用户每次上网流量的计费数据都自动地记录在管理中心的服务器上。计费数据的记录格式为： 日期 IP地址 受访问的IP地址 访问开始时间 持续时间管理中心为了用计算机自动处理流量收费以提高工作效率，开发计费管理系统。该系统每月能为每个用户打印出网络流量缴费通知单。缴费通知单的记录格式为： IP地址 用户编码 国内流量费用 国际流量费用 总额【流程图】 下面的流程图描述了该系统的数据处理过程。该系统每天对原始的计费数据进行分类排序，并确定每个网络访问记录的访问类型(本地/国内/国际)，冉根据流量费用单价文件，算出每个记录应收取的费用。因此，形成的日计费文件中增加了两个数据项：访问类型和话费。该系统每日对日计费文件进行累计(按IP地址和访问类型，对该类型的费用进行累计，得到该p地址该访问类型的当月费用总计)，形成月计费文件。月计费文件经过出账处理形成流量费用账单文件。流量费用账单文件的记录格式为： 月份 用户编码 IP地址 国内费用 国际费用

问答题[说明]已知某企业欲开发一家用电器遥控系统，即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器如图1所示。该遥控器共有4个按钮，编号分别是0～3，按钮0和按钮2能够遥控打开电器1和电器2，按钮1和按钮3则能遥控关闭电器1和电器2。由于遥控系统需要支持形式多样的电器，因此该遥控系统的设计要求具有较高的扩展性。现假设需要控制客厅电视和卧室电灯，对该遥控系统进行设计所得类图如图2所示。在图2中，类RomoteController的方法onPressButton(intbutton)表示当遥控器按键按下时调用的方法，参数为按键的编号；Command接口中on和off方法分别用于控制电器的开与关；Light中turnLight(intdegree)方法用于调整电灯光的强弱，参数degree值为0时表示关灯，值为100时表示开灯，并且将灯光亮度调整到最大；TV中setChannel(intchannel)方法表示设置电视播放的频道，参数channel值为0时表示关闭电视，为1时表示开机并将频道切换为第1频道。[Java程序]classLight//电灯类{publicvoidturnLight(intdegree){//调整灯光亮度，0表示关灯，100表示亮度最大}};classTV//电视机类{publicvoidsetChannel(intchannel){//0表示关机，1表示开机并切换到1频道)};interfaceCommand//抽象命令类{voidon();voidoff();};classRemoteController//遥控器类{protectedCommand[]commands=newCommand[4];//遥控器有4个按钮，按照编号分别对应4个Command对象publicvoidonPressButton(intbutton){//按钮被按下时执行命令对象中的命令if(button%2==0)commands[button].on();elsecommands[button].off();}publicvoidsetCommand(intbutton,Commandcommand){______=command;//设置每个按钮对应的命令对象}};classLightCommandimplementsCommand//电灯命令类{protectedLightlight;//指向要控制的电灯对象publicvoidon(){light.turnLight(100);};publicvoidoff(){light.______;};publicLightCommand(Lightlight){this.1ight=light;};};classTVCommandimplementsCommand//电视机命令类{protectedTVtv;//指向要控制的电视机对象publicvoidon(){tv.______;};publicvoidoff(){tv.setChannel(0);};publicTVCommand(TVtv){this.tv=tv;};};publicclassrs{publicstaticvoidmain(String[]args){Lightlight=newLight();TVtv=newTV();//创建电灯和电视对象LightCommandlightCommand=newLightCommand(light);TVCommandtvCommand=newTVCommand(tv);RemoteControlletremoteController=newRemoteController();//设置按钮和命令对象remoteController.setCommand(0,______);…//此处省略设置按钮1、按钮2和按钮3的命令对象代码}}本题中，应用命令模式能够有效地让类______和类______、类______之间的耦合性降至最小。

问答题[问题3](3分) 请说明关系模式“会议申请”存在的问题及解决方案。

问答题问题：6.1 请填写（1）（2）（3）（4）（5）

问答题阅读下列算法说明和算法，将应填入{{U}}(n){{/U}}的字句写在答题纸的对应栏内。【说明】下列最短路径算法的具体流程如下：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。该算法的基本思想是：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出n-1条互不构成回路的权值最小边为止。【算法】/*对图定义一种新的表示方法，以一维数组存放图中所有边，并在构建图的存储结构时将它构造为一个“有序表”。以顺序表MSTree返回生成树上各条边。*/typedefstrnct{VertexTypevex1;VertexTypevex2;VRTypeweight;}EdgeType;typedefElemTypeEdgeType;typedefstruct{//有向网的定义VertexTypevexs[MAX_VERTEX_NUM];//顶点信息EdgeTypeedge[MAX_EDGE_NUM];//边的信息Mtvexnum,arcnum;//图中顶点的数目和边的数目}ELGraph;voidMiniSpanTree_Kruskal(ELGraphG,SqListInitSet(F,G.vexnum);//将森林F初始化为n棵树的集合InitList(MSTree,G.vexaum);//初始化生成树为空树i=O;k=l;while(k＜{{U}}(1){{/U}}){e=G.edge[i];//取第i条权值最小的边rl=fix_mfset(F,LocateVex(e.vexl));r2={{U}}(2){{/U}}//返回两个顶点所在树的树根if(ri{{U}}(3){{/U}}r2){//选定生成树上第k条边if(Listlnsert(MSTree,k,e)){{U}}(4){{/U}};//插入生成树mix_mfset(F,ri,r2);//将两棵树归并为一棵树}{{U}}(5){{/U}};//继续考察下一条权值最小边}DestroySet(F);}

问答题[说明]某机器上需要处理n个作业job1，job2，…，jobn，其中：(1)每个作业jobi(1≤i≤n)的编号为i，jobi有一个收益值P[i]和最后期限值d[i]；(2)机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；(3)job1～jobn的收益值呈非递增顺序排列，即p[1]≥p[2]≥…≥p[n]；(4)如果作业jobi在其期限之内完成，则获得收益p[i]；如果在其期限之后完成，则没有收益。为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图3-25是基于贪心策略求解该问题的流程图。(1)整型数组J[]有n个存储单元，变量k表示在期限之内完成的作业数，J[1..k]存储所有能够在期限内完成的作业编号，数组J[1..k)里的作业按其最后期限非递减排序，即d[J[1]]≤…≤d[J[k]]。(2)为了便于在数组J中加入作业，增加一个虚拟作业job0，并令d[0]=0，J[0]=0。(3)算法大致思想是：先将作业job1的编号1放入J[1]，然后，依次对每个作业jobi(2≤i≤n)进行判定，看其能否插入到数组J中。若能，则将其编号插入到数组J的适当位置，并保证J中作业按其最后期限非递减排列；否则不插入。jobi能插入数组J的充要条件是：jobi和数组J中已有作业均能在其期限之内完成。(4)流程图中的主要变量说明如下。i：循环控制变量，表示作业的编号；k：表示在期限内完成的作业数；r：若jobi能插入数组J，则其在数组J中的位置为r+1；q：循环控制变量，用于移动数组J中的元素。1.[问题1]请将图3-25中的(1)～(3)空缺处的内容填写完整。

问答题阅读下列说明和数据流图，回答问题1至问题3，将解答填入对应栏内。[说明]下面给出的是某房产管理系统的一套分层数据流图。其功能描述如下：(1)系统随时根据住房送来的入住单更新住户基本信息文件；(2)每月初系统根据物业管理委员会提供的月附加费(例如清洁费、保安费、大楼管理费等)表和房租调整表，计算每家住户的月租费(包括月附加费)，向住户发出交费通知单。住户交费时，系统输入交费凭证，核对后输出收据给住户；(3)系统定期向物业管理委员会提供住房分配表和交费清况表；(4)住户因分户或换房，在更新住户基本信息文件的同时，系统应立即对这些住户做月租费计算，以了结分户或换房前的房租。以下是经分析得到的数据流图及部分数据字典，有些地方有待填充，假定顶层数据流图是正确的。图1-1是项层数据流图，图1-2是第0层数据流图，图1-3是第1层数据流图，其中A是加工1的细化图，B是加工2的细化图。假定题中提供的顶层图是正确的，请回答下列问题。[图1-1][图1-2][图1-3]

问答题例如：设散列函数为Hash(Key)=Keymod7，记录的关键字序列为15,14,21,87,97,293,35,24,149,19,63,16,103,77,5,153,145,356,51,68,705,453，建立的散列文件内容如图所示。为简化起见，散列文件的存储单位以内存单元表示。函数InsertToHashTable(intNewElemKey)的功能是：将元素NewEIemKey插入散列桶中，若插入成功则返回0，否则返回-1。采用的散列函数为Hash(NewElemKey)=NewElemKey%P，其中P为设定的基桶数目。函数中使用的预定义符号如下：#defineNULLKEY-1/*散列桶的空闲单元标识*/#defineP7/*散列文件中基桶的数目*/#defineITEMS3/*基桶和溢出桶的容量*/typedefstructBucketNode/*基桶和溢出桶的类型定义*/intKcyData[ITEMS];structBucketNode*Link;BUCKET;BUCKETBucket[P];/*基桶空间定义*/[函数]intlnsertToHashTable(intNewElemKey)/*将元素NewElemKey插入散列桶中，若插入成功则返回0，否则返回-1*//*设插入第一个元素前基桶的所有KeyData[]、Link域已分别初始化为NULLKEY、NULL*/intIndex;/*基桶编号*/inti,k;BUCKET*s,*front,*t;(1);for(i=0;i＜ITEMS;i++)/*在基桶查找空闲单元，若找到则将元素存入*/if(Bucket[Index].KeyData[i]=NULLKEY)Bucket[Index].KeyData[i]=NewElemKey;break;if((2))return0;/*若基桶已满，则在溢出桶中查找空闲单元，若找不到则申请新的溢出桶*/(3);t=Bucket[Index].Link;if(t!=NULL)/*有溢出桶*/while(t!=NULL)for(k=0;k＜ITEMS;k++)if(t-＞KeyData[k]=NULLKEY)/*在溢出桶链表中找到空闲单元*/t-＞KeyData[k]=NewElemKey;break;/*if*/front=t;if((4))t=t-＞Link;elsebreak;/*while*//*if*/if((5))/*申请新溢出桶并将元素存入*/s=(BUCKET*)malloe(sizeof(BUCKET));if(!s)return-1;s-＞Link=NULL;for(k=0;k＜ITEMS;k++)s-＞KeyData[k]=NULLKEY;s-＞KeyData[0]=NewElemKey;(6);/*if*/return0;/*InsertToHashTable*/

问答题{{B}}试题1～试题4是必答题{{/B}}阅读以下关于住宅安全系统的技术说明，根据要求回答问题1～问题4。[说明]基于某嵌入式系统的住宅安全系统可使用传感器(如红外探头、摄像头等)来检测各种意外情况，如非法进入、火警和水灾等。房主可以在安装该系统时配置安全监控设备(如传感器、显示器、报警器等)，也可以在系统运行时修改配置，通过录像机和电视机监控与系统连接的所有传感器，并通过控制面板上的键盘与系统进行信息交互。在安装过程中，系统给每个传感器赋予一个ID编号和类型，并设置房主密码以启动和关闭系统，设置传感器事件发生时应自动拨出的电话号码。当系统检测到一个传感器事件时，就激活警报，拨出预置的电话号码，并报告关于位置和检测到的事件的性质等信息。住宅安全系统的顶层数据流图如图6-13所示，图6-14是住宅安全系统的第0层数据流图，图6-15是对住宅安全系统的第0层数据流图中加工4的细化图。

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

问答题试题一（共15分）阅读以下说明和图，回答问题1至问题3.将解答填入答题纸的对应栏内。【说明】某时装邮购提供商拟开发订单处理系统，用于处理客户通过电话、传真、邮件或Web站点所下订单。其主要功能如下：（1）增加客户记录。将新客户信息添加到客户文件，并分配一个客户号以备后续使用。（2）查询商品信息。接收客户提交商品信息请求，从商品文件中查询商品的价格和可订购数量等商品信息，返回给客户。（3）增加订单记录。根据客户的订购请求及该客户记录的相关信息，产生订单并添加到订单文件中。（4）产生配货单。根据订单记录产生配货单，并将配货单发送给仓库进行备货；备好货后，发送备货就绪通知。如果现货不足，则需向供应商订货。（5）准备发货单。从订单文件中获取订单记录，从客户文件中获取客户记录，并产生发货单。（6）发货。当收到仓库发送的备货就绪通知后，根据发货单给客户发货；产生装运单并发送给客户。（7）创建客户账单。根据订单文件中的订单记录和客户文件中的客户记录，产生并发送客户账单，同时更新商品文件中的商品数量和订单文件中的订单状态。（8）产生应收账户。根据客户记录和订单文件中的订单信息，产生并发送给财务部门应收账户报表。现采用结构化方法对订单处理系统进行分析与设计，获得如图1-1所示的顶层数据流图和图1-2所示0层数据流图。注：名称使用说明中的词汇，起点和终点均使用图1-2中的符号或词汇。

问答题试题五(共15分)阅读下列说明和C++代码，将应填入____(n)____处的字句写在答题纸的对应栏内。[说明]现欲开发一个软件系统，要求能够同时支持多种不同的数据库，为此采用抽象工厂模式设计该系统。以SQLServer和Access两种数据库以及系统中的数据库表Department为例，其类图如图5-1所示。

问答题【问题 3】(2 分) 对于本题的作业处理问题，用图4-1 的贪心算法策略，能否求得最高收益？ (6) 。用贪心算法求解任意给定问题时，是否一定能得到最优解？ (7) 。

问答题试题四（共15分）阅读下列说明，回答问题1至问题2，将解答填入答题纸的对应栏内。【说明】0-1背包问题可以描述为：有n个物品，对i=1,2,···,n，第i个物品价值为vi,重量为wi(vi和wi为非负数），背包容量为W(W为非负数)，选择其中一些物品装入背包，使装入背包物品的总价值最大，即,且总重量不超过背包容量，即,其中，xi∈{0,1},xi=0表示第i个物品放入背包。

问答题[说明] ①为类Circle增加一个构造函数，该函数有一个参数，并在构造时将该参数值赋给成员 radius。将该函数实现为一个非内联函数，并且使用参数列表的方式将类成员赋值。 ②为类Circle增加一个成员函数print()，使得可以输出有关圆的信息，比如下列程序 Circle c； c. SetRadius(5)； c. Print()； 将输出：The circle has radius of 5! ③完成友元函数void CompareR(Circle *c1，Circle *c2)的定义，在屏幕中输出c1与c2比较radius大小结果，要求使用if - else结构完成。 输出结果如下： The circle has radus of 5 ! The circle has radius of 10 ! cl ＜c2 源程序文件test7_3, cpp 清单如下: #include ＜ iostream, h ＞ class Circle { public: Circle( ) :radius(5) {} {{U}} (1) {{/U}} void SetRadius(int r) { radius = r; } int GetRadius() { return radius; } {{U}} (2) {{/U}} friend void CompareR(Circle * c1,Circle * c2); private: int radius; }; void CompareR(Circle * c! ,Circle * c2) { {{U}} (3) {{/U}} cout ＜＜ "c1 ＞ c2" ＜＜ endl; else if ( (c1 -＞ GetRadius( )) == (c2 -＞ GetRadius( ))) tout ＜ ＜"c1=c2' ＜ ＜ endl; else if ( (c1 -＞ GetRadius( )) ＜ ( c2 -＞ GetRadius( ))) cout ＜＜"c1＜c2" ＜＜endl; void main( ) Circle c1 c1. SetRadius(5) c1. Print( ) Circle c2(10); c2. Print( ) CompareR( }