软件水平考试
假设以S和X分别表示入栈和出栈操作，并且初始和终止时栈都为空，那么（ ）不是合法的操作序列。A.SSXXXSSXSX B.SSSXXXSSXX C.SSXSSXSXXX D.SXSXSXSXSX
题目
B.SSSXXXSSXX
C.SSXSSXSXXX
D.SXSXSXSXSX
相似问题和答案
第1题：
假设以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<<“序列非法”<
[算法讨论]在入栈出栈序列(即由‘I’和‘O’组成的字符串)的任一位置，入栈次数(‘I’的个数)都必须大于等于出栈次数(即‘O’的个数)，否则视作非法序列，立即给出信息，退出算法。整个序列(即读到字符数组中字符串的结束标记‘\0’)，入栈次数必须等于出栈次数(题目中要求栈的初态和终态都为空)，否则视为非法序列。
第2题：
设初始栈为空，s表示入栈操作，x表示出栈操作，则______是合法的操作序列。
A．sxxsssxxx
B．xxssxxss
C．sxsxssxx
D．Xssssxxx
A．
B．
C．
D．
第3题：
● 设初始栈为空，s 表示入栈操作，x表示出栈操作，则 （33） 是合法的操作序列。
（33）
A. sxxsssxxx
B. xxssxxss
C. sxsxssxx
D. xssssxxx
第4题：
已知栈S 初始为空，用 I 表示入栈、O表示出栈，若入栈序列为a1a2a3a4a5，则通过栈 S 得到出栈序列a2a4a5a3a1的合法操作序列（ ）。
A.IIOIIOIOOOB.IOIOIOIOIOC.IOOIIOIOIOD.IIOOIOIOOO
第5题：
对于初始为空的栈S，入栈序列为a、b、c、d，且每个元素进栈、出栈各1次。若出栈的第一元素为d，则合法的出栈序列为（）。
A.dcba
B.dabc
C.dcab
D.dbca
第6题：
若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作序列是( )
A．SXSSXXXX
B．SXXSXSSX
C．SXSXXSSX
D．SSSXXSXX
解析：可以按以下两个原则来判断出正确的栈操作序列：(1)操作序列中进栈次数和出栈次数相等；(2)操作序列中任一操作之前的进栈次数大于等于出栈次数。
第7题：
若pllsh、pop分别表示入栈、出栈操作，初始栈为空且元素1、2、3依次进栈，则经过操作序列push、push、pop、pop、push、pop之后，得到的出栈序列为 ______。
A．321
B．213
C．231
D．123
A．
B．
C．
D．
第8题：
若push、pop分别表示入栈、出栈操作，初始栈为空且元素1、2、3依次进栈，则经过操作序列push、push、pop、pop、push、pop之后，得到的出栈序列为(29)。
A．321
B．213
C．231
D．123
解析：栈的运算特点为在同一端插入和删除元素，即先入后出，总是栈顶元素先出栈，新元素总是压在栈顶元素之上并成为栈顶元素。初始栈为空，如下图(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)所示。
第9题：
设初始栈为空，s表示入栈操作，x表示出栈操作，则(33)是合法的操作序列。
A．sxxsssxxx
B．xxssxxss
C．sxsxssxx
D．xssssxxx
解析：本题考查数据结构中栈的基本知识。
栈是操作受限的线性表，其特点是后进先出。应用中可将栈看作一个桶状的容器，当栈中有元素时，栈顶元素先出栈，栈为空时进行出栈操作是不正确的。因此，对于一个关于初始为空的栈的操作序列，要求序列中任何一个操作之前，入栈操作的次数要大于等于出栈操作的次数。题目选项中仅操作序列SXSXSSXX满足该要求。
第10题：
设有初始为空的栈S，对于入栈序列a b c d e f, 经由进栈、进栈、出栈、进栈、进栈、出栈的操作后，栈顶和栈底元素分别为（ ）。
A.c和bB.b和aC.c和aD.d 和b