第 1 题

元素按 1,2,3,4,5 的顺序入栈，并可在任意时刻出栈。下列哪个序列不可能成为出栈顺序？

{{ select(1) }}

• 2,1,4,3,5
• 3,2,1,5,4
• 3,1,2,5,4
• 1,2,5,4,3

---

第 2 题

元素按 1,2,3,4,5,6 的顺序入栈。若出栈顺序为 3,2,5,6,4,1，模拟过程中栈内元素个数的最大值是多少？（只填数字）

{{ input(2) }}

---

第 3 题

从左到右检查字符串 ([{}])([)]。位置从 1 开始编号，第一次能够确定括号序列不合法的是第几个字符？（只填数字）

{{ input(3) }}

---

第 4 题

写出程序的输出结果：

stack<int> st;
queue<int> q;
int a[6] = {3, 8, 5, 2, 7, 4};
for (int x : a) {
    if (x % 2) st.push(x);
    else {
        if (!st.empty()) {
            q.push(st.top() + x);
            st.pop();
        }
    }
}
while (!q.empty()) {
    cout << q.front() << " ";
    q.pop();
}

{{ input(4) }}

---

第 5 题

后缀表达式 8 3 2 * - 4 + 的值是多少？（只填数字）

{{ input(5) }}

---

第 6 题

写出程序的输出结果：

void f(int n) {
    if (n <= 0) return;
    cout << n;
    f(n - 2);
    cout << n;
}
f(5);

{{ input(6) }}

---

第 7 题

队列初始为 2,4,6,8（左端为队首）。重复两次操作：取出队首元素 $x$，把 $x+1$ 加入队尾。操作结束后，队列从队首到队尾依次是什么？（数字间用一个空格）

{{ input(7) }}

---

第 8 题

长度为 10 的循环队列用 head 指向队首、tail 指向下一个可插入位置，并约定牺牲一个位置区分空与满。若 head=7, tail=2，队列中有几个元素？（只填数字）

{{ input(8) }}

---

第 9 题

上述循环队列已满时应满足哪个条件？

{{ select(9) }}

• head == tail
• (tail + 1) % 10 == head
• tail + 1 == head
• (head + 1) % 10 == tail

---

第 10 题

括号匹配程序读到右括号 c 时，下面哪组检查顺序正确？

{{ select(10) }}

• 先读取栈顶，再判断空栈，再比较类型
• 先弹栈，再比较类型
• 先判断空栈，再比较栈顶类型，匹配后弹栈
• 只比较左右括号总数

---

第 11 题

用队列进行分层搜索时，为什么先发现的状态通常先处理？

{{ select(11) }}

• 队列后进先出
• 队列先进先出，能维持按层扩展的次序
• 队列会自动排序
• 队列能去除所有重复状态

---

第 12 题

对长度为 $n$ 的括号串进行一次从左到右的栈匹配，时间复杂度和额外空间复杂度在最坏情况下分别是（ ）。

{{ select(12) }}

• $O(n),O(1)$
• $O(n),O(n)$
• $O(n^2),O(n)$
• $O(\log n),O(n)$

---