niusouti.com

已知栈S 初始为空,用 I 表示入栈、O表示出栈,若入栈序列为a1a2a3a4a5,则通过栈 S 得到出栈序列a2a4a5a3a1的合法操作序列( )。A.IIOIIOIOOOB.IOIOIOIOIOC.IOOIIOIOIOD.IIOOIOIOOO

题目

已知栈S 初始为空,用 I 表示入栈、O表示出栈,若入栈序列为a1a2a3a4a5,则通过栈 S 得到出栈序列a2a4a5a3a1的合法操作序列( )。

A.IIOIIOIOOOB.IOIOIOIOIOC.IOOIIOIOIOD.IIOOIOIOOO


相似考题
更多“已知栈S 初始为空,用 I 表示入栈、O表示出栈,若入栈序列为a1a2a3a4a5,则通过栈 S 得到出栈序列a2a ”相关问题
  • 第1题:

    若pllsh、pop分别表示入栈、出栈操作,初始栈为空且元素1、2、3依次进栈,则经过操作序列push、push、pop、pop、push、pop之后,得到的出栈序列为 ______。

    A.321

    B.213

    C.231

    D.123

    A.

    B.

    C.

    D.


    正确答案:B

  • 第2题:

    对于初始为空的栈S,入栈序列为a、b、c、d,且每个元素进栈、出栈各1次。若出栈的第一元素为d,则合法的出栈序列为()。

    A.dcba

    B.dabc

    C.dcab

    D.dbca


    正确答案:A

  • 第3题:

    设有初始为空的栈S,对于入栈序列a b c d e f, 经由进栈、进栈、出栈、进栈、进栈、出栈的操作后,栈顶和栈底元素分别为( )。

    A.c和bB.b和aC.c和aD.d 和b


    正确答案:C

  • 第4题:

    设有初始力空的栈s,对于入栈序列a、b、c、d,经由一个合法的进栈和出栈操作序列后(每个元素迸栈、出栈各1次),以c作为第一个出栈的元素时,不能得到的序列为( )。

    A.c d b aB.c b d aC.c d a bD.c b a d


    正确答案:C

  • 第5题:

    对于初始为空的栈S,入栈序列为a、b、c、d,且每个元素进栈、出栈各1次。若出栈的第一元素为d,则合法的出栈序列为( )。

    A. d c b a
    B. d a b c
    C. d c a b
    D. d b c a

    答案:A
    解析:

  • 第6题:

    设有初始为空的栈S,对于入栈序列a、b、c,经由一个合法的进栈和出栈操作序列后(每个元素进栈、出栈各1次),不能得到的序列为( ).

    A.abc
    B.acb
    C.cab
    D.Cba

    答案:C
    解析:
    C中cba意味着c先出栈,此时b与a仍在栈中,按照先进后出的原则,这时候只能是按照ba出栈。

  • 第7题:

    对于初始为空的栈S,入栈序列为a、b、c、d,且每个元素进栈、出栈各1次。若出栈序列的第一个元素为d,则合法的出栈序列为( )

    A.d c b a
    B.d a b c
    C.d c a b
    D.d b c a

    答案:A
    解析:
    题干要求d第一个出栈,所以入栈的次序为a,b,c,d,栈的特点是先进后出的,如下图所示,且每个元素进栈、出栈各1次,所以出栈序列为d,c,b,a。

  • 第8题:

    对于初始为空的栈S,入栈序列为a、b、c、d、e,且每个元素进栈、出栈各1次。则不合法的出栈序列为( )

    A.a b c d e
    B.e d c b a
    C.e d a b c
    D.a c b e d

    答案:C
    解析:
    栈的特点是先进后出的,如下图所示,且每个元素进栈、出栈各1次,经分析e第一个出栈,d第二个出栈的话,后面只能跟c,不可能跟a。

  • 第9题:

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

    • A、6
    • B、5
    • C、4
    • D、3

    正确答案:C

  • 第10题:

    若序列a、b、c、d、e按顺序入栈,假设P表示入栈操作,S表示出栈操作,则操作序列PSPPSPSPSS后得到的输出序列为()


    正确答案:acdeb

  • 第11题:

    问答题
    设将整数1,2,3,4依次进栈,但只要出栈时栈非空,则可将出栈操作按任何次序夹入其中,请回答下述问题: (1)若入、出栈次序为Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop(),则出栈的数字序列为何?(这里Push(i)表示i进栈,Pop()表示出栈) (2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。 (3)请分析1,2,3,4的24种排列中,哪些序列是可以通过相应的入出栈操作得到的。

    正确答案: (1)出栈序列为:1324
    (2)不能得到1423序列。因为要得到14的出栈序列,则应做
    Push(1),Pop(),Push(2),Push(3),Push(4),Pop()。这样,3在栈顶,2在栈底,所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为:Push(1),Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。
    (3)在1,2,3,4的24种排列中,可通过相应入出栈操作得到的序列是:1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321
    不能得到的序列是:
    1423,2413,3124,3142,3412,4123,4132,4213,4231,4312
    解析: 暂无解析

  • 第12题:

    填空题
    若序列a、b、c、d、e按顺序入栈,假设P表示入栈操作,S表示出栈操作,则操作序列PSPPSPSPSS后得到的输出序列为()

    正确答案: acdeb
    解析: 暂无解析

  • 第13题:

    已知栈S初始为空,对于一个符号序列a1a2a3a4a5(入栈次序也是该次序),当用I表示入栈、O表示出栈,则通过栈S得到符号序列a2a4a5a3a1的操作序列为______。

    A.I O I I O O I O O I

    B.I I O I O I O I O O

    C.I O O I I O I O I O

    D.I I O I I O I O O O

    A.

    B.

    C.

    D.


    正确答案:D

  • 第14题:

    设初始栈为空,s表示入栈操作,x表示出栈操作,则(33)是合法的操作序列。

    A.sxxsssxxx

    B.xxssxxss

    C.sxsxssxx

    D.xssssxxx


    正确答案:C
    解析:本题考查数据结构中栈的基本知识。
    栈是操作受限的线性表,其特点是后进先出。应用中可将栈看作一个桶状的容器,当栈中有元素时,栈顶元素先出栈,栈为空时进行出栈操作是不正确的。因此,对于一个关于初始为空的栈的操作序列,要求序列中任何一个操作之前,入栈操作的次数要大于等于出栈操作的次数。题目选项中仅操作序列SXSXSSXX满足该要求。

  • 第15题:

    设有初始为空的栈S,对于入栈序列a、b、c,经由一个合法的进栈和出栈操作序列后(每个元素进栈、出栈各1次),不能得到的序列为( )。

    A.abcB.acb C.cab D.Cba


    正确答案:C

  • 第16题:

    ●设push、pop分别表示入栈、出栈操作,若初始栈为空,对于元素序列a b c,

    则操作序列push、pop、pop、push、push、pop (36)。

    (36)

    A.得到出栈序列为abc

    B.得到出栈序列为bac

    C.得到出栈序列为bca

    D.是非法的操作序列


    正确答案:D

  • 第17题:

    用s表示入栈操作,*表示出栈操作,栈的初态、终态均为空,人栈和出栈的操作序列可表示成仅为由S和*组成的序列。下面的序列中合法的操作序列有()。

    A.S*SS*S**
    B.SSS****S
    C.S**S*SS*
    D.SSS*S*S*

    答案:A
    解析:
    要使栈的初态、终态均为空,入栈和出栈的操作次数应该相等,因此排除D项。而BC两项项都出现某一时刻栈已空的情况下执行出栈操作。

  • 第18题:

    对于初始为空的栈S,入栈序列为a、b、c,且每个元素进栈、出栈各1次。则不合法的出栈序列为( )。

    A.c b a
    B.c a b
    C.a b c
    D.b c a

    答案:B
    解析:
    栈的特点是先进后出的,如下图所示,且每个元素进栈、出栈各1次,经分析c第一个出栈的话,后面只能跟b,不可能跟a。所以B选项的出栈顺序是不合理的。

  • 第19题:

    对于初始为空的栈S,入栈序列为a、b、c、d,且每个元素进栈、出栈各1次。则不合法的出栈序列为( )

    A.d c b a
    B.a b c d
    C.d a b c
    D.b c d a

    答案:C
    解析:
    栈的特点是先进后出的,如下图所示,且每个元素进栈、出栈各1次,经分析d第一个出栈的话,后面只能跟c,不可能跟a。所以C选项的出栈顺序是不合理的。

  • 第20题:

    已知栈S初始为空,用I表示入栈、O表示出栈,若入栈序列为a1a2a3a4a5,则通过栈S得到出栈序列a2a4a5a3a1的合法操作序列(58)。

    A.IIOIIOIOOO
    B.IOIOIOIOIO
    C.IOOIIOIOIO
    D.IIOOIOIOOO

    答案:A
    解析:
    操作步骤:a1a2入,a2出,a3a4入,a4出,a5入,a5出,a3出,a1出。

  • 第21题:

    假设以S和X分别表示入栈和出栈的操作,则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列(例如,SXSX为合法序列,SXXS为非法序列)。试给出区分给定序列为合法序列或非法序列的一般准则,并证明:两个不同的合法(栈操作)序列(对同一输入序列)不可能得到相同的输出元素(注意:在此指的是元素实体,而不是值)序列。


    正确答案: 任何前n个序列中S的个数一定大于X的个数。
    设两个合法序列为:
    T.1=S……X……S……
    T.2=S……X……X……
    假定前n个操作都相同,从第n+1个操作开始,为序列不同的起始操作点。由于前n个操作相同,故此时两个栈(不妨为栈A、B)的存储情况完全相同,假设此时栈顶元素均为a。
    第n+1个操作不同,不妨T1的第n+1个操作为S,T2的第n+1个操作为X。T1为入栈操作,假设将b压栈,则T1的输出顺序一定是先b后a;而T2将a退栈,则其输出顺序一定是先a后b。由于T1的输出为……ba……,而T2的输出顺序为……ab……,说明两个不同的合法栈操作序列的输出元素的序列一定不同。

  • 第22题:

    设将整数1,2,3,4依次进栈,但只要出栈时栈非空,则可将出栈操作按任何次序夹入其中,请回答下述问题: (1)若入、出栈次序为Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop(),则出栈的数字序列为何?(这里Push(i)表示i进栈,Pop()表示出栈) (2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。 (3)请分析1,2,3,4的24种排列中,哪些序列是可以通过相应的入出栈操作得到的。


    正确答案:(1)出栈序列为:1324
    (2)不能得到1423序列。因为要得到14的出栈序列,则应做
    Push(1),Pop(),Push(2),Push(3),Push(4),Pop()。这样,3在栈顶,2在栈底,所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为:Push(1),Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。
    (3)在1,2,3,4的24种排列中,可通过相应入出栈操作得到的序列是:1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321
    不能得到的序列是:
    1423,2413,3124,3142,3412,4123,4132,4213,4231,4312

  • 第23题:

    单选题
    设栈S的初始状态为空,元素a,b,c,d,e,f依次入栈S,出栈的序列为b,d,f,e,c,a,则栈S的容量至少应该是()
    A

    6

    B

    5

    C

    4

    D

    3


    正确答案: D
    解析: 暂无解析