首页 › 题库 › C/C++编程考级 › C/C++编程六级 › 简答题
简答题 偏难
#13154

整型关键字的平方探测法散列 本题的任务很简单:将给定的无重复正整数序列插入一个散列表,输出每个输入的数字在表中的位置。所用的散列函数是 H(key) = key…

整型关键字的平方探测法散列

本题的任务很简单:将给定的无重复正整数序列插入一个散列表,输出每个输入的数字在表中的位置。所用的散列函数是 H(key) = key % TSize,其中 TSize 是散列表的表长。要求用平方探测法(只增不减,即H(Key)+i2)解决冲突。

注意散列表的表长最好是个素数。如果输入给定的表长不是素数,你必须将表长重新定义为大于给定表长的最小素数。

时间限制:4000,内存限制:65536

输入

首先第一行给出两个正整数 MSize(≤ 10^4)和 N(≤ MSize),分别对应输入的表长和输入数字的个数。

随后第二行给出 N 个不重复的正整数,数字间以空格分隔。

输出

在一行中按照输入的顺序给出每个数字在散列表中的位置(下标从 0 开始)。如果某个数字无法插入,就在其位置上输出 -。输出间以 1 个空格分隔,行首尾不得有多余空格。

样例输入

4 4
10 6 4 15

样例输出

0 1 4 -
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//该答案由AI生成 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;cmath&gt; using namespace std; bool isPrime(int num) {     if (num &lt;= 1) return false;     if (num == 2) return true;     if (num % 2 == 0) return false;     for (int i = 3; i &lt;= sqrt(num); i += 2) {         if (num % i == 0) return false;     }     return true; } int nextPrime(int n) {     if (n &lt;= 1) return 2;     int prime = n;     bool found = false;     while (!found) {         prime++;         if (isPrime(prime)) found = true;     }     return prime; } int main() {     int MSize, N;     cin &gt;&gt; MSize &gt;&gt; N;          int TSize = MSize;     if (!isPrime(TSize)) {         TSize = nextPrime(MSize);     }          vector&lt;int&gt; hashTable(TSize, -1);     vector&lt;string&gt; results;          for (int idx = 0; idx &lt; N; idx++) {         int key;         cin &gt;&gt; key;                  bool inserted = false;         for (int i = 0; i &lt; TSize; i++) {             int pos = (key % TSize + i * i) % TSize;             if (hashTable[pos] == -1) {                 hashTable[pos] = key;                 results.push_back(to_string(pos));                 inserted = true;                 break;             }         }         if (!inserted) {             results.push_back("-");         }     }          for (int i = 0; i &lt; results.size(); i++) {         if (i &gt; 0) cout &lt;&lt; " ";         cout &lt;&lt; results[i];     }     cout &lt;&lt; endl;          return 0; }</pre>
这道题暂未补解析。