哈尔滨工程大学考研-数据结构-3.doc

《哈尔滨工程大学考研-数据结构-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、溢出”现象，并给出解决方