问答题 在用除余法作为散列函数、线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。【中科院计算所2000八(15分)】
【正确答案】正确答案:首先计算关键字的散列地址,若该地址为空(null),则空操作;若该地址有关键字,但与给定值不等,则用解决冲突的方法去查找给定值;若该关键字与给定值相等,则实行删除。由于用线性探测解决冲突,设被删除元素的散列地址为i,则其余m一1(m为表长)个位置均可能是同义词。查找同义词的操作直到碰到空地址或循环一圈回到i才能结束。为了提高算法效率,应将最后一个同义词前移填充被删除关键字,但要保证二次聚集时也正确。
【答案解析】