（简答题）

假定一个待散列存储的线性表为（32，75，29，63，48，94，25，46，18，70），散列地址空间为HT[13]，若采用除留余数法构造散列函数和线性探查法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。

正确答案

散列函数：H（K）=k%m其中依题意得m=13
H（32）=32%13=6
H（5）=75%13=10
H（29）=29%13=3
H（63）=63%13=11
H（8）=48%13=9
H（94）=94%13=3（冲突）
设d₀=H（K）=H（94）=3
d₁=（d₀+1）%m=（3+1）%13=4
H（25）=25%13=12
H（46）=46%13=7
H（18）=18%13=5
H（70）=70%13=5（冲突）
设d₀=H（K）=H（70）=5
d₁=（d₀+1）%m=（5+1）%13=6（冲突）
d₂=（d₁+1）%m=（6+1）%13=7（冲突）
d₃=（d₂+1）%m=（7+1）%13=8
ASL=（8*1+1*2+1*4）/10=1.4

答案解析

略

相似试题

（简答题）
假定一个待散列存储的线性表为（32，75，29，63，48，94，25，46，18，70），散列地址空间为HT[11]，若采用除留余数法构造散列函数和链接法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。
答案解析
（单选题）
已知一个线性表（38，25，74，63，52，48），假定采用h（k）=k%7计算散列地址进行散列存储，若引用线性探测的开放定地址法解决冲突，则在该散列表上进行查找的平均查找长度为（）。
答案解析
（填空题）
若待散列的序列为（18，25，63，50，42，32，9），散列函数为H（key）=keyMOD9，与18发生冲突的元素有（）个。
答案解析
（填空题）
假定要对长度n=100的线性表进行散列存储，并采用链接法处理冲突，则对于长度m=20的散列表，每个散列地址的单链表的长度平均为（）。
答案解析
（填空题）
假定对线性表（38，25，74，52，48）进行散列存储，采用H（K）=K%7作为散列函数，若分别采用线性探查法和链接法处理冲突，则对各自散列表进行查找的平均查找长度分别为（）和（）。
答案解析
（填空题）
对于线性表（18，25，63，50，42，32，90）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为0的元素有（）个，散列地址为5的元素有（）个。
答案解析
（填空题）
在下面数组a中链接存储着一个线性表，表头指针为a[0].next，则该线性表为（）。
答案解析
（填空题）
假定一个线性表为（12，23，74，55，63，40，82，36），若按Key%3条件进行划分，使得同一余数的元素成为一个子表，则得到的三个子表分别为（）、（）和（）。
答案解析
（单选题）
对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（）个。
答案解析