则有 【解答】 已知要存储的记录数为n=150,查找成功的平均查找长度为ASLa≤2,则有 ASLs ≤2,解得a≤2。又有=m=150≤2,则m222 n 10-19若设散列表的大小为m,利用散列函数计算出的散列地址为h=hash(x) (1)试证明:如果二次探查的顺序为(h+q),(h+(q-1)2)…;(h+1),h,(h-1),…(hv2), 其中,q=(m-1)/2。因此在相继被探查的两个桶之间地址相减所得的差取模(%m)的结果为 m-2,m4,m6,…,5,3,1,1,3,5,…,m6,m-,m2 (2)编写一个算法,使用课文中讨论的散列函数h(x)和二次探查解决冲突的方法,按给 定值x来搜索一个大小为m的散列表。如果ⅹ不在表中,则将它插入到表中。 10-22设有1000个值在1到10000的整数,试设计一个利用散列方法的算法,以最少的数 据比较次数和移动次数对它们进行排序 【解答】 10-23设有15000个记录需放在散列文件中,文件中每个桶内各页块采用链接方式连结,每 个页块可存放30个记录。若采用按桶散列,且要求搜索到一个已有记录的平均读盘时间不 超过1.5次,则该文件应设置多少个桶? 【解答】 已知用链地址法(开散列)解决冲突,搜索成功的平均搜索长度为1+α/2≤1.5,解出 a≤1,又a=n/m=15000/30/m=500/m≤1,m≥500。由此可知,该文件至少应设置 500个桶。则有 ASLsucc = + − 1 2 1 1 1 ( )  【解答】 已知要存储的记录数为 n = 150，查找成功的平均查找长度为 ASLsucc  2，则有 ASLsucc = 1 2 1 1 1 + −         2，解得   2 3 。又有 = n m m = 150  2 3 ，则 m  225。 10-19 若设散列表的大小为 m，利用散列函数计算出的散列地址为 h = hash(x)： (1) 试证明：如果二次探查的顺序为(h + q 2 ), (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)和二次探查解决冲突的方法，按给 定值 x 来搜索一个大小为 m 的散列表。如果 x 不在表中，则将它插入到表中。 10-22 设有 1000 个值在 1 到 10000 的整数，试设计一个利用散列方法的算法，以最少的数 据比较次数和移动次数对它们进行排序。 【解答】 10-23 设有 15000 个记录需放在散列文件中，文件中每个桶内各页块采用链接方式连结，每 个页块可存放 30 个记录。若采用按桶散列，且要求搜索到一个已有记录的平均读盘时间不 超过 1.5 次，则该文件应设置多少个桶？ 【解答】 已知用链地址法（开散列）解决冲突，搜索成功的平均搜索长度为 1+α/2≤1.5，解出 α≤1，又α= n / m = 15000 / 30 / m = 500 / m ≤1，m≥500。由此可知，该文件至少应设置 500 个桶