第三章 栈与队列 习题及答案
第三章栈与队列习题及答案
一、基础知识题
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的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢?
答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。
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 , 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中所有结点均删去的算法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.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时
3.12 用第二种方法，即少用一上元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取队头元素等六个基本操作的算法。
3.13 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空、入队和出队等算法。
3.14 对于循环向量中的循环队列，写出求队列长度的公式。
3.15 假设循环队列中只设rear和quelen 来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。
答案：
3.2 答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。
3.3 答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间。每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。
3.4答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。
3.5 答： (1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。
(2)程序段的功能是利用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;
InitStack( &T);
l=strlen(S); //求向量长度
for ( i=0; i Push( &T, S[i]); while( !EmptyStack( &T)) { // 每弹出一个字符与相应字符比较 t=Pop (&T); if( t!=S[l-i]) { return 0 ;}// 不等则返回0 i--; } return -1 ; // 比较完毕均相等则返回-1 } // 以下程序用于验证上面的算法 //以下是栈定义( 存为stack.h) //出错控制函数 #include #include void Error(char * message) { fprintf(stderr, "Error: %s\n",message); exit(1); } // 定义栈类型 #define StackSize 100 typedef char Datatype; typedef struct{ Datatype data[StackSize]; 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 x) { //进栈 if(FullStack(S)) Error("Stack overflow"); S->data[++S->Top]=x; } Datatype Pop(SeqStack *S) { // 出栈(退栈) if (EmptyStack( S) ) Error( "Stack underflow"); return S->data[S->Top--]; } //取栈顶元素(略) //----------------------------------------------- //以下是主程序 #include #include #include "stack.h> #include "ishuiwen.h" void main( ) { char Str[100]=""; printf("输入一个字符串:\n"); scanf("%s",Str); if( IsHuiwen(Str)) printf(" \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(&S)) { Pop(&S); n++; } return n; } 类似于上面的原因，我们要计算栈中元素个数就要弹出元素才能"数"得出来，那如果用指针做参数的话，就会把原来的栈中元素"弹"光，要恢复还得用别的办法给它装回去，而不用指针做参数，则可以避免对原来的栈中元素进行任何操作，系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数就可以了。 3.9 解：根据提示，可以设计算法如下： #include #include "stack.h" int PairBracket( char *S) { //检查表达式中括号是否配对 int i; SeqStack T; //定义一个栈 InitStack (&T); for (i=0; i { if ( S[i]=='(' ) Push(&T, S[i]); //遇'('时进栈 if ( S[i]==')' ) Pop(&T); //遇')'时出栈 } return !EmptyStack(&T); // 由栈空否返回正确配对与否 } 3.10 解：双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。双向栈的算法设计如下： //双向栈的栈结构类型与以前定义略有不同 #define StackSize 100 // 假定分配了100个元素的向量空间 #define char Datatype typedef struct{ Datatype Data[StackSize] int top0; //需设两个指针 int top1; }DblStack void InitStack( DblStack *S ) { //初始化双向栈 S->top0 = -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 )) 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 ) return ( S->Data[ S->top1++] ); //因为这个栈是以另一端为底的，所以指针值加1。 } //其余算法略,以上算法没有上机调试过，请学友自行验证一下。主要是我们理解了算法也就可以了。 3.11 解：算法如下 int AKM( int m, int n) { if ( m== 0) return n+1; if ( m<>0 && n==0 ) return AKM( m-1, 1); if ( m<>0 && n<>0 ) 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后等于头指针，则认为满 return (Q->rear+1)%QueueSize== Q->front; } Datatype DeQueue( CirQueue *Q) { //出队 if(EmptyQueue(Q)) Error("队已空，无元素可以出队"); Datatype temp; temp=Q->Data[Q->front] ;//保存元素值 Q->front= ( Q->front+1 ) %QueueSize;//循环意义上的加1 return temp; //返回元素值 } void EnQueue (CirQueue *Q, Datatype x) { // 入队 if( FullQueue( Q)) Error ("队已满，不可以入队"); Q->Data[Q->rear]=x; Q->rear=(Q->rear+1)%QueueSize; //rear 指向下一个空元素位置} Datatype FrontQueue( CirQueue *Q) { //取队头元素 if (EmptyQueue( Q)) Error( "队空，无元素可取"); return Q->Data[Q->front]; } //为了验证上述算法是否正确，晓津设计了以下程序 //循环队列的定义存入StructQ.h文件中 #define QueueSize 10 //为便与验证，这里假设为10个元素的空间typedef char Datatype ; //设元素的类型为char型 typedef struct { int front; int rear; Datatype Data[QueueSize]; }CirQueue; //以下是主程序,用来验证算法 #include #include #include "StrctQ.h" // 包含队列结构 #include "Queue2.h"//包含算法头文件 //------------------出错控制程序 #include void Error(char * message) { fprintf(stderr, "Error: %s\n",message); exit(1); } //------------------------主函数----- void main( ) { int i; CirQueue Q;// 定义一个循环队列 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:\n"); for(i=0; i EnQueue(&Q, getchar()); } //上机时可以输入字符，也可以直接输入回车的次数来验证，注意：一个回车也是一个字符。 3.13 解：算法如下： //先定义链队结构: typedef struct queuenode{ Datatype data; struct queuenode *next; }QueueNode; //以上是结点类型的定义 typedef struct{ queuenode *rear; }LinkQueue; //只设一个指向队尾元素的指针 //linkQ.h 相应算法 void InitQueue( LinkQueue *Q) { //置空队：就是使头结点成为队尾元素 Q->rear = 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;//初始化结点 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;//摘下结点p free(p);//释放被删结点 return x; } 3.14解：公式如下： { 0 EmptyQueue Queuelen={ rear - front rear>front { rear+QueueSize-front rear { QueueSize FullQueue 3.15 解：知道了尾指针和元素个数，当然就能知道队头元素了。算法如下： int FullQueue( CirQueue *Q) { //判队满,队中元素个数等于空间大小 return Q->quelen==QueueSize; } void EnQueue( CirQueue *Q, Datatype x) { // 入队 if(FullQueue( Q)) Error("队已满，无法入队"); Q->Data[Q->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->Data[tmpfront]; } //如果需要验证上面的算法，则需定义好结点类型的队列结构，以相应的变量来表示尾指针和队列长度。自己试试吧。最主要的是能够理解算法的意义和实现。 第三章栈、队列和数组 一、名词解释： 1.栈、栈顶、栈底、栈顶元素、空栈 2.顺序栈 3.链栈 4.递归 5.队列、队尾、队头 6.顺序队 7.循环队 8.队满 9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵 二、填空题： 1.栈修改的原则是_________或称________，因此，栈又称为________线性表。在栈顶 进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________ 或________。 2.栈的基本运算至少应包括________、________、________、________、________五 种。 3.对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。 4.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。 5.一般地，栈和线性表类似有两种实现方法，即________实现和________实现。 6.top=0表示________，此时作退栈运算，则产生“________”； top=sqstack_maxsize-1表示________，此时作进栈运算，则产生“________”。 7.以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。 int InitStack(SqStackTp *sq) { ________; return(1);} 8.以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。 Int Push(SqStackTp *sq,DataType x) { if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);} else{________________: ________________=x; return(1);} } 9.以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。 Int Pop(SqStackTp *sq,DataType *x) {if(sp->top==0){error(“下溢”);return(0);} else{*x=________________; ________________; return(1);} } 10. 以下运算实现在顺序栈上判栈空，请在________________处用适当句子予以填充。 Int EmptyStack(SqStackTp *sq) {if(________________) return(1); else return(0); } 11.以下运算实现在顺序栈上取栈顶元素，请在________________处用适当句子予以填充。 Int GetTop(SqStackTp *sq,DataType *x) 第3章栈和队列练习题答案 一、填空题 1. 线性表、栈和队列都是线性结构，可以在线性表的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。 3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 二、判断正误 （√）1. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（√）2. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （×）3. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （√）4. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （√）5. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （×）6. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （×）7. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题 （B）1.栈中元素的进出原则是 Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出 （C）2.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为 Ａ．i Ｂ．n-i Ｃ．n-i+1 Ｄ．不确定 解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，…，n，则出栈的序列是n，…，3，2，1。 （若不要求顺序出栈，则输出序列不确定） （D）3．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为 （Ａ）r－f; （Ｂ）（n＋f－r）% n; （Ｃ）n＋r－f; （Ｄ）（n＋r－f）% n E：①1 ②2 ③3 ④0 四、阅读理解 1.【严题集②】写出下列程序段的输出结果（栈的元素类型SElem Type为char）。 void main( ){ Stack S; Char x,y; InitStack(S); x=’c’;y=’k’; 第三章栈和队列 一、判断题 1、链栈的初始化是指开辟足够多的结点，然后置栈顶指针为 NULL。（×） 2、递归定义的数据结构通常不需要用递归的算法来实现对它的操作。（×） 二、填空题 1、向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给___栈顶指针_____。 2、迷宫问题是一个回溯控制的问题，最好使用____栈______的方法来解决。 3、有如下递归过程： Void Print(int w) { int i; if (w!=0) { Print(w?1); for (i=1;i<=w;i++) printf(“%3d”,w); printf(“\n”); } } 调用语句print(4)的结果是__________。 1 2 2 3 3 3 4 4 4 4 4、假设用循环单链表实现队列，若队列非空，且队尾指针为R, 则将新结点S加入队列时，需执行下面语句：_ S->next=R->next _________；___ R->next=S _______；R=S； 三、选择题 1、设有4个数据元素a1、a 2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a 3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。 现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A 2，第二次出栈得到的元素是 B 4；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C 1，第二次出队得到的元素是 D 2。经操作后，最后在栈中或队中的元素还有 E 2个。 供选择的答案： A～D：①a1 ②a2 ③ a3 ④a4 E：①1 ②2 ③ 3 ④ 0 2、栈是一种线性表，它的特点是 A 2。设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值 B 2；从栈中弹出（POP）一个元素时，变量T的值 C 1。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D 6，变量T的值是 E 4。 供选择的答案： A：①先进先出②后进先出③进优于出④出优于进⑤随机进出 B，C：①加1 ②减1 ③不变④清⑤加2 ⑥减2 D：① a,b ②b,c ③c,a ④b,a ⑤ c,b ⑥a,c E：① n+1 ②n+2 ③ n ④ n-1 ⑤ n-2 3、在做进栈运算时，应先判别栈是否 A 2；在做退栈运算时，应先判别栈是否 B 1。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 2。 第三章栈和队列 一、单项选择题 参考答案： 1. A 2. B 3. C 4. A 5. B 6. B 7. D 8. D 9. C 10. A 11. D 12. A 13. A 14. D 15. C 二、填空题 参考答案： 1. 先进后出 2. 先进先出 3. 队尾，队头 4. 栈顶指针 5. 栈顶指针 6. MaxSize-1 7. top==0 8. 空栈 9. 栈顶指针10. p->link=top，top=p 11. top=top->link 12. Q.front==Q.rear 13. (Q.rear+1)%MaxSize==Q.front 14. 队尾指针15. 空，只含有一个结点 16. front == rear && front != NULL或者front == rear && rear != NULL 17. 两端18. 3x2+*5- 19. 15 20. 3 三、判断题 参考答案： 1. 是 2. 是 3. 否 4. 是 5. 是 6. 否 7. 否 8. 是 9. 否10. 否 11. 否12. 是13. 否14. 是15. 否 16. 否 四、运算题 参考答案： 1.根据以上规则，给出计算中缀表达式a + b * c – d / e时两个栈的变化。 步扫描项项类型动作OPND栈OPTR栈 0 OPTR栈与OPND栈初始化, ‘#’ 进OPTR栈, # 取第一个符号 1 a 操作数a进OPND栈, 取下一符号 a # 2 + 操作符icp (‘+’ ) > isp (‘#’ ), 进OPTR栈, 取 a # + 下一符号 3 b 操作数b进OPND栈, 取下一符号 a b # + a b # + * 4 * 操作符icp (‘*’ ) > isp (‘+’ ), 进OPTR栈, 取 下一符号 5 c 操作数c进OPND栈, 取下一符号 a b c # + * a s1# + 6 - 操作符icp (‘-’ ) < isp (‘*’ ), 退OPND栈‘c’, 退OPND 栈‘b’, 退OPTR栈‘*’, 计算 b * c→ s1, 结果 进OPND栈 s2# 7 同上同上ic p (‘-’ ) < isp (‘+’ ), 退OPND栈‘s ’, 1 退OPND 栈‘a’, 退OPTR栈‘+’, 计算 a * s1→ s2, 结果 进OPND栈 第4章栈和队列 一、填空题 1.向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。 3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 4. 在一个循环队列中，队首指针指向队首元素的前一个位置。 5. 在具有n个单元的循环队列中，队满时共有n-1个元素。 6. 向栈中压入元素的操作是先移动栈顶指针，后存入元素。 7. 从循环队列中删除一个元素时，其操作是先移动队首指针，后取出元素。 二、判断正误（判断下列概念的正确性，并作出简要的说明。） （×）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。（×）2. 在表结构中最常用的是线性表，栈和队列不太常用。 错，不一定吧？调用子程序或函数常用，CPU中也用队列。 （√）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （×）5. 栈和链表是两种不同的数据结构。 错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。 （×）6. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （√）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （√）8*. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （×）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （×）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题 （B）1.栈中元素的进出原则是 Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出 （B）2. 判定一个栈ST（最多元素为m0）为空的条件是 Ａ．ST→top<>0 Ｂ．ST→top=-1 Ｃ．ST→top<>m0 Ｄ．ST→top=m0 四、简答题 1. 说明线性表、栈与队的异同点。 答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。 不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。 ②用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。 2*.设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。 第三章栈和队列习题答案 一、基础知识题 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 的出栈序列，则应做 Push(1),Pop(),Push(2),Push (3),Push(4),Pop()o这样，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,4123,4132,4213,4231,4312 3.2 链栈中为何不设置头结点? 答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。 3.3 循环队列的优点是什么? 如何判别它的空和满? 答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分 的利用。判别循环队列的”空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间，每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或 满，还可以得到队列中元素的个数。 3.4 设长度为n 的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢? 答：当只设头指针时，出队的时间为1,而入队的时间需要n,因为每次入队均需从头指针开始查找， 找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾 指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。 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) ) 习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（） A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后，i值为：（） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1)); A．2 B. 4 C. 8 D. 无限递归 7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 8. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front 第三章栈和队列练习题答案 一、名词说明： 1.栈、栈顶、栈底、栈顶元素、空栈 2.顺序栈 3.链栈 4.递归 5.队列、队尾、队头 6.顺序队 7.循环队 8.队满 9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵 二、填空题： 1.栈修改的原那么是_先进后出________或称后进先出________，因此，栈又称为__后进先出______线性表。在栈顶进行插入运算，被称为_进栈_______或__入栈______，在栈顶进行删除运算，被称为___退栈_____或__出栈______。 2.栈的大体运算至少应包括_初始化InitStack(S)_______、_进栈Push(S,X)_______、_退栈Pop(S)_______、读栈顶Top(S)________、_判栈空Empty(S)_______五种。 3.关于顺序栈，假设栈顶下标值top=0,现在，若是作退栈运算，那么产生“__下溢______”。 4.关于顺序栈而言，在栈满状态下，若是现在在作进栈运算，那么会发生“_上溢_______”。 5.一样地，栈和线性表类似有两种实现方式，即__顺序______实现和__链接实现。 6. top=0表示栈空，现在作退栈运算，那么产生“下溢”；top=sqstack_maxsize-1表示栈满，现在作进栈运算，那么产生“上溢”。 7.以下运算实此刻顺序栈上的初始化，请在________处用适当的句子予以填充。 int InitStack(SqStackTp *sq) { sq->top=0; return(1);} 8.以下运算实此刻顺序栈上的进栈，请在________处用适当的语句予以填充。 Int Push(SqStackTp *sq,DataType x) { if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);} else{_ sq->top++, sq->data[sq->top] =x; return(1);} } 9.以下运算实此刻顺序栈上的退栈，请在________________用适当句子予以填充。 Int Pop(SqStackTp *sq,DataType *x) {if(sp->top==0){error(“下溢”);return(0);} 第三章栈和队列 一、选择题 二、判断题 部份答案解释如下。 1、尾递归的消除就不需用栈 2、这个数是前序序列为1,2,3,…,n，所能取得的不相似的二叉树的数量。 三、填空题 1、操作受限（或限定仅在表尾进行插入和删除操作）后进先出 2、栈 3、3 1 2 4、23 100CH 5、0 n+1 top[1]+1=top[2] 六、两栈顶指针值相减的绝对值为1（或两栈顶指针相邻）。 7、(1)满(2)空(3)n (4)栈底(5)两栈顶指针相邻（即值之差的绝对值为1） 八、链式存储结构九、S×SS×S××10、data[++top]=x； 1一、（注：表达式中的点(.)表示将数隔开，如是三个数） 1二、假溢出时大量移动数据元素。 13、(M+1) MOD N (M+1)% N；14、队列1五、先进先出1 六、先进先出 17、s=(LinkedList)malloc(sizeof(LNode))；s->data=x;s->next=r->next； r->next=s；r=s； 1八、捐躯一个存储单元设标记 1九、（TAIL+1）MOD M=FRONT (数组下标0到M-1，若必然利用1到M，则取模为0者，值改取M 20、=+1)%(M+1)；return)；+1)%(M+1)==； 2一、栈2二、（rear-front+m）% m；23、（R-P+N）% N； 24、（1）a[i]或a[1] （2）a[i] （3）pop（s）或s[1]； 2五、（1）PUSH（OPTR，w）（2）POP（OPTR）（3）PUSH（OPND，operate （a，theta，b）） 26、（1）T>0（2）i 第3章栈和队列习题参考答案 第3章栈和队列 一、基础知识题 3.1有五个数依次进栈：1，2，3，4，5。在各种出栈的序列中，以3，4先出的 序列有哪几个。（３在４之前出栈）。 【解答】34215 ，34251，34521 3.2铁路进行列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序为： 1，2，3，4，5，6，那么是否能够得到435612，325641，154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到(即写出"进栈"或"出栈"的序列)。 【解答】输入序列为123456，不能得出435612和154623。不能得到435612的理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能让栈底元素1在栈顶元素2之前出栈。不能得到154623的理由类似，当栈中元素只剩23，且3在栈顶，2不可能先于3出栈。 得到325641的过程如下：1 2 3顺序入栈，32出栈，得到部分输出序列32；然后45入栈，5出栈，部分输出序列变为325；接着6入栈并退栈，部分输出序列变为3256；最后41退栈，得最终结果325641。 得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。 3.3若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别 为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？ 栈和队列习题及答案 【篇一：栈和队列练习题答案】 xt>一、填空题 1. 线性表、栈和队列都是结构，可以在线性表的在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为栈底。 3. 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 二、判断正误 （√）1. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（√）2. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （√）4. 栈和队列的存储方式既可是顺序方式，也可是链接方式。（√）5. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底 分别设在这片内存空间的两端。 错，有可能。 三、单项选择题 （b）1.栈中元素的进出原则是 Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出 （c）2.若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若p1=n，则pi为 Ａ．i Ｂ．n-iＣ．n-i+1 Ｄ．不确定 解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，?，n，则出栈的序列是n，?，3，2，1。 （若不要求顺序出栈，则输出序列不确定） （d）3．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的 习题三参考答案 备注: 红色字体标明的是与书本内容有改动的内容。 一、选择题 1.在栈中存取数据的原则是（ B ）。 A．先进先出 B. 先进后出 C. 后进后出 D. 没有限制 2．若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（ D ）。 A．1234 B. 1324 C. 4321 D. 1423 3．在链栈中，进行出栈操作时（B ）。 A．需要判断栈是否满 B. 需要判断栈是否为空 C. 需要判断栈元素的类型 D. 无需对栈作任何差别 4．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize，则顺序栈的判空条件是（ A ）。 A．top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 5．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（ C ）。 A．top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 6．在队列中存取数据元素的原则是（ A ）。 A．先进先出 B. 先进后出 C. 后进后出 D. 没有限制 7．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front 和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判空条件是（A ）。 A．front==rear B. front!=rear C. front==rear+1 D. front==(rear+1)% maxSize 8．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front 和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满条件是（D ）。 A．front==rear B. front!=rear C. front==rear+1 D. front==(rear+1)% maxSize 9.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front 和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（C ）。 A．rear-front B. rear-front+1 C. (rear-front+maxSize)%maxSize D. (rear-front+1)%maxSize 10.设长度为n的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入 队操作的时间复杂度为（ B ）。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 二、填空题 1.栈是一种操作受限的特殊线性表，其特殊性体现在其插入和删除操作都限制在表尾进 堆栈和队列测试题 一、选择题 1. 对于栈操作数据的原则是（B）。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在做进栈运算时,应先判别栈是否( B),在做退栈运算时应先判别栈是否( A)。当栈中元素为n个,做进栈运算时发生上溢,则说明该栈的最大容量为( B )。为 了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空 间时,应将两栈的( D )分别设在这片内存空间的两端。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D.n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 3. 一个栈的输入序列依次为1，2，3，…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（B）。 A. 不确定 B. n-i+1 C. i D. n-i 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出 元素是（ D ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则pi是( D )。 A. i B. n-i C. n-i+1 D. 不确定 6.有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ C ） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 7. 设栈的输入序列是1，2，3，4,则（ D ）不可能是其出栈序列。 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4， 8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是 （ B ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 9. 设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（D）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 一、单选题 1、元素A、B、C、D依次进栈后，栈顶元素是 _______。 A.B B.D C.C D.A 正确答案：B 2、经过以下运算后， x的值是 _______。 InitStack (s); Push(s, a); Push(s, b); Pop(s, x); GetTop(s,x) A.0 B.b C.a D.1 正确答案：C 3、经过以下栈运算后，StackEmpty(s)的值是 _______。 InitStack (s); Push(s, a); Push(s, b); Pop(s, x); Pop(s,y) A.0 B.b C.a D.1 正确答案：D 4、已知一个栈的进栈序列是ABC，出栈序列为CBA，经过栈的操作是 _______。 A.push, push, push, pop, pop, pop B.push,pop,push, push,pop, pop C.push, push,pop, pop,push,pop D.push,pop,push,pop,push,pop 正确答案：A 5、若元素a、b、c、d、e、f依次进栈，允许进栈、退栈的操作交替进行，但不允许 连续3次退栈工作，则不可能得到的出栈序列是 _______。 A. bcaefd B.afedcb C.cbdaef D.dcebfa 正确答案：B 6、设一个栈的输入序列为A、B、C、D，则借助一个栈所得的输出序列不可能是 _______。 A.DCBA B.DABC C.ACDB D.ABCD 正确答案：B 7、一个栈的进栈序列是abcde，则栈的不可能的输出序列是 _______。 A.decba B.abcde C.dceab D.edcba 正确答案：C 8、已知一个栈的进栈序列是1，2，3，…n，其输出序列的第一个元素是i（1≤i≤n），则第j（1≤j≤n）个出栈元素是_______。 A.n-i B.j-i+1 C.i D.不确定 正确答案：D 第3章栈和队列 3.1栈 一、填空题 1. 线性表、栈和队列都是________ 结构，可以在线性表的__________ 位置插入和删除元素；对于栈只能 ___________插入和删除元素；对于队列只在 ____________ 插入元素，并且只在____________ 删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为____________ 。不允许插入和删除运算的一端称 为_________ 。 3. 向栈中压入元素的操作是先____________ ，后 _______ 。 4. 从栈中弹出元素的操作是先____________ ，后 ________ 。 二、选择题： 1. （）栈中元素的进出原则是（）。 A.先进先出 B .后进先出C .栈空则进D .栈满则出 2. （）若已知一个栈的入栈序列是1 , 2, 3,…，n,其输出序列为pl, p2, p3,…， pn,若p仁n,贝U pi为（）。 A. i B . n=i C . n-i+1 D .不确定 3. （）判定一个栈ST （最多元素个数为m0）为空的条件是（）。 A. ST->top<>0 B . ST->top=0 C . ST->top<>mO D . ST->top=mO 4. （）有六个元素1,2,3,4,5,6 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 1,2,3,4,5,6 B. 5,4,3,2,1,6 C. 4,3,2,1,5,6 D. 6,5,4,3,1,2 5. （）将递归算法转换成非递归算法时，通常要借助的数据结构是（）。 A.线性表 B. 栈 C. 队列 D. 树 6. （）若栈采用顺序存储方式存储，现两栈共享空间V[1..m] , top[i]代表第i个栈（i =1,2）栈顶, 栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 7. （）一个递归算法必须包括（）。 A.递归部分 B. 终止条件和递归部分 C. 迭代部分 D. 终止条件和迭代部分 8. （）从供选择的答案中，选出应填入下面叙述? 内的最确切的解答，把相应编号写在答卷 对应栏内。 设有4个数据元素a1、a2、a3和a4,对他们分别进行栈操作。在进栈操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈初始状态都是空。现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是A，第二次出栈得到的元素是B 经操作后，最后在栈中的元素还有_C ___ 个。 供选择的答案： A 〜B：①a1 ②a2 ③a3 ④a4 C :①1 ②2 ③3 ④0 9. （）从供选择的答案中，选出应填入下面叙述? 内的最确切的解答，把相应编号写在答卷 的对应栏内。 在做进栈运算时，应先判别栈是否_A_ ;在做退栈运算时，应先判别栈是否_B—。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为_C_。 为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 D 分别设在这片内存空间的两端,这样，只有当 E 时，才产生上溢。 供选择的答案： A , B:①空②满③ 上溢④下溢 栈和队列习题及答案 栈和队列习题及答案 【篇一：栈和队列练习题答案】 xt>一、填空题 1. 线性表、栈和队列都是结构，可以在线性表的在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为栈底。 3. 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 二、判断正误 （√）1. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（√）2. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （√）4. 栈和队列的存储方式既可是顺序方式，也可是链接方式。（√）5. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底 分别设在这片内存空间的两端。 错，有可能。 三、单项选择题 （b）1.栈中元素的进出原则是 Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出 （c）2.若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若p1=n，则pi为 Ａ．i Ｂ．n-iＣ．n-i+1 Ｄ．不确定 解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，?，n，则出栈的序列是n，?，3，2，1。 （若不要求顺序出栈，则输出序列不确定） （d）3．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的 位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（Ａ）r－f; （Ｂ）（n＋f－r）% n; （Ｃ）n＋r－f;（Ｄ）（n＋r －f）% n e：①1 ②2 ③ 3 ④ 0 四、阅读理解 1. 【严题集3.3②】写出下列程序段的输出结果（栈的元素类型selem type为char）。 void main( ){ stack s; char x,y; initstack(s); x=’c’;y=’k’; push(s,x); push(s,’a’); push(s,y); pop(s,x); push(s,’t’); push(s,x); pop(s,x); push(s,’s’); while(!stackempty(s)){ pop(s,y);printf(y); }; printf(x); } 答：输出为“stack”。 2. 【严题集 3.12②】写出下列程序段的输出结果（队列中的元素类型qelem type为char）。 void main( ){ queue q; init queue (q); char x=’e’; y=’c’; enqueue (q,’h’); enqueue (q,’r’); enqueue (q, y); dequeue (q,x); enqueue (q,x);数据结构练习题第三章栈、队列和数组习题与答案
栈和队列练习题答案
第三章+栈和队列(参考答案)
《数据结构》习题汇编03 第三章 栈和队列 试题(答案)
数据结构(Java)复习题及答案 3栈和队列
第三章栈和队列习题答案
数据结构栈和队列习题及答案
第三章栈和队列练习题答案
数据结构习题第三章栈和队列答案
第3章栈和队列习题参考答案
栈和队列习题及答案
最新第3章 栈与队列习题参考答案02464
数据结构第三章堆栈和队列测试题及答案
数据结构(栈和队列)习题与答案
数据库系统l试题库及答案第3章栈与队列
栈和队列习题及答案