《第3章 栈与队列习题参考答案02464(12页).doc》由会员分享，可在线阅读，更多相关《第3章 栈与队列习题参考答案02464(12页).doc（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-第3章 栈与队列习题参考答案02464-第 11 页习题三参考答案备注: 红色字体标明的是与书本内容有改动的内容。一、选择题1. 在栈中存取数据的原则是（ B ）。A 先进先出 B. 先进后出 C. 后进后出 D. 没有限制2若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（ D ）。A1234 B. 1324 C. 4321 D. 14233在链栈中，进行出栈操作时（ B ）。A需要判断栈是否满 B. 需要判断栈是否为空C. 需要判断栈元素的类型 D. 无需对栈作任何差别4在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize，则顺序栈的判空条
2、件是（ A ）。 Atop=0 B.top=-1 C. top=maxSize D.top=maxSize-15在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（ C ）。 Atop=0 B.top=-1 C. top=maxSize D.top=maxSize-16在队列中存取数据元素的原则是（ A ）。A先进先出 B. 先进后出 C. 后进后出 D. 没有限制7在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，
3、队列的最大存储容量为maxSize，则队列的判空条件是（ A ）。 Afront=rear B. front!=rearC. front=rear+1 D. front=(rear+1)% maxSize 8在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满条件是（ D ）。 Afront=rear B. front!=rearC. front=rear+1 D. front=(rear+1)% maxSize9. 在循环顺序队列中，
4、假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（ C ）。 Arear-front B. rear-front+1C. (rear-front+maxSize)%maxSize D. (rear-front+1)%maxSize10.设长度为n的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度为（ B ）。 AO(1) BO(n) CO(log2n) DO(n2)二、填空题1. 栈是一种操作受限的特殊线性表，其特
5、殊性体现在其插入和删除操作都限制在 表尾 进行。允许插入和删除操作的一端称为 栈顶 ，而另一端称为 栈底 。栈具有 后进先出 的特点。2. 栈也有两种存储结构，一种是 顺序存储 ，另一种是 链式存储 ；以这两种存储结构存储的栈分别称为 顺序栈 和 链栈 。3. 在顺序栈中，假设栈顶指针top是指向栈顶元素的下一个存储单元，则顺序栈判空的条件是 top=0 ; 栈顶元素的访问形式是 stackElemtop-1 ;4. 在不带表头结点的链栈中，若栈顶指针top直接指向栈顶元素，则将一个新结点p入栈时修改链的两个对应语句为 p.setNext(top) ； top=p; 。5. 在不带表头结点的链
6、栈中，若栈顶指针top直接指向栈顶元素，则栈顶元素出栈时的修改链的对应语句为 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) stackElemtop1-=X;/出栈操作
10、方法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 new Exception(第0号栈为空); else x=stackElem+top1; return x; / DuSqStack类结束4. 循环顺序队列类采用设置一个计数器的方法来区分循环队列的判空和判
11、满。试分别编写顺序循环队列中入队和出队操作的函数。参考答案:/循环顺序队列存储结构类描述如下:class CircleSqQueue_num private Object queueElem; / 队列存储空间private int front;/ 队首的引用，若队列不空，指向队首元素，初值为0 private int rear;/ 队尾的引用，若队列不空，指向队尾元素的下一个位置,初值为0 private int num; / 计数器用来记录队列中的数据元素个数 / CircleSqQueue_num类结束为类CircleSqQueue_num所编写的入队和出队操作方法如下：/ 入队操作方法
12、public void offer(Object x) throws Exception /把指定的元素x插入队列if (num=queueElem.length)/ 队列满 throw new Exception(队列已满);/ 输出异常 else / 队列未满 queueElemrear = x;/ x加入队尾 rear=(rear + 1) % queueElem.length; /更改队尾的位置 +num; /计数器加1/ 出队操作方法public Object poll() /移除队首元素并作为此函数的值返回该对象，如果此队列为空，则返回 nullif (num=0)/ 队列为空re
13、turn null;else Object t = queueElemfront;/ 取出队首元素front = (front + 1) % queueElem.length;/ 更改队首的位置-num; /计数器减1return t;/ 返回队首元素5. 假设采用带头结点的循环链表来表示队列，并且只设一个指向队尾元素的指针（不设队首指针），试编写相应的队列置空、队列判空、入队和出队操作的函数。参考答案:用队尾指针标识的循环链队列的类描述如下:class CircleLinkQueue private Node rear;/ 循环链队列的尾指针为此类编写的队列置空、队列判空、入队和出队操作的方
14、法分别如下：/ 队列置空操作方法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 void poll() throws Exception / 移除带头结点的循环链队列
15、中的队首元素并作为此函数的值返回该对象，如果此队列为空，则返回 nullNode p = rear.getNext().getNext();/ p指向待删除的队首结点if (p=rear) rear.setNext(rear); /删除队首结点后，链队列变成了空链队列 else rear.getNext().setNext(p.getNext();/ 删除队首结点四、上机实践题1. 在顺序栈类中增加一个main成员函数，使其实际运行来测试顺序栈类中各成员函数的正确性。参考答案:package ch03Exercise;/顺序栈类public class SqStack private Obje
16、ct stackElem; / 栈存储空间 private int top; / 非空栈中始终表示栈顶元素的下一个位置，当栈为空时其值为0/ 栈的构造函数，构造一个存储空间容量为maxSize的栈public SqStack(int maxSize) top = 0; / 初始化top为0stackElem = new ObjectmaxSize;/ 为栈分配maxSize个存储单元/ 将一个已经存在的栈置成空public void clear() top = 0;/ 测试栈是否为空public boolean isEmpty() return top = 0;/ 求栈中的数据元素个数并由函数
17、返回其值public int length() return top;/ 查看栈顶对象而不移除它，返回栈顶对象public Object peek() if (!isEmpty()/ 栈非空return stackElemtop - 1; / 栈顶元素else/ 栈为空return null;/ 移除栈顶对象并作为此函数的值返回该对象public Object pop() if (top = 0)/ 栈为空return null;else / 栈非空return stackElem-top;/ 修改栈顶指针，并返回栈顶元素/ 把o压入栈顶public void push(Object o) t
18、hrows Exception if (top = stackElem.length)/ 栈满throw new Exception(栈已满);/ 输出异常else/ 栈未满stackElemtop+ = o;/ o赋给栈顶元素后，top增1/ 打印函数，打印所有栈中的元素(栈顶到栈底)public void display() for (int i = top - 1; i = 0; i-)System.out.print(stackElemi.toString() + );/ 打印/测试类 public class Exercise3_4_1 public static void main
19、(String args) throws Exception SqStack S = new SqStack(100); / 初始化一个新的栈for (int i = 1; i = 10; i+)/ 初始化栈中的元素，其中元素个数为10 S.push(i);System.out.println(栈中各元素为(栈顶到栈底)： );S.display();/ 打印栈中元素（栈低到栈顶）System.out.println();if (!S.isEmpty()/ 栈非空，输出System.out.println(栈非空！);System.out.println(栈的长度为： + S.length()
20、;/ 输出栈的长度System.out.println(栈顶元素为： + S.peek().toString();/ 输出栈顶元素System.out.println(去除栈顶元素后，栈中各元素为(栈顶到栈底)： );S.pop();/ 删除元素S.display();/ 打印栈中元素System.out.println();System.out.println(去除栈中剩余的所有元素！ 进行中。); / 输出S.clear(); / 将栈清空if (S.isEmpty()/ 栈空，输出System.out.println(栈已清空!);运行结果：2. 在链队列类中增加一个main成员函数，使
21、其实际运行来测试链队列类中各成员函数的正确性。参考答案:package ch03Exercise;import ch02.Node;/链队列类class LinkQueue private Node front;/ 队头的引用private Node rear;/ 队尾的引用，指向队尾元素/ 链队列类的构造函数public LinkQueue() front = rear = null;/ 将一个已经存在的队列置成空public void clear() front = rear = null;/ 测试队列是否为空public boolean isEmpty() return front =
22、null;/ 求队列中的数据元素个数并由函数返回其值public int length() Node p = front;int length = 0;/ 队列的长度while (p != null) / 一直查找到队尾p = p.getNext();+length;/ 长度增1return length;/ 把指定的元素O插入队列public void offer(Object o) Node p = new Node(o);/ 初始化新的结点if (front != null) / 队列非空rear.setNext(p);rear = p;/ 改变队列尾的位置 else/ 队列为空fron
23、t = rear = p;/ 查看队列的头而不移除它，返回队列顶对象，如果此队列为空，则返回 nullpublic Object peek() if (front != null) / 队列非空return front.getData();/ 返回队列元素elsereturn null;/ 移除队列的头并作为此函数的值返回该对象，如果此队列为空，则返回 nullpublic Object poll() if (front != null) / 队列非空Node p = front;/ p指向队列头结点front = front.getNext();return p.getData();/ 返回
24、队列头结点数据 elsereturn null;/ 打印函数，打印所有队列中的元素(队列头到队列尾)public void display() if (!isEmpty() Node p = front;while (p != rear.getNext() / 从对头到队尾System.out.print(p.getData().toString() + );p = p.getNext(); else System.out.println(此队列为空);/测试类public class Exercise3_4_2 public static void main(String args) Lin
25、kQueue Q = new LinkQueue();for (int i = 1; i = 10; i+)/ 初始化队列中的元素，其中元素个数为10Q.offer(i);System.out.println(队列中各元素为(从队首到队尾)： );Q.display();/ 打印队列中元素（从队首到队尾）System.out.println();if (!Q.isEmpty()System.out.println(队列非空！);System.out.println(队列的长度为： + Q.length();/ 输出队列的长度System.out.println(队列头元素为： + Q.peek
26、().toString();/ 输出队列头元素System.out.println(去除队列头元素后，队列中各元素为(从队首到队尾)： );Q.poll();/ 删除元素Q.display();/ 打印队列中元素System.out.println();System.out.println(去除队列中剩余的所有元素！ 进行中。); / 输出Q.clear(); / 清除队列中的元素if (Q.isEmpty()/ 队列空，输出System.out.println(队列已清空!);运行结果：3. 设计一个循环顺序队列类。要求：(1) 循环顺序队列类采用设置标志位的方法来区分循环队列的判空和判满条
27、件。(2) 循环顺序队列类除构造函数外，成员函数还应包括入队、出队和判队列是否为空的函数。(3) 设计一个测试程序进行测试，并给出测试结果。参考答案:package ch03Exercise;import java.util.Scanner;/循环顺序队列类(采用设置标志位的方法来区分循环队列的判空和判满条件)class CircleSqQueue_flag private Object queueElem; / 队列存储空间private int front;/ 队头的引用，若队列不空，指向队首元素 private int rear;/ 队尾的引用，若队列不空，指向队尾元素的下一个位置 pr
28、ivate int flag; / 队列判空与判满的标志,当入列操作后其值置为1,出队操作后其值置为0/构造函数public CircleSqQueue_flag(int maxSize) queueElem = new ObjectmaxSize;/ 为队列分配maxSize个存储单元front =rear= 0;/ 队头、队尾初始化为0 flag = 0;/ 判断队列是否为空public boolean isEmpty() return front=rear&flag=0;/ 判断队列是否已满public boolean isFull() return front=rear&flag=1;
29、/ 入队操作方法:把指定的元素x插入队列public void offer(Object x) throws Exception if (isFull()/ 队列满throw new Exception(队列已满);/ 输出异常else / 队列未满queueElemrear = x;/ x赋给队尾元素rear = (rear + 1) % queueElem.length;/ 修改队尾指针 flag=1; /修改标志位值/出队操作方法: 移除队列的头并作为此函数的值返回该对象，如果此队列为空，则返回 nullpublic Object poll() if (isEmpty()/ 队列为空re
30、turn null;else Object t = queueElemfront;/ 取出队首元素front = (front + 1) % queueElem.length;/ 更改队首的位置flag=0; /修改标志位值return t;/ 返回队首元素/ 打印函数:打印所有队列中的元素(队首到队尾)public void display() if (!isEmpty() /队列非空/ 从队首到队尾 int i = front;do System.out.print(queueElemi.toString() + ); i = (i + 1)% queueElem.length; whil
31、e(i!=rear); else System.out.println(此队列为空);/测试类public class Exercise3_4_3 public static void main(String args) throws Exception CircleSqQueue_flag Q = new CircleSqQueue_flag(100);for (int i = 1; i = 10; i+)/ 初始化队列中的元素，其中元素个数为10Q.offer(i);System.out.println(队列中各元素为(队首到队尾)： );Q.display();/ 打印队列中元素（队首到
32、队尾）System.out.println();if (!Q.isEmpty()/ 队列非空，输出System.out.println(队列非空！);System.out.print(输入待入栈的元素值： ); Q.offer(new Scanner(System.in).next();/ 删除元素 System.out.println(入队后，队列中各元素为(队首到队尾)： ); Q.display(); / 打印队列中元素System.out.println(); System.out.println(去除队首元素后，队列中各元素为(队首到队尾)： );Q.poll();/ 队首元素出队Q
33、.display();/ 打印队列中元素System.out.println();运行结果：4. 设计一个数制转换类。要求： (1) 编写一个将十进制数转换成二进制数的方法。(2) 设计一个测试程序进行测试，并给出测试结果。参考答案:package ch03Exercise;import java.util.Scanner;import ch03.IStack;import ch03.LinkStack;public class Exercise3_4_4 public IStack convertDToB(int decimal) LinkStack S = new LinkStack();
34、while (decimal != 0) S.push(decimal % 2);/ 二进制位进栈decimal /= 2;return S;public static void main(String args) System.out.println(请输入一个十进制数：);Scanner sc = new Scanner(System.in);/ 构造用于输入的对象Exercise3_4_4 e = new Exercise3_4_4();int input = sc.nextInt();IStack S = e.convertDToB(input);/ 进行二进制转换System.out.println(input + 对应的二进制数位：);S.display();运行结果：