数据结构（栈）练习题与答案

1、栈的“先进后出”特性是指（）。

A.最后进栈的元素总是最先出栈

B.同时进行进栈和出栈操作时，总是进栈优先

C.每当有出栈操作时，总要先进行一次进栈操作

D.每次出栈的元素总是最先进栈的元素

正确答案：A

2、给定一个足够大的空栈，有4个元素的进栈次序为A、B、C、D,

则以C、D开头的出栈序列的个数为（）。

A.1

B.2

C.3

D.4

正确答案：A

解析：若出栈序列为CD…，则A、B、C进栈，C出栈，D进栈，D出

栈，此后只有B出栈和A出栈一种情况，所以这样的出栈序列只有

CDBA一个。

3、若元素a、b、c、d、e、f依次进栈，允许进栈、退栈的操作交

替进行，但不允许连续3次退栈工作，则不可能得到的出栈序列是

（）0

A.dcebfa

B.cbdaef

C.bcaefd

D.afedcb

正确答案：D

解析：选项A操作：a进，b进，c进，d进，d出，c出，e进，e

出，b出，f进，f出，a出。

选项B操作：a进，b进，c进，c出，b出，d进，d出，a出，e

进，e出，f进，f出。

选项C操作：a进，b进，b出，c进，c出，a出，d进，e进，e

出，f进，f出，d出。

选项D操作：a进，a出，b进，c进，d进，e进，f进，f出，e

出，d出，c出，b出。

从中看到，选项D中最后连续出栈5次，不符合要求。

4、一个栈的进栈序列是a、b、c、d、e,则栈的不可能的输出序列

是（）。

A.edcba

B.decba

C.dceab

D.abode

正确答案：C

解析：对于选项A,a、b、c、d、e进栈，e、d、c、b、a出栈；

对于选项B,a,b,c,d进栈，d出栈，e进栈，e出栈，c、b、a

依次出栈；

对于选项C,a、b、c、d进栈，d出栈，c出栈，e进栈，e出栈，

此时栈中从栈底到栈顶为a、b,不可能a先出栈，所以C是不可能

的输出序列；

对于选项D,a进栈，a出栈，b进栈，b出栈，c进栈，c出栈，d

进栈，d出栈，e进栈，e出栈。

5、当用一个数组data[0..nT]存放栈中元素时，栈底最好（）。

A.设置在data[0]处

B.设置在data[nT]处

C.设置在data[0]或data[nT]处

D.设置在data数组的任何位置

正确答案：C

解析：栈中元素的逻辑关系呈现线性关系，这样有两个端点，最好

将栈底设置在某个端点data[0]或data[nT]处，从而方便栈运算算

法的设计。

6、若一个栈用数组data[l..n]存储，初始栈顶指针top为n+1,则

以下元素x进栈的正确操作是（）。

A.top++;data[top]=x;

B.data[top]=x;top++;

C.top一;data[top]=x;

D.data[top]=x;top—;

正确答案：C

7、若一个栈用数组data[l..n]存储，初始栈顶指针top为0,则以

下元素x进栈的正确操作是（）。

A.top++;data[top]=x;

B.data[top]=x;top++;

C.top一;data[top]=x;

D.data[top]=x;top一;

正确答案：A

解析：初始栈顶指针top为0,说明data[l]端作为栈底，在进栈时

top应递增，由于不存在data[0]的元素，所以在进栈时应先将top

递增，再将x放在top处

8、在设计链栈时，通常采用单链表作为链栈，而不采用双链表作为

链栈，其准确的原因是（）。

A.栈中元素是顺序存取的，用单链表就足够了

B.栈中元素是随机存取的，用单链表就足够了

C.双链表运算较单链表更复杂

D.双链表存储密度较单链表低

正确答案：A

解析：因为栈中元素是顺序存取的（指逐个存或取结构中的元素），

而不是随机存取的，用单链表就足够了。

9、栈和队列的不同点是（）。

A.都是线性表

B.都不是线性表

C.栈只能在同一端进行插入删除操作，而队列在不同端进行插入删

除操作

D.没有不同点

正确答案：C

解析：栈和队列的不同点是，栈在同一端进行插入和删除操作，而

队列在不同端进行插入和删除操作。

10、设循环队列qu中数组data的下标是。〜N-1,其队头、队尾指

针分别为f和r（f指向队首元素的前一位置，r指向队尾元素），

元素x进队的操作是（）;qu.dataEqu.rear]=xo

A.qu.rear++

B.qu.rear=（qu.rear+1）%N

C.qu.front++;

D.qu.front=（qu.front+l）%N

正确答案：B

解析：对于循环队列，进队操作仅移动队尾指针，元素x进队的操

作是：qu.rear=(qu.rear+l)%N;qu.data[qu.rear]=x。

11、设循环队列qu中数组data的下标是。〜NT,其队头、队尾指

针分别为f和r(f指向队首元素的前一位置，r指向队尾元素)，

元素x出队的操作是()；x=qu.data[qu.front]。

A.qu.rear++

B.qu.rear=(qu.rear+1)%N

C.qu.front++;

D.qu.front=(qu.front+l)%N

正确答案：D

解析：对于循环队列，出队操作仅移动队头指针，元素x出队的操

作是：qu.front=(qu.front+l)%N;x=qu.data[qu.rear]。

12＞若某循环队列有队首指针front和队尾指针rear,在队不空时

出队操作仅会改变()。

A.front

B.rear

C.front和rear

D.以上都不对

正确答案：A

解析：当循环队列不空时，出队操作只能改变队头指针front。

13、通常设置循环队列qu的队空条件(front队首指针指向队首元

素的前一位置，rear队尾指针指向队尾元素)是()。

A.(qu.rear+1)%MaxSize==(qu.front+1)%MaxSize

B.(qu.rear+1)%MaxSize==qu.front+1

C.（qu.rear+1）%MaxSize==qu.front

D.qu.rear==qu.front

正确答案：D

解析：在循环队列中，通常设置队头等于队尾时表示队空。

14、设循环队列的存储空间为a[0..20],且当前队头指针（f指向

队首元素的前一位置）和队尾指针（r指向队尾元素）的值分别为8

和3,则该队列中元素个数为（）。

A.5

B.6

C.16

D.17

正确答案：C

解析：这里MaxSize=21,其中的元素个数=（r-

f+MaxSize）%MaxSize=16o

15、假设用一个不带头节点的单链表表示队列，队头在链表的（）

位置。

A.链头

B.链尾

C.链中

D.以上都可以

正确答案：A

解析：在用单链表表示的链队中，以单链表的链头作为队头，以单

链表的链尾作为队尾。

16、与顺序队相比,链队（）。

A.优点是可以实现无限长队列

B.优点是进队和出队时间性能更好

C.缺点是不能进行顺序访问

D.缺点是不能根据队首和队尾指针计算队的长度

正确答案：D

解析：尽管链队总是采用动态分配方式，其长度也受内存大小的限

制，也不可能实现无限长队列。顺序队和链队的进队和出队操作时

间均为0（1）。顺序队和链队都可以进行顺序访问。在顺序队中可以

通过队头和队尾指针计算队中元素个数，而链队不能。

17、若用一个大小为6的数组来实现循环队列，且当前rear和

front的值分别为。和3,当从队列中删除一个元素，再加入两个元

素后，rear和front的值分别为（）。

A.1和5

B.2和4

C.4和2

D.5和1

正确答案：B

解析：rear=0,进队2个元素后，rear循环递增2,rear=2；

front=3,出队一个元素后，front循环递增1,front=4o

18、一个循环队列中用data[0..n-l]数组保存队中元素，另设置一

个队尾指针rear和一个记录队中实际元素个数的变量count,则该

队中最多可以存放的元素个数是（）。

A.n-1

B.n

C.(rear+n)%n

D.(n-rear)%n

正确答案：B

解析：队满的条件为count==n0

19、已知循环队列存储在一维数组A[O..n-l]中，且队列非空时

front和rear分别指向队头元素和队尾元素。若初始时队列空，且

要求第一个进入队列的元素存储在A[0]处，则初始时front和rear

的值分别是（）。

A.0,0

B.0,n-1

C.n-1,0

D.n-l,n-1

正确答案：B

解析：在循环队列中，进队操作是队尾指针rear循环加1