第3章栈和队列

第3章栈和队列教材中练习题及参考答案1.有5个元素，其进栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？答：要使C第一个且D第二个出栈，应是A进栈，B进栈，C进栈，C出栈，D进栈，D出栈，之后可以有以下几种情况：（1）B出栈，A出栈，E进栈，E出栈，输出序列为CDBAE；（2）B出栈，E进栈，E出栈，A出栈，输出序列为CDBEA；（3）E进栈，E出栈，B出栈，A出栈，输出序列为CDEBA。所以可能的次序有：CDBAE、CDBEA、CDEBA。2.在一个算法中需要建立多个栈（假设3个栈或以上）时可以选用以下3种方案之一，试问这些方案之间相比各有什么优缺点？（1）分别用多个顺序存储空间建立多个独立的顺序栈。（2）多个栈共享一个顺序存储空间。（3）分别建立多个独立的链栈。答：（1）优点是每个栈仅用一个顺序存储空间时，操作简单。缺点是分配空间小了，容易产生溢出，分配空间大了，容易造成浪费，各栈不能共享空间。（2）优点是多个栈仅用一个顺序存储空间，充分利用了存储空间，只有在整个存储空间都用完时才会产生溢出。缺点是当一个栈满时要向左、右查询有无空闲单元。如果有，则要移动元素和修改相关的栈底和栈顶指针。当接近栈满时，要查询空闲单元、移动元素和修改栈底、栈顶指针，这一过程计算复杂且十分耗时。（3）优点是多个链栈一般不考虑栈的溢出。缺点是栈中元素要以指针相链接，比顺序存储多占用了存储空间。3.在以下几种存储结构中，哪个最适合用作链栈？（1）带头结点的单链表（2）不带头结点的循环单链表（3）带头结点的双链表答：栈中元素之间的逻辑关系属线性关系，可以采用单链表、循环单链表和双链表之一来存储，而栈的主要运算是进栈和出栈。当采用（1）时，前端作为栈顶，进栈和出栈运算的时间复杂度为O(1)。当采用（2）时，前端作为栈顶，当进栈和出栈时，首结点都发生变化，还需要找到尾2数据结构教程学习指导结点，通过修改其next域使其变为循环单链表，算法的时间复杂度为O(n)。当采用（3）时，前端作为栈顶，进栈和出栈运算的时间复杂度为O(1)。但单链表和双链表相比，其存储密度更高，所以本题中最适合用作链栈的是带头结点的单链表。4.简述以下算法的功能（假设ElemType为int类型）：voidfun(ElemTypea[],intn){inti;ElemTypee;SqStack*st1,*st2;InitStack(st1);InitStack(st2);for(i=0;in;i++)if(a[i]%2==1)Push(st1,a[i]);elsePush(st2,a[i]);i=0;while(!StackEmpty(st1)){Pop(st1,e);a[i++]=e;}while(!StackEmpty(st2)){Pop(st2,e);a[i++]=e;}DestroyStack(st1);DestroyStack(st2);}答：算法的执行步骤如下：（1）扫描数组a，将所有奇数进到st1栈中，将所有偶数进到st2栈中。（2）先将st1的所有元素（奇数元素）退栈，并放到数组a中并覆盖原有位置的元素；再将st2的所有元素（偶数元素）退栈，并放到数组a中并覆盖原有位置的元素。（3）销毁两个栈st1和st2。所以本算法的功能是，利用两个栈将数组a中所有的奇数元素放到所有偶数元素的前面。例如，ElemTypea[]={1,2,3,4,5,6}，执行算法后数组a改变为{5,3,1,6,4,2}。5.简述以下算法的功能（顺序栈的元素类型为ElemType）。voidfun(SqStack*&st,ElemTypex){SqStack*tmps;ElemTypee;InitStack(tmps);while(!StackEmpty(st)){Pop(st,e);if(e!=x)Push(tmps,d);}while(!StackEmpty(tmps)){Pop(tmps,e);第3章栈和队列3Push(st,e);}DestroyStack(tmps);}答：算法的执行步骤如下：（1）建立一个临时栈tmps并初始化。（2）退栈st中所有元素，将不为x的元素进栈到tmps中。（3）退栈tmps中所有元素，并进栈到st中。（4）销毁栈tmps。所以本算法的功能是，如果栈st中存在元素x，将其从栈中清除。例如，st栈中从栈底到栈顶为a、b、c、d、e，执行算法fun(st，'c')后，st栈中从栈底到栈顶为a、b、d、e。6.简述以下算法的功能（栈st和队列qu的元素类型均为ElemType）。boolfun(SqQueue*&qu,inti){ElemTypee;intj=1;intn=(qu-rear-qu-front+MaxSize)%MaxSize;if(j1||jn)returnfalse;for(j=1;j=n;j++){deQueue(qu,e);if(j!=i)enQueue(qu,e);}returntrue;}答：算法的执行步骤如下：（1）求出队列qu中的元素个数n。参数i错误时返回假。（2）qu出队共计n次，除了第i个出队的元素外，其他出队的元素立即进队。（3）返回真。所以本算法的功能是，删除qu中从队头开始的第i个元素。例如，qu中从队头到队尾的元素是a、b、c、d、e，执行算法fun(qu，2)后，qu中从队头到队尾的元素改变为a、c、d、e。7.什么是环形队列？采用什么方法实现环形队列？答：当用数组表示队列时，把数组看成是一个环形的，即令数组中第一个元素紧跟在最末一个单元之后，就形成一个环形队列。环形队列解决了非环形队列中出现的“假溢出”现象。通常采用逻辑上求余数的方法来实现环形队列，假设数组的大小为n，当元素下标i增1时，采用i=(i+1)%n来实现。8.环形队列一定优于非环形队列吗？什么情况下使用非环形队列？答：队列主要是用于保存中间数据，而且保存的数据满足先产生先处理的特点。非环形队列可能存在数据假溢出，即队列中还有空间，可是队满的条件却成立了，为此改为环形队列，这样克服了假溢出。但并不能说环形队列一定优于非环形队列，因为环形队列中4数据结构教程学习指导出队元素的空间可能被后来进队的元素覆盖，如果算法要求在队列操作结束后利用进队的所有元素实现某种功能，这样环形队列就不适合了，这种情况下需要使用非环形队列，例如利用非环形队列求解迷宫路径就是这种情况。9.假设以I和O分别表示进栈和出栈操作，栈的初态和终栈均为空，进栈和出栈的操作序列可表示为仅由I和O组成的序列。（1）下面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO（2）通过对（1）的分析，设计一个算法判定所给的操作序列是否合法。若合法返回真；否则返回假。（假设被判定的操作序列已存入一维数组中）。解：（1）选项A、D均合法，而选项B、C不合法。因为在选项B中，先进栈一次，立即出栈3次，这会造成栈下溢。在选项C中共进栈5次，出栈3次，栈的终态不为空。（2）本题使用一个链栈来判断操作序列是否合法，其中str为存放操作序列的字符数组，n为该数组的字符个数（这里的ElemType类型设定为char）。对应的算法如下：booljudge(charstr[],intn){inti=0;ElemTypex;LinkStNode*ls;boolflag=true;InitStack(ls);while(in&&flag){if(str[i]=='I')//进栈Push(ls,str[i]);elseif(str[i]=='O')//出栈{if(StackEmpty(ls))flag=false;//栈空时elsePop(ls,x);}elseflag=false;//其他值无效i++;}if(!StackEmpty(ls))flag=false;DestroyStack(ls);returnflag;}10.假设表达式中允许包含3种括号：圆括号、方括号和大括号。编写一个算法判断表达式中的括号是否正确配对。解：设置一个栈st，扫描表达式exp，遇到‘(’、‘[’或‘{’，则将其进栈；遇到‘)’，若栈顶是‘(’，则继续处理，否则以不配对返回假；遇到‘]’，若栈顶是‘[’，则继续处理，否则以不配对返回假；遇到‘}’，若栈顶是‘{’，则继续处理，否则以不配对返回假。在exp扫描完毕，若栈不空，则以不配对返回假；否则以括号配对返回真。本题算法如下：boolMatch(charexp[],intn){LinkStNode*ls;第3章栈和队列5InitStack(ls);inti=0;ElemTypee;boolflag=true;while(in&&flag){if(exp[i]=='('||exp[i]=='['||exp[i]=='{')Push(ls,exp[i]);//遇到'('、'['或'{',则将其进栈if(exp[i]==')')//遇到')',若栈顶是'(',则继续处理,否则以不配对返回{if(GetTop(ls,e)){if(e=='(')Pop(ls,e);elseflag=false;}elseflag=false;}if(exp[i]==']')//遇到']',若栈顶是'[',则继续处理,否则以不配对返回{if(GetTop(ls,e)){if(e=='[')Pop(ls,e);elseflag=false;}elseflag=false;}if(exp[i]=='}')//遇到'}',若栈顶是'{',则继续处理,否则以不配对返回{if(GetTop(ls,e)){if(e=='{')Pop(ls,e);elseflag=false;}elseflag=false;}i++;}if(!StackEmpty(ls))flag=false;//若栈不空,则不配对DestroyStack(ls);returnflag;}11.设从键盘输入一序列的字符a1、a2、„、an。设计一个算法实现这样的功能：若ai为数字字符，ai进队，若ai为小写字母时，将队首元素出队，若ai为其他字符，表示输入结束。要求使用环形队列。解：先建立一个环形队列qu，用while循环接收用户输入，若输入数字字符，将其进队；若输入小写字母，出队一个元素，并输出它；若为其他字符，则退出循环。本题算法如下：voidfun(){ElemTypea,e;SqQueue*qu;//定义队列指针InitQueue(qu);while(true){printf(输入a:);scanf(%s,&a);if(a='0'&&a='9')//为数字字符6数据结构教程学习指导{if(!enQueue(qu,a))printf(队列满,不能进队\n);}elseif(a='a'&&a='z')//为小写字母{if(!deQueue(qu,e))printf(队列空,不能出队\n);elseprintf(出队元素:%c\n,e);}elsebreak;//为其他字符}DestroyQueue(qu);}12.设计一个算法，将一个环形队列（容量为n，元素下标从0到n-1）的元素倒置。例如，图3.2（a）中为倒置前的队列（n=10），图3.2（b）中为倒置后的队列。图3.2一个环形队列倒置前后的状态解：使用一个临时栈st，先将qu队列中所有元素出队并将其进栈st，直到队列空为止。然后初始化队列qu（队列清空），再出栈st的所有元素并将其进队qu，最后销毁栈st。对应的算法如下：voidReverse(SqQueue*&qu){ElemTypee;SqStack*st;InitStack(st);while(!QueueEmpty(qu))//队不空时,出队并进栈{deQueue(qu,e);Push(st,e);}InitQueue(qu);//队列初始化while(!StackEmpty(st))//栈