数据结构 习题课2.doc

《数据结构 习题课2.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题课2栈1．设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序加入其中，请回答下述问题：(1)若入、出栈次序为push(1),pop(),push(2),push(3),pop(),pop(),push(4),pop(),出栈的数字序列为何(这里push(i)表示进栈pop()表示出栈)？(2)能否得到出栈序列1423和1432？并说明为什么不能得到或者如何得到。(3)请分析1，2，3，4的24中排列中，哪些序列是可以通过相应的入出栈操作得到的。【答案】（1）1，3，2，4；（2）不能得到1423序列，因为要得到4必须2，3入栈，才能4入栈，然后4

2、出栈，而这时，只能得到3而不能得到2；能得到1432,依照以下入、出栈序列即可得到：push(1),pop(),push(2),push(3),push(4),pop(),pop(),pop()2．链栈中为何不设置头结点？【答案】栈的操作位置就是栈顶一个位置，不设置头结点，插入、删除更方便。3．循环队列的优点是什么？如何判别它为空和满？【答案】(1)循环队列结构解决了假溢出问题；(2)采用少用一个存储单元的策略，让队头指针指向实际队头，队尾指针指向队尾元素的下一个位置。队空的判定条件：Q->front＝＝Q->rear队满的判定条件：Q->front＝＝（Q->rear+1）

3、%Queuesize4．设计长度为n的链队列用单循环链表表示，若只设头指针，则入队、出队的时间为何？若只设尾指针呢？【答案】若只设头指针，则出队的时间为O(1),入队时需要扫描整个链表，所用的时间为O(n)；若只设尾指针，则入队、出队的时间均为O(1)。5．指出下述程序段的功能是什么？voiddemo(Seqstack*S){inti,arr[64],n＝0;while(!stackempty(S))arr[n++]＝pop(S);for(i＝0;i

4、。SeqstackS1,S2,temp;Datatypex;…//假设已作过初始化while(!Stackempty(&S1)){x＝pop(&S1);push(&temp,x);while(!Stackempty(&temp)){x＝pop(&temp);push(&S1,x);push(&S2,x);}【答案】程序段的功能是：利用工作栈temp将栈S1复制到栈S2。(3)voiddemo2(Seqstack*S,intm){SeqstackT;inti;Initstack(&T);while(!stackempty(S))if(i＝pop(S))!＝m)push(&T,i

5、);while(!Stackempty(&T)){i＝pop(&T);push(S,i);}}//demo2【答案】程序段的功能是：利用工作栈t将栈S中的值为m的元素滤掉。(4)voiddemo3(CirQueue*Q){intx;SeqstackS;Initstack(&S);while(!QueueEmpty(Q)){x＝Delqueue(Q);push(&S,x);}while(!Stackempty(&S)){x＝pop(&S);Enqueue(Q,x);}}//demo3【答案】见同步练习题。CirQueueQ1,Q2;intx,i,m＝0;……//假设Q1已有内容

6、Q2已作过初始化while(!QueueEmpty(&Q1)){x＝Delqueue(&Q1);Enqueue(Q2,x);m++;}for(i＝0;i

7、rch;intk,n;Initstack(S)n＝strlen(t);for(k＝0;k