该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

一、选择题

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

{{ select(1) }}

• a, b, c, d, e
• e, d, c, b, a
• b, a, c, d, e
• c, d, a, e, b

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

{{ select(2) }}

• $**a+bcd$
• $abc+*d*$
• $abc+d**$
• $*a*+bcd$

3. 链表不具有的特点是（）。

{{ select(3) }}

• 可以随机访问任一元素
• 不必事先估计储存空间
• 插入删除不需要移动元素
• 所需空间与线性长度成正比

4. 下图的过程符合哪个数据结构？

{{ select(4) }}

• 栈
• 队列
• 二叉树
• 哈希表

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

{{ select(5) }}

• a, b, c, d, e, f, g
• a, b, c, d, e, g, f
• a, d, b, c, g, f, e
• g, f, e, d, c, b, a

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

{{ select(6) }}

• he->next = s;
• s->next = hs; hs = s;
• s->next = hs->next; hs->next = s;
• s->next = hs; hs = hs->next;

7. 线性表若采用链表储存结构，要求内存中可用储存单元地址（）。

{{ select(7) }}

• 必须连续
• 部分地址必须连续
• 一定不连续
• 连续不连续均可

8. 今有一个空栈 $S$，对下列待进栈的数据元素序列 a, b, c, d, e, f 依次进行进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈$S$ 的栈顶元素为（）。

{{ select(8) }}

• $f$
• $c$
• $a$
• $b$

9.（ ）是一种先进先出的线性表。

{{ select(9) }}

• 栈
• 队列
• 哈希表（离散表）
• 二叉树

10. 如果一个栈初始为空，且当前栈中的元素从栈底到栈顶依次是 a, b, c,另有元素 $d$ 已经出栈，则可能的入栈顺序是（）。

{{ select(10) }}

• a, d, c, b
• b, a, c, d
• a, c, b, d
• d, a, b, c

11. 广度优先搜索时，需要用到的数据结构是（）。

{{ select(11) }}

• 链表
• 队列
• 栈
• 离散表

12. 在含有 $n$ 个元素的双向链表中，查询是否存在关键字为 $k$ 的元素，最快情况下运行时间复杂度是（）。

{{ select(12) }}

• $O(1)$
• $O(logn)$
• $O(n)$
• $O(nlogn)$

13. 前缀表达式 $+3*2+5\ 12$ 的值是（）。

{{ select(13) }}

• $23$
• $25$
• $37$
• $65$

14. 有六个元素 FEDCBA从左至右依次顺序进栈，在进栈过程中会有元素被弹出栈。问下列哪一个不可能是合法的出栈序列？

{{ select(14) }}

• EDCFAB
• DECABF
• CDFEBA
• BCDAEF

15. 设栈 $S$ 的初始状态为空，元素 a, b, c, d, e, f 以此入栈 $S$，出栈的序列为 b, d, f, e, c, a, 则栈 $S$ 的容量至少应该是（）。

{{ select(15) }}

• $6$
• $5$
• $4$
• $3$

16. 地面上有标号 A、B、C 的三根柱，在 $A$ 柱上放有 $10$ 个直径相同中间有孔的圆盘，从上到下依次编号为 $1,2,3,...$, 将 $A$ 柱上的部分盘子经过 $B$ 柱子移入 $C$ 柱，也可以在 $B$ 柱上暂存。如果 $B$ 柱上的操作记录为 进、进、出、进、进、出、出、进、进、出、进、出、出。那么，在 $C$ 柱上，从下到上的编号为（）。

{{ select(16) }}

• 2 4 3 6 5 7
• 2 4 1 2 5 7
• 2 4 3 1 7 6
• 2 4 3 6 7 5