欢迎来到天天文库
浏览记录
ID:34785786
大小:105.50 KB
页数:14页
时间:2019-03-10
《栈与队列习题参考附标准答案》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
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=(
此文档下载收益归作者所有