简答题
偏难
#13205
散列表平均查找时间 本题目标很简单:首先将一系列各不相同的正整数键值插入一张散列表,随后在表中查找另外给定的一个整数键值系列,输出平均查找时间(确定一个数字在或…
散列表平均查找时间
本题目标很简单:首先将一系列各不相同的正整数键值插入一张散列表,随后在表中查找另外给定的一个整数键值系列,输出平均查找时间(确定一个数字在或不在表中所需要比较的次数)。这里用到的哈希函数定义为 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
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考程序1
#include <iostream>
#include <vector>
#include <iomanip>
// 找到比给定数大的最小素数
int nextPrime(int num) {
if (num <= 2) return 2;
if (num % 2 == 0) num++;
while (true) {
bool isPrime = true;
for (int i = 3; i * i <= num; i += 2) {
if (num % i == 0) {
isPrime = false;
break;
}
}
if (isPrime) break;
num += 2;
}
return num;
}
int main() {
int mSize, n, m;
std::cin >> mSize >> n >> m;
mSize = nextPrime(mSize);
std::vector<int> hashTable(mSize, -1);
// 插入键值
for (int i = 0; i < n; ++i) {
int key;
std::cin >> key;
int hash = key % mSize;
bool inserted = false;
for (int j = 0; j < mSize; ++j) {
int index = (hash + j * j) % mSize;
if (hashTable[index] == -1) {
hashTable[index] = key;
inserted = true;
break;
}
}
if (!inserted) {
std::cout << key << " cannot be inserted." << std::endl;
}
}
// 查找键值
int totalSearchTime = 0;
for (int i = 0; i < m; ++i) {
int key;
std::cin >> key;
int hash = key % mSize;
for (int j = 0; j <= mSize; ++j) {
totalSearchTime++;
int index = (hash + j * j) % mSize;
if (hashTable[index] == key || hashTable[index] == -1) {
break;
}
}
}
// 输出平均查找时间
double averageSearchTime = static_cast<double>(totalSearchTime) / m;
std::cout << std::fixed << std::setprecision(1) << averageSearchTime << std::endl;
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//参考程序2
#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>
using namespace std;
bool isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) return false;
}
return true;
}
int getTSize(int m) {
if (isPrime(m)) return m;
int t = m + 1;
while (true) {
if (isPrime(t)) return t;
++t;
}
}
int main() {
int MSize, N, M;
cin >> MSize >> N >> M;
int TSize = getTSize(MSize);
vector<int> hashTable(TSize, -1); // -1表示空位置
// 插入元素到哈希表
vector<bool> insertedKeys(N);
for (int i = 0; i < N; ++i) {
int key;
cin >> key;
int h = key % TSize;
bool inserted = false;
for (int j = 0; j < TSize; ++j) {
int pos = (h + j * j) % TSize;
if (hashTable[pos] == -1) {
hashTable[pos] = key;
inserted = true;
break;
}
}
if (!inserted) {
cout << key << " cannot be inserted." << endl;
}
}
// 计算平均查找时间
double total = 0.0;
for (int i = 0; i < M; ++i) {
int key;
cin >> key;
int h = key % TSize;
int count = 0;
for (int j = 0; j < TSize; ++j) {
++count;
int pos = (h + j * j) % TSize;
if (hashTable[pos] == -1) {
break;
} else if (hashTable[pos] == key) {
break;
}
}
total += count;
}
double avg = total / M;
cout << fixed << setprecision(1) << avg << endl;
return 0;
}</pre><p><br/></p>
这道题暂未补解析。