发布时间 : 星期六 文章严蔚敏-数据结构集合习题更新完毕开始阅读4410cb09bb68a98271fefaf5
2．（1）散列表存储的基本思想是用关键字的值决定数据元素的存储地址 （2）散列表存储中解决碰撞的基本方法：
① 开放定址法 形成地址序列的公式是：Hi=（H（key）+di）% m，其中m是表长，di是增量。根据di取法不同，又分为三种：
a．di =1，2，?，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。
22222
b．di =1，-1，2，-2，? ，?k（k≤m/2） 称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j为整数）的素数时才有可能。
c．di =伪随机数序列，称为随机探测再散列。
② 再散列法 Hi=RHi（key） i=1，2，?，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。
③ 链地址法 将关键字为同义词的记录存储在同一链表中，散列表地址区间用H[0..m-1]表示，分量初始值为空指针。凡散列地址为i（0≤i≤m-1）的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而①中的散列表称闭散列表，含义是元素个数受表长限制。
④ 建立公共溢出区 设H[0..m-1]为基本表，凡关键字为同义词的记录，都填入溢出区
O[0..m-1]。 （3）用分离的同义词表和结合的同义词表解决碰撞均属于链地址法。链地址向量空间中的每个元素不是简单的地址，而是关键字和指针两个域，散列地址为i（0≤i≤m-1）的第一个关键字存储在地址空间向量第i个分量的“关键字”域。前者的指针域是动态指针，指向同义词的链表，具有上面③的优缺点；后者实际是静态链表，同义词存在同一地址向量空间（从最后向前找空闲单元），以指针相连。节省了空间，但易产生“堆积”，查找效率低。 （4）要在被删除结点的散列地址处作标记，不能物理的删除。否则，中断了查找通路。 （5）记录 负载因子
3．评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。解决冲突的方法见上面2题。
4．哈希方法的平均查找路长主要取决于负载因子（表中实有元素数与表长之比），它反映了哈希表的装满程度，该值一般取0.65~0.9。解决冲突方法见上面2题。
5．不一定相邻。哈希地址为i（0≤i≤m-1）的关键字，和为解决冲突形成的探测序列i的同义词，都争夺哈希地址i。 6．
散列地址 0 关键字 14 比较次数 1 1 01 1 2 9 1 3 23 2 4 84 5 27 6 55 1 7 20 2 8 9 3 4 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8 以关键字27为例：H（27）=27%7=6（冲突） H1=（6+1）=7（冲突）
23
H2=（6+2）=0（冲突） H3=（6+3）=5 所以比较了4次。 7．由于装填因子为0.8，关键字有8个，所以表长为8/0.8=10。 （1）用除留余数法，哈希函数为H（key）=key % 7
（2）
散列地址 0 关键字 21 比较次数 1 1 15 1 2 30 1 3 36 3 4 25 1 5 40 1 6 26 2 7 37 6 8 9 （3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，当其哈希地址为i（0≤i≤m-1）时的查找次数。本例中m=10。故查找失败时的平均查找长度为：
ASLunsucc=（9+8+7+6+5+4+3+2+1+1）/10=4.6 ASLsucc =16/8=2 （4）int Delete（int h[n]，int k）
// 从哈希表h[n]中删除元素k，若删除成功返回1，否则返回0 {i=k%7；// 哈希函数用上面（1），即H（key）=key % 7
if（h[i]== maxint）//maxint解释成空地址
printf（“无关键字%d\\n”，k）；return （0）；}
if（h[i]==k）{h[i]=-maxint ；return （1）；} //被删元素换成最大机器数的负数
else // 采用线性探测再散列解决冲突 {j=i;
for（d=1；d≤n-1；d++）
{i=（j+d）%n； // n为表长，此处为10
if（h[i]== maxint）return (0); //maxint解释成空地址
if（h[i]==k）{ h[i]=-maxint ；return （1）；} }//for }
printf（“无关键字%d\\n”，k）；return (0) } 8． 散列地址 0 关键字 比较次数 散列地址 0 关键字 比较次数 1 15 1 1 15 1 2 2 17 3 3 24 1 3 24 1 4 10 2 4 10 2 5 19 1 5 19 1 6 17 4 6 40 2 7 38 5 7 38 4 8 18 5 8 18 4 9 40 5 9 哈希表a: ASLsucc=24/8=3；
哈希表b: ASLsucc =18/8 9．（1）
散列地址 0 关键字 13 比较次数 1 1 22 1 2 3 53 1 4 1 2 5 6 41 1 7 67 2 8 46 1 9 10 51 1 11 12 30 1 （2）装填因子=9/13=0.7 （3）ASLsucc =11/9 （4）ASLunsucc =29/13
10． 11．ASLsucc=19/12 12．常用构造哈希函数的方法有：
（1）数字分析法 该法事先需知道关键字集合，且关键字位数比散列表地址位数多，应选数字分布均匀的位。
（2）平方取中法 将关键字值的平方取中间几位作哈希地址。
（3）除留余数法 H（key）=key%p，通常p取小于等于表长的最大素数。
（4）折叠法 将关键字分成长度相等（最后一段可不等）的几部分，进行移位叠加或间界叠加，其值作哈希地址。
（5）基数转换法 两基数要互素，且后一基数要大于前一基数。
在哈希表中删除一个记录，在拉链法情况下可以物理地删除。在开放定址法下，不能物理地删除，只能作删除标记。该地址可能是该记录的同义词查找路径上的地址，物理的删除就中断了查找路径。因为查找时碰到空地址就认为是查找失败。
散列地址 0 1 关键字 13．（1） 散列地址 0 关键字 比较次数 1 4 1 2 3 12 1 4 49 1 5 38 2 6 13 1 7 24 2 8 32 1 9 21 2 10 比较次数 1 2 2 3 1 4 4 5 3 6 1 7 1 8 3 9 9 10 11 12 13 14 15 1 1 3 14 01 68 27 55 19 20 84 79 23 11 10 ASLsucc =（1+1+1+2+1+2+1+2）/8=11/8 ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11
（2）
13题图ASLsucc =11/8 ASLunsucc=19/11 14题（2） ASLsucc=13/8 ASLunsucc=19/11
值得指出，对用拉链法求查找失败时的平均查找长度有两种观点。其一，认为比较到空指针算失败。以本题为例，哈希地址0、2、5、7、9和10均为比较1次失败，而哈希地址1和3比较2次失败，其余哈希地址均为比较3次失败，因此，查找失败时的平均查找长度为19/11，我们持这种观点。还有另一种理解，他们认为只有和关键字比较才计算比较次数，而和空指针比较不计算。照这种观点，本题的ASLunsucc=（1+1+2+2+2）/11=8/11
14．由hashf(x)=x mod 11 可知，散列地址空间是0到10，由于有8个数据，装载因子取0.7。 （1） 散列地址 0 关键字 33 比较次数 1 1 1 1 2 13 1 3 12 3 4 34 4 5 38 1 6 27 2 7 22 8 8 9 10 ASLsucc=21/8 ASLunsucc=47/11 15．
（1）ASL=42/12
（2）a：ASLsucc=31/12 （2）b：ASLsucc=18/12 (注：本题[x]取小于等于x的最大整数) 16．
17．查找时，对关键字49,22,38,32,13各比较一次，对21,18各比较两次