数据结构习题课第八章

1.设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数：

H(key)=key%13

采用开放地址法的线性探测再散列方法解决冲突，试在0～18的散列地址空间中对该关键字序列构造哈希表。

解：依题意，m=19，线性探测再散列的下一地址计算公式为：

d1=H(key)

dj+1=(dj+1)%m；j=1，2，...

其计算函数如下：

H(19)=19%13=6

H(01)=01%13=1

H(23)=23%13=10

H(14)=14%13=1(冲突)

H(14)=(1+1)%19=2

H(55)=55%13=3

H(20)=20%13=7

H(84)=84%13=6(冲突)

H(84)=(6+1)%19=7(仍冲突)

H(84)=(7+1)%19=8

H(27)=27%13=1(冲突)

H(27)=(1+1)%19=2(冲突)

H(27)=(2+1)%19=3(仍冲突)

H(27)=(3+1)%19=4

H(68)=68%13=3(冲突)

H(68)=(3+1)%19=4(仍冲突)

H(68)=(4+1)%19=5

H(11)=11%13=11

H(10)=10%13=10(冲突)

H(10)=(10+1)%19=11(仍冲突)

H(10)=(11+1)%19=12

H(77)=77%13=12(冲突)

H(77)=(12+1)%19=13

因此：各关键字的记录对应的地址分配如下：

addr(01)=1

addr(14)=2

addr(55)=3

addr(27)=4

addr(68)=5

addr(19)=6

addr(20)=7

addr(84)=8

addr(23)=10

addr(11)=11

addr(10)=12

addr(77)=13

其他地址为空。

2．设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数：

H(key)=key%13

采用开放地址法的二次探测再散列方法解决冲突，试在0～18的散列地址空间中对该关键字序列构造哈希表。

解：依题意，m=19，二次探测再散列的下一地址计算公式为：

d=H(key)

d=(d+j*j)%m

d=(d-j*j)%m；j=1，2，...

其计算函数如下：

H(19)=19%13=6

H(01)=01%13=1

H(23)=23%13=10

H(14)=14%13=1(冲突)

H(14)=(1+1*1)%19=2

H(55)=55%13=3

H(20)=20%13=7

H(84)=84%13=6(冲突)

H(84)=(6+1*1)%19=7(仍冲突)

H(84)=(6-1*1)%19=5

H(27)=27%13=1(冲突)

H(27)=(1+1*1)%19=2(冲突)

H(27)=(1-1)%19=0

H(68)=68%13=3(冲突)

H(68)=(3+1*1)%19=4

H(11)=11%13=11

H(10)=10%13=10(冲突)

H(10)=(10+1*1)%19=11(仍冲突)

H(10)=(10-1*1)%19=9

H(77)=77%13=12

因此：各关键字的记录对应的地址分配如下：

addr(27)=0

addr(01)=1

addr(14)=2

addr(55)=3

addr(68)=4

addr(84)=5

addr(19)=6

addr(20)=7

addr(10)=9

addr(23)=10

addr(11)=11

addr(77)=12

其他地址为空。

编辑：孙玉璐

转载请注明：http://www.92nongye.com/xxnr/2033.html