填空题阅读下列说明和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)

单选题采用三级结构/两级映像的数据库体系结构，如果对数据库的一张表创建聚簇索引，改变的是数据库的（ ）

单选题面向对象分析过程中，从给定需求描述中选择（ ）来识别对象

单选题设某二叉树采用二叉链表表示 （即结点的两个指针分别指示左、右孩子）

单选题两个递增序列A和B的长度分别为m和n(mn且m与n接近)，将二者归井为一个长度为m+n的递增序列

单选题相比于 TCP，UDP的优势为（ ）

单选题在程序执行过程中，Cache 与主存的地址映射是由（ ）完成的

单选题设S是一个长度为n的非空字符串，其中的字符各不相同，则其互异的非平凡子串（非空且不同于S本身）个数为（ ）

单选题采用继承机制创建子类时，子类中（ ）

单选题以下关于管道过滤器体系结构的有点的叙述中，不争取的是（ ）

单选题计算机系统的层次结构如下圈所示，基于硬件之上的软件可分为 a、b和c三个层次

单选题某医院预约系统的部分需求为： 患者可以查看医院发布的专家特长介绍及其就诊时间：系统记录患者信息，患者预约特定时间就诊

单选题以下关于海明码的叙述中，正确的是（ ）

单选题某文件系统采用多级索引结构

单选题李某购买了一张有注册商标的应用软件光盘，则李某享有（ ）

单选题内存按字节编址，若用存储容量为32K*8bit的存储器芯片构成地址从AOOOOH到DFFFFH的内存，则至少需要（ ）片芯片