欢迎来到天天文库
浏览记录
ID:61198970
大小:34.00 KB
页数:3页
时间:2021-01-22
《哈尔滨工程大学考研-数据结构-3.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、一、选择题1.对于栈操作数据的原则是()。A.先进先出B.后进先出C.后进后出D.不分顺序2.若一个栈的输入序列为1,2,3,…,n,输出序列的第一个元素是i,则第j个输出元素是()。A.i-j-1B.i-jC.j-i+1D.不确定的3.有六个元素按6,5,4,3,2,1的顺序进栈,问下列哪一个不是合法的出栈序列?()A.543612B.453126C.346521D.2341564.若一个栈以向量V[1..n]存储,初始栈顶指针top为n+1,则下面x进栈的正确操作是()。A.top:=top+1;V[top]:=xB.V[top]:=x;top:=top+1
2、C.top:=top-1;V[top]:=xD.V[top]:=x;top:=top-15.用链接方式存储的队列,在进行删除运算时()。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改6.循环队列存储在数组A[0..m]中,则入队时的操作为()。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)7.最大容量为n的循环队列,队尾指针是rear,队头是front,则队空的条件是()。A.(rear+1)MODn=frontB.re
3、ar=frontC.rear+1=frontD.(rear-l)MODn=front二、判断题1.消除递归不一定需要使用栈。2.两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片内存空间的两端。3.栈与队列是一种特殊操作的线性表。4.循环队列通常用指针来实现队列的头尾相接。35.队列和栈都是运算受限的线性表,只允许在表的两端进行运算。6.栈和队列都是线性表,只是在插入和删除时受到了一些限制。三、填空题1._______是限定仅在表尾进行插入或删除操作的线性表。2.循环队列的引入,目的是为了克服_______。3.设循环队列
4、存放在向量sq.data[0:M]中,则队头指针sq.front在循环意义下的出队操作可表示为_______,若用牺牲一个单元的办法来区分队满和队空(设队尾指针sq.rear),则队满的条件为_______。4.完善下面算法。后缀表达式求值,表达式13/25+61的后缀表达式格式为:13,25/61,+FUNCcompute(a):real;后缀表达式存储在数组a[1..m]中。BEGINsetnull(s);i:=1;ch:=(1)______;WHILEch<>’@’DOBEGINCASEchOF‘0’..‘9’:x:=0;WHILEch<>’,’DOBEG
5、INx:=x*10+ord(ch)-ord(‘0’);i:=i+1;ch:=(2)_______;END‘+’:x:=pop(s)+pop(s);‘-‘:x:=pop(s);x:=pop(s)-x;‘*’:x:=pop(s)*pop(s);‘/’:x:=pop(s);x:=pop(s)/x;ENDCASEpush(s,x);i:=i+1;ch:=a[i];END;comput:=(3)_______;END;35.算术表达式求值的流程,其中OPTR为算术符栈,OPND为操作数栈,precede(oper1,oper2)是比较运算符优先级别的函数,operate(
6、opnd1,oper,opnd2)为两操作数的运算结果函数。(#表示运算起始和终止符号)FUNCTIONexp_reduced:operandtype;INITSTACK(OPTR);PUSH(OPTR"#");INITSTACK(OPND);read(w);WHILENOT((w='#’)AND(GETTOP(OPTR)='#'))DOIFNOTwinopTHENPUSH(OPND,w);ELSECASEprecede(GETTOP(OPTR),w)OF'<':[(1)_______;read(w);]'=':[(2)_______;read(w);];'>'
7、:[theta:=POP(OPTR);b:=POP(OPND);a:=POP(OPND);(3)_______;]ENDC;RETURN(GETTOP(OPND));ENDF;四、应用题1.有5个元素,其入栈次序为:A,B,C,D,E,在各种可能的出栈次序中,以元素C,D最先出栈(即C第一个且D第二个出栈)的次序有哪几个?2.如果输入序列为123456,试问能否通过栈结构得到以下两个序列:435612和135426;请说明为什么不能或如何才能得到。3.用栈实现将中缀表达式8-(3+5)*(5-6/2)转换成后缀表达式,画出栈的变化过程图。4.举例说明顺序队的“假
8、溢出”现象,并给出解决方
此文档下载收益归作者所有