练习题题目

练习题答案 · 上篇（第1~8题）

来源：练习题.docx · 代码紧凑含关键注释，可直接复制到 Dev-C++ 运行。

第1题 出现次数最多的数

【题目】给定n个整数，找出出现次数最多的数；次数相同则输出数值最小的。

【参考代码】

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
int main() {
int n; cin >> n;
map<int,int> cnt; //统计频次
while (n--) { int x; cin >> x; cnt[x]++; }
int best = cnt.begin()->first, mx = 0;
for (auto &p : cnt)
if (p.second > mx || (p.second == mx && p.first < best))
mx = p.second, best = p.first;
cout << best << endl;
return 0;
}

第2题 相反数统计

【题目】n个互不相同整数，统计有多少对互为相反数。

【参考代码】

#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
int n; cin >> n;
unordered_set<int> s;
for (int i = 0, x; i < n; i++) { cin >> x; s.insert(x); }
int ans = 0;
for (int x : s) if (x != 0 && s.count(-x)) ans++;
cout << ans / 2 << endl; //每对计两次，除2
return 0;
}

第3题 相邻数对

【题目】n个互不相同整数，统计差的绝对值为1的数对个数。

【参考代码】

#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
int n; cin >> n;
unordered_set<int> s;
for (int i = 0, x; i < n; i++) { cin >> x; s.insert(x); }
int ans = 0;
for (int x : s) if (s.count(x + 1)) ans++; //只统计x < x+1
cout << ans << endl;
return 0;
}

第4题 数字频率排序

【题目】按出现次数从大到小输出每个不同整数及次数；次数相同则整数小的先输出。

【参考代码】

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n; cin >> n;
map<int,int> cnt;
while (n--) { int x; cin >> x; cnt[x]++; }
vector<pair<int,int>> v(cnt.begin(), cnt.end());
sort(v.begin(), v.end(), [](auto &a, auto &b) {
if (a.second != b.second) return a.second > b.second;
return a.first < b.first;
});
for (auto &p : v) cout << p.first << " " << p.second << endl;
return 0;
}

第5题 有序数组查找

【题目】递增数组，m次查询，用折半查找判断x是否存在，输出YES/NO。

【参考代码】

#include <iostream>
#include <vector>
using namespace std;
bool binSearch(const vector<int> &a, int x) {
int l = 0, r = (int)a.size() - 1;
while (l <= r) {
int m = (l + r) / 2;
if (a[m] == x) return true;
if (a[m] < x) l = m + 1; else r = m - 1;
}
return false;
}
int main() {
int n, m; cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
while (m--) {
int x; cin >> x;
cout << (binSearch(a, x) ? "YES" : "NO") << endl;
}
return 0;
}

第6题 线性探测哈希表

【题目】H(x)=x mod p，线性探测插入，输出p个位置，空位-1。

【参考代码】

#include <iostream>
#include <vector>
using namespace std;
int main() {
int p, n; cin >> p >> n;
vector<int> h(p, -1);
while (n--) {
int x; cin >> x;
int pos = x % p;
while (h[pos] != -1) pos = (pos + 1) % p; //线性探测
h[pos] = x;
}
for (int i = 0; i < p; i++) {
if (i) cout << " ";
cout << h[i];
}
cout << endl;
return 0;
}

第7题 平方探测哈希表

【题目】H(x)=x mod p，平方探测(+1²,-1²,+2²,-2²…)，输出每个数最终插入位置，失败-1。

【参考代码】

#include <iostream>
#include <vector>
using namespace std;
int main() {
int p, n; cin >> p >> n;
vector<int> h(p, -1);
while (n--) {
int x; cin >> x;
int pos = -1;
int home = x % p;
for (int i = 0; i < p; i++) {
int d = (i % 2 ? -1 : 1) * ((i + 1) / 2);
d = (d * d) % p;
int t = (home + d) % p; if (t < 0) t += p;
if (h[t] == -1) { h[t] = x; pos = t; break; }
}
cout << pos << endl;
}
return 0;
}

第8题 单词去重

【题目】n个单词，大小写敏感，输出不同单词个数。

【参考代码】

#include <iostream>
#include <set>
#include <string>
using namespace std;
int main() {
int n; cin >> n;
set<string> st;
while (n--) { string w; cin >> w; st.insert(w); }
cout << st.size() << endl;
return 0;
}