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

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

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

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

4、针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为front和 rear 分别为队首 maxSize ，则队列的长度是（ C ）。A rear-frontB. rear-front+1C. （rear-front+maxSize）%maxSize D. （rear-front+1）%maxSize10. 设长度为 n 的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度 为（ B ）。A O（1）BO（n）CO（log 2n）DO（n2）、填空题1. 栈是一种操作受限的特殊线性表，其特殊性体现在其插入和删除操作都限制在 表尾 进行。允许插入

5、和删除 操作的一端称为 栈顶 ，而另一端称为 栈底 。栈具有 后进先出 的特点。2. 栈也有两种存储结构，一种是 顺序存储 ，另一种是 链式存储 ；以这两种存储结构存储的栈分别称为 顺序 栈 和 链栈 。3. 在顺序栈中，假设栈顶指针 top 是指向栈顶元素的下一个存储单元，则 顺序栈判空的条件是 top=0 ; 栈顶元素的访问形式是 stackElemtop-1 ;4. 在不带表头结点的链栈中，若栈顶指针 top 直接指向栈顶元素，则将一个新结点 p 入栈时修改链的两个对应 语句为 p.setNext(top) ； top=p; 。5. 在不带表头结点的链栈中，若栈顶指针 top 直接指向栈

6、顶元素，则栈顶元素出栈时的修改链的对应语句为 top=top.getNext(); 。6. 队列也是一种操作受限的线性表，它与栈不同的是，队列中所有的插入操作均限制在表的一端进行，而所有 的删除操作都限制在表的另一端进行，允许插入的一端称为 队尾 ，允许删除的一端称为 队首 。队列具有 先进先出 的特点。7. 由于队列的删除和插入操作分别在队首和队尾进行，因此，在 链式 存储结构描述中分别需要设置两个指针分 别指向 队首结点 和 队尾结点 ，这两个指针又分别称为 队首指针 和 队尾指针 。8. 循环顺序队列是将顺序队列的存储区域看成是一个首尾相连的环， 首尾相连的状态是通过数学上的 求模(或

7、取余) 运算来实现的。9. 在循环顺序队列中，若规定当 front=rear 时，循环队列为空；当 front=(rear+1)%maxSize 时，循环队列 为满，则入队操作时的队尾指针变化的相应语句是 rear=(rear+1)% maxSize ；出队操作时的队首指针变化 的相应语句是 front=(front+1)%maxSize 。10. 无论是顺序栈还是顺序队列， 插入元素时必须先进行 栈或队列是否为满的 判断，删除元素时必须先进行 栈 或队列是否为空的 判断；而链栈或链队列中，插入元素无需进行栈或队列是否为满的判断，只要在删除元 素时先进行 栈或队列是否为空的 判断。三、算法设计

8、题1. 编写一个函数，要求借助一个栈把一个数组中的数据元素逆置。参考答案 :/ 借助一个顺序栈将已知一个数组中的数据元素逆置public reverse(Object a) throws Exception SqStack S=new SqStack(a.length); / 构造一个容量为 a.length 的顺序栈for(int i=0;ia.length;i+) S.push(ai);for( int i=0;ia.length;i+) ai=S.pop();2. 编写一个函数判断一个字符序列是否为回文序列，所谓回文序列就是正读与反读都相同的字符序列，例如： abba 和 abdba 均

9、是回文序列。要求只使用栈来实现。参考答案 :/ 判断字符序列是否为回文序列 , 若是则返回 true 值, 否则返回 false 。public boolean isPalindSeq(String str) LinkStack S = new LinkStack();int i = 0;for (; i str.length(); i+) S.push(str.charAt(i);for (i = 0; i top1) /栈满throw new Exception( 栈已满 );/ 抛出异常 else if (i=0)stackElemtop0+=X;else if (i=1) stackE

10、lemtop1-=X;/ 出栈操作方法 public Object pop(int i) throws Exception /将 S中第 i 号栈的栈顶元素出栈 , 并返回栈顶元素值Object x=null;if(i=0)if (top0=base0)throw new Exception(第 0 号栈为空 );elsex=stackElem-top0;else if (i=1)if (top1=base1)throw new Exception( 第 0 号栈为空 ); elsex=stackElem+top1;试编写一个顺序双向栈类 DuSqStack ，类中要求编写 3 个方法。 一个

11、是 此方法实现构造一个容量为 maxSize 的顺序双向空栈；一个是实现入 此方法完成将数据元素 X 压入到第 i(i=0 或 1)号栈中的操作；一个是return x; / DuSqStack 类结束4. 循环顺序队列类采用设置一个计数器的方法来区分循环队列的判空和判满。 试分别编写顺序循环队列中入队 和出队操作的函数。参考答案 :/ 循环顺序队列存储结构类描述如下 :class CircleSqQueue_num private Object queueElem; / private int front;private int rear;private int num;/队列存储空间队首的

12、引用，若队列不空，指向队首元素，初值为 队尾的引用，若队列不空，指向队尾元素的下一个位置 计数器用来记录队列中的数据元素个数0, 初值为 0 / CircleSqQueue_num类结束为类 CircleSqQueue_num 所编写的入队和出队操作方法如下： / 入队操作方法public void offer(Object x) throws Exception /把指定的元素 x 插入队列if (num=queueElem.length)/队列满throw new Exception(队列已满 );/输出异常else / 队列未满queueElemrear = x;/ x加入队尾rear=

13、(rear + 1) % queueElem.length; /更改队尾的位置+num; / 计数器加 1/ 出队操作方法 public Object poll() / 移除队首元素并作为此函数的值返回该对象，如果此队列为空，则返回 null if (num=0)/ 队列为空return null;else Object t = queueElemfront;/取出队首元素front = (front + 1) % queueElem.length;/ 更改队首的位置-num; / 计数器减 1 return t;/ 返回队首元素，试编写相5. 假设采用带头结点的循环链表来表示队列，并且只设一

14、个指向队尾元素的指针(不设队首指针) 应的队列置空、队列判空、入队和出队操作的函数。参考答案 :用队尾指针标识的循环链队列的类描述如下 :class CircleLinkQueue private Node rear;/循环链队列的尾指针 为此类编写的队列置空、队列判空、入队和出队操作的方法分别如下：/ 队列置空操作方法public void clear() / 将一个已经存在的带头结点的循环链队列置成空队列rear.setNext(rear);/ 入队操作方法public void offer ( Object x) throws Exception / 将指定的元素 x 插入到带头结点的循环链队列中Node p= new Node(x); /生成新结点p.setNext(rear.getNext();/ 插入链列列的尾部 rear.setNext(p);rear=p;/ 出队操作方法public