首页 > 试题广场 >

对包含n个元素的散列表进行检索,平均检索长度()

[单选题]

对包含n个元素的散列表进行检索,平均检索长度()

  • O(log(2n))
  • O(n)
  • O(nlog(2n))
  • 不直接依赖于n
推荐
D
散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
查找过程中,关键码的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高,产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。影响产生冲突多少有以下三个因素:
  • 散列函数是否均匀;
  • 处理冲突的方法;
  • 散列表的装填因子(即填入表中的元素个数 / 散列表的长度)。由于表长是定值,装填因子与"填入表中的元素个数"成正比,所以,装填因子越大,填入表中的元素较多,产生冲突的可能性就越大;装填因子越小,填入表中的元素较少,产生冲突的可能性就越小。
编辑于 2019-12-04 14:31:44 回复(0)
D
散列表是线性表查找的一种方法。这种方法的一个特点是,平均检索长度不直接依赖于元素的个数。元素的个数增加,其平均检索长度并不增加,而与负载因子有关。所以,本题的答案是D。
发表于 2019-12-03 16:42:45 回复(0)
D
散列底层数据结构是哈希表,哈希表的时间复杂度是O(1),意思是与数据量无关。
发表于 2019-12-03 15:24:17 回复(0)
装填因子
发表于 2022-10-22 17:50:39 回复(0)
题目不够严谨,严格说来,B不算错
发表于 2021-12-28 17:12:28 回复(0)

D


发表于 2019-04-24 12:45:24 回复(0)
B
发表于 2018-08-30 09:04:43 回复(0)