4. (共15分)设哈希表长为m=13,散列函数为H(k)=k mod 11,关键字序列为5,7,16,12,11,21,31,51,17,81;试求:散列后的表中关键字分布(假定解决冲突的方法为线性探测再散列法);求平均查找长度ASL;计算

首先，将关键字序列散列到哈希表中，使用线性探测再散列法解决冲突：

|位置|关键字|
|---|---|
|0|17|
|1|81|
|2|11|
|3|31|
|4|12|
|5|5|
|6|16|
|7|7|
|8|51|
|9|21|
|10||
|11||
|12||

其中，第10个位置发生了冲突，需要再散列。由于哈希表长为13，因此再散列的散列函数为H'(k) = k mod 13。将10号位置的关键字再次散列：

|位置|关键字|
|---|---|
|0|17|
|1|81|
|2|11|
|3|31|
|4|12|
|5|5|
|6|16|
|7|7|
|8|51|
|9|21|
|10|1|
|11||
|12||

现在所有关键字都能够插入到哈希表中了。关键字分布如下：

|位置|关键字|
|---|---|
|0|17|
|1|81|
|2|11|
|3|31|
|4|12|
|5|5|
|6|16|
|7|7|
|8|51|
|9|21|
|10|1|
|11|16|
|12|31|

平均查找长度ASL的计算公式为：ASL = (查找成功的关键字的比较次数之和 + 查找失败的关键字的比较次数之和) / 关键字总数。

对于查找成功的关键字，比较次数为1，因此查找成功的关键字的比较次数之和为：1+1+1+1+1+1+1+1+1+1 = 10。

对于查找失败的关键字，需要按照散列函数和线性探测的规则进行查找，直到找到空位置或者找到该关键字。因此，查找失败的关键字的比较次数之和为：

- 16：1（位置6）+1（位置7）+1（位置8）+1（位置9）+1（位置10）= 5
- 51：1（位置8）+1（位置9）+1（位置10）+1（位置11）+1（位置12）= 5

因此，查找失败的关键字的比较次数之和为10。

综上，ASL = (10 + 10) / 10 = 2。