作业帮数据结构求 ASL 平均搜索长度 急
来源：学生作业帮 编辑：作业帮 分类：数学作业 时间：2024/05/12 12:40:28
数据结构求 ASL 平均搜索长度 急
设散列表的长度m=13：散列函数为 H（K）=K mod m,给定的关键码序列为19、1、23、14、68、20、84、27、77、11,试画出用线性探查法解决冲突时所构造的散列表.并求出在等概率的情况下,这种方法的搜索成功时的平均搜索长度?
设散列表的长度m=13：散列函数为 H（K）=K mod m,给定的关键码序列为19、1、23、14、68、20、84、27、77、11,试画出用线性探查法解决冲突时所构造的散列表.并求出在等概率的情况下,这种方法的搜索成功时的平均搜索长度?
不知道你说的是什么平均查找长度,一般考试会考哈希表的,因为其他的更简单.
对于含有n个数据元素的查找表,查找成功的平均查找长度为：ASL=∑PiCi (i=1,2,3,…,n).其中：Pi 为查找表中第i个数据元素的概率,Ci为找到第i个数据元素时已经比较过的次数.
已知一个待散列存储的线性表为(38,25,74,63,52,48),散列函数为H(k)=k mod 7,若采用线性探测的开放地址法处理冲突,则平均查找长度为：
ASL=p1c1+p2c2+p3c3+.
也可以表示为
ASL=1/n(c1+c2+c3+.)
其中c是每个数查询的次数
按照H（K）=k mod 7得：
38----1
25----1
74----2
63----1
52----4
48----3
所以ASL=1/6（1+1+2+1+4+3）=2
对于含有n个数据元素的查找表,查找成功的平均查找长度为：ASL=∑PiCi (i=1,2,3,…,n).其中：Pi 为查找表中第i个数据元素的概率,Ci为找到第i个数据元素时已经比较过的次数.
已知一个待散列存储的线性表为(38,25,74,63,52,48),散列函数为H(k)=k mod 7,若采用线性探测的开放地址法处理冲突,则平均查找长度为：
ASL=p1c1+p2c2+p3c3+.
也可以表示为
ASL=1/n(c1+c2+c3+.)
其中c是每个数查询的次数
按照H（K）=k mod 7得：
38----1
25----1
74----2
63----1
52----4
48----3
所以ASL=1/6（1+1+2+1+4+3）=2