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)
欢迎大家讨论~!
问题点数：20、回复次数：9Top
1 楼alen_ghl（东方求*）回复于 2005-11-07 18:00:17 得分 4
顶BOBO一下Top
2 楼bobob（静思）回复于 2005-11-08 10:34:04 得分 0
怎么这么冷清~~~Top
3 楼shijin1231（(云里雾里....)）回复于 2005-11-08 10:55:53 得分 4
太难了,我这个菜鸟往边站了Top
4 楼ljmanage（过客）回复于 2005-11-08 17:15:00 得分 3
楼主在这里表演啊Top
5 楼kugou123（酷狗)(彪悍的人生，不需要解释 www.xiaozhou.net）回复于 2005-11-09 11:09:05 得分 3
怎么不考那种什么汇编了？？？Top
6 楼twinsen0398（）回复于 2005-11-09 12:17:58 得分 3
看了一下！不难！~！以后有时间去考一下！毕业找工作多个证书！（现在流行）：）Top
7 楼xiao_fang（frank）回复于 2005-11-09 12:42:10 得分 3
仔细看了一下试题五，简单！
楼主的答案可要注意大小写啊：）
前三个都有大小写问题
Top
8 楼bobob（静思）回复于 2005-11-10 13:13:23 得分 0
今年汇编已经没有了
Top
9 楼MaxWind（[USBidiot@smth.edu.cn]）回复于 2005-12-16 15:54:58 得分 0
好铁，必须顶下Top
相关问题
关键词
得分解答快速导航
相关链接
广告也精彩
反馈
