首页 › 题库 › C/C++编程考级 › C/C++编程六级 › 简答题
简答题 偏难
#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 &lt;iostream&gt; #include &lt;vector&gt; #include &lt;iomanip&gt; // 找到比给定数大的最小素数 int nextPrime(int num) {     if (num &lt;= 2) return 2;     if (num % 2 == 0) num++;     while (true) {         bool isPrime = true;         for (int i = 3; i * i &lt;= 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 &gt;&gt; mSize &gt;&gt; n &gt;&gt; m;     mSize = nextPrime(mSize);     std::vector&lt;int&gt; hashTable(mSize, -1);     // 插入键值     for (int i = 0; i &lt; n; ++i) {         int key;         std::cin &gt;&gt; key;         int hash = key % mSize;         bool inserted = false;         for (int j = 0; j &lt; mSize; ++j) {             int index = (hash + j * j) % mSize;             if (hashTable[index] == -1) {                 hashTable[index] = key;                 inserted = true;                 break;             }         }         if (!inserted) {             std::cout &lt;&lt; key &lt;&lt; " cannot be inserted." &lt;&lt; std::endl;         }     }     // 查找键值     int totalSearchTime = 0;     for (int i = 0; i &lt; m; ++i) {         int key;         std::cin &gt;&gt; key;         int hash = key % mSize;         for (int j = 0; j &lt;= mSize; ++j) {             totalSearchTime++;             int index = (hash + j * j) % mSize;             if (hashTable[index] == key || hashTable[index] == -1) {                 break;             }         }     }     // 输出平均查找时间     double averageSearchTime = static_cast&lt;double&gt;(totalSearchTime) / m;     std::cout &lt;&lt; std::fixed &lt;&lt; std::setprecision(1) &lt;&lt; averageSearchTime &lt;&lt; std::endl;     return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考程序2 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;iomanip&gt; #include &lt;cmath&gt; using namespace std; bool isPrime(int n) { if (n &lt;= 1) return false; for (int i = 2; i * i &lt;= 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 &gt;&gt; MSize &gt;&gt; N &gt;&gt; M; int TSize = getTSize(MSize); vector&lt;int&gt; hashTable(TSize, -1); // -1表示空位置 // 插入元素到哈希表 vector&lt;bool&gt; insertedKeys(N); for (int i = 0; i &lt; N; ++i) { int key; cin &gt;&gt; key; int h = key % TSize; bool inserted = false; for (int j = 0; j &lt; TSize; ++j) { int pos = (h + j * j) % TSize; if (hashTable[pos] == -1) { hashTable[pos] = key; inserted = true; break; } } if (!inserted) { cout &lt;&lt; key &lt;&lt; " cannot be inserted." &lt;&lt; endl; } } // 计算平均查找时间 double total = 0.0; for (int i = 0; i &lt; M; ++i) { int key; cin &gt;&gt; key; int h = key % TSize; int count = 0; for (int j = 0; j &lt; 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 &lt;&lt; fixed &lt;&lt; setprecision(1) &lt;&lt; avg &lt;&lt; endl; return 0; }</pre><p><br/></p>
这道题暂未补解析。