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

时间: 2024-02-29 13:56:57 浏览: 15
根据题意,我们可以按照以下步骤构造散列表: 1. 创建一个大小为 19 的散列表,其中下标为 0 到 18。 2. 对于每个关键字 key,计算其散列地址 h = key % 17,如果该地址已经被占用,则使用平方探测方法探测下一个地址,直到找到一个空闲位置为止。 3. 将该关键字存储在散列表中对应的位置。 按照上述方法,我们可以得到以下散列表: ``` 0: 01 1: 27 2: 15 3: 74 4: 56 5: 20 6: 87 7: 29 8: 9: 9 10: 10 11: 69 12: 13 13: 14: 15: 16: 17: 18: ``` 其中,关键字 29、27、13、15、56、20、87、01、9、10、74 分别被散列到了下标为 7、1、12、3、4、5、6、0、9、10、3 的位置。注意,有些地址上出现了冲突,需要使用平方探测方法找到下一个空闲位置。 成功查找的平均查找长度是指在散列表中查找一个已知的关键字时,平均需要比较的次数。它可以通过以下公式计算: ``` 平均查找长度 = 所有关键字的查找长度之和 / 关键字总数 ``` 在本例中,共有 12 个关键字需要查找。我们可以分别计算出这些关键字在散列表中的查找长度,然后求和并除以 12,即可得到平均查找长度。 关键字 29 在下标为 7 处,查找长度为 1。 关键字 01 在下标为 0 处,查找长度为 1。 关键字 13 在下标为 12 处,查找长度为 1。 关键字 15 在下标为 3 处,查找长度为 1。 关键字 56 在下标为 4 处,查找长度为 1。 关键字 20 在下标为 5 处,查找长度为 1。 关键字 87 在下标为 6 处,查找长度为 1。 关键字 27 在下标为 1 处,查找长度为 1。 关键字 69 在下标为 11 处,查找长度为 1。 关键字 9 在下标为 9 处,查找长度为 1。 关键字 10 在下标为 10 处,查找长度为 1。 关键字 74 在下标为 3 处,经过 1 次平方探测后查找到,查找长度为 2。 将所有关键字的查找长度之和除以 12,得到: ``` (1+1+1+1+1+1+1+1+1+1+1+2) / 12 = 11 / 12 ≈ 0.917 ``` 因此,成功查找的平均查找长度为约为 0.917。

相关推荐

最新推荐

recommend-type

〖程序设计基础〗练习题2及答案

21. 用于定义类成员的访问控制权的一组关键字是( )。 A) class, float, double, public B) float, boolean, int, long C) char, extends, float, double D) public, private, protected 22. 不能构成循环的语句是( ...
recommend-type

华为OD机试D卷 - 用连续自然数之和来表达整数 - 免费看解析和代码.html

私信博主免费获取真题解析以及代码
recommend-type

Screenshot_2024-05-10-20-21-01-857_com.chaoxing.mobile.jpg

Screenshot_2024-05-10-20-21-01-857_com.chaoxing.mobile.jpg
recommend-type

数字图像处理|Matlab-频域增强实验-彩色图像的频域滤波.zip

数字图像处理|Matlab-频域增强实验-彩色图像的频域滤波.zip
recommend-type

2024-2030中国定向转向膜市场现状研究分析与发展前景预测报告.docx

2024-2030中国定向转向膜市场现状研究分析与发展前景预测报告
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

实现实时数据湖架构:Kafka与Hive集成

![实现实时数据湖架构:Kafka与Hive集成](https://img-blog.csdnimg.cn/img_convert/10eb2e6972b3b6086286fc64c0b3ee41.jpeg) # 1. 实时数据湖架构概述** 实时数据湖是一种现代数据管理架构,它允许企业以低延迟的方式收集、存储和处理大量数据。与传统数据仓库不同,实时数据湖不依赖于预先定义的模式,而是采用灵活的架构,可以处理各种数据类型和格式。这种架构为企业提供了以下优势: - **实时洞察:**实时数据湖允许企业访问最新的数据,从而做出更明智的决策。 - **数据民主化:**实时数据湖使各种利益相关者都可
recommend-type

spring添加xml配置文件

1. 创建一个新的Spring配置文件,例如"applicationContext.xml"。 2. 在文件头部添加XML命名空间和schema定义,如下所示: ``` <beans xmlns="http://www.springframework.org/schema/beans" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.springframework.org/schema/beans
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。