栈和队列习题集

《栈和队列习题集》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、3.1设将整数1,2,3,4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为Push(l),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序列。因为要得到1

2、4的出栈序列，则应做Push(1),Pop(),Push(2),Push(3),Push(4),Pop()o这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为:Push(l),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,43211423,2413,31

3、24,3142,3412,4123,4132,4213,4231,4312关闭3.2链栈中为何不设置头结点?答:链栈不需要在头部附加头结点，因为栈都是在头部进行反而使算法更复杂，所以只要有链表的头指针就可以了。关闭3.3循环队列的优点是什么？如何判别它的空和满?答：循环队列的优点是：它可以克服顺序队列的〃假上溢〃现象,能够使存储队列的向量空间得到充分的利用。判别循环队列的〃空〃或〃满〃不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间，每次入队前测试入队后头尾指针是否会重合，如

4、果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。关闭3.4设长度为n的链队用单循环链表表示，若设头指针,则入队岀队操作的时间为何？若只设尾指针呢？答：当只设头指针时，出队的时间为1,而入队的时间需要n,因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。关闭3.5指出下述程序段的功能是什么？(1)voidDemol(SeqStack*S){int

5、i;arr[64];n二0;while(StackEmpty(S))arr[n++]二Pop(S);for(i二0,i

6、ntm){//设DataType为int型SeqStackT;inti;InitStack(&T);wh订e(!StackEmpty(S))if((i=Pop(S))!=m)Push(&T,i);wh订e(!StackEmpty(&T)){i二Pop(&T);Push(S,i);}}(2)voidDemo3(CirQueue*Q){//设DataType为int型intx;SeqStackS;InitStack(&S);wh订e(!QueueEmpty(Q)){x二DeQueue(Q);Push(&S,x);}wh订e(!StackEmpt

7、y(&s)){x=Pop(&S);EnQueue(Q,x);}}//Demo3(1)CirQueueQI,Q2;//设DataType为int型intx,i,df0;...〃设QI已有内容，Q2已初始化过while(!QueueEmpty(&Q1)){x二DeQueue(&Q1);EnQueue(&Q2,x):n++;}for(i二0;i

8、到栈顶。此栈中元素个数限制在64个以内。(2)程序段的功能是利用tmp栈将一个非空栈si的所有元素按原样复制到一个栈s2当中去。(1)程序段的功能是利用栈T,将一个非空栈S中值等