h=H(M),其中H为散列函数,H应该具有的特性包括()
A.给定M,很容易计算h
B.给定h,很容易计算M
C.给定M,不能计算h
D.给定h,不能计算M
E.给定M,要找到另一个输入串M'并满足H(M')=H(M)很难
A.给定M,很容易计算h
B.给定h,很容易计算M
C.给定M,不能计算h
D.给定h,不能计算M
E.给定M,要找到另一个输入串M'并满足H(M')=H(M)很难
假定把关键码k散列到有n个结点(从0到n-1编号)的散列表中。对于下面的每一个函数h(k)(七为整数),这个函数作为散列函数可以接受吗?(即对于插入和检索,散列程序能正常工作吗?)如果可以,它是一个好的散列函数吗?设函数Random(n)返回一个0到n-1之间的随机整数(包含这两个数在内)。 (1)h(k)=k/n; (2)h(k)=1; (3)h(k)=(k+random(n))mod n; (4)h(k)=k mod m,其中m是一个小于等于n的最大素数。
给定表(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Oct,Nov,Dec)。设取散列函数H(x)=i/2,其中i为键值中第一个字母在英文字母表中的序号,要求:
dr(61)=6、addr(84)=7.其余地址为空。如用二次探查法解决冲突,关键码值为49的散列地址是()。
A、8
B、3
C、5
D、9
A.8
B.3
C.5
D.9
已知一个待散列存储的线性表18,34,58,26,75,67,48,81,散列函数为H(k)=k mod 11,若采用线性探测法解决冲突,则平均查找长度为______。若采用链接法解决冲突,则平均查找长度为______。
A.1
B.2
C.3
D.4
设散列表的长度为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为关键字中第一个字母在字母表中的序号。
20,03,78,31,15,36建立表。
(1)采用线性探查法寻找下一个空位,画出机应的散列表,并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
(2)采用双散列法寻找下一个空位,再散列函数为RH(key)=(7×key)%10+1,寻找下一个空位的公式为Hi=(Hi-1+RH(key))%13,H1=H(key)。画出相应的散列表,并计算等概率下搜索成功的平均搜索长度。