填空题阅读下列说明和C++代码，将应填入(n)处的字句写在对应栏内。[说明]现欲构造一棵文件/目录树，采用组合(Composite)设计模式来设计，得到的类图如图18-19所示。[C++代码]#include＜list＞#include＜iostream＞#include＜string＞uslngnamesPacestd；classAbStractFileprotected：stringname；//文件或目录名称public：voidprintName()cout＜＜name；//打印文件或目录名称virtualcoidaddChild(AbstractFile*file)=0；//给一个目录增加子目录或文件virtualvoidremoveChild(AbstractFile*file)=0；//删除一个目录的子目录或文件virtuallist＜AbstractFile*＞*getChiidren()=0；//获得一个目录的子目录或文件；classFile：publicAbstractFilepublic：File(stringname)((1)=name；voidaddChild(AbstractFile*file)return；voidremoveChild(AbstractFile*file)return；(2)getChiidren()return(3)；；classFolder：publicAbstractFileprivate：list＜AbstractFile*＞childList；//存储子目录或文件public：Folder(stringname)(4)=name；voidaddChiid(AbstractFile*file)chiidList.push_back(file)；voidremoveChiId(AbstractFile*file)chiidList.remove(file)；list＜AbstractFile*＞*getchildren()return(5)；；voidmsin()//构造一个树形的文件/目录结构AbstractFile*rootFolder=newFolder("C://")；AbstractFile*compositeFolder=newFolder("composite")；AbstractFile*windowsFolder=newFolder("windows")；AbstractFile*file=newFile("TestComposite.java")；rootFolder-＞addChild(compositeFolder)；rootFolder-＞addChiid(windowsFolder)；compositeFolder-＞addChiid(file)；

填空题阅读以下函数说明、图和C代码，将应填入(n)处的字句写在对应栏内。[说明]散列文件的存储单位称为桶(Bucket)。假如一个桶能存放m个记录，当桶中已有m个同义词(散列函数值相同)的记录时，存放第m+1个同义词会发生“溢出”。此时需要将第m+1个同义词存放到另一个称为“溢出桶”的桶中。相对地，称存放前m个同义词的桶为“基桶”。溢出桶和基桶大小相同，用指针链接。查找指定元素记录时，首先在基桶中查找。若找到，则成功返回；否则沿指针到溢出桶中进行查找。例如：设散列函数为Hash(Key)=Keymod7，记录的关键字序列为15，14，21，87，96，293，35，24，149，19，63，16，103，77，5，153，145，356，51，68，705，453，建立的散列文件内容如图21-3所示。为简化起见，散列文件的存储单位以内存单元表示。函数InsertToHashTable(intNewElemKey)的功能是：若新元素NewElemKey正确插入散列文件中，则返回值1；否则返回值0。采用的散列函数为Hash(NewElemKey)=NewElemKey%P，其中P为设定的基桶数目。函数中使用的预定义符号如下：#defineNULLKey-1/*散列桶的空闲单元标识*/#defineP7/*散列文件中基桶的数目*/#defineITEMS3/*基桶和溢出桶的容量*/typedefstructBucketNode/*基桶和溢出桶的类型定义*/intKeyData[ITEMS]；structBucketNode*Link；BUCKET；BUCKETBucket[P]；/*基桶空间定义*/[本题函数]intInsertToHashTable(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*/if((4))t=t-＞Link；elsebreak；/*while*//*if*/if((5))/*申请新溢出桶并将元素存入*/s=(BUCKET*)mallOC(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*/

填空题阅读下列说明，回答问题1和问题2，将解答填入对应栏内。[说明]0-1背包问题可以描述为：有n个物品，i=1，2，…，n，第i个物品价值为vi，重量为wi(vi和wi为非负数)，背包容量为W(W为非负数)，选择其中一些物品装入背包，使装入背包物品的总价值最大，即，且总重量不超过背包容量，即，其中，xi∈0，1，xi=0表示第i个物品不放入背包，xi=1表示第i个物品放入背包。[问题1]用回溯法求解此0-1背包问题，请填充伪代码中的空缺(1)～(4)。回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点已经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND(v，w，k，w)函数，其中v、w、k和W分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该结点无须再扩展。下面给出0-1背包问题的回溯算法伪代码。函数参数说明如下：W：背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。变量说明如下：cw：当前的背包重量；cp：当前获得的价值；k：当前考虑的物品编号；Y：当前已获得的部分解。BKNAP(W，n，w，v，fw，fp，X)1cw←cp←02(1)3fp←-14Whiletrue5whilek≤nandcw+w[k]≤Wdo6(2)7cp←cp+v[k]8Y[k]←19k←k+110ifk＞nthen11iffp＜cpthen12fp←cp13fw←cw14k←n15X←Y16elseY(k)←017whileBOUND(cp，cw，k，W)≤fpdo18whilek≠0andY(k)≠1do19(3)20ifk=0thenreturn21Y[k]←022cw←cw←w[k]23cp←cp←v[k]24(4)[问题2]考虑表21-3所示的实例，假设有3个物品，背包容量为22。图21-12是根据上述算法构造的搜索树，其中结点的编号表示搜索树生成的顺序，边上的数字I/O分别表示选择/不选择对应物品。除了根结点之外，每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解，应该选择物品(5)，获得的价值为(6)。表21-30-1背包问题实例物品1物品2物品3重量151010价值301817单位价值21.81.7对于表21-3所示的实例，若采用穷举法搜索整个解空间，则搜索树的结点数为(7)；而采用上述的回溯法，搜索树的结点数为(8)。

填空题阅读以下说明和Java代码，将应填入 (n) 处的字句写在对应栏内。 [说明] 在一公文处理系统中，开发者定义了一个公文类OfficeDoc，其中定义了公文具有的属性和处理公文的相应方法。当公文类的内容或状态发生变化时，关联此OfficeDoc类对象的相应的DocExplorer对象都要更新其自身的状态。一个OfficeDoc对象能够关联一组DocExplorer对象。当OfficeDoc对象的内容或状态发生变化时，所有与之相关联的DocExplorer对象都将得到通知，这种应用被称为观察者模式。以下代码写在一个Java源文件中，能够正确编译通过。 [Java代码] //Subject.java文件 public interface Subject public void attach(Observer DocExplorer)； public void detach(Observer DocExplorer)； void notifyObservers()； //Observer.Java文件 public interface Obsever( void update( (1) )； //OfficeDoc.Java文件 import Java.util.*； public class OfficeDoc implements Subject//OfficeDoc类实现Subject接口 private Vector ObserverVector=new Java.util.Vector()； //存储与OfficeDoc相关联的DocExplorer对象 public void attach(Obsever observer) //将某DocExplorer对象与OfficeDoc相关联 ObserverVector.addElement(observer)； public void detach(Observer observer) //解除某DocExplorer对象与OfficeDoc的关联关系 ObsprverVector.removeElement(observer)； public void notifyobserVers() //当OfficeDoc对象状态已发生变化时，通知所有的DocExplorer对象 Enumeration enumeration= (2) ； while(enumeration.hasMoreElements()) ((Observer)enumeration.nextElement()). (3) ； public Enumeration Observers() return ObserverVector.elements()； //其他公文类的属性和方法省略 //DocExplorer.java文件 public class DocExplorer implements (4) public void update( (5) ) //更新DocExplorer自身的状态，代码省略

填空题阅读下列说明和C代码，将应填入(n)处的字句写在对应栏内。[说明]栈(Stack)结构是计算机语言实现中的一种重要数据结构。对于任意栈，进行插入和删除操作的一端称为栈顶(StackTop)，而另一端称为栈底(StackBottom)。栈的基本操作包括：创建栈(NewStack)、判断栈是否为空(IsEmpty)、判断栈是否已满(IsFull)、获取栈顶数据(Top)、压栈/入栈(Push)、弹栈/出栈(Pop)。当设计栈的存储结构时，可以采取多种方式。其中，采用链式存储结构实现的栈中各数据项不必连续存储(如图21-9所示)。以下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)

填空题阅读下列说明和Java代码，将应填入(n)处的字句写在对应栏内。[说明]已知某企业的采购审批是分级进行的，即根据采购金额的不同由不同层次的主管人员来审批，主任可以审批5万元以下(不包括5万元)的采购单，副董事长可以审批5万元至10万元(不包括10万元)的采购单，董事长可以审批10万元至50万元(不包括50万元)的采购单，50万元及以上的采购单就需要开会讨论决定。采用责任链设计模式(ChainofResponsibility)对上述过程进行设计后得到的类图如图18-10所示。[Java代码]classPurchaseRequestpublicdoubleAmount；//采购的金额publicintNumber；//采购单编号publicStringPurpose；//采购目的；classApprover//审批者类publicApprover()successor=null；publicvoidProcessRequest(PurchaseRequestaRequest)if(successor!=null)(successor.(1)；publicvoidSetSuccessor(ApproveraSuccesssor)successor=aSuccesssor；private(2)successor；；ClassCongressextendsApproverpublicvoidProcessRequest(PurchaseRequestaRequest)if(aRequest.Amount＞=500000)/*决定是否审批的代码省略*/else(3).ProcessRequest(aRequest)；；classDirectorextendsApproverpublicvoidProcessRequest(PurchaseRequestaRequest)/*此处代码省略*/；classPresidentextendsApproverpublicvoidProcessRequest(purchaseRequestaRequest)/*此处代码省略*/；classVicePresidentextendsApproverpublicvoidProcessRequest(purchaseRequestaRequest)/*此处代码省略*/；publicclassrspublicstaticvoidmain(String[]args)throwsIOExceptionCongressMeeting=newCongress()；VicePresidentSam=newVicePresident()；DirectorLarry=newDirector()；PresidentTammy=newPresident()；//构造责任链Meeting.SetSuccessor(null)；Sam.SetSuccessor((4))；Tammy.SetSuccessor((5))；Larry.SetSuccessor((6))；//构造采购审批请求PurchaseRequestaRequest=newPurchaseRequest()；BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in))；aRequest.Amount=Double.parseDouble(br.readLine())；(7).ProcessRequest(aRequest)；//开始审批return；

填空题在VB6.0中，用于设置ADO结果集的内容，这个内容可以来自一张表，也可以来自一个查询语句，还可以来自一个存储过程的执行结果的属性是______。

填空题阅读下列说明和C函数代码，将应填入(n)处的字句写在对应栏内。[说明]对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二又树的每个结点，且每个结点仅访问一次的过程。函数InOrder()借助栈实现二叉树的非递归中序遍历运算。设二叉树采用二叉链表存储，结点类型定义如下：typedefstructBtNodeElemTypedata；/*结点的数据域，ElemType的具体定义省略*/structBtNode*lchiid，*rchiid；/*结点的左、右孩子指针域*/BtNode，*BTree；在函数InOrderO中，用栈暂存二叉树中各个结点的指针，并将栈表示为不含头结点的单向链表(简称链栈)，其结点类型定义如下：typedefstructStNode/*链栈的结点类型*/BTreeelem；/*栈中的元素是指向二叉链表结点的指针*/StructStNode*link；StNode；假设从栈顶到栈底的元素为en，en-1，…，e1，则不含头结点的链栈示意图如图21-11所示。[C函数]intInOrder(BTreeroot)/*实现二叉树的非递归中序遍历*/BTreeptr；/*ptr用于指向二叉树中的结点*/StNode*q；/*q暂存链栈中新创建或待删除的结点指针*/StNode*stacktop=NULL；/*初始化空栈的栈顶指针stacktop*/ptr=root；/*ptr指向二叉树的根结点*/while((1)||stacktop!=NULL)while(ptr!=NULL)q=(StNode*)malloc(Sizeof(StNode))；if(a==NULL)return-1；q-＞elem=ptr；(2)；stacktop=q；/*stacktop指向新的栈顶*/ptr=(3)；/*进入左子树*/q=stacktop；(4)；/*栈顶元素出栈*/visit(q)；/*visit是访问结点的函数，其具体定义省略*/ptr=(5)；/*进入右子树*/free(q)；/*释放原栈顶元素的结点空间*/return0；/*Inorder*/

填空题阅读下列说明和Java代码，将应填入(n)处的字句写在对应栏内。[说明]某饭店在不同的时段提供多种不同的餐饮，其菜单的结构图如图18-29所示。现在采用组合(Composition)模式来构造该饭店的菜单，使得饭店可以方便地在其中增加新的餐饮形式，得到如图18-30所示的类图。其中MenuComponent为抽象类，定义了添加(add)新菜单和打印饭店所有菜单信息(print)的方法接口。类Menu表示饭店提供的每种餐饮形式的菜单，如煎饼屋菜单、咖啡屋菜单等。每种菜单中都可以添加子菜单，例如图18-29中的甜点菜单。类MenuLtem表示菜单中的菜式。[Java代码]importjava.util.*；(1)MenucomponentprotectedStringname；(2)；//添加新菜单publicabstractvoidprint0；∥打印菜单信息publicStringgetName0returnname，classMenultemextendsMenuComponentprivatedoubleprice；publicMenultem(Stringname，doubleprice)this.name=name；this.price=price；publicdoublegetPrice0returnprice；publicvoidadd(MenucomponentmenuComponent)return；∥添加新菜单publicvoidprint0System.out.print(""+getName0)；System.out.println("，"+getPrice0)；classMenuextendsMenuComponent'privateList＜MenuComponent＞menuComponents=newArrayList＜MenuComponent＞0；publicMenu(Stringname)this.name=name；publicvoidadd(MenucomponentmenuComponent)//添加新菜单menucomponents.(3)；publicvoidprint0System.out.print("/n"+getName0)；System.out.printin("，"+"……………")；Iteratoriterator-menuComponents.iteratoro；while(iterator.hasNext0)MenuComponentmenuComponent=(MenuComponent)iterator.next0；(4)；classMenuTestDrivepublicstaticvoidmain(Stringargs[])MenuComponentaIIMenus=newMenu("ALLMENUS")；MenuC0mponentdinerMenu-newMenu("DINERMENU")；……∥创建更多的Menu对象，此处代码省略allMenus.add(dinerMenu)；//将dinerHenu添加到餐厅菜单中……∥为餐厅增加更多的菜单，此处代码省略(5)；∥打印饭店所有菜单的信息

填空题阅读以下说明和C++代码，将应填入(n)处的字句写在对应栏内。[说明]某绘图系统存在Point、Line、Square三种图元，它们具有Shape接口，图元的类图关系如图18-1所示。现要将Circle图元加入此绘图系统以实现功能扩充。已知某第三方库已经提供了XCircle类，且完全满足系统新增的Circle图元所需的功能，但XCircle不是由Shape派生而来的，它提供的接口不能被系统直接使用。代码18.1既使用了XCircle又遵循了Shape规定的接口，既避免了从头开发一个新的Circle类，又可以不修改绘图系统中已经定义的接口。代码18.2根据用户指定的参数生成特定的图元实例，并对之进行显示操作。绘图系统定义的接口与XCircle提供的显示接口及其功能如表18-1所示。表18-1显示接口及其功能ShapeXCircle功能display()DisplayIt()显示图元[代码18.1]classCircle：public(1)private：(2)m_circle；public：voiddisplay()m_circle.(3)；；[代码18.2]classFactorypublic：(4)getShapeInstance(inttype)//生成特定类实例switch(type)case0：returnnewpoint；case1：returnnewRectangle；case2：returnnewline；case3：returnnewCircle；default：returnNULL；；voidmain(intargc，char*argv[])if(argc!=2)cout＜＜"errorparameters!"＜＜end1；return；inttype=atoi(argv[1])；Factoryfactory；Shape*s；S=factory.(5)；if(s=NULL)cout＜＜"Errorgettheinstance!"＜＜end1；return；C-＞display()；(6)；return；

填空题当数据库出现故障时要对数据库进行恢复，恢复的原理是______，常用的技术是数据转储和______。

填空题阅读下列说明，回答问题1至问题3，将解答填入对应栏内。 [说明] 希赛公司供应各种标准的营养套餐。假设菜单上共有n项食物m1，m2，…，mn，每项食物mi的营养价值为vi，价格为pi，其中i=1，2，…，n，套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过M的营养价值最大的套餐。 [问题1] 下面是用动态规划策略求解该问题的伪代码，请填充其中的空缺(1)、(2)和(3)。 伪代码中的主要变量说明如下： n：总的食物项数； v：营养价值数组，下标从1到n，对应第1项到第n项食物的营养价值； p：价格数组，下标从1到n，对应第1项到第n项食物的价格； M：总价格标准，即套餐的价格不超过M； x：解向量(数组)，下标从1到n，其元素值为0或1，其中元素值为0表示对应的食物不出现在套餐中，元素值为1表示对应的食物出现在套餐中； nv：n+1行M+1列的二维数组，其中行和列的下标均从0开始，nv[i][j]表示由前i项食物组合且价格不超过j的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为nv[n][M]。 伪代码如下： MaxNutrientValue(n，v，p，M，x) 1 for i=0 to n 2 nv[i][0]=0 3 for j=1 to M 4 nv[0][j]=0 5 for i=1 to n 6 for j=1 to M 7 if j＜p[i] //若食物mi不能加入到套餐中 8 nv[i][j]=nv[i-1][j] 9 else if (1) 10 nv[i][j]=nv[i-1][j] 11 else 12 nv[i][j]=nv[i-1][j-p[i]]+v[i] 13 j=M 14 for i=n downto 1 15 if (2) 16 x[i]=0 17 else 18 x[i]=1 19 (3) 20 return x and nv[n][M] [问题2] 现有5项食物，每项食物的营养价值和价格如表21-2所示。 表21-2 食物的营养价值和价格表 编码 营养价值 价格 ml 200 50 m2 180 30 m3 225 45 m4 200 25 m5 50 5 若要求总价格不超过100的营养价值最大的套餐，则套餐应包含的食物有 (4) (用食物项的编码表示)，对应的最大营养价值为 (5) 。 [问题3] 问题1中伪代码的时间复杂度为 (6) (用O符号表示)。

填空题阅读以下说明及Java程序，将应填入(n)处的字句写在对应栏内。[说明]传输门是传输系统中的重要装置。传输门具有Open(打开)、Closed(已关闭)、Opening(正在打开)、StayOpen(保持打开)、Closing(正在关闭)5种状态。触发状态的转换事件有crick、complete和timeout三种。事件与其相应的状态转换如图18-6所示。下面的“Java代码1”与“Java代码2”分别用两种不同的设计思路对传输门进行状态模拟，请填补代码中的空缺。[Java代码1]pubZicclassDoorpublicstaticfinalintCLOSED=1；publicstaticfinalintOPENING=2；publicstaticfinalintOPEN=3；publicstaticfinalintCLOSING=4；publicstaticfinalintSTAYOPEN=5；privateintstare=CLOSED；//定义状态变量，用不同的整数表示不同状态privatevoidsetState(intstate)(this.stale=stare；//设置传输门当前状态publicvoidgetState()//此处代码省略，本方法输出状态字符串//例如，当前状态为CLOSED时，输出字符串为"CLOSED"publicvoidclick()//发生click事件时进行状态转换if((1))setState(OPENING)；elseif((2))setStare(CLOSZNG)；elseif((3))setStare(STAYOPEN)；//发生timeout事件时进行状态转换publicvoidtimeout()(if(state==OPEN)setState(CLOSING)；pubncvoidcomplete()//发生complete事件时进行状态转换if(state==OPENING)setState(OPEN)；elseif(state==CLOSING)setState(CLOSED)；publicStaticvoidmain(String[]args)DooraDoor=newDoor()；aDoor.geLStaLe()；aDoor.click()；aDoor.getState()；aDoor.complete()；aDoor.getState()；aDoor.click()；aDoor.getState()；aDoor.clik()；aDoor.getState()；return；[Java代码2]publicclassDoorpublicfinalDoorStateCLOSED=newDoorClosed(this)；publicfinalDoorStateOPENING=newDooropening(this)；publicfinalDoorStateOPEN=newDoorOpen(this)；publicfinalDoorStateCLOSING=newDoorClosing(this)；publicfinalDoorStateSTAYOPEN=newDoorStayopen(this)；privateDoorStatestate=CLOSED；//设置传输门当前状态publicvoidsetState(DoorStatestate)(this.state=state；publicvoidgetState()//根据当前状态输出对应的状态字符串System.out.printIn(state.getClass().getName())；publicvoidclick()((4)；//发生click事件时进行状态转换publicvoidtimeout()((5)；//发生timeout事件时进行状态转换publicvoidcomplete()((6)；//发生complete事件时进行状态转换publicstaticvoidmain(String[]args)DooraDoor=newDoor()：aDoor.getState()；aDoor.Click()；aDoor.getState()；aDoor.complete()；aDoor.getstate()；aDoor.timeout()；aDoor.getState()；return；publicabstractclassDoorState//定义所有状态类的基类protectedDoordoor：publicDoorState(Doordoor)(this.door=door；publicvoidclick()publiccoidcomplete()publicvoidtimeout()classDoorClosedextendsDoorState//定义一个基本的Closed状态publicDoorClosed(Doordoor)(super(door)；publicvoidclick()(7)；//该类定义的其余代码省略//其余代码省略

填空题阅读下列说明，回答问题1和问题2，将解答填入对应栏内。[说明]现需要在某城市中选择一个社区建一个大型超市，使该城市的其他社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。现设计一个算法来找到该大型超市的最佳位置，即在给定图中选择一个顶点，使该顶点到其他各顶点的最短路径之和最小。首先，算法需要求出每个顶点到其他任一顶点的最短路径，即需要计算任意两个顶点之间的最短路径；然后，对每个顶点计算其他各顶点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。[问题1]本题采用Floyd-Warshall算法求解任意两个顶点之间的最短路径。已知图G的顶点集合为V=1，2，…，n)，W=Wijn*n为权重矩阵。设为从顶点i到顶点j的一条最短路径的权重。当k=0时，不存在中间顶点，因此；当k＞0时，该最短路径上所有的中间顶点均属于集合1，2，…，k。若中间顶点包括顶点k，则；若中间顶点不包括顶点k，则。于是得到如下递归式：因为对于任意路径，所有的中间顶点都在集合1，2，…，n内，因此矩阵给出了任意两个顶点之间的最短路径，即对所有i，j∈V，表示顶点i到顶点j的最短路径。下面是求解该问题的伪代码，请填充其中的空缺(1)～(6)。伪代码中的主要变量说明如下：W：权重矩阵；n：图的顶点个数；SP：最短路径权重之和数组，SP[i]表示顶点i到其他各顶点的最短路径权重之和，i取值为1～n；min_SP：最小的最短路径权重之和；min_v：具有最小的最短路径权重之和的顶点；i：循环控制变量；j：循环控制变量；k：循环控制变量。LOCATE-SHC)PPINGNALL(W，n)1D(0)=W2for(1)3fori=1ton4forj=1ton5if6(2)7else8(3)9fori=1ton10SP[i]=011forj=1ton12(4)13min_SP=SP[1]14(5)15fori=2ton16ifmin_SP＞SP[i]17min_SP=SP[i]18min_v=i19return(6)[问题2]问题1中伪代码的时间复杂度为(7)(用O符号表示)。

填空题有学生选课表SC(Sno，Cno，Grade)，各属性分别为学号、课程号和成绩；完成下列SQL语句：找出每个学生超过他选修课平均成绩的课程号。 SELECT Sno，Cno FROM SC X WHERE______ (SELECT______ FROM SC Y WHERE Y.Sno=X.Sno)

填空题阅读下列说明和Java代码，将应填入(n)处的字句写在对应栏内。[说明]某软件公司现欲开发一款飞机飞行模拟系统，该系统主要模拟不同种类飞机的飞行特征与起飞特征。需要模拟的飞机种类及其特征如表18-7所示。表18-7飞机种类及其特征飞机种类起飞特征飞行特征直升机(Helicopter)垂直起飞(VerticalTakeOff)亚音速飞行(SubSonicFly)客机(AirPlane)长距离起飞(LongDistanceTakeOff)亚音速飞行(SubSonicFly)歼击机(Fighter)长距离起飞(LongDistanceTakeOff)超音速飞行(SuperSonicFly)鹞式战斗机(Harrier)垂直起飞(VerticalTakeOff)超音速飞行(SuperSonicFly)为支持将来模拟更多种类的飞机，采用策略设计模式(Strategy)设计的类图如图18-22所示。在图18-22中，AirCraft为抽象类，描述了抽象的飞机，而类Helicopter、AirPlane、Fighter和Harrier分别描述具体的飞机种类，方法fly()和takeOff()分别表示不同飞机都具有飞行特征和起飞特征；类FlyBehavior与TakeOffBehavior为抽象类，分别用于表示抽象的飞行行为与起飞行为；类SubSonicFly与SuperSonicFly分别描述亚音速飞行和超音速飞行的行为；类VerticalTakeOff与LongDistanceTakeOff分别描述垂直起飞与长距离起飞的行为。[Java代码]interfaceFlyBehaviorpublicvoidfly()；；classSubSonicFlyimplementsFlyBehaviorpublicvoidfly()System.out.println("亚音速飞行!")；；classSuperSonicFlyimplementsFlyBehaviorpublicvoidfly()System.out.println("超音速飞行!")；；interfaceTakeOffBehaviorpublicvoidtakeOff()；；classVerticalTakeoffimplementsTakeOffBehaviorpublicvoidtakeOff()System.out.println("垂直起飞!")；；classLongDistanceTakeOffimplementsTakeoffBehaviorpublicvoidtakeOff()System.out.println("长距离起飞!")；；abstractclassAirCraftprotected(1)；protected(2)；publiCvoidfly()(3)；publicvoidtakeOff()(4)；；；classHelicopter(5)AirCraftpubliCHelicopter()flyBehavior=new(6)；takeOffBehavior=new(7)；；//其他代码省略

填空题利用散列函数实现文件记录域取值到记录物理地址间的直接映射关系的机制是______。

填空题阅读以下说明、图和C代码，将应填入(n)处的字句写在对应栏内。[说明]一般的树结构常采用孩子一兄弟表示法表示，即用二叉链表作为树的存储结构，链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如，如图21-6(a)所示的树的孩子一兄弟表示如图21-6(b)所示。函数LevelTraverse0的功能是：对给定树进行层序遍历。例如，对如图21-6(a)所示的树进行层序遍历时，结点的访问次序为：DBAEFPC。对树进行层序遍历时使用了队列结构，实现队列基本操作的函数原型如表21-1所示。表21-1实现队列基本操作的函数原型表函数原型说明VoidInitQueue(Queue*Q)初始化队列BoolIsEmpty(QueueQ)判断队列是否为空，若是则返回TRUE；否则返回FALSEVoidEnQueue(Queue*Q，TreeNodep)元素入队列VoidDeQueue(Queue*Q，TreeNode*p)元素出队列Bool、Status类型定义如下：typedefenum(FALSE=0，TRUE=1)Bool；typedefenum(OVERFLOW=-2，UNDERFLOW=-1，ERROR=0，OK=1)Status；树的二叉链表结点定义如下：typedefstructNodechardata；structNode*fimstchild，*nextbrother；Node，*TreeNode；[本题函数]StatusLeveiTraverse(TreeNoderoot)/*层序遍历树，树采用孩子一兄弟表示法，root是树根结点的指针*/QueuetemQ；TreeNodeptr，brotherptr；if(!root)returnERROR；InitQueue(＆tempQ)；(1)；brotherptr=root-＞nextbrother；while(brotherptr)EnQueue(＆tempQ，brotherptr)；(2)；/-end-while*/while((3))(4)；printf("%c/t"，ptr-＞data)；if((5))continue；(6)；brotherptr=ptr-＞firstchild-＞nextbrother；while(brotherptr)EnQueue(＆tempQ，brotherptr)；(7)；/*end-while*//*end-while*/returnOK；/*LevelTraverse*/

填空题阅读下列说明和C++代码，将应填入(n)处的字句写在对应栏内。[说明]已知某企业的采购审批是分级进行的，即根据采购金额的不同由不同层次的主管人员来审批，主任可以审批5万元以下(不包括5万元)的采购单，副董事长可以审批5万元至10万元(不包括10万元)的采购单，董事长可以审批10万元至50万元(不包括50万元)的采购单，50万元及以上的采购单就需要开会讨论决定。采用责任链设计模式(ChainofResponsibility)对上述过程进行设计后得到的类图如图18-9所示。[C++代码]#include＜string＞#include＜iostream＞usingnamespacestd；classPurchaseRequestpublic：doubleAmount；//采购的金额intNumber；//采购单编号stringPurpose；//采购目的；classApprover//审批者类public：Approver()(successor=NULL；virtualvoidProcessRequest(PurchaseRequestaRequest)if(successor!=NULL)(successor-＞(1)；voidSetSuccessor(Approver*aSucceSSsor)successor=aSuccesssor；private：(2)successor；；classCongress：publicApproverpublic：voidProcessRequest(PurchaseRequeStaRequest)if(aRequest.Amount＞=500000)/*决定是否审批的代码省略*/else(3)ProceSsRequest(aRequest)；；classDirector：publicApproverpubllc：voidProcessRequest(PurchaseRequestaRequest)/*此处代码省略*/；classPresident：publicApproverpublic：voidProcessRequest(PurchaseRequestaRequest)/*此处代码省略*/；classVicePresident：publicApproverpublic：voidProcessRequest(PurchaseRequestaRequest)/*此处代码省略*/；voidmsin()CongressMeeting；VicePresidentSam；DirectorLarry；PresidentTammy；//构造责任链Meeting.SetSuccessor(NULL)；Sam.SetSuccessor((4))；Tammy.SetSuccessor((5))；Larry.SetSuccessot((6))；PurchaseRequestaRequest；//构造采购审批请求cin＞＞aRequest.Amount；//输入采购请求的金额(7).ProcessRequest(aRequest)；//开始审批return；

填空题阅读以下说明和C程序，将应填入 (n) 处的字句写在对应栏内。 [说明] 假设需要将N个任务分配给N个工人同时去完成，每个人都能承担这N个任务，但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案，在该方案中，为每个人分配1个不同的任务。 程序中，N个任务从0开始依次编号，N个工人也从0开始依次编号，主要的变量说明如下： c[i][i]：将任务i分配给工人j的费用。 task[i]：值为0表示任务i未分配；值为j表示任务i分配给工人j。 worker[k]：值为0表示工人k未分配任务；值为1表示工人k已分配任务。 mincost：最小总费用。 [程序] #include＜stdio.h＞ #define N 8 /*N表示任务数和工人数*/ int c[N][N]； unsigned int mincost=65535； /*设置min的初始值，大于可能的总费用*/ int task[N]，temp[N]，worker[N]； void plan(int k，unsigned int cost) int i； if( (1) ＆＆cost＜mincost) mincost=cost； for(i=0；i＜N；i++)temp[i]=task[i]； eise for(i=0；i＜N；i++) /*分配任务k*/ if(worker[i]==0 ＆＆ (2) ) worker[i]=1；task[k]= (3) ； plan( (4) ，cost+c[k][i])； (5) ；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"，＆c[i][j])； 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*/