dequeue是什么意思ueue在线翻译读音例句

精品文档

2016

1/21

第三章,栈和队列,练习题

一、选择题

1、栈结构通常采用的两种存储结构是。

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

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

2、设栈ST用顺序存储结构表示，则栈ST为空的条件

是

A、0B、==0C、

、==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;

7、一个队列的入列序列是1，2，3，4，则队列的输

出序列是//尾插入元素，头删除元素。

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

精品文档

2016

2/21

4，1

9、循环队列SQ采用数组空间[0,n-1]存放其

元素值，已知其头尾指针分别是front和rear，则判定此循

环队列为满的条件是//不懂啊！！！

A、==、!=、

==%nD、!=%n

11、用单链表表示的链式队列的队头在链表的位置

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

12、判定一个链队列Q为空的条件是

A、==、!=、

==%nD、!=%n

14、在一个链队列Q中，删除一个结点需要执行的指

令是

A、=->next;B、

->next=->next->next;C、

->next=->next->next;D、

=->next;

15、用不带头结点的单链表存储队列，其队头指针指

向队头结点，队尾指针指向队尾结点，则在进行出队操作时

A、仅修改队头指针B、仅修改队尾指针C、队头尾指

针都要修改D、队头尾指针都可能要晏殊《蝶恋花》昨夜西风凋碧树 修改。

16、栈和队列的共同点是

精品文档

2016

3/21

A、都是先进后出B、都是先进先出C、只允许在端点

处插入和删除元素D、没有共同点

18、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次

进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则

栈的容量至少应该是

A、B、C、D、

20、设有一顺序栈已经含有3个元素，如图3.1所示

元素a4正等待进栈。下列不可能出现的出栈序列是

0maxsize-1

A、a3,a1,a4,aB、a3,a2,a4,a1C、a3,a4,a2,a1D、

a4,a3,a2,a1

图3.1二、判断题

1、在顺序栈栈满情况下，不能做进栈运算，否则会产

生“上溢”。T

2、链栈与顺序栈相比的一个优点是链栈插入和删除操

作更加方便。T

3、若一个栈的输入序列为1，2，3，?，n，其输出序

列的第一个元素为n，则其输出序列的每个元素ai一定满足

ai=i+1。F

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

F

5、在对链队列做出队操作时，不会改变front指针的

精品文档

2016

4/21

值。F

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

7、一个栈的输入序列是1,2,3,4，则在栈的输出序列

中可以得到4,3,1,2。F,有5种情况

8、一个栈的输入序

列是1,2,3,4，则在栈的输出序列中可以得到1,2,3,4。T

9、若以链表作为栈的存储结构，则进栈需要判断栈

是否满。F

10、若以链表作为栈的存储结构，则出栈需要判断栈

是否空。T

三、填空题

1、栈的特点是，队列的特点是。

2、线性表、栈、队列都是结构，可以在线性表的位置

插入和删除元素；对于栈只能在插入和删除元素；对于队列

只能在插入元素和在位置删除元素。

3、有程序如下，则此程序的输出结果是。//不懂！！！

Voidmain

{stacks;charx,y;initstack;x=’c’;y=’k’;

push;push;push;

pop;push;push;pop;push;

while){pop;printf;}

printf;}

精品文档

2016

5/21

4、在栈顶指针为HS的链栈中，判定栈空的条件是。

5、向栈中压入元素的操作是先后。6、对栈进行退栈

操作是先后。

7、用循环链表表示的队列长度为n，若只设头指针，

则出队和入队的时间复杂度分别是和；若只设尾指针，则出

队和入队的时间复杂度分别是和。

8、从循环队列中删除一个元素时，其操作是。

12、设栈S和队列Q的出始状态为空，元素a,b,c,d,e,f

依次通过栈S，一个元素出栈后即进入队列Q。若这6个元

素出队列的顺序是b,d,c,f,e,a则栈S的容量至少应该是。

13、有程序如下，则此程序的输出结果是。

Voidmain

{charx=’e’,y=’c’;

enqueue;enqueue;enqueue;dequeue;enqueue;degueue;

enqueue;

while){dequeue;printf;}

printf;}

四、简答题

1、对于堆栈，给出三个输入项A，B，C，如果输入

项序列为ABC，试给出全部可能的输出序列，并写出每种序

列对应的操作。例如：A进B进C进C出B出A出，产生践的组词 的

精品文档

2016

6/21

序列为CBA。

2、简述以下算法的功能。

statu英语诗歌朗诵著名诗歌 salgo1

{int

I,n,a[255];n=0;while){n++;pop;}

forpush;}

statusalgo2

{stackt;int

d;initstack;while){pop;ifpu

sh;}

while){pop;push;}}

3、内存中一片连续空间提供给两个栈s1和s2使用，

怎样分配这部分存储空间，使得对任一栈仅当这部分空间全

满时才发生溢出。

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

第三章栈和队列1、什么叫堆栈？什么叫队列？、线

性表、堆栈和队列这三种抽象数据类型有什么相同之处和不

精品文档

2016

7/21

同之处？、在顺序队列中，什么叫真溢出？什么叫假溢出？

为什么顺序队列通常都采用顺序循环队列结构？、什么叫

优先级队列？优先级队列和队列有什么相同之处和不同之

处？.什么是递归程序？递归程序的优、缺点是什么？递

归程序在执行时，应借助于什么来完成？递归程序的入口

语句、出口语句一般用什么语句实现？、设有个数据元素

a1、a2、a和a4，对他们分别进行栈操作或队操作。在进

栈或进队操作时，按a1、a2、a3、a次序每次进入一个元素。

假设栈或队的初始状态都是空。现要进行的栈操作是进栈

两次，出栈一次，再进栈两次，出栈一次；这时，第一次

出栈得到的元素是A，第二次出栈得到的元素是B；类似

地，考虑对这四个数据元素进行的队操作是进队两次，出队

一次，再进队两次，出队一次；这时，第一次出队得到的

元素是C，第二次出队得到的元素E个。是D。经操作

后，最后在栈中或队中的元素还有供选择的答案：A～D：

①a1②a2E：①1②③④0③a3④a47、栈是一种线性

表，它的特点是A。设用一维数组A[1,…,n]来表示一个

栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]

为栈顶元素。往栈中推入一个新元素时，变量T的值B变

量T的值C；从栈中弹出一个元素时，。设栈空时，有输

入序列a，b，c，经过PUSH，POP，PUSH，，变量T的值

是E。PUSH，POP操作后，从栈中弹出的元素的序列是D

精品文档

2016

8/21

供选择的答案：A：①先进先出②后进先出③进优于出④

出优于进⑤随机进出B，C：①加1②减1③不变④清

⑤加⑥减

D：①a,bE：①n+1②b,c②n+2③c,a④b,a⑤c,b

③n④n-1⑤n-2⑥a,c8、在做进栈运算时，应先判别

栈是否A；在做退栈运算时，应先判别栈是否B。当栈

中元素为n个，做进栈运算时发生上溢，则说明该栈的最

大容量为C。为了增加内存空间的利用率和减少溢出的可

能性，由两个栈共享一片连续的内存空间时，应将两栈的

D当E时，才产生上溢。分别设在这唐代诗人 片内存空间的两端，

这样，只有供选择的答案：A，B：①空C：①n-1②满②

n②深度③上溢③n+1③栈顶④下溢④n/④栈底

D：①长度E：①两个栈的栈顶同时到达栈空间的中心点

②其中一个栈的栈顶到达栈空间的中心点③两个栈的栈顶

在达栈空间的某一位置相遇④两个栈均不空，且一个栈的

栈顶到达另一个栈的栈底、写出下列中缀表达式的后缀形

式：A*B*C-A+B-C+DA*-B+C*D+

E/+C10、写出下列程序段的输出结果。void

main{StackS;charx,y;InitStack;x=’c’;y=’k’;

Push;Push;Push;

}11、写出下列程序段的输出结果：。void

main{QueueQ;InitQueue;charx=’e’;y=’c’;EnQueue;

精品文档

2016

9/21

EnQueue;EnQueue;DeQueue;EnQueue;DeQueue;

EnQueue;while){DeQueue;printf;};printf;}12、

简述以下算法的功能。voidalgo3{StackS;intd;

InitStack;while){DeQueue;Push;};while){Pop;

EnQueue;}}13、有个元素，其入栈次序为：A，B，C，

D，E，在各种可能的出栈次序中，以元素C，D最先出栈

的次序有哪几个？14、假设以S和X分别表示入栈和出

栈操作，则对初态和终态均为空的栈操作可由S和X组

成的序列表示。试指出判别给定序列是否合法的一般规

则。两个不同合法序列能否得到相同的输出元素序列？如

能得到，请举列说明。15、编写一个从栈建立队列的伪码

算法StacktoQueue，队列建成后，队列的头为栈顶,队列

的尾为栈底,算法结束后，栈为

空。与栈有关的操作为：popStackemptyStack

pushStackStackTop元素出栈栈空元素进栈取栈顶与队

列有关的操作为：enqueuedequeuefullqueue入队出队

队列满16、假设带头结点的循环链表表示对列，并且只设一

个指针指向队尾元素结点，试编写相应的队列初始化、入

队列和出队列的算法。17、设顺序双向循环队列的数据结

构定义为：typedefstruct{DataTypelist[MaxSize];int

front;/*队头指针*/intrear;/*队尾指针*/}

BSeqCQueue;设Q为BSeqCQueue类型的变参，并设初始

精品文档

2016

10/21

化操作时有：Q->rear=Q->front=0，现要求：给出

顺序双向循环队列满和空的条件。给出顺序双向循环队列

的入队列操作和出队列操作算法思想。18、假设称正读和

反读都相同的字符序列为“回文”，例如‘abba’和‘abcba’

是回文，‘abcde’和‘ababab’则不是回文，试写一

个算法判别读入的一个似‘@’为结束符的字符序列是否

是“回文”。

第三章栈和队列习题答案

一、基础知识题

3.1设将整数1，2，3，4依次进栈，但只要出栈时栈

非空，则可将出栈操作按任何次序夹入其中，请回答下述问

题：

若入、出栈次序为Push,Pop,Push,Push,Pop,

Pop,Push,Pop,则出栈的数字序列为何表示i进栈，Pop表

示出栈)?

能否得到出栈序列1423和1432?并说明为什么不能得

到或者如何得到。

请分析1，，，的24种排列中，哪些序列是可以通过相

应的入出栈操作得到的。答：出栈序列为：1324

不能得到1423序列。因为要得到14的出栈序列，则

应做Push,Pop,Push,Push,Push,Pop。这样，3在栈顶，2

在栈底，所以不能得到23的出栈序列。能得到1432的出栈

精品文档

2016

11/21

序列。具体操作为：Push,

Pop,Push,Push,Push,Pop,Pop,Pop。

在1，，，的24种排列中，可通过相应入出栈操作得到

的序列是：

1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3

214,3241,3421,4321

不能得到的序列是：

1423,2413,3124,3142,3412,4123,4132,4213,4231,4312

3.链栈中为何不设置头结点?

答：链栈不需要在头部附加头结点，因为栈都是在头

部进行操作的，如果加了头结点，等于要对头结点之后的结

点进行操作，反而使算法更复杂，所以只要有链表的头指针

就可以了。

3.循环队列的优点是什么?如何判别它的空和满?

答：循环队列的优点是：它可以克服顺序队列的”假

上溢”现象，能够使存储队列的向量空间得到充分的利用。

判别循环队列的”空”或”满”不能以头尾指针是否相等

来确定，一般是通过以下几种方法：一是另设一布尔变量来

区别队列的空和满。二是少用一个元素的空间,每次入队前

测试入队后头尾指针是否会重合，如果会重合就认为队列已

精品文档

2016

12/21

满。三是设置一计数器记录队列中元素总数，不仅可判别空

或满，还可以得到队列中元素的个数。

3.设长度为n的链队用单循环链表表示，若设头指针，

则入队出队操作的时间为何?若只设尾指针呢?

答：当只设头指针时，出队的时间为1，而入队的时

间需要n，因为每次入队均需从头指针开始查找，找到最后

一个元素时方可进行入队操作。若只设尾指针，则出入队时

间均为1。因为是循环链表，尾指针所指的下一个元素就是

头指针所指元素，所以出队时不需要遍历整个队列。

3.指出下述程序段的功能是什么?

voidDemo1{

inti;arr[64];n=0;

while)arr[n++]=Pop;

forPush;

}//Demo1

SeqStackS1,S2,tmp;

DataTypex;

...//假设栈tmp和S2已做过初始化

while)

{x=Pop;

Push;

}

精品文档

2016

13/21

while)

{x=Pop;

Push;

Push;

}

voidDemo2

{//设DataType为int型

SeqStackT;inti;

InitStack;

while)

if)!=m)Push;

while)

{

i=Pop;Push;

}

}

voidDemo3

{//设DataType为int型

intx;SeqStackS;

InitStack;

while)

{x=DeQueue;Push;}

精品文档

2016

14/21

while)

{x=Pop;EnQueue;}

}//Demo3

CirQueueQ1,Q2;//设DataType为int型

intx,i,n=0;

...//设Q1已有内容，Q2已初始化过

while)

{x=DeQueue;EnQueue;n++;}

for

{x=DeQueue;

EnQueue;EnQueue;}

答：

程序段的功能是将一栈中的元素按反序重新排列，也

就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此

栈中元素个数限制在64个以内。

程序段的功能是利用tmp栈将一个非空栈s1的所有元

素按原样复制到一个栈s2当中去。

程序段的功能是利用栈T，将一个非空栈S中值等于m

的元素全部删去。

程序段的功能是将一个循环队列Q经过S栈的处理，

反向排列，原来的队头变成队尾，原来的队尾变成队头。

这段程序的功能是将队列1的所有元素复制到队列2

精品文档

2016

15/21

中去，但其执行过程是先把队列1的元素全部出队，进入队

列2，然后再把队列2的元素复制到队列1中。

二、算法设计题

3.回文是指正读反读均相同的字符序列，如”abba”

和”abdba”均是回文，但”good”不是回文。试写一个算

法判定给定的字符向量是否为回文。

解：根据提示，算法可设计为：

//以下为顺序栈的存储结构定义

#defineStackSize100//假定预分配的栈空间最多

为100个元素

typedefcharDataType;//假定栈元素的数据类型为

字符

typedefstruct{

DataTypedata[StackSize];

inttop;

}SeqStack;

intIsHuiwen

{//判断t字符向量是否为回文，若是，返回1，否则

返回0

SeqStacks;

inti,len;

chartemp;

精品文档

2016

16/21

InitStack;

len=strlen;//求向量长度

for//将一半字符入栈

Push;

while)

{//每弹出一个字问渠那得清如许 为有源头活水来 符与相应字符比较

temp=Pop;

ifreturn0;//不等则返回0

elsei++;

}

return1;//比较完毕均相等则返回1

}

3.利用栈的基本操作，写一个将栈S中所有结点均删

去的算法voidClearStack，并说明S为何要作为指针参数?

解：算法如下

voidClearStack

{//删除栈中所有结点

S->Top=-1;//其实只是将栈置空

}

因为要置空的是栈S，如果不用指针来做参数传递，

那么函数进行的操作不能对原来的栈产生影响，系统将会在

内存中开辟另外的单元来对形参进行函数操作。结果等于什

精品文档

2016

17/21

么也没有做。所以想要把函数操作的结果返回给实参的话，

就只能用指针来做参数传递了。

3.利用栈的基本操作10个历史故事简短 ，写一个返回S中结点个数的算

法intStackSize,并说明S为何不作为指针参数?

解：算法如下：

intStackSize

{//计算栈中结点个数

intn=0;

if)

{

Pop;

n++;

}

returnn;

}

上述算法的目的只要得到S栈的结点个数就可以了。

并不能改变栈的结构。所以S不用指针做参数，以避免对原

来的栈中元素进行任何改变。系统会把原来的栈按值传递给

形参，函数只对形参进行操作，最后返回元素个数。

3.设计算法判断一个算术表达式的圆括号是否正确配

对。‘就退掉栈顶的’

{//检查表达式ST中括号是否配对

精品文档

2016

18/21

inti;

SeqStackS;//定义一个栈

InitStack;

for;i++)

{

ifPush;//遇’’)//遇’)’

if)//栈不为空时，将栈顶元素出栈

Pop;

elsereturn0;//不匹配，返回0

}

ifEmptyStackreturn1;//匹配，返回1

elsereturn0;//不匹配，返回0

}

3.10一个双向栈S是在同一向量空间内实现的两个

栈，它们的栈底分别设在向量空间的两端。试为此双向栈

设计初始化InitStack、入栈Push和出栈Pop等算法，其

中i为0或1，用以表示栈号。

解：双向栈其实和单向栈原理相同，只是在一个向量

空间内，好比是两个头对头的栈放在一起，中间的空间可以

充分利用。双向栈的算法设计如下：

//双向栈的栈结构类型与以前定义略有不同

#defineStackSize100//假定分配了100个元素的

精品文档

2016

19/21

向量空间

#definecharDataType

typedefstruct{

DataTypeData[StackSize]

inttop0;//需设两个指针

inttop1;

}DblStack

voidInitStack

{//初始化双向栈

S->top0=-1;

S->top1=StackSize;//这里的top2也指出了向量

空间，但由于是作为栈底，因此不会出错}

intEmptyStack

{//判栈空

return;

}

intFullStack

{//判栈满,满时肯定两头相遇

return;

}

voidPush

{//进栈

精品文档

2016

20/21

if)

Error;//上溢、退出运行

ifS->Data[++S->top0]=x;//栈0入栈

ifS->Data[--S->top1]=x;//栈1入栈

}

DataTypePop

{//出栈

if)

Error;//下溢退出

if

return;//返回栈顶元素，指针值减1

if

return;//因为这个栈是以另一端为底的，所以指针

值加1。}

3.11Ackerman函数定义如下：请写出递归算法。

┌n+1当m=0时

AKM=│AKM当m≠0，n=0时

└AKM)当m≠0,n≠0时

解：算法如下

intAKM

{

ifreturnn+1;

精品文档

2016

21/21

ifreturnAKM;

ifreturnAKM);

}

3.1用第二种方法，即少用一个元素空间的方法来区

别循环队列的队空和队满，试为其设计置空队，判队空，判

队满、出队、入队及取队头元素等六个基本操作的算法。

解：算法设计如下:

//循环队列的定义