问题：
[填空题,简答题] 对于一个栈，给出输入项A,B,C,D，如果输入项序列为A,B,C,D，试给出全部可能的输出序列。
问题：
[单选] 设有两个串S1和S2，求串S2在S1中首次出现位置的运算称作（）。
连接。求子串。模式匹配。判断子串。
问题：
[单选] 已知串S=’aaab’，则next数组值为（）。
0123。1123。1231。1211。
问题：
[单选] 串与普通的线性表相比较，它的特殊性体现在（）。
顺序的存储结构。链式存储结构。数据元素是一个字符。数据元素任意。
问题：
[单选] 设串长为n，模式串长为m，则KMP算法所需的附加空间为（）。
O（m）。O（n）。O（m*n）。O（nlog2m）。
问题：
[单选] 设SUBSTR（S，i，k）是求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=’Beijing&Nanjing’，SUBSTR（S，4，5）=（）。
‘ijing’。‘jing&’。‘ingNa’。‘ing&N’。
问题：
[判断题] KMP算法的最大特点是指示主串的指针不需要回溯。
正确。错误。
问题：
[判断题] 完全二叉树某结点有右子树，则必然有左子树。
正确。错误。
问题：
[填空题] 求子串在主串中首次出现的位置的运算称为（）。
