第3章 桟和队列

第3章桟和队列

3.1 选择题

1．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1≤i≤n）个元素是（）A）不确定 B）n-i+1 C）i D）n-i

【答案】B

【解析】根据栈的性质（LIFO），若输出的第一个元素是n，则表明所有的元素已经入栈，则出栈顺序为n，n-1，…，3，2，1。

2．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是（）A）6 B）4 C）3 D）2

【答案】C

【解析】根据栈的性质（LIFO）得，e2出栈前，栈中存有e1和e2两个元素，e4出栈前，栈中存有e1、e3和e4三个元素，e4和e3出栈以后，e5和e6入栈，栈中同样存在e1、e5和e6三个元素，然后三个元素依次出栈，所以栈的容量至少应该为3。

3．若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是（）

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

【答案】C

【解析】栈式运算受限的线性表，只允许在栈顶进行插入和删除操作。本题中栈顶指针为n+1，该数组将栈顶放在了下标大的一端，所以在进行入栈操作时top指针应该进行减一操作。通常元素进栈的操作为：先移动栈顶指针后存入元素。

4．如果我们用数组A[1..100]来实现一个大小为100的栈，并且用变量top来指示栈顶，top的初值为0，表示栈空。请问在top为100时，再进行入栈操作，会产生（）

A）正常动作 B）溢出 C）下溢 D）同步

【答案】B

【解析】当top为100时，表示栈已经满了，此时再进行入栈操作，则会造成溢出。

5．栈在（）中应用。

A）递归调用 B）子程序调用 C）表达式求值 D）A，Ｂ，Ｃ

【答案】D

7．用链接方式存储的队列，在进行删除运算时（）

A）仅修改头指针 B）仅修改尾指针

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

【答案】D

【解析】若队列中的元素多于一个，删除队列中的队尾元素，只需修改队尾指针；若队列中只有一个元素，删除该元素后，队头队尾指针都需要修改。

8．循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )

A）(rear-front+m)%m B）rear-front+1

C）rear-front-1 D）rear-front

【答案】A

【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的求元素个数的运算可以利用求模运算。

9．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )

A）1和 5 B）2和4 C）4和2 D）5和1

【答案】B

【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的加1运算通常用求模运算来实现。所以入队和出队时的操作分别为：rear=(rear+1)%m，front=(front+1)%m。10．栈和队列的共同点是（）

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

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

【答案】C

【解析】栈和队列都是运算受限的线性表，只允许在表端点处进行操作。

11．在一个链队列中，假定front和rear分别为队头和队尾指针，则插入*s结点的操作为（）A）front->next=s;front=s; B）s->next=rear;rear=s;

C）rear->next=s;rear=s; D）s->next=front;front=s;

【答案】C

【解析】队列是运算受限的线性表（FIFO），插入元素只能插在队尾，所以需修改队尾指针。

12．判定一个栈S（元素个数最多为MAXSIZE）为空和满的条件分别为（）

A）S->top!=-1 S->top!=MAXSIZE-1

B）S->top=-1 S->top=MAXSIZE-1

C）S->top=-1 S->top!=MAXSIZE-1

D）S->top!=-1 S->top=MAXSIZE-1

【答案】B

3.2 填空题

1．栈是_____________的线性表，其运算遵循_____________的原则。

【答案】（1）操作受限（或限定仅在表尾进行插入和删除操作）（2）后进先出

2．设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过

PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_____________，而栈顶指针值是

_____________H。设栈为顺序栈，每个元素占4个字节。

【答案】（1）23 （2）100CH

【解析】PUSH为入栈操作，POP为出栈操作。根据栈的性质，经过PUSH,PUSH,POP运算之后，栈中存在元素1，输出数据为2，然后经过PUSH,POP，3入栈，3出栈，然后经过PUSH,PUSH之后4，5入栈，此时出栈序列为2，3，栈中元素为1，4，5；每个元素占4个字节，所以栈顶指针的值为1000H+3*4=100CH （十六进制数）

3．循环队列的引入，目的是为了克服_____________。

【答案】假溢出时大量移动数据元素。

4．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_____________。【答案】先进先出

5．已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_____________。

【答案】

s=(LinkList)malloc(sizeof(LNode));

s->data=x;

s->next=r->next;

r->next=s;

r=s;

【解析】根据队列的性质，新插入的元素永远插在队尾。

8．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是：M=_____________。

【答案】(M+1)% N；

【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的加1运算通常用求模运算来实现。

9．当两个栈共享一存储区时，栈利用一维数组stack[1..n]表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为_____________，栈2空时，top[2]为_____________，栈满时为_____________。【答案】（1）0 （2）n+1 （3）top[1]+1=top[2]

【解析】为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的栈顶分别设在这片内存空间的两端,这样,当两个栈的栈顶在栈空间的某一位置相遇时，才产生上溢，即top[1[+1=top[2]。

10．在作进栈运算时应先判别栈是否_____________；在作退栈运算时应先判别栈是否

_____________；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_____________。

为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的

_____________分别设在内存空间的两端，这样只有当______________时才产生溢出。

【答案】（1）满（2）空（3）n （4）栈底（5）两栈顶指针相邻

13．无论对于顺序存储还是链式存储的栈和队列来说，进行插入和删除运算的时间复杂度均相同为

_____________。

【答案】O(1)

【解析】对于栈用栈顶指针表示栈顶，而栈的插入和删除操作均在栈顶进行。对于队列用队头和队尾指针分别表示允许插入和删除的一端。

14．在顺序队列中，当尾指针等于数组的上界，即使队列不满，再作入队操作也会产生溢出，这种现象称为_____________。

【答案】假溢出

【解析】产生该现象的原因是，被删元素空间在该元素被删除后就永远得不到使用。为了克服这种现象，采用循环队列来实现。

3.5 程序设计题

1．设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。)

【算法分析】判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配。

【算法源代码】

int EXYX (char E[]){

/*E[]存放字符串表达式，以‘#’结束*/

char s[30]; /*s是一维数组，容量足够大，用作存放括号的栈*/

int top=0,i; /*top用作栈顶指针*/

s[top]='#'; /*‘#’先入栈，用于和表达式结束符号‘#’匹配*/

i=0; /*字符数组E的工作指针*/

while(E[i]!='#') /*逐字符处理字符表达式的数组*/

switch (E[i])

{case '(': s[++top]= '('; i++ ; break ;

case ')': if(s[top]=='('){top--; i++; break;}

else{printf("括号不配对");exit(0);}

case '#': if(s[top]=='#'){printf("括号配对\n");return (1);}

else {printf(" 括号不配对\n");return (0);} /*括号不配对*/

default : i++; /*读入其它字符，不作处理*/

}

}/*算法结束*/

2．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列和出队列算法。

【算法分析】

根据队列的先进先出的性质，队列的入队操作在队尾进行，出队操作在队头进行。而题目所采用的数据结构是只设一个尾指针的循环链表。我们可以根据循环链表的特点找到头指针。

【算法源代码1】

void EnQueue (LinkList rear, ElemType x)

/* rear是带头结点的循环链队列的尾指针，本算法将元素x插入到队尾*/

{ s=(LinkList)malloc(sizeof(LNode)); /*申请结点空间*/

s->data=x; s->next=rear->next; /*将s结点链入队尾*/

rear->next=s; rear=s; /*rear指向新队尾*/

}

【算法源代码2】

void DeQueue (LinkList rear)

/* rear是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队头元素；否则给出出错信息*/

{ if(rear->next==rear) {printf("队空\n"); exit(0);}

s=rear->next->next; /*s指向队头元素*/

rear->next->next=s->next; /*队头元素出队*/

printf ("出队元素是:%d",s->data);

if(s==rear) rear=rear->next; /*空队列*/

free(s);

}

3．设整数序列a1，a2，…，an，给出求解最大值的递归程序。

【算法分析】根据题意，本题的函数定义为：

a[1] n=1

maxvalue(a,n)= a[n] a[n]>maxvalue(a,n-1)

maxvalue(a,n-1) a[n]

【算法源代码】

int MaxValue (int a[],int n)

/*设整数序列存于数组a中，共有n个，本算法求解其最大值*/

{int max;

if (n==1) max=a[1];

else if (a[n]>MaxValue(a,n-1)) max=a[n];

else max=MaxValue(a,n-1);

return(max);

}

4．试将下列递归函数改写为非递归函数。

void test(int *sum)

{

int x;

scanf("%d",&x);

if(x==0) *sum=0 ;

else {test(&sum); (*sum)+=x;}

printf("%5d",*sum);

}

【算法分析】

该函数是以读入数据的顺序为相反顺序进行累加问题，可将读入数据放入栈中，等输入结束时，将栈中数据退出进行累加。累加的初值为0。

【算法源代码】

int test()

{

int x,sum=0,top=0,s[30];

scanf("%d",&x);

while (x!=0)

{s[++top]=a; scanf("%d",&x); }

printf("%5d",sum);

while (top)

{sum+=s[top--]; printf("%5d",sum); }

}

5．编写一个算法，利用栈的基本运算将指定栈中的内容进行逆转。

【算法分析】

利用两个临时栈s1和s2。先将s栈中的内容移到s1栈中，再将s1栈中的内容移到s2栈中，最后将s2栈中的内容移到s栈中，即可实现。

【算法源代码】

reverse(SqStack *s)

{SqStack *s1,*s2; /*s,s1,s2均为栈类型

ElemType x; /*栈中元素的类型，用于存储从栈中取出元素的临时变量*/ initstack(s1); /*栈的初始化*/

initstack(s2);

while(!stackempty(s)) /*如果栈不空，将s栈中的内容移到s1栈中*/ {pop(s,x); /*取栈顶元素放入变量x中*/

push(s1,x); /*将变量x入栈*/

}

while(!stackempty(s1)) /*如果栈不空，将s1栈中的内容移到s2栈中*/ {pop(s1,x);

push(s2,x);

}

while(!stackempty(s2)) /*如果栈不空，将s2栈中的内容移到s栈中*/ {pop(s2,x);

push(s,x);

}

}

数据结构习题集：第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; 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;

《数据结构及其应用》笔记含答案 第三章_栈和队列

第3章栈和队列 一、填空题 1、栈是限定仅在表尾进行插入或删除操作的线性表。 2、栈的修改是按照后进先出的原则进行的。 3、队是一种先进先出的线性表。 4、把队列头尾相接的顺序存储结构称为循环队列。 5、队列也是一种操作受限的线性表，允许插入的一端叫做__队尾___，允许删除的一端叫做__队头__。 二、判断题 1、栈和队列的存储，既可以采用顺序存储结构，又可以采用链式存储结构。（√） 2、任何一个递归过程都可以转换成非递归过程。（√） 3、若输入序列为1,2,3,4,5,6，则通过一个栈可以输出序列3,2,5,6,4,1。（√） 4、通常使用队列来处理函数的调用。（╳） 5、循环队列通常用指针来实现队列的头尾相接。（╳） 三、单项选择题 1、若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（C）种情况。 A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1 解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。 2、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（C）。 A．i B．n-i C．n-i+1 D．不确定 解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。3、数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（D）。 A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n 解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。 4、链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（A）。 A．x=top->data;top=top->link；B．top=top->link;x=top->link； C．x=top;top=top->link；D．x=top->link； 解释：x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶下一结点，即摘除栈顶结点。 5、设有一个递归算法如下 int fact(int n) { //n大于等于0 if(n<=0) return 1; else return n*fact(n-1); } 则计算fact(n)需要调用该函数的次数为（A ）。

《数据结构》习题汇编03第三章栈和队列试题

第三章栈和队列试题 一、单项选择题 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.递归 5.队列、队尾、队头 6.顺序队 7.循环队 8.队满 9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵 二、填空题： 1.栈修改的原则是_________或称________，因此，栈又称为________线性表。在栈顶 进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________ 或________。 2.栈的基本运算至少应包括________、________、________、________、________五 种。 3.对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。 4.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。 5.一般地，栈和线性表类似有两种实现方法，即________实现和________实现。 6.top=0表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1 表示________，此时作进栈运算，则产生“________”。 7.以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。 int InitStack(SqStackTp *sq) { ________; return(1);} 8.以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。 Int Push(SqStackTp *sq,DataType x) { if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);} else{________________: ________________=x; return(1);} } 9.以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。 Int Pop(SqStackTp *sq,DataType *x) {if(sp->top==0){error(“下溢”);return(0);} else{*x=________________; ________________; return(1);} } 10. 以下运算实现在顺序栈上判栈空，请在________________处用适当句子予以填充。 Int EmptyStack(SqStackTp *sq) {if(________________) return(1); else return(0); } 11.以下运算实现在顺序栈上取栈顶元素，请在________________处用适当句子予以填充。 Int GetTop(SqStackTp *sq,DataType *x) {if(________________) return(0);

第3章++栈和队列+课后习题答案

第3章栈和队列 习题 1．选择题 （1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。 A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1 （2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。 A．i B．n-i C．n-i+1 D．不确定（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。 A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n （4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。 A．x=top->data;top=top->link；B．top=top->link;x=top->link； C．x=top;top=top->link；D．x=top->link； （5）设有一个递归算法如下 int fact(int n) { //n大于等于0 if(n<=0) return 1; else return n*fact(n-1); } 则计算fact(n)需要调用该函数的次数为（）。 A． n+1 B． n-1 C．n D．n+2 （6）栈在（）中有所应用。 A．递归调用B．函数调用C．表达式求值D．前三个选项都有（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。 A．队列 B．栈C．线性表D．有序表（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。 A．2 B．3 C．4 D．6（9）在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top作为栈顶指针，则当作进栈处理时，top的变化为（）。 A．top不变B．top=0 C．top-- D．top++（10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。 A．线性表的顺序存储结构 B．队列 C. 线性表的链式存储结构 D. 栈

第3章 栈和队列

第三章栈和队列 基本概念 1、栈的定义、特点 2、顺序栈和链栈的进栈和退栈操作；栈空和栈满的判定条件 3、队列的定义和特点 4、循环队列、链队列的出队和入队操作、判定队列为空、队列为满的条件 一、选择题 1、一个栈的输入序列为：a，b，c，d，e，则栈的不可能输出的序列是（）。 A. a,b,c,d,e B. d,e,c,b,a C. d,c,e,a,b D. e,d,c,b,a 2、判断一个循环队列Q（最多n个元素）为满的条件是（）。 A. Q->rear==Q->front B. Q->rear==Q->front+1 C. Q->front==(Q->rear+1)%n D. Q->front==(Q->rear-1)%n 3、设计一个判别表达式中括号是否配对的算法，采用（）数据结构最佳。 A. 顺序表 B. 链表 C. 队列 D. 栈 4、带头结点的单链表head为空的判定条件是（）。 A. head==NULL B. head->next==NULL C. head->next!=NULL D. head!=NULL 5、一个栈的输入序列为：1,2,3,4，则栈的不可能输出的序列是（）。 A. 1243 B. 2134 C. 1432 D. 4312 E. 3214 6、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0，3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。 A. 1和5 B. 2和4 C. 4和2 D. 5和1 大小为6的数组：下标从0-5;从前面出队，从后面入队 front(前面)=3 rear(后面)=0 当出队列中删除一个元素，也就是出队，即front+1:=4 再插入两个元素，即rear+2= 2 7、队列的插入操作是在（）。 A. 队尾 B. 队头 C. 队列任意位置 D. 队头元素后 8、循环队列的队头和队尾指针分别为front和rear，则判断循环队列为空的条件是（）。 A. front==rear B. front==0 C. rear==0 D. front=rear+1 9、一个顺序栈S，其栈顶指针为top，则将元素e入栈的操作是（）。 A. *S->top=e;S->top++; B. S->top++;*S->top=e;

栈和队列答案

第3章栈和队列答案 一、填空题 1. 向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。 3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性 表。 4. 在具有n个单元的循环队列中，队满时共有 n-1 个元素。 5. 带表头结点的空循环双向链表的长度等于0。 解：Array 二、判断正误 （×）1. 在表结构中最常用的是线性表，栈和队列不太常用。 错，不一定吧调用子程序或函数常用，CPU中也用队列。 （√）2. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）3. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同 而已。 （×）4. 栈和链表是两种不同的数据结构。 错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同 类项。 （×）5. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不 同而已。 （√）6. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （√）7. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个 栈的栈底分别设在这片内存空间的两端。 （×）8. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （×）9. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题 （ B）1. 栈中元素的进出原则是 Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出 （C）2. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为 Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定

第3章习题答案

习题3 1.名词解释：栈、队列、循环队列。 解：栈是只能在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出表。 队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最后插入的元素最先删除，故栈也称先进先出表。最先入队的元素最先删除，故队列也称先进先出表。 用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入，队头删除），容易造成“假溢出”现象，即队尾已达到一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储空间”的方法解决“队满”和“队空”的判定问题。 2.如果输入序列为1，2，3，4，5，6，试问能否通过栈结构得到以下两个序列：4，3，5，6，1，2和1，3，5，4，2，6；请说明为什么不能或如何才能得到。 解：输入序列为1，2，3，4，5，6，不能得到4，3，5，6，1，2，其理由是：输出序列最后两个元素是1，2，前面四个元素（4，3，5，6）得到后，栈中元素剩下1，2，且2在栈顶，栈底元素1不可能在栈顶元素2出栈之前出栈。 得到序列1，3，5，4，2，6的过程是：1入栈并出栈；然后2和3依次入栈，3出栈，部分输出序列是1，3；紧接着4和5入栈，5，4和2依次出栈，此时输出序列为1，3，5，4，2；最后6入栈并出栈，得到最终结果序列是1，3，5，4，2，6。 3.试证明：若借助栈由输入序列1，2，…，n 得到序列1p ，2p ，…，n p (它是输入序列的一个全排列)，则在输出序列中不可能出现下列情形：存在着i j p 的情况，则说明要将j p 压到i p 之上，也就是在j p 出栈之后i p 才能出栈。这说明，对于i

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

第三章,栈和队列,练习题 一、选择题 1、栈结构通常采用的两种存储结构是。 A、顺序存储结构和链表存储结构 B、散列和索引 C、链表存储结构和数组 D、线性链表和非线性存储 2、设栈ST用顺序存储结构表示，则栈ST为空的条件是 A、ST.top-ST.base0 B、ST.top-ST.base==0 C、ST.top-ST.basen 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; 7、一个队列的入列序列是1，2，3，4，则队列的输出序列是//尾插入元素，头删除元素。 A、4，3，2，1 B、1，2，3， C、1，4，3， D、3，2，

4，1 9、循环队列SQ采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列为满的条件是//不懂啊！！！ A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==%n D、Q.front!=%n 11、用单链表表示的链式队列的队头在链表的位置 A、链头 B、链尾 C、链中 12、判定一个链队列Q为空的条件是 A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==%n D、Q.front!=%n 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、栈和队列的共同点是

数据结构第3章栈和队列

第3章栈和队列 一选择题 1. 对于栈操作数据的原则是（）。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元 素是（）。 A. 不确定 B. n-i+1 C. i D. n-i 3. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是 （）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 4. 有六个元素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 5．设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 6．输入序列为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 7．若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是 ( )。 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 8．若栈采用顺序存储方式存储，现两栈共享空间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] 9．栈在（）中应用。 A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ 10. 一个递归算法必须包括（）。 A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分 11.. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。 A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈 12. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针 可能都要修改 13. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中 的元素个数为（）。 A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m 14. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。 A. (rear+1) MOD n=front B. rear=front C．rear+1=front D. (rear-l) MOD n=front 15. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个 元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少

第三部分 栈 队列 带答案

第三部分栈队列 一、选择题 1．( A )又称为FIFO表。 A.队列 B.散列表 C.栈 D.哈希表 2．设依次进入一个栈的元素序列为c,a,b,d,不可得到出栈的元素序列有(B D )。 A.a.b,c,d B.a,d,c,b C.b,a,d,c D.c,d,a,b 3.链式栈与顺序栈相比，一个比较明显的优点是( B )。 A. 插入操作更加方便 B. 通常不会出现栈满的情况 C. 不会出现栈空的情况 D. 删除操作更加方便 4.在一个顺序存储的循环队列中，队头指针指向队头元素的( A )。 A. 前一个位置 B. 后一个位置 C. 队头元素位置 D. 队尾元素的前一位置 5.若一个栈的输入序列是1，2，3……n，则输出序列的第一个元素是n，则第i个输出元素是（C ）。 A n-i B i C n-i+1 D n-i-1 6.栈的数组表示中，top为栈顶指针，栈空的条件是( D )。 （A）top=0 （B）top=maxSize （C）top=maxSize（D）top=-1 7.在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( B )。 （A）front=maxSize （B）(rear+1)%maxSize=front （C）rear=maxSize （D）rear=front 8. 栈和队列的共同特点是( C )。 （A）都是先进后出（B）都是先进先出 （C）只允许在端点处插入和删除（D）没有共同点 9．与中缀表达式a+b*c-d等价的前缀表达式是( C )。 A.+a-*bcd B.*+-abcd C.-+a*bcd D.abcd+*- 10．中缀表达式A-(B+C)*D/E的后缀形式是( D )。 A.ABC+-D*E/ B.ABC+D*-E/ C.ABC+D-*E/ D.ABC+D*E/- 11．若非空队列采用链式存储结构，front和rear分别为队头元素与队列尾元素的指针，

第三章 栈和队列

第三章栈和队列 一．选择题 1.在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针，则当做退栈处理时，top变化为。 A．top不变 B．top＝top-n C．top＝top-1 D．top=top+1 2.在一个顺序存储的循环队列中，队首指针指向队首元素的。 A．前一个位置 B．后一个位置 C．队首元素位置 D．队尾元素位置3.若进栈序列为1,2,3,4,栈过程中可以出栈，则不可能是一个出栈序列。A．3,4,2,1 B．2,4,3,1 C．1,4,2,3 D．3,2,1,4 4.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是。 A．front= =rear+1 B．front+1= =rear C．front= =rear D．front= =0 5.向一个栈项指针为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; 6.下列说法哪个正确：_______ A．堆栈是在两端操作、先进后出的线性表 B．堆栈是在一端操作、先进先出的线性表 C．队列是在一端操作、先进先出的线性表 D．队列是在两端操作、先进先出的线性表 7.栈和队列的共同点_______ A．都是先进后出 B．都是先进先出 C．只允许在端点处插入和删除元素 D．没有共同点 8.以下数据结构中哪一个是非线性结构？_______ A．队列 B．栈 C．线性表 D．二叉树 9.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3 ，…，pn，若p1=n，则 pi 为_______ A．i B．n=i C．n-i+1 D．不确定 10.当利用大小为 N 的一维数组顺序存储一个栈时，假定用top==N 表示栈空，则向这个栈插入一个元素时，首先应执行_______语句修改top指针。 A．top++ B．top-- C．top=0 D．top 11.4个元素进S栈的顺序是 A,B,C,D,经运算 POP(S)后栈顶元素是_______ A．A B．B C．C D．D 12.一个栈的输入序列是a,b,c,d,e,则栈的不可能的输出序列是_______ A. edcba B.decba C.dceab D. abcde 13．设用链表作为栈的存储结构则退栈操作_______。 A．必须判别栈是否为满 B．必须判别栈是否为空 C．判别栈元素的类型 D．对栈不作任何判别 14．设输入序列是 1、2、3、……、n，经过栈的作用后输出序列的第一个元素是 n，则输出序列中第i个输出元素是_______。 A． n-i B．n-1-i C．n+1-i D．不能确定 15．递归函数f(n)=f(n-1)十 n(n>1) 的递归出口是_______。 A．f(1)=0 B．f(1)=1 C．f(0)=1 D．f(n)=n 16．中缀表达式A-(B+C／D)*E 的后缀形式是_______。

数据结构 第3章答案(已核)

3.5习题 一、名词解释 （1）栈 栈是限制在表的一端进行插入和删除操作的线性表。 允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。 栈的顺序结构：利用顺序存储方式实现的栈称为顺序栈。 栈的链式结构：用链式存储结构实现的栈称为链栈。 （2）队 队是一种“先进先出” (FIFO---First In First Out)的数据结构，即插入操作在表一端进行，而删除操作在表的另一端进行，这种数据结构称为队列。把允许插入的一端称为队尾(rear)，把允许删除的一端称为队头(front)。 队的顺序结构：顺序存储的队称为顺序队。 队的链式结构：采用链式存储结构的队称为链队。 二、判断题 （1）栈和队列都是特殊的线性表。 ( √ ) （2）栈和队列都将插入和删除操作限制在表的端点处进行。 (√ ) （3）只允许在表的一端进行插入和删除操作的线性表称为栈。(√) （4）没有元素的栈称为空栈，空栈用不着栈顶指针。( × ) （5）只要栈不空，就能任意删除栈的元素。 (× ) （6）栈允许删除的一端称为栈顶，而栈底元素是不能删除的。 (× ) （7）对采用链式存储结构的栈进行操作不必判断溢出。 (√ ) （8）元素进出队列一定满足“先进先出”的规律。 (√ ) （9）链队列不存在溢出问题。 (√ ) （10）在链队列中删除一个元素是在链表的最前端进行的。 (√ ) 三、单项选择题 （1）栈和队列的共同之处在于它们具有相同的( A )。 A．逻辑特性 B．物理特性 C．运算方法 D．元素类型

（2）栈和队列都是特殊的线性表，其特殊性在于( C )。 A．它们具有一般线性表所没有的逻辑特性 B．它们的存储结构比较特殊 C．对它们的使用方法做了限制 D．它们比一般线性表更简单 （3）若5个元素的出栈序列为1，2，3，4，5，则进栈序列可能是( )。 A．2，4，3，1，5 B．2，3，1，5，4 C．3，1，4，2，5 D．3，1，2，5，4 （4）某队列初始为空，若它的输入序列为a，b，c，d，它的输出序列应为( )。 A．a，b，c，d B．d，c，b，a C．a，c，b，d D．d，a，c，b （5）当3个元素的进栈序列给定以后，由这3个元素组成的可能的出栈序 列应该有( )。 A．5种 B．6种 C．4种 D．3种 （6）若栈采用顺序存储结构，正常情况下，往堆栈中插入一个元素，栈顶 指针top的变化是( )。 A．不变 B．top=0 C．--top D．top++ （7）若栈采用顺序存储结构，正常情况下，删除栈中一个元素，栈顶指 针top的变化是( )。 A．不变 B．top=0 C．top-- D．top++ （8）若队列采用顺序存储结构，元素的排列顺序( B )。 A．与元素的值的大小有关 B．由元素进入队列的先后顺序决定 C．与队头指针和队尾指针的取值有关 n与作为顺序存储结构的数组的大小有关 （9）若非空栈采用含头结点的链式存储结构，栈顶指针为top，删除堆栈的一个元素的过程是依次执行：p=top，( B )，free(p)。 A．top=p->next B．top->next =p->next C．p=top D．p=p-> next

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

数据结构第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 C．1 B．b D．0 3．已知一个栈的进栈序列是ABC，出栈序列为CBA，经过的栈操作是。A．push,pop,push,pop,push,pop C．push,push,pop,pop,push,pop B．push,push,push,pop,pop,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 C．dceab B．decba D．abcde 6．已知一个栈的进栈序列是1，2，3，……,n，其输出序列的第一个元素是i，则第j个出栈元素是。 A．i C．j-i+1 B．n-i D．不确定

7．已知一个栈的进栈序列是1，2，3，……，n，其输出序列是p1,p2,…,Pn，若 p1=n，则pi的值。 A．i C．n-i+1 B．n-i D．不确定 8．设n个元素进栈序列是1，2，3，……，n，其输出序列是p1,p2,…,pn，若p1=3,则p2的值。 A．一定是2 B．一定是1 C．不可能是1 D．以上都不对 9．设n个元素进栈序列是p1,p2,…,pn，其输出序列是1，2，3，……，n，若p3=1,则p1的值。 A．可能是2 C．不可能是2 B．一定是1 D．不可能是3 10．设n个元素进栈序列是p1,p2,…,pn，其输出序列是1，2，3，……，n，若p3=3,则p1的值。 A．可能是2 C．不可能是1 B．一定是2 D．一定是1 11．设n个元素进栈序列是p1,p2,…,pn，其输出序列是1，2，3，……，n，若pn=1,则pi(1≤i≤n-1)的值。 A．n-i+1 B．n-i C．i D．有多种可能 12．判定一个顺序栈S为空的条件为。 A．S.top= =S.base C．S.top!= S.base+S.stacksize A．S.top-S.base= =S.stacksize C．S.top- S.base!=S.stacksize B．S.top!= S.base D．S.top= = S.base+S.stacksize B．S.top= = S.base D．S.top!= S.base 13．判定一个顺序栈S为栈满的条件是。

3.数据结构作业答案第3章--第3章栈和队列自测卷答案作业答案

head 第3章 栈和队列 自测卷答案 姓名 班级 一、填空题（每空1分，共15分） 1. 【李春葆】向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。 3. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 4. 在一个循环队列中，队首指针指向队首元素的 前一个 位置。(注：不一定，这是一种约定，在殷教材中是队首指针指向队列的首元素位置) 5. 在具有n 个单元的循环队列中，队满时共有 n-1 个元素。 6. 向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。 7. 从循环队列中删除一个元素时，其操作是 先 移动队首指针 ，后 取出元素 。(注：不一定，这是一种约定，在殷教材中是先 取出元素 ，后移动队首指针 ) 8. 〖00年统考题〗带表头结点的空循环双向链表的长度等于 0 。 解： 二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分） （ × ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。 （ × ）2. 在表结构中最常用的是线性表，栈和队列不太常用。 错，不一定吧调用子程序或函数常用，CPU 中也用队列。 （ √ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

第三章 栈和队列习题与解析good

第四章栈和队列习题 一判断题(y/n)nyynnynnn 1做进栈运算时应先判别,栈是否为空。 2,做退栈运算时应先判别,栈是否为空。 3,当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为n. 4,为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的栈顶分别设在着片内存空间的两端。 5, 只有当两个基本栈的栈底在栈空间的某一位置相遇时，才产生上溢。 6, 栈是一种线性表，它的特点是后进先出。 7, 设一数列的顺序为1,2,3,4,5,6, 通过栈结构可以排成的顺序必须是3,2,5,6,4,1. 8, 设有一个空栈，栈顶指针为1000H(十六进制，下同），现有输入序列1,2,3,4,5,经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH后，输出序列是2,1. 9, 设有一个空栈，栈顶指针为1000H(十六进制，下同），现有输入序列1,2,3,4,5,经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH后,栈顶指针是不是1005H.

二单选题(请从下列A，B，C，D选项中选择一项） 1,栈的特点是： 先进先出 后进先出 进优于出 出优于进 2，队列的特点是： 先进先出 后进先出 进优于出 出优于进 3,栈与队列都是： 顺序存储的线性结构 链式存储的线性结构 限制存取点的线性结构 限制存取点的非线性结构 4,若进栈序列为1，2，3，4，则（）不可能是一个出栈序列。 3，2，1，4 3，2，4，1 4，2，3，1 4，3，2，1 1，2，3，4 1，3，2，4 5,若进栈队列的序列为1，2，3，4，则（）是一个出队列序列。 3，2，1，4 3，2，4，1 4，2，3，1 4，3，2，1 1，2，3，4 1，3，2，4 6,若一个栈的输入序列是：1，2，3，...,n，输出序列的第一个元素是n，则第i个输出元素是： 不确定 n-i

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

数据结构练习第三章栈和队列 一、选择题 1．栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2．向顺序栈中压入新元素时，应当（）。 A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针C．先后次序无关紧要 D．同时进行 3．允许对队列进行的操作有( )。 A. 对队列中的元素排序 B. 取出最近进队的元素 C. 在队头元素之前插入元素 D. 删除队头元素 4．用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 5．设用链表作为栈的存储结构则退栈操作（）。 A. 必须判别栈是否为满 B. 必须判别栈是否为空 C. 判别栈元素的类型 D.对栈不作任何判别 6．设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。 A.front->next=s；front=s； B. s->next=rear；rear=s； C. rear->next=s；rear=s； D. s->next=front；front=s； 7．设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。 A.top=top+1; B. top=top-1; C. top->next=top; D. top=top->next; 8．队列是一种（）的线性表。 A. 先进先出 B. 先进后出 C. 只能插入 D. 只能删除 9．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。 A. n-i B. n-1-i C. n+l -i D.不能确定 10．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。 A. 5，3，4，6，1，2 B. 3，2，5，6，4，1 C. 3，1，2，5，4，6 D. 1，5，4，6，2，3 11．队列的删除操作是在（）进行。 A．队首 B．队尾 C．队前 D．队后 12．当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（）语句修改top指针。 A．top++; B．top=0; C．top--; D．top=N; 13．队列的插入操作是在（）进行。