设有一组关键字{29,01,13,15,56,20,87,27,69,9,10,74},散列函数为：H(key)=key % 17,采用线性测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表，并计算成功查找的平均查找度。手写过程

### 回答1：
首先，根据散列函数H(key)=key%17，将关键字序列映射到散列表中的位置：

| 地址 | 关键字 |
|------|--------|
| 12 | 29 |
| 1 | 01 |
| 13 | 13 |
| 15 | 15 |
| 5 | 56 |
| 3 | 20 |
| 4 | 87 |
| 10 | 27 |
| 2 | 69 |
| 9 | 09 |
| 10 | 10 |
| 7 | 74 |

可以看到，有两个关键字(27和10)哈希到了同一个位置(地址10)，这就是冲突。采用线性探测法解决冲突，即从发生冲突的位置开始，依次向后查找，直到找到一个空的位置或者遍历了整个散列表。

经过线性探测后，散列表变为：

| 地址 | 关键字 |
|------|--------|
| 12 | 29 |
| 1 | 01 |
| 13 | 13 |
| 15 | 15 |
| 5 | 56 |
| 3 | 20 |
| 4 | 87 |
| 10 | 27 |
| 2 | 69 |
| 9 | 09 |
| 11 | 10 |
| 7 | 74 |

接下来，计算成功查找的平均查找长度。假设要查找的关键字等概率地分布在散列表中，那么平均查找长度ASL可以用以下公式计算：

ASL = (sum(ci^2) - n) / (2n)

其中，ci为散列表中第i个位置的关键字个数，n为关键字总数。

对于这个散列表，ci的值为：

| 地址 | 关键字 | ci |
|------|--------|----|
| 0 | | 0 |
| 1 | 01 | 1 |
| 2 | 69 | 1 |
| 3 | 20 | 1 |
| 4 | 87 | 1 |
| 5 | 56 | 1 |
| 6 | | 0 |
| 7 | 74 | 1 |
| 8 | | 0 |
| 9 | 09 | 1 |
| 10 | 27,10 | 2 |
| 11 | | 0 |
| 12 | 29 | 1 |
| 13 | 13 | 1 |
| 14 | | 0 |
| 15 | 15 | 1 |
| 16 | | 0 |
| 17 | | 0 |

根据公式，ASL = (sum(ci^2) - n) / (2n) = (1^2+1^2+1^2+1^2+1^2+1^2+1^2+1^2+1^2+2^2+1^2+1^2-12) / (2*12) = 1.25

因此，成功查找的平均查找长度为1.25。

### 回答2：
散列表的散列地址空间为0到18，散列函数为H(key)=key % 17。

首先，我们要计算每个关键字的散列地址。根据散列函数，可以得到关键字的散列地址如下：

29 % 17 = 12
01 % 17 = 1
13 % 17 = 13
15 % 17 = 15
56 % 17 = 5
20 % 17 = 3
87 % 17 = 2
27 % 17 = 10
69 % 17 = 1
9 % 17 = 9
10 % 17 = 10
74 % 17 = 6

接下来，我们采用线性探测法解决冲突。当发生冲突时，我们向后查找空的槽位，直到找到一个空的槽位或者循环一圈后回到原来的位置。将关键字插入到空的槽位中。

插入过程如下：

地址12：29
地址1：01 --> 冲突，向后查找，地址1已经被占用，继续向后，地址9已被占用，继续向后，找到地址10为空，插入01
地址13：13
地址15：15
地址5：56
地址3：20
地址2：87 --> 冲突，向后查找，地址2已经被占用，继续向后，找到地址3为空，插入87
地址10：27 --> 冲突，向后查找，地址10已经被占用，继续向后，找到地址11为空，插入27
地址1：69 --> 冲突，向后查找，地址1已经被占用过，继续向后，地址2已经被占用过，继续向后，找到地址3已被占用过，继续向后，找到地址4已被占用过，继续向后，找到地址5已被占用过，继续向后，找到地址6已被占用过，继续向后，找到地址7已被占用过，继续向后，找到地址8已被占用过，继续向后，找到地址9已被占用过，继续向后，找到地址10已被占用过，继续向后，找到地址11已被占用过，继续向后，找到地址12已被占用过，继续向后，找到地址13已被占用过，继续向后，找到地址14已被占用过，继续向后，找到地址15已被占用过，继续向后，找到地址16已被占用过，继续向后，找到地址0为空，插入69
地址9：9
地址10：10 --> 冲突，向后查找，地址10已经被占用过，继续向后，地址11已被占用过，继续向后，找到地址12已被占用过，继续向后，找到地址13已被占用过，继续向后，找到地址14已被占用过，继续向后，找到地址15已被占用过，继续向后，找到地址16已被占用过，继续向后，找到地址0已被占用过，继续向后，找到地址1已被占用过，继续向后，找到地址2已被占用过，继续向后，找到地址3已被占用过，继续向后，找到地址4已被占用过，继续向后，找到地址5已被占用过，继续向后，找到地址6已被占用过，继续向后，找到地址7已被占用过，继续向后，找到地址8已被占用过，继续向后，找到地址9已被占用过，继续向后，找到地址10已被占用过，继续向后，找到地址11已被占用过，继续向后，找到地址12已被占用过，继续向后，找到地址13已被占用过，继续向后，找到地址14已被占用过，继续向后，找到地址15已被占用过，继续向后，找到地址16已被占用过，继续向后，找到地址0已被占用过，继续向后，找到地址1已被占用过，继续向后，找到地址2已被占用过，继续向后，找到地址3已被占用过，继续向后，找到地址4已被占用过，继续向后，找到地址5已被占用过，继续向后，找到地址6已被占用过，继续向后，找到地址7已被占用过，继续向后，找到地址8已 被占用过，继续向后，找到地址9已被占用过，继续向后，找到地址10已被占用过，循环回到原来的位置
地址6：74

最终得到的散列表如下：

地址0：69
地址1：01
地址2：87
地址3：20
地址4：
地址5：56
地址6：74
地址7：27
地址8：
地址9：9
地址10：10
地址11：13
地址12：29
地址13：13
地址14：
地址15：15
地址16：

成功查找的平均查找度可以通过计算每个关键字发生冲突时的查找度并求平均得到。在这个例子中，地址1、地址2、地址10和地址13发生了冲突。

地址1：查找度为1
地址2：查找度为1
地址10：查找度为3
地址13：查找度为0

平均查找度 = (1 + 1 + 3 + 0) / 4 = 1.25

因此，成功查找的平均查找度为1.25。

### 回答3：
根据给定的关键字序列{29,01,13,15,56,20,87,27,69,9,10,74} 和散列函数H(key)=key % 17，我们需要构造一个散列表。散列地址空间为0到18。

首先，我们将关键字29进行散列，计算得到散列地址为H(29)=29%17=12。此时，散列地址12为空，我们直接将关键字29存放在散列地址为12的位置上。

接下来，处理关键字01，计算得到散列地址H(01)=01%17=1。此时散列地址1已经被占用，发生了冲突。由于采用线性探测法，我们需要从当前位置开始逐个探查下一个位置，直到找到一个空闲的位置。依次探查位置为2、3、4...，直到找到散列地址为5的空闲位置，将关键字01存放在散列地址5。

按照上述方法，依次处理剩余的关键字。计算得到散列地址序列为：
{12, 5, 13, 15, 5, 3, 3, 10, 4, 9, 10, 0}

完成散列表的构建后，我们计算成功查找的平均查找长度（ASL）。ASL的计算公式为：
ASL = (查找长度1 + 查找长度2 + … + 查找长度n) / 关键字个数

我们假设要查找的关键字序列为{29, 01, 13, 15, 56, 20, 87, 27, 69, 9, 10, 74}。

首先，查找关键字29，它的散列地址为12，经过1次查找就找到了。查找长度为1。
然后，查找关键字01，它的散列地址为5，经过1次查找就找到了。查找长度为1。
依次类推，我们可以得到每个关键字的查找长度。

最后，将所有关键字的查找长度相加并除以关键字个数，即可得到成功查找的平均查找长度。