(11)设散列表的地址空间为 0到 10,散列函数为 h(k)=k mod 11,用线性探查法解决碰撞。现从空的散列

Question

（11）设散列表的地址空间为 0到 10，散列函数为 h(k)=k mod 11，用线性探查法解决碰撞。现从空的散

列表开始，依次插入关键码值 36，95，14，27，68，82，则最后一个关键码插入后散列表的负载因子 a 约

为（ ）。

A）0.45

B）0.55

C）0.65

D）0.75

Answer 1

正确答案：B

（11）【答案】B）
【解析】线性探查法将散列表看成是一个环行表，若在基地址d（即h（K）=d）发生冲突，则依次探查下述地址单元：d+1，d+2，…，M-0，0，1…，d-1直到找到一个空闲地址或岔道找到关键码为key的结点为止。题中三列表长度M=11，n=6，散列函数为h（k）=k mod11。在本题中，按顺序插入各个结点。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单元。负载因子a=N/M.其中M是散列表存储空间大小，N表中当前的记录数目。故a=0.55.