《中南大学数据结构与算法第3章栈和队列课后作业答案汇总》由会员分享，可在线阅读，更多相关《中南大学数据结构与算法第3章栈和队列课后作业答案汇总（14页珍藏版）》请在金锄头文库上搜索。
1、第3章栈和队列习题练习答案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种排列中，哪些序列是可以通过相应的入出栈操作得到的。答：(1)出栈序列为：1324 (2)不能得到1423序列。因为要得到14
2、的出栈序列，则应做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。(3)在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是： 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是：1423,2413,3124,3142,3412
3、,4123,4132,4213,4231,43123.2 链栈中为何不设置头结点?答： 链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。3.3 循环队列的优点是什么? 如何判别它的空和满?答：循环队列的优点是：它可以克服顺序队列的假上溢现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的空或满不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置
4、一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。3.4 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢?答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。3.5 指出下述程序段的功能是什么?(1) void Demo1(SeqStack *S)int i; arr64 ; n=0 ;while ( StackEmpty(S) arr
5、n+=Pop(S);for (i=0, i n; 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;InitS
6、tack (&T);while (! StackEmpty( 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)
7、CirQueue Q1, Q2; / 设DataType 为int 型int x, i , n= 0;. / 设Q1已有内容， Q2已初始化过while ( ! QueueEmpty( &Q1) ) x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n+;for (i=0; i n; i+) x=DeQueue(&Q2) ;EnQueue( &Q1, x) ; EnQueue( &Q2, x);答：(1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。(2)程序段的功能是利用tmp栈将一个非空
8、栈s1的所有元素按原样复制到一个栈s2当中去。(3)程序段的功能是利用栈T，将一个非空栈S中值等于m的元素全部删去。(4)程序段的功能是将一个循环队列Q经过S栈的处理，反向排列，原来的队头变成队尾，原来的队尾变成队头。(5)这段程序的功能是将队列1的所有元素复制到队列2中去，但其执行过程是先把队列1的元素全部出队，进入队列2，然后再把队列2的元素复制到队列1中。3.6 回文是指正读反读均相同的字符序列，如abba和abdba均是回文，但good不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)解：根据提示，算法可设计为：/以下为顺序栈的存储结构定义#define St
9、ackSize 100 /假定预分配的栈空间最多为100个元素typedef char DataType;/假定栈元素的数据类型为字符typedef structDataType dataStackSize;int top;SeqStack;int IsHuiwen( char *t)/判断t字符向量是否为回文，若是，返回1，否则返回0SeqStack s;int i , len;char temp;InitStack( &s);len=strlen(t); /求向量长度for ( i=0; iTop = -1; /其实只是将栈置空因为要置空的是栈S，如果不用指针来做参数传递，那么函数进行的操
10、作不能对原来的栈产生影响，系统将会在内存中开辟另外的单元来对形参进行函数操作。结果等于什么也没有做。所以想要把函数操作的结果返回给实参的话，就只能用指针来做参数传递了。3.8 利用栈的基本操作， 写一个返回S中结点个数的算法 int StackSize( SeqStack S),并说明S为何不作为指针参数?解：算法如下：int StackSize (SeqStack S)/计算栈中结点个数int n=0;if(!EmptyStack(&S)Pop(&S);n+;return n;上述算法的目的只要得到S栈的结点个数就可以了。并不能改变栈的结构。所以S不用指针做参数，以避免对原来的栈中元素进行任何改变。系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数。3.9 设计算法判断一个算术表达式的圆括号是否正确配对。 (提示： 对表达式进行扫描，凡遇到(就进栈，遇)就退掉栈顶的(，表达式被扫描完毕，栈应为空。解：根据提示，可以设计算法如下：int PairBracket( char *SR)/检查表达式ST中括号是否配对int i;SeqStack S; /定义一个栈InitStack (&s);for (i=0; itop0 = -1;S-top1 = StackS
