首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下函数说明、图和C程序代码,将C程序段中(1)~(6)空缺处的语句填写完整。 [说明] 散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录,当桶中已有m个同义词(散列函数值相同)的记录时,存放第m+1个同义词会发生“溢出
阅读以下函数说明、图和C程序代码,将C程序段中(1)~(6)空缺处的语句填写完整。 [说明] 散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录,当桶中已有m个同义词(散列函数值相同)的记录时,存放第m+1个同义词会发生“溢出
admin
2013-01-05
24
问题
阅读以下函数说明、图和C程序代码,将C程序段中(1)~(6)空缺处的语句填写完整。
[说明]
散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录,当桶中已有m个同义词(散列函数值相同)的记录时,存放第m+1个同义词会发生“溢出”。此时需要将第m+1个同义词存放到另一个称为“溢出桶”的桶中。相对地,称存放前m个同义词的桶为“基桶”。溢出桶和基桶大小相同,用指针链接。查找指定元素记录时,首先在基桶中查找。若找到,则成功返回,否则沿指针到溢出桶中进行查找。
例如,设散列函数为Hash(Key)=Key mod7,记录的关键字序列为15,14,21,87,96,293,35,24, 149,19,63,16,103,77,5,153,145,356,51,68,705,453,建立的散列文件内容如图2-27所示。
为简化起见,散列文件的存储单位以内存单元表示。
函数InsertToHashTable(int NewElemKey)的功能是:若新元素NewElemKey正确插入散列文件中,则返回值0;否则返回值-1。
采用的散列函数为Hash(NewElemKey)=NewElemKey%P,其中P设定基桶的数目。
函数中使用的预定义符号如下。
选项
答案
这是一道要求读者掌握如何在散列文件中插入一个新的数据元素的编程题。本题的解答思路如下。 在散列文件中插入一个新的数据元素的基本思路是,首先将要插入的元素代入到散列函数中,从而计算出该元素的散列地址。然后按照散列地址,在基桶中查找空闲单元,若找到,则将元素插入,若基桶已满,则在溢出桶中查找空闲单元。若溢出桶中也查找不到,则申请新的溢出桶,然后将元素存入。 在散列文件中查找一个元素的基本思路是,查找指定元素记录时,首先在基桶中查找,若找到,则成功返回,否则沿指针到溢出桶中进行查找。 在本试题中,将元素存储在预先设定的基桶或根据需要申请的溢出桶中,只要基桶中有空闲单元,就将新元素NewElemkey插入在基桶中,若基桶中无空闲单元,则看是否存在溢出桶,若存在,则在溢出桶中查找空闲单元,若不存在溢出桶或溢出桶中无空闲单元,则申请一个溢出桶并存入新元素。 在基桶查找空闲单元时,使用的桶号为Index,由此可知(1)空缺处所填写的内容是“Index=NewElemKey%P”,或“Index=Hash(NewElemKey)”等其他等价形式。 一旦在基桶中找到空闲单元,即“Bucket[1ndex].keyData[i]==NULLKEY”(0≤i<ITEMS),则可将元素NewElemkey放入Bucket[Index].keyData[i],至此元素已经插入散列桶中,函数可返回,因此(2)空缺处所填写的内容是“i<ITEMS”。反之, 若在基桶中没有找到空闲单元,则需查找溢出桶。“t=Bucket[Index].Link”,指针t首先指向桶号Index的第一个溢出桶。以下的代码完成在溢出桶中查找空闲单元的功能。 [*] 由于每个溢出桶都可以存储ITEMS个元素,因此在溢出桶中查找空闲单元与在基桶中的查找过程相同,代码如下。 [*] 若在指针t指向的溢出桶中找到空闲单元则插入元素,否则,由“t=t->Link”得到下一个溢出桶的指针,因此“k<ITEMS”可作为是否在当前溢出桶中找到空闲单元的判定条件。显然,在桶号Index的基桶和其所有溢出桶都已满的情况下,t的值为空指针。此时才需要申请新的溢出桶并建立链接关系,因此在上面查找溢出桶中空闲单元时,进行指针t的后移“t=t->Link’’前应先用front记录t的值,以便于后面建立链接关系。所以(3)空缺处应给front置初值,即所填写的内容是“front=&Bucket[Index]”,或“front=Bucket+Index”等其他等价形式。 (4)空缺处用于判断该溢出桶是否已满,即所填写的内容是“k=ITEMS(或k>=ITEMS)”。如果该溢出桶已满,则继续查找下一个溢出桶,直到查找到空闲单元为止。 若所有溢出桶都不存在空闲单元(即t==NULL),则申请新的溢出桶,并将新的溢出桶的首地址保存在原有的最后一个溢出桶的Link域中(即front->Link=s)。因此(5)空缺处所填写的内容是“t==NULL”, (6)空缺处用于建立新申请溢出桶的链接关系——“front->Link=s”。
解析
转载请注明原文地址:https://kaotiyun.com/show/nYDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
若计算机中地址总线的宽度为24位,则最多允许直接访问主存储器(6)________________的物理空间(以字节为单位编址)。
在CPU的寄存器中,______对用户是完全透明的。
系统响应时间和作业吞吐量是衡量计算机系统性能的重要指标。对于一个持续处理业务的系统而言,其(4)。
网络杀毒软件厂商已经开始使用数据库技术和LDAP技术进行策略日志存储和用户管理,这里LDAP指的是______。A.轻量目录访问协议B.本地目录访问协议C.轻量数据访问协议D.本地数据访问协议
若C程序的表达式中引用了未赋初值的变量,则______。
若要求对大小为n的数组进行排序的时间复杂度为O(nlog2n),且是稳定的(即如果待排序的序列中两个数据元素具有相同的值,在排序前后它们的相对位置不变),则可选择的排序方法是______。
在网络应用测试中,网络延迟是一个重要指标。以下关于网络延迟的理解,正确的是(64)
给出关系R(A,B,C)和S(A,B,C),R和S的函数依赖集F={A→B,B→C}。若R和S进行自然连接运算,则结果集有3个属性。关系R和S________。
同一个VLAN中的成员可以形成一个广播域,从而实现何种功能?使Switch1的千兆端口允许所有VLAN通过的配置命令如下,请给出空白处的配置内容:Switchl(config)#interfacegigabit0/1(进入千兆端口配置模式)
阅读下列说明和C程序,将应填入(n)处的字句写在对应栏中。[说明]借助一个栈结构,可实现二叉树的非递归遍历算法。InOrderTraverse数实现中序非递归遍历,遍历过程如下:若不是空树,根节点入栈,进入左子树;若已
随机试题
Bananasareplantsthatgrowintropicalregions.Theygrowfourtothirtyfeetinheight.Thebananalookslikeatree,【C1】___
我国事故应急救援体系将事故应急救援预案分为()个级别。
板桩建筑物锚碇系统拉杆安装时,拉杆的螺母应全部旋进,并有不少于()个丝扣外露。
SherlockHolmesisconsideredbymanypeopleasthegreatdetectiveinfiction.Heis,infact,morefamousthanhisowncreator
我党处理宗教问题的基本政策是()宗教信仰的自由。
科学家们认为,由单一基因异常而导致的癌症少之又少,癌症起源于某个累积了一连串错误的细胞。慢性髓细胞白血病只需要一个突变就会发生,然而要达到足以致命的程度则需要更多偏差。大肠息肉通常只要几个基因突变就能发生,但发展成为癌症则需要更多受损的基因。从上
试论犯罪既遂的认定。
进程P1、P2、P3、P4和P5的前趋图如下所示:若用PV操作控制这5个进程的同步与互斥的程序如下,那么程序中的空①和空②处应分别为_______(1);空③和空④处应分别为_______(2);空⑤和空⑥处应分别为_______(3)。(1)
对于10Mb/s的端口,半双工端口带,宽为10Mb/s,而全双工端口带宽为______。
A、Theyaresoftandtenderinside.B、Theycanbecomfortablewiththemselves.C、Theydonotwantotherstobullythem.D、Theyha
最新回复
(
0
)