栈与队列习题参考附标准答案

《栈与队列习题参考附标准答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、习题三参考答案备注:红色字体标明的是与书本内容有改动的内容。一、选择题1.在栈中存取数据的原则是（B）。A．先进先出B.先进后出C.后进后出D.没有限制2．若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（D）。A．1234B.1324C.4321D.14233．在链栈中，进行出栈操作时（B）。A．需要判断栈是否满B.需要判断栈是否为空C.需要判断栈元素的类型D.无需对栈作任何差别4．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize，则顺序栈的判空条件是（A）。矚慫润厲钐瘗睞枥庑赖。A．top==0B.top==-1C.top==maxS

2、izeD.top==maxSize-1聞創沟燴鐺險爱氇谴净。5．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（C）。残骛楼諍锩瀨濟溆塹籟。A．top==0B.top==-1C.top==maxSizeD.top==maxSize-1酽锕极額閉镇桧猪訣锥。6．在队列中存取数据元素的原则是（A）。A．先进先出B.先进后出C.后进后出D.没有限制7．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储

3、容量为maxSize，则队列的判空条件是（A）。彈贸摄尔霁毙攬砖卤庑。A．front==rearB.front!=rearC.front==rear+1D.front==(rear+1)%maxSize謀荞抟箧飆鐸怼类蒋薔。8．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满条件是（D）。厦礴恳蹒骈時盡继價骚。A．front==rearB.front!=rearC.front==rear+1D.front==(rear+1)%m

4、axSize茕桢广鳓鯡选块网羈泪。9.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（C）。鹅娅尽損鹌惨歷茏鴛賴。A．rear-frontB.rear-front+1C.(rear-front+maxSize)%maxSizeD.(rear-front+1)%maxSize籟丛妈羥为贍偾蛏练淨。10.设长度为n的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度为（B）。預頌圣鉉儐歲龈讶骅籴。

5、A．O(1)B．O(n)C．O(log2n)D．O(n2)二、填空题1.栈是一种操作受限的特殊线性表，其特殊性体现在其插入和删除操作都限制在表尾进行。允许插入和删除操作的一端称为栈顶，而另一端称为栈底。栈具有后进先出的特点。渗釤呛俨匀谔鱉调硯錦。2.栈也有两种存储结构，一种是顺序存储，另一种是链式存储；以这两种存储结构存储的栈分别称为顺序栈和链栈。铙誅卧泻噦圣骋贶頂廡。3.在顺序栈中，假设栈顶指针top是指向栈顶元素的下一个存储单元，则顺序栈判空的条件是top==0;栈顶元素的访问形式是stackElem[top-1];擁締凤袜备訊顎轮烂蔷。4.在不带表头结点的链栈中，若栈顶指针top直接

6、指向栈顶元素，则将一个新结点p入栈时修改链的两个对应语句为p.setNext(top)；top=p;。贓熱俣阃歲匱阊邺镓騷。5.在不带表头结点的链栈中，若栈顶指针top直接指向栈顶元素，则栈顶元素出栈时的修改链的对应语句为top=top.getNext();。坛摶乡囂忏蒌鍥铃氈淚。6.队列也是一种操作受限的线性表，它与栈不同的是，队列中所有的插入操作均限制在表的一端进行，而所有的删除操作都限制在表的另一端进行，允许插入的一端称为队尾，允许删除的一端称为队首。队列具有先进先出的特点。蜡變黲癟報伥铉锚鈰赘。7.由于队列的删除和插入操作分别在队首和队尾进行，因此，在链式存储结构描述中分别需要设置

7、两个指针分别指向队首结点和队尾结点，这两个指针又分别称为買鲷鴯譖昙膚遙闫撷凄。队首指针和队尾指针。8.循环顺序队列是将顺序队列的存储区域看成是一个首尾相连的环，首尾相连的状态是通过数学上的求模（或取余）运算来实现的。綾镝鯛駕櫬鹕踪韦辚糴。9.在循环顺序队列中，若规定当front==rear时，循环队列为空；当front==(rear+1)%maxSize时，循环队列为满，则入队操作时的队尾指针变化的相应语句是rear=(