灵神常见算法

2019

无

2020

第 11 题

下图中所使用的数据结构是（ )。

A. 栈

B. 队列

C. 二叉树

D. 哈希表

选A。先入后出，是栈。

2021

第 5 题

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

A. a,b,c,d,e

B. e,d,c,b,a

C. b,a,c,d,e

D. c,d,a,e,b

选D。

flowchart LR AA("出栈顺序 --- ​ 栈") --> A(" --- ​ c ​ b a") -->|c出栈| B("c --- ​ b a") -->|d入栈| C("c --- ​ d ​ b a") -->|d出栈| D("c d --- ​ b ​ a") --> |a出栈| E(a不在栈顶,错误)

flowchart LR
     AA("出栈顺序
      ---
          栈") --> 
      A("
      ---
          c
        b
        a") -->|c出栈| B("c
        ---
        b
        a") -->|d入栈| C("c
        ---
        d
        b
        a") -->|d出栈| D("c d
        ---
        b
        a") --> |a出栈| E(a不在栈顶,错误)

2022

第 2 题

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

A. 5 4 3 6 1 2

B. 4 5 3 1 2 6

C. 3 4 6 5 2 1

D. 2 3 4 1 5 6

选C。

graph LR A("3 4 5 6") -->|弹出3| B("4 5 6") -->|弹出4| C("5 6") -->|弹出6| D[6出不来] style D fill:#bbf,stroke:#f66,stroke-width:2px,color:#fff,stroke-dasharray: 5 5

graph LR
      A("3
            4
            5
            6") -->|弹出3| B("4
            5
            6") -->|弹出4| C("5
            6") -->|弹出6| D[6出不来]

 style D fill:#bbf,stroke:#f66,stroke-width:2px,color:#fff,stroke-dasharray: 5 5

第 5 题

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

A. 2

B. 3

C. 4

D. 6

选B。出队列的顺序跟进队列的顺序一样，跟第2题差不多，出队列Q的顺序看作出栈S的顺序即可。
栈容量最多为3。

graph LR A("e2 e1") -->|弹出e2| B("e4 e3 e1") -->|弹出e4| C("e3 e1") -->|弹出e3, e5 e6进栈| D("e6 e5 e1") -->|依次弹出e6 e5 e1| empty

graph LR
      A("e2
            e1") -->|弹出e2| B("e4
            e3
            e1") -->|弹出e4| C("e3
            e1") -->|弹出e3, e5 e6进栈| D("e6
            e5
            e1") -->|依次弹出e6 e5 e1| empty

第 10 题

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

A. 图的深度优先遍历算法常使用的数据结构为栈。

B. 栈的访问原则后进先出，队列的访问原则是先进先出。

C. 队列常常被用于广度优先搜索算法。

D. 栈与队列存在本质不同，无法用栈实现队列。

选D。虽然本质不同，但是勉强能用，比较麻烦，用两个栈就能实现。

• 入第1个栈，变成倒序。
• 入第2个栈，倒序反过来，就变回原来的顺序。