题3

题3

题目

Q:下列关于散列表的说法中, 正确的是 ( ).
I. 若散列表的填装因子 ,则可避免碰撞的产生
II. 散列查找中不需要任何关键字的比较
III. 散列表在查找成功时平均查找长度仅与表长有关
IV. 若在散列表中删除一个元素, 不能简单地将该元素删除
A. I 和 IV
B. II 和 III
C. III
D. IV

分析

A:散列表的填装因子是指散列表中已存储元素个数与散列表长度的比值。

• 例如，一个长度为 10 的散列表中存储了 5 个元素，则该散列表的填装因子为 0.5。
• 填装因子是衡量散列表性能的重要指标之一。
• 填装因子越大，散列表中已存储的元素越多，发生冲突的可能性就越大，散列查找的效率就越低。
• 反之，填装因子越小，发生冲突的可能性就越小，散列查找的效率就越高，但也会造成存储空间的浪费。
  描述1肯定不太对，因为还有映射到的线性表中元素相隔是否紧密的问题
  我认为了2是对的，因为忘记了关键字的比较确认，也是一次比较的过程

解

D
冲突 (碰撞) 是不可避免的, 与装填因子无关, 因此需要设计处理冲突的方法, I 错误。
散列查找的思想是计算出散列地址来进行查找, 然后比较关键字以确定是否查找成功, II 错误。
散列查找成功的平均查找长度与装填因子有关, 与表长无直接关系, III 错误。
在开放定址的情形下, 不能随便删除散列表中的某个元素, 否则可能会导致搜索路径被中断 (因此通常的做法是在要删除的地方做删除标记, 而不是直接删除), IV 正确。