【正确答案】正确答案：(1)哈希表存储的基本思想是用关键字的值决定数据元素的存储地址。 (2)哈希表存储中解决碰撞的基本方法： ①开放定址法。形成地址序列的公式是：H
i
=(H(key)+d
i
)％m，其中m是表长，d
i
是增量。根据d
i
取法不同，又分为三种：a.d
i
=1，2，…，m一1称为线性探测再哈希，其特点是逐个探测表空间，只要哈希表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一哈希地址。b.d
i
=1
2
，一1
2
，2
2
，一2
2
，…，±k
2
(k≤m／2)称为二次探测再哈希，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3(，为整数)的素数时才有可能。c.d
i
=伪随机数序列，称为随机探测再哈希。 ②再哈希法。H
i
=RH
i
(key)i=1，2，…，k，是不同的哈希函数，即在同义词产生碰撞时，用另一哈希函数计算哈希地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。 ③链地址法。将关键字为同义词的记录存储在同一链表中，哈希表地址区间用研0一..m一1]表示，哈希表元素初始值为空指针。凡哈希地址为f(0≤i≤m一1)的记录均插在以研[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种哈希表常称为开哈希表，“开”的含义是哈希表无边界，元素个数没限制，哈希表不会溢出，只受存储空间限制。而①中的哈希表称闭哈希表，“闭”含义是元素个数受表长限制。 ④建立公共溢出区。设H[0一m一1]为基本表，凡关键字为同义词的记录，都填入溢出区O[0..m一1]。 (3)用分离的同义词表和结合的同义词表解决碰撞均属于链地址法。链地址向量空间中的每个元素不是简单的地址，而是关键字和指针两个域，哈希地址为i(0≤i≤m—1)的第一个关键字存储在地址空间向量下标为i的“关键字”域。前者的指针域是动态指针，指向同义词的链表，具有上面 ③的优缺点；后者实际是静态链表，同义词存在同一地址向量空间(从最后向前找空闲单元)，以静态指针(下标)相连。这节省了空间，但易产生“堆积”，查找效率低。 (4)要在被删除结点的哈希地址处作标记，不能物理地删除。否则，中断了查找通路。 (5)记录、负载因子