首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下函数说明、图和C代码,将应填入(n)处的字句写在对应栏内。 【说明】 散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录,当桶中已有m个同义词(散列函数值相同)的记录时,存放第m+1个同义词会发生“溢出”。此时需要将第m+1
阅读以下函数说明、图和C代码,将应填入(n)处的字句写在对应栏内。 【说明】 散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录,当桶中已有m个同义词(散列函数值相同)的记录时,存放第m+1个同义词会发生“溢出”。此时需要将第m+1
admin
2009-05-15
160
问题
阅读以下函数说明、图和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)。
EIARS-232C定义了DTE和DCE之间的接口,其机械特性规定RS-232C的D型连接器有(11)个插脚,其电气特性与CCITT的(12)兼容。DTE和DCE之间的接口信号线按功能一般可分为(13)4类,使用EIARS-232C接口进行数据通信时,至少
某电子商务公司由相对独立的6个子公司组成,在管理上其中3个子公司管理基础完善,基本达到科学管理的要求。企业高层为企业长远发展考虑决定建设一个基于B/S结构的管理信息系统。该系统项目可使用(6)进行开发建设。
内存按字节编址,地址从0B4000H到0DBFFFH。至少需要(1)片存储容量为32K×8bit的存储器芯片构成该内存。
在互连的网络设备中,交换机的工作与网桥相比,区别在于(27),网桥是根据(28)知道是应该转发还是应该过滤数据包。交换机与Hub相比,优点是(29),网桥中为了防止产生循环路径,需要运行(30);算法。具有自学习功能的网桥是(31)。
自标准实施之日起,至标准重申重新确认、修改或废止的时间,称为标准的有效期(标龄),我国的国家标准有效期一般为(48)年,国家标准是由政府或国家级的机构制定或批准的,适用于全国范围的标准,是一个国家标准体系的主体和基础,国内各级标准必须服从且不得与之相抵触。
RS-232-C是目前常见的一种接口标准,它是由(32)提供制定的。该标准在OSI模型中属于(33)层协议标准,通过RS-232-C来连接两个设备最少要连接(34)条线。这个标准的设计数据速率是处理(35)bit/s。(35)bit/s条件下,采用RS-4
In the following essay, each blank has four choices. Choose the best answer and write down on the answer sheet.Microwave communi
Networks can be interconnected by different devices in the physical layer networks can be connected by(1)or hubs. Which just mov
Networks can be interconnected by different devices in the physical layer networks can be connected by(1)or hubs. Which just mov
随机试题
先王之制,大都不过参国之一。参国之一:
石瘿的病因病机是
生产工艺技术的()主要体现在产品质量性能好,工艺水平高,装备自动控制程度和可靠性高。
综观有关茶叶标准中的国家标准、国际(组织)标准、行业标准、企业标准,被检验者、生产商、消费者首先关注的技术指标包括()
某居民企业2008年实际支出的工资、薪金总额为80万元,福利费本期发生10万元,拨缴的工会经费1.60万元,已经取得工会拨缴收据,实际发生职工教育经费1.50万元。税务机关审核确定该企业合理工资支付应当为60万元。该企业填列《企业所得税年度纳税申报表(A类
从工厂的原材料购进入库起直到成品库的成品发送为止的整个过程中的物流活动是()。
教育活动的基本规律包括()
图1-12中缺少了哪些数据流?请指明每条数据流的名称、起点和终点。为建立功能完善的库存管理系统,除了查询、统计、报表输出功能外,还应具有哪些对提高企业效益至关重要的功能?
A、Inafactory.B、Inahospital.C、Inamusem.C他们谈的话题是出土文物,自然是在博物馆。
Thewordhorsepowerwasfirstusedtwohundredyearsago.JamesWatthadmadetheworld’sfirst(11)usedsteamengine.Hehad
最新回复
(
0
)