《第三章-栈与队列---习题及答案.doc》由会员分享，可在线阅读，更多相关《第三章-栈与队列---习题及答案.doc（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精品文档，仅供学习与交流，如有侵权请联系网站删除第三章 栈与队列 习题及答案一、基础知识题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种排列中，哪些序列是可以通过相应的入出栈操作得到的。
2、3.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
4、; i+) Push(S, arri); /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);(3) void Demo2( SeqStack *S, int m) / 设DataType 为int 型SeqStack T; int i;InitStack (&T);while (! Sta
5、ckEmpty( S)if( 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; / 设Dat
6、aType 为int 型int x, i , m = 0;. / 设Q1已有内容， Q2已初始化过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中所
7、有结点均删去的算法void ClearStack( SeqStack *S)，并说明S为何要作为指针参数? 3.8 利用栈的基本操作， 写一个返回S中结点个数的算法 int StackSize( SeqStack S),并说明S为何不作为指针参数? 3.9 设计算法判断一个算术表达式的圆括号是否正确配对。 (提示： 对表达式进行扫描，凡遇到(就进栈，遇)就退掉栈顶的(，表达式被扫描完毕，栈应为空。 3.10 一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop(
8、 S , i )等算法， 其中i为0 或1， 用以表示栈号。 3.11 Ackerman 函数定义如下：请写出递归算法。 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
9、对于循环向量中的循环队列，写出求队列长度的公式。 3.15 假设循环队列中只设rear和quelen 来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。 答案：3.2 答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。3.3 答：循环队列的优点是：它可以克服顺序队列的假上溢现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的空或满不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量
10、来区别队列的空和满。二是少用一个元素的空间。每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。3.4答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。3.5 答：(1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。(2)程
11、序段的功能是利用tmp栈将一个非空栈的所有元素按原样复制到一个空栈当中去。(3)程序段的功能是将一个非空栈中值等于m的元素全部删去。(4)程序段的功能是将一个循环队列反向排列，原来的队头变成队尾，原来的队尾变成队头。(5)首先指出程序可能有印刷错误，for语句中的n应为m才对。这段程序的功能是将队列1的所有元素复制到队列2中去，但其执行过程是先把队列1的元素全部出队，进入队列2，然后再把队列2的元素复制到队列1中。3.6 解：根据提示，算法可设计为：/ishuiwen.h 存为头文件int IsHuiwen( char *S)SeqStack T;int i , l;char t;InitSt
12、ack( &T);l=strlen(S);/求向量长度for ( i=0; il/2; i+)/将一半字符入栈Push( &T, Si);while( !EmptyStack( &T)/ 每弹出一个字符与相应字符比较t=Pop (&T);if( t!=Sl-i) return 0 ;/ 不等则返回0i-;return -1 ;/ 比较完毕均相等则返回 -1/ 以下程序用于验证上面的算法/以下是栈定义( 存为stack.h)/出错控制函数#include #include void Error(char * message)fprintf(stderr, Error: %sn,message);
13、exit(1);/ 定义栈类型#define StackSize 100typedef char Datatype;typedef structDatatype dataStackSize;int Top; SeqStack;void InitStack( SeqStack *S)/初始化(置空栈)S-Top=-1;int EmptyStack(SeqStack *S)/判栈空return S-Top = -1;int FullStack (SeqStack *S)/ 判栈满return S-Top=StackSize-1; void Push (SeqStack *S , Datatype
14、x)/进栈if(FullStack(S) Error(Stack 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.hvoid main( )char Str100=;printf(输入一个字符串:n);scanf(%s,Str);if( IsHuiwen(Str)pr
15、intf( n这个字符串是回文。);else printf(n这个字符串不是回文。);3.7解： 算法如下void ClearStack (SeqStack *S)/ 删除栈中所有结点S-Top = -1; /其实只是将栈置空因为我们要置空的是栈S，如果不用指针来做参数传递，那么函数进行的操作不能对原来的栈产生影响，系统将会在内存中开辟另外的单元来对形参进行函数操作。结果等于什么也没有做。所以想要把函数操作的结果返回给实参的话，就只能用指针来做参数传递了。3.8 解：算法如下：int StackSize (SeqStack S)/计算栈中结点个数int n=0;if(!EmptyStack(&
16、S)Pop(&S);n+;return n;类似于上面的原因，我们要计算栈中元素个数就要弹出元素才能数得出来，那如果用指针做参数的话，就会把原来的栈中元素弹光，要恢复还得用别的办法给它装回去，而不用指针做参数，则可以避免对原来的栈中元素进行任何操作，系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数就可以了。3.9 解：根据提示，可以设计算法如下：#include #include stack.hint PairBracket( char *S)/检查表达式中括号是否配对int i;SeqStack T;/定义一个栈InitStack (&T);for (i=0; itop
17、0 = -1;S-top1 = StackSize; /这里的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 ) Err
18、or(Stack overflow);/上溢、退出运行if ( i = 0) S-Data + S-top0= x; /栈0入栈if ( i = 1) S-Data - S-top1= x; / 栈1入栈Datatype Pop(DblStack *S, int i)/出栈(栈号i)if (EmptyStack ( S,i) ) Error(Stack underflow);/下溢退出if( i=0 ) return ( S-Data S-top0- );/返回栈顶元素，指针值减1if( i=1 )return ( S-Data S-top1+ ); /因为这个栈是以另一端为底的，所以指针值加
19、1。/其余算法略 ,以上算法没有上机调试过，请学友自行验证一下。主要是我们理解了算法也就可以了。3.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
20、 Q-front=Q-rear;int FullQueue( CirQueue *Q)/ 判队满/如果尾指针加1后等于头指针，则认为满return (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;/循环意义上的加1return temp; /返回元素值void EnQueue (CirQueue *Q,
21、 Datatype x) / 入队if( FullQueue( Q)Error (队已满，不可以入队);Q-DataQ-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个元素的空间typede
22、f char Datatype ; /设元素的类型为char型typedef struct int front;int rear;Datatype DataQueueSize;CirQueue;/以下是主程序,用来验证算法#include #include #include StrctQ.h/ 包含队列结构#include Queue2.h/包含算法头文件/-出错控制程序#include void Error(char * message)fprintf(stderr, Error: %sn,message);exit(1);/-主函数-void main( )int i;CirQueue Q
23、;/ 定义一个循环队列InitQueue( &Q );/初始化队列printf(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:
24、n);for(i=0; irear = Q-rear-next;/头结点成为尾结点Q-rear-next = Q-rear;/形成循环链表int EmptyQueue( LinkQueue *Q)/判队空/当头结点的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;/初始化结点
25、Q-rear-next-next=p; / 将新结点链入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;/摘下结点pfree(p);/释放被删结点return x;3.14解：公式如下： 0EmptyQueu
26、eQueuelen= rear - front rearfront rear+QueueSize-frontrearquelen=QueueSize;void EnQueue( CirQueue *Q, Datatype x)/ 入队if(FullQueue( Q)Error(队已满，无法入队);Q-DataQ-rear=x;Q-rear=(Q-rear+1)%QueueSize;/在循环意义上的加1Q-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;/如果需要验证上面的算法，则需定义好结点类型的队列结构，以相应的变量来表示尾指针和队列长度。自己试试吧。最主要的是能够理解算法的意义和实现。【精品文档】第 9 页