结构推理
确定一个数据的逻辑结构之后,可以用不同的方法在计算机内表示这个结构。请说明散列(或杂凑)表示方法的基本思想、优缺点以及适用情况。
【正确答案】散列表示方法用一个散列函数(例如取模运算)将关键码均匀地映射到散列空间的地址上,并采用一定的策略(例如线性探索)来处理碰撞。
优点:
①如果设计好,可以基本上达到随机存取。
②插入结点比较方便。
缺点:
①删除结点时,有的情况只能做标记(例如线性探索法解决碰撞)。
②散列函数的选择与具体关键码集合有关,并且可能出现堆积而影响检索的效率。
③增加一定的空间开销。
适用于需要高速检索的、静态的或基本上是静态的结构。
【答案解析】