栈和队列习题答案.pdfVIP

第三章栈和队列习题答案

一、基础知识题

设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请

回答下述问题：

(1)若入、出栈次序为Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop(),则出栈的数字序

列为何(这里Push(i)表示i进栈，Pop()表示出栈)

(2)能否得到出栈序列1423和1432并说明为什么不能得到或者如何得到。

(3)请分析1，2，3，4的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。

答：(1)出栈序列为：1324

(2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push

(3),Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序

列。具体操作为：Push(1),Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。

(3)在1，2，3，4的24种排列中，可通过相应入出栈操作得到的序列是：

1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321

不能得到的序列是：

1423,2413,3124,3142,3412,4123,4132,4213,4231,4312

链栈中为何不设置头结点

答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结

点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。

循环队列的优点是什么如何判别它的空和满

答：循环队列的优点是：：循环队列的优点是：它它可以可以克服顺克服顺序队列的序队列的假上溢假上溢现象，能够使存储队列的向量空间得到充分

的的利用利用。判别循环队列的。判别循环队列的空空或或满满不能以头尾指针是否相等来确定，一般是通过以下几种方法：一

是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针

是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或

满，还可以得到队列中元素的个数。

设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何若只设尾指针呢

答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，

找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾

指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。

指出下述程序段的功能是什么

(1)voidDemo1(SeqStack*S){

inti;arr[64];n=0;

while(StackEmpty(S))arr[n++]=Pop(S);

for(i=0,in;i++)Push(S,arr[i]);

}..//设Q1已有内容，Q2已初始化过

while(!QueueEmpty(Q1))

{x=DeQueue(Q1);EnQueue(Q2,x);n++;}

for(i=0;in;i++)

{x=DeQueue(Q2);

EnQueue(Q1,x);EnQueue(Q2,x);}

答：

(1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的

元素放到栈顶。此栈中元素个数限制在64个以内。

(2)程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。

(3)程序段的功能是利用栈T，将一个非空栈S中值等于m的元素全部删去。

(4)程序段的功能是将一个循环队列Q经过S栈的处理，反向排列，原来的队头变成队尾，原来

的队尾变成队头。

(5)这段程序的功能是将队列1的所有元素复制到队列2中去，但其执行过程是先把队列1的元素

全部出队，进入队列2，然后再把队列2的元