问答题【问题1】 经过进一步分析，设计人员决定定义一个类Items_on_loan，以表示类Book和ED的共有属性和方法。请采用图3-3中属性和方法的名称给出类Items_on_loan应该具有的属性和方法 (注意：不同名称的属性和方法表示不同的含义，如CD中的composer与Book中的author无任何关系)。

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

问答题【说明】设M叉树采用列表法表示，即每棵子树对应一个列表，列表的结构为：子树根节点的值部分(设为一个字符)和用“()”，括起来的各子树的列表(如有子树的话)，各子列表间用“，”分隔。例如下面的三叉树可用列表a(b(c，d)，e，f(g，h，i))表示。本程序输入列表，生成一棵M叉树，并由M叉树输出列表。假定输入无错误。【函数5-8】#inelude＜stdio.h＞#include＜stdlib.h＞#defineM3typedefstructnode{charval;streetnode*subTree[M];}NODE;charbuf[255],*six=buf;NODE*d=NULL;NODE*makeTree()/*由列表生成M叉树*/{intk;NODE*s;s={{U}}(1){{/U}};s-＞val=*six++;for(k=0;k＜M;k++)s-＞subTree[k]=NULL;if(*str=='('){k=0;do{six++;s-＞subTree[k]={{U}}(2){{/U}};if(*str==')'){six++;break;}k=k+1;}while({{U}}(3){{/U}});}returns;}voidwalkTree(NODE*t)/*由M叉数输出列表*/{inti;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}putchax(')');}}voidmain(){prinff("Enterexp:");scanf("%s",str);d=makeTree();walkTree(d);putchaW',n');}

问答题阅读以下说明和图，回答问题1至问题3，将解答填入对应栏内。[说明]某房屋租赁公司欲建立一个房屋租赁服务系统，统一管理房主和租赁者的信息，从而快速地提供租赁服务。该系统具有以下功能。(1)登记房主信息。对于每名房主，系统需登记其姓名、住址和联系电话，并将这些信息写入房主信息文件。(2)登记房屋信息。所有在系统中登记的房屋都有一个唯一的识别号(对于新增加的房屋，系统会自动为其分配一个识别号)。除此之外，还需登记该房屋的地址、房型(如平房、带阳台的楼房、独立式住宅等)、最多能够容纳的房客数、租金及房屋状态(待租赁、已出租)。这些信息都保存在房屋信息文件中。一名房主可以在系统中登记多个待租赁的房屋。(3)登记租赁者信息。所有想通过该系统租赁房屋的租赁者，必须首先在系统中登记个人信息，包括：姓名、住址、电话号码、出生年月和性别。这些信息都保存在租赁者信息文件中。(4)租赁房屋。已经登记在系统中的租赁者，可以得到一份系统提供的待租赁房屋列表。一旦租赁者从中找到合适的房屋，就可以提出看房请求。系统会安排租赁者与房主见面。对于每次看房，系统会生成一条看房记录并将其写入看房记录文件中。(5)收取手续费。房主登记完房屋后，系统会生成一份费用单，房主根据费用单交纳相应的费用。(6)变更房屋状态。当租赁者与房主达成租房或退房协议后，房主向系统提交变更房屋状态的请求。系统将根据房主的请求，修改房屋信息文件。图15-11和图15-12分别给出了该系统的顶层数据流图和第0层数据流图。

问答题阅读下列说明和流程图(如图17-1所示)，回答问题，把解答填入对应栏内。[说明]本流程图描述了某子程序的处理流程，现要求用白盒测试法对子程序进行测试。[问题]根据判定覆盖、条件覆盖、判定/条件覆盖、多重条件覆盖(条件组合覆盖)和路径覆盖5种覆盖标准，从供选择的答案中分别找出满足相应覆盖标准的最小的测试数据组(用①～⑩表示)。供选择的答案如下①a=5，b=1②a=5，b=-1③a=5，b=1④a=5，b=1a=-5，b=-1a=0，b=-1⑤a=5，b=-1⑥a=5，b=1a=5，b=1a=0，b=0a=-5，b=-1a=-5，b=-1⑦a=5，b=1⑧a=5，b=1a=0，b=1a=0，b=-1a=0，b=-1a=5，b=1a=-5，b=1a=5，b=-1⑨a=5，b=1⑩d=5，b=1a=0，b=-1a=5，b=0a=0，b=1a=5，b=-1a=-5，b=1a=0，b=1a=-5，b=-1a=0，b=0a=0，b=-1a=5，b=1a=-5，b=0a=-5，b=1

问答题【问题2】 依据上述说明中给出的词语，将图3-7中的(1)～(5)处补充完整。

问答题【问题3】 写出子程序B的功能，并顺序写出实现该功能的操作。

问答题阅读下列说明和图，回答下面问题。[说明]某慈善机构欲开发一个募捐系统，已跟踪记录为事业或项目向目标群体进行募捐而组织的集体性活动。该系统的主要功能如下所述。(1)管理志愿者。根据募捐任务给志愿者发送加入邀请、邀请跟进、工作任务；管理志愿者提供的邀请响应、志愿者信息、工作时长、工作结果等。(2)确定募捐需求和收集所募捐赠(资金及物品)。根据需求提出募捐任务、活动请求和捐赠请求，获取所募集的资金和物品。(3)组织募捐活动。根据活动请求，确定活动时间范围。根据活动时间，搜索场馆，即：向场馆发送场馆可用性请求，获得场馆可用性。然后根据活动时间和地点推广募捐活动，根据相应的活动信息举办活动，从募捐机构获取资金并向其发放赠品。获取和处理捐赠，根据捐赠请求，提供所募集的捐赠；处理与捐赠人之间的交互，即：录入捐赠人信息，处理后存入捐赠人信息表；从捐赠人信息表中查询捐赠人信息，向捐赠人发送募捐请求，并将已联系的捐赠人存入已联系的捐赠人表。根据捐赠请求进行募集，募得捐赠后，将捐赠记录存入捐赠表；对捐赠记录进行处理后，存入已处理捐赠表，向捐赠人发送致谢函，根据已联系的捐赠人和捐赠记录进行跟踪，将捐赠跟进情况发送给捐赠人。先采用结构化方法对募捐系统进行分析与设计，获得如图1至图3所示的分层数据流图。图10层数据流图图21层数据流图图32层数据流图

问答题阅读下列说明和C代码，回答下面问题。 [说明] 设有m台完全相同的机器运行n个独立的任务，运行任务i所需要的时间为t i ，要求确定一个调度方案，使的完成所有任务所需要的时间最短。 假设任务已经按照其运行时间从大到小排序，算法基于最长运行时间作业优先的策略；按顺序先把每个任务分配到一台机器上，然后将剩余的任务一次放入最先空闲的机器。 [C代码] 下面是算法的C语言实现。 (1)常量和变量说明 ●m：机器数。 ●n：任务数。 ●t[]：输入数组，长度为n，其中每个元素表示任务的运行时间，下标从0开始。 ●s[][]：二维数组，长度为m*n，下标从0开始，其中元素s[i][j]表示机器i运行的任务j的编号。 ●d[]：数组，长度为m其中元素d[i]表示机器i的运行时间，下标从0开始。 ●count[]：数组，长度为m，下标从0开始，其中元素count[i]表示机器i运行的任务数。 ●i：循环变量。 ●i：循环变量。 ●k：临时变量。 ●max：完成所有任务的时间。 ●min：临时变量。 (2)函数schedule void schedule() { int i,j,k max=0; for(i=0; i＜m;i++) { d[i]=0; for(j=0;j＜n;j++) { s[i][j]=0; } } for(i=0;i＜m;i++) { //分配前m个任务 s[i][0]=i; ______; count[i]=1; } for(______;i＜n;i++) { //分配后n-m个任务 int min=d[0]; k=0; for(j=1;j＜m;j++) { //确定空闲机器 if(min＞d[j]) { min=d[j]; k=j; //机器k空闲 } } ______; count[k]=count[k]+1; d[k]=d[k]+t[i]; for(i=0;i＜m;i++) { //确定完成所有任务所需要的时间 if(______) { max=d[i]; } } } }

问答题阅读下列说明和Java代码，在(n)处填入适当的字句。[说明]已知某企业欲开发一家用电器遥控系统，即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器如图10.33所示。该遥控器共有4个按钮，编号分别是0至3，按钮0和2能够遥控打开电器1和电器2，按钮1和3则能遥控关闭电器1和电器2。由于遥控系统需要支持形式多样的电器，因此，该遥控系统的设计要求具有较高的扩展性。现假设需要控制客厅电视和卧室电灯，对该遥控系统进行设计所得类图如10.34所示。图10.34中，类RomoteController的方法onPressButton(intbutton)表示当遥控器按键按下时调用的方法，参数为按键的编号；Command接口中on和off方法分别用于控制电器的开与关；Light中turnLight(intdegree)方法用于调整电灯光的强弱，参数degree值为0时表示关灯，值为100时表示开灯并且将灯光亮度调整到最大；TV中setChannel(intchannel)方法表示设置电视播放的频道，参数channel值为0时表示关闭电视，为l时表示开机并将频道切换为第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();elsecommnands[button].off();publicvoidsetComrnand(intbutton,Commandcommand)(1)=command;//设置每个按钮对应的命令对象;classLightCommandimplementsCommand//电灯命令类protectedLightlight;//指向要控制的电灯对象publicvoidon()light.turnLight(100);;publicvoidoff()light.(2);;publicLightCommand(Lightliaht)this.light=light;;；classTVCornmandimplementsCommand//电视机命令类protectedTVtv;//指向要控制的电视机对象publicvoidon()tv.(3);;publicvoidoff()tv.setChannel(0);;publicTVCommand(TVtv)this.tv=tv;;；publicclassrspublicstaticvoidmain(String[]args)Lightlight=newLight()；TVtv=newTV();//创建电灯和电视对象LightCommandlightCommand=newLightCommand(light);TVCommandtvCommand=newTVCommand(tv);RemoteControllerremoteController=newRemoteController();//设置按钮和命令对象remoteController.setCommand(0,(4));…//此处省略设置按钮1、按钮2和按钮3的命令对象代码本题中，应用命令模式能够有效让类(5)和类(6)、类(7)之间的耦合性降至最小。

问答题阅读以下说明和图，回答问题1至问题4，将解答填入对应栏内。 [说明] 某音像制品出租商店欲开发一个音像管理信息系统，管理音像制品的租借业务。需求如下： (1)系统中的客户信息文件保存了该商店的所有客户的用户名、密码等信息。对于首次来租借的客户，系统会为其生成用户名和初始密码。 (2)系统中音像制品信息文件记录了商店中所有音像制品的详细信息及其库存数量。 (3)根据客户所租借的音像制品的品种，会按天收取相应的费用。音像制品的最长租借周期为一周，每位客户每次最多只能租借6件音像制品。 (4)客户租借某种音像制品的具体流程为： ①根据客户提供的用户名和密码，验证客户身份。 ②若该客户是合法客户，则查询音像制品信息文件，查看商店中是否还有这种音像制品。 ③若还有该音像制品，且客户所要租借的音像制品数小于等于6件，就可以将该音像制品租借给客户。这时，系统给出相应的租借确认信息，生成一条新的租借记录并将其保存在租借记录文件中。 ④系统计算租借费用，将费用信息保存在租借记录文件中并告知客户。 ⑤客户付清租借费用之后，系统接收客户付款信息，将音像制品租借给该客户。 (5)当库存中某音像制品数量不能满足客户的租借请求数量时，系统可以接受客户网上预约租借某种音像制品。系统接收到预约请求后，检查库存信息，验证用户身份，创建相应的预约记录，生成预约流水号给该客户，并将信息保存在预约记录文件中。 (6)客户归还到期的音像制品，系统修改租借记录文件，并查询预约记录文件和客户信息文件，判定是否有客户预约了这些音像制品。若有，则生成预约提示信息，通知系统履行预约服务，系统查询客户信息文件和预约记录文件，通知相关客户前来租借音像制品。

问答题阅读下列说明和UML图，回答问题。[说明]某企业为了方便员工用餐，餐厅开发了一个订餐系统(CafeteriaOrderingSystem，COS),企业员工可通过企业内联网使用该系统。企业的任何员工都可以查看菜单和今日特价。系统的顾客是注册到系统的员工，可以订餐(如果未登录，需先登录)、注册工资支付、预约规律的订餐，在特殊情况下可以覆盖预订。餐厅员工是特殊顾客，可以进行备餐、生成付费请求和请求送餐，其中对于注册工资支付的顾客生成付费请求并发送给工资系统。菜单管理员是餐厅特定员工，可以管理菜单。送餐员可以打印送餐说明，记录送餐信息(如送餐时间)以及记录收费(对于没有注册工资支付的顾客，由送餐员收取现金后记录)。顾客订餐过程如下。(1)顾客请求查看菜单。(2)系统显示菜单和今日特价。(3)顾客选菜。(4)系统显示订单和价格。(5)顾客确认订单。(6)系统显示可送餐时间。(7)顾客指定送餐时间、地点和支付方式。(8)系统确认接收订单，然后发送Email给顾客以确认订餐，同时发送相关订餐信息通知给餐厅员工。系统采用面向对象方法开发，使用UML进行建模。系统的顶层用例图和一次订餐的活动图初稿分别如图10.13和图10.14所示。[问题1]根据说明中的描述，给出图10.13中A1和A2所对应的参与者。[问题2]根据说明中的描述，给出图10.14缺少的4个用例及其所对应的参与者。[问题3]根据说明中的描述，给出图10.14中(1)～(4)处对应的活动名称或图形符号。[问题4]指出图10.13中员工和顾客之间是什么关系，并解释该关系的内涵。

问答题阅读下列说明和C代码，回答问题。[说明]堆数据结构定义如下。对于n个元素的关键字序列a1，a2，…，an，当且仅当满足下列关系时称其为堆。在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若堆顶元素为最小元素，则称为小顶堆。堆常用完全二叉树表示，图8.7是一个大顶堆的例子。堆数据结构常用于优先队列中，以维护由一组元素构成的集合。对应于两类堆结构，优先队列也有最大优先队列和最小优先队列，其中最大优先队列采用大顶堆，最小优先队列采用小项堆。以下考虑最大优先队列。假设现已建好大顶堆A，且已经实现了调整堆的函数heapify(A，n，index)。下面将C代码中需要完善的3个函数说明如下。(1)heapMaximum(A)：返回大项堆A中的最大元素。(2)heapExtractMax(A)：去掉并返回大顶堆A的最大元素，将最后一个元素“提前”到堆顶位置，并将剩余元素调整成大顶堆。(3)maxHeapInsert(A，key):把元素key插入到大顶堆A的最后位置，再将A调整成大顶堆。优先队列采用顺序存储方式，其存储结构定义如下。#definePARENT(i)i/2typedefstructarrayint*int_array;//优先队列的存储空间首地址intarray_size;//优先队列的长度intcapacity;//优先队列存储空间的容量ARRAY;[C代码](1)函数heapMaximumintheapMaximum(ARRAY*A)return(1);(2)函数heapExtractMaxint_heapExtractMax(ARRAY*A)intmax;max=A-＞int_array[0]；(2);A-＞array_size--;Heapify(A,A-＞array_size,0);//将剩余元素调整成大顶堆returnmax;)(3)函数maxHeaplnsertintmaxHeaplnsert(ARRAY*A,intkey)inti,*p;if(A-＞array-size==A-＞capacity)//存储空间的容量不够时扩充空间p=(int*)realloc(A-＞intarray,A-＞capacity*2*sizeof(int));if(!p)return-1;A-＞int_array=P;A-＞capacity=2*A-＞capacity;A-＞array_size++:i=(3)；while(i＞0＆＆(4))A-＞int_array[i]=A-＞int_array[PARENT(i)];i=PARENT(i);(5);return0;[问题1]根据以上说明和C代码，填充C代码中的空(1)～(5)。[问题2]根据以上C代码，函数heapMaximum,heapExtractMax和maxHeaplnsert的时间复杂度的紧致上界分别为(6)、(7)和(8)(用O符号表示)。[问题3]若将元素10插入到堆A=(15,13,9，5，12,8，7，4，0，6，2，1)中，调用maxHeaplnsert函数进行操作，则新插入的元素在堆A中第(9)个位置(从1开始)。

问答题阅读以下说明和C++代码，将应填入______处的字句写在下面。[说明]欲开发一个绘图软件，要求使用不同的绘图程序绘制不同的图形。以绘制直线和圆形为例，对应的绘图程序如下表所示。不同的绘图程序DPIDP2绘制直线drawaline(x1,y1,x2,y2)drawline(x1,x2,y1,y2)绘制圆drawacircle(x,y,r)drawcircle(x,y,r)该绘图软件的扩展性要求，将不断扩充新的图形和新的绘图程序。为了避免出现类爆炸的情况，现采用桥接(Bridge)模式来实现上述要求，得到如下图所示的类图。某绘图软件类图[C++代码]classDP1{public:staticvoiddraw_aline(doublex1,doubley1,doublex2,doubley2){/*代码省略*/}staticvoiddraw_a_circle(doublex,doubley,doubler){/*代码省略*/)};ClassDP2{public:staticvoiddrawline(doublex1,doublex2,doubley1,doubley2){/*代码省略*/}staticvoiddrawcircle(doublex,doubley,doubler){/*代码省略*/}};classDrawing{public:______;______;};classV1Drawing:publicDrawing{public:voiddrawLine(doublex1,doubley1,doublex2,doubley2){/*代码省略*/)voiddrawCircle(doublex,doubley,doubler){______;}};classV2Drawing:publicDrawing{public:voiddrawLine(doublex1,doubley1,doublex2,doubley2){/*代码省略*/)voiddrawCircle(doublex,doubley,doubler){______;)};classShape{public:______;Shape(Drawing*dp){_dp=dp;}voiddrawLine(doublex1,doubley1,doublex2,doubley2){_dp-＞drawLine(x1,y1,x2,y2);}voiddrawCircle(doublex,doubley,doubler){_dp-＞drawCircle(x,y,r);}private:Drawing*_dp;};classRectangle:publicShape{public:voiddraw(){/*代码省略*/}//其余代码省略};classCircle:publicShape{private:double_x,_y,_r;public:Circle(Drawing*dp,doublex,doubley,doubler):______{_x=x;_y=y;_r=r;}voiddraw(){drawCircle(_x,_y,_r);};

问答题阅读下列说明和C代码，回答下面问题。[说明]用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得n个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。算法步骤如下。(1)确定候选解上界为最短的单台处理机处理所有作业的完成时间m：(2)用p(x，y，k)=1表示前k个作业可以在A用时不超过x且在B用时不超过y时间内处理完成，则p(x，y，k)=p(x-ak，y，k-1)‖p(x，y-bk，k-1)(‖表示逻辑或操作)。(3)得到最短处理时间为min(max(x，y))。下面是该算法的C语言实现。(1)常量和变量说明n：作业数m：候选解上界a：数组，长度为n，记录n个作业在A上的处理时间，下标从0开始b：数组，长度为n，记录n个作业在B上的处理时间，下标从0开始k：循环变量p：三维数组，长度为(m+1)*(m+1)*(n+1)temp：临时变量max：最短处理时间(2)C代码#include＜stdio.h＞intn,m;inta[60],b[60],p[100][100][60];voidread(){/*输入n、a、b，求出m，代码略*/}voidschedule(){/*求解过程*/intx,y,k;for(x=0;x＜=m;x++){for(y=0;y＜m;y++){______for(k=1;k＜n;k++)p[x][y][k]=0;}}for(k=1;k＜n;k++){for(x=0;x＜=m;x++){for(y=0;y＜=m;y++){if(x-a[k-1]＞=0)______;if(______)p[x][y][k]=(p[x][y][k]||[x][y-b[k-1]][k-1]);}}}}voidwrite(){/*确定最优解并输出*/intx,y,temp,max=m;for(x=0;x＜=m;x++){for(y=0;y＜=m;y++){if(______){temp=______;if(temp＜max)max=temp;}}}printf("\n%d\n",max);}voidmain(){read();schedule();write();}

问答题阅读下列说明和c代码，回答问题1至问题3，将解答写在对应栏内。 [说明] 某应用中需要对100000个整数元素进行排序，每个元素的取值在0～5之间。排序算法的基本思想是：对每一个元素x，确定小于等于x的元素个数(记为m)，将x放在输出元素序列的第m个位置。对于元素值重复的情况，依次放入第m-1，m-2，…个位置。例如，如果元素值小于等于4的元素个数有10个，其中元素值等于4的元素个数有3个，则4应该在输出元素序列的第10个位置、第9个位置和第8个位置上。算法的具体步骤如下。 步骤1：统计每个元素值的个数。 步骤2：统计小于等于每个元素值的个数。 步骤3：将输入元素序列中的每个元素放入有序的输出元素序列。 [C代码] 下面是该排序算法的c语言实现。 (1)常量和变量说明 R：常量，定义元素取值范围中的取值个数，如上述应用中R值应取6； i：循环变量； n：待排序元素个数； a：输入数组，长度为n； b：输出数组，长度为n； c：辅助数组，长度为R，其中每个元素表示小于等于下标所对应的元素值的个数。 (2)函数sort 1 void sort(int n，int a[]，int b[]) 2 int c[R]，i； 3 for(i=0；i＜ (1) ；i++) 4 c[i]=0； 5 6 for(i=0；i＜n；i++) 7 c[a[i]]= (2) ； 8 9 for(i=1；i＜R；i++) 10 c[i]= (3) 11 12 for(i=0；i＜n；i++) 13 b[c[a[i]]-1]= (4) ； 14 c[a[i]]=c[a[i]]-1； 15 16

问答题阅读下列说明和C代码，回答问题1至问题3，将解答写在对应栏内。[说明]对有向图进行拓扑排序的方法如下。(1)初始时拓扑序列为空。(2)任意选择一个入度为0的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧。(3)重复(2)，直到不存在入度为0的顶点为止(若所有顶点都进入拓扑序列，则完成拓扑排序；否则，由于有向图中存在回路无法完成拓扑排序)。函数int*TopSort(LinkedDigraphG)的功能是对有向图G中的顶点进行拓扑排序，返回拓扑序列中的顶点编号序列，若不能完成拓扑排序，则返回空指针。其中，图G中的项点从1开始依次编号，顶点序列为v1，v2，…，vn，图G采用邻接表表示，其数据类型定义如下：#defineMAXVNUM50/*最大顶点数*/typedefstructArcNode/*表结点类型*/intadjvex；/*邻接顶点编号*/StructArcNode*nextarc；/*指示下一个邻接顶点*/ArcNode；typedefstructAdjList/*头结点类型*/charvdata；/*顶点的数据信息*/ArcNode*firstarc；/*指向邻接表的第一个表结点*/AdjList；typedefstructLinkedDigraph/*图的类型*/intn；/*图中顶点个数*/AdjListVhead[MAXVNUM]；/*所有顶点的头结点数组*/LinkedDigraph；例如，某有向图G如图21-13所示，其邻接表如图21-14所示。函数TopSort中用到了队列结构(Queue的定义省略)，实现队列基本操作的函数原型如表21-4所示。表21-4函数原型函数原型说明voidInitQueue(Queue*Q)初始化队列(构造一个空队列)boolIsEmpty(QueueQ)判断队列是否为空，若是则返回true，否则返回falsevoidEnQueue(Queue*Q，inte)元素入队列voidDeQueue(Queue*Q，int*p)元素出队列[C代码]int*TopSort；(LinkedDigraphG)ArcNode*p；/*临时指针，指示表结点*/QueueQ；/*临时队列，保存入度为0的顶点编号*/intk=0；/*临时变量，用作数组元素的下标*/intj=0，w=0；/*临时变量，用作顶点编号*/int*topOrder，*inDegree；topOrder=(int*)malloc((G.n+1)*sizeof(int))；/*存储拓扑序列中的顶点编号*/inDegree=(int*)malloc((G.n+1)*siZeof(int))；/*存储图G中各顶点的入度*/if(!inDegree||!topOrder)returnNULL；(1)；/*构造一个空队列*/for(j=1；j＜=G.n；j++)/*初始化*/topOrder[j]=0；inDegree[j]=0；for(j=1；j＜=G.n；j++)/*求图G中各顶点的入度*/for(p=G.Vhead[j].firstarc；p；p=p-＞nextarc)inDegree[p-＞adjvex]+=1；for(j=1；j＜=G.n；j++)/*将图G中入度为0的顶点保存在队列中*/if(0==inDegree[j])EnQueue(＆Q，j)；while(!IsEmpty(Q))(2)；/*队头顶点出队列并用W保存该顶点的编号*/topOrder[k++]=w；/*将顶点w的所有邻接顶点的入度减1(模拟删除顶点W及从该顶点出发的弧的操作)*/for(p=G.Vhead[w].firstare；p；p=p-＞nextarc)(3)-=1；if(0==(4))EnQueue(＆Q，p-＞adjvex)；/*for*//*while*/free(inDegree)；if((5))returnNULL；returntopOrder；/*TopSort*/

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

问答题阅读以下说明，回答下面问题。[说明]某宾馆需要建立一个住房管理系统，部分的需求分析结果如下。(1)一个房间有多个床位，同一房间内的床位具有相同的收费标准。不同房间的床位收费标准可能不同。(2)每个房间有房间号(如201、202等)、收费标准、床位数目等信息。(3)每位客人有身份证号码、姓名、性别、出生日期和地址等信息。(4)对每位客人的每次住宿，应该记录其入住日期、退房日期和预付款额信息。(5)管理系统可查询出客人所住房间号。根据以上的需求分析结果，设计一种关系模型如图所示。住房管理系统的实体联系图

问答题阅读下列说明和Java代码，将应填入______处的字句写在下面。[说明]某灯具厂商欲生产一个灯具遥控器，该遥控器具有7个可编程的插槽，每个插槽都有开关按钮，对应着一个不同的灯。利用该遥控器能够统一控制房间中该厂商所有品牌灯具的开关，现采用Command(命令)模式实现该遥控器的软件部分，Command模式的类图如下图所示。Command模式类图[Java代码]classLight{publicLight(){};publicLight(stringname){/*代码省略*/}publicvoidon(){/*代码省略*/}//开灯publicvoidoff(){/*代码省略*/}//关灯};______{publicvoidexecute();}classLightOnCommandimplementsCommand{//开灯命令Lightlight;publicLightOnCommand(Lightlight){this.light=light;}publicVoidexecute(){______;}}classLightOffCommandimplementsCommand{//关灯命令Lightlight;publicLightOffCommand(Lightlight){this.light=light;}publicVoidexecute(){______;}}ClassRemoteControl{//遥控器Command[]onCommands[7];Command[]offCommands[7];PublicRemoteControl(){/*代码省略*/}PublicvoidsetCommand(intslotCommandonCommand,CommandOffCommand){______=onCommand;______=offCommand;}PubliCvoidonButtonWasPushed(intslot){______;)PublicvoidoffButtonWasPushed(intslot){______;}}ClassremoteLoader{publicstaticvoidmain(string[]args){RemoteControlremoteControl=newRemoteControl();LightlivingRoomLight=newLight("LivingRoom");LightkitchenLight=newLight("kitchen");LightOnCommandlivingRoomLightOn=newLightOnCommand(livingRoomLight);LightOffCommandlivingRoomLightOff=newLightOffCommand(liVingRoomLight);LightOnCommandkitchenLighton=newLightOnCommand(kitchenLight);LightOffCommandkitchenLightOff=newLightOffCommand(kitchenLight);remoteControl.setCommand(0,livingRoomLighton,livingRoomLightoff);remoteControl.setCommand(1,kitchenLighton,kitchenLightoff);remoteControl.onButtonWasPushed(0);remoteControl.offButtonWasPushed(0);remoteControl.onButtonWasPushed(1);remoteControl.offButtonWasPushed(1);}}