刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！
简答题
4.散列表平均查找时间
本题目标很简单：首先将一系列各不相同的正整数键值插入一张散列表，随后在表中查找另外给定的一个整数键值系列，输出平均查找时间（确定一个数字在或不在表中所需要比较的次数）。这里用到的哈希函数定义为 H(key) = key % TSize，其中 TSize 是散列表的容量。使用平方探测（仅做正向递增的探测）来解决冲突。
注意散列表的容量最好是一个素数。如果用户给出的容量不是素数，你必须将容量重新定义为比用户给定容量大的一个最小的素数。
时间限制：1000
内存限制：65536
输入
输入第一行给出 3 个正整数：MSize、N、M，分别是用户定义的散列表容量、要插入的键值的数量、以及要查找的键值的数量。这 3 个数都不超过 104。 随后第二行给出 N 个各不相同的正整数键值待插入。第三行给出 M 个正整数键值待查找。同一行中数字间以一个空格分隔，数均不超过 105。
输出
如果某个数无法插入，则在一行中输出 `X cannot be inserted.`，其中 `X` 是那个输入的数字。最后一行输出全部 M 个键值的平均查找时间，精确到小数点后 1 位。
样例输入
4 5 4
10 6 4 15 11
11 4 15 2
样例输出
15 cannot be inserted.
2.8
本题目标很简单：首先将一系列各不相同的正整数键值插入一张散列表，随后在表中查找另外给定的一个整数键值系列，输出平均查找时间（确定一个数字在或不在表中所需要比较的次数）。这里用到的哈希函数定义为 H(key) = key % TSize，其中 TSize 是散列表的容量。使用平方探测（仅做正向递增的探测）来解决冲突。
注意散列表的容量最好是一个素数。如果用户给出的容量不是素数，你必须将容量重新定义为比用户给定容量大的一个最小的素数。
时间限制：1000
内存限制：65536
输入
输入第一行给出 3 个正整数：MSize、N、M，分别是用户定义的散列表容量、要插入的键值的数量、以及要查找的键值的数量。这 3 个数都不超过 104。 随后第二行给出 N 个各不相同的正整数键值待插入。第三行给出 M 个正整数键值待查找。同一行中数字间以一个空格分隔，数均不超过 105。
输出
如果某个数无法插入，则在一行中输出 `X cannot be inserted.`，其中 `X` 是那个输入的数字。最后一行输出全部 M 个键值的平均查找时间，精确到小数点后 1 位。
样例输入
4 5 4
10 6 4 15 11
11 4 15 2
样例输出
15 cannot be inserted.
2.8
使用微信搜索喵呜刷题，轻松应对考试！
答案：
解析：
这个问题需要实现一个散列表，包括插入和查找操作。首先，需要根据给定的MSize来初始化散列表，如果MSize不是素数，则需要找到一个比它大的最小素数作为实际的散列表容量TSize。然后，使用给定的哈希函数H(key) = key % TSize来将键值插入到散列表中。如果发生哈希冲突（即两个键值哈希到同一位置），则使用平方探测法来解决冲突。插入完所有的键值后，对于每一个查找的键值，在散列表中查找，并统计查找的次数。最后计算平均查找时间，并输出结果。注意处理无法插入的情况，当某个数无法插入时，输出相应提示信息。
创作类型：
原创
本文链接：4.散列表平均查找时间本题目标很简单：首先将一系列各不相同的正整数键值插入一张散列表，随后在表中查找
版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！
分享考题 
