数据结构

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

题目

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

如果没有搜索结果，请直接 联系老师 获取答案。
如果没有搜索结果，请直接 联系老师 获取答案。
相似问题和答案

第1题：

● 设初始栈为空，s 表示入栈操作，x表示出栈操作，则 （33） 是合法的操作序列。

（33）

A. sxxsssxxx

B. xxssxxss

C. sxsxssxx

D. xssssxxx


正确答案：C

第2题：

假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

①下面所示的序列中哪些是合法的?

A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO

②通过对①的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false(假定被判定的操作序列已存入一维数组中)。


参考答案：
　　①A和D是合法序列，B和C 是非法序列。
　　②设被判定的操作序列已存入一维数组A中。
　　int Judge(char A[])
　　//判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返回false。
　　{i=0; //i为下标。
　　j=k=0; //j和k分别为I和字母O的的个数。
　　while(A[i]!=‘\0’) //当未到字符数组尾就作。
　　{switch(A[i])
　　{case‘I’: j++; break; //入栈次数增1。
　　case‘O’: k++; if(k>j){cout<<“序列非法”<　　}
　　i++; //不论A[i]是‘I’或‘O’，指针i均后移。}
　　if(j!=k) {cout<<“序列非法”<　　else { cout<<“序列合法”<　　}//算法结束。
　　[算法讨论]在入栈出栈序列(即由‘I’和‘O’组成的字符串)的任一位置，入栈次数(‘I’的个数)都必须大于等于出栈次数(即‘O’的个数)，否则视作非法序列，立即给出信息，退出算法。整个序列(即读到字符数组中字符串的结束标记‘\0’)，入栈次数必须等于出栈次数(题目中要求栈的初态和终态都为空)，否则视为非法序列。

第3题：

已知元素的入栈顺序为abcde，则下列哪种出栈顺序是不可能的(出栈和入栈操作可交叉进行)?（ ）

A．edcba

B．cabde

C．dcbae

D．bcdea


正确答案：B
 abCde依次入栈，再依次出栈，得到出栈顺序edCba，所以选项A可能；我们现在来看选项B．第一个出栈的是C，&-Itl可以肯定栈中有b、a，等待入栈的是d、e，此时出栈的可能是b或d(d入栈马上出栈)，不可能是a，所以CA选项8不可能；选项C，第一个出栈的是d，可以肯定栈中有C、b、a，等待入栈的是e，此时出栈的可能是C或e(C入栈马上出栈)，若C、b、a依次出栈，e入栈马上出栈，刚好得到出栈顺序dCbae，因此选项C可能；选项D．第l个出栈的是b，可以肯定栈中有a，等待入栈的是c、d、e，C、d、e分别入栈马上又出栈得到出栈顺序bcde，最后a出栈，刚好得到出栈顺序bcdea，所以选项D可能。因此本题的正确答案是B。

第4题：

已知栈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

第5题：

设初始栈为空，s表示入栈操作，x表示出栈操作，则______是合法的操作序列。

A．sxxsssxxx

B．xxssxxss

C．sxsxssxx

D．Xssssxxx

A．

B．

C．

D．


正确答案：C

第6题：

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

A．321

B．213

C．231

D．123


正确答案：B
解析：栈的运算特点为在同一端插入和删除元素，即先入后出，总是栈顶元素先出栈，新元素总是压在栈顶元素之上并成为栈顶元素。初始栈为空，如下图(a)所示。对于元素　1、2、3，依照操作序列push、push、pop、pop、push、pop，可以得到出栈序列213，其过程为：第一个push操作将元素1压入栈中，如下图(b)所示：第二个push操作将元素2压入栈中，如下图(c)所示：第一个pop将栈顶元素2弹出栈，新栈顶元素为1，如下图(d)所示；第二个pop将栈顶元素1弹出栈，导致栈空，如下图(e)所示：其后的push和pop分别将元素3压入和弹出栈，操作结果如下图(f)和(g)所示。

第7题：

栈的入栈序列是1,2,„,n,输出序列为p1,p2,„pn,若p1=n,则pi为()。

A.i

B.n-i

C.n-i+1

D.不确定


参考答案：C

第8题：

对于长度为m(m>1)的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是()

A.若入栈和入队的序列相同，则出栈序列和出队序列可能相同

B.若入栈和入队的序列相同，则出栈序列和出队序列可以互为逆序

C.入队序列与出队序列关系为1:1，而入栈序列和出栈序列关系是1：n(n>=1)

D.入栈序列和出栈序列关系为1:1，而入队序列与出队序列关系是1：n(n>=1)


正确答案：D

第9题：

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

A．321

B．213

C．231

D．123

A．

B．

C．

D．


正确答案：B

第10题：

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

A.dcba

B.dabc

C.dcab

D.dbca


正确答案：A

更多相关问题
相关内容