各位学员大家好，大家在学习程序设计语言的时候，栈结构是必考的内容，字符串方面的知识虽然简单，但也不能忽视。为了让大家快速掌握这方面的知识点，接下来就带领大家一起来学习一下！
例题1：对于初始为空的栈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
【昊洋详解】：本题考查程序设计语言中栈结构的基础知识。
栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。换句话说，栈的修改是按先进后出的原则进行的。因此，栈又称为后进先出(Last In First Out, LIFO)的线性表。在栈中进行插入和删除操作的一端称为栈顶(top)，相应地，另一端称为栈底(bottom)，不含数据元素的栈称为空栈。
题干要求d第一个出栈，所以入栈的次序为a、b、c、d，栈的特点是先进后出的，且每个元素进栈、出栈各1次，既然第一个出栈的元素是d，那么元素a、b、c肯定都还没有出栈，所以a先进栈、然后b进栈、c进栈、d进栈。然后d出栈，c出栈，b出栈，最后a出栈，因而出栈序列只可能为d、c、b、a。
故该题目的正确答案为：A。
例题2：若有字符串“software”，则其长度为3的子串有( )个
A、5
B、6
C、7
D、8
【昊洋详解】：本题考查字符串的基础知识。
字符串：简称串，是一种特殊的线性表，其数据元素为字符。计算机中非数值问题处理的对象经常是字符串数据，例如，在汇编和高级语言的编译程序中，源程序和目标程序都是字符串，在事务处理程序中，姓名、地址等一般也是作为字符串处理的。字符串具有自身的特性，运算时常常把一个字符串作为一个整体来处理。
字符串是仅由字符构成的有限序列，是取值范围受限的线性表。子串长度为3，则至少需要3个字符，字符串“software”一共有8个字符，所以在本题中“are”是最后一个满足要求的字串，“sof”是最后一个满足要求的字串，字串个数的计算公式为：字符串字符个数-字串字符个数+1=8-3+1=6，所以长度为3的字串一共有6个。
故该题目的正确答案为：B。
（1）表示"以字符a 开头且仅由字符 a、b 构成的所有字符串"的正规式为（ ）
A、a*b*
B、(alb)*a
C、a(alb)*
D、(ab)*
（2）可利用一个栈来检查表达式中的括号是否匹配，其方法是：初始时设置栈为空，然后从左到右扫描表达式，遇到左括号“(”就将其入栈，遇到右括号“)”就执行出栈操作，忽略其他符号。对于算术表达式“a*(b+c))d”，由于( )，因此可判断出该表达式中的括号不匹配。
A、需要进行出栈操作但栈已空
B、需要进行入栈操作但栈已满
C、表达式处理已结束，但栈中仍留有字符“(”
D、表达式处理已结束，但栈中仍留有字符“)”
（3）设元素a、b、c、d依次进入一个初始为空的栈，则不可能通过合法的栈操作序列得到（ ）。
A、a b cd
B、b a c d
C、c a b d
D、d c b a
（1）解析：本题考查字符串正规式的基础知识。
正规式：一种表示正规集的工具，正规式是描述程序语言单词的表达式。若两个正规式表示的正规集相同，则认为二者等价。两个等价的正规集U和V记作U=V。需要注意的是，编译原理里面的正规式叫做范式，和正则表达式不是一个概念，但是有相通之处：都是通过一定的语法规则来描述文法，也就是所谓的匹配。
运算符“|”、“·”、“*”分别称为“或”、“连接”和“闭包”。在正规式的书写中，连接运算符“·”可省略。运算符的优先级从高到低顺序排列为：“*”、“·”、“|”。运算符“|”表示“或”、并集。“*”表示*之前括号里的内容出现0次或多次。那么我们分别看一下选项中的正规式表示的是什么意思吧。
a*b*={a} *{b}*：表示由若干个a后跟若干个b所组成的任何长度的字符串。
(alb)*a={a,b}*{a}：表示以a结尾，前面有任意个a或b组成的字符串。
a(alb)*={a}{a,b}*：表示以a开头，后面跟任意个a或b组成的字符串。
(ab)*={ab}*：表示由每个ab为一个单位所组成的任何长度的字符串(其中ab不能分离)。
四个选项只有C能保证以a开头，其他选项中的若干个是可以为0个的，所以不能保证第一字符一定是a。
故该题目的正确答案为：C。
（2）解析：本题考查栈结构的基础知识。
栈的特点是先进后出的，左括号入栈，右括号出栈，忽略其他符号。所以该题中只观察括号即可，即：（）），可见从左到右分别是左括号（入栈操作），右括号（出栈操作），右括号（出栈操作），所以当执行第2个右括号时，第一个左括号已经出栈了，栈为空栈，无法完成出栈操作。
故该题目的正确答案为：A。
（3）解析：本小题考查栈结构的基础知识。
栈：作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
对于A选项：a、b、c、d 分别单独地先进栈，再出栈就可以实现。
对于B选项：a进栈，b进栈，然后b出栈，a出栈，之后c、d分别单独地先进栈，再出栈就可以实现。
对于D选项：a、b、c、d 先顺序进栈，然后再顺序出栈就可以实现d、c、b、a的序列。
对于C选项：第一个出栈的是c，那么元素a、b肯定还在栈里，此时如果要出栈，接下来肯定是b，不可能是a，因为栈结构的特点就是先进后出，既然a先进栈，那么肯定是在b出栈后才能出栈，所以序列c、a、b、d是无法实现的，
故该题目的正确答案为：C。
作者唯一官方个人微信公众号（昊洋与你一起成长）：HYJY20180101
写于2020年8月30日
作者：昊洋讲师
版权所有，侵权必究
网友评论