CSP初赛第15节栈和队列

您的姓名：



一、单项选择题（共11题，每题5分，共计55分;每题有且仅有一个正确选项）

1.下图中所使用的数据结构是（）。
*

A.哈希表

B.栈

C.队列

D.二叉树

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

A. 6

B. 5

C. 4

D. 3

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

A.EDCFAB

B.DECABF

C.CDFEBA

D.BCDAEF

4.元素R1、R2 、R3、R4、R5入栈的顺序为R1 、R2、R3 、R4 、R5。如果第1个出栈的是R3 ，那么第5个出栈的不可能是（）。

A. R1

B. R2

C. R4

D. R5

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

A.a, d, c, b

B.b, a, c, d

C.a, c, b, d

D.d, a, b, c

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

A.f

B.c

C.a

D.b

7.表达式a * (b + c) * d 的后缀形式是（）。

A. a b c d * + *

B. a b c + * d *

C. a * b c + * d

D. b + c * a * d

8.对于入栈顺序为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, c, g, f, e

D. g, f, e, d, c, b, a

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

A. 链表

B. 队列

C. 栈

D. 散列表

10.向一个栈顶指针为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;

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

A.栈

B.队列

C.哈希表(散列表)

D.二叉树

二、不定项选择题（共3题，每题5分，共计15分;每题有一个或多个正确选项，多选或少选均不得分）

1.元素R1、R2 、R3、R4、R5入栈的顺序为R1 、R2、R3 、R4 、R5。如果第1个出栈的是R3 ，那么第5个出栈的可能是（）。【多选题】

A.R1

B.R2

C.R4

D.R5

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

【多选题】

A.a, b, c, d