现有长度为 7、初始为空的散列表ht，散列函数h(k)=k%7，用线性探测再散列法解决冲突。将关键字 22, 43, 15 依次插入到ht后，查找成功的平均查找长度是：

根据线性探测再散列法，当发生冲突时，我们会依次检查散列表中下一个位置，直到找到一个空位置为止。因此，插入关键字 22 时，它会被散列到位置 1，插入关键字 43 时，它会被散列到位置 1 的下一个位置 2，插入关键字 15 时，它会被散列到位置 1 的下两个位置 3。

现在，我们来计算查找成功的平均查找长度。对于每个关键字，我们需要计算它在散列表中的查找长度，然后将这些长度相加并除以关键字的总数。具体地，对于关键字 22，它在散列表中的查找长度为 1；对于关键字 43，它在散列表中的查找长度为 2；对于关键字 15，它在散列表中的查找长度为 3。因此，关键字的总数为 3，它们在散列表中的查找长度之和为 1+2+3=6。因此，查找成功的平均查找长度为 6/3=2。

因此，插入关键字 22, 43, 15 后，查找成功的平均查找长度是 2。

相关问题

现有长度为 11 且初始为空的散列表 ht，散列函数是 h(key)=key%7，采用线性探查（线性探测再散列）法解决冲突。将关键字序列 87,40,30,6,11,22,98,20 依次插入到 ht 后，ht 查找失败的平均查找长度是：

根据线性探查法，当发生冲突时，会依次往后查找空闲位置，直到找到空闲位置或者查找到整个散列表。因此，插入的顺序会影响散列表的填充情况，从而影响查找的效率。

根据给定的散列函数 h(key)=key%7，将关键字序列依次插入到散列表 ht 中，得到如下填充情况：

ht[6] = 87
ht[5] = 40
ht[2] = 30
ht[6] 已经被占用，因此线性探查到下一个位置 ht[]
ht[] = 6
ht[4] = 11
ht[1] = 22
ht[] 已经被占用，因此线性探查到下一个位置 ht[1]
ht[1] 已经被占用，因此线性探查到下一个位置 ht[2]
ht[3] = 98
ht[6] 已经被占用，因此线性探查到下一个位置 ht[3]
ht[3] 已经被占用，因此线性探查到下一个位置 ht[4]
ht[4] 已经被占用，因此线性探查到下一个位置 ht[5]
ht[5] 已经被占用，因此线性探查到下一个位置 ht[6]
ht[] 已经被占用，因此线性探查到下一个位置 ht[1]
ht[1] 已经被占用，因此线性探查到下一个位置 ht[2]
ht[2] 已经被占用，因此线性探查到下一个位置 ht[3]
ht[3] 已经被占用，因此线性探查到下一个位置 ht[4]
ht[4] 已经被占用，因此线性探查到下一个位置 ht[5]
ht[5] 已经被占用，因此线性探查到下一个位置 ht[6]
ht[6] 已经被占用，因此线性探查到下一个位置 ht[]
ht[] 已经被占用，因此线性探查到下一个位置 ht[1]
ht[1] 已经被占用，因此线性探查到下一个位置 ht[2]
ht[2] 已经被占用，因此线性探查到下一个位置 ht[3]
ht[3] 已经被占用，因此线性探查到下一个位置 ht[4]
ht[4] 已经被占用，因此线性探查到下一个位置 ht[5]
ht[5] 已经被占用，因此线性探查到下一个位置 ht[6]
ht[6] 已经被占用，因此线性探查到下一个位置 ht[]
ht[] 已经被占用，因此线性探查到下一个位置 ht[1]
ht[1] 已经被占用，因此线性探查到下一个位置 ht[2]
ht[2] 已经被占用，因此线性探查到下一个位置 ht[3]
ht[3] 已经被占用，因此线性探查到下一个位置 ht[4]
ht[4] 已经被占用，因此线性探查到下一个位置 ht[5]
ht[5] 已经被占用，因此线性探查到下一个位置 ht[6]
ht[6] 已经被占用，因此线性探查到下一个位置 ht[]
ht[] 已经被占用，因此线性探查到下一个位置 ht[1]
ht[1] 已经被占用，因此线性探查到下一个位置 ht[2]
ht[2] 已经被占用，因此线性探查到下一个位置 ht[3]
ht[3] 已经被占用，因此线性探查到下一个位置 ht[4]
ht[4] 已经被占用，因此线性探查到下一个位置 ht[5]
ht[5] 已经被占用，因此线性探查到下一个位置 ht[6]
ht[6] 已经被占用，因此线性探查到下一个位置 ht[]
ht[] 已经被占用，因此线性探查到下一个位置 ht[1]
ht[1] 已经被占用，因此线性探查到下一个位置 ht[2]
ht[2] 已经被占用，因此线性探查到下一个位置 ht[3]
ht[3] 已经被占用，因此线性探查到下一个位置 ht[4]
ht[4] 已经被占用，因此线性探查到下一个位置 ht[5]
ht[5] 已经被占用，因此线性探查到下一个位置 ht[6]

最终的散列表 ht 如下：

ht[] = 6
ht[1] = 22
ht[2] = 30
ht[3] = 98
ht[4] = 11
ht[5] = 40
ht[6] = 87

平均查找长度 = 所有查找失败的情况下，查找次数的总和 / 查找失败的次数

对于给定的关键字序列，查找失败的情况有两种：

1. 要查找的关键字不在散列表中，需要查找整个散列表，查找次数为散列表的长度 11。
2. 要查找的关键字在散列表中，但是被其他关键字占用了位置，需要依次查找下一个位置，直到找到空闲位置或者查找到整个散列表。假设散列表中已经填充了 k 个关键字，则查找次数的期望为 (1/2) * (1 + 1/2 + ... + 1/(k+1))，其中 1/2 是因为每次查找有一半的概率需要继续查找下一个位置，1/(k+1) 是因为最多需要查找 k+1 个位置才能找到空闲位置。根据等差数列求和公式，可以得到 (1/2) * (1 + 1/2 + ... + 1/(k+1)) = (k+3)/(2*(k+1))。

因此，平均查找长度 = (11 + (1/2)*(4/3 + 5/4 + 6/5 + 7/6 + 8/7 + 9/8 + 10/9 + 11/10)) / 8 ≈ 2.59。

已知散列表的地址区问为0~10,散列函数为 H(K=k% 11,采用线性探测法处理冲突。 ,设计算法在其 中查找值为x的元素,若查找成功,返回其下标,否则返回一1。

算法如下：

1. 根据散列函数 H(K) = k % 11 计算出要查找元素 x 的散列地址 h。

2. 如果散列表中第 h 个位置存放的元素就是 x，则返回 h。

3. 如果第 h 个位置为空，则说明散列表中没有 x 这个元素，返回 -1。

4. 如果第 h 个位置存放的元素不是 x，则向后依次查找下一个位置，直到找到一个空位置或者找到了 x。

5. 如果找到了 x，则返回其下标；如果找到了空位置，则说明散列表中没有 x 这个元素，返回 -1。

算法实现的代码如下：

int linear_probe_search(int* hash_table, int x) {
    int h = x % 11;  // 计算散列地址
    while (hash_table[h] != -1) {
        if (hash_table[h] == x)  // 找到了 x
            return h;
        h = (h + 1) % 11;  // 继续查找下一个位置
    }
    return -1;  // 散列表中没有 x 这个元素
}

其中，散列表的初始值全部设为 -1，表示该位置为空。