课堂练习

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

A.哈希表 B.栈 C.队列 D.二叉树 【答案】B 【分析】图中描述的是一个后进先出的容器表达，因此是栈。

2. 【NOIP2008】设栈S的初始状态为空，元素a,b,c,d,e,f依次入栈S，出栈的序列为b,d,f,e,c,a，则栈S的容量至少应该是( )。 A.6 B.5 C.4 D.3 【答案】C 【分析】满足"后进先出"原则，栈最多元素时是4个，从上到下依次为f,e,c,a。

3. 【NOIP2009】有六个元素FEDCBA从左至右依次顺序进栈，在进栈过程中会有元素被弹出栈。下列不可能是合法出栈序列的是( )。 A. EDCFAB B. DECABF C. CDFEBA D.BCDAEF 【答案】C 【分析】C选项中当C出栈，此时F是被压在E下，不可能先于E出栈。

4. 【NOIP2010】元素 R1,R2,R3,R4,R5入栈的顺序为R1,R2,R3,R4,R5。如果第一个出栈的是R3，那么第5个出栈的不可能是( )。 A.R1 B.R2 C.R4 D.R5 【答案】B 【分析】R3出栈时，R2为栈顶，R1在R2之下，肯定晚于R2之后出栈，R2不可能最后一个出栈，自然不会是第5个出栈。

5. 【NOIP2012】如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a,b,c(如右图所示)，另有元素d已经出栈，则可能的入栈顺序是( )。 A.a,d,c,b B.b,a,c,d C.a,c,b,d D.d,a,b,c 【答案】D 【分析】栈的性质决定了栈里面三个元素的相对入栈顺序是a,b,c，结合四个选项，只有D选项符合a,b,c三个元素的相对位置。

6. 【NOIP2015】今有一空栈S，对下列待进栈的数据元素序列a,b,c,d,e,f依次进行进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈S的栈顶元素为( )。 A.f B.c C.a D.b 【答案】B 【分析】按照题目意思模拟操作可得栈顶元素为c。

7. 【NOIP2017】表达式a*(b+c)d的后缀形式是( )。 A.abcd+* B.abc+d C.a*bc+*d 【答案】B 【分析】通过加括号和去括号的方法求解，后缀形式为abc+d。

8. 【NOIP2017】对于入栈顺序为a,b,c,d,e,f,g的序列，下列不可能是合法的出栈序列的是( )。 A. a,b,c,d,e,f,g B.a,d,c,b,e,g,f C.a,d,b,cg,fe D.g,fye,d,c,b,a 【答案】C 【分析】考查栈的相关知识，C选项中b比c先入栈，不可能比c先出栈。

9. 【NOIP2011】广度优先搜索时，需要用到的数据结构是( )。 A.链表 B.队列 C.栈 D.散列表 【答案】B 【分析】广度优先搜索使用的数据结构是队列。

10. 【NOIP2017】向一个栈顶指针为hs的链式栈中插入一个指针s指向的结点时，应执行( )。 A. hs -> next =s; B.s->next=hs;hs=s; C.s-next=hs-next;hs->next=s; D.s-next=hs;hs=hs->next; 【答案】B 【分析】栈顶为hs，插入s时，先将s的下一个节点指向hs，再把hs指向s。

11. 【NOIP2012】( )是一种先进先出的线性表。 A.栈 B.队列 C.哈希表(散列表) D.二叉树 【答案】B 【分析】队列是先进先出的线性表。

不定项选择题

1. 【NOIP2010】元素R1,R2,R3,R4,R5入栈的顺序为R1,R2,R3,R4,R5。如果第1个出栈的是R3，那么第5个出栈的可能是( )。 A.R1 B.R2 C.R4 D.R5 【答案】ACD 【分析】栈的特点是先进后出，R1比R2先进，在R2后出栈，所以第5个出栈不可能是R2。

2. 【NOIP2012】如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a,b,c(如右图所示)，另有元素d已经出栈，则可能的入栈顺序有( )。 A.a,b,c,d B.b,a,c,d C.a,c,b,d D.d,a,b,c 【答案】AD 【分析】栈中元素相对入栈顺序是a,b,c，A、D选项符合。

3. 【NOIP2017】对于入栈顺序为a,b,c,d,e,f,g的序列，下列( )不可能是合法的出栈序列。 A.a,b,c,d,e,f,g C.a,d,b,c,g,f,e B.a,d,c,b,e,g,f D.g,f,e,d,c,b,a 【答案】C 【分析】C选项中b比c先入栈，不可能比c先出栈。