问题
单项选择题
设散列表的地址空间为0到10，散列函数为h(k)=k mod 11，用线性探查法解决碰撞。现从空的散列表开始，依次插入关键码值36，95，14，27，68，82，则最后一个关键码插入后散列表的负载因子α约为
A．0.45
B．0.55
C．0.65
D．0.75
答案
参考答案：B
解析：线性探查法将散列表看成是一个环形表，若在基地址d(即h(K)=d)发生冲突，则依次探查下述地址单元：d+1，d+2，…，M-1，O，1，…，d-1直到找到一个空闲地址或查找到关键码为key的结点为止。题中散列表长度M=11，n=6，散列函数为：h(k)=k mod 11。按顺序插入各个结点：36：h(36)=3，95：h(95)=7，插入14时，其散列地址为3，由于3已被关键码为36的元素占用，故需进行探查。按顺序探查法，显然4为开放的空闲地址，故可将其放在4单元。27：h(27)=5，68：h(68)=2，插入82时，其散列地址为5，由于5已被关键码为27的元素占用，故需进行探查。按顺序探查法，显然6为开放的空闲地址，故可将其放在6单元。负载因子α=N/M。其中，M是散列表存储空间大小，N是表中当前的记录数目。故α=0.55。