北理工珠海学院《数据结构》习题集：第3章 栈和队列(第1次更新2012-3)

第3章 栈和队列

一、 选择题

1. 栈结构通常采用的两种存储结构是（ ）。【＊】

A、顺序存储结构和链表存储结构 B、散列和索引方式

C、链表存储结构和数组 D、线性链表结构和非线性存储结构

2. 设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ ）【＊，★】

A、ST.top-ST.base<>0 B、ST.top-ST.base==0

C、ST.top-ST.base<>n D、ST.top-ST.base==n

3. 向一个栈顶指针为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;

4. 从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行（ ）（龚注：栈无头结点）【＊，★】

A 、x=HS；HS=HS->next; B 、HS=HS->next；x=HS->data;

1/20

2011-3-1

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

C 、x=HS->data；HS=HS->next; D 、s->next=Hs；Hs=HS->next;

5. 表达式a*(b+c)-d 的后缀表达式为（ ）【＊*，★】

A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd

6. 中缀表达式A-（B+C/D）*E 的后缀形式是（ ）【＊*】

A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*-

7. 一个队列的入列序列是1，2，3，4， 则队列的输出序列是（ ）【＊，★】

A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1

8. 循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为空的条件是（ ）【＊，★】

A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n

C、Q.front==Q.rear D、Q.front==Q.rear+1

9. 循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为满的条件是（ ）【＊*，★】

A、Q.front==Q.rear B、Q.front!=Q.rear

2/20

2011-3-1

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

C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n

10. 若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（ ）【＊*】

A、1，5 B、2, 4 C、4，2 D、5，1

11. 用单链表表示的链式队列的队头在链表的（ ）位置【＊】

A、链头 B、链尾 C、链中

12. 判定一个链队列Q（最多元素为n 个）为空的条件是（ ）【＊】

A、Q.front==Q.rear B、Q.front!=Q.rear

C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n

13. 在链队列Q 中，插入s 所指结点需顺序执行的指令是（ ）【＊】

A 、Q.front->next=s；f=s; B 、Q.rear->next=s；Q.rear=s;

C 、s->next=Q.rear；Q.rear=s; D 、s->next=Q.front；Q.front=s;

14. 在一个链队列Q 中，删除一个结点需要执行的指令是（ ）【＊】

A、Q.rear=Q.front->next; B、Q.rear->next=Q.rear->next->next;

2011-3-1

3/20

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

C、Q.front->next=Q.front->next->next; D、Q.front=Q.rear->next;

15. 用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（ ）

A、仅修改队头指针 B、仅修改队尾指针【＊*，★】

C、队头尾指针都要修改 D、队头尾指针都可能要修改。

16. 栈和队列的共同点是（ ）【＊】

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

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

17. 消除递归（ ）需要使用栈。【＊*，★】

A、一定 B、不一定

18. 设有一顺序栈S，元素s1，s2，s3，s4，s5，s6 依次进栈，如果6 个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少应该是（ ）【＊*，★】

A、2 B、3 C、 5 D、 6

19. 若一个栈的输入序列是a，b，c，则通过入、出栈操作可能得到a,b,c 的不同排列个数为（ ）【＊*，★】

4/20

2011-3-1

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

A、 4 B、 5 C、 6 D、 7

20. 设有一顺序栈已经含有3 个元素，如图3.1 所示元素a4 正等待进栈。下列不可能出现的出栈序列是（ ）【＊*，★】

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

图3.1

21. 链栈和顺序栈相比，有一个比较明显的优势是（ ）【＊】

A、通常不会出现栈满的情况 B、通常不会出现栈空的情况

C、插入操作更容易实现 D、删除操作更加容易实现

22. 若一个栈的输入序列是1，2，3，4，…，n，输出序列的第一个元素是n，则第i 个输出元素是（【＊*，★】

A、不确定 B、 n-i C、 n-i+1 D、n-i-1

23. 以下说法正确的是( ) 【＊*】

2011-3-1

）5/20

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

A、因链栈本身没有容量,故在用户内存空间的范围内不会出现栈满情况

B、因顺序栈本身没有容量,故在用户内存空间的范围内不会出现栈满情况

C、对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢”

D、对于顺序栈而言在栈满状态下如果此时再作进栈运算，则会发生“下溢”。

(续：第1次2012-3)

24. 某队列允许在两端进行入队操作，但仅允许在一端进行出队操作，若a、b、c、d、e元素进队，则不可能得到的顺序是( )。【＊＊＊，★，考研2010】

A. bacde B. dbace C. dbcae D. ecbad

25. 已知输入序列为abcd，经过输出受限的双端队列后能得到的输出序列是（ ）。【＊＊＊，联考】

A. dacb B. cadb C. dbca D. 以上序列都不能得到

26. 栈和队列具有相同的（ ）。【＊＊，★，联考】

A. 抽象数据类型 B. 逻辑结构

C. 存储结构 D. 运算

6/20

2011-3-1

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

二、 判断题

1. 在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。 【＊】

2. 链栈与顺序栈相比的一个优点是链栈插入和删除操作更加方便。【＊】

3. 若一个栈的输入序列为 1，2，3，…，n，其输出序列的第一个元素为n，则其输出序列的每个元素一定满足ai=i+1(i=1,2, …,n)。【＊*】

4. 在链队列中，即使不设置尾指针也能进行入队操作。【＊】

5. 在对链队列（带头结点）做出队操作时，不会改变 front 指针的值。【＊】

6. 循环队列中元素个数为 rear-front。【＊*，★】

7. 一个栈的输入序列是 1,2,3,4，则在栈的输出序列中可以得到4,3,1,2。【＊】

8. 一个栈的输入序列是 1,2,3,4，则在栈的输出序列中可以得到1,2,3,4。【＊】

9. 若以链表作为栈的存储结构，则进栈需要判断栈是否满。【＊】

10. 若以链表作为栈的存储结构，则出栈需要判断栈是否空。【＊】

三、 填空题

1. 1、2、3、4顺序入栈，则出入栈的序列共有（ ）种。【＊*＊，★】

2. 栈的特点是（ ），队列的特点是（ ）。【＊】

7/20

2011-3-1

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

3. 线性表、栈、队列都是（ ）结构，可以在线性表的（ ）位置插入和删除元素；对于栈只能在（ ）插入和删除元素；对于队列只能在（ ）插入元素和在（ ）位置删除元素。【＊，★】

4. 有程序如下，则此程序的输出结果（栈的元素类型是SelemType 为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’);

2011-3-1

8/20

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

push(s,x);

pop(s,x);

push(s,’s’);

while(!stackempty(s)){

pop(s,y);

printf(y);//(龚注：printf(“%c”,y);

}

printf(x);//(龚注：printf(“%c”,x);

}

5. 在栈顶指针为HS 的链栈中，判定栈空的条件是（ ）。（龚注：文字描述）【＊】

6. 向栈中压入元素的操作是先（ ）后（ ）。（龚注：应是顺序存储结构栈）【＊，★】7. 对栈进行退栈操作是先（ ）后（ ）。（龚注：应是顺序存储结构栈）【＊，★】

8. 用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（ 若只设尾指针，则出队和入队的时间复杂度分别是（ ）和（ ）。【＊，★】

2011-3-1

和（ ）；9/20

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

9. 从循环队列中删除一个元素时，其操作是（ ）。（龚注：文字描述）【＊*，★】

10. 在一个循环队列中，队首指针指向队首元素的（ ）。【＊，★，？】

11. 在具有n 个单元的循环队列中，队满时共有（ ）个元素。【＊，★】

12. 在HQ 的链队列中，判断只有一个结点的条件是（ ）。（龚注：C语言描述）【＊】

13. 设栈S 和队列Q 的初始状态为空，元素a、b、c、d、e、f 依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b、d、c、f、e、a 则栈S 的容量至少应该是（ ）。【＊*】

14. 有程序如下，则此程序的输出结果（队列的元素类型是QSelemType 为char）是（ ）。【＊，★】

void main(){

char x=’e’,y=’c’;

enqueue(q,’h’);enqueue(q,’r’);enqueue(q,y);dequeue(q,x);enqueue(q,x);degueue(q,x);

enqueue(q,’a’);

while(!queueempty(q)){

dequeue(q,y);printf(y);//龚注：printf(“%c”,y);

10/20

2011-3-1

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

}

printf(x);//龚注：printf(“%c”,x);

}

15. 有如下递归函数：【＊*】

int dunno(int m){

int value;

if(m==0)

value=3;

else

value=dunno(m-1)+5;

return(value);

}

执行语句printf(“%d\\n”,dunno(3));的结果是（ ）。

2011-3-1

11/20

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

四、 简答题

1. 对于堆栈，给出三个输入项A，B，C，如果输入项序列为ABC，试给出全部可能的输出序列，并写

出每种序列对应的操作。例如：A 进B 进C 进C 出B 出A 出，产生的序列为CBA。【＊*】

2. 简述以下算法的功能（栈的元素类型是 SelemType 为int）。【＊*，★】

（1）

status algo1(stack s){

int I,n,a[255];

n=0;

while(!stackempty(s)){

n++;

pop(s,a[n]);

}

for(I=1;I<=n;I++)

push(s,a[I]);

2011-3-1

12/20

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

}

(2)

status algo2(stack s,int e){

stack t;int d;

initstack(t);

while(!stackempty(s)){

pop(s,d);

if(d!=e)

push(t,d);

}

while(!stackempty(t)){

pop(t,d);

push(s,d);

2011-3-1

13/20

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

}

}

3. 内存中一片连续空间（不妨假设地址从0 到m-1）提供给两个栈s1 和s2 使用，怎样分配这部分存储空间，使得对任一栈仅当这部分空间全满时才发生溢出。【＊*】

4. 有递归过程如下：【＊*】

void print(int w){

int I;

if(w!=0){

print(w-1);

for(I=1;I<=w;I++)

printf(“%3d”,w);

printf(“\\n”);

}

}

2011-3-1

14/20

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

问：调用语句print(4)的结果是什么？

5. 简述以下算法的功能（栈和队列的元素类型均为 int）【＊，★】

void algo(queue &q){

stack s;

int d;

initstack(s);

while(!queueempty(q)){

dequeue(q,d);

push(s,d);

}

while(!stackempty(s)){

pop(s,d);

enqueue(q,d);

2011-3-1

15/20

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

}

}

6. 假设 Q[0，9]是一个非循环线性队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的状态变化情况，如果不能入队，请指出其元素，并说明理由。【＊*，★】

d,e,b,g,h 入队 d,e 出队 I,j,k,l,m入队 b 出队 n,o,p,q,r 入队。

7. 按照运算符优先数法，画出对下面算术表达式求值时，操作数栈和运算符栈的变化过程：【＊*，★】

9-2*4+(8+1)/3。

8. 设栈S＝（1，2，3，4，5，6，7），其中7 为栈顶元素。写出调用algo 后栈S 的状态。【＊*，★】

void algo(Stack *S){

int i=0;

Queue Q;

Stack T;

InitQueue(Q);

InitStack(T);

16/20

2011-3-1

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

while(!StackEmpty(S)){

if(i%2==0)

Push(T,Pop(S));

else

EnQueue(Q,Pop(S));

i++;

}

while(!QueueEmpty(Q))

Push(S,DeQueue(Q));

while(!StackEmpty(T))

Push(S,Pop(T));

}

五、 设计题

1. 在栈顶指针为 HS 的链栈中，写出计算该链栈中结点个数的函数？【＊*】

2011-3-1

17/20

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

2. 已知 Q 是一个非空队列，S 是一个空栈，使用C 语言编写一个算法，仅用队列和栈的ADT 函数和少量工作变量，将队列Q 中的所有元素逆置。【＊*＊，★】

栈的ADT 函数有:

void SetEmpty(stack s); //置空栈

void Push(stack s,ElemTye value); //新元素value 进栈

ElemType Pop(stack s); //出栈，返回栈顶值

Boolean IsEmptyS(stack s); //判断栈空否

队列ADT 的函数有：

void EnQueue(Queue q,ElemType value); //元素入队

ElemType DeQueue(Queue q); //出队列返回队头值

Boolean IsEmptyQ(Queue q); //判断队列是否为空

3. 用单链表实现队列，如下图所示，并令 front=rear=NULL 表示队列为空，编写实现队列的如下五种运算的函数。【＊*＊，★】

Setnull:将队列置成空队列。

18/20

2011-3-1

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

getfirst:返回队列的第一个元素。

enqueue:把元素插入队列的后端。

dequeue:删除队列的第一个元素。

empty:判定队列是否为空。

4. 有 A,B,C 三个塔座，A 上套有n 个直径不同的圆盘，按直径从大到小叠放，形如宝塔,编号1,2,3……n。要求将n 个圆盘从A 移到C，叠放顺序不变，移动过程中遵循下列原则：【＊*＊】

a) 每次只能移一个圆盘

b) 圆盘可在三个塔座上任意移动

c) 任何时刻，每个塔座上不能将大盘压到小盘上

5. 回文游戏：顺读与逆读字符串一样（不含空格）【＊*＊】

6. 数制转换：对于输入的任意一个非负十进制数,打印输出与其等值的八进制数。（利用栈）【＊*＊，★】

7. 括号匹配检验：假设在表达式中有三种括号（ ）{ } [ ]，检查表达式括号是否配对。【＊*＊，★】行编

19/20

2011-3-1

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

辑程序问题：在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。

要求： 设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退

格符，“@”为退行符。（利用栈来完成）

2011-3-1

20/20