第三章栈和队列习题数据结构电子教案.docx
《第三章栈和队列习题数据结构电子教案.docx》由会员分享，可在线阅读，更多相关《第三章栈和队列习题数据结构电子教案.docx（16页珍藏版）》请在冰点文库上搜索。
第三章栈和队列习题数据结构电子教案
习题三栈和队列
一单项选择题
1.在作进栈运算时,应先判别栈是否（①）,在作退栈运算时应先判别栈是否（②）。
当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为（③）。
①,②:
A.空B.满C.上溢D.下溢
③:
A.n-1B.nC.n+1D.n/2
2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为（）。
A可能是2B一定是2C可能是1D一定是1
3.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？
（）
A.543612B.453126C.346521D.234156
4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是（）
A.2B.3C.5D.6
5.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈（i=1,2）栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。
A.|top[2]-top[1]|=0B.top[1]+1=top[2]
C.top[1]+top[2]=mD.top[1]=top[2]
6.执行完下列语句段后，i值为：
（）
intf（intx）
{return（（x>0）?
x*f（x-1）:
2）;}
inti;
i=f（f
（1））;
A．2B.4C.8D.无限递归
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+1B.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
12.栈和队列的共同点是（）。
A.都是先进先出B.都是先进后出
C.只允许在端点处插入和删除元素D.没有共同点
二、填空题
1．栈是_______的线性表，其运算遵循_______的原则。
2.一个栈的输入序列是：
1，2，3则不可能的栈输出序列是_______。
3．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_______。
4.循环队列的引入，目的是为了克服_______。
5．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_______。
6.已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_______。
7．表达式求值是_______应用的一个典型例子。
8．循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是_______。
9.以下运算实现在链栈上的初始化，请在________________处用请适当句子予以填充。
VoidInitStacl（LstackTp*ls）{________________;}
10.`以下运算实现在链栈上的进栈，请在处用请适当句子予以填充。
VoidPush（LStackTp*ls,DataTypex）
{LstackTp*p;p=malloc（sizeof（LstackTp））;
________________;
p->next=ls;
________________;
}
11．以下运算实现在链栈上的退栈，请在________________处用请适当句子予以填充。
IntPop（LstackTp*ls,DataType*x）
{LstackTp*p;
if（ls!
=NULL）
{p=ls;
*x=________________;
ls=ls->next;
________________;
return
（1）；
}elsereturn（0）;
}
12.以下运算实现在链队上的入队列，请在________________处用适当句子予以填充。
VoidEnQueue（QueptrTp*lq,DataTypex）
{LqueueTp*p;
p=（LqueueTp*）malloc（sizeof（LqueueTp））;
________________=x;
p->next=NULL;
（lq->rear）->next=________________;
________________;
}
三、应用题
1．给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？
2.画出对算术表达式A-B*C/D-E↑F求值时操作数栈和运算符栈的变化过程。
3.将两个栈存入数组V[1..m]应如何安排最好？
这时栈空、栈满的条件是什么？
4.怎样判定循环队列的空和满？
四、算法设计题
1．借助栈（可用栈的基本运算）来实现单链表的逆置运算。
2.设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法：
EXYX（E）;（注：
算法中可调用栈操作的基本算法。
）
3.假设以I和O分别表示入栈和出栈操作。
栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
（1）下面所示的序列中哪些是合法的？
A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO
（2）通过对
（1）的分析，写出一个算法，判定所给的操作序列是否合法。
若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。
4.设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O..maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。
试设计S1,S2有关入栈和出栈的操作算法。
5.请利用两个栈S1和S2来模拟一个队列。
已知栈的三个运算定义如下：
PUSH（ST,x）:
元素x入ST栈；POP（ST,x）：
ST栈顶元素出栈，赋给变量x；Sempty（ST）：
判ST栈是否为空。
那么如何利用栈的运算来实现该队列的三个运算：
enqueue:
插入一个元素入队列；dequeue:
删除一个元素出队列；queue_empty：
判队列为空。
（请写明算法的思想及必要的注释）
6．要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。
7.已知Q是一个非空队列，S是一个空栈。
仅用队列和栈的ADT函数和少量工作变量，编写一个算法，将队列Q中的所有元素逆置。
栈的ADT函数有：
makeEmpty（s:
stack）;置空栈
push（s:
stack;value:
datatype）;新元素value进栈
pop（s:
stack）:
datatype;出栈，返回栈顶值
isEmpty（s:
stack）:
Boolean;判栈空否
队列的ADT函数有：
enqueue（q:
queue:
value:
datatype）;元素value进队
deQueue（q:
queue）:
datatype;出队列，返回队头值
isEmpty（q:
queue）:
boolean;判队列空否
第3章栈和队列
一单项选择题
1.BAB
2．A
3.C
4.B
5.B
6.B
7.D
8.D
9.C
10．D
11.C
12.C
二、填空题
1．操作受限（或限定仅在表尾进行插入和删除操作）后进先出
2.312
3．S×SS×S××
4.假溢出时大量移动数据元素
5．先进先出
6.s=（LinkedList）malloc（sizeof（LNode））；s->data=x;s->next=r->next；r->next=s；r=s；
7．栈
8．（rear-front+m）%m；
9．ls=NULL
10．p->data=x,ls=p
11．p->data,free（p）
12．p->data,p,lq->rear=p
三、应用题
1．【解答】
（1）顺序栈（top用来存放栈顶元素的下标）
判断栈S空：
如果S->top==-1表示栈空。
判断栈S满：
如果S->top==Stack_Size-1表示栈满。
（2）链栈（top为栈顶指针，指向当前栈顶元素前面的头结点）
判断栈空：
如果top->next==NULL表示栈空。
判断栈满：
当系统没有可用空间时，申请不到空间存放要进栈的元素，此时栈满。
2.设操作数栈是opnd，操作符栈是optr，对算术表达式A-B*C/D-E↑F求值，过程如下：
步骤
opnd栈
optr栈
输入字符
主要操作
初始
#
A-B*C/D-E↑F#
PUSH（OPTR,’#’）
1
A
#
A-B*C/D-E↑F#
PUSH（OPND,A）
2
A
#-
-B*C/D-E↑F#
PUSH（OPTR,’-’）
3
AB
#-
B*C/D-E↑F#
PUSH（OPND,B）
4
AB
#-*
*C/D-E↑F#
PUSH（OPTR,’*’）
5
ABC
#-*
C/D-E↑F#
PUSH（OPND,C）
6
AT（T=B*C）
#-/
/D-E↑F#
PUSH（OPND,POP（OPND）*POP（OPND））
PUSH（OPTR,’/’）
7
ATD
#-/
D-E↑F#
PUSH（OPND,D）
8
AT（T=T/D）
T（T=A-T）
#-
#-
-E↑F#
x=POP（OPND）;y=POP（OPND）
PUSH（OPND,y/x）;
x=POP（OPND）;y=POP（OPND）;
PUSH（OPND,y-x）
PUSH（OPTR,’-’）
9
TE
#-
E↑F#
PUSH（OPND,E）
10
TE
#-↑
↑F#
PUSH（OPTR,‘↑’）
11
TEF
#-↑
F#
PUSH（OPND,F）
12
TE
TS（S=E↑F）
R（R=T-S）
#-
#
#
X=POP（OPND）Y=POP（OPND）
POP（OPTR）PUSH（OPND,y↑x）
x=POP（OPND）y=POP（OPND）
POP（OPTR）PUSH（OPND,y-x）
3.设栈S1和栈S2共享向量V[1..m]，初始时，栈S1的栈顶指针top[0]=0，栈S2的栈顶指针top[1]=m+1，当top[0]=0为左栈空，top[1]=m+1为右栈空；当top[0]=0并且top[1]=m+1时为全栈空。
当top[1]-top[0]=1时为栈满。
4.设顺序存储队列用一维数组q[m]表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。
设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。
当front等于-1时队空，rear等于m-1时为队满。
由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等于-1，则队列中仍有空闲单元，所以队列并不是真满。
这时若再有入队操作，会造成假“溢出”。
其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0..m-1）。
在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。
另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。
四算法设计题
1．解：
方法是先依次让单链表上的元素进栈，然后再依次出栈。
Voidinvert（lklisthead）
{LstackTps;
initstack（s）;
p=head;
while（p<>null）
{Push（s,p->data）;p=p->next;}
p=head;
while（notemptystack（s））
{pop（s,p->data）;p=p->next;}
}
2.[题目分析]判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时退栈。
退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。
如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配。
intEXYX（charE[],intn）
//E[]是有n字符的字符数组，存放字符串表达式，以‘#’结束。
本算法判断表达式中圆括号是否匹配。
{chars[30];//s是一维数组，容量足够大，用作存放括号的栈。
inttop=0;//top用作栈顶指针。
s[top]=‘#’;//‘#’先入栈，用于和表达式结束符号‘#’匹配。
inti=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++;//读入其它字符，不作处理。
}
}//算法结束。
[算法讨论]本题是用栈判断括号匹配的特例：
只检查圆括号的配对。
一般情况是检查花括号（‘{’，‘}’）、方括号（‘[’，‘]’）和圆括号（‘（’，‘）’）的配对问题。
编写算法中如遇左括号（‘{’，‘[’，或‘（’）就压入栈中，如遇右括号（‘}’，‘]’，或‘）’），则与栈顶元素比较，如是与其配对的括号（左花括号，左方括号或左圆括号），则弹出栈顶元素；否则，就结论括号不配对。
在读入表达式结束符‘#’时，栈中若应只剩‘#’，表示括号全部配对成功；否则表示括号不匹配。
另外，由于本题只是检查括号是否匹配，故对从表达式中读入的不是括号的那些字符，一律未作处理。
再有，假设栈容量足够大，因此入栈时未判断溢出。
3.
（1）A和D是合法序列，B和C是非法序列。
（2）设被判定的操作序列已存入一维数组A中。
intJudge（charA[]）
//判断字符数组A中的输入输出序列是否是合法序列。
如是，返回true，否则返回false。
{i=0;//i为下标。
j=k=0;//j和k分别为I和字母O的的个数。
while（A[i]!
=‘\0’）//当未到字符数组尾就作。
{switch（A[i]）
{case‘I’:
j++;break;//入栈次数增1。
case‘O’:
k++;if（k>j）{printf（“序列非法\n”）；exit（0）;}
}
i++;//不论A[i]是‘I’或‘O’，指针i均后移。
}
if（j!
=k）{printf（“序列非法\n”）；return（false）;}
else{printf（“序列合法\n”）；return（true）;}
}//算法结束。
[算法讨论]在入栈出栈序列（即由‘I’和‘O’组成的字符串）的任一位置，入栈次数（‘I’的个数）都必须大于等于出栈次数（即‘O’的个数），否则视作非法序列，立即给出信息，退出算法。
整个序列（即读到字符数组中字符串的结束标记‘\0’），入栈次数必须等于出栈次数（题目中要求栈的初态和终态都为空），否则视为非法序列。
4．[题目分析]两栈共享向量空间，将两栈栈底设在向量两端，初始时，s1栈顶指针为-1，s2栈顶为maxsize。
两栈顶指针相邻时为栈满。
两栈顶相向，迎面增长，栈顶指针指向栈顶元素。
#definemaxsize两栈共享顺序存储空间所能达到的最多元素数
#defineelemtpint//假设元素类型为整型
typedefstruct
{elemtpstack[maxsize];//栈空间
inttop[2];//top为两个栈顶指针
}stk;
stks;//s是如上定义的结构类型变量，为全局变量。
（1）入栈操作：
intpush（inti,intx）
//入栈操作。
i为栈号，i=0表示左边的栈s1，i=1表示右边的栈s2，x是入栈元素。
入栈成功返回1，否则返回0。
{if（i<0||i>1）{printf（“栈号输入不对”）;exit（0）;}
if（s.top[1]-s.top[0]==1）{printf（“栈已满\n”）;return（0）;}
switch（i）
{case0:
s.stack[++s.top[0]]=x;return
（1）;break;
case1:
s.stack[--s.top[1]]=x;return
（1）;
}
}//push
（2）退栈操作
elemtppop（inti）
//退栈算法。
i代表栈号，i=0时为s1栈，i=1时为s2栈。
退栈成功返回退栈元素，否则返回-1。
{if（i<0||i>1）{printf（“栈号输入错误\n”）；exit（0）;}
switch（i）
{case0:
if（s.top[0]==-1）{printf（“栈空\n”）；return（-1）；}
elsereturn（s.stack[s.top[0]--]）;
case1:
if（s.top[1]==maxsize{printf（“栈空\n”）;return（-1）;}
elsereturn（s.stack[s.top[1]++]）;
}
}//算法结束
[算法讨论]请注意算法中两栈入栈和退栈时的栈顶指针的计算。
两栈共享空间示意图略，s1栈是通常意义下的栈，而s2栈入栈操作时，其栈顶指针左移（减1），退栈时，栈顶指针右移（加1）。
5.[题目分析]栈的特点是后进先出，队列的特点是先进先出。
所以，用两个栈s1和s2模拟一个队列时，s1作输入栈，逐个元素压栈，以此模拟队列元素的入队。
当需要出队时，将栈s1退栈并逐个压入栈s2中，s1中最先入栈的元素，在s2中处于栈顶。
s2退栈，相当于队列的出队，实现了先进先出。
显然，只有栈s2为空且s1也为空，才算是队列空。
（1）intenqueue（stacks1,elemtpx）
//s1是容量为n的栈，栈中元素类型是elemtp。
本算法将x入栈，若入栈成功返回1，否则返回0。
{if（top1==n&&!
Sempty（s2））//top1是栈s1的栈顶指针，是全局变量。
{printf（“栈满”）;return（0）;}//s1满s2非空,这时s1不能再入栈。
if（top1==n&&Sempty（s2））//若s2为空，先将s1退栈,元素再压栈到s2。
{while（!
Sempty（s1））{POP（s1,x）;PUSH（s2,x）;}
PUSH（s1,x）;return
（1）;//x入栈，实现了队列元素的入队。
}
（2）voiddequeue（stacks2,s1）
//s2是输出栈，本算法将s2栈顶元素退栈，实现队列元素的出队。
{if（!
Sempty（s2））//栈s2不空，则直接出队。
{POP（s2,x）;printf（“出队元素为”,x）;}
else//处理s2空栈。
if（Sempty（s1））{printf（“队列空”）;exit（0）;}//若输入栈也为空，则判定队空。
else//先将栈s1倒入s2中，再作出队操作。
{while（!
Sempty（s1））{POP（s1,x）;PUSH（s2,x）;}
POP（s2,x）;//s2退栈相当队列出队。
printf（“出队元素”，x）;
}
}//结束算法dequue。
（3）intqueue_empty（）
//本算法判用栈s1和s2模拟的队列是否为空。
{if（Sempty（s1）&&Sempty（s2））return
（1）;//队列空。
elsereturn（0）;//队列不空。
}
[算法讨论]算法中假定栈s1和栈s2容量相同。
出队从栈s2出，当s2为空时，若s1不空，则将s1倒入s2再出栈。
入队在s1，当s1满后，若s2空，则将s1倒入s2，之后再入队。
因此队列的容量为两栈容量之和。
元素从栈s1倒入s2，必须在s2空的情况下才能进行，即在要求出队操作时，若s2空，则不论s1元素多少（只要不空），就要全部倒入s2中。
6．【解答】入队算法：
intEnterQueue（SeqQueue*Q,QueueElementTypex）
{/*将元素x入队*/
if（Q->front==Q->front&&tag==1）/*队满*/
return（FALSE）;
if（Q->front==Q->front&&tag==0）/*x入队前队空，x入队后重新设置标志*/
tag=1;
Q->elememt[Q->rear]=x;
升级会员 