将关键字序列 { 7,8,30,11,18,9,14 },散列存储到散列列表中,散列表的存储空间是一个下标从 0 开始的一维数组。处理冲突采用线性探测法。散列函数为 h(key)=(key×3)% 表长,要求装入因子为 0.7。则成功查找的平均查找长度为 __
时间: 2023-05-31 07:20:59 浏览: 458
### 回答1:
根据装入因子为.7,散列表的长度应该为10,即能存储7个关键字。
散列函数为h(key)=(key×3)%表长,将关键字序列散列存储到散列列表中:
h(7)=(7×3)%10=1,散列到下标为1的位置
h(8)=(8×3)%10=4,散列到下标为4的位置
h(30)=(30×3)%10=,散列到下标为的位置
h(11)=(11×3)%10=3,散列到下标为3的位置
h(18)=(18×3)%10=4,发生冲突,线性探测到下标为5的位置
h(9)=(9×3)%10=7,散列到下标为7的位置
h(14)=(14×3)%10=2,散列到下标为2的位置
散列列表为:{30, 7, 14, 11, 18, 9, 8, null, null, null}
成功查找的平均查找长度为:
(1×1 + 4×1 + ×1 + 3×1 + (4+1)×1 + 7×1 + 2×1) / 7 = 3
因此,成功查找的平均查找长度为3。
### 回答2:
将关键字序列 { 7,8,30,11,18,9,14 } 散列存储到散列列表中,需要先确定散列表的大小,以便计算装入因子。根据题目要求,采用线性探测法,散列函数为 h(key)=(key×3)%表长,可知表长为:
表长 = 散列成功存储关键字的数量 / 装入因子
表长 = ceil(7 / 0.7)
表长 = 10
于是散列表的空间就是一个下标从 0 开始,长度为 10 的一维数组。
现在开始散列存储。对于每个关键字,先计算出其散列地址,如果该地址已经被占用,就采用线性探测法在散列表中依次向后查找,直到找到空位置为止。具体操作如下:
1. 将 7 存储到散列表中,计算其散列地址为 h(7) = (7×3) % 10 = 1,将其存储到下标为 1 的位置处;
2. 将 8 存储到散列表中,计算其散列地址为 h(8) = (8×3) % 10 = 4,将其存储到下标为 4 的位置处;
3. 将 30 存储到散列表中,计算其散列地址为 h(30) = (30×3) % 10 = 0,将其存储到下标为 0 的位置处;
4. 将 11 存储到散列表中,计算其散列地址为 h(11) = (11×3) % 10 = 7,将其存储到下标为 7 的位置处;
5. 将 18 存储到散列表中,计算其散列地址为 h(18) = (18×3) % 10 = 4,由于下标为 4 的位置已经被占用,采用线性探测法,依次查找下标为 5、6、7、8、9 的位置,直到找到空位置下标为 2,将其存储到下标为 2 的位置处;
6. 将 9 存储到散列表中,计算其散列地址为 h(9) = (9×3) % 10 = 7,由于下标为 7 的位置已经被占用,采用线性探测法,依次查找下标为 8、9、0、1 的位置,由于这些位置都被占用,将会回到起始位置,继续查找下标为 2、3、4 的位置,最终找到下标为 3 的空位置,将其存储到下标为 3 的位置处;
7. 将 14 存储到散列表中,计算其散列地址为 h(14) = (14×3) % 10 = 2,将其存储到下标为 2 的位置处。
现在散列表中的数据为:
0: 30
1: 7
2: 14
3: 9
4: 8
5:
6:
7: 11
8:
9: 18
其中空位置用空格表示。
接下来计算成功查找的平均查找长度。对于每个关键字的查找,从其散列地址开始,依次查找散列表中的位置,直到找到该关键字或者找到一个空位置。假设每个关键字的查找次数为 x,那么成功查找的平均查找长度为所有关键字的查找次数之和除以成功查找的关键字数目。即:
成功查找的平均查找长度 = 所有关键字的查找次数之和 / 成功查找的关键字数目
现在依次对每个关键字进行查找:
1. 查找 7,其散列地址为 1,查找次数为 1;
2. 查找 8,其散列地址为 4,查找次数为 1;
3. 查找 30,其散列地址为 0,查找次数为 1;
4. 查找 11,其散列地址为 7,由于下标为 7 的位置存储的是 9,于是向下查找,查找到下标为 8 的位置为空,查找次数为 2;
5. 查找 18,其散列地址为 4,由于下标为 4 的位置存储的是 8,于是向下查找,查找到下标为 5 的位置为空,查找次数为 2;
6. 查找 9,其散列地址为 7,查找次数为 1;
7. 查找 14,其散列地址为 2,查找次数为 1。
所有关键字的查找次数之和为:1 + 1 + 1 + 2 + 2 + 1 + 1 = 9
成功查找的关键字数目为 7,因为散列表中共有 7 个关键字。因此,成功查找的平均查找长度为:
成功查找的平均查找长度 = 所有关键字的查找次数之和 / 成功查找的关键字数目
成功查找的平均查找长度 = 9 / 7
成功查找的平均查找长度 ≈ 1.29
因此,成功查找的平均查找长度为约 1.29。
### 回答3:
散列存储是一种通过散列函数将数据存储到一定范围内的连续地址上,以提高数据访问速度的存储方式。将关键字序列 { 7,8,30,11,18,9,14 } 散列存储到散列列表中,散列表的存储空间是一个下标从 0 开始的一维数组。处理冲突采用线性探测法。散列函数为 h(key)=(key×3)%表长,要求装入因子为 0.7。则成功查找的平均查找长度为:
1. 计算表长
由于要求装入因子为 0.7,故需要表长为(7/0.7=10)。所以,散列表的存储空间为一个长度为 10 的一维数组。
2. 散列存储
根据散列函数,计算关键字在散列表中的存储地址:
h(7) = (7×3) % 10 = 1
h(8) = (8×3) % 10 = 4
h(30) = (30×3) % 10 = 0
h(11) = (11×3) % 10 = 9
h(18) = (18×3) % 10 = 6
h(9) = (9×3) % 10 = 7
h(14) = (14×3) % 10 = 2
然后,将关键字序列 { 7,8,30,11,18,9,14 } 散列存储到散列表中:
[30, 7, 14, 11, 18, 8, 9, _, _, _]
下划线表示空闲单元格。
3. 查找关键字
假设要查找的关键字为 18,其散列地址为 6。在散列表中的单元格 6 已经存储了关键字 18。查找成功,平均查找长度为 1。
4. 成功查找的平均查找长度
根据线性探测法,平均查找长度为 1/(1-α/2)。其中,α=装入因子=7/10=0.7。带入公式,可得:
平均查找长度 = 1 / (1-0.7/2) = 1 / 0.65 ≈ 1.538
故,成功查找的平均查找长度为约 1.538。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)