北京门户网站建设公司,wordpress模板 科技,国家乡村振兴局,免费做网站推荐哈希表的平均查找长度是#xff08;#xff09;的函数。 A.哈希表的长度 B.哈希表的装填因子 C.哈希函数 D.表中元素的多少 装填因子 关键字个数 / 表长
符号表#xff1a;是 “名字#xff08;Name#xff09;–属性#xff08;Attribute#xff09;”对的集合 符号表… 哈希表的平均查找长度是的函数。 A.哈希表的长度 B.哈希表的装填因子 C.哈希函数 D.表中元素的多少 装填因子 关键字个数 / 表长
符号表是 “名字Name–属性Attribute”对的集合 符号表也叫散列表哈希表
散列是一种重要的查找方法
它的基本思想是以数据对象的关键字key为自变量通过一个确定的函数关系h计算出 对应的函数值h(key)把这个值解释为数据对象的存储地址并按此存放即“存储位置h(key)”
散列方法中使用的计算函数称为**“散列函数/哈希函数”** 按这个思想构造的表称为散列表
散列函数的构造方法 数字关键词的散列函数构造
直接定址法h(key)a*keyb除留余数法:h(key)key mod p数字分析法
字符串关键词的散列函数构造
处理冲突的方法
开放地址法
线性探测法 冲突发生时顺序查看表中下一单元直到找出一个空单元或查遍全表 二次探测法 冲突发生时在表的左右进行跳跃式探测比较灵活
采用开放定址法处理冲突中的二次探测再散列也即是题目中的二元探测法,则哈希函数变为Hash(key (Hash(key) d) % 11其中d 12, -12, 22, -22, 32,……则开始计算。
分离链接法 其做法就是将散列到同一个值的所有元素保存到一个表中。 双散列探测方法 对于使用平方探测的开放定址散列法当元素填得太满的时候操作运行的时间将消耗过长而且插入操作有可能失败此时则可以进行一次再散列来解决这一问题。
再散列会创建一个新的散列表新的散列表大小为大于原散列表大小2倍的第一个素数随后将原散列表的值重新散列至新的散列表中。 假定有K个关键字互为同义词若用线性探测法把这K个关键字存入散列表中至少要进行多少次探测 A.K−1 B.K C.K1 D.K(K1)/2 从一个具有N个结点的单链表中查找其值等于X的结点时在查找成功的情况下需平均比较多少个结点 A.N/2 B.N C.(N−1)/2 D.(N1)/2 由于单链表只能进行单向顺序查找以从第一个节点开始查找为例查找第m个节点需要比较的节点数f(m)m查找成功的最好情况是第一次就查找成功只用比较1个节点最坏情况则是最后才查找成功需要比较n个节点。
所以一共有n种情况平均下来需要比较的节点为(123…(n-1)n)/n(n1)/2。 下面关于哈希查找的说法不正确的是 。 A.采用链地址法处理冲突时查找一个元素的时间是相同的 B.采用链地址法处理冲突时若插入规定总是在链首则插入任一个元素的时间是相同的 C.用链地址法处理冲突不会引起二次聚集现象 D.用链地址法处理冲突适合表长不确定的情况
