首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明、图和C代码,将应填入(n)处的字句。 [说明] 散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录,当桶中已有 m个同义词(散列函数值相同)的记录时,存放第m+1个同义词会发生“溢出”。此时需要将第m+1个同义词存放
阅读下列函数说明、图和C代码,将应填入(n)处的字句。 [说明] 散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录,当桶中已有 m个同义词(散列函数值相同)的记录时,存放第m+1个同义词会发生“溢出”。此时需要将第m+1个同义词存放
admin
2008-01-15
44
问题
阅读下列函数说明、图和C代码,将应填入(n)处的字句。
[说明]
散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录,当桶中已有 m个同义词(散列函数值相同)的记录时,存放第m+1个同义词会发生“溢出”。此时需要将第m+1个同义词存放到另一个称为“溢出桶”的桶中。相对地,称存放前m个同义词的桶为“基桶”。溢出桶和基桶大小相同,用指针链接。查找指定元素记录时,首先在基桶中查找。若找到,则成功返回,否则沿指针到溢出桶中进行查找。
例如:设散列函数为Hash(Key)=Key mod 7,记录的关键字序列为15,14,21,87,97,293,35,24,149,19,63,16,103,77,5,153,145,356,51,68,705,453,建立的散列文件内容如图4-1所示。
[图4-1]
为简化起见,散列文件的存储单位以内存单元表示。
函数InsertToHashTable(int NewElemKey)的功能是:将元素NewEIemKey插入散列桶中,若插入成功则返回0,否则返回-1。
采用的散列函数为Hash(NewElemKey)=NewElemKey % P,其中P为设定的基桶数目。
函数中使用的预定义符号如下:
#define NULLKEY -1 /*散列桶的空闲单元标识*/
#define P 7 /*散列文件中基桶的数目*/
#define ITEMS 3 /*基桶和溢出桶的容量*/
typedef struct BucketNode{ /*基桶和溢出桶的类型定义*/
int KcyData[ITEMS];
struct BucketNode *Link;
}BUCKET;
BUCKET Bucket[P]; /*基桶空间定义*/
[函数]
int lnsertToHashTable(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*)malloe(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*/
return 0;
}/*InsertToHashTable*/
选项
答案
(1) Index=NewElemKey % P (2) i<ITEMS (3) front=&Bucket[Index] (4) k==ITEMS (5) t==NULL,或!t (6) front->Link=s
解析
本题考查元素的散列存储。
元素作散列存储时,首先用设定的散列函数计算元素的存储位置。在本题中,将元素存储在预先设定的基桶或根据需要申请的溢出桶中,只要基桶中有空闲单元,就将新元素NewElemKey插入在基桶中,若基桶中无空闲单元,则看是否存在溢出桶,若存在,则在溢出桶中查找空闲单元,若不存在溢出桶或溢出桶中无空闲单元,则申请一个溢出桶并存入新元素。
在基桶查找空闲单元时使用的桶号为Index,可知空(1)处应填入“Index= NewElemKey % P”。显然,一旦在基桶中找到空闲单元,即“Bucket[Index].KeyData
== NULLKEY”(0≤i<ITEMS),则可将元素NewElemKey放入Bucket[Index].KeyData
,至此元素已经插入散列桶中,函数可返回,因此空(2)处应填入“i<ITEMS”;反之,若在基桶中没有找到空闲单元,则需查找溢出桶。“t=Bucket[Index].Link”,指针t首先指向桶号Index的第一个溢出桶。下面的代码即为在溢出桶中查找空闲单元。
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*/
由于每个溢出桶都可以存储ITEMS个元素,所以在溢出桶中查找空闲单元与在基桶中的查找过程相同,代码如下。
for(k=0;k<ITEMS;k++)
if(t->KcyData[k]==NULLKEY){/*在溢出桶链表中找到空闲单元*/
t->KeyData[k]=NewElemKey; break;
}/*if*/
若在指针t指向的溢出桶中找到空闲单元则插入元素,否则,由“t=t->Link”得到下一个溢出桶的指针,因此“k<ITEMS”可作为是否在当前溢出桶中找到空闲单元的判定条件。
显然,在桶号Index的基桶和其所有溢出桶都已满的情况下,t的值为空指针。此时才需要申请新的溢出桶并建立链接关系,因此在上面查找溢出桶中空闲单元时,进行指针t的后移“t=t->Link”前应先用front记录t的值,以便于后面建立链接关系。所以空(3)处应给front置初值,即“front=&Bucket[Index]”,空(4)填入“k==ITEMS”,空(5)填入“t=NULL”。空(6)处建立新申请溢出桶的链接关系“front->Link=s”。
转载请注明原文地址:https://kaotiyun.com/show/mfDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
为了解决进程间的同步和互斥问题,通常采用一种称为(21)机制的方法。若系统中有5个进程共享若干个资源R,每个进程都需要4个资源R,那么使系统不发生死锁的资源R的最少数目是(22)。
高速缓存cache与主存间采用全相联地址映像方式,高速缓存的容量为4MB,分为4块,每块1MB,主存容量为256MB。若主存读写时间为30ns,高速缓存的读写时间为3ns,平均读写时间为3.27ns,则该高速缓存的命中率为(3)%。若地址变换表如下所示,
不属于界面元素测试的是(50)。
(51)不属于测试人员编写的文档。
对软件可靠性的理解,正确的是(45)。①软件可靠性是指在指定条件下使用时,软件产品维持规定的性能级别的能力②软件可靠性的种种局限是由于随着时间的推移,软件需求和使用方式发生了变化③软件可靠性包括成熟性、有效性、容错性、易恢复性
一个软件系统的生存周期包含可行性分析和项目开发计划、需求分析、设计(概要设计和详细设计)、编码、测试和维护等活动,其中(18)是软件工程的技术核心,其任务是确定如何实现软件系统。
为验证某呼叫中心是否能够承受大量呼叫信息同时呼入并得到正确处理,测试工程师一般采用______测试工具。A.负载压力B.代码C.网络仿真D.故障诊断
对于逻辑表达式((a&b)||c,需要______个测试用例才能完成条件组合覆盖。
在ISO/IEC软件质量模型中,功能性是与一组功能及其指定的性质的存在有关的一组属性,其子特性不包括__________。
结构化开发方法中,(35)主要包含对数据结构和算法的设计。对算法设计时,其主要依据来自(36)。描述算法时,(37)不是理想的表达方式。(35)
随机试题
下列中药用水处理时,应尽量少泡多润的有
王先生被诊断为肺癌晚期,其家属的首要需求是
患者,男性,50岁,脊髓型颈椎病,在全麻下行颈椎前路手术治疗,术后12h出现胸闷、憋气、颈部肿胀,伤口引流管未见引流液引出。患者出现憋气的原因错误的是
类风湿关节炎的关节症状,具有特征性的是:
一侧上肢或下肢的运动不能或运动无力,称为
竞争力对比分析的比较内容包括()。
上市公司甲股份有限公司(简称“甲公司”)主要是从事各种型号钢材的研发、生产和销售,钢材生产所需要的主要原材料均在国内采购,各种型号钢材产品主要销往国内。ABC会计师事务所连续多年负责审计甲公司财务报表,2012年甲公司财务报表审计继续是A注册会计师担任审计
根据下列统计资料回答问题。2016年,某市全年实现工业增加值3884.9亿元,比上年增长5.0%。其中,规模以上工业增加值增长5.1%。在规模以上工业中,国有控股企业增加值增长6.7%;股份合作企业、外商及港澳台企业增加值分别增长9.3%和8.5
Retailshoppingisn’tdeadyet,atleastnotforacompanyworth(atleast)hundredsofbillionsofdollars.Amazonisplanning
midasWWW是基于(58)系统的浏览程序。
最新回复
(
0
)