第3章 栈与队列习题参考答案.docx
- 文档编号:10252976
- 上传时间:2023-05-24
- 格式:DOCX
- 页数:22
- 大小:59.75KB
第3章 栈与队列习题参考答案.docx
《第3章 栈与队列习题参考答案.docx》由会员分享,可在线阅读,更多相关《第3章 栈与队列习题参考答案.docx(22页珍藏版)》请在冰点文库上搜索。
第3章栈与队列习题参考答案
习题三参考答案
备注:
红色字体标明的是与书本内容有改动的内容。
一、选择题
1.在栈中存取数据的原则是(B)。
A.先进先出B.先进后出
C.后进后出D.没有限制
2.若将整数1、2、3、4依次进栈,则不可能得到的出栈序列是(D)。
A.1234B.1324C.4321D.1423
3.在链栈中,进行出栈操作时(B)。
A.需要判断栈是否满B.需要判断栈是否为空
C.需要判断栈元素的类型D.无需对栈作任何差别
4.在顺序栈中,若栈顶指针top指向栈顶元素的下一个存储单元,且顺序栈的最大容量是maxSize,则顺序栈的判空条件是(A)。
A.top==0B.top==-1C.top==maxSizeD.top==maxSize-1
5.在顺序栈中,若栈顶指针top指向栈顶元素的下一个存储单元,且顺序栈的最大容量是maxSize。
则顺序栈的判满的条件是(C)。
A.top==0B.top==-1C.top==maxSizeD.top==maxSize-1
6.在队列中存取数据元素的原则是(A)。
A.先进先出B.先进后出
C.后进后出D.没有限制
7.在循环顺序队列中,假设以少用一个存储单元的方法来区分队列判满和判空的条件,front和rear分别为队首和队尾指针,它们分别指向队首元素和队尾元素的下一个存储单元,队列的最大存储容量为maxSize,则队列的判空条件是(A)。
A.front==rearB.front!
=rear
C.front==rear+1D.front==(rear+1)%maxSize
8.在循环顺序队列中,假设以少用一个存储单元的方法来区分队列判满和判空的条件,front和rear分别为队首和队尾指针,它们分别指向队首元素和队尾元素的下一个存储单元,队列的最大存储容量为maxSize,则队列的判满条件是(D)。
A.front==rearB.front!
=rear
C.front==rear+1D.front==(rear+1)%maxSize
9.在循环顺序队列中,假设以少用一个存储单元的方法来区分队列判满和判空的条件,front和rear分别为队首和队尾指针,它们分别指向队首元素和队尾元素的下一个存储单元,队列的最大存储容量为maxSize,则队列的长度是(C)。
A.rear-frontB.rear-front+1
C.(rear-front+maxSize)%maxSizeD.(rear-front+1)%maxSize
10.设长度为n的链队列采用单循环链表加以表示,若只设一个头指针指向队首元素,则入队操作的时间复杂度为(B)。
A.O
(1)B.O(n)C.O(log2n)D.O(n2)
二、填空题
1.栈是一种操作受限的特殊线性表,其特殊性体现在其插入和删除操作都限制在表尾进行。
允许插入和删除操作的一端称为栈顶,而另一端称为栈底。
栈具有后进先出的特点。
2.栈也有两种存储结构,一种是顺序存储,另一种是链式存储;以这两种存储结构存储的栈分别称为顺序栈和链栈。
3.在顺序栈中,假设栈顶指针top是指向栈顶元素的下一个存储单元,则顺序栈判空的条件是top==0;栈顶元素的访问形式是stackElem[top-1];
4.在不带表头结点的链栈中,若栈顶指针top直接指向栈顶元素,则将一个新结点p入栈时修改链的两个对应语句为p.setNext(top);top=p;。
5.在不带表头结点的链栈中,若栈顶指针top直接指向栈顶元素,则栈顶元素出栈时的修改链的对应语句为top=top.getNext();。
6.队列也是一种操作受限的线性表,它与栈不同的是,队列中所有的插入操作均限制在表的一端进行,而所有的删除操作都限制在表的另一端进行,允许插入的一端称为队尾,允许删除的一端称为队首。
队列具有先进先出的特点。
7.由于队列的删除和插入操作分别在队首和队尾进行,因此,在链式存储结构描述中分别需要设置两个指针分别指向队首结点和队尾结点,这两个指针又分别称为
队首指针和队尾指针。
8.循环顺序队列是将顺序队列的存储区域看成是一个首尾相连的环,首尾相连的状态是通过数学上的求模(或取余)运算来实现的。
9.在循环顺序队列中,若规定当front==rear时,循环队列为空;当front==(rear+1)%maxSize时,循环队列为满,则入队操作时的队尾指针变化的相应语句是rear=(rear+1)%maxSize;出队操作时的队首指针变化的相应语句是front=(front+1)%maxSize。
10.无论是顺序栈还是顺序队列,插入元素时必须先进行栈或队列是否为满的判断,删除元素时必须先进行栈或队列是否为空的判断;而链栈或链队列中,插入元素无需进行栈或队列是否为满的判断,只要在删除元素时先进行栈或队列是否为空的判断。
三、算法设计题
1.编写一个函数,要求借助一个栈把一个数组中的数据元素逆置。
参考答案:
//借助一个顺序栈将已知一个数组中的数据元素逆置
publicreverse(Object[]a)throwsException{
SqStackS=newSqStack(a.length);//构造一个容量为a.length的顺序栈
for(inti=0;i S.push(a[i]); for(inti=0;i a[i]=S.pop(); } 2.编写一个函数判断一个字符序列是否为回文序列,所谓回文序列就是正读与反读都相同的字符序列,例如: abba和abdba均是回文序列。 要求只使用栈来实现。 参考答案: //判断字符序列是否为回文序列,若是则返回true值,否则返回false。 publicbooleanisPalindSeq(Stringstr){ LinkStackS=newLinkStack(); inti=0; for(;i S.push(str.charAt(i)); for(i=0;i charc=((Character)S.pop()).charValue(); if(c! =str.charAt(i)) returnfalse; } returntrue; } 3.假设以一个数组实现两个栈: 一个栈以数组的第一个存储单元作为栈底,另一个栈以数组的最后一个存储单元作为栈底,这种栈称为顺序双向栈。 试编写一个顺序双向栈类DuSqStack,类中要求编写3个方法。 一个是构造方法DuDuSqStack(intmaxSize),此方法实现构造一个容量为maxSize的顺序双向空栈;一个是实现入栈操作的方法push(ObjectX,inti),此方法完成将数据元素X压入到第i(i=0或1)号栈中的操作;一个是实现出栈操作的方法pop(inti),此方法完成将第i号栈的栈顶元素出栈的操作。 参考答案: classDuSqStack{ privateObject[]stackElem;//栈存储空间 privateinttop0;//栈顶指针,指示第0号的栈顶元素的下一个位置 privateinttop1;//栈顶指针,指示第1号的栈顶元素的下一个位置 privateintbase0;//栈尾指针,指示第0号的栈底元素 privateintbase1;//栈尾指针,指示第1号的栈底元素 //构造方法 publicDuSqStack(intmaxSize){ //初始化栈,即构造一个双向空栈 stackElem=newObject[maxSize];//为栈分配maxSize个存储单元 top0=base0=0; top1=base1=maxSize-1; } //入栈操作方法 publicvoidpush(ObjectX,inti)throwsException{ //将数据元素X压入到第i(i的值为0或1)号栈中 if(top0>top1)//栈满 thrownewException("栈已满");//抛出异常 elseif(i==0) stackElem[top0++]=X; elseif(i==1) stackElem[top1--]=X; } //出栈操作方法 publicObjectpop(inti)throwsException{ //将S中第i号栈的栈顶元素出栈,并返回栈顶元素值 Objectx=null; if(i==0) if(top0==base0) thrownewException("第0号栈为空"); else x=stackElem[--top0]; elseif(i==1) if(top1==base1) thrownewException("第0号栈为空"); else x=stackElem[++top1]; returnx; } }//DuSqStack类结束 4.循环顺序队列类采用设置一个计数器的方法来区分循环队列的判空和判满。 试分别编写顺序循环队列中入队和出队操作的函数。 参考答案: //循环顺序队列存储结构类描述如下: classCircleSqQueue_num{ privateObject[]queueElem;//队列存储空间 privateintfront;//队首的引用,若队列不空,指向队首元素,初值为0 privateintrear;//队尾的引用,若队列不空,指向队尾元素的下一个位置,初值为0 privateintnum;//计数器用来记录队列中的数据元素个数 …… }//CircleSqQueue_num类结束 为类CircleSqQueue_num所编写的入队和出队操作方法如下: //入队操作方法 publicvoidoffer(Objectx)throwsException{//把指定的元素x插入队列 if(num==queueElem.length)//队列满 thrownewException("队列已满");//输出异常 else{//队列未满 queueElem[rear]=x;//x加入队尾 rear=(rear+1)%queueElem.length;//更改队尾的位置 ++num;//计数器加1 } } //出队操作方法 publicObjectpoll(){ //移除队首元素并作为此函数的值返回该对象,如果此队列为空,则返回null if(num==0)//队列为空 returnnull; else{ Objectt=queueElem[front];//取出队首元素 front=(front+1)%queueElem.length;//更改队首的位置 --num;//计数器减1 returnt;//返回队首元素 } } 5.假设采用带头结点的循环链表来表示队列,并且只设一个指向队尾元素的指针(不设队首指针),试编写相应的队列置空、队列判空、入队和出队操作的函数。 参考答案: 用队尾指针标识的循环链队列的类描述如下: classCircleLinkQueue{ privateNoderear;//循环链队列的尾指针 …… } 为此类编写的队列置空、队列判空、入队和出队操作的方法分别如下: //队列置空操作方法 publicvoidclear(){ //将一个已经存在的带头结点的循环链队列置成空队列 rear.setNext(rear); } //入队操作方法 publicvoidoffer(Objectx)throwsException{ //将指定的元素x插入到带头结点的循环链队列中 Nodep=newNode(x);//生成新结点 p.setNext(rear.getNext());//插入链列列的尾部 rear.setNext(p); rear=p; } //出队操作方法 publicvoidpoll()throwsException{ //移除带头结点的循环链队列中的队首元素并作为此函数的值返回该对象,如果此队列为空,则返回null Nodep=rear.getNext().getNext();//p指向待删除的队首结点 if(p==rear) rear.setNext(rear);//删除队首结点后,链队列变成了空链队列 else rear.getNext().setNext(p.getNext());//删除队首结点 } 四、上机实践题 1.在顺序栈类中增加一个main成员函数,使其实际运行来测试顺序栈类中各成员函数的正确性。 参考答案: packagech03Exercise; //顺序栈类 publicclassSqStack{ privateObject[]stackElem;//栈存储空间 privateinttop;//非空栈中始终表示栈顶元素的下一个位置,当栈为空时其值为0 //栈的构造函数,构造一个存储空间容量为maxSize的栈 publicSqStack(intmaxSize){ top=0;//初始化top为0 stackElem=newObject[maxSize];//为栈分配maxSize个存储单元 } //将一个已经存在的栈置成空 publicvoidclear(){ top=0; } //测试栈是否为空 publicbooleanisEmpty(){ returntop==0; } //求栈中的数据元素个数并由函数返回其值 publicintlength(){ returntop; } //查看栈顶对象而不移除它,返回栈顶对象 publicObjectpeek(){ if(! isEmpty())//栈非空 returnstackElem[top-1];//栈顶元素 else //栈为空 returnnull; } //移除栈顶对象并作为此函数的值返回该对象 publicObjectpop(){ if(top==0)//栈为空 returnnull; else{//栈非空 returnstackElem[--top];//修改栈顶指针,并返回栈顶元素 } } //把o压入栈顶 publicvoidpush(Objecto)throwsException{ if(top==stackElem.length)//栈满 thrownewException("栈已满");//输出异常 else //栈未满 stackElem[top++]=o;//o赋给栈顶元素后,top增1 } //打印函数,打印所有栈中的元素(栈顶到栈底) publicvoiddisplay(){ for(inti=top-1;i>=0;i--) System.out.print(stackElem[i].toString()+"");//打印 } } //测试类 publicclassExercise3_4_1{ publicstaticvoidmain(String[]args)throwsException{ SqStackS=newSqStack(100);//初始化一个新的栈 for(inti=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());//输出栈的长度 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成员函数,使其实际运行来测试链队列类中各成员函数的正确性。 参考答案: packagech03Exercise; importch02.Node; //链队列类 classLinkQueue{ privateNodefront;//队头的引用 privateNoderear;//队尾的引用,指向队尾元素 //链队列类的构造函数 publicLinkQueue(){ front=rear=null; } //将一个已经存在的队列置成空 publicvoidclear(){ front=rear=null; } //测试队列是否为空 publicbooleanisEmpty(){ returnfront==null; } //求队列中的数据元素个数并由函数返回其值 publicintlength(){ Nodep=front; intlength=0;//队列的长度 while(p! =null){//一直查找到队尾 p=p.getNext(); ++length;//长度增1 } returnlength; } //把指定的元素O插入队列 publicvoidoffer(Objecto){ Nodep=newNode(o);//初始化新的结点 if(front! =null){//队列非空 rear.setNext(p); rear=p;//改变队列尾的位置 }else //队列为空 front=rear=p; } //查看队列的头而不移除它,返回队列顶对象,如果此队列为空,则返回null publicObjectpeek(){ if(front! =null)//队列非空 returnfront.getData();//返回队列元素 else returnnull; } //移除队列的头并作为此函数的值返回该对象,如果此队列为空,则返回null publicObjectpoll(){ if(front! =null){//队列非空 Nodep=front;//p指向队列头结点 front=front.getNext(); returnp.getData();//返回队列头结点数据 }else returnnull; } //打印函数,打印所有队列中的元素(队列头到队列尾) publicvoiddisplay(){ if(! isEmpty()){ Nodep=front; while(p! =rear.getNext()){//从对头到队尾 System.out.print(p.getData().toString()+""); p=p.getNext(); } }else{ System.out.println("此队列为空"); } } } //测试类 publicclassExercise3_4_2{ publicstaticvoidmain(String[]args){ LinkQueueQ=newLinkQueue(); for(inti=1;i<=10;i++) //初始化队列中的元素,其中元素个数为10 Q.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().toString());//输出队列头元素 System.out.println("去除队列头元素后,队列中各元素为(从队首到队尾): "); Q.poll();//删除元素 Q.display();//打印队列中元素 System.out.println(); System.out.println("去除队列中剩余的所有元素! 进行中。 。 。 ");//输出 Q.clear();//清除队列中的元素 if(Q.isEmpty())//队列空,输出 Syst
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第3章 栈与队列习题参考答案 队列 习题 参考答案