第4章 栈与队列.doc

第四章习题参考答案一、简答题1. 【参考答案】 ：栈是满足“LIFO后进先出”的特点，即只在线性表的一端进行插入、删除等操作的顺序表。队列是满足“FIFO后进先出”的特点，即可在线性表的一端进行插入、另一端进行删除操作的线性表。2【参考答案】 ：顺序栈的结构和高级语言中的数组一样，在存储结构方面都可用一段连续的空间存储栈中的各个元素。但是在操作时，数据可以对每个元素进行操作，而顺序栈只能在固定的栈顶元素进行操作。3【参考答案】 ：栈的两种存储结构分别为顺序栈和链栈。其应用如下:表达式求解、递归问题求解过程等。4【参考答案】 ：当top达到数组的最大值an时，表示栈满状态，此时，只能进行出栈操作，而不能进行入栈操作。5【参考答案】 ：4辆车时，结果：001，002，003，004 001，004，003，002 001，002，004，003 001，003，002，004 001，003，004，002 002，001，003，004 002，001，004，003 002，003，004，001 002，003，001，004 002，004，003，001 003，002，001，004 003，004，002，001 003，002，004，001 004，003，002，0013辆车时，结果：001，002，003 001，003，002 002，001，003 002，003，001 003，002，0016【参考答案】 ：队列的两种存储结构分别为顺序队列和链队列。排队实例、汽车通过某站点顺序问题求解实例、二叉树的层次遍历等都是队列的应用。7【参考答案】 ：解决假上溢现象，可将最大值（假设为n）的下一个元素设置成整个队列的第一个元素，这样使队列形成了一个环，称为环形队列，这样可充分利用存储空间。8.【参考答案】 ：符合栈操作的实例：表达式求解，其过程如本章第12题过程实现。符合队列操作的实例：汽车通过某站点顺序问题，其求解过程比较简单，此处略。二、简答题1【参考答案】 ：参考教材中例题，此处略。2【参考答案】 ：import java.util.Vector;import java.util.Stack;public class ArrayStack int top; int stack; public ArrayStack(int initialCapacity) if(initialCapacity1); stack=new intinitialCapacity; top=-1; public boolean empty() return top=-1; public void push(int theElement) if(top=stack.length-1) System.out.println(栈满！); stack+top=theElement; public int pop() if(empty() System.out.println(此栈为空，不能出栈！); int topElement=stacktop; top-; return topElement; public static void main(String args) ArrayStack array=new ArrayStack(50); int f=new int50; int sum=0; f0=0; f1=1; array.push(f0); array.push(f1); for(int n=2;n50;n+) fn=fn-1+fn-2; array.push(fn); System.out.println(该数列的前50项为:); for(int n=0;n50;n+) System.out.println(fn+,); 3【参考答案】 ：import java.util.*; public class N public static void main(String args) Scanner reader=new Scanner(System.in); System.out.println(请输入一正整数); int x=reader.nextInt(); System.out.println(请输入另一正整数); int y=reader.nextInt(); set(x,y); public static void set(int m,int n) int temp; if(mn) temp=m; m=n; n=temp; while(n!=0) temp=m%n; m=n; n=temp; System.out.println(两数的最大公因数为:+m); 4【参考答案】 ：-3030，-入栈*5-303*5-305，*入栈，后面遇到括号/3*5-303入栈0.4*5-30/入栈/ 后为7，3，/出栈计算3/7结果入栈-19.6*5-30-，20入栈，并得到下一个20判断其后为），0.4，-，20出栈-98-30-19.6,*,5出栈,并运算得-98结果128-98,-出栈，30出栈并运算得12820-0.4*5-30-19.6三、思考题1【参考答案】 ：栈是限制在一端进行