《2022年栈与队列习题参考答案文 .pdf》由会员分享，可在线阅读，更多相关《2022年栈与队列习题参考答案文 .pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、习题三参考答案备注: 红色字体标明的是与书本内容有改动的内容。一、选择题1.在栈中存取数据的原则是（ B ） 。A 先进先出 B. 先进后出C. 后进后出 D. 没有限制2若将整数1、2、3、4 依次进栈，则不可能得到的出栈序列是（ D ） 。A 1234 B. 1324 C. 4321 D. 1423 3在链栈中，进行出栈操作时（B ） 。A需要 判断栈是否满 B. 需要 判断栈是否为空C. 需要 判断栈元素的类型 D. 无需对栈作任何差别4在顺序栈中，若栈顶指针top 指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize，则顺序栈的判空条件是（ A ） 。 A top=0 B.
2、top=-1 C. top=maxSize D.top=maxSize-1 5在顺序栈中，若栈顶指针top 指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（ C ） 。 A top=0 B.top=-1 C. top=maxSize D.top=maxSize-16在队列中存取数据元素的原则是（ A ） 。A先进先出 B. 先进后出C. 后进后出 D. 没有限制7在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front 和 rear 分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为m
3、axSize，则队列的判空条件是（A ） 。Afront=rear B. front!=rear C. front=rear+1 D. front=(rear+1)% maxSize 8在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front 和 rear 分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满条件是（D ） 。Afront=rear B. front!=rear C. front=rear+1 D. front=(rear+1)% maxSize 9.在循环顺序队列中，假设以少用一个存
4、储单元的方法来区分队列判满和判空的条件，front 和 rear 分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（C ） 。Arear-front B. rear-front+1 C. (rear-front+maxSize)%maxSize D. (rear-front+1)%maxSize 10. 设长度为n 的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度为（ B ） 。AO(1) BO(n) CO(log2n) DO(n2) 二、填空题1. 栈是一种操作受限的特殊线性表，其特殊
5、性体现在其插入和删除操作都限制在表尾进行。允许插入和删除操作的一端称为栈顶，而另一端称为栈底 。栈具有后进先出的特点。2. 栈也有两种存储结构，一种是顺序存储，另一种是链式存储；以这两种存储结构存储的栈分别称为顺序栈 和 链栈。3. 在顺序栈中，假设栈顶指针top 是指向栈顶元素的下一个存储单元，则顺序栈判空的条件是 top=0 ; 栈顶名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 元素的访问形式是 stackElemtop-
6、1 ; 4. 在不带表头结点的链栈中，若栈顶指针top 直接指向栈顶元素，则将一个新结点p 入栈时修改链的两个对应语句为 p.setNext(top) ； top=p; 。5. 在不带表头结点的链栈中，若栈顶指针top直接指向栈顶元素，则栈顶元素出栈时的修改链的对应语句为top=top.getNext(); 。6. 队列也是一种操作受限的线性表，它与栈不同的是，队列中所有的插入操作均限制在表的一端进行，而所有的删除操作都限制在表的另一端进行，允许插入的一端称为队尾 ，允许删除的一端称为队首。队列具有先进先出的特点。7. 由于队列的删除和插入操作分别在队首和队尾进行，因此，在链式 存储结构描述中
7、分别需要设置两个指针分别指向队首结点和 队尾结点，这两个指针又分别称为队首指针和 队尾指针。8.循环顺序队列是将顺序队列的存储区域看成是一个首尾相连的环，首尾相连的状态是通过数学上的求模（或取余）运算来实现的。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+
9、) ai=S.pop(); 2.编写一个函数判断一个字符序列是否为回文序列，所谓回文序列就是正读与反读都相同的字符序列，例如：abba 和 abdba 均是回文序列。要求只使用栈来实现。参考答案 : / 判断字符序列是否为回文序列, 若是则返回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 n
10、ew Exception(栈已满 );/ 抛出异常 else if (i=0) stackElemtop0+=X; else if (i=1) stackElemtop1-=X; / 出栈操作方法public Object pop(int i) throws Exception / 将 S 中第 i 号栈的栈顶元素出栈, 并返回栈顶元素值Object x=null; if(i=0) if (top0=base0) throw new Exception(第 0 号栈为空 ); else x=stackElem-top0; else if (i=1) if (top1=base1) throw
11、new Exception(第 0 号栈为空 ); else x=stackElem+top1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - return x; / DuSqStack类结束4.循环顺序队列类采用设置一个计数器的方法来区分循环队列的判空和判满。试分别编写顺序循环队列中入队和出队操作的函数。参考答案 : / 循环顺序队列存储结构类描述如下: class CircleSqQueue_num private Obj
12、ect queueElem; / 队列存储空间private int front;/ 队首的引用，若队列不空，指向队首元素，初值为0 private int rear;/ 队尾的引用，若队列不空，指向队尾元素的下一个位置, 初值为 0 private int num; / 计数器用来记录队列中的数据元素个数 / CircleSqQueue_num类结束为类 CircleSqQueue_num 所编写的入队和出队操作方法如下：/ 入队操作方法public void offer(Object x) throws Exception /把指定的元素x 插入队列if (num=queueElem.le
13、ngth)/ 队列满 throw new Exception(队列已满 );/ 输出异常 else / 队列未满 queueElemrear = x;/ x加入队尾 rear=(rear + 1) % queueElem.length; /更改队尾的位置 +num; /计数器加1 / 出队操作方法public Object poll() / 移除队首元素并作为此函数的值返回该对象，如果此队列为空，则返回 null if (num=0)/ 队列为空return null; else Object t = queueElemfront;/ 取出队首元素front = (front + 1) % q
14、ueueElem.length;/ 更改队首的位置-num; /计数器减1 return t;/ 返回队首元素 5.假设采用带头结点的循环链表来表示队列，并且只设一个指向队尾元素的指针（不设队首指针），试编写相应的队列置空、队列判空、入队和出队操作的函数。参考答案 : 用队尾指针标识的循环链队列的类描述如下: class CircleLinkQueue 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - private Node r
15、ear;/ 循环链队列的尾指针 为此类编写的队列置空、队列判空、入队和出队操作的方法分别如下：/ 队列置空操作方法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; / 出队操作方法pub
16、lic void poll() throws Exception / 移除带头结点的循环链队列中的队首元素并作为此函数的值返回该对象，如果此队列为空，则返回 null Node p = rear.getNext().getNext();/ p指向待删除的队首结点if (p=rear) rear.setNext(rear); /删除队首结点后，链队列变成了空链队列 else rear.getNext().setNext(p.getNext();/ 删除队首结点 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -