《栈和队列习题集》由会员分享，可在线阅读，更多相关《栈和队列习题集（21页珍藏版）》请在金锄头文库上搜索。
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 种排列中，哪些序列是可以通过相应的入出栈操作得到的。答：(1) 出栈序列为： 1324 (2)不能得到 1423 序列。
2、因为要得到14 的出栈序列，则应做 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,24
3、13,3124,3142,3412,4123,4132,4213,4231,4312 关闭 3.2 链栈中为何不设置头结点? 答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点， 等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。关闭 3.3 循环队列的优点是什么? 如何判别它的空和满? 答：循环队列的优点是：它可以克服顺序队列的“假上溢 “现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的“空“ 或“ 满“ 不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间 ,
4、 每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。 三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。关闭 3.4 设长度为n 的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢 ? 答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。关闭 3.5 指出下述程序段的功能是什么? (1) void Demo1(SeqStack
5、 *S) int i; arr64 ; n=0 ; while ( StackEmpty(S) arrn+=Pop(S); for (i=0, iTop = -1; /其实只是将栈置空 因为要置空的是栈S，如果不用指针来做参数传递，那么函数进行的操作不能对原来的栈产生影响，系统将会在内存中开辟另外的单元来对形参进行函数操作。结果等于什么也没有做。所以想要把函数操作的结果返回给实参的话，就只能用指针来做参数传递了。关闭关闭 3.8 利用栈的基本操作，写一个返回 S中结点个数的算法int StackSize( SeqStack S),并说明 S为何不作为指针参数? 解：算法如下：int Stack
6、Size (SeqStack S) / 计算栈中结点个数int n=0; if(!EmptyStack( n+; return n; 上述算法的目的只要得到S栈的结点个数就可以了。 并不能改变栈的结构。 所以 S不用指针做参数， 以避免对原来的栈中元素进行任何改变。 系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数。关闭3.9 设计算法判断一个算术表达式的圆括号是否正确配对。 ( 提示：对表达式进行扫描，凡遇到(就进栈，遇 )就退掉栈顶的 (，表达式被扫描完毕，栈应为空。解：根据提示，可以设计算法如下：int PairBracket( char *SR) / 检查表达式
7、ST中括号是否配对int i; SeqStack S; /定义一个栈InitStack ( for (i=0; itop0 = -1; S-top1 = StackSize; / 这里的 top2 也指出了向量空间，但由于是作为栈底，因此不会出错 int EmptyStack( DblStack *S, int i ) /判栈空 ( 栈号 i) return (i = 0 int FullStack( DblStack *S) /判栈满 , 满时肯定两头相遇return (S-top0 = S-top1-1); void Push(DblStack *S, int i, DataType x)
8、 /进栈( 栈号 i) if (FullStack( S ) Error(“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- );/返回栈顶元素，指针值减 1 if( i=1
9、) return ( S-Data S-top1+ ); /因为这个栈是以另一端为底的，所以指针值加1。 关闭 3.11 Ackerman 函数定义如下：请写出递归算法。 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时解：算法如下int AKM( int m, int n) if ( m= 0) return n+1; if ( m0 关闭 3.12 用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取队头元素
10、等六个基本操作的算法。解：算法设计如下 : /循环队列的定义#define QueueSize 100 typedef char Datatype ; /设元素的类型为char 型typedef struct int front; int rear; DataType DataQueueSize; CirQueue; (1)置空队void InitQueue ( CirQueue *Q) / 置空队Q-front=Q-rear=0; (2) 判队空int EmptyQueue( CirQueue *Q) /判队空return Q-front=Q-rear; (3) 判队满int FullQue
11、ue( CirQueue *Q) / 判队满 / 如果尾指针加1 后等于头指针，则认为满return (Q-rear+1)%QueueSize= Q-front; (4) 出队DataType DeQueue( CirQueue *Q) /出队DataType temp; if(EmptyQueue(Q) Error(“队已空，无元素可以出队“); temp=Q-DataQ-front ;/保存元素值Q-front= ( Q-front+1 ) %QueueSize;/ 循环意义上的加 1 return temp; /返回元素值 (5) 入队void EnQueue (CirQueue *Q,
12、 DataType x) / 入队if( FullQueue( Q) Error (“队已满，不可以入队“); Q-DataQ-rear=x; Q-rear=(Q-rear+1)%QueueSize; /rear 指向下一个空元素位置 (6) 取队头元素DataType FrontQueue( CirQueue *Q) /取队头元素if (EmptyQueue( Q) Error( “队空，无元素可取“); return Q-DataQ-front; 关闭 3.12 用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取队头元素等六个
13、基本操作的算法。解：算法设计如下 : /循环队列的定义#define QueueSize 100 typedef char Datatype ; /设元素的类型为char 型typedef struct int front; int rear; DataType DataQueueSize; CirQueue; (1)置空队void InitQueue ( CirQueue *Q) / 置空队Q-front=Q-rear=0; (2) 判队空int EmptyQueue( CirQueue *Q) /判队空return Q-front=Q-rear; (3) 判队满int FullQueue(
14、 CirQueue *Q) / 判队满 / 如果尾指针加1 后等于头指针，则认为满return (Q-rear+1)%QueueSize= Q-front; (4) 出队DataType DeQueue( CirQueue *Q) /出队DataType temp; if(EmptyQueue(Q) Error(“队已空，无元素可以出队“); temp=Q-DataQ-front ;/保存元素值Q-front= ( Q-front+1 ) %QueueSize;/ 循环意义上的加 1 return temp; /返回元素值 (5) 入队void EnQueue (CirQueue *Q, Da
15、taType x) / 入队if( FullQueue( Q) Error (“队已满，不可以入队“); Q-DataQ-rear=x; Q-rear=(Q-rear+1)%QueueSize; /rear 指向下一个空元素位置 (6) 取队头元素DataType FrontQueue( CirQueue *Q) /取队头元素if (EmptyQueue( Q) Error( “队空，无元素可取“); return Q-DataQ-front; 关闭 3.14 对于循环向量中的循环队列，写出求队列长度的公式。解：公式如下 ( 设采用第二种方法， front指向真正的队首元素，rear 指向真正队尾后一位置，向量空间大小：QueueSize Queuelen=(QueueSize+rear-front)%QueueSize 关闭 3.15 假设循环队列中只设rear 和quelen 来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。解：根据题意，可定义该循环队列的存储结构：#define QueueSize 100 typedef char Datatype ; /设元素的类型为char 型typedef st
