第三章栈和队列：习题
习 题
一、选择题
1．栈和队列都是( )。
A.顺序存储的线性结构 B.限制存取点的线性结构
C．链接存储的线性结构 D.限制存取点的非线性结构
2．一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是( )。
A. edcba B. decba C. dceab D. abcde
3．若已知一个栈的入栈序列是l，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则Pi为 ( )。
A.i B. n-i C. n-i+l D.不确定
4．循环队列SQ采用数组空间SQ.data[0，n-l]存放其元素值，已知其头尾指标分别是front和rear，则当前队列中的元素个数是( )。
A. (rear-front+n)%n B. rear-front+l
C. rear-front-l D. rear-front
5．中缀表达式A-(B+C/D)*E的后缀形式是( )。
A. AB-C+D／E* B. ABC+D／E*
C. ABCD／E*+- D. ABCD／+E*-
6．一个队列的入列序列是1，2，3，4，则队列的输出序列是( )。
A.4，3，2，1 B．1，2，3，4
C．1，4，3，2 D．3，2，4，1
7．若在一个大小为6的数组上实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( )。
A.1和5 B.2和4 C.4和2 D.5和l
8．用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指标指向队尾结点，则在进行出队运算时( )。
A.仅修改队头指针 B.仅修改队尾指针
C.对头、队尾指针都要修改 D.对头、对尾指针都可能要修改
9．若进栈序列为a，b，c，则通过入出栈运算可能得到的a，b，c的不同排列个数为( )。
A.4 B.5 C.6 D.7
10.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，
则执行出队运算后其头指针front值为( )。
A. front=front+l B. front=(front+l) %(m-l)
C.front=(front-1)%m D. front=(front+l)%m
11.在一个链队中，假定front和rear分别为队首指标和队尾指标，则删除一个结点的运
算应执行( )。
A. front front->next； B.rear=rear->next;
C.rear=front->next; D. front=rear->next;
12.向一个栈顶指标为hs的链栈中插入结点*s时，应执行( )。
A.hs->next=s； B. s->next=hs; hs=s;
C.s->next=hs->next; hs->next=s; D. s->next=hs; hs=hs->next:
13.在具有n个单元的顺序循环队列中，假定front和rear分别为队首指针和队尾指针，
顺序表的下标下界从0开始，则判断队满的条件是( )。
A.(l+rear)% n=front B.(l+rear)% (n-l)=front
C.l+rear%n=front D.(l+front)%n=rear
14.若已知一个栈的入栈序列是l，2，3，…，30，其输出序列是pl,p2，p3，…，pn，若p1=30，则pl0为( )。
A. 11 B. 20 C. 30 D. 21
二、填空题
1．设长度为n的链队列用单循环链表表示，若只设头指针，则入队和出队运算的时间复杂度分别为____和____；若只设尾指针，则入队和出队运算的时间复杂度分别为和 一。
2．基本线性表，栈和队列都是____ 结构。可以在基本线性表的____插入和删除元素；对于栈只能在____ 插入和删除元素；对于队列只能在____插入元素和删除元素。
3．一个栈的输入序列是235614，则栈的输出序列54321是____。（可能或不可能）
4．对于顺序循环队列Q[M]，下标从0到M-1，头尾指针分别为F和R表示，出队时，队首指针循环加l可表示F=____。
5．因为顺序栈的空间是有限的。因此，在进行插入运算时，可能会发生____。
6．假设以s和x分别表示进栈和退栈运算，则对输入序列a，b，c，d，e进行一系列栈运算ssxsxssxxx之后，得到的输出序列为____。
7．栈顶的位置是随着____ 运算而变化的。
8．有如下递归函数：
int dunno (int m)
{ int value；
if(m==0) value=3;
else value=dunno (m-l) +5;
return (value)；
}
执行语句printf(”%d\\n'’，dunno(3))；的结果是_________。
9．设a是含有N个分量的整数数组，写出求n个整数之和的递归定义________，写出求n个整数之积的递归定义____。
10.设栈S和队列Q的初始状态为空，元素a，b，c，d，e，f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b，d，c，f, e，a，则栈S的容量至少应该是________。
三、简答题
1．什么是队列的“假溢出”现象？一般有哪几种处理方法？
2．试证明：若借助栈由输入序列1，2，3，…，n，得到输出序列P1，P2，P3，…，Pn（它是输入序列 的一个排列），则输出序列中不可能出现这样的情况：若i 4．试推导求解n阶Hanoi塔问题至少需执行的move运算的次数。 四、算法设计题 1．利用两个栈S1和S2模拟一个队列时，要求实现该队列的进队、出队、判队空3种运算。 2．假设如题图3-1所示，火车调度站的入口处有n节硬席或软席车厢（分别以H和S表示）等待调度。试编写算法，输出对这n节车厢进行调度的运算（入栈或出栈运算）序列，以使所有的软席车厢都被调整到硬席车厢之前。 3．求两个正整数m和n的最大公约数可以用如下gcd (m，n)公式表示： (1)编写一个计算gcd(m，n)的递归过程。 (2)将上述过程转化成非递归过程。 (3)画出计算gcd (20，6)的过程及栈的状态变化，给出计算结果。 4．如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0或l来区分尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好）。 5．用单链表实现队列，如题图3-2所示，并令front reaFNULL表示队列为空，编写实现队列的如下5种运算的函数： SetNull:将队列置成空队列。 GetFirst:返回队列的第一个元素。 EnQueue：把元素插入队列的后端。 DeQueue：删除队列的第一个元素。 Empty：判定队列是否为空。 6．若使用循环链表来表示队列，p是链表中的一个指针。试基于此结构给出队列的插入( EnQueue)和删除(DeQueue)算法，并给出p为何值时队列空。 7．编写程序将一个循环队列的内容倒置，该循环队列存储在一个数组A[1...N-1]中，例如，题图3-3 (a)中为倒置前的队列，题图3-3 (b)中为倒置后的队列。 8．已知Ackermann函数的定义如下： 写出计算Ack(m，n)的非递归算法 第三章 栈和队列 第3章栈和队列 一、选择题 1.B 2.C 3.C 4.A 5.D 6.B 7.A 8.D 9.B 10.B 11.A 12.B 13.A 14.D 二、填空题 1．O(n)，O(1)，O(1)，O(n)。 2．线性任何栈顶队尾队首。 3．不可能。 4．F=(1+F)%M。 5．上溢。 6．Bceda。 7．进栈或出栈。 8. 18。 9． 10.3 三、简答题 1．假设顺序队列的头指针为front，尾指针为rear，队列的容量为MaxSize，下标下 界为0，则最后一个单元的下标为MaxSize-1。 (1)“假溢出”是指rear=MaxSize-l，而front≠0的现象。 (2)处理“假溢出”的方法通常有下列3种： 1)每当从队首删除一个元素时，将队列中剩余的全部元素均向队首方向移动一个位置。 2)当发生假溢出时，将队列中现有的全部元素均向低下标方向移动一个位置。 3)上述两种方法都要进行大量元素的移动，效率低。最巧妙的方法是采用循环队列方式。循环队列是通过头、尾指针的循环来实现的。入队时，修改尾指针：rear=(l+rear)%MaxSize;出队时，修改队首指针：front=(l+front)%MaxSize。 2．要想得到PkPiPj，则必须先按i，j．k顺序全部进栈以后，再进行出栈操作。显然，第1个出栈的是最后进栈的Pk，而Pk出栈之后，栈顶元素是Pj，因此第2个出栈的应该是Pj。最后出栈的才是Pi，即出栈序列应该为PkPjPi，而不是PkPiPj。 3．-般环状队列头或尾其中之一要进行特殊处理，否则，当队列“空”或“满”时，只凭q.rear= =q.front无法判断。一般的处理方法是将q.rear指向下一个要插入的位置。这样，虽牺牲了一个单元的存储空间，但可以很容易地区分队列“空”或“满”。当q.rear==q.front时，表示队列“满”，当q.rear==(q.front+l)%n时，表示队列“空”。 4．设至少要执行M (n)次move操作，则 求解此方程，得M(n)=2n一l。 也可以递推得到，并由“数学归纳法”证明。 四、算法设计题 1．【分析与解答】 用一个栈SI作为输入栈，另一个栈S2作为输出栈。进行入队操作时，总是将数据加入到S1中;进行出队操作时，如果S2不空，则输出S2的元素;如果S2为空，则读取Sl的全部元素加入到S2中，然后由S2输出。当SI和S2均为空时，表示队列为空。假设栈的类型为STACK。 (1)进队。 void EnQueue (STACK *S, ElemType x) { if (SI->top==MaxSize-l) printf(¨overflow”); else Push (Sl，x); //以进栈代替进队 } (2)出队。 ElemType DeIQueue (STACK *SI,STACK kS2) { ElemType x; if(S2->top! =-1) Pop (S2, &x); else{ while( 1Empty (S1)){ Pop (S1, &x); Push (S2,x); } Pop (S2, &x); } return X; } (3)判断队空。 int EmptyQueue (STACK *S1, STACK *S2) { if(S1->top==-1 ＆＆S2->top==-l) return 1; //两个栈同时为空，则表示队空 return O; //队不空，返回O } 2．注意两侧的铁道均为单向行驶道，且两侧不相通。故车辆都必须通过“栈道”进行调度。 typedef char ElemType; int attemper (STACK *p, STACK *q) {//将p栈道的车厢，经调度之后入q栈道，使软席车厢调整到硬席车厢之前 STACK *temp; ElemType e; InitStack (temp); while(! Empty (p)){ P0p(p，＆e); if(e=='S') Push(q，e); else Push (temp,e); } while(! Empty (temp)) { Pop (temp; &e); Push (q,e);} } 本题本质上是对两类数据执行排序操作，将其中一类置于另一类之前。 3．(1)递归算法如下： int gcd（int m，int n） { int k; if(n==O) return (m); else return (gcd (n, m%n)); } (2)可以不使用栈而得到非递归函数gcd20如下： int gcd2 (int m，int n) { int r; do f r=m%n. m=n; n=r; } while (r); return m; ) (3)计算gcd(20，6)之值，栈变化过程如下图所示。 在top=3时，n的值为0，退栈，并返回2作为最后结果。 4．标志位tag的初值置为“0”。一旦元素入队，使rear==front时，需置tag为“1”;反之，一旦元素出队列使front=rear时，需置tag为“0”，以便使下一次进行入队列或出队列操作时(此时front= =rear)，可由标志位tag的值来区别队列当时的状态是“满”，还是“空”。 #define MaxSize 100 typedef struct f ElemType data [MaxSize]; int front，rear; int tag; } SqQueue; int EnQueue (SqQueue *q, ElemType e) {/插入元素e为q的新队尾元素，如队列满，则置tag=l if(q->rear==q->front＆＆tag==l) return 0; q->data[q->rear] =e; q->rear=(q->rear+l))%MaxSize; if(q->rear==q->front) tag=l; return 1： } int DeQueue (SqQueue *q, ElemType *e) {//若队列不空，则删除q的队头元素，用e返回;如队列空，则置tag=0 if (q->rear==q->front＆＆tag==0) return O; *e=q->data [q->front]; q->front=( q->front+l) %MaxSize; if (q->rear==q->front) tag=0; return 1; } 从空间角度看，设标记节省了一个空间(ElemType)，但在队列的使用过程中增加了算法复杂性。而不设标记正好相反。故当循环队列容量较小而队列中每个元素占的空间较多 时，可通过在结构体中增加一个标记位来最大限度地使用循环队列容量。 5．依题意，定义单链表结点类型如下： typedef struct Lnode( ElemType data; struct Lnode *next; }LinkNode; 根据单链表的特点，实现队列的5种运算的函数如下： void SetNull (LinkNode **front, LinkNode **rear) { *f ront=NULL; *rear=NULL;) int GetFirst (LinkNode *front, ElemType *x) { if (front==NULL) return O; else { x=front->data; return 1;) } int EnQueue (LinkNode **front, LinkNode **rear,ElemType x) { LinkNode *p; if (*rear==NULL){//若队列为空，则直接建立一个链表 *rear=( LinkNode*)malloc( sizeof( LinkNode)); ( *rear) ->d.ata=x;*front=*rear; } else { //若不为空，则建立一个结点将其链表链接到末尾 p= (LinkNode*)malloc (sizeof( LinkNode)); p->data=x; p->next=NULL; (*rear) ->next=p; *rear=p; } return 1; } int DeQueue (LinkNode **front, LinkNode**rear, { LinkNode *p; if (*front==NULL) return O; else{ p=*front; x=p->data; *front= (*front) ->next; free (p); if (*front==NULL) *rear=NULL; return l; *x) ElemType } } int QueueEmpty (LinkNode **front) { if (*front==NULL) return l; else return O; } 6．这里使用的循环链表不带头结点，规定p始终指向队尾结点，p->next即为队头结点。当p= =NULL时队列为空。队列插入和删除算法如下： typedef struct node( ElemType data; struct node *next; } QNode; void EnQueue (QNode **p, ElemType x) //队列插入 { QNode *s; s= (QNode*)malloc( sizeof( QNode)); s->data=x; if (*p==NULL)( *p=s; (*p)一>next=*p; } else{ s->next= (*p) ->next; //将s作为*p之后的结点 (*p) ->next=s; *p=s; //*p指向*s } } int DeQueue (QNode **p, ElemType *x) //队列删除 { QNode *s; if (*p==NULL) return 0; if( (*p)->next==NULL){ //只有一个结点的情况 x= (*p)->data; free (*p); *p=NUIL; } else{//将*p之后结点的data域值赋给x，然后删除之 s= (*p) ->next; *x=s->data; (*p)->next=s->next; free (s); } return 1; } 7．使用一个栈起到过渡的作用。先将sq队列中元素出队并将其入栈ss，直到队列空为止;然后初始化队列，即sq->front=sq->rear=n;再出栈并将其入队列，直到栈空为止。对应的算法如下： #define n 100 void reverse (squeue *sq) { ElemType x; STACK *ss; ss- (STACK *)malloc (sizeof (STACK)); //栈初始化 ss->top=-l; while(sq->front! =sq->rear){ //队不空时，出队并入栈 sq->front=(sq->front+l) %n; if (sq->front==0) sq->front=n; //队列元素下标从1到n x=sq->data[sq->front]; ss->top++; ss->data[ ss->top]=x; //将x入栈 } sq->front=sq->rear=n; while(ss->top>=0){ x=ss->data[ss->top]; ss->top--; sq->rear=(sq->rear+l)%n; sq->data[ sq->rear] =x; } } 8．计算Ack(m,n)的非递归算法为fun0函数。在fun0中采用一个二维数组作为栈，其内容如下： st (top,O)存储标记，该标记为l(m=0)、2(m≠O，n=0)或3 (m+0, n+0)。 st (top,1)存储Ack (m,n)之值，初值为0。 st (top,2)存储m。 st (top,3)存储n。 #define MaxSize 5000 int no (int m，int n) //根据m，n之值返回相应的标志 { if(m==0) return 1; else if(n==O) return 2; else return 3： } int fun (int m，int n) { int st [MaxSize][4],top=0, ml, nl; st [top] [0] =no (m,n); top++; //先移动栈指针 st [top] [1] =0; //初值O入栈 st [top] [2] =m; //初值m入栈 //top初值为O st [top] [3] =n; //初值n入栈 do{ if(st[top][1]==O)f if(st[top][O]==3){ top++; //入栈 st [top][1]=0; st[top] [2]=st [top-l][2]; st [top][3]=st [top-l][3]-1; st [top][0] =no (st[top][2], st[top] [3]); } else if (st [top] [0] ==2){ top++; //入栈 st [top][1]=0; st[top][2] =st [top-l] [2] -1; st [top][3] =1; st[top] [0] =no(st[top] [2], st [top] [3]); } if (st[top][0] ==1) st[top] [1] =st[top][3]+1; //求值 } if (top>=l&＆st[top] [1] !=0＆＆st [top-l] [0]==2){ st [top-l] [1] =st [top] [1]; top--; //出栈 } else if (top>=l＆＆st[top] [1] 1=0＆&st[top一1][O]==3)f nl=st [top] [1]; ml=st[top-l][2] -1; top--; //出栈 st [top] [1] =0; st [top] [2] =ml; st [top] [3] =nl; st [top][0] =no (st [top] [2], st [top] [3]); } if (top==l＆&st [top] [1] !=0) break; //栈中只有1个元素，且已计算出值，则退出循环 )while (top>=l); return (st [1] [1]); //st [1][1]就是所求的函数值 } 因篇幅问题不能全部显示，请点此查看更多更全内容