首页 › 题库 › C/C++编程考级 › 6 STL

C/C++编程五级 题库

共 54 道题 ,第 1 / 3 页 · 按题型筛选,点「查看答案」核对解析
1 单选题 适中 C/C++编程考级 ·C/C++编程五级 · 6 STL

以下哪个STL容器是基于红黑树实现的,元素自动有序且不重复?( )

A
vector
B
set
C
queue
D
list
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
2 单选题 适中 C/C++编程考级 ·C/C++编程五级 · 6 STL

STL中,用于在容器中查找指定元素的函数是?( )

A
sort()
B
find()
C
swap()
D
reverse()
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
3 单选题 适中 C/C++编程考级 ·C/C++编程五级 · 6 STL

以下关于`vector`容器的说法,错误的是?( )

A
vector是动态数组,支持动态扩容
B
可以用`push_back()`在数组尾部插入元素
C
可以用`pop_front()`删除数组头部的元素
D
支持下标随机访问
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
4 单选题 适中 C/C++编程考级 ·C/C++编程五级 · 6 STL

以下代码的输出是?( )

set<int> s;
s.insert(5);
s.insert(2);
s.insert(8);
for (int x : s) cout << x <<" ";
A
5 2 8
B
2 5 8
C
8 5 2
D
随机顺序
答案与解析
正确答案:B

C++ 的 set 是有序且元素唯一的容器,默认升序。

题目详情
5 单选题 适中 C/C++编程考级 ·C/C++编程五级 · 6 STL

以下代码的输出是?( )

map<string, int> m;
m["apple"]= 5;
m["banana"] = 3;
cout << m["apple"];
A
0
B
3
C
5
D
编译错误
答案与解析
正确答案:C

map 是 C++ 标准模板库的字典,m["apple"] 的值已经设为 5,输出为:5。

题目详情
6 单选题 适中 C/C++编程考级 ·C/C++编程五级 · 6 STL

查找键 "key" 是否存在,正确的代码是?( )

A
if (m.find("key")!= m.end())
B
if (m["key"]!= 0)
C
if (m.count("key")> 0)
D
A和C
答案与解析
正确答案:D

find() 返回迭代器,如果等于 end() 说明没找到,否则存在。

count() 对于 map 返回 0 或 1,可以判断键是否存在。

题目详情
7 单选题 适中 C/C++编程考级 ·C/C++编程五级 · 6 STL

set 的组织特点是?( )

A
元素有序、可重复
B
元素无序、不重复
C
元素有序、不重复
D
元素无序、可重复
答案与解析
正确答案:C

C++ 中的 set 是基于红黑树实现的有序关联容器,元素有序、不重复。

题目详情
8 判断题 偏易 C/C++编程考级 ·C/C++编程五级 · 6 STL

map 容器存储键值对,键唯一不可重复。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
9 判断题 偏易 C/C++编程考级 ·C/C++编程五级 · 6 STL

`string`类的`c_str()`函数可以将string对象转换为C风格的const char*字符串。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
10 判断题 偏易 C/C++编程考级 ·C/C++编程五级 · 6 STL

map 中的一个键不能对应两组数据。( )

A
对
B
错
答案与解析
正确答案:对

在 C++ 的 map(和 unordered_map)中,每个键只能对应一个值,如果插入相同键的新值,会覆盖旧值。

题目详情
11 判断题 偏易 C/C++编程考级 ·C/C++编程五级 · 6 STL

map 的查找单个键的时间复杂度是 O(log n)。( )

A
对
B
错
答案与解析
正确答案:对

在 C++ 中,map 是基于红黑树(平衡二叉搜索树)实现的,插入、删除、查找操作的时间复杂度都是 O(log n)。

题目详情
12 判断题 偏易 C/C++编程考级 ·C/C++编程五级 · 6 STL

set 的元素按大小降序排列。( )

A
对
B
错
答案与解析
正确答案:错

默认情况下,C++ 的 set 是按 升序(从小到大)排列的。

题目详情
13 判断题 偏易 C/C++编程考级 ·C/C++编程五级 · 6 STL

set 的 insert 操作不会插入重复元素。( )

A
对
B
错
答案与解析
正确答案:对

C++ 的 set 是有序且元素唯一的容器。

题目详情
14 简答题 偏难 C/C++编程考级 ·C/C++编程五级 · 6 STL

通配符匹配

给定一个字符串s和一个字符模式p,请实现一个支持'?'和'*'的通配符匹配功能。

其中‘?’可以匹配任何单个字符,如‘a?c’可以成功匹配‘aac’,‘abc’等字符串,但不可匹配‘ac’,‘aaac’等字符串 。

‘*’ 可以匹配任意长度字符串(包括空字符串),如‘a*c’可以成功匹配‘ac’,‘abdc’,‘abc’,‘aaac’等字符串,但不可匹配‘acb’,‘cac’等字符串。

两个字符串完全匹配才算匹配成功。

时间限制:2000

内存限制:262144

输入

输入为一个数字n表示测试字符串与字符模式对数,换行。(n ≤ 30) 后续2n行为每组匹配的s与p,每行字符串后换行。 s 非空,只包含从 a-z 的小写字母。 p 非空,只包含从 a-z 的小写字母,以及字符 ? 和 *。 字符串s和p的长度均小于50

输出

每一组匹配串匹配成功输出‘yes’,否则输出‘no’。

样例输入

3
abc
abc
abc
a*c
abc
a??c

样例输出

yes
yes
no
答案与解析
参考答案
#include <iostream>
#include <cstring>
using namespace std;

bool isMatch(char* s, char* p) {
    int m = strlen(s);
    int n = strlen(p);
    int i = 0; // s的指针
    int j = 0; // p的指针
    int star = -1; // 上一个星号的位置
    int match = 0; // 上一个星号匹配到的位置

    while (i < m) {
        if (j < n && (p[j] == '?' || s[i] == p[j])) { // '?'或者相等的情况
            i++;
            j++;
        }
        else if (j < n && p[j] == '*') { // '*'的情况
            star = j; // 保存上一个星号的位置
            match = i; // 保存当前匹配到的位置
            j++; // p的指针向后移动一位
        }
        else if (star != -1) { // p中有星号,并且当前字符和p的字符不同,则回溯
            j = star + 1; // p的指针回到上一个星号的下一位
            match++; // 匹配位置向后移动一位
            i = match; // s的指针回到上一个星号匹配到的位置的下一位
        }
        else { // 最后一种情况,匹配失败
            return false;
        }
    }

    while (j < n && p[j] == '*') { // 如果p中还有星号,则可以匹配空字符串
        j++;
    }
    return j == n; // s和p都遍历完了才算匹配成功
}

int main() {
    int n; // 测试样例数
    cin >> n;

    char s[51]; // s的最大长度为50,再加上一个结束符'\0'
    char p[51]; // p的最大长度为50,再加上一个结束符'\0'

    for (int i = 0; i < n; i++) {
        cin >> s >> p;
        if (isMatch(s, p)) {
            cout << "yes" << endl;
        }
        else {
            cout << "no" << endl;
        }
    }

    return 0;
}
题目详情
15 简答题 偏难 C/C++编程考级 ·C/C++编程五级 · 6 STL

求逆序对数

对于一个长度为N的整数序列A,满足i < j 且 Ai > Aj.的数对(i,j)称为整数序列A的一个逆序

请求出整数序列A的所有逆序对个数

时间限制:500

内存限制:65536

输入

输入包含多组测试数据,每组测试数据有两行 第一行为整数N(1 <= N <= 20000),当输入0时结束 第二行为N个整数,表示长为N的整数序列

输出

每组数据对应一行,输出逆序对的个数

样例输入

5
1 2 3 4 5
5
5 4 3 2 1
1
1
0

样例输出

0
10
0
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
const int N = 20005;
int merge(int a[], int s, int m, int e) {
  vector<int> a1;
  int m1 = s, m2 = m + 1, c = 0;
  while (m1 <= m && m2 <= e) {
    if (a[m1] > a[m2]) {
      c += m - m1 + 1;
      a1.push_back(a[m2]);
      m2++;
    } else {
      a1.push_back(a[m1]);
      m1++;
    }
  }
  while (m1 <= m) {
    a1.push_back(a[m1]);
    m1++;
  }
  while (m2 <= e) {
    a1.push_back(a[m2]);
    m2++;
  }
  int k = 0;
  for (int i = s; i <= e; i++)
    a[i] = a1[k++];
  return c;
}
int solve(int a[], int s, int e) {
  if (s >= e)
    return 0;
  int m = (s + e) / 2;
  int l = solve(a, s, m);
  int r = solve(a, m + 1, e);
  int l_r = merge(a, s, m, e);
  return l + r + l_r;
}

int main() {
  int n;
  int a[N];
  while (scanf("%d", &n) && n != 0) {
    for (int i = 0; i < n; i++)
      scanf("%d", &a[i]);
    int sum = solve(a, 0, n - 1);
    cout << sum << endl;
  }
  return 0;
}
题目详情
16 简答题 偏难 C/C++编程考级 ·C/C++编程五级 · 6 STL

分成互质组

给定n个正整数,将它们分组,使得每组中任意两个数互质。至少要分成多少个组?

时间限制:1000

内存限制:65536

输入

第一行是一个正整数n。1 <= n <= 10。 第二行是n个不大于10000的正整数。

输出

一个正整数,即最少需要的组数。

样例输入

6
14 20 33 117 143 175

样例输出

3
答案与解析
参考答案
// 参考答案1:
#include <iostream>
#include <vector>
using namespace std;
const int N = 15;
int n, cnt, ans = N, p[N];
vector<int> s[N];
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
bool check(int k, int x) {
  for (int i = 0; i < s[k].size(); i++)
    if (gcd(s[k][i], x) > 1)
      return false;
  return true;
}
void dfs(int u) {
  if (u == n) {
    ans = min(ans, cnt);
    return;
  }
  for (int i = 0; i < cnt; i++)
    if (check(i, p[u])) {
      s[i].push_back(p[u]);
      dfs(u + 1);
      s[i].pop_back();
    }
  s[cnt++].push_back(p[u]);
  dfs(u + 1);
  s[--cnt].pop_back();
}
int main() {
  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> p[i];
  dfs(0);
  cout << ans << endl;
  return 0;
}

  

// 参考答案2:
#include <iostream>
using namespace std;
const int N = 15;
int n;
int p[N];
int group[N][N];
bool used[N];
int ans = N;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
bool check(int group[], int k, int x) {
  for (int i = 0; i < k; i++)
    if (gcd(p[group[i]], x) > 1)
      return false;
  return true;
}
void dfs(int g, int gc, int cnt, int start) {
  if (g >= ans)
    return;
  if (cnt == n)
    ans = g;

  bool flag = false;
  for (int i = start; i < n; i++)
    if (!used[i] && check(group[g], gc, p[i])) {
      used[i] = true;
      group[g][gc] = i;
      dfs(g, gc + 1, cnt + 1, i + 1);
      used[i] = false;
      flag = true;
    }
  if (!flag)
    dfs(g + 1, 0, cnt, 0);
}
int main() {
  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> p[i];
  dfs(1, 0, 0, 0);
  cout << ans << endl;
  return 0;
}


题目详情
17 简答题 偏难 C/C++编程考级 ·C/C++编程五级 · 6 STL

拼点游戏

C和S两位同学一起玩拼点游戏。有一堆白色卡牌和一堆蓝色卡牌,每张卡牌上写了一个整数点数。C随机抽取n张白色卡牌,S随机抽取n张蓝色卡牌,他们进行n回合拼点,每次两人各出一张卡牌,点数大者获得三颗巧克力,小者获得一颗巧克力,如果点数相同,每人各得二颗巧克力,使用过的卡牌不得重复使用。已知C和S取到的卡牌点数,请编程计算S最多和最少能得到多少颗巧克力。

时间限制:1000

内存限制:65536

输入

输入包含多组测试数据。 每组测试数据的第一行是一个整数n(1<=n<=1000),接下来一行是n个整数,表示C抽到的白色卡牌的点数,下一行也是n个整数,表示S抽到的蓝色卡牌的点数。 输入的最后以一个0表示结束。

输出

对每组数据,输出一行,内容是两个整数用空格格开,分别表示S最多和最少可获得的巧克力数。

样例输入

3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
0

样例输出

9 5
4 4
4 4
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int n, o = 0;
int c[1000] = {0}, s[1000] = {0};
int c1[1000], s1[1000];
int main() {
  while (cin >> n, n) {
    o++;
    for (int i = 0; i < n; i++) {
      cin >> c[i];
    }
    for (int i = 0; i < n; i++) {
      cin >> s[i];
    }
    int cs = 0, ss = 0;
    int ch = 0, sh = 0, ct = n - 1, st = n - 1;
    sort(c, c + n);
    sort(s, s + n);
    while (ch <= ct) {
      if (s[st] > c[ct]) {
        ss += 3;
        cs += 1;
        st--;
        ct--;
      } else if (s[st] < c[ct]) {
        ss += 1;
        cs += 3;
        sh++;
        ct--;
      } else if (s[st] == c[ct]) {
        if (s[sh] <= c[ch]) {
          if (s[sh] < c[ct]) {
            ss += 1;
            cs += 3;
            sh++;
            ct--;
          } else if (s[sh] == c[ct]) {
            ss += 2;
            cs += 2;
            sh++;
            ct--;
          }
        } else {
          ss += 3;
          cs += 1;
          sh++;
          ch++;
        }
      }
    }
    s1[o] = ss;
    for (int i = 0; i < n; i++) {
      swap(c[i], s[i]);
    }
    cs = 0, ss = 0;
    ch = 0, sh = 0, ct = n - 1, st = n - 1;
    sort(c, c + n);
    sort(s, s + n);
    while (ch <= ct) {
      if (s[st] > c[ct]) {
        ss += 3;
        cs += 1;
        st--;
        ct--;
      } else if (s[st] < c[ct]) {
        ss += 1;
        cs += 3;
        sh++;
        ct--;
      } else if (s[st] == c[ct]) {
        if (s[sh] <= c[ch]) {
          if (s[sh] < c[ct]) {
            ss += 1;
            cs += 3;
            sh++;
            ct--;
          } else if (s[sh] == c[ct]) {
            ss += 2;
            cs += 2;
            sh++;
            ct--;
          }
        } else {
          ss += 3;
          cs += 1;
          sh++;
          ch++;
        }
      }
    }
    c1[o] = cs;
  }
  for (int i = 1; i <= o; i++) {
    cout << s1[i] << " " << c1[i] << endl;
  }
  return 0;
}
题目详情
18 简答题 偏难 C/C++编程考级 ·C/C++编程五级 · 6 STL

数字变换

给定一个包含5个数字(0-9)的字符串,例如 “02943”,请将“12345”变换到它。 你可以采取3种操作进行变换 

1. 交换相邻的两个数字 

2. 将一个数字加1。如果加1后大于9,则变为0 

3. 将一个数字加倍。如果加倍后大于9,则将其变为加倍后的结果除以10的余数。 

最多只能用第2种操作3次,第3种操作2次 求最少经过多少次操作可以完成变换。

时间限制:1000

内存限制:65536

输入

有最多 100,000 组数据 每组数据就是包含5个数字的字符串

输出

对每组数据,输出将"12345"变换到给定字符串所需要的最少操作步数。如果无法变换成功,输出-1

样例输入

12435
99999
12374

样例输出

1
-1
3

提示

由于测试数据太多,如果对每组数据都从头进行搜索,就会超时。 建议先做预处理,即以“12345”作为初始状态做一遍彻底的广搜,找出“12345”经合法变换能够到达的所有字符串,并记录到达这些字符串各需要多少步操作。 然后对读入的每组数据,在上述预处理记录的结果中进行查询即可。

答案与解析
参考答案
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>

using namespace std;
char a[6] = "12345";
bool vis[100000][4][3];
int ans[100000];
struct node {
  string a;
  int op2, op3, step;
  node(string aa, int o2, int o3, int ss = 0)
      : a(aa), op2(o2), op3(o3), step(ss){};
};
queue<node> q;
int main() {
  memset(vis, false, sizeof(vis));
  memset(ans, -1, sizeof(ans));
  q.push(node("12345", 0, 0));
  vis[12345][0][0] = true;
  ans[12345] = 0;
  while (!q.empty()) {
    node no = q.front();
    q.pop();
    string temp = no.a;
    if (ans[int(atof(temp.c_str()))] == -1)
      ans[int(atof(temp.c_str()))] = no.step;
    //    cout<<no.a<<endl;
    // 第一种操作
    for (int i = 0; i < 4; i++) {
      swap(temp[i], temp[i + 1]);
      if (!vis[int(atof(temp.c_str()))][no.op2][no.op3]) {
        vis[int(atof(temp.c_str()))][no.op2][no.op3] = true;
        q.push(node(temp, no.op2, no.op3, no.step + 1));
      }
      swap(temp[i], temp[i + 1]);
    }
    // 第二种操作
    if (no.op2 < 3) {
      for (int i = 0; i < 5; i++) {
        temp = no.a;
        int num = temp[i] - '0';
        num++;
        if (num == 10)
          num = 0;
        temp[i] = '0' + num;
        if (!vis[int(atof(temp.c_str()))][no.op2 + 1][no.op3]) {
          vis[int(atof(temp.c_str()))][no.op2 + 1][no.op3] = true;
          q.push(node(temp, no.op2 + 1, no.op3, no.step + 1));
        }
      }
    }

    // 第三种操作
    if (no.op3 < 2) {
      for (int i = 0; i < 5; i++) {
        temp = no.a;
        int num = temp[i] - '0';
        num *= 2;
        if (num > 9)
          num %= 10;
        temp[i] = '0' + num;
        if (!vis[int(atof(temp.c_str()))][no.op2][no.op3 + 1]) {
          vis[int(atof(temp.c_str()))][no.op2][no.op3 + 1] = true;
          q.push(node(temp, no.op2, no.op3 + 1, no.step + 1));
        }
      }
    }
  }
  while (cin >> a) {
    cout << ans[int(atof(a))] << endl;
  }
  return 0;
}
题目详情
19 简答题 偏难 C/C++编程考级 ·C/C++编程五级 · 6 STL

Freda的越野跑

Freda报名参加了学校的越野跑。越野跑共有N人参加,在一条笔直的道路上进行。这N个人在起点处站成一列,相邻两个人之间保持一定的间距。比赛开始后,这N个人同时沿着道路向相同的方向跑去。换句话说,这N个人可以看作x轴上的N个点,在比赛开始后,它们同时向x轴正方向移动。

假设越野跑的距离足够远,这N个人的速度各不相同且保持匀速运动,那么会有多少对参赛者之间发生“赶超”的事件呢?

时间限制:1000

内存限制:262144

输入

第一行1个整数N。 第二行为N 个非负整数,按从前到后的顺序给出每个人的跑步速度。 对于50%的数据,2<=N<=1000。 对于100%的数据,2<=N<=100000。

输出

一个整数,表示有多少对参赛者之间发生赶超事件。

样例输入

5
1 3 10 8 5

样例输出

7

提示

我们把这5个人依次编号为A,B,C,D,E,速度分别为1,3,10,8,5。 在跑步过程中: B,C,D,E均会超过A,因为他们的速度都比A快; C,D,E都会超过B,因为他们的速度都比B快; C,D,E之间不会发生赶超,因为速度快的起跑时就在前边。

答案与解析
参考答案
#include <iostream>
using namespace std;
int a[100001];
int ta[100001];
long long int ans = 0;
void merge(int left, int right, int middle) {
  int i, j, index1, index2;
  for (j = left; j <= right; ++j)
    ta[j] = a[j];
  index1 = left;
  index2 = middle + 1;
  i = left;
  while (index1 <= middle && index2 <= right) {
    if (ta[index1] >= ta[index2]) {
      a[i] = ta[index1];
      ++i;
      ++index1;
    } else {
      a[i] = ta[index2];
      ans += middle - index1 + 1; // 这个右子列元素超过了左子列中剩余的元素
      ++i;
      ++index2;
    }
  }
  while (index1 <= middle) {
    a[i] = ta[index1];
    ++i;
    ++index1;
  }
  while (index2 <= right) {
    a[i] = ta[index2];
    ++i;
    ++index2;
  }
}
void mergesort(int left, int right) {
  int middle;
  if (left < right) {
    middle = (left + right) / 2;
    mergesort(left, middle);
    mergesort(middle + 1, right);
    merge(left, right, middle);
  }
}
int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  mergesort(0, n - 1);
  cout << ans;
  // system("pause");
  return 0;
}
题目详情
20 简答题 偏难 C/C++编程考级 ·C/C++编程五级 · 6 STL

问题求解

给定一个正整数N,求最小的M满足比N大且M与N的二进制表示中有相同数目的1。

举个例子,假如给定N为78,二进制表示为1001110,包含4个1,那么最小的比N大的并且二进制表示中只包含4个1的数是83,其二进制是1010011,因此83就是答案。

时间限制:1000

内存限制:65536

输入

输入若干行,每行一个数N(1 ≤ N ≤ 1000000),如果这行为0表示输入结束。

输出

对于每个N,输出对应的M。

样例输入

1
2
3
4
78
0

样例输出

2
4
5
8
83
答案与解析
参考答案
//解法1
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define INF 999999999
#define N 1001
using namespace std;
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF&&n)
    {
        int cnt=0;
        int temp=n;
        while(temp>0)
        {
            if(temp%2)
                cnt++;
            temp/=2;
        }
        int sum=0;
        while(1)
        {
            temp=++n;
            while(temp>0)
            {
                if(temp%2)
                    sum++;
                temp/=2;
            }
            if(cnt==sum)
            {
                cout<<n<<endl;
                break;
            }
            sum=0;
        }
    }
    return 0;
}
//解法2 样例代码  枚举
using namespace std;
int n;  // 定义变量 n
int tj(int x) {
    int ans = 0;  // 定义变量 ans
    while (x) {  // 当 x 不为0循环执行
        if (x &)
            ans++;  // 如果 x 的最低位为1,则将 ans 加1
        x >>= 1;  // 将 x 右移1位,即将 x 的二进制表示向右移动一位
    }
    return ans;  // 返回 ans
}
int main() {
    while (1) {  // 无限循环
        cin >> n;  // 从标准输入读取一个整数 n
        if (!n)break;  如果 n 为0,则结束循环
        int t = tj(n);  // 调用函数 tj 计算 n 的二进制中的1的个数,并将结果赋值给 t
        for (int i = n + 1;; i++) {  // 从 n+1 开始递增遍历整数 i
            if (t == tj(i)) {
                cout << i << endl;  // 输出第一个满足条件的整数 i,即其二进制表示中的1的个数与 t 相等
                break;  // 结束循环
            }
        }
    }
    return 0;  // 返回 0,表示程序正常结束
}
题目详情