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

数据结构课后练习题 第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; 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 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;

1/7

北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1

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

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

A、Q.rear=Q.front->next; B、Q.rear->next=Q.rear->next->next; 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 的不同排列个数为（ ）【＊*，★】

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. 以下说法正确的是( ) 【＊*】

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. 栈和队列具有相同的（ ）。【＊＊，★，联考】

2/7

北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1

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

A. 抽象数据类型 C. 存储结构 B. 逻辑结构 D. 运算

二、 判断题

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. 栈的特点是（ ），队列的特点是（ ）。【＊】

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’); 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);

北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1

3/7

）插

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

} 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.

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

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

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

从循环队列中删除一个元素时，其操作是（ ）。（龚注：文字描述）【＊*，★】 在一个循环队列中，队首指针指向队首元素的（ ）。【＊，★，？】 在具有n 个单元的循环队列中，队满时共有（ ）个元素。【＊，★】

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

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

有程序如下，则此程序的输出结果（队列的元素类型是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); }

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));的结果是（ ）。

四、 简答题

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++;

4/7

北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1

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

pop(s,a[n]); }

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

push(s,a[I]); } (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); } }

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(“=”,w); printf(“\\n”);

} } 问：调用语句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);

5/7

北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1

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