数据结构第3章栈和队列练习题

第三章 栈和队列

一、 选择题

1.以下不是栈的基本运算的是( )

A) 删除栈顶元素 B) 删除栈底元素 C) 判断栈是否为空 D) 将栈置为空栈

2.若进栈序列为1,2,3,4,进栈过程中可以出栈,则下列不可能的一个出栈序列是( ) A) 1,4,3,2 B) 2,3,4,1 C) 3,1,4,2 D) 3,4,2,1

3.栈和队列的共同点( )

A) 都是先进先出 B) 都是后进先出

C) 只允许在端点处插入和删除元素 D) 没有共同点

4.若已知一个进栈序列是1,2,3,……,n,其输出序列是p1,p2,vp3,……pn, 若p1=n, 则pi(1

A) I B) n-i

C) n-i+1 D) 不确定

5.判断一个栈ST(最多元素为MaxSize)为空的条件是( ) A) ST->top==1 B) ST->top==-1

C) ST->top!=MaxSize-1 D) ST->top==MaxSize-1

6.向一个栈指针为HS的链式栈中插入一个s所指的结点时,则执行() A) HS->NEXT=S;

B) S->NEXT=HS->NEXT;HS->NEXT=S; C) S->NEXT=HS;HS=S;

D) S-.NEXT=HS;HS=HS->NEXT;

7.在一个链式队列中.假设f和r分别为队头和队尾指针,则插入s所指的结点运算是() A) f->next=s;f=s; B) r->next=s;r=s; C) s->next=s;r=s; D) s->next=f;f=s;

8.在一个链式队列中,假设f和r分别为队头和队尾指针,则删除结点的运算是() A) r=f->next; B) r=r->next; C) f=f->next; D) f=r->next; 9.下列关于线性表,栈和队列叙述,错误的是()

A) 线性表是给定的n(n必须大于零)个元素组成的序列 B) 线性表允许在表的任何位置进行插入和删除操作 C) 栈只允许在一端进行插入和删除操作

D) 队列只允许在一端进行插入一端进行删除

10.一个队列的入队序列是1,2,3,4,则队列的输出序列是() A) 4,3,2,1 B) 1,2,3,4 C) 1,4,3,2 D) 3,2,4,1

11.设初始输入序列为1,2,3,4,5,利用一个栈产生输出序列,下列()序列是不可能通过栈产生的. A) 1,2,3,4,5 B) 5,3,4,1,2 C) 43,2,1,5 D) 3,4,5,2,1

12.设栈s的初始状态为空,6个元素的入栈顺序为e1,e2,e3,e4,e5和e6.若出栈的顺序是e2,e4, e3,e6,e5,e1,则栈s的容量至少应该是()

A) 6 B) 4 C) 3 D) 2

13.为了减小栈溢出的可能性，可以让两个栈共享一片连续存储空间，两个栈的栈底分别设在这片空间的两端，这样只有当（ ）时才可能产生上溢。

A．两个栈的栈顶在栈空间的某一位相遇 B．其中一栈的栈顶到达栈空间的中心点 C．两个栈的栈顶同时到达空间的中心点

D．两个栈均不空，且一个栈的栈顶到达另一个栈的栈顶

14.若进栈序列为3，5，7，9，进栈过程中可以出栈，则（ ） 不可能是一个出栈序列。

A.7,5,3,9 B.9,7,5,3 C.7,5,9,3 D.9,5,7,3

15.数组Q[0……n-1]用来表示一个环形队列，f为当前对头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数总小于n，计算队列中元素个数的公式为（ ）。

A.r-f B.n+f-r

C.n+r-f D.(n+r-f)mod n

16.4个元素a1、a2、 a3和a4 依次入栈，入栈过程中允许元素出栈，假设某一时刻站的状态是a3（栈顶）、a2、a1、（栈底），则不可能的出栈顺序是（ ）。

A. a4, a3, a2 , a1 B. a3, a2 ,a4,a1 C. a3, a1 ,a4 ,a2 D. a3,a4, a1, a2

17.与数据元素本身的形式、内容、相对位置、个数无关的数据是（ ）。

A.存储结构 B.存储实现 C.逻辑结构 D.运算实现 18.设用一个数组A[1……N]来存储一个栈，令A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。当从栈中弹出一个元素时，变量T的变化为（ ）。

A.T=T+1 B.T=T-1 C.T不变 D.T=n

19.有六个元素1、2、3、4、5、6的顺序进栈，下列（ ）不是合法的出栈序列。

A.2、3、4、1、6、5 B.3、2、4、6、5、1 C.4、3、1、2、5、6 D.5、4、6、3、2、1

20.一个栈的入栈顺序是a、b、c、d、e，则栈的不可能输出序列是（ ）。

A.e、d、c、b、a B.d、e、c、b、a C.d、c、e、a、b D.a、b、c、d、e

21.设计一个判别表达式左、右括号是否配对出现的算法，采用（ ）数据结构最佳。

A.线性表的顺序存储结构 B.栈

C.队列 D.线性表的链式存储结构 22.下面4种内排序方法中，要求内存容量最大的是（ ）。

A.插入排序 B.选择排序 C.快速排序 D.归并排序 23.栈的插入和删除操作在（ ）进行。

A.栈顶 B.栈底 C.任意位置 D.指定位置 24.向顺序栈中压入新元素时，应在（ ）。

A.先移动栈顶指针 B.先存入元素，再移动栈顶指针 C.先后次序无关紧要 D.同时进行

25.链式栈与顺序栈相比，一个比较明显的优点是（ ）。

A.插入操作更加方便 B.通常不会出现栈满的情况 C.不会出现栈空的情况 D.删除操作更加方便

26.设一列顺序为1，2，3，4，5，6通过栈操作可以得到（ ）的输出序列。

A.3，2，5，6，4，1 B.1，2，3，4，5，6 C.6，5，4，3，2，1 D.4，5，3，2，6，1

27.设一个栈的输入序列为A,B,C,D，则借助一个栈所得到输出序列不可能是( ).

A.A,B,C,D B.D,C,B,A C.A,C,D,B D.D,A,B,C

28.若用一个大小为6的数组来实现循环队列，且当前rear和fornt的值分别为0和3。从当前队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）。

A.1和5 B.2和4 C.4和2 D.5和1 29.由两个栈共享一个向量空间的好处是（ ）。

A.减少存取时间，降低下溢发生的机率 B.节省存储空间，降低上溢发生的机率 C.减少存取时间，降低上溢发生的机率 D.节省存储空间，降低下溢发生的机率 30.设一数列的顺序为1，2，3，4，5，6，通过队列操作可以得到（ ）的输出序列。

A.3,2,5,6,4,1 B.1,2,3,4,5,6 C.6,5,4,3,2,1 D.4,5,3,2,6,1 31.从一个顺序队列中删除元素时，首先要（ ）。

A.前移一位队首指针 B.后移一位队首指针

C.取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素 32.在一个顺序存储的循环队列中，队头指针指向队头元素的（ ）。

A.前一个位置 B.后一个位置 C.队头元素位置 D.队尾元素位置

33.两栈共享数组存储空间，前一个栈的栈顶指针为p后一个栈的栈顶指针为q，能进行正常入栈操作的条件是（ ）。

A.p<=q B.p>q C.p

34.一个递归的定义可以用递归过程的求解，也可以用非递归过程求解，但单位从用行时间来看，通常递归过程比非递归过程（ ）。

A .较快 B.较慢 C.相同 D.无法确定 35.在一个顺序循环队列中，队尾指针指向队尾元素的（ ）位置。

A.后两个 B.后一个 C.当前 D.前一个 36.若(a-b)*(c+d)是中序表达式，则其后序表达式是（ ）。

A．abcd+*- B.ab-cd+* C.ab-*cd+ D.a-bcd+*

37.字符A,B,C依次进入一个栈,按出栈的先后顺序组成不同的字符串,则至多可以组成()个不同的字符串.

A)14 B)5 C)6 D)8

二、 填空题

1.栈和队列的区别在于______________。

2.通常元素进栈的顺序是______________________ 。 3.通常元素出栈的顺序是________________________。

4.从一个循环队列中删除一个元素，通常的操作是____________________. 5.像一个循环队列中插入一个元素，通常的操作是____________________. 6.设栈S的初始状态为空，队列Q的初始状态如图所示 ___________________________________________ a1 a2 a3 a4

___________________________________________

↑ ↑

对头 队尾 对栈S和队列Q进行以下两步操作：

（1）删除Q中的元素，将删除的元素插入S，直到Q为空 （2）依次将S中的元素插入Q，直到S为空

在上述两步操作后，队列q的状态是_______________ 7.栈又称为___________表，队列又称为__________表。 8.栈中元素的进出原则是：_____________。 9.队列中元素的进出原则是：_______________。

10.一个栈的输入序列是12345，则栈的输出序列43512是_______________。 11.从循环队列中删除一个元素时，通常的操作是__________________。 12.向循环队列中插入一个元素时，通常的操作是______________。

13.对于顺序存储的栈，因为栈的空间是有限的，在进行__________运算时，可能发生栈的上溢，__________在进行_____________运算时，可能发生栈的下溢。

14.当堆栈用用顺序存储结构时，栈顶元素的值可用_________表示；当堆栈采用链式存储结构时，栈顶元素的值可用____________表示。

15.若已知一个栈的入栈顺序是1，2，3，……n,其输出序列为p1,p2,p3,……，pn,若p1=n,则pi(1

16.向一个链栈插入一个p 所指向的结点时，需要把栈顶指针的值赋给p所指向的结点的_____________，然后把p赋给______________。

17.当用长度为N的数组顺序存储一个栈时，假定用top=N表示栈空，则表示栈满的条件为____________。

18.在用一维数组A[N]存储一个顺序循环队列时，若队列的首、尾指针分别用f和r表示，则队列长度为____________。

19.假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列操作SSXSXSSXXX之后，得到的输出序列为_________。

三、指出下述程序段的功能是什么?

(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);}

四、判断题

1.栈和队列的存储，既可以采用顺序存储结构，又可以采用链式存储结构。 2.任何一个递归过程都可以转换成非递归过程。

3.若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列3，2，5，6，4， 4.通常使用队列来处理函数的调用。

5.循环队列通常用指针来实现队列的头尾相接。 6．栈的数据存储原则是先进先出。 7．栈中只有栈底元素不能被删除。 8．循环队列也存在空间溢出问题。 9．栈和队列的存储方式，只能是顺序存储。 10．栈和队列逻辑上都是线性的。

11．对于链队来说，即使不设置尾指针也能进行入队操作。

12．队列的入队序列为”1，2，3，……，n”，出队序列为”P1,P2,P3,……,Pn”，则Pi+1>Pi。

13．循环队列就是采用循环链表作为存储结构的队列。

14.若一个栈为空，则可以不用栈顶指针。

15．栈是一种入栈和出栈操作的次序作了限制的线性表。

五、算法设计题

1．采用递归方法把任一十进制正整数转换为s(2<=s<=9)数输出。 2．采用辗转相除和递归方法求两个正整数的最大公约数。 3. 采用递归的方法求两个数的最小公倍数

4．在一个链式队列中只设置队尾指针，不设置队首指针，并且让队尾结点的指针域指向队首结点（称此为循环队列），试分别写出在循环链队上进行插入和删除操作的算法。 5. 一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法， 其中i为0 或1， 用以表示栈号。 6.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时

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

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

9.利用栈的基本操作，写一个将栈S中所有结点均删去的算法void ClearStack( SeqStack *S)，并说明S为何要作为指针参数?

10.利用栈的基本操作， 写一个返回S中结点个数的算法 int StackSize( SeqStack S),并说明S为何不作为指针参数?

11. 设计算法判断一个算术表达式的圆括号是否正确配对。 (提示： 对表达式进行扫描，凡遇到'('就进栈，遇')'就退掉栈顶的'('，表达式被扫描完毕，栈应为空。

12. 用少用一个元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取队头元素等六个基本操作的算法。 13. 对于循环向量中的循环队列，写出求队列长度的公式。 14.写算法，借助于栈将一个单链表置逆。

本文来源：https://www.bwwdw.com/article/q5l3.html