《数据结构》习题集：第3章 栈和队列

第3章栈和队列

一、选择题

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

A、顺序存储结构和链表存储结构

B、散列和索引方式

C、链表存储结构和数组

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

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

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 结点时，则执行（C ）

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 保存被删除结点的值，则执行（C ）

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 的后缀表达式为（ B ）

A、abcdd+-

B、abc+*d-

C、abc*+d-

D、-+*abcd

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

A、AB-C+D/E*

B、ABC+D/E*

C、ABCD/E*+-

D、ABCD/+E*-

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

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，则判定此循环队

列为空的条件是（C ）

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，则判定此循环队

列为满的条件是（C ）

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 的值分别为（ B ）

A、1，5

B、2, 4

C、4，2

D、5，1

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

A、链头

B、链尾

C、链中

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

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 所指结点需顺序执行的指令是（B ）

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 中，删除一个结点需要执行的指令是（ C ）

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.用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时

（ D ）

A、仅修改队头指针

B、仅修改队尾指针

C、队头尾指针都要修改

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

16.栈和队列的共同点是（C ）

A、都是先进后出

B、都是先进先出

C、只允许在端点处插入和删除元素

D、没有共同点

17.消除递归（ B ）需要使用栈。

A、一定

B、不一定

18.设有一顺序栈S，元素s1，s2，s3，s4，s5，s6 依次进栈，如果6 个元素出栈的顺序是s2，s3，s4，s6，s5，s1，

则栈的容量至少应该是（ B ）

A、2

B、3

C、5

D、6

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

A、4

B、5

C、6

D、7

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

A、a3,a1,a4,a2

B、a3,a2,a4,a1

C、a3,a4,a2,a1

D、a4,a3,a2,a1

图3.1

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

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

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

C、插入操作更容易实现

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

22.若一个栈的输入序列是1，2，3，4，…，n，输出序列的第一个元素是n，则第i 个输出元素是（ C ）

A、不确定

B、n-i

C、n-i+1

D、n-i-1

23.以下说法正确的是( A )

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

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

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

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

二、判断题

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

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

3.若一个栈的输入序列为1，2，3，…，n，其输出序列的第一个元素为n，则其输出序列的每个元素一定满足

a i=i+1(i=1,2, …,n)。(F)

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

5.在对链队列（带头指针）做出队操作时，不会改变front 指针的值。(T)

6.循环队列中元素个数为rear-front。(F)

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

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

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

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

三、填空题

1.栈的特点是（先进后出），队列的特点是（先进先出）。

2.线性表、栈、队列都是（线性）结构，可以在线性表的（任意）位置插入和删除元素；对于栈只能在（栈

顶）插入和删除元素；对于队列只能在（尾）插入元素和在（头）位置删除元素。

3.有程序如下，则此程序的输出结果（Stack）。

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

}

4.在栈顶指针为HS 的链栈中，判定栈空的条件是（HS==NULL ）。

5.向栈中压入元素的操作是先（存入元素）后（移动栈顶指针）。

6.对栈进行退栈操作是先（移动栈顶指针）后（删除元素）。

7.用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（o(1)）和（o(n)）；若只

设尾指针，则出队和入队的时间复杂度分别是（o(1) ）和（o(1)）。

8.从循环队列中删除一个元素时，其操作是（先移除元素,再移动队首指针，）。

9.在一个循环队列中，队首指针指向队首元素的（当前位置）。

10.在具有n 个单元的循环队列中，队满时共有（n-1）个元素。

11.在HQ 的链队列中，判断只有一个结点的条件是（HQ.front->next=HQ.rear）。

12.设栈S 和队列Q 的初始状态为空，元素a、b、c、d、e、f 依次通过栈S，一个元素出栈后即进入队列Q。若

这6个元素出队列的顺序是b、d、c、f、e、a 则栈S 的容量至少应该是（3）。

13.有程序如下，则此程序的输出结果是（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(x);

}

14.有如下递归函数：

int dunno(int m){

int value;

if(m==0)

value=3;

else

value=dunno(m-1)+5;

return(value);

}

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

四、简答题

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

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

答：A进A出B进B出C进C出产生的序列为ABC

A进A出B进C进C出B出产生的序列为ACB

A进B进B出C进C出A出产生的序列为BCA

A进B进C进C出B出A出产生的序列为CBA

A进B进B出A出C进C出产生的序列为BAC

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

}

答：翻转储存栈里的内容

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

}

}

答：利用栈t 将栈s 中的数据元素e 删除

3.内存中一片连续空间（不妨假设地址从0 到m-1）提供给两个栈s1 和s2 使用，怎样分配这部分存储空间，

使得对任一栈仅当这部分空间全满时才发生溢出。

答：把0作为s1的栈底, m-1作为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”);

}

}

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

1

2 2

3 3 3

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

}

}

答：把队列的元素的存储顺序倒转存储。

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 入队。

答：d,e,g,h入队后front=0,rear=5

d,e出队后front=2 ,rear =5

I,j,k,l,m入队后front=2,rear=10

b出队后front=3,rear=10

n,o,p,q,r入队后front=3,rear=15

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

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

答:操作数栈进栈的顺序是：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);

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

}

答:{6 4 2 1 3 5 7}

五、设计题

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

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:将队列置成空队列。

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

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

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

empty:判定队列是否为空。

4.有A,B,C 三个塔座，A 上套有n 个直径不同的圆盘，按直径从大到小叠放，形如宝塔,编号1,2,3……n。要求

将n 个圆盘从A 移到C，叠放顺序不变，移动过程中遵循下列原则：

a)每次只能移一个圆盘

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

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

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

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

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

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

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

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

完整版数据结构习题集第3章栈和队列

第3章栈和队列 一、选择题 1.栈结构通常采用的两种存储结构是（A ）。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2.设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ B ） 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 结点时，则执行（ C ） 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 保存被删除结点的值，则执行（ C） 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 的后缀表达式为（ B ） A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6.中缀表达式A-（B+C/D）*E 的后缀形式是（ D ） A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7.一个队列的入列序列是1，2，3，4，则队列的输出序列是（ B ） 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;

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

第三章栈和队列试题 一、单项选择题 1.栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 2.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时， 首先应执行（）语句修改top指针。 A. top++; B. top--; C. top = 0; D. top; 3.若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。 A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 5.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 6.从一个顺序存储的循环队列中删除一个元素时，需要（）。 A. 队头指针加一 B. 队头指针减一 C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear 8.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 9.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一 个由指针s所指的结点，则应执行操作（）。 A. top->link = s; B.s->link = top->link; top->link = s; C. s->link = top; top = s; D. s->link = top; top = top->link; 10.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点， 并将被摘除结点的值保存到x中，则应执行操作（）。 A. x = top->data; top = top->link; B. top = top->link; x = top->data; C. x = top; top = top->link; D. x = top->data; 11.设循环队列的结构是 #define MaxSize 100 typedef int ElemType;

栈和队列习题答案

第三章栈和队列习题答案 一、基础知识题 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： (1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈) (2)能否得到出栈序列1423和1432并说明为什么不能得到或者如何得到。 (3)请分析1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 答：(1)出栈序列为：1324 (2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。 (3)在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是： 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是： 1423,2413,3124,3142,3412,4123,4132,4213,4231,4312 链栈中为何不设置头结点 答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。 循环队列的优点是什么如何判别它的空和满 答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何若只设尾指针呢答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。 指出下述程序段的功能是什么 (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]); } .. // 设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)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的

第三章栈和队列习题_数据结构电子教案

习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（） A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后，i值为：（） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1)); A．2 B. 4 C. 8 D. 无限递归 7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 8. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front

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

第3章栈与队列 一、单项选择题 1．元素A、Ｂ、C、D依次进顺序栈后，栈顶元素是，栈底元素是。 A．A B．B C．C D．D 2．经过以下栈运算后，x的值是。 InitStack(s)；Push(s,a)；Push(s,b)；Pop(s,x)；GetTop(s,x); A．a B．b C．1 D．0 3．已知一个栈的进栈序列是ABC，出栈序列为CBA，经过的栈操作是。 A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,pop C．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop 4．设一个栈的输入序列为A、B、C、D，则借助一个栈所得到的序列是。 A．A,B,C,D B．D,C,B,A C．A,C,D,B D．D,A,B,C 5．一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是。 A．edcba B．decba C．dceab D．abcde 6．已知一个栈的进栈序列是1，2，3，……,n，其输出序列的第一个元素是i，则第j个出栈元素是。 A．i B．n-i C．j-i+1 D．不确定 7．已知一个栈的进栈序列是1，2，3，……，n，其输出序列是p1,p2,…,Pn，若p1=n，则pi的值。 A．i B．n-i C．n-i+1 D．不确定 8．设n个元素进栈序列是1，2，3，……，n，其输出序列是p1,p2,…,p n，若p1=3,则p2的值。 A．一定是2 B．一定是1

C．不可能是1 D．以上都不对 9．设n个元素进栈序列是p1,p2,…,p n，其输出序列是1，2，3，……，n，若p3=1,则p1的值。 A．可能是2 B．一定是1 C．不可能是2 D．不可能是3 10．设n个元素进栈序列是p1,p2,…,p n，其输出序列是1，2，3，……，n，若p3=3,则p1的值。 A．可能是2 B．一定是2 C．不可能是1 D．一定是1 11．设n个元素进栈序列是p1,p2,…,p n，其输出序列是1，2，3，……，n，若p n=1,则p i(1≤i≤n-1)的值。 A．n-i+1 B．n-i C．i D．有多种可能 12．判定一个顺序栈S为空的条件为。 A．S.top= =S.base B．S.top!= S.base C．S.top!= S.base+S.stacksize D．S.top= = S.base+S.stacksize 13．判定一个顺序栈S为栈满的条件是。 A．S.top-S.base= =S.stacksize B．S.top= = S.base C．S.top-S.base!=S.stacksize D．S.top!= S.base 14．链栈与顺序栈相比有一个明显的优点，即。 A．插入操作方便B．通常不会出现栈满的情况 C．不会出现栈空的情况D．删除操作更加方便 15．最不适合用作链栈的链表是。 A．只有表头指针没有表尾指针的循环双链表 B．只有表尾指针没有表头指针的循环双链表 C．只有表尾指针没有表头指针的循环单链表 D．只有表头指针没有表尾指针的循环单链表 16．如果以链表作为栈的存储结构，则退链栈操作时。 A．必须判别链栈是否满B．判别链栈元素的类型 C．必须判别链栈是否空D．对链栈不作任何判别

第三章栈和队列练习题

第三章栈和队列练习题 一、单项选择题 1．一个顺序栈一旦被声明，其占用空间的大小（）。 A．已固定B．可以改变C．不能固定D．动态变化 2．链栈和顺序栈相比，有一个比较明显的缺点，即（）。 A．插入操作更加方便B．通常不会出现栈满的情况 C．不会出现栈空的情况D．删除操作更加方便 3．用单链表表示的链式队列的队头在链表的（）位置。 A．链头B．链尾C．链中D．任意位置 4．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（）结构。 A．堆栈B．队列C．数组D．先性表 5．若已知一个栈的入栈序列是1，2，3，…，30，其输出序列是p1,p2,p3,…p n，若p1=30，则p10为（）。 A．11 B．20 C．19 D．21 6．循环队列A[m] 存放其元素，用front和rear分别表示队头及队尾，则循环队列满的条件是（）。 A．（rear+1)%m=front B．rear =front+1 C．rear=front D．（rear+1)%m-1=front 7．在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（）。 A．top->next=p; B．p->next=top->next; top->next=p; C．p->next=top; top=p; D．p->next=top->next; top=top->next; 8．在一个栈顶指针为top的链栈中删除一个结点时，用x保存被删结点的值，则执行（）。 A．x=top;top=top->next; B．x=top->data;

PTA第三章栈与队列练习题

1-1 通过对堆栈S操作:Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出得序列为:123。(2分) T F 作者: DS课程组 单位: 浙江大学 1-2 在用数组表示得循环队列中,front值一定小于等于rear值。(1分) T F 作者: DS课程组 单位: 浙江大学 1-3 若一个栈得输入序列为{1, 2, 3, 4, 5},则不可能得到{3, 4, 1, 2, 5}这样得出栈序列。(2分) T F 作者: 徐镜春 单位: 浙江大学 1-4 If keys are pushed onto a stack in the order {1, 2, 3, 4, 5}, then it is impossible to obtain the output sequence {3, 4, 1, 2, 5}、(2分) T F 作者: 徐镜春 单位: 浙江大学 1-5 所谓“循环队列”就是指用单向循环链表或者循环数组表示得队列。(1分) T F 作者: DS课程组 单位: 浙江大学 1-6 An algorithm to check for balancing symbols in an expression uses a stack to store the symbols、(1分) T F 2-1 设栈S与队列Q得初始状态均为空,元素a、b、c、d、e、f、g依次进入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队得顺序就是b、d、c、f、e、 a、g,则栈S得容量至少就是: (2分) 1. 1 2. 2 3. 3 4. 4 作者: DS课程组

栈和队列答案

栈和队列 一选择题 1. 对于栈操作数据的原则是（）。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ①B ),在作退栈运算时应先判别栈是否( ②A)。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。 A. 不确定 B. n-i+1 C. i D. n-i 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j 个输出元素是（）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为 p1,p2,p3，…，pN,若pN 是n，则pi 是( )。 A. i B. n-i C. n-i+1 D. 不确定 6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4， 8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2

第3章-栈与队列习题参考答案

习题三参考答案 备注: 红色字体标明的是与书本内容有改动的内容。 一、选择题 1.在栈中存取数据的原则是（ B ）。 A．先进先出 B. 先进后出 C. 后进后出 D. 没有限制 2．若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（ D ）。 A．1234 B. 1324 C. 4321 D. 1423 3．在链栈中，进行出栈操作时（B ）。 A．需要判断栈是否满 B. 需要判断栈是否为空 C. 需要判断栈元素的类型 D. 无需对栈作任何差别 4．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize，则顺序栈的判空条件是（ A ）。 A．top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 5．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（ C ）。 A．top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 6．在队列中存取数据元素的原则是（ A ）。 A．先进先出 B. 先进后出 C. 后进后出 D. 没有限制 7．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判空条件是（A ）。 A．front==rear B. front!=rear C. front==rear+1 D. front==(rear+1)% maxSize 8．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满条件是（D ）。 A．front==rear B. front!=rear C. front==rear+1 D. front==(rear+1)% maxSize 9.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首 和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（C ）。 A．rear-front B. rear-front+1 C. (rear-front+maxSize)%maxSize D. (rear-front+1)%maxSize 10.设长度为n的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度 为（ B ）。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 二、填空题 1.栈是一种操作受限的特殊线性表，其特殊性体现在其插入和删除操作都限制在表尾进行。允许插入和删除 操作的一端称为栈顶，而另一端称为栈底。栈具有后进先出的特点。 2.栈也有两种存储结构，一种是顺序存储，另一种是链式存储；以这两种存储结构存储的栈分别称为顺序 栈和链栈。 3.在顺序栈中，假设栈顶指针top是指向栈顶元素的下一个存储单元，则顺序栈判空的条件是 top==0 ; 栈顶

第三章+栈和队列(参考答案)

第三章栈和队列 一、判断题 1、链栈的初始化是指开辟足够多的结点，然后置栈顶指针为 NULL。（×） 2、递归定义的数据结构通常不需要用递归的算法来实现对它的操作。（×） 二、填空题 1、向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给___栈顶指针_____。 2、迷宫问题是一个回溯控制的问题，最好使用____栈______的方法来解决。 3、有如下递归过程： Void Print(int w) { int i; if (w!=0) { Print(w?1); for (i=1;i<=w;i++) printf(“%3d”,w); printf(“\n”); } } 调用语句print(4)的结果是__________。 1 2 2 3 3 3 4 4 4 4 4、假设用循环单链表实现队列，若队列非空，且队尾指针为R, 则将新结点S加入队列时，需执行下面语句：_ S->next=R->next _________；___ R->next=S _______；R=S； 三、选择题 1、设有4个数据元素a1、a 2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a 3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。 现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A 2，第二次出栈得到的元素是 B 4；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C 1，第二次出队得到的元素是 D 2。经操作后，最后在栈中或队中的元素还有 E 2个。 供选择的答案： A～D：①a1 ②a2 ③ a3 ④a4 E：①1 ②2 ③ 3 ④ 0 2、栈是一种线性表，它的特点是 A 2。设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值 B 2；从栈中弹出（POP）一个元素时，变量T的值 C 1。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D 6，变量T的值是 E 4。 供选择的答案： A：①先进先出②后进先出③进优于出④出优于进⑤随机进出 B，C：①加1 ②减1 ③不变④清⑤加2 ⑥减2 D：① a,b ②b,c ③c,a ④b,a ⑤ c,b ⑥a,c E：① n+1 ②n+2 ③ n ④ n-1 ⑤ n-2 3、在做进栈运算时，应先判别栈是否 A 2；在做退栈运算时，应先判别栈是否 B 1。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 2。

PTA第三章栈和队列练习题教学提纲

1-1 通过对堆栈S 操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。 (2分) T F 作者: DS 课程组 单位: 浙江大学 1-2 在用数组表示的循环队列中，front 值一定小于等于rear 值。 (1分) T F 作者: DS 课程组 单位: 浙江大学 1-3 若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。 (2分) T F 作者: 徐镜春 单位: 浙江大学 1-4 If keys are pushed onto a stack in the order {1, 2, 3, 4, 5}, then it is impossible to obtain the output sequence {3, 4, 1, 2, 5}. (2分) T F 作者: 徐镜春 单位: 浙江大学 1-5 所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。 (1分) T F 作者: DS 课程组 单位: 浙江大学 1-6 An algorithm to check for balancing symbols in an expression uses a stack to store the symbols. (1分) T F 2-1 设栈S 和队列Q 的初始状态均为空，元素a 、b 、c 、d 、e 、f 、g 依次进入栈S 。若每个元素出栈后立即进入队列Q ，且7个元素出队的顺序是b 、d 、c 、f 、e 、a 、g ，则栈S 的容量至少是： (2分)

栈和队列练习题答案

第3章栈和队列练习题答案 一、填空题 1. 线性表、栈和队列都是线性结构，可以在线性表的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。 3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 二、判断正误 （√）1. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（√）2. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （×）3. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （√）4. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （√）5. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （×）6. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （×）7. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题 （B）1.栈中元素的进出原则是 Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出 （C）2.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为 Ａ．i Ｂ．n-i Ｃ．n-i+1 Ｄ．不确定 解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，…，n，则出栈的序列是n，…，3，2，1。 （若不要求顺序出栈，则输出序列不确定） （D）3．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为 （Ａ）r－f; （Ｂ）（n＋f－r）% n; （Ｃ）n＋r－f; （Ｄ）（n＋r－f）% n E：①1 ②2 ③3 ④0 四、阅读理解 1.【严题集3.3②】写出下列程序段的输出结果（栈的元素类型SElem Type为char）。 void main( ){ Stack S; Char x,y; InitStack(S); x=’c’;y=’k’;

第3章栈和队列作业参考答案5页word文档

第三章栈和队列作业 1、若按教材P44页图3.1（b）所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请回答： （1）如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？ （2）如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到？（写出进栈和出栈的栈操作序列）。 123、132、213、231、321 输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。 得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。 2、试证明：若借助栈由输入序列1、2……n得到的输出序列为p1、p2……p n(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着，i〈j〈k使p j

p j的情况，则说明要将p j压到p i之上，也就是在p j出栈之后p i才能出栈。这就说明，对于i

序列。换句话说，对于输入序列1，2，3，不可能出现3，1，2的输出序列。 3、按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿照教科书3.2节3--2的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程： A-B*C/D-E ↑F 4、试编写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列，序列1和序列2中不包含字符‘&’，序列1是序列2的逆序列。例如‘a+b&b+a’是属于该模式的字符序列，而‘a+b&a-b’则不是。 Status Model(){ //识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式 的字符序列,序列1和序列2中不包含字符‘&’，序列1是序列2的逆序列 InitStack(s); c=getchar(); while (c!='&') {Push(s,c); c=getchar();} c=getchar(); while (c!='@'&&!StackEmpty(s)) { Pop(s,x); if (c==x) c=getchar(); else return FALSE; if (c=='@' && StackEmpty(s)) return TRUE; else return FALSE; 5、假设称正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘＠’为结束符的字符序列是否是回文。

第三章栈与队列 练习题

第三章栈与队列练习题 一、选择题 1、栈结构通常采用的两种存储结构是（ A ）。 A、顺序存储结构和链表存储结构 B、散列和索引 C、链表存储结构和数组 D、线性链表和非线性存储 2、设栈ST用顺序存储结构表示，则栈ST为空的条件是（B） 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保存被删除结点的值，则执行（C） 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; 7、一个队列的入列序列是1，2，3，4，则队列的输出序列是（B ）//尾插入元素，头删除元素。 A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 9、循环队列SQ采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列为满的条件是（C）//不懂啊！！！ A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 11、用单链表表示的链式队列的队头在链表的（A）位置 A、链头 B、链尾 C、链中 12、判定一个链队列Q（最多元素为n个）为空的条件是（ A） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 14、在一个链队列Q中，删除一个结点需要执行的指令是（C） 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、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（D） A、仅修改队头指针 B、仅修改队尾指针 C、队头尾指针都要修改 D、队头尾指针都可能要修改。 16、栈和队列的共同点是（C） A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 18、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少应该是（B） A、2 B、 3 C、 5 D、 6 20、设有一顺序栈已经含有3个元素，如图3.1所示元素a4正等待进栈。下列不可能出现的出栈序列是（A） 0 maxsize-1

数据结构及应用算法教程习题第四章 栈和队列

第四章栈和队列 一、选择题 1．对于栈操作数据的原则是（B ）。 A．先进先出B．后进先出C．后进后出D．不分顺序 2．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i （1<=i<=n）个元素是（ B ）。 A．不确定B．n-i+1 C．i D．n-i 3．有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ C ） A．5 4 3 6 1 2 B．4 5 3 1 2 6 C．3 4 6 5 2 1 D．2 3 4 1 5 6 4．设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。 A．1，2，4，3，B．2，1，3，4，C．1，4，3，2，D．4，3，1，2，E．3，2，1，4， 5．某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（）。 A．a，c，b，d B．b, c，d，a C．c, d，b, a D．d, c，a，b 6．设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。 A．XYZ B．YZX C．ZXY D．ZYX 7．输入序列为ABC，可以变为CBA时，经过的栈操作为（B ）A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,pop C．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop 8．若一个栈以向量V[1．．n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( C )。 A．top:=top+1; V [top]:=x B．V [top]:=x; top:=top+1 C．top:=top-1; V [top]:=x D．V [top]:=x; top:=top-1 10．栈在（ D ）中应用。 A．递归调用B．子程序调用C．表达式求值D．A，Ｂ，Ｃ11．一个递归算法必须包括（ B ）。

第三章 栈与队列 习题及答案(优选.)

第三章栈与队列习题及答案 一、基础知识题 3.1 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： (1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)? (2) 能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。 (3)请分析1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 3.2 链栈中为何不设置头结点? 答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。 3.3 循环队列的优点是什么? 如何判别它的空和满? 答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间。每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。 3.4 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢? 答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。 3.5 指出下述程序段的功能是什么? (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); }