设一个散列表采用闭散列法构造,散列数采用除留余数法,解决冲突的方法采用二次探查法。基于6-34
(1)在散列表中搜索具有指定关键码值的表项的函数。
(2)在散列表中删除具有指定关键码值的表项的函数。
(3)在散列表中插人具有指定关键码值的表项的函数,
(4)求搜索成功时的平均搜索长度的函数.
(1)在散列表中搜索具有指定关键码值的表项的函数。
(2)在散列表中删除具有指定关键码值的表项的函数。
(3)在散列表中插人具有指定关键码值的表项的函数,
(4)求搜索成功时的平均搜索长度的函数.
义词子表法。
(1)设计用分离的同义词子表组织的开散列表的类。
(2)设计在做列表中搜索具有指定关键码值的表项的算法。
(3)设计在散列表中删除具有指定关键码值的表项的算法。
(4)设计在散列表中插人具有指定关键码值的表项的算法。
(5)设计由一组关键码值建立散列表的算法。
(6)设计输出散列表的算法。
(7)求搜索成功时的平均搜索长度的算法。
(8)求搜索不成功时的平均搜索长度的算法。
若设散列表的大小为m,利用散列函数计算出的散列地址为h-hash(x)。
(1)试说明确定m的原则。
(2)试证明:如果采用二次探查法解决冲突,表的大小是一个索数,若当表的装载因子α≤0.5,则新的元素总能被插入,且在插人过程中没有一个存储地址被探查2次。
20,03,78,31,15,36建立表。
(1)采用线性探查法寻找下一个空位,画出机应的散列表,并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
(2)采用双散列法寻找下一个空位,再散列函数为RH(key)=(7×key)%10+1,寻找下一个空位的公式为Hi=(Hi-1+RH(key))%13,H1=H(key)。画出相应的散列表,并计算等概率下搜索成功的平均搜索长度。
存储字。如果在表中已经有n个表项,散列表总共有m个散列位置,包括空表项所占据的位置。
(1)如果采用闭散列(开地址)法解决冲突,散列表需要多少存储字?
(2)如果采用开散列(链地址)法解决冲突,所有记录信息存于若于分离的结点中,每个结点连同指针成员包含s+1个存储字。那么n个结点总共需要多少个存储字?
(3)如果采用开散列(链地址)法解决冲突,散列表本身需要多少个存储字?设定指向溢出链(同义词子表)的指针只占1个存储字。
设有一散列表如下图所示:
设该散列表采用双散列函数法解决碰撞,其两个散列函数为H1(K)=K mod 13,H2(K)=(K mod 11)+1。从该散列表中检索出35需几次比较?请写出比较顺序。
【题目描述】
● 若线性表(24, 13, 31, 6, 15, 18, 8)采用散列(Hash)法进行存储和查找,设散列函数为H(Key)=Key mod 11,则构造散列表时发生冲突的元素为 (1) 。(其中的mod表示整除取余运算)
(1)
A. 24和13
B. 6 和15
C. 6 和24
D. 18和8
【我提交的答案】: B |
【参考答案与解析】: 正确答案:A |
【我的疑问】(如下,请求专家帮助解答)
求详解
设散列表的长度为13,散列函数为H(K)=K%13,给定的关键字序列为19,14,23,1,68,20,84,27,55,11,10,79。试画出分别用链地址法和线性探测法解决冲突时所构造的散列表,并求等概率下这两种方法的成功和不成功的平均查找长度。
设α是散列表的装载因子,则应用线性探查法解决冲突时的搜索成功的平均搜索长度和搜索不成功的平均搜索长度分别为:
请根据题意选择合用的公式。
在地址空间为0~16的散列区中,对以下关键字序列构造两个散列表:
1)用线性探测开放定址法处理冲突;
2)用链地址法处理冲突。
并分别求这两个散列表在等概率情况下查找成功和不成功的平均查找长度。设散列函数为H(key)=i/2,其中i为关键字中第一个字母在字母表中的序号。