Question

以下计算机中数据结构与算法的问题答案是什么？

2、在地址空间为0~16的散列区中，对以下关键字序列构造两个哈希表：
{Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec}
（1） 用线性探测开放地址法处理冲突；
（2） 用链地址法（开散列存储）处理冲突
并分别求这两个哈希表在等概率情况下查找成功的平均查找长度。设哈希函数为
H(key) = i/2,其中i为关键字中第一个字母在字母表中的序号,如下：
A B C D E F G H I J K L M N O P Q R S R U V W X Y Z
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Answer 1

（1） 用线性探测开放地址法处理冲突；
H(Jan)=10/2=5;
H(Feb)=6/2=3;
H(Mar)=13/2=6;
H(Apr)=1/2=0;
H(May)=13/2=6;冲突;H1=6+1=7;
H(June)=10/2=5;冲突;H1=5+1=6;冲突;H2=7;H3=8;
H(July)=5;H1=6;H2=7;H3=8;H4=9
H(Aug)=0;H1=1;
H(Sep)=9;H1=10;
H(Oct)=7;H1=8;H2=9;H3=10;H4=11;
H(Nov)=7;H1=8;H2=9;H3=10;H4=11;H5=12
H(Dec)=2
ASL=(1+2+1+1+1+1+2+4+5+2+5+6)/12=31/12
(2） 用链地址法处理冲突
H(Jan)=5;
H(Feb)=3;
H(Mar)=6;
H(Apr)=0;
H(May)=6
H(June)=5;
H(July)=5;
H(Aug)=0;;
H(Sep)=9;
H(Oct)=7;
H(Nov)=7;
H(Dec)=2

0->Apr->Aug
1->
2->Dec
3->Feb
4->
5->Jan->June->July
6->Mar->May
7->Oct->Nov
8->
9->Sep
ASL=(1+2+1+1+1+2+3+1+2+1+2+1)/12=18/12