问答题【说明】StringEditor类的功能是：已知一个字符串，返回将字符串中的非字母字符都删除后的字符串。 public{{U}} (1) {{/U}}{ public static String removeNonLetters({{U}} (2) {{/U}}){ StringBuffer aBuffer={{U}} (3) {{/U}}; char aCharacter; for(int i=0; i＜original.length();i++){ aCharacter={{U}} (4) {{/U}}; if(Character.isLetter(aCharacter)) aBuffer.append({{U}} (5) {{/U}}); } return new String(aBuffer); } } public class StringEditorTester{ public static void main(String args[]){ String original="Hi!, My Name is Mark, 234I think you are my classmate?!!"; System.out.println(StringEditor.removeNonLetters(original)); } }

问答题[说明] 一个描述学校的部分关系模式的结果描述如下： 1．一个系有若干学生，但一个学生只能在一个系； 2．一个系只有一名主任； 3．一个学生可以选修多门课程，每门课程有若干学生选修； 4．每个学生所学的每门课程都有一个成绩； 5．“学生”和“课程表”及“选课表”的关系示例分别如表1、表2、表3所示。 Student(学生表)的字段按顺序为学号(Sno)、姓名(Sname)、性别(Ssex)、年龄(Sage)、所属院系(Sdept)、系主任(Smaster)； Course(课程表)的字段按顺序为课程编号(Cno)、课程名(Cname)、先行课程(Cpno)、课程学分 (Ccredit)； SC(选课表)的字段按顺序为学号(Sno)、课程号(Cno)、成绩(Grade)。 各表的记录如下： 表1 Student Sno Sname Ssex Sage Sdept Smaster 95001 李勇 男 20 CS 王平 95002 刘晨 女 19 IS 周言 95003 王明 女 18 MA 展评 95004 张立 男 19 IS 周言 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　表2 Course Cno Cname Cpno Ceredit 1 　数据库 5 4 2 　数学 2 3 　信息系统 1 4 4 　操作系统 6 3 5 　数据结构 7 4 6 　数据处理 2 7 　PASCAL 6 4 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　表3 SC 　Sno 　Cno 　Grade 　95001 　1 　92 　95001 　2 　85 　95001 　3 　88 　95002 　2 　90 　95003 　3 　80

问答题[问题1]（6 分） （1） 数据流图1-1 缺少了一条数据流(在图1-2 中也未给出该数据流)，请给出此数据流的起点和终点，并采用说明中的词汇给出此数据流名。 （2） 数据流图1-2 中缺少了与“查询房屋”加工相关的数据流，请指出此数据流的起点和终点。

问答题【函数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，则返回1j =0;while(i＜{{U}} (1) {{/U}}else{{U}} (2) {{/U}};if(A. length == B. length) return(0);else if(A. length＜B. length)return(-1);else return(1)}//compare //函数1的时间复杂度是{{U}} (3) {{/U}}。 【函数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({{U}} (6) {{/U}} //以指针ha记a1结点的位置 L -＞ next = p -＞ next; //将B1结点链接在头结点之后 p -＞ next = NULL; //设am的后继为空 q={{U}} (7) {{/U}}; //令q指向b1结点 while(q-＞next)q ={{U}} (8) {{/U}}; //查找bn结点 q-＞＞next={{U}} (9) {{/U}}; //将a1结点链接到bn结点之后 }}}//函数2的时间复杂度是{{U}} (10) {{/U}}。

问答题【问题3】如果限制该算法最多输出K个可供选择的房间号，则在流程图1的。所指的判断框应改成什么处理?[流程图1](如图2所示)

问答题[说明]在一个分布网络中，资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中，资源会有损耗。例如，天然气的气压会减少，电压会降低。我们将需要输送的资源信息称为信号。在信号从信源地送往消耗地的过程中，仅能容忍一定范围的信号衰减，称为容忍值。分布网络可表示为一个树型结构，如图1所示。信号源是树根，树中的每个节点(除了根)表示一个可以放置放大器的子节点，其中某些节点同时也是信号消耗点，信号从一个节点流向其子节点。每个节点有一个d值，表示从其父节点到该节点的信号衰减量。例如，在图1中，节点w、p、q的d值分别为2、1、3，树根节点表示信号源，其d值为0。每个节点有一个M值，表示从该节点出发到其所有叶子节点的信号衰减量的最大值。显然，叶子节点的M值为0。对于非叶子节点j，M(j)=max{M(k)+d(k)|k是j的子节点}。在此公式中，要计算节点的M值，必须先算出其所有子节点的M值。在计算M值的过程中，对于某个节点i，若其有一个子节点k满足d(k)+Mfk)大于容忍值，则应在k处放置放大器，否则，从节点i到某叶子节点的信号衰减量会超过容忍值，使得到达该叶子节点时信号不可用，而在节点i处放置放大器并不能解决到达叶子节点的信号衰减问题。例如，在图1中，从节点P到其所有叶子节点的最大衰减值为4。若容忍值为3，则必须在s处放置信号放大器，这样可使得节点p的M值为2。同样，需要在节点q、v处放置信号放大器，如图2阴影节点所示。若在某节点放置了信号放大器，则从该节点输出的信号与信号源输出的信号等价。函数placeBoosters(TreeNode*root)的功能是：对于给定树型分布网络中的各个节点，计算其信号衰减量的最大值，并确定应在树中的哪些节点放置信号放大器。全局变量Tolerance保存信号衰减容忍值。树的节点类型定义如下：typedefstructTreeNode{intid;/*当前节点的以别号*/intChildNum;/*当前节点的子节点数目*/intd;/*父节点到当前节点的信号衰减值*/structTreeNode**childptr;/*向量，存放当前节点到其所有子节点的指针*/intM;/*当前节点到其所有子节点的信号衰减值中的最大值*/boolboost;/*是否存当前节点放置信号放大器的标志*/}TreeNode;[C程序]voidplaceBooster(TreeNode*root){/*计算root所指节点处的衰减量，如果衰减量超出了容忍值，则放置放大器*/TreeNode*P;inti,degradation;if(______){degradation=0;root→M=0;i=0;if(i＞=root→ChildNum)return;p=______;for(;i＜root→ChildNumi++,p=______){p→M=0;______;if(p→d+p→M＞Tolerance)/*在p所指节点中放置信号放大器*/{p→boost=true;P→M=0;}if(p→d+p→M＞degradation)degradation=p→d+p→M;}Root→M=______;}}

问答题某城市拟开发一个基于Web的城市黄页，公开发布该城市重要的组织或机构(一下统称为客户)的基本信息，方便城市生活。该系统的主要功能描述如下：(1)搜索信息：任何使用Internet的网络用户都可以搜索发布在城市黄页中的信息，例如客户的名称、地址、联系电话等。(2)认证：客户若想在城市黄页上发布信息，需通过系统的认证。认证成功后，该客户成为系统授权用户。(3)更新信息：授权用户登录系统后，可以更改自己在城市黄页中的相关信息，例如变更联系电话等。(4)删除客户：对于拒绝继续在城市黄页上发布信息的客户，有系统管理员删除该客户的相关信息。系统采用面向对象方法进行开发，在开发过程中认定出如下表所示的类。系统的用例图和类图分别如图1和图2所示。类列表类名说明InternetClient网络用户CustomerList客户集.维护城市黄页上的所有客户信息Customer客户信息，记录单个客户的信息RegisteredClient授权用户Administrator系统管理员

问答题问题：6.1 （15分） 阅读上述说明和Java代码，将应填入 (n) 处的字句写在答题纸的对应栏内。

问答题【问题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]