第二章 程序设计基本知识

第7节 栈和队列

1.【NOIP2013】 【NOIP2018】下图中所使用的数据结构是( )。

{{ select(1) }}

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

2.【NOIP2008】设栈S的初始状态为空，元素a,b,c,d,e,f依次入栈S,出栈的序列为b,d,f,e,c,a,则栈S的容量至少应该是()。

{{ select(2) }}

• 6
• 5
• 4
• 3

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

{{ select(3) }}

• EDCFAB
• DECABF
• CDFEBA
• BCDAEF

4.【NOIP2010】元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第一 个出栈的是R3,那么第5个出栈的不可能是( )。

{{ select(4) }}

• R1
• R2
• R4
• R5

5.【NOIP2012】如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a,b,c(如右图所示),另有元素d已经出栈，则可能的入栈顺序是( )。

{{ select(5) }}

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

6.【NOIP2015】今有一空栈S,对下列待进栈的数据元素序列a,b,c,d,e,f依次进行进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈S的栈顶元素为( )。

{{ select(6) }}

• f
• c
• a
• b

7.【NOIP2017】表达式a*(b+c)*d的后缀形式是( )。

{{ select(7) }}

• a b c d*+*
• a b c+*d *
• a*b c+*d
• b+c*a*d

8.【NOIP2017】对于入栈顺序为a,b,c,d,e,f,g的序列，下列()不可能是合法的出栈序列。

{{ select(8) }}

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

9.【NOIP2011】广度优先搜索时，需要用到的数据结构是( )。

{{ select(9) }}

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

10.【NOIP2017】 向一个栈顶指针为hs的链式栈中插入一个指针s 指向的结点时，应执行()。

{{ select(10) }}

• hs->next =S:
• S->next =hs;hs =s;
• s->next =hs->next;hs->next =s;
• s->next =hs;hs =hs->next;

11.【NOIP2012】( )是一种先进先出的线性表。

{{ select(11) }}

• 栈
• 队列
• 哈希表(散列表)
• 二叉树

不定项选择题

1.【NOIP2010】元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3,那么第5个出栈的可能是( )。

{{ multiselect(12) }}

• R1
• R2
• R4
• R5

2.【NOIP2012】如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a,b,c(如右图所示),另有元素d已经出栈，则可能的入栈顺序有( )。

{{ multiselect(13) }}

• a,b,c,d
• B.b,a,c,d
• a,c,b,d
• d,a,b,c

3.【NOIP2017】对于入栈顺序为a,b,c,d,e,f,g的序列，下列( )不可能是合法的出栈序列。

{{ multiselect(14) }}

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