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

一、选择题1对于栈操作数据的原则是（ ）。A先进先出 B后进先出 C后进后出 D不分顺序2若一个栈的输入序列为1,2,3,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。 Ai-j-1 Bi-j Cj-i+1 D不确定的3 有六个元素按6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）A5 4 3 6 1 2 B4 5 3 1 2 6 C3 4 6 5 2 1 D2 3 4 1 5 6 4若一个栈以向量V1.n存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。Atop:=top+1; V top:=x BV top:=x; top:=top+1 Ctop:=top-1; V top:=x DV top:=x; top:=top-15用链接方式存储的队列，在进行删除运算时（ ）。A仅修改头指针 B仅修改尾指针 C头、尾指针都要修改 D头、尾指针可能都要修改6循环队列存储在数组A0.m中，则入队时的操作为（ ）。Arear=rear+1 Brear=(rear+1) mod (m-1) Crear=(rear+1) mod m Drear=(rear+1)mod(m+1) 7 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。 A(rear+1) MOD n=front B rear=front Crear+1=front D(rear-l) MOD n=front二、判断题1消除递归不一定需要使用栈。2两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。3栈与队列是一种特殊操作的线性表。4循环队列通常用指针来实现队列的头尾相接。5队列和栈都是运算受限的线性表，只允许在表的两端进行运算。6栈和队列都是线性表，只是在插入和删除时受到了一些限制。三、填空题 1_是限定仅在表尾进行插入或删除操作的线性表。2循环队列的引入，目的是为了克服_。 3设循环队列存放在向量sq.data0:M中，则队头指针sq.front在循环意义下的出队操作可表示为_，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_。4完善下面算法。后缀表达式求值，表达式13/25+61的后缀表达式格式为： 13, 25/61, +FUNC compute(a):real; 后缀表达式存储在数组a1.m中。BEGIN setnull(s)；i:=1；ch:= (1)_； WHILE ch<> DO BEGIN CASE ch OF 0.9: x:=0; WHILE ch<>,DO BEGIN x:=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:=ai；END;comput:= (3)_；END;5算术表达式求值的流程，其中OPTR为算术符栈，OPND为操作数栈，precede(oper1，oper2)是比较运算符优先级别的函数，operate(opnd1,oper,opnd2)为两操作数的运算结果函数。（#表示运算起始和终止符号） FUNCTION exp_reduced:operandtype; INITSTACK(OPTR);PUSH(OPTR"#")；INITSTACK(OPND);read(w)； WHILE NOT(w=#) AND (GETTOP(OPTR)=#) DO IF NOT w in op THEN PUSH(OPND,w); ELSE CASE precede(GETTOP(OPTR),w)OF <:(1)_; read(w); =:(2)_; read(w); >: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 如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6;请说明为什么不能或如何才能得到。3用栈实现将中缀表达式8-(3+5)*(5-6/2)转换成后缀表达式，画出栈的变化过程图。4举例说明顺序队的“假溢出”现象，并给出解决方案。3