资源描述:
《第3章栈和队列(习题)》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、第3章栈和队列课堂练习K栈和队列是的线性表;▲2、有一栈,元素A,B,C,D只能依次进栈,则出栈序列中以下哪个是不可能得到的。()①D、C、B、A(3)A、B、C、D②C、B、A、D④D、C、A、B3、试写出队列中的出队算法。习题一、基础知识题A3.1设将整数1,2,3,4依次进栈,但只要出栈时栈非空,则可将出栈操作按任何次序夹入其中,请回答下述问题:▲⑴若入、出栈次序为Push(l),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop(),则出栈的数字序列为
2、何(这里Push(i)表示i进栈,Pop()表示出栈)?▲(2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。(3)请分析1,2,3,4的24种排列中,哪些序列是可以通过相应的入出栈操作得到的。A3.2链栈中为何不设置头结点?▲3.3循环队列的优点是什么?如何判别它的空和满?▲3.4设长度为n的链队用单循环链表表示,若设头指针,则入队出队操作的时间为何?若只设尾指针呢?3.5指出下述程序段的功能是什么?(1)AvoidDemol(SeqStack*S){inti,arr[64
3、],n=0;wh订e(IStackEmpty(S))arr[n++]=Pop(S):for(i=0;i4、SeqStack*S,intm){//设DataType为int型SeqStackT:inti;InitStack(&T);whi.le(!StackEmpty(S))if((i=Pop(S))!=m)Push(&T,i);wh订e(!StackEmpty(&T)){i=Pop(&T);Push(S,i);}}(3)voidDemo3(CirQueue*Q){//设DataType为int型intx;SeqStackS;InitStack(&S);whi.le(!QueueEmpty(Q)){x二D
5、eQueue(Q);Push(&S,x);}wh订e(!StackEmpty(&s)){x=Pop(&S);EnQueue(Q,x);}}//Demo3(3)CirQueueQI,Q2;//设DataType为int型intx,i,m=0;...//设QI已有内容,Q2已初始化过wh订e(!QueueEmpty(&Q1))x);m++;};EnQueue(&Q2,x);}{x二DeQueue(&Q1);EnQueue(&Q2,for(i=0;i6、ue(&Q1,x)二、算法设计题A3.6回文是指正读反读均相同的字符序列,如"abba"和"abdba"均是回文,但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。(提示:将一半字符入栈)3.7利用栈的基本操作,写一个将栈S中所有结点均删去的算法voidClearStack(SeqStack*S),并说明S为何要作为指针参数?3.8利用栈的基本操作,写一个返回S中结点个数的算法intStackSize(SeqStackS),并说明S为何不作为指针参数?A3.9设计算法判断一个算术表达
7、式的圆括号是否正确配对。(提示:对表达式进行扫描,凡遇到’('就进栈,遇就退掉栈顶的’(',表达式被扫描完毕,栈应为空。3.10一个双向栈S是在同一向量空间内实现的两个栈,它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化InitStack(S)、入栈Push(S,i,x)和出栈Pop(S,i)等算法,其中i为0或1,用以表示栈号。A3.11Ackerman函数定义如下:请写出递归算法。[n+1当m=0时AKM(m,n)二{AKM(m-1,1)当mHO,n二0时[AKM(m-1,AKM(m,n
8、-1))当mHO,n工0时3.12用第二种方法,即少用一个元素空间的方法来区别循环队列的队空和队满,试为其设计置空队,判队空,判队满、出队.入队及取队头元素等六个基本操作的算法。3.13假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针),试编写相应的置空队、判队空、入队和出队等算法。A3.14对于循环向量中的循环队列,写出求队列长度的公式。A3.15假设循环队列中只设rear和quelen来分别指示队尾元素的位置和队中元素的个数,试给