CSP-J 卷

下图中所使用的数据结构是（ ）。图示依次执行“压入 A、压入 B、弹出 B、压入 C”。

对于入栈顺序为 a, b, c, d, e 的序列，下列（ ）不是合法的出栈序列。

表达式 a*(b+c)*d 的后缀表达式为（ ），其中 * 和 + 是运算符。

有 $6$ 个元素，按照 $6$、$5$、$4$、$3$、$2$、$1$ 的顺序进入栈 S，请问下列哪个出栈序列是非法的（ ）。

对表达式 a+(b-c)*d 的前缀表达式为（ ），其中 +、-、* 是运算符。

以下对数据结构的表述不恰当的一项为：（ ）。

后缀表达式 6 2 3 + - 3 8 2 / + * 2 ^ 3 + 对应的中缀表达式是（ ）。

给定一个空栈，支持入栈和出栈操作。若入栈操作的元素依次是 1 2 3 4 5 6，其中 1 最先入栈、6 最后入栈，下面哪种出栈顺序是不可能的？（ ）

对假设栈 S 和队列 Q 的初始状态为空。存在 e1~e6 六个互不相同的数据，每个数据按照进栈 S、出栈 S、进队列 Q、出队列 Q 的顺序操作，不同数据间的操作可能会交错。已知栈 S 中依次有数据 e1、e2、e3、e4、e5 和 e6 进栈，队列 Q 依次有数据 e2、e4、e3、e6、e5 和 e1 出队列。则栈 S 的容量至少是（ ）个数据。

给定一个初始为空的整数栈 $S$ 和一个空的队列 $P$。我们按顺序处理输入的整数队列 $A: 7, 5, 8, 3, 1, 4, 2$。对于队列 $A$ 中的每一个数，执行以下规则：如果该数是奇数，则将其压入栈 $S$；如果该数是偶数，且栈 $S$ 非空，则弹出一个栈顶元素，并加入到队列 $P$ 的末尾；如果该数是偶数，且栈 $S$ 为空，则不进行任何操作。当队列 $A$ 中的所有数都处理完毕后，队列 $P$ 的内容是什么？（ ）

在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。

有关下面 C++ 代码的说法，正确的是（ ）。

01#include <iostream>
02using namespace std;
03
04class ManyData {
05    int * __data;
06    int head, tail, capacity;
07public:
08    ManyData(int cap) {
09        capacity = cap;
10        __data = new int[capacity];
11        head = tail = 0;
12    }
13    void push(int val) {
14        __data[tail++] = val;
15    }
16    int pop() {
17        return __data[--tail];
18    }
19    int size() {
20        return tail - head;
21    }
22};
23int main() {
24    auto myData = ManyData(100);
25    myData.push(1);
26    myData.push(2);
27    myData.push(3);
28    myData.push(100);
29    cout << myData.size() << endl;
30    cout << myData.pop() << endl;
31    return 0;
32}

给定一个空栈，执行以下操作序列：

操作序列：push(1), push(2), push(3), pop(), pop(), push(4), push(5), pop()

最终栈中的元素是（ ）。

栈的基本操作包括入栈（push）和出栈（pop）。

向一个栈顶为 hs 的链式栈中插入一个指针为 s 的结点时，应执行（ ）。

在栈数据结构中，元素的添加和删除是按照什么原则进行的？

采用如下代码实现检查输入的字符串括号是否匹配，横线上应填入的代码为（ ）。

01#include <iostream>
02#include <stack>
03#include <string>
04
05using namespace std;
06
07bool is_valid(string s) {
08    stack<char> st;
09    char top;
10
11    for (char& ch : s) {
12        if (ch == '(' || ch == '{' || ch == '[') {
13            st.push(ch);    // 左括号入栈
14        }
15        else
16        {
17            if (st.empty())
18                return false;
19            ____________ // 在此处填入代码
20            if ((ch == ')' && top != '(') ||
21                (ch == '}' && top != '{') ||
22                (ch == ']' && top != '[')) {
23                return false;
24            }
25        }
26    }
27
28    return st.empty();      // 栈为空则说明所有括号匹配成功
29}

栈是一种线性结构，可通过数组或链表来实现。二者相比，数组实现占用的内存较少，链表实现的入队和出队操作的时间复杂度较低。

阅读以下代码，下面哪一项是正确的？

01void processData() {
02    stack<int> s;
03    queue<int> q;
04    for (int i = 1; i <= 5; ++i) {
05        s.push(i);
06        q.push(i);
07    }
08    while (!s.empty()) {
09        cout << "Stack pop: " << s.top() << endl;
10        s.pop();
11    }
12    while (!q.empty()) {
13        cout << "Queue pop: " << q.front() << endl;
14        q.pop();
15    }
16}

栈中元素的插入和删除操作都在栈的顶端进行，所以方便用单向链表实现。

栈中元素的插入和删除操作都在栈的顶端进行，所以方便用双向链表比单向链表更合适实现。

以下代码判断括号是否匹配，请在横线处填入代码。

01bool isBalanced(string s) {
02    stack<char> st;
03    for (char c : s) {
04        if (c == '(' || c == '[' || c == '{') {
05            st.push(c);
06        } else {
07            if (st.empty()) return false; // 无括号匹配
08            char top = st.top();
09            st.pop();
10            if ((c == ')' && top != '(') ||
11                (c == ']' && top != '[') ||
12                (c == '}' && top != '{')) {
13                return false;
14            }
15        }
16    }
17    return ____________; // 在此处填入代码
18}

以下关于栈和队列的代码，执行后输出是（）。

01stack<int> s;
02queue<int> q;
03
04for (int i = 1; i <= 3; ++i) {
05    s.push(i);
06    q.push(i);
07}
08cout << s.top() << " " << q.front() << endl;

栈的操作特点是（）。

在 C++ STL 中，栈（std::stack）的 pop 操作返回栈顶元素并移除它。

某文本编辑器把用户输入的字符依次压入栈 S。用户依次输入 A、B、C、D 后，用户按了两次撤销（每次撤销，弹出栈顶一个字符）。此时栈从栈底到栈顶的内容是（）。

函数调用管理可用栈来管理。

在以下计算机系统应用场景中，最适合使用循环队列的是（）。

某文本编辑器把用户输入的字符依次压入栈 S 。用户依次输入 X, Y, Z, W 后，连续执行两次撤销操作。每次撤销都会弹出栈顶一个字符。此时栈从栈底到栈顶的内容是（ ）。

在 C++ STL 中， stack 的 pop() 函数会返回栈顶元素并将其删除。

递归调用在运行时会由于层数过多导致程序崩溃，可以通过循环配合栈缓解这一问题。

$n$ 个不同元素依次入栈的出栈序列数与将 $n$ 个不同元素划分成若干非空子集的方案数相等。

将$4$个元素按 1,2,3,4的顺序入栈，在该过程中可随时插入出栈操作。下列序列中不可能作为出栈序列的是（ ）。