首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下函数说明、图和C代码,将应填入(n)处的字句写在对应栏内。 【说明】 散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录,当桶中已有m个同义词(散列函数值相同)的记录时,存放第m+1个同义词会发生“溢出”。此时需要将第m+1
阅读以下函数说明、图和C代码,将应填入(n)处的字句写在对应栏内。 【说明】 散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录,当桶中已有m个同义词(散列函数值相同)的记录时,存放第m+1个同义词会发生“溢出”。此时需要将第m+1
admin
2009-05-15
62
问题
阅读以下函数说明、图和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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在ISDN网络中,与ISDN交换机直接相连的是(46)设备,他们通过(47)实现互连。NT1到用户设备之间的连接点是(48)。对于非ISDN设备要通过(49)设备接入ISDN网络,该设备的主要作用是(50)。
在局域网中,常用的介质访问控制方法CSMA/CD、令牌总线和令牌环,IEEE802.4标准采用(16)媒体访问控制方法,IEEE802.5标准采用(17)媒体访问控制方法。其中(18)介质访问控制方法对最短帧长度有要求。假设这种网络的传输速率为10Mbi
在局域网中,常用的介质访问控制方法CSMA/CD、令牌总线和令牌环,IEEE802.4标准采用(16)媒体访问控制方法,IEEE802.5标准采用(17)媒体访问控制方法。其中(18)介质访问控制方法对最短帧长度有要求。假设这种网络的传输速率为10Mbi
EIARS-232C定义了DTE和DCE之间的接口,其机械特性规定RS-232C的D型连接器有(11)个插脚,其电气特性与CCITT的(12)兼容。DTE和DCE之间的接口信号线按功能一般可分为(13)4类,使用EIARS-232C接口进行数据通信时,至少
SDH网络是一个基于(22)技术的数字传输网络。
TCP通过建立连接为用户提供可靠传输,与数据链路层的连接建立不同,TCP要经过(58)才能确定一个连接,这是因为(59)。TCP采用的差错控制也是超时重发技术,超时时间的设置采用—(60)策略,以便适应互联网的特性。超时时间设置根据的是(61)。TCP的拥
一个Lan拓扑可以使用令牌传递或CSMA/CD控制媒体访问,其拓扑属于下列的(69),若仅使用像令牌传递这样的确定性媒体控制方法,其拓扑属于下列的(70)。
ICMP是Internet控制协议报文协议,它允许主机或路由器报告(37)和提供有关异常情况的报告。它是(38)的组成部分,其报文格式包括报文头和数据区两部分,其中报文头部分是由—些刨等三个字段组成,字段长度分别为(40)。ICMP可作为询问报文,用来测试
CPU的工作我们也可以大致分为指令的获取、解码、运算和结果的写入四个步骤,其芯片中使用流水线技术的目的是(17)。
Networks can be interconnected by different devices in the physical layer networks can be connected by(1)or hubs. Which just mov
随机试题
奥利司他的临床应用注意事项有
中医认为流行性腮腺炎的病机主要是风温邪毒壅阻
《企业职工伤亡事故分类标准》(GB6441-1986)将企业工伤事故分为20类,其中不包括()。
冬期开挖路堑表层冻土时,1m以上的冻土层采用下面哪种方法施工合适( )。
某机电工程采用EPC/交钥匙总承包的方式进行公开招标,并在国家发改委依法指定的媒体上发布了招标公告和资格预审公告。公告中明确说明了承包商报名时间及提供的资料;工程的基本情况;投标人需提交标书费用、押金、投标保函的要求;投标人获取和送达标书的方式、地点和起止
2009年全国研究机构R&D经费995.9亿元,是2000年的3.9倍,年平均增长16.2%。按活动类型分,基础研究经费110.6亿元,占11.1%;应用研究经费350.9亿元,占35.2%;试验发展经费534.4亿元,占53.7%。基
选出下列文化常识的有关内容。秀才、举人、贡士、进士依次是封建社会科举考试中______、______、______、______的合格者。
以下关于MIS基本任务的描述中,不正确的是
Themostnoticeabletrendamongtoday’smediacompaniesisverticalintegration—anattempttocontrolseveralrelatedaspectsof
我到那儿就给你打电话。
最新回复
(
0
)