首页 › 题库 › C/C++编程考级 › 1 栈与队列

C/C++编程六级 题库

共 51 道题 ,第 1 / 3 页 · 按题型筛选,点「查看答案」核对解析
章节 1 栈与队列 清除
1 单选题 适中 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列
队列的进出规则是?( )
A
先进后出
B
先进先出
C
后进先出
D
随机进出
答案与解析
正确答案:B
队列是一种线性数据结构,元素的添加发生在一端,移除发生在另一端。新进入的元素总是置于队列末尾,而最先进入的元素始终位于队列前端,只有当其前面没有其他元素时才能被移除。每一元素按进入顺序依次等待处理,任何元素不能跳过在其前面的元素直接被移除。该结构确保了元素的处理顺序与其进入顺序完全一致,不存在优先级调整或随机选择机制。所有操作遵循固定的顺序规则,不因外部条件改变进出次序。
题目详情
2 单选题 适中 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列
一棵二叉树的前序遍历为`1 2 4 5 3`,中序遍历为`4 2 5 1 3`,则后序遍历为?( )
A
4 5 2 3 1
B
1 2 3 4 5
C
4 2 5 3 1
D
5 4 3 2 1
答案与解析
正确答案:A
AI解析服务异常,请稍后重试
题目详情
3 单选题 适中 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

栈的进出规则?( )

A
先进先出
B
先进后出
C
随机进出
D
后进后出
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
4 单选题 适中 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

二叉树的遍历中,顺序为“左子树→根节点→右子树”的?( )

A
前序遍历
B
中序遍历
C
后序遍历
D
层序遍历
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
5 判断题 偏易 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

无向图的邻接矩阵是对称矩阵。( )

A
对
B
错
答案与解析
正确答案:对
无向图中每条边连接两个顶点且无方向,若顶点i与顶点j之间存在边,则在邻接矩阵中第i行第j列和第j行第i列的元素值相等。邻接矩阵通过矩阵元素表示顶点间的连接关系,矩阵的行和列分别对应图的顶点。由于边的无向性,任意两顶点间的连接关系在矩阵中对称出现,导致矩阵关于主对角线对称。只要图结构满足无向性,其邻接矩阵必然呈现对称特性。
题目详情
6 判断题 偏易 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

哈希冲突是指两个不同的关键字,通过哈希函数得到了相同的哈希地址。( )

A
对
B
错
答案与解析
正确答案:对
哈希函数将不同关键字映射到有限的地址空间,当两个不同关键字经哈希函数计算后得到相同哈希地址时,即发生哈希冲突。该现象由哈希函数的非单射性导致,是哈希表设计中的固有现象。冲突的产生不依赖于具体实现或外部条件,仅由关键字分布与哈希函数数学性质决定。所有基于哈希函数的存储结构均可能遇到此情况,其存在独立于冲突解决机制。
题目详情
7 判断题 偏易 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

一棵有n个节点的树,恰好有n-1条边。( )

A
对
B
错
答案与解析
正确答案:对
树是无向图的一种特殊形式,满足连通且无环的性质。根据图论基本定理,一个具有n个节点的连通无向图若恰好有n-1条边,则该图是一棵树。反之,若一个无向图是树,则其边数必然为n-1。边数与节点数之间的关系由树的结构决定:每新增一个节点,仅需添加一条边连接至已有节点,以维持连通性和无环性。因此,n个节点的树必须具备n-1条边,此关系为树定义的直接推论。
题目详情
8 判断题 偏易 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

哈希表的核心是通过哈希函数将关键字映射到数组下标,实现快速查找。( )

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

哈夫曼编码的构建过程使用了贪心算法的思想。( )

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

有向图的邻接矩阵中,第 i 行第 j 列的元素表示从节点 j 到节点 i 的边。( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
11 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

波兰表达式

波兰表达式是一种把运算符前置的算术表达式,例如普通的表达式2 + 3的波兰表示法为+ 2 3。波兰表达式的优点是运算符之间不必有优先级关系,也不必用括号改变运算次序,例如(2 + 3) * 4的波兰表示法为* + 2 3 4。本题求解波兰表达式的值,其中运算符包括+ - * /四个。

时间限制:1000

内存限制:65536

输入

输入为一行,其中运算符和运算数之间都用空格分隔,运算数是浮点数。

输出

输出为一行,表达式的值。 可直接用printf("%f\n", v)输出表达式的值v。

样例输入

* + 11.0 12.0 + 24.0 35.0

样例输出

1357.000000
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
double exp() {
  char s[20];
  cin >> s;
  switch (s[0]) {
  case '+':
    return exp() + exp();
  case '-':
    return exp() - exp();
  case '*':
    return exp() * exp();
  case '/':
    return exp() / exp();
  default:
    return stof(s);
  }
}
int main() {
  printf("%0.6f", exp());
  return 0;
}
题目详情
12 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

括号配对

字符串中可能有三种成对的括号,"( )"、"[ ]"、"{ }"。请判断字符串的括号是否都正确配对。无括号也算正确配对。括号交叉算不正确配对,例如"12{34[78}ab]"就不算正确配对。但是一对括号被包含在另一对括号里面,例如"12{ab[8]}"不影响正确性。

时间限制:1000

内存限制:65536

输入

第一行为整数n(n<40),接下来有n行,每行一个无空格的字符串,长度小于1000。

输出

对每行字符串,如果括号配对,输出"YES",否则输出"NO"。

样例输入

2
12{ab[8]}
12{34[78}ab]

样例输出

YES
NO
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int main() {
  cin >> n;
  while (n--) {
    cin >> s;
    stack<char> st;
    int ls = s.size();
    bool sign = true;
    for (int i = 0; i < ls; i++) {
      if (s[i] == '(' || s[i] == '[' || s[i] == '{')
        st.push(s[i]);
      else if (!st.empty() && s[i] == ')') {
        if (st.top() == '(')
          st.pop();
        else
          sign = false;
      } else if (s[i] == '}') {
        if (!st.empty() && st.top() == '{')
          st.pop();
        else
          sign = false;
      } else if (s[i] == ']') {
        if (!st.empty() && st.top() == '[')
          st.pop();
        else
          sign = false;
      }
    }
    if (st.empty() && sign)
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  }
  return 0;
}
题目详情
13 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

扑克牌排序(2023.3)

假设这里有36张扑克牌,分别为A1~A9,B1~B9,C1~C9,D1~D9,其中A代表方片,B代表草花,C代表红桃,D代表黑桃,那么,设定如下的排序规则:

1.对于两张卡牌,X1Y1与X2Y2,X1与X2表示A~D,Y1与Y2表示1~9,如果X1与X2不同,那么依照D>C>B>A的方式进行排序

2.假如有X1与X2相同时,那么就比较Y1与Y2的大小。

例如,对于如下的四张牌,有如下的升序排序结果:

D3,C4,A4,C1

升序排序的结果为A4,C1,C4,D3

有人提出了如下的排序策略:

先建立9个队列,用于存放点数的大小,将卡牌依点数存放入各自的队列之中,然后再按队列1到队列9依次出队。

例如,对于上面的结果,依次进队后,结果如下:

队列1:C1;队列3:D3,队列4:C4,A4

将其依次出队后,结果为C1,D3,C4,A4

然后,再建立4个队列,用于存放花色。将卡牌依花色A~D存放入队列1~4中,然后再按队列1到队列4依次出队。

例如,对于上面刚刚出队的序列C1,D3,C4,A4,将其依次进队,结果如下:

队列1:A4;队列3:C1,C4;队列4:D3

将其依次出队后,结果为A4,C1,C4,D3,排序结束。

请根据上面的算法,编写一个用队列对扑克牌排序的程序,要求依照上面的排序规则,根据先花色后点数的方法进行排序。

时间限制:1000

内存限制:65536

输入

输入分为两行,第一行为一个整数n,表示一共有n张牌(1<=n<=100) 第二行用XY的形式表示每一张牌,其中X为A~D,Y为1~9

输出

输出三个部分 第一个部分为第一次进队出队的结果,用Queue1:...表示,共9行,结果用空格分隔,下同 第二部分为第二次进队出队的结果,用QueueA:...表示,共4行 第三部分为一行,即将卡牌排序后的结果(升序排序)


样例输入

8
D8 A6 C3 B8 C5 A1 B5 D3

样例输出

Queue1:A1
Queue2:
Queue3:C3 D3
Queue4:
Queue5:C5 B5
Queue6:A6
Queue7:
Queue8:D8 B8
Queue9:
QueueA:A1 A6
QueueB:B5 B8
QueueC:C3 C5
QueueD:D3 D8
A1 A6 B5 B8 C3 C5 D3 D8

提示

第二次入队出队时,可以复用第一次时9个队列中的4个。所以其实只需要开辟9个队列即可。

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  string s;
  queue<string> qn[9];
  queue<string> color[4];
  queue<string> qs;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> s;
    int t = s[1] - '0' - 1;
    qn[t].push(s);
  }
  for (int i = 0; i <= 8; i++) {
    cout << "Queue" << i + 1 << ":";
    while (!qn[i].empty()) {
      s = qn[i].front();
      switch (s[0]) {
      case 'A':
        color[0].push(s);
        break;
      case 'B':
        color[1].push(s);
        break;
      case 'C':
        color[2].push(s);
        break;
      case 'D':
        color[3].push(s);
        break;
      }
      qn[i].pop();
      cout << s << " ";
    }
    cout << endl;
  }
  for (int i = 0; i <= 3; i++) {
    cout << "Queue" << (char)('A' + i) << ":";
    while (!color[i].empty()) {
      s = color[i].front();
      color[i].pop();
      qs.push(s);
      cout << s << " ";
    }
    cout << endl;
  }
  while (!qs.empty()) {
    cout << qs.front() << " ";
    qs.pop();
  }
  return 0;
}
题目详情
14 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

滑动窗口

给定一个长度为n(n<=10^6)的数组。有一个大小为k的滑动窗口从数组的最左端移动到最右端。你可以看到窗口中的k个数字。窗口每次向右滑动一个数字的距离。

下面是一个例子:

数组是 [1 3 -1 -3 5 3 6 7], k = 3。

你的任务是得到滑动窗口在每个位置时的最大值和最小值。

时间限制:20000

内存限制:65536

输入

输入包括两行。 第一行包括n和k,分别表示数组的长度和窗口的大小。 第二行包括n个数字。

输出

输出包括两行。 第一行包括窗口从左至右移动的每个位置的最小值。 第二行包括窗口从左至右移动的每个位置的最大值。


样例输入

8 3
1 3 -1 -3 5 3 6 7

样例输出

-1 -3 -3 -3 3 3
3 3 5 5 6 7
答案与解析
参考答案
#include 
#include 
#include 

using namespace std;
int n, k, tmp;
deque p;
deque q;
vector arr;
vector MyMax;
vector MyMin;
int main() {
  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &tmp);
    arr.push_back(tmp);
  }

  for (int i = 0; i < n; ++i) {
    if (!p.empty() && p.front() == i - k) // 把窗口划过部分的序号删掉
      p.pop_front();

    while (!p.empty() &&
           arr[p.back()] < arr[i]) // 删去队尾比当前元素小的,肯定用不到他们
      p.pop_back();
    p.push_back(i); // 当前元素入队

    if (i >= k - 1) // 从k-1开始记录(第一个窗口
      MyMax.push_back(arr[p.front()]);
  }

  for (int i = 0; i < n; ++i) {
    if (!q.empty() && q.front() == i - k)
      q.pop_front();
    while (!q.empty() && arr[q.back()] > arr[i])
      q.pop_back();
    q.push_back(i);
    if (i >= k - 1)
      MyMin.push_back(arr[q.front()]);
  }

  for (int i = 0; i <= n - k; ++i)
    cout << MyMin[i] << ' ';

  cout << endl;

  for (int i = 0; i <= n - k; ++i)
    cout << MyMax[i] << ' ';

  return 0;
}
题目详情
15 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

区间合并(2022-12-六级)

给定 n 个闭区间 [ai; bi],其中i=1,2,...,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如,[1;2] 和 [2;3] 可以合并为 [1;3],[1;3] 和 [2;4] 可以合并为 [1;4],但是[1;2] 和 [3;4] 不可以合并。

我们的任务是判断这些区间是否可以最终合并为一个闭区间,如果可以,将这个闭区间输出,否则输出no。

时间限制:1000

内存限制:65536

输入

第一行为一个整数n,3 ≤ n ≤ 50000。表示输入区间的数量。 之后n行,在第i行上(1 ≤ i ≤ n),为两个整数 ai 和 bi ,整数之间用一个空格分隔,表示区间 [ai; bi](其中 1 ≤ ai ≤ bi ≤ 10000)。

输出

输出一行,如果这些区间最终可以合并为一个闭区间,输出这个闭区间的左右边界,用单个空格隔开;否则输出 no。

样例输入

5
5 6
1 5
10 10
6 9
8 10

样例输出

1 10
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
struct Nod {
  int x, y;
  friend bool operator<(Nod a, Nod b) {
    if (a.x != b.x)
      return a.x < b.x;
    else
      return a.y < b.y;
  }
} node[50005];
int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> node[i].x >> node[i].y;
  sort(node, node + n);
  int lf = node[0].x;
  int rt = node[0].y;
  for (int i = 1; i < n; i++) {
    if (lf <= node[i].x && node[i].x <= rt) {
      rt = max(rt, node[i].y);
    } else {
      cout << "no";
      return 0;
    }
  }
  cout << lf << " " << rt;
  return 0;
}
题目详情
16 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

电话号码(2022-12,六级)

给你一些电话号码,请判断它们是否是一致的,即是否有某个电话是另一个电话的前缀。比如:

Emergency 911

Alice 97 625 999

Bob 91 12 54 26

在这个例子中,我们不可能拨通Bob的电话,因为Emergency的电话是它的前缀,当拨打Bob的电话时会先接通Emergency,所以这些电话号码不是一致的。

时间限制:1000

内存限制:65536

输入

第一行是一个整数t,1 ≤ t ≤ 40,表示测试数据的数目。 每个测试样例的第一行是一个整数n,1 ≤ n ≤ 10000,其后n行每行是一个不超过10位的电话号码。

输出

对于每个测试数据,如果是一致的输出“YES”,如果不是输出“NO”。

样例输入

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

样例输出

NO
YES
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct Trie {
  int c[10], s;
  Trie() {
    memset(c, 0, sizeof(c));
    s = 0;
  }
} t[N];
int tot;
void clear(int x) {
  t[x].s = 0;
  for (int i = 0; i <= 9; i++)
    if (t[x].c[i])
      clear(t[x].c[i]), t[x].c[i] = 0;
}
char s[15];
bool bt(int x) {
  int len = strlen(s + 1);
  bool bk = false;
  for (int i = 1; i <= len; i++) {
    int y = s[i] - '0';
    if (!t[x].c[y])
      t[x].c[y] = ++tot;
    else if (i == len)
      bk = true;
    x = t[x].c[y];
    if (t[x].s)
      bk = true;
  }
  t[x].s++;
  return bk;
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    bool bk = false;
    clear(0);
    tot = 0;
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
      scanf("%s", s + 1);
      if (bk)
        continue;
      if (bt(0))
        bk = true;
    }
    if (bk)
      puts("NO");
    else
      puts("YES");
  }
  return 0;
}

  

题目详情
17 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

扑克牌排序

假设这里有36张扑克牌,分别为A1~A9,B1~B9,C1~C9,D1~D9,其中A代表方片,B代表草花,C代表红桃,D代表黑桃,那么,设定如下的排序规则:

1.对于两张卡牌,X1Y1与X2Y2,X1与X2表示A~D,Y1与Y2表示1~9,如果X1与X2不同,那么依照D>C>B>A的方式进行排序

2.假如有X1与X2相同时,那么就比较Y1与Y2的大小。

例如,对于如下的四张牌,有如下的升序排序结果:

D3,C4,A4,C1

升序排序的结果为A4,C1,C4,D3

有人提出了如下的排序策略:

先建立9个队列,用于存放点数的大小,将卡牌依点数存放入各自的队列之中,然后再按队列1到队列9依次出队。

例如,对于上面的结果,依次进队后,结果如下:

队列1:C1;队列3:D3,队列4:C4,A4

将其依次出队后,结果为C1,D3,C4,A4

然后,再建立4个队列,用于存放花色。将卡牌依花色A~D存放入队列1~4中,然后再按队列1到队列4依次出队。

例如,对于上面刚刚出队的序列C1,D3,C4,A4,将其依次进队,结果如下:

队列1:A4;队列3:C1,C4;队列4:D3

将其依次出队后,结果为A4,C1,C4,D3,排序结束。

请根据上面的算法,编写一个用队列对扑克牌排序的程序,要求依照上面的排序规则,根据先花色后点数的方法进行排序。

时间限制:1000

内存限制:65536

输入

输入分为两行,第一行为一个整数n,表示一共有n张牌(1<=n<=100) 第二行用XY的形式表示每一张牌,其中X为A~D,Y为1~9

输出

输出三个部分 第一个部分为第一次进队出队的结果,用Queue1:...表示,共9行,结果用空格分隔,下同 第二部分为第二次进队出队的结果,用QueueA:...表示,共4行 第三部分为一行,即将卡牌排序后的结果(升序排序)

样例输入

8
D8 A6 C3 B8 C5 A1 B5 D3

样例输出

Queue1:A1
Queue2:
Queue3:C3 D3
Queue4:
Queue5:C5 B5
Queue6:A6
Queue7:
Queue8:D8 B8
Queue9:
QueueA:A1 A6
QueueB:B5 B8
QueueC:C3 C5
QueueD:D3 D8
A1 A6 B5 B8 C3 C5 D3 D8

提示

第二次入队出队时,可以复用第一次时9个队列中的4个。所以其实只需要开辟9个队列即可。

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  string s;
  queue<string> qn[9];
  queue<string> color[4];
  queue<string> qs;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> s;
    int t = s[1] - '0' - 1;
    qn[t].push(s);
  }
  for (int i = 0; i <= 8; i++) {
    cout << "Queue" << i + 1 << ":";
    while (!qn[i].empty()) {
      s = qn[i].front();
      switch (s[0]) {
      case 'A':
        color[0].push(s);
        break;
      case 'B':
        color[1].push(s);
        break;
      case 'C':
        color[2].push(s);
        break;
      case 'D':
        color[3].push(s);
        break;
      }
      qn[i].pop();
      cout << s << " ";
    }
    cout << endl;
  }
  for (int i = 0; i <= 3; i++) {
    cout << "Queue" << (char)('A' + i) << ":";
    while (!color[i].empty()) {
      s = color[i].front();
      color[i].pop();
      qs.push(s);
      cout << s << " ";
    }
    cout << endl;
  }
  while (!qs.empty()) {
    cout << qs.front() << " ";
    qs.pop();
  }
  return 0;
}
题目详情
18 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

现代艺术

在对二维艺术作品感到厌烦之后,伟大的艺术牛Picowso决定从事创作一项更为小众的艺术形式,一维画。

尽管目前她的画作可以用一个由颜色组成的长度为N(1~100000)的数组表示,但她的创作风格依然保持不变:从一张空白的矩形画布上,不断地画上一些矩形,在一维的情况下,这些矩形就只是一个区间。她用N种颜色,颜色编号为1~N进行创作,每种颜色只使用一次,之后使用的颜色可以完全的覆盖之前在相同位置上的颜色。

令Picowso感到十分沮丧的是,她的竞争对手Moonet似乎弄明白了如何复制她的这些一维画作,Moonet会画一些不相交的间隔,等待这些颜色晾干,然后再画另外的一些间隔,直到画完。Moonet每次每种颜色最多只能画一个间隔,但是他可以一次画不同颜色不相交的多个间隔,只要这些间隔没有重叠部分。之后Moonet再进行下一轮绘制。请计算Moonet为了复制一幅画需要画几个回合。

时间限制:10000

内存限制:65536

输入

第一行是一个整数N,之后N行包含了N个整数,范围0到N表示纸带每个格点的颜色,0表示没有涂色。

输出

输出一行,需要复制这幅画作的最少回合数,如果这幅画不可能是Picowso的画作输出-1(比如说这幅画不可能是通过一次在一条上画一层的方法进行创作的)

样例输入

7
0
1
4
5
1
3
3

样例输出

2

提示

在这个样例中,第一轮涂成0111133,第二轮涂成0145133,所以共需两轮。

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int end_pos[N], a[N];
int n, result, flag = 1;
char v[N];
stack<int> s;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i += 1) {
    scanf("%d", &a[i]);
    end_pos[a[i]] = i; // 记录每个颜色的终点位置
  }
  v[0] = 1; // 初始化 将0视为覆盖整个画布的第一种颜色
  end_pos[0] = n + 1;
  s.push(0);
  for (int i = 1; i <= n && flag; i++) {
    if (s.top() != a[i]) {
      if (v[a[i]])
        flag = 0;   // 颜色被使用过 标记非法
      s.push(a[i]); // 加入新的颜色
    }
    v[a[i]] = 1; // 标记该颜色被使用过
    result = max(result, (int)s.size());
    if (i == end_pos[a[i]]) {
      s.pop(); // 该颜色最后一次被使用 弹出改颜色
    }
  }
  if (!flag)
    cout << -1;
  else
    cout << result - 1;
  return 0;
}
题目详情
19 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

字符串插入

有两个字符串str和substr,str的字符个数不超过10,substr的字符个数为3。(字符个数不包括字符串结尾处的'\0'。)将substr插入到str中ASCII码最大的那个字符后面,若有多个最大则只考虑第一个。

时间限制:1000

内存限制:65536

输入

输入包括若干行,每一行为一组测试数据,格式为 str substr

输出

对于每一组测试数据,输出插入之后的字符串。

样例输入

abcab eee
12343 555

样例输出

abceeeab
12345553
答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string str,substr;
  while(cin>>str>>substr)
  {
    int maxn=0,maxid,i;
    for(i=0;i<str.size();i++)
    {
      if((str[i]-'0')>maxn)
      {
        maxn=str[i]-'0';
        maxid=i;
      }
    }
    for(i=0;i<str.size();i++)
    {
      cout<<str[i];
      if(i==maxid) cout<<substr;
    }
    cout<<endl;
  }
  return 0;
}
题目详情
20 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

机器翻译

VariantF的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,并将这个单词和译义放入内存,以备后续的查找和翻译。

假设内存中有M 个单元,每单元能存放一个单词和译义。每当软件将一个新单词存入内存前,如果当前内存中已存入的单词数不超过M,软件会将新单词存入一个未使用的内存单元;若内存中已存入M 个单词,软件会清空最早进入内存的那个单词,腾出单元来,存放新单词。

假设一篇英语文章的长度为N 个单词。给定这篇待译文章,翻译软件需要去外存查找多少次词典?假设在翻译开始前,内存中没有任何单词。

时间限制:1000

内存限制:262144

输入

第一行为两个正整数M 和N,代表内存容量和文章的长度。 第二行为N 个非负整数,按照文章的顺序,每个数(大小不超过1000000)代表一个英文单词。文章中两个单词是同一个单词,当且仅当它们对应的非负整数相同。 对于50%的数据,1<=N、M<=1000; 对于100%的数据,1<=N、M<=1000000。

输出

一个整数,为软件需要查词典的次数。

样例输入

3 7 
1 2 1 5 4 4 1

样例输出

5

提示

整个查字典过程如下:每行表示一个单词的翻译,冒号前为本次翻译后的内存状况: 空:内存初始状态为空。 1. 1:查找单词1 并调入内存。 2. 1 2:查找单词2 并调入内存。 3. 1 2:在内存中找到单词1。 4. 1 2 5:查找单词5 并调入内存。 5. 2 5 4:查找单词4 并调入内存替代单词1。 6. 2 5 4:在内存中找到单词4。 7. 5 4 1:查找单词1 并调入内存替代单词2。 共计查了5 次词典。

答案与解析
参考答案
#include<cstdio>
int word[2000];
bool sch(int tgt,int range)//线性搜索,因为数据<1000,不会超时。 
{
    for(int i=0;i<range;i++)
    {
        if(word[i]==tgt)
        {
            return true;
        }
    }
    return false;
}
int main()
{
    int mem,num,tm,wor,ans=0;
    scanf("%d %d",&mem,&num);
    tm=0;
    for(int i=0;i<2000;i++)
    {
        word[i]=-1;//数组初始化一定要初始化成-1!!!!
        //字母代号有可能是0,所以初始化成0会出错!!!!
    }
    for(int i=0;i<num;i++)
    {
        scanf("%d",&wor);
        //非常节省空间和时间的模拟  
        if(tm>=mem)
        {
            tm=0;
        }
        if(!sch(wor,mem))
        {
            //自己进行轮回。。。 
            ans++;
            word[tm]=wor;
            tm++;     
        }
    }
    printf("%d",ans);
}
// 题解2
#include <bits/stdc++.h>
using namespace std;
int main() {
  deque<int> v;
  int m, n, ans = 0;
  cin >> m >> n;
  for (int i = 1, a; i <= n; i++) {
    cin >> a;
    if (v.empty()) {
      v.push_back(a);
      ans++;
    } else {
      auto it = std::find(v.begin(), v.end(), a);
      if (it != v.end())
        continue;
      else {
        if (v.size() == unsigned(m))
          v.pop_front();
        v.push_back(a);
        ans++;
      }
    }
  }
  cout << ans;
  return 0;
}
题目详情