算法与数据结构C语言版课后习题答案(机械工业出版社)第3,4章 习题参考精品.pdfVIP

第3章栈和队列

一、基础知识题

3.1有五个数依次进栈：1，2，3，4，5。在各种出栈的序列中，以3，4先出的

序列有哪几个。（３在４之前出栈）。

【解答】34215，34251，34521

3.2铁路进行列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序为：

1，2，3，4，5，6，那么是否能够得到435612，325641，154623和135426

的出站序列，如果不能，说明为什么不能；如果能，说明如何得到(即写出

进栈或出栈的序列)。

【解答】输入序列为123456，不能得出435612和154623。不能得到435612的

理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素

剩12，且2在栈顶，不可能让栈底元素1在栈顶元素2之前出栈。不能得到154623

的理由类似，当栈中元素只剩23，且3在栈顶，2不可能先于3出栈。

得到325641的过程如下：123顺序入栈，32出栈，得到部分输出序列32；

然后45入栈，5出栈，部分输出序列变为325；接着6入栈并退栈，部分输出序

列变为3256；最后41退栈，得最终结果325641。

得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3

入栈，3出栈，部分输出序列变为13；接着4和5入栈，5，4和2依次出栈，

部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。

3.3若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别

为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的

值分别为多少？

【解答】2和4

3.4设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过

栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e3，e5，e4，

e6，e2，e1，则栈S的容量至少应该是多少？

【解答】4

3.5循环队列的优点是什么，如何判断“空”和“满”。

【解答】循环队列解决了常规用0--m-1的数组表示队列时出现的“假溢出”（即

队列未满但不能入队）。在循环队列中我们仍用队头指针等于队尾指针表示队空，

而用牺牲一个单元的办法表示队满，即当队尾指针加1（求模）等于队头指针时，

表示队列满。也有通过设标记以及用一个队头或队尾指针加上队中元素个数来区

分队列的“空”和“满”的。

3.6设长度为n的链队列用单循环链表表示，若只设头指针，则入队和出队的时

间如何？若只设尾指针呢？

【解答】若只设头指针，则入队的时间为O(n），出队的时间为O(1)。若只设尾

指针，则入队和出队的时间均为O(1)。

3.7指出下面程序段的功能是什么？

(1)voiddemo1(SeqStackS)

{inti，arr[64]，n=0;

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

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

}

【解答】程序段的功能是实现了栈中元素的逆置。

(2)voiddemo2(SeqStackS，intm)∥设栈中元素类型为int型

{intx;SeqStackT;

StackInit(T);

while(!StackEmpty(S))

if((x=Pop(S)!=m)Push(T，x);

while(!(StackEmpty(T)){x=Pop(T);Push(S，x);}

}

【解答】程序段的功能是删除了栈中值为m的元素。

(3)voiddemo3(SeQueueQ，intm)∥设队列中元素类型为