中南大学数据结构与算法第3章栈和队列课后作业答案.doc

《中南大学数据结构与算法第3章栈和队列课后作业答案.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第3章栈和队列习题练习答案3.1设将整数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种排列中，哪些序列是可以通过相应的入出栈操作

2、得到的。 答：　　(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

3、,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321     不能得到的序列是：　　　　1423,2413,3124,3142,3412,4123,4132,4213,4231,43123.2链栈中为何不设置头结点?答：   链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。3.3循环队列的优点是什么?如何判别它的空和满? 答：　　循环

4、队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。3.4设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何?若只设尾指针呢? 答：　　当只设头指针时，出队的时间

5、为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。3.5指出下述程序段的功能是什么? (1)voidDemo1(SeqStack*S){　　　　inti;arr[64];n=0;　　　　while(StackEmpty(S))arr[n++]=Pop(S);　　　　for(i=0,i

6、mo1(2)SeqStackS1,S2,tmp;　　DataTypex;　　...//假设栈tmp和S2已做过初始化　　while(!StackEmpty(&S1))　　　{　　　　x=Pop(&S1);　　　　Push(&tmp,x);　　　}　　while(!StackEmpty(&tmp))　　　{　　　　x=Pop(&tmp); 　　　　Push(&S1,x);　　　　Push(&S2,x);　　　}(3)voidDemo2(SeqStack*S,intm) 　　　{//设DataType为int型

7、　　　　SeqStackT;inti;　　　　InitStack(&T);　　　　while(!StackEmpty(S))　　　　　if((i=Pop(S))!=m)Push(&T,i);　　　　while(!StackEmpty(&T))　　　　　{　　　　　　i=Pop(&T);Push(S,i);　　　　　}　　　}(4)voidDemo3(CirQueue*Q)　　　{//设DataType为int型　　　　intx;SeqStackS;　　　　InitStack(&S);　　　　while(!Q

8、ueueEmpty(Q))　　　　　{x=DeQueue(Q);Push(&S,x);}　　　　while(!StackEmpty(&s))　　　　　{x=Pop(&S);EnQueue(Q,x);}　　　}//Demo3(5)CirQueueQ1,Q2;//设DataType为int型　　intx,i,n=0;　　...//设Q1已有内容，Q2已初始化过　　while(!QueueEmpty(&Q1))