第10章索引与散列 录。最少有2*「m/213=2*503=25000个结点,存储2*「m213*「m1/21=200000个记录 10-13设散列表为H13],散列函数为H(key)=key%13。用闭散列法解决冲突,对下列关 键码序列12,23,45,57,20,03,78,31,15,36造表 (1)采用线性探查法寻找下一个空位,画出相应的散列表,并计算等概率下搜索成功的 平均搜索长度和搜索不成功的平均搜索长度 (2)采用双散列法寻找下一个空位,再散列函数为RH(key)=(7*key)%10+1,寻找下 个空位的公式为H=(H-1+RH(key)%13,H=H(key)。画出相应的散列表,并计算等概 率下搜索成功的平均搜索长度。 【解答】 使用散列函数H(key)= key mod13,有 H(23)=10 H(45)=6, H(20)=7, H(03)=3 H(78)=0 H(31)= H(15)=2 H(36)=10 (1)利用线性探查法造表: 1503 57452031 3612 (1)(1) (1)(1)(1)(4) (1)(2)(1) 搜索成功的平均搜索长度为 As1、(1+1+1+1+1+1+4+1+2+1)= 10 搜索不成功的平均搜索长度为 aslunsu (2+1+3+2+1+5+4+3+2+1+5+4+3)= (2)利用双散列法造 Hi=(Hi-1+ RH(key))%13, H1=H(key) 8 15035745203136231 (1) (1)(1) (1)(1)(1)(3)(5)(1) (1) 搜索成功的平均搜索长度为 ALoud=;(1+1+1+1+1+1+3+5+1+16 10-14设有150个记录要存储到散列表中,要求利用线性探查法解决冲突,同时要求找到所 需记录的平均比较次数不超过2次。试问散列表需要设计多大?设a是散列表的装载因子, 则有 ASL 【解答】 已知要存储的记录数为n=150,查找成功的平均查找长度为 ASLs≤2,则有 ASLs 1(1+-1)≤2,解得a≤2。又有a==150≤2,则m225 10-15若设散列表的大小为m,利用散列函数计算出的散列地址为h= hash(x) (1)试证明:如果二次探查的顺序为(h+q2),(h+(q-1)2)…,(h+1,h,(h-1)…(h-q), 其中,q=(m-l)2。因此在相继被探查的两个桶之间地址相减所得的差取模(%m)的结果为 m-2,m-4,m-6,…,5,3,l,1,3,5,…;,m-6,m-4,m-2 (2)编写一个算法,使用课文中讨论的散列函数h(x)和二次探查解决冲突的方法,按给 7第 10 章 索引与散列 7 录。最少有 2* m/2 3 = 2 * 503 = 250000 个结点，存储 2* m/2 3 * m1/2 = 2000000 个记录。 10-13 设散列表为 HT[13], 散列函数为 H (key) = key %13。用闭散列法解决冲突, 对下列关 键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。 (1) 采用线性探查法寻找下一个空位, 画出相应的散列表, 并计算等概率下搜索成功的 平均搜索长度和搜索不成功的平均搜索长度。 (2) 采用双散列法寻找下一个空位, 再散列函数为 RH (key) = (7*key) % 10 + 1, 寻找下 一个空位的公式为 Hi = (Hi-1 + RH (key)) % 13, H1 = H (key)。画出相应的散列表, 并计算等概 率下搜索成功的平均搜索长度。 【解答】 使用散列函数 H(key) = key mod 13，有 H(12) = 12, H(23) = 10, H(45) = 6, H(57) = 5, H(20) = 7, H(03) = 3, H(78) = 0, H(31) = 5, H(15) = 2, H(36) = 10. (1) 利用线性探查法造表： 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 (1) (1) (1) (1) (1) (1) (4) (1) (2) (1) 搜索成功的平均搜索长度为 ASLsucc = 1 10 (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 14 10 搜索不成功的平均搜索长度为 ASLunsucc = 1 13 (2 + 1 + 3 + 2 + 1 + 5 + 4 + 3 + 2 + 1 + 5 + 4 + 3) = 36 13 (2) 利用双散列法造表： Hi = (Hi-1 + RH (key)) % 13, H1 = H (key) 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 36 23 12 (1) (1) (1) (1) (1) (1) (3) (5) (1) (1) 搜索成功的平均搜索长度为 ASLsucc = 1 10 (1 + 1 + 1 + 1 + 1 + 1 + 3 + 5 + 1 + 1) = 16 10 10-14 设有 150 个记录要存储到散列表中, 要求利用线性探查法解决冲突, 同时要求找到所 需记录的平均比较次数不超过 2 次。试问散列表需要设计多大？ 设是散列表的装载因子， 则有 ) 1 1 (1 2 1 ASLsucc − = + 【解答】 已知要存储的记录数为 n = 150，查找成功的平均查找长度为 ASLsucc  2，则有 ASLsucc = 1 2 1 1 1 + −         2，解得   2 3 。又有 = n m m = 150  2 3 ，则 m  225。 10-15 若设散列表的大小为 m，利用散列函数计算出的散列地址为 h = hash(x)。 (1) 试证明：如果二次探查的顺序为(h + q2 ), (h + (q-1)2 ), …, (h+1), h, (h-1), …, (h-q 2 )， 其中， q = (m-1)/2。因此在相继被探查的两个桶之间地址相减所得的差取模(%m)的结果为 m-2, m-4, m-6, …, 5, 3, 1, 1, 3, 5, …, m-6, m-4, m-2 (2) 编写一个算法，使用课文中讨论的散列函数 h(x)和二次探查解决冲突的方法，按给