问答题
已知某哈希表HT的装填因子小于1，哈希函数H(key)为关键字的第一个字母在字母表中的序号。【西北大学2001五】
问答题
处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。
【正确答案】正确答案：由于装填因子小于1，且哈希函数H(k)为关键字第一个字母在字母表中的序号，字母 ‘A’的序号为1，表长可设为n(n≥27)，而在链地址法中，表长为26。查找不成功是指碰到空指针为止(另一种观点是空指针不计算比较次数，请参见本章应用题第65题 (2))。核心语句段如下： for(i=1；i≤26；i++) ／／哈希地址1到26 (j=1；count(
【答案解析】
问答题
处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。
【正确答案】正确答案：for(i=1；i≤26；i++) (p=h[i]；j=1；／／按我们的约定，查找不成功指到空指针为止 while(p!=null) {j++；p=p一>next；} count+=j； } return (count／26．0)；
【答案解析】