A. 5 4 3 6 1 2 B . 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 3. 输入序列为AB C，可以变为CB A时，经过的栈操作为（ ）。
A. push,pop,push,pop,push,pop B . push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop
4. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
A．线性表的顺序存储结构 B . 队列 C. 线性表的链式存储结构 D. 栈 5. 用链接方式存储的队列，在进行删除运算时（ ）。
A. 仅修改头指针 B .仅修改尾指针
C. 头、尾指针都要修改 D. 头、尾指针可能都要修改
6. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。
A．(rear-front+m)%m B ．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m
7. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B . 2和4 C. 4和2 D. 5和1 8. 栈和队列的共同点是（ ）。
A. 都是先进先出 B . 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点
9. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。
A． 6 B .4 C. 3 D. 2 10. 栈和队列都是（ ）。
A．顺序存储的线性结构 B . 链式存储的非线性结构 C. 限制存取点的线性结构 D. 限制存取点的非线性结构 二、判断题
1. 若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。（ ） 2. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ ）
3. 队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ） 4. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（ ） 5. 任何一个递归过程都可以转换成非递归过程。（ ） 三、填空题
1．栈是_______的线性表，其运算遵循_______的原则。 2．在作进栈运算时应先判别栈是否_ _;在作退栈运算时应先判别栈是否 _；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_ 。
3. 用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_______。 4. 顺序栈用data[0?n-1]存储数据，栈顶指针是top,则值为x的元素入栈的操作是_______。
5．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_______。 6. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_______。 7．表达式求值是_______应用的一个典型例子。 8．循环队列的引入，目的是为了克服_______。 9. 循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是_______。
实验题目
1、将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长，当向第0号栈插入一个新元素时，使top[0]增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使top[1]减1得到新的栈顶位置。当top[0]+1 == top[1]时或top[0] = top[1]-1时，栈空间满，此时不能再向任一栈加入新的元素。试定义这种双栈结构的类型定义，并实现判栈空、判栈满、插入、删除算法。
2、假设以数组Q[m]存放循环队列中的元素，同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入和删除算法。
练习题目答案
一 单选题 1 B 1 × 2 C 3 B 2 × 4 D 5 D 3 × 6 A 7 B 4 √ 8 C 9 C 5 √ 10 C 二、判断题 三、填空题
1．操作受限（或限定仅在表尾进行插入和删除操作）后进先出 2．(1)满 (2)空 (3)n 3.S×SS×S×× 4.data[++top]=x； 5.先进先出
6.s=(LinkedList)malloc(sizeof(LNode))； s->data=x;s->next=r->next；r->next=s；r=s； 7．栈
8.假溢出时大量移动数据元素 9.（rear-front+m）% m
第四章 串
4.5总结与提高
4.5.1主要知识点
（1）熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。
（2）熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。 （3）了解串的堆存储结构以及在其上实现串操作的基本方法。
（4）理解串匹配的KMP算法，熟悉NEXT函数的定义，学会手工计算给定模式串的next函数值和改进的next函数值。
（5） 了解串操作的应用方法和特点。
4.5.2典型例题
1、?abcde?有多少个子串? 解：
自身：1 ；空串数：1 含1个字符的子串数：5 含2个字符的子串数：4 含3个字符的子串数：3 含4个字符的子串数：2 共有1+1+2+3+4+5=16个子串。
2、设计顺序串上实现串比较运算Strcmp(s,t)的算法。 解：本例的算法思路如下：
（1）比较s和t两个串共同长度范围内的对应字符: ①若s的字符＜t的字符,返回1； ②若s的字符＞t的字符,返回-1；
③若s的字符=t的字符,按上述规则继续比较。 （2）当(1)中对应字符均相同时,比较s1和s2的长度: ①两者相等时,返回0； ② s的长度＞t的长度,返回1； ③ s的长度＜t的长度,返回-1。 int Strcmp(SString s,SString t) {
int i,comlen;
if (s.len //逐个字符比较 if (s.data[i] //s==t //求s和t的共同长度 return 0; else if (s.len return -1; else return 1; } 3、在链串中，设计一个算法把最先出现的子串?ab?改为?xyz?。 解：在串s中找到最先出现的子串?ab?，p指向data域值为'a'的结点，其后为data域值为'b'的结点。将它们的data域值分别改为'x'和'z'，再创建一个data域值为'y'的结点，将其插入到*p之后。本例算法如下： void Repl(LString *&s) { LiString *p=s->next,*q;int find=0; while (p->next!=NULL && find==0) { if (p->data==?a? && p->next->data==?b?) { p->data='x';p->next->data='z'; q=(lstring *)malloc(sizeof(lstring)); q->data='y';q->next=p->next; p->next=q; find=1; } else p=p->next; } } 4、求模式串abcabaa的next[j]和nextval[j]的值。 解：模式串对应的next数组和nextval数组的值如下： j T[j] next[j] nextval[j] 1 a 0 0 2 b 1 1 3 c 1 1 4 a 1 0 5 b 2 1 6 a 3 3 7 a 2 2 //s // 找到 //替换为xyz 练习题目 一、单选题 1．下面关于串的的叙述中，哪一个是不正确的？（）【北方交通大学 2001 一、5】 A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行
