一、基础知识题

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 链栈中为何不设置头结点?

3.3 循环队列的优点是什么? 如何判别它的空和满? 

3.4 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢? 

3.5 指出下述程序段的功能是什么? 
(1) void Demo1(SeqStack *S){
　　　　 int i; arr[64] ; n=0 ;
　　　　 while ( StackEmpty(S)) arr[n++]=Pop(S);
　　　　 for (i=0, i< n; i++) Push(S, arr[i]);
　　　 } //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 (! 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) 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);} 

二、算法设计题 

3.6 回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) 

3.7 利用栈的基本操作，写一个将栈S中所有结点均删去的算法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( S , i )等算法， 其中i为0 或1， 用以表示栈号。 

3.11Ackerman 函数定义如下：请写出递归算法。
　　　　　　　　┌ n+1　　　 当m=0时 
AKM ( m , n ) = │ AKM( m-1 ,1) 当m≠0 ，n=0时 
　　　　　　　　└ AKM( m-1, AKM( m,n-1)) 当m≠0, n ≠ 0时  

3.12用第二种方法 ，即少用一个元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取队头元素等六个基本操作的算法。 

3.13 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。 

3.14 对于循环向量中的循环队列，写出求队列长度的公式。 

3.15 假设循环队列中只设rear和quelen 来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。