GESP-C++七级 题库
以下哪个方案可以合理解决或缓解哈希表冲突( )。
在哈希表中,冲突(也称碰撞)是指两个不同的键被映射到哈希表的同一位置。
A选项,这个方案显然不是一个好的解决策略,因为它会导致信息丢失。如果频繁发生冲突,大量新元素将被丢弃, 哈希表将失去其存储和检索数据的能力。
B选项,这个方案不可取,因为会导致旧元素被覆盖,从而丢失数据。哈希表应该能够可靠地存储和检索每个键对应 的值。
C选项,这个方案不合理,因为没有明确定义“下一个位置”是什么。在哈希表中,冲突位置之后的“下一个位置” 可能仍然是一个冲突位置,或者可能是一个已经存储了其它元素的位置。此外这种策略也没有提供一种系统化的方法 来遍历哈希表中的所有元素。
D选项,这个方案合理,描述了一种称为开放地址法(Open Addressing)的冲突解决策略。在这种方法中,当发生 冲突时,哈希表会尝试在冲突位置的后续位置找到一个空位来存储新元素。
以下哪个方案不能合理解决或缓解哈希表冲突( )。
不能丢弃发生冲突的新元素
以下哪个方案不能合理解决或缓解哈希表冲突( )。
在每个哈希表项处,使用单链表管理该表项的冲突元素。
建立额外的单链表,用来管理所有发生冲突的元素。
使用不同的哈希函数再建立一个哈希表,用来管理所有发生冲突的元素。
用新元素覆盖发生冲突的哈希表项。
哈希表长31,按照下面的程序依次输入 4 17 28 30 4 ,则最后的 4 存入哪个位置?( )

3
4
5
6
对关键字序列 {44,36,23,35,52,73,90,58} 建立哈希表,哈希函数为 h(k)=k%7 ,执行下面的Insert 函数,则等概率情况下的平均成功查找长度(即查找成功时的关键字比较次数的均值)为( )。

7/8
1
1.5
2
使用链地址法处理冲突的哈希表,当所有元素都映射到同一个槽位时,查找操作的最坏时间复杂度为O(n),其中n为元素个数。
C++语言中, float 和 int 类型一般都是 4 字节,因此 float 类型能够表达不同的浮点数值的数量,与 int 类型能够表达不同的整数值的数量是相同的。
使用 math.h 或 cmath 头文件中的对数函数,表达式 log(256) 的结果类型为 double 、值约为 8.0 。
很多游戏中为玩家设置多种可供学习的技能,要学习特定技能又往往需要先学习1个或以上的前置技能。尽管这样的技能间依赖关系常被玩家称为“技能树”,但它并不一定是树,更可能是有向无环图。
MD5是一种常见的哈希函数,可以由任意长度的数据生成128位的哈希值,曾广泛应用于数据完整性校验。
中国科学家的系列工作首次发现了可实用的MD5破解方法。之后,MD5逐渐被其他哈希函数所取代。
某个哈希表键值 x 为整数, H(x) = x % p 是常用的哈希函数之一,要求 p 选择素数是因为这样不会产生冲突。( )
当x是p的倍数是会发送冲突。选择素数作为模数p,可以使哈希函数的值分布更均匀,减少冲突的概率,但不能完全避免冲突。
现使用有 N 个表项的哈希表,从 M 个元素中进行查找。该哈希表为解决哈希函数冲突,为每个表项处建立单链表存储冲突元素。其查找操作的最坏情况时间复杂度为O(M)。
如果M个元素全部冲突,则需要去单链表进行查询,时间复杂度为O(M).
某 N 个表项的哈希表,在发生哈希函数冲突时采用向后寻找空位的方法解决冲突。其查找操作的平均时间复杂度为O(1),即使当该哈希表的每个表项都有元素时,查找操作的平均时间复杂度仍为O(1)。( )