栈

1

以下是一个错误的伪代码，该算法本应判断括号序列是否平衡：

创建一个字符栈
while(还有输入可用) {
    读取一个字符
    if(该字符是 '(')
        将其压入栈中
    else if(该字符是 ')' 且栈不为空)
        弹出栈顶字符
    else
        打印 "unbalanced" 并退出
}
打印 "balanced"

上述代码会将下列哪个不平衡序列误判为平衡？（ ）

正确答案：A
  • 关键问题：在 while 循环结束后，必须检查栈是否为空。
  • 示例分析：对于输入 ((())，循环结束后栈不为空（剩余一个未匹配的 '('），但代码未执行此检查，导致误判为平衡。
2

使用一个单数组 A[1..MAXSIZE] 实现两个栈。这两个栈从数组的两端向中间增长。变量 top1 和 top2（top1 < top2）分别指向每个栈的栈顶元素位置。若要高效利用空间，则“栈满”的条件是（ ）：

正确答案：D

解释：

  • 该设计允许两个栈动态共享数组空间
  • 当 top1 = top2 - 1 时，表示两个栈顶指针相邻
  • 此时数组中已无可用空间（因 top1 < top2 的约束）
  • 其他条件均未体现双栈协同增长的特性
  • 该条件能最大化利用数组存储空间
3

评估一个没有嵌套函数调用的表达式时（ ）：

正确答案：B

任何表达式都可以转换为后缀或前缀形式。前缀和后缀表达式的计算可以通过单个栈完成。例如：给定表达式 ‘10 2 8 * + 3 -’，操作步骤如下：

  1. 将 10 压入栈
  2. 将 2 压入栈
  3. 将 8 压入栈
  4. 遇到运算符 ‘*’ 时，弹出 2 和 8，计算 2*8=16 后压入栈
  5. 遇到运算符 ‘+’ 时，弹出 16 和 10，计算 10+16=26 后压入栈
  6. 将 3 压入栈
  7. 遇到运算符 ‘-’ 时，弹出 26 和 3，计算 26-3=23 后压入栈

最终结果 23 是通过单个栈得到的。因此选项 (B) 正确。

4

计算后缀表达式 10 5 + 60 6 / * 8 - 的结果是（ ）：

正确答案：C

步骤 1：后缀表达式求值规则
操作数（数字）被压入栈中。遇到运算符时，从栈中弹出所需数量的操作数，执行运算，并将结果重新压入栈中。

步骤 2：逐步求值
表达式：10 5 + 60 6 / ∗ 8 −

  • 压入 10：栈 = [10]
  • 压入 5：栈 = [10, 5]
  • 遇到 +：弹出 10 和 5，相加：10+5=15。将结果压入栈：栈=[15]
  • 压入 60：栈 = [15, 60]
  • 压入 6：栈 = [15, 60, 6]
  • 遇到 /：弹出 60 和 6，相除：60/6=10。将结果压入栈：栈=[15,10]
  • 遇到 *：弹出 15 和 10，相乘：15×10=150。将结果压入栈：栈=[150]
  • 压入 8：栈 = [150, 8]
  • 遇到 -：弹出 150 和 8，相减：150−8=142。将结果压入栈：栈=[142]

步骤 3：栈中的最终结果
最终结果为 142

5

假设使用链表而非数组实现一个栈。对于使用链表实现的栈（假设实现方式高效），其入栈和出栈操作的时间复杂度会受到什么影响？

正确答案：B
  • 插入操作（入栈）：在链表头部插入新节点时，仅需修改头指针和新节点的引用关系，无需遍历链表，因此时间复杂度为 O(1)。
  • 删除操作（出栈）：移除链表头部节点时，同样只需调整头指针指向下一个节点，操作时间为 O(1)。
  • 链表实现栈的核心优势在于始终在头部进行操作，避免了尾部操作所需的遍历开销。
6

考虑有 n 个元素均匀分布在 k 个栈中。每个栈中的元素按升序排列（每个栈的顶部是最小值，向下依次递增）。

现有一个容量为 n 的队列，需要将所有 n 个元素按升序放入其中。已知最优算法的时间复杂度是多少？（ ）

正确答案：A

  • 核心思路：构建大小为 k 的最小堆

    1. 初始阶段将所有栈顶元素加入堆（共 k 个元素）
    2. 每次从堆中提取最小值后，从对应栈取出下一个元素并重新插入堆
    3. 重复此过程直至所有元素入队

  • 时间复杂度分析：

    • 堆初始化：$O(k)$
    • 后续操作：每轮堆操作耗时 $O(\log k)$，共需执行 $n - k$ 次
    • 总时间复杂度：$O(k) + (n - k)\log k = O(n \log k)$
7

假设输入序列是 5, 6, 7, 8, 9（按此顺序），以下哪种排列可以通过栈操作得到相同的顺序？（ ）

正确答案：C

选项 (C) 的解析说明

  • 该序列可通过以下栈操作实现：
    • Push 5
    • Push 6
    • Push 7
    • Pop 7
    • Push 8
    • Pop 8
    • Push 9
    • Pop 9
    • Pop 6
    • Pop 5
  • 栈遵循先进后出原则，上述操作严格满足输入顺序与输出序列的匹配关系
  • 最终输出结果为 7, 8, 9, 6, 5
8

检查算术表达式中括号是否匹配的最佳数据结构是（ ）

正确答案：B
  • 原因：栈的后进先出（LIFO）特性与括号匹配需求高度契合
  • 操作流程：
    1. 遇到左括号 ( 时，将其压入栈
    2. 遇到右括号 ) 时，检查栈顶元素是否为对应左括号
    3. 若栈为空或类型不匹配，则括号不匹配
    4. 表达式处理完成后，若栈为空则表示完全匹配
  • 优势对比：
    • 队列（FIFO）无法保证最近左括号优先匹配
    • 树/列表缺乏顺序性约束，需额外维护索引
9

如果在栈上执行以下操作序列：push(1)、push(2)、pop、push(1)、push(2)、pop、pop、pop、push(2)、pop，那么弹出值的顺序是（ ）：

正确答案：A

解析过程：

  1. Push(1) → 栈 = [1]
  2. Push(2) → 栈 = [1, 2]
  3. Pop → 弹出 2，栈 = [1]
  4. Push(1) → 栈 = [1, 1]
  5. Push(2) → 栈 = [1, 1, 2]
  6. Pop → 弹出 2，栈 = [1, 1]
  7. Pop → 弹出 1，栈 = [1]
  8. Pop → 弹出 1，栈 = []
  9. Push(2) → 栈 = [2]
  10. Pop → 弹出 2，栈 = []

最终弹出顺序： 2, 2, 1, 1, 2

10

考虑以下对一个大小为 5 的栈执行的操作：Push(a)；Pop()；Push(b)；Push(c)；Pop()；Push(d)；Pop()；Pop()；Push(e)。以下哪项陈述是正确的？（ ）

正确答案：B

解析

  • 初始空栈容量为 5
  • 操作序列分析：
    1. Push(a) → [a]
    2. Pop() → []
    3. Push(b) → [b]
    4. Push(c) → [b, c]
    5. Pop() → [b]
    6. Push(d) → [b, d]
    7. Pop() → [b]
    8. Pop() → []
    9. Push(e) → [e]
  • 所有操作均未超出栈容量限制
  • 最终栈状态为 [e]
  • 因此选项 (B) 正确，栈操作顺利执行
11

以下哪项不是栈的固有应用？（ ）

正确答案：C
  • 栈的典型应用场景包括：
    • 字符串反转（D）
    • 后缀表达式求值（B）
    • 递归函数调用（A）
  • 作业调度（C）通常由操作系统中的队列管理，而非栈结构
  • 因此选项 C 不属于栈的固有应用
12

考虑以下在空栈上的操作序列：

Push(54);
Push(52);
Pop();
Push(55);
Push(62);
s = Pop();

考虑以下在空队列上的操作序列：

Enqueue(21);
Enqueue(24);
Dequeue();
Enqueue(28);
Enqueue(32);
q = Dequeue();

s + q 的值是（  ）。

正确答案：A

我们构建一个空栈并执行操作。栈遵循后进先出（LIFO）顺序：

  • Push(54) // (54)
  • Push(52) // (54,52)
  • Pop() // (54)
  • Push(55) // (54,55)
  • Push(62) // (54,55,62)
  • s = Pop() // (54,55) s=62

我们构建一个空队列并执行操作。队列遵循先进先出（FIFO）顺序：

  • Enqueue(21) // [21]
  • Enqueue(24) // [21,24]
  • Dequeue() // [24]
  • Enqueue(28) // [24,28]
  • Enqueue(32) // [24,28,32]
  • q = Dequeue() // [28,32] q=24

因此，s + q = 62 + 24 = 86。

另一种方式：

  • 栈是后进先出的数据结构，因此 s = Pop() = 62
  • 队列是先进先出的数据结构，因此 q = Dequeue() = 24
  • 所以 s + q = 62 + 24 = 86。
13

以下关于使用链表实现栈的说法中，哪一项是正确的？（ ）

正确答案：D

为了保持后进先出（LIFO）的顺序，可以使用链表以两种方式实现栈：

  • a) 在 push 操作中，如果新节点插入到链表的开头，则在 pop 操作中必须从开头删除节点。
  • b) 在 push 操作中，如果新节点插入到链表的末尾，则在 pop 操作中必须从末尾删除节点。
14

堆栈 A 中包含元素 a、b、c（a 在顶部），堆栈 B 为空。从堆栈 A 弹出的元素可以立即打印或压入堆栈 B，而从堆栈 B 弹出的元素只能被打印。在这种安排下，以下哪个排列顺序不可能实现？（ ）

正确答案：C

  • 选项 (A):

    1. 从堆栈 A 弹出 a
    2. 将 a 压入堆栈 B
    3. 打印 b
    4. 从堆栈 B 弹出 a 并打印
    5. 从堆栈 A 弹出 c 并打印
      输出顺序：b a c

  • 选项 (B):

    1. 从堆栈 A 弹出 a
    2. 将 a 压入堆栈 B
    3. 从堆栈 A 弹出 b 并打印
    4. 从堆栈 A 弹出 c 并打印
    5. 从堆栈 B 弹出 a 并打印
      输出顺序：b c a

  • 选项 (C):

    1. 从堆栈 A 弹出 a → 压入堆栈 B
    2. 从堆栈 A 弹出 b → 压入堆栈 B
    3. 从堆栈 A 弹出 c → 直接打印
      此时堆栈 B 内容为 [a, b]（a 在顶部）
      后续操作限制：
    • 必须先弹出 b 才能弹出 a
    • 导致输出顺序为 c b a 或 c a b（需先弹出 b）
      因此 c a b 无法实现

  • 选项 (D):

    1. 从堆栈 A 依次弹出 a → 打印
    2. 弹出 b → 打印
    3. 弹出 c → 打印
      输出顺序：a b c
15

将五个元素 A、B、C、D 和 E 依次入栈（从 A 开始）。随后将栈中弹出四个元素并依次插入队列。接着从队列中删除两个元素并重新压入栈。此时从栈中弹出一个元素，该元素是（ ）：

正确答案：D

  • 当五个元素 A、B、C、D 和 E 依次入栈时：
    栈的顺序为：A、B、C、D、E（A 在底部，E 在顶部）

  • 弹出四个元素并插入队列后：
    队列的顺序为：B、C、D、E（B 在队尾，E 在队首）
    弹出操作后的栈仅剩：A

  • 从队列中删除两个元素并重新压入栈后：
    新栈的顺序为：A、E、D（A 在底部，D 在顶部）

  • 最终操作结果：
    由于 D 位于栈顶，因此弹出操作会取出 D

所以，正确选项是 (D)。

16

考虑以下陈述：

i. 先进先出（FIFO）类型的计算通过栈（STACKS）可以高效支持。
ii. 在链表上实现列表（LISTS）比在数组上实现列表对于几乎所有基本列表操作都更高效。
iii. 在循环数组上实现队列（QUEUES）比在使用两个索引的线性数组上实现队列更高效。
iv. 后进先出（LIFO）类型的计算通过队列（QUEUES）可以高效支持。

以下哪项是正确的？（ ）

正确答案：C

正确陈述是：iii. 在循环数组上实现队列比在使用两个索引的线性数组上实现队列更高效。
解释：

  • i. 错误：栈（STACKS）支持 LIFO 操作，而非 FIFO。FIFO 由队列（QUEUES）实现。
  • ii. 错误：链表在插入/删除操作上更高效，但随机访问不如数组高效。
  • iii. 正确：循环数组通过索引环绕机制提升队列操作效率。
  • iv. 错误：队列（QUEUES）实现 FIFO，LIFO 由栈（STACKS）实现。

综上，选项 (C) 是正确答案。

17

实现一个队列所需的最小栈数量是（ ）

正确答案：C

实现原理：

  • 使用两个栈 S₁ 和 S₂
  • 新元素入队时，压入 S₁ 栈顶
  • 出队操作时：
    • 若 S₂ 为空，则将 S₁ 所有元素依次弹出并压入 S₂
    • 直接弹出 S₂ 栈顶元素（即队首）

时间复杂度分析：

  • 入队操作：O(1)
  • 出队操作：均摊 O(1)（每个元素最多被压入/弹出两次）

结论：
通过这种双栈结构，既能保证先进先出的队列特性，又能达到最优的时间效率。因此最少需要 2 个栈 实现队列，选项 (C) 正确。

18

使用逆波兰表示法在栈机器上计算表达式 (A * B) + (C * D / E) 需要多少次 PUSH 和 POP 操作？（ ）

正确答案：B

逆波兰表示法是一种无需括号或特殊标点的公式表示方法。
计算 (A ∗ B) + (C ∗ D / E) 的过程如下：

  1. 去除括号和标点，将其转换为后缀形式 AB+CDE/*+
  2. 将 AB 压入栈 → 执行 * 操作时弹出 AB 并计算 A*B，将结果（设为 X）重新压入栈
  3. 将 CDE 压入栈 → 执行 / 操作时弹出 DE 并计算 C*D/E，将结果（设为 Y）重新压入栈
  4. 执行 * 操作时弹出 CY 并计算 Y*C，将结果（设为 Z）重新压入栈
  5. 最后执行 + 操作时弹出 XZ 并计算 X+Z，将最终结果压入栈
    上述计算过程共包含 5 次 PUSH 和 4 次 POP 操作。因此选项 (B) 正确。