第3章 栈与队列习题参考答案

《第3章 栈与队列习题参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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，则顺序栈的

2、判空条件是（A）。A．top==0B.top==-1C.top==maxSizeD.top==maxSize-15．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（C）。A．top==0B.top==-1C.top==maxSizeD.top==maxSize-16．在队列中存取数据元素的原则是（A）。A．先进先出B.先进后出C.后进后出D.没有限制7．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，

3、front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判空条件是（A）。A．front==rearB.front!=rearC.front==rear+1D.front==(rear+1)%maxSize8．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满

4、条件是（D）。A．front==rearB.front!=rearC.front==rear+1D.front==(rear+1)%maxSize9.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（C）。A．rear-frontB.rear-front+1C.(rear-front+maxSize)%maxSizeD.(rear-

5、front+1)%maxSize10.设长度为n的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度为（B）。A．O(1)B．O(n)C．O(log2n)D．O(n2)二、填空题1.栈是一种操作受限的特殊线性表，其特殊性体现在其插入和删除操作都限制在表尾进行。允许插入和删除操作的一端称为栈顶，而另一端称为栈底。栈具有后进先出的特点。2.栈也有两种存储结构，一种是顺序存储，另一种是链式存储；以这两种存储结构存储的栈分别称为顺序栈和链栈。3.在顺序栈中，假设栈顶指针t

6、op是指向栈顶元素的下一个存储单元，则顺序栈判空的条件是top==0;栈顶元素的访问形式是stackElem[top-1];1.在不带表头结点的链栈中，若栈顶指针top直接指向栈顶元素，则将一个新结点p入栈时修改链的两个对应语句为p.setNext(top)；top=p;。2.在不带表头结点的链栈中，若栈顶指针top直接指向栈顶元素，则栈顶元素出栈时的修改链的对应语句为top=top.getNext();。3.队列也是一种操作受限的线性表，它与栈不同的是，队列中所有的插入操作均限制在表的一端进行

7、，而所有的删除操作都限制在表的另一端进行，允许插入的一端称为队尾，允许删除的一端称为队首。队列具有先进先出的特点。4.由于队列的删除和插入操作分别在队首和队尾进行，因此，在链式存储结构描述中分别需要设置两个指针分别指向队首结点和队尾结点，这两个指针又分别称为队首指针和队尾指针。8.循环顺序队列是将顺序队列的存储区域看成是一个首尾相连的环，首尾相连的状态是通过数学上的求模（或取余）运算来实现的。9.在循环顺序队列中，若规定当front==rear时，循环队列为空；当front==(rear+1)%

8、maxSize时，循环队列为满，则入队操作时的队尾指针变化的相应语句是rear=(rear+1)%maxSize；出队操作时的队首指针变化的相应语句是front=(front+1)%maxSize。10.无论是顺序栈还是顺序队列，插入元素时必须先进行栈或队列是否为满的判断，删除元素时必须先进行栈或队列是否为空的判断；而链栈或链队列中，插入元素无需进行栈或队列是否为满的判断，只要在删除元素时先进行栈或队列是否为空的判断。三、算法设计题1.编写一个函数，要求借助一个栈把一个数组中的数据元素逆置。参考