设关键字序列为{15，7，22，18，3，11，26，16，24，29}，哈希表表长为13，哈希函数为 H(key)=keymod13，用线性探测法处理冲突，请回答以下问题：（1）按照关键字的给定次序，构造哈希表；（2）计算查找关键字22，26，29时的比较次数；（3）计算查找成功情况下，哈希表的平均查找长度(ASL)。

1. 按照关键字的给定次序，构造哈希表如下：

索引   关键字
 0       15
 1       -
 2        7
 3       22
 4       18
 5        3
 6       11
 7       26
 8       16
 9       24
10       29
11       -
12       -

其中“-”表示该位置没有关键字。

2. 查找关键字22需要比较3次，查找关键字26需要比较4次，查找关键字29需要比较1次。

3. 假设哈希表中有n个关键字，m个位置，平均查找长度ASL = (查找成功的总次数/ n)。由于哈希函数是keymod13，因此关键字的哈希值只有13种可能。在本题中，有10个关键字，因此平均每个哈希值对应1个或多个关键字。根据线性探测法，若一个关键字的哈希值对应的位置已经被占用，则顺序往后查找，直到找到一个空位置为止。因此，查找成功的总次数为10，平均查找长度ASL = 10/10 = 1。因此，查找成功时的平均查找长度为1。

相关问题

设有一组初始关键字序列为 （24,35,12,27,18,26),则第3趟直接插入排序结束后的结果的是

在第3趟直接插入排序中，前三个关键字已经有序，第四个关键字27需要插入到前面有序子序列中。

(24,35,12,27,18,26) -> (12,24,35,27,18,26)

然后，前四个关键字已经有序，第五个关键字18需要插入到前面有序子序列中。

(12,24,35,27,18,26) -> (12,18,24,35,27,26)

最后，前五个关键字已经有序，第六个关键字26需要插入到前面有序子序列中。

(12,18,24,35,27,26) -> (12,18,24,27,35,26)

经过3趟直接插入排序后，得到的有序序列为(12,18,24,27,35,26)，其中，26需要再次插入到前面有序子序列中，最终得到完全有序序列为(12,18,24,26,27,35)。

设有一组初始关键字序列为(24,35,12,27,18,26),则第3趟直接插入排序结束后的结果的是

在第3趟直接插入排序结束后，前三个关键字已经有序，因此只需要将第4个关键字27插入到前面的有序序列中即可。插入过程如下：

1. 从序列中取出第4个关键字27。
2. 将27依次与前面的有序序列中的关键字进行比较，找到27插入的位置。
3. 在比较过程中，发现27大于12，因此将12向后移动一位，得到序列(24,35,12,27,18,26)。
4. 继续比较，发现27大于24，因此将27插入到24和35之间，得到序列(24,27,35,12,18,26)。
5. 第3趟直接插入排序结束后的结果为(24,27,35,12,18,26)。

因此，第3趟直接插入排序结束后的结果为(24,27,35,12,18,26)。