首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下函数说明、图和C代码,将应填入(n)处的字句写在对应栏内。 【说明】 散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录,当桶中已有m个同义词(散列函数值相同)的记录时,存放第m+1个同义词会发生“溢出”。此时需要将第m+1
阅读以下函数说明、图和C代码,将应填入(n)处的字句写在对应栏内。 【说明】 散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录,当桶中已有m个同义词(散列函数值相同)的记录时,存放第m+1个同义词会发生“溢出”。此时需要将第m+1
admin
2009-05-15
169
问题
阅读以下函数说明、图和C代码,将应填入(n)处的字句写在对应栏内。
【说明】
散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录,当桶中已有m个同义词(散列函数值相同)的记录时,存放第m+1个同义词会发生“溢出”。此时需要将第m+1个同义词存放到另一个称为“溢出桶”的桶中。相对地,称存放前m个同义词的桶为“基桶”。溢出桶和基桶大小相同,用指针链接。查找指定元素记录时,首先在基桶中查找。若找到,则成功返回,否则沿指针到溢出桶中进行查找。
例如:设散列函数为Hash(Key)=Key mod 7,记录的关键字序列为15,14,21,87,96, 293,35,24,149,19,63,16,103,77,5,153,145,356,51,68,705,453,建立的散列文件内容如图5-3所示。
为简化起见,散列文件的存储单位以内存单元表示。
函数InsertToHashTable(int NewElemKey)的功能是;若新元素NewElemKey正确插入散列文件中,则返回值1;否则返回值0。
采用的散列函数为Hash(NewElemKey)=NewElemKey % P,其中P为设定的基桶数目。
函数中使用的预定义符号如下:
#define NULLKEY-1 /*散列桶的空闲单元标识*/
#define P 7 /*散列文件中基桶的数目*/
#define ITEMS 3 /*基桶和溢出桶的容量*/
typedef struet BucketNode{ /*基桶和溢出桶的类型定义*/
int KeyData[ITEMS];
struct BucketNode *Link;
}BUCKET;
BUCKET Bucket[P]; /*基桶空间定义*/
【函数5-3】
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
==NULLKEY){
Bucket[Index].KeyData
=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*/
if((5)){ /* 申请新溢出桶并将元素存入*/
s=(BUCKET *)malloc(sizeof(BUCKET));
if(!s)retum -1;
s->Link=NULL;
for(k=0;k<ITEMS;k++)
s->KeyData[k]=NULLKEY;
s->KeyData[0]=NewElemKey;
(6);
}/*if*/
return 0;
}/*InsertToHashTable*/
选项
答案
(1) Index=Hash(NewElemKey),或Index=NewElemKey%P (2) i<ITEMS (3) front=&Bucket[Index],或front=Bucket+Index (4) k==ITEMS,或k>=ITEMS (5) t==NULL (6) front->Link=s
解析
本题考查链式存储的插入算法。
根据题意,空(1)比较简单,应为计算散列值,并将关键字NewElemKey对应的散列值赋给表示基桶编号的变量Index,故空(1)应填Index=Hash(NewElemKey)。
接下来进行插入操作,分3种情况进行处理:基桶未满、基桶已满但溢出桶未满、基桶和溢出桶(若有)都已满。基桶未满时,直接将关键字插入到基桶中即可;若基桶已满但溢出桶未满,则找到未满的溢出桶,将关键字插入;若基桶和溢出桶(若有)均已满,则新建溢出桶,并将关键字插入到新建的溢出桶中。
空(1)之后的for语句在基桶中查找空闲单元,若找到则进行插入,如条件空(2)成立,返回0,表示插入成功,可见空(2)表示基桶未满,关键字已经成功插入。故空(2)应填i<ITEMS。注意break语句,若基桶只剩最后一个单元,即i=ITEMS-1时才进行插入操作,由于有break语句,跳出for循环后,i值仍为ITEMS-1,而不会被加1。所以填成i<=ITEMS是错误的。
接着处理基桶已满的情况。空(3)应该是某个变量的初始化,不过暂时无法确定。
首先处理有溢出桶的情况。既然基桶已满,就只能在溢出桶中查找空闲单元,若找到则进行插入。注意赋值语句“front=t”。空(4)条件成立时继续查找下一个溢出桶,即表示当前溢出桶中已经没有空闲单元了,因此空(4)应填k==ITEMS。这样结束while循环对应两种情况:已经成功插入(对应t不为NULL,front不确定)和所有溢出桶都没有空闲单元(对应 t为NULL,front指向最后一个溢出桶)。
接着处理基桶和溢出桶(若有)均已满的情况,此时需要新建溢出桶。空(5)即为“基桶和溢出桶(若有)均已满”对应的条件,此处有个特例,基桶已满但没有溢出桶,此时对应 t==NULL。根据上面的分析并结合特例可得空(5)应该为t==NULL。新建溢出桶并将关键字插入后,还需要将溢出桶链接到正确位置。故空(6)应填front->link=s。
注意,对于特例(基桶己满但没有溢出桶,对应t==NULL),front并未赋值,此时front应该指向相应的基桶。由此可得空(3)应填front=&Bucket[Index]。
转载请注明原文地址:https://kaotiyun.com/show/65xZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
在局域网中,常用的介质访问控制方法CSMA/CD、令牌总线和令牌环,IEEE802.4标准采用(16)媒体访问控制方法,IEEE802.5标准采用(17)媒体访问控制方法。其中(18)介质访问控制方法对最短帧长度有要求。假设这种网络的传输速率为10Mbi
在局域网中,常用的介质访问控制方法CSMA/CD、令牌总线和令牌环,IEEE802.4标准采用(16)媒体访问控制方法,IEEE802.5标准采用(17)媒体访问控制方法。其中(18)介质访问控制方法对最短帧长度有要求。假设这种网络的传输速率为10Mbi
某局域网的Internet接入拓扑图如图7-5所示。由于用户在使用telnet登录网络设备或服务器时所使用的用户名和口令在网络中是以明文传输的,很容易被网络上的非法协议分析设备截获。因此需要定义一条规则号为110,禁止所有外网主机和内网主机进行远程登录的访
在X.25网络中,通常用户计算机与网络的(41)相连接。X.25网络的数据链路层使用的标准是(42),它允许在收到应答前连续发送(43)帧数据,为用户提供的最高速率为(44)Kbps。两个X.25网络之间互联时使用(45)协议。
TCP是一个面向连接的协议,它提供连接的功能是(31)的,采用(32)来实现可靠数据流的传送。为了提高效率,又引入了滑动窗口协议,协议规定重传(33)的分组,这种分组的数量最多可以(34),TCP协议采用滑动窗口协议解决了(35)。
IEEE802.5令牌环(TokenRing)网中,时延是由(1)决定。要保证环网的正常运行,环的时延必须有一个最低限度,即(2)。如果达不到这个要求,可以采用的一种办法是通过增加电缆长度,人为地增加时延来解决。设有某一个令牌环网长度为400m
在OSI参考模型中,上层协议实体与下层协议实体之间的逻辑接口叫做服务访问点(SAP)。在因特网中,应用层的服务访问点是(65)。
SNMPc是一个通用的多用户分布式网络管理平台,采用(21)轮询机制,具有高度的可伸缩性。假设有一个局域网,管理站每15分钟轮询被管理设备一次,一次查询访问需要的时间是200ms,则管理站最多可以支持(22)台网络设备。
简要说明VLAN的静态和动态两种实现方式分别是如何实现的?在VLAN中,STP和VTP是什么协议?各有什么作用?
在局域网中可动态或静态划分VLAN,静态划分VLAN是根据()划分。
随机试题
怎样应用坐标平移进行槽类零件的铣削加工操作?
女性,28岁,妊娠36周,既往体健,化验血Hb60g/L,MCV102fl,WBC4.5×109/L,PLT98×109/L最具特征的临床表现是
“白胆汁”是
患者,女,25岁。妊娠39周,于2:30pm正常分娩。6:40pm主诉腹胀、腹痛。视诊:下腹膀胱区隆起。叩诊:耻骨联合上浊音。其存在的健康问题是
若心移热于小肠或热结于本腑,证见心烦,口舌生疮,咽痛,小便短赤或溺血,茎中痛,小腹胀痛,舌质红而苔黄,脉象濡数。腧穴宜取
甲乙丙丁四人共同出资设立了一家普通合伙企业,其合伙协议中有这样两项规定:规定一“处分合伙企业不动产,应当经过半数的合伙人同意”;规定二“合伙人向合伙人以外的人转让其在合伙企业中的财产份额的,其他合伙人无优先购买权”。关于这两项规定的效力判断正确的是?
5268
水电、风电与光伏是当前可再生能源的主要形式。其中水力发电由于发展时间较长,技术相对________,水力发电量占亚洲可再生能源总发电量的50%左右。但由于选址经济性下降和环境社会问题日渐凸显,未来水电发展或将变得________。填入画横线部分最恰当的一项
假定有如下程序代码,程序运行后,把鼠标光标移到窗体内,每单击一次,变换一种鼠标光标的形状,依次显示鼠标光标的15个属性。请在划线处将程序补充完整。PrivateSubForm_Click()StaticxAsInt
要显示当前过程中的所有变量及对象的取值,可以利用的调试窗口是
最新回复
(
0
)