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

问答题下面所示的序列中哪些是合法的? A．IOIIIIOO B．IOOIOIIO C．IIIOIOIO D．OOOIIOII

【正确答案】正确答案：A和D是合法序列，B和C是非法序列。

【答案解析】

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

【正确答案】正确答案：设被判定的操作序列已存入一维数组A中。 int Judge(char A[]){ ／／判断字符数组A中的输入／输出序列是否是合法序列。如是，返回true，／／否则返回false int i=0；／／i为下标 int 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){printf(”序列非法＼n”)；exit(0)；} } i++；／／不论A[i]是’I’或‘O’，指针i均后移} if(j!=k){printf(”序列非法＼n”)；return(false)；} else{printf(”序列合法＼n”)；return(true)；} } }

【答案解析】