2005年11月5日软件设计师下午题目

试题四：
散列文件的存储单位称为桶（BUCKET）。假如一个桶能存放m个记录，当桶中已经有m个同义词（散列函数值相同）的记录时，存放第m+1个同义词会发生“益出”。此时需要将第m+1个同义词存放到另一个“益出桶”的桶中。相对的，称存放 前m个同义词的桶称为基桶。益处桶和基桶大小相同，用指针链接。查找指定元素记录时，首先在基桶中查找。若找到，则成功返回，否则沿指针到益处桶中查找。
为了简化起见，散列文件的存储单位以内存单元表示。
函数InsertToHashTable(int NewElemKey)的功能是：若新的元素NewElemKey正确插入散列文件中。则返回1，否则 0。
采用的散列函数为Hash(NewElemKey)= NewElemKey% P,其中P为设定的基桶数目。
函数中使用的预定仪符号为：
#define NULLKEY –1 /*散列桶的空闲单元标示*/
#define P 7 /*散列文件基桶的数目*/
#define ITEMS 3 /*基桶和益处桶的容量*/
typedef struct BucketNode{ /*基桶和益处桶的类型定义*/
int KeyData[ITEMS];
struct  BucketNode *link;
}BUCKET;
BUCKET Bucket[P]; /*基桶的空间定义*/
Int  InsertToHashTable(int NewElemKey)
{/*将元素NewElemKey 插入散列桶中插入成功则返回0，否则返回-1 。设插入第一个元素前基桶的所有 KeyData[],link域已分别初始化为NULLKEY,NULL*/int Index; /*基桶编号*/
int i,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)___) return 0; /*若基桶已满，则在益出桶查找空闲单元，若找到则申请新的益出桶*/_________(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;
else break;
}/*while*/
}
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)____;
}
return 0;
}试题五：
在一公文处理系统中，开发者定义了一个公文类OfficeDoc,其中第一了公文具有的属性和处理公文的方法。当公文的内容或状态发生变化时，关注此OfficeDoc类的对象的响应的DocExplorer对象都要更新其自身的状态。一个OfficeDoc对象能够关联一组DocExplorer对象。当OfficeDoc 对象的内容或状态发生变化时，所有与之相关的DocExplorer对象都将得到通知。这种应用被称为观察者模式。
#Include<iostream>
const OBS_MAXNUM=20; //最多与OfficeDoc对象想关联的DocExplorer
//对象的个数
___(1)____;
class DocExplorer  //关注OfficeDoc公文对象的类
{
public:
DocExplorer (___(2)___  *doc);  //构造函数
___(3)___ void update(OfficeDoc *doc) = 0;
//更新自身状态的函数 其他相关属性和方法省略
};class OfficeDoc
{
private:
DocExplorer *myObs[OBS_ MAXNUM];
//关注此公文类的DocExplorer 类对象指针数组
Int index;  //与OfficeDoc对象关联的DocExplorer对象个数
Public:
OfficeDoc()
{
index = 0;
}
void attach(DocExplorer *o) //将一DocExplorer与
//OfficeDoc对象相关联
{
if (index >= OBS_MAXNUM || o== NULL)  return;
for (int loop=0; loop < index; loop++)
if (myObs[loop] == 0 )     return;
myObs[index] = 0 ;
index++;
}
void detach(DocExplorer *o) //解除DocExplorer对象与
//OfficeDoc对象的关联
{
if(o==NULL)   return;
for (int loop = 0 ;loop < index; loop ++) 
{
if (myObs[loop] == 0 
{
if(loop <= index-2) myObs[loop] = myObs[index-1];
myObs[index-1]=NULL;
index--;
break;
}
}
}
private:
void notifyObs()
{
for(int loop = 0;loop < index; loop++)
{
myObs[loop]->______(4)_____;
}
}
}
DocExplorer::DocExplorer(OfficeDoc *doc)       // DocExplorer 类对象的构造函数
{
doc->____(5)_____;   // 此DocExplorer对象与doc对象 相关联
}我的答案:四
1 Index=NewElemKey % P       
2 i< ITEMS                     
3 front = Bucket[Index]      
4 k == ITEMS  
5 t == NULL    
6 front->Link = s  五
1 class officeDoc
2 officeDoc
3 Virtual               汗~~写成了virture
4 update(this)
5 attact(this)欢迎大家讨论~!