A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n
10、若在一个大小为6的数组上实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ） A、1，5 B、2, 4 C、4，2 D、5，1
11、用单链表表示的链式队列的队头在链表的（ ）位置 A、链头 B、链尾 C、链中
12、判定一个链队列Q（最多元素为n个）为空的条件是（ ）
A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13、在链队列Q中，插入s所指结点需顺序执行的指令是（ ）
A、Q.front->next=s;f=s; B、Q.rear->next=s;Q.rear=s; C、s->next=Q.rear;Q.rear=s; D、s->next=Q.front;Q.front=s;
14、在一个链队列Q中，删除一个结点需要执行的指令是（ ） A、Q.rear=Q.front->next; B、Q.rear->next=Q.rear->next->next; C、Q.front->next=Q.front->next->next; D、Q.front=Q.rear->next;
15、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（ ）
A、仅修改队头指针 B、仅修改队尾指针 C、队头尾指针都要修改 D、队头尾指针都可能要修改。 16、栈和队列的共同点是（ ）
A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 17、消除递归（ ）需要使用栈。 A、一定 B、不一定
18、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少应该是（ ）
A、2 B、 3 C、 5 D、 6
19、若一个栈的输入序列是a,b,c，则通过入、出栈操作可能得到a,b,c的不同排列个数为（ ）
A、 4 B、 5 C、 6 D、 7 20、设有一顺序栈已经含有3个元素，如图3.1所示元素a4正等待进栈。下列不可能出现的出栈序列是（ ）
A、a3,a1,a4,a2 B、 a3,a2,a4,a1 C、 a3,a4,a2,a1 D、 a4,a3,a2,a1
maxsize-1 0 a1 Top 图3.1 21、链栈和顺序栈相比，有一个比较明显的优势是（ ）
A、通常不会出现栈满的情况 B、 通常不会出现栈空的情况 C、 插入操作更容易实现 D、 删除操作更加容易实现
22、若一个栈的输入序列是1,2,3,4,?,n，输出序列的第一个元素是n，则第i个输出元素是（ ）
A、不确定 B、 n-i C、 n-i+1 D、n-i-1 23、以下说法正确的是( )
A、因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 B、因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 C、对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢” D、对于顺序栈而言在栈满状态下如果此时再作进栈运算，则会发生“下溢”。
二、判断题
1、 在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。
a2 a3
2、 链栈与顺序栈相比的一个优点是链栈插入和删除操作更加方便。
3、 若一个栈的输入序列为1，2，3，?，n，其输出序列的第一个元素为n，则其输出序列的每个元素
ai一定满足ai=i+1(i=1,2, ?,n)。
4、 在链队列中，即使不设置尾指针也能进行入队操作。
5、 在对链队列（带头指针）做出队操作时，不会改变front指针的值。 6、 循环队列中元素个数为rear-front。
7、 一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到4,3,1,2。 8、 一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到1,2,3,4。 9、 若以链表作为栈的存储结构，则进栈需要判断栈是否满。 10、 若以链表作为栈的存储结构，则出栈需要判断栈是否空。
三、 填空题
1、栈的特点是（ ），队列的特点是（ ）。
2、线性表、栈、队列都是（ ）结构，可以在线性表的（ ）位置插入和删除元素；对于栈只能在（ ）插入和删除元素；对于队列只能在（ ）插入元素和在（ ）位置删除元素。
3、有程序如下，则此程序的输出结果（栈的元素类型是SelemType为char）是（ ）。
Void main()
{stack s; char x,y; initstack (s); x=?c?;y=?k?;
push(s,x);push(s,?a?);push(s,y);
pop(s,x);push(s,?t?);push(s,x);pop(s,x);push(s,?s?); while(!stackempty(s)){pop(s,y);printf(y);} printf(x);}
4、在栈顶指针为HS的链栈中，判定栈空的条件是（ ）。 5、向栈中压入元素的操作是先（ ）后（ ）。 6、对栈进行退栈操作是先（ ）后（ ）。
7、用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（ ）和（ ）；若只设尾指针，则出队和入队的时间复杂度分别是（ ）和（ ）。 8、从循环队列中删除一个元素时，其操作是（ ）。 9、在一个循环队列中，队首指针指向队首元素的（ ）。
10、在具有n个单元的循环队列中，队满时共有（ ）个元素。 11、在HQ的链队列中，判断只有一个结点的条件是（ ）。
12、设栈S和队列Q的出始状态为空，元素a,b,c,d,e,f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b,d,c,f,e,a 则栈S的容量至少应该是（ ）。
13、有程序如下，则此程序的输出结果（队列的元素类型是QSelemType为char）是（ ）。
Void main()
{char x=?e?,y=?c?;
enqueue(q,?h?);enqueue(q,?r?);enqueue(q,y);dequeue(q,x);enqueue(q,x);degueue(q,x); enqueue(q,?a?);
while(!queueempty(q)){dequeue(q,y);printf(y);} printf(x);}
14、有如下递归函数：
int dunno(int m)
{int value;if(m==0)value=3;
else value=dunno(m-1)+5;
return(value);}
执行语句printf(“%d\\n”,dunno(3));的结果是（ ）。 四、 简答题
1、 对于堆栈，给出三个输入项A，B，C，如果输入项序列为ABC，试给出全部可能的输出序列，并写
出每种序列对应的操作。例如：A进B进C进C出B出A出，产生的序列为CBA。 2、 简述以下算法的功能（栈的元素类型是SelemType为int）。
（1） status algo1(stack s)
{int I,n,a[255];n=0;while(!stackempty(s)){n++;pop(s,a[n]);} for(I=1;I<=n;I++)push(s,a[I]);}
(2) status algo2(stack s,int e)
{stack t;int d;initstack(t);while(!stackempty(s)){pop(s,d);if(d!=e)push(t,d);} while(!stackempty(t)){pop(t,d);push(s,d);}}
3、 内存中一片连续空间（不妨假设地址从0到m-1）提供给两个栈s1和s2使用，怎样分配这部分存储
空间，使得对任一栈仅当这部分空间全满时才发生溢出。 4、 有递归过程如下：
void print(int w){int I;if(w!=0){print(w-1)
for(I=1;I<=w;I++)printf(“=”,w);printf(“\\n”);}}
问：调用语句print(4)的结果是什么？
5、 简述以下算法的功能（栈和队列的元素类型均为int）
void algo(queue &q) {stack s;int d;initstack(s);
while(!queueempty(q)){dequeue(q,d);push(s,d);} while(!stackempty(s)){pop(s,d);enqueue(q,d);} }
6、 假设Q[0，9]是一个非循环线性队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针
的状态变化情况，如果不能入队，请指出其元素，并说明理由。
d,e,b,g,h入队 d,e出队 I,j,k,l,m入队 b出队 n,o,p,q,r入队。
7、按照运算符优先数法，画出对下面算术表达式求值时，操作数栈和运算符栈的变化过程： 9-2*4+(8+1)/3。
8、设栈S＝（1，2，3，4，5，6，7），其中7为栈顶元素。写出调用algo后栈S的状态。 void algo(Stack *S) {int i=0;
Queue Q; Stack T;
InitQueue(Q); InitStack(T); while(!StackEmpty(S))
{if(i%2==0) Push(T,Pop(S)); else EnQueue(Q,Pop(S)); i++;
}
while(!QueueEmpty(Q)) Push(S,DeQueue(Q)); while(!StackEmpty(T)) Push(S,Pop(T)); } 9、试将下列递归过程改写为非递归过程 void digui(int *sum) {scanf(x);
if(x==0) sum=0;
else {digui(sum);sum+=x;} printf(sum);
10、写出下列中缀表达式的后缀形式： (1) A * B * C (2) (A + B)* C -D (3) A* B + C/(D-E) (4) (A + B) * D + E / (F + A * D) + C
11 设表达式的中缀表示为a * x - b / x↑2，试利用栈将它改为后缀表示ax * bx2↑/ -。写出转换过程中栈的变化。 五、 设计题
1、 在栈顶指针为HS的链栈中，写出计算该链栈中结点个数的函数？ 2、 求两个正整数m和n的最大公约数可用如下gcd(m,n)公式表示：
gcd(m,n)=m当n=0时，或gcd(n,m%n)当 n>0时 （1） 编写一个计算gcd(m,n)的递归过程 （2） 将上述过程转化为非递归过程
（3） 画出计算gcd(20,6)的过程及栈的状态变化，给出计算结果。
3、 已知Q是一个非空队列，S是一个空栈，使用C语言编写一个算法，仅用队列和栈的ADT函数和少
量工作变量，将队列Q中的所有元素逆置。 栈的ADT函数有
void SetEmpty(stack s); //置空栈
void Push(stack s,ElemTye value); //新元素value进栈 ElemType Pop(stack s); //出栈，返回栈顶值 Boolean IsEmptyS(stack s); //判断栈空否
队列ADT的函数有：
void EnQueue(Queue q,ElemType value); //元素入队 ElemType DeQueue(Queue q); //出队列返回队头值 Boolean IsEmptyQ(Queue q); //判断队列是否为空
4、 用单链表实现队列，如下图所示，并令front=rear=NULL表示队列为空，编写实现队列的如下五种运
算的函数。
Setnull:将队列置成空队列。 getfirst:返回队列的第一个元素。 enqueue:把元素插入队列的后端。 dequeue:删除队列的第一个元素。 empty:判定队列是否为空。
第四章 串 复习题
一、 选择题
1、设串s1=?ABCDEFG?，s2=?PQRST?，函数Concat(x,y)返回x和y串的连接串，Substr(s,i,j)返回串s从序号I开始的j个字符组成的子串，length(s)返回串s的长度，则Concat(Substr(s1,2,length(s2)),Substr(s1,length(s2),2))的结果串是（ ）。
A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF 2、空串和空格是相同的。A、正确 B、错误
3、若串S1=?ABCDEFG?，S2=?9898?，S3=?###?，S4=?012345?，则执行
replace(s1,Substr(s1,4,length(s3)),s3),Concat(s1,Substr(s4,index(s2,?8?),length(s2)))后，其结果为（ ）。
A、ABC###G0123 B、ABCD###2345 C、ABC###G2345 D、ABC###2345 E、ABC###G1234 F、ABCD###1234 G、ABC###01234
4、串是一种特殊的线性表，其特殊性体现在（ ）。
A、可以顺序存储 B、数据元素是一个字符 C、可以链接存储 D、数据元素可以是多个字符 5、设有两个串p和q，求q在p中首次出现的位置的运算称为（ ）。 A、连接 B、模式匹配 C、求子串 D、求串长
6、下面关于串的的叙述中，哪一个是不正确的？（ ）
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 7、串的长度是指（ ）
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数
二、 判断题
1、 子串定位函数的时间复杂度在最坏的情况下为O（n*m），因此子串定位函数没有实际利用价值。 2、 设有两个串p和q，其中q是p的子串，把q在p中首次出现的位置作为子串q在p中的位置的算法
称为匹配。
3、 KMP算法的最大特点是指示主串的指针不需要回朔。
三、 填空题
1、设s=?I_AM_A_TEACHER?，其长度为（ ）。 2、空串是（ ），其长度为（ ）。
3、设S1=?GOOD?，S2=?︼?，S3=?BYE!?，则S1、S2和S3连接后的结果是（ ）。 4、两个串相等的充分必要条件是（ ）。