问答题
解答题。【中国海洋大学2006六(15分)】
(1)画出对长度为10的有序表进行折半查找的查找树,并求其等概率时查找成功的平均查找长度。
(2)设有一组关键字{9,01,23,14,55,20,84,27},采用哈希函数:H(key)=key MOD 7,表长为10,用开放地址法的二次探测再散列方法胁=H(key)+di)MOD 10(di=1
2
,2
2
,3
2
,…)解决冲突。要求:对该关键字序列构造哈希表,指出有哪些同义词并计算查找成功的平均查找长度。
【正确答案】正确答案:(1)ASL
成功
=(1*1+2*2+4*3+3*4)/10=29/10(4*3含义是4个长度为3的结点)判定树请参见上面第9题。 (2)55、20和27是同义词,9和23是同义词,14和84是同义词。

【答案解析】