第3章栈和队列(习题)

《第3章栈和队列(习题)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第3章栈和队列课堂练习K栈和队列是的线性表;▲2、有一栈，元素A,B,C,D只能依次进栈，则出栈序列中以下哪个是不可能得到的。()①D、C、B、A(3)A、B、C、D②C、B、A、D④D、C、A、B3、试写出队列中的出队算法。习题一、基础知识题A3.1设将整数1,2,3,4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：▲⑴若入、出栈次序为Push(l),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop()，则出栈的数字序列为

2、何(这里Push(i)表示i进栈，Pop()表示出栈)？▲(2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。(3)请分析1,2,3,4的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。A3.2链栈中为何不设置头结点?▲3.3循环队列的优点是什么？如何判别它的空和满？▲3.4设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何？若只设尾指针呢？3.5指出下述程序段的功能是什么？(1)AvoidDemol(SeqStack*S){inti,arr[64

3、],n=0;wh订e(IStackEmpty(S))arr[n++]=Pop(S):for(i=0;i

4、SeqStack*S,intm){//设DataType为int型SeqStackT:inti;InitStack(&T);whi.le(!StackEmpty(S))if((i=Pop(S))!=m)Push(&T,i);wh订e(!StackEmpty(&T)){i=Pop(&T);Push(S,i);}}(3)voidDemo3(CirQueue*Q){//设DataType为int型intx;SeqStackS;InitStack(&S);whi.le(!QueueEmpty(Q)){x二D

5、eQueue(Q);Push(&S,x);}wh订e(!StackEmpty(&s)){x=Pop(&S);EnQueue(Q,x);}}//Demo3(3)CirQueueQI,Q2;//设DataType为int型intx,i,m=0;...//设QI已有内容，Q2已初始化过wh订e(!QueueEmpty(&Q1))x);m++;};EnQueue(&Q2,x);}{x二DeQueue(&Q1);EnQueue(&Q2,for(i=0;i

6、ue(&Q1,x)二、算法设计题A3.6回文是指正读反读均相同的字符序列,如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)3.7利用栈的基本操作，写一个将栈S中所有结点均删去的算法voidClearStack(SeqStack*S),并说明S为何要作为指针参数？3.8利用栈的基本操作，写一个返回S中结点个数的算法intStackSize(SeqStackS),并说明S为何不作为指针参数?A3.9设计算法判断一个算术表达

7、式的圆括号是否正确配对。(提示：对表达式进行扫描，凡遇到’('就进栈，遇就退掉栈顶的’(',表达式被扫描完毕，栈应为空。3.10一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化InitStack(S)、入栈Push(S,i,x)和出栈Pop(S,i)等算法，其中i为0或1,用以表示栈号。A3.11Ackerman函数定义如下：请写出递归算法。[n+1当m=0时AKM(m,n)二｛AKM(m-1,1)当mHO,n二0时[AKM(m-1,AKM(m,n

8、-1))当mHO,n工0时3.12用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队.入队及取队头元素等六个基本操作的算法。3.13假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的置空队、判队空、入队和出队等算法。A3.14对于循环向量中的循环队列，写出求队列长度的公式。A3.15假设循环队列中只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给