第三章栈与队列习题及答案

《第三章栈与队列习题及答案》由会员分享，可在线阅读，更多相关《第三章栈与队列习题及答案（12页珍藏版）》请在装配图网上搜索。

1、第三章 栈与队列 习题及答案 1/121/12 第三章 栈与队列 习题及答案 一、基础知识题 3.1 设将整数 1，2，3，4 依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为 Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop(),则出栈的数字序列为何(这里 Push(i)表示 i 进栈，Pop()表示出栈)?(2)能否得到出栈序列 1423 和 1432?并说明为什么不能得到或者如何得到。(3)请分析 1，2，3，4 的 24 种排列中，哪些序列是可以通过相应的入出栈操作得到的。3

2、.2 链栈中为何不设置头结点?答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。3.3 循环队列的优点是什么?如何判别它的空和满?答：循环队列的优点是：它可以克服顺序队列的假上溢现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的空或满不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间。每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到

3、队列中元素的个数。3.4 设长度为 n 的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何?若只设尾指针呢?答：当只设头指针时，出队的时间为 1，而入队的时间需要 n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为 1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。3.5 指出下述程序段的功能是什么?(1)void Demo1(SeqStack*S)int i;arr64;n=0;while(StackEmpty(S)arrn+=Pop(S);for(i=0,i n;i+)Push(S,a

4、rri);/Demo1 (2)SeqStack S1,S2,tmp;DataType x;./假设栈 tmp 和 S2 已做过初始化 while(!StackEmpty(&S1)x=Pop(&S1);Push(&tmp,x);while(!StackEmpty(&tmp)x=Pop(&tmp);Push(&S1,x);Push(&S2,x);第三章 栈与队列 习题及答案 2/122/12 (3)void Demo2(SeqStack*S,int m)/设 DataType 为 int 型 SeqStack T;int i;InitStack(&T);while(!StackEmpty(S)if

5、(i=Pop(S)!=m)Push(&T,i);while(!StackEmpty(&T)i=Pop(&T);Push(S,i);(4)void Demo3(CirQueue*Q)/设 DataType 为 int 型 int x;SeqStack S;InitStack(&S);while(!QueueEmpty(Q)x=DeQueue(Q);Push(&S,x);while(!StackEmpty(&s)x=Pop(&S);EnQueue(Q,x);/Demo3 (5)CirQueue Q1,Q2;/设 DataType 为 int 型 int x,i,m=0;./设 Q1 已有内容，Q2

6、 已初始化过 while(!QueueEmpty(&Q1)x=DeQueue(&Q1);EnQueue(&Q2,x);m+;for(i=0;i n;i+)x=DeQueue(&Q2);EnQueue(&Q1,x);EnQueue(&Q2,x);二、算法设计题 3.6 回文是指正读反读均相同的字符序列，如abba和abdba均是回文，但good不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)3.7 利用栈的基本操作，写一个将栈 S 中所有结点均删去的算法 void ClearStack(SeqStack*S)，并说明 S 为何要作为指针参数?3.8 利用栈的基本操作，

7、写一个返回 S 中结点个数的算法 int StackSize(SeqStack S),并说明S 为何不作为指针参数?3.9 设计算法判断一个算术表达式的圆括号是否正确配对。(提示：对表达式进行扫描，凡遇到(就进栈，遇)就退掉栈顶的(，表达式被扫描完毕，栈应为空。第三章 栈与队列 习题及答案 3/123/12 3.10 一个双向栈 S 是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化 InitStack(S)、入栈 Push(S,i,x)和出栈 Pop(S,i)等算法，其中 i 为 0 或 1，用以表示栈号。3.11 Ackerman 函数定义如下：请写出

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

9、个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。答案：3.2 答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。3.3 答：循环队列的优点是：它可以克服顺序队列的假上溢现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的空或满不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间。每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素

10、总数，不仅可判别空或满，还可以得到队列中元素的个数。3.4 答：当只设头指针时，出队的时间为 1，而入队的时间需要 n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为 1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。3.5 答：(1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在 64 个以内。(2)程序段的功能是利用 tmp 栈将一个非空栈的所有元素按原样复制到一个空栈当中去。(3)程序段的功能是将一个非空栈中值等于 m 的元

11、素全部删去。(4)程序段的功能是将一个循环队列反向排列，原来的队头变成队尾，原来的队尾变成队头。(5)首先指出程序可能有印刷错误，for 语句中的 n 应为 m 才对。这段程序的功能是将队列 1的所有元素复制到队列 2 中去，但其执行过程是先把队列 1 的元素全部出队，进入队列 2，然后再把队列 2 的元素复制到队列 1 中。3.6 解：根据提示，算法可设计为：/ishuiwen.h 存为头文件 第三章 栈与队列 习题及答案 4/124/12 int IsHuiwen(char*S)SeqStack T;int i,l;char t;InitStack(&T);l=strlen(S);/求向量

12、长度 for(i=0;il/2;i+)/将一半字符入栈 Push(&T,Si);while(!EmptyStack(&T)/每弹出一个字符与相应字符比较 t=Pop(&T);if(t!=Sl-i)return 0;/不等则返回 0 i-;return -1;/比较完毕均相等则返回-1 /以下程序用于验证上面的算法 /以下是栈定义(存为 stack.h)/出错控制函数#include#include void Error(char*message)fprintf(stderr,Error:%sn,message);exit(1);/定义栈类型#define StackSize 100 typed

13、ef char Datatype;typedef struct Datatype dataStackSize;int Top;SeqStack;void InitStack(SeqStack*S)/初始化(置空栈)S-Top=-1;第三章 栈与队列 习题及答案 5/125/12 int EmptyStack(SeqStack*S)/判栈空 return S-Top=-1;int FullStack(SeqStack*S)/判栈满 return S-Top=StackSize-1;void Push(SeqStack*S,Datatype x)/进栈 if(FullStack(S)Error(S

14、tack overflow);S-data+S-Top=x;Datatype Pop(SeqStack*S)/出栈(退栈)if(EmptyStack(S)Error(Stack underflow);return S-dataS-Top-;/取栈顶元素(略)/-/以下是主程序#include#include#include stack.h#include ishuiwen.h void main()char Str100=;printf(输入一个字符串:n);scanf(%s,Str);第三章 栈与队列 习题及答案 6/126/12 if(IsHuiwen(Str)printf(n 这个字符串

15、是回文。);else printf(n 这个字符串不是回文。);3.7 解：算法如下 void ClearStack(SeqStack*S)/删除栈中所有结点 S-Top=-1;/其实只是将栈置空 因为我们要置空的是栈 S，如果不用指针来做参数传递，那么函数进行的操作不能对原来的栈产生影响，系统将会在内存中开辟另外的单元来对形参进行函数操作。结果等于什么也没有做。所以想要把函数操作的结果返回给实参的话，就只能用指针来做参数传递了。3.8 解：算法如下：int StackSize(SeqStack S)/计算栈中结点个数 int n=0;if(!EmptyStack(&S)Pop(&S);n+;

16、return n;类似于上面的原因，我们要计算栈中元素个数就要弹出元素才能数得出来，那如果用指针做参数的话，就会把原来的栈中元素弹光，要恢复还得用别的办法给它装回去，而不用指针做参数，则可以避免对原来的栈中元素进行任何操作，系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数就可以了。3.9 解：根据提示，可以设计算法如下：#include#include stack.h int PairBracket(char*S)/检查表达式中括号是否配对 int i;SeqStack T;/定义一个栈 InitStack(&T);for(i=0;itop0=-1;S-top1=Stac

17、kSize;/这里的 top2 也指出了向量空间，但由于是作为栈底，因此不会出错 int EmptyStack(DblStack*S,int i)/判栈空(栈号 i)return (i=0&S-top0=-1|i=1&S-top1=StackSize);int FullStack(DblStack*S)/判栈满,满时肯定两头相遇 return(S-top0=S-top1-1);void Push(DblStack*S,int i,Datatype x)/进栈(栈号 i)if(FullStack(S)Error(Stack overflow);/上溢、退出运行 if(i=0)S-Data+S-t

18、op0=x;/栈 0 入栈 if(i=1)S-Data-S-top1=x;/栈 1 入栈 Datatype Pop(DblStack*S,int i)/出栈(栈号 i)第三章 栈与队列 习题及答案 8/128/12 if(EmptyStack(S,i)Error(Stack underflow);/下溢退出 if(i=0)return(S-Data S-top0-);/返回栈顶元素，指针值减 1 if(i=1)return(S-Data S-top1+);/因为这个栈是以另一端为底的，所以指针值加 1。/其余算法略,以上算法没有上机调试过，请学友自行验证一下。主要是我们理解了算法也就可以了。3

19、.11 解：算法如下 int AKM(int m,int n)if(m=0)return n+1;if(m0&n=0)return AKM(m-1,1);if(m0&n0)return AKM(m-1,AKM(m,n-1);3.12 解：算法设计如下:/存为 Queue2.h 文件 void InitQueue(CirQueue *Q)/置空队 Q-front=Q-rear=0;int EmptyQueue(CirQueue*Q)/判队空 return Q-front=Q-rear;int FullQueue(CirQueue*Q)/判队满/如果尾指针加 1 后等于头指针，则认为满 retur

20、n(Q-rear+1)%QueueSize=Q-front;Datatype DeQueue(CirQueue*Q)/出队 if(EmptyQueue(Q)Error(队已空，无元素可以出队);Datatype temp;temp=Q-DataQ-front;/保存元素值 Q-front=(Q-front+1)%QueueSize;/循环意义上的加 1 第三章 栈与队列 习题及答案 9/129/12 return temp;/返回元素值 void EnQueue(CirQueue*Q,Datatype x)/入队 if(FullQueue(Q)Error(队已满，不可以入队);Q-DataQ-

21、rear=x;Q-rear=(Q-rear+1)%QueueSize;/rear 指向下一个空元素位置 Datatype FrontQueue(CirQueue*Q)/取队头元素 if(EmptyQueue(Q)Error(队空，无元素可取);return Q-DataQ-front;/为了验证上述算法是否正确，晓津设计了以下程序/循环队列的定义 存入 StructQ.h 文件中#define QueueSize 10 /为便与验证，这里假设为 10 个元素的空间 typedef char Datatype ;/设元素的类型为 char 型 typedef struct int front;i

22、nt rear;Datatype DataQueueSize;CirQueue;/以下是主程序,用来验证算法#include#include#include StrctQ.h/包含队列结构#include Queue2.h/包含算法头文件 /-出错控制程序#include void Error(char*message)fprintf(stderr,Error:%sn,message);exit(1);/-主函数-第三章 栈与队列 习题及答案 10/1210/12 void main()int i;CirQueue Q;/定义一个循环队列 InitQueue(&Q);/初始化队列 printf

23、(please enter characters:n);for(i=0;i QueueSize-1;i+)EnQueue(&Q,getchar();printf(n);if(!EmptyQueue(&Q)/先输出一个头元素 printf(frontData is%c,FrontQueue(&Q);printf(n);while(!EmptyQueue(&Q)/如果非空就把队列中的元素输出 printf(%c,DeQueue(&Q);printf(nPlease enter characters again:n);for(i=0;irear=Q-rear-next;/头结点成为尾结点 Q-rea

24、r-next=Q-rear;/形成循环链表 int EmptyQueue(LinkQueue*Q)第三章 栈与队列 习题及答案 11/1211/12 /判队空 /当头结点的 next 指针指向自己时为空队 return Q-rear-next-next=Q-rear-next;void EnQueue(LinkQueue*Q,Datatype x)/入队 /也就是在尾结点处插入元素 QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode);/申请新结点 p-data=x;p-next=NULL;/初始化结点 Q-rear-next-next=p;/将新结

25、点链入 p-next=Q-rear;/形成循环链表 Q-rear=p;/将尾指针移至新结点 Datatype DeQueue(LinkQueue*Q)/出队 /把头结点之后的元素摘下 Datatype t;QueueNode*p;if(EmptyQueue(Q)Error(Queue underflow);p=Q-rear-next-next;/将要摘下的结点 x=p-data;/保存结点中数据 Q-rear-next-next=p-next;/摘下结点 p free(p);/释放被删结点 return x;3.14 解：公式如下：0 EmptyQueue Queuelen=rear-fron

26、t rearfront rear+QueueSize-front rearquelen=QueueSize;void EnQueue(CirQueue *Q,Datatype x)/入队 第三章 栈与队列 习题及答案 12/1212/12 if(FullQueue(Q)Error(队已满，无法入队);Q-DataQ-rear=x;Q-rear=(Q-rear+1)%QueueSize;/在循环意义上的加 1 Q-quelen+;Datatype DeQueue(CirQueue*Q)/出队 if(Q-quelen=0)Error(队已空，无元素可出队);int tmpfront;/设一个临时队头指针 if(Q-rear Q-quelen)/计算头指针位置 tmpfront=Q-rear-Q-quelen;else tmpfront=Q-rear+QueueSize-Q-quelen;quelen-;return Q-Datatmpfront;/如果需要验证上面的算法，则需定义好结点类型的队列结构，以相应的变量来表示尾指针和队列长度。自己试试吧。最主要的是能够理解算法的意义和实现。