数据结构考研分类复习真题 第三章 栈和队列[14]

算术表达式求值的流程其中OPTR为算术符栈OPND为操作数栈precede(operoper)是比较运算符优先级别的函数operate(opndoperopnd)为两操作数的运算结果函数（#表示运算起始和终止符号）【西北工业大学 六 (分)】

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(OPNDw);

ELSE CASE precede(GETTOP(OPTR)w)OF

<:[()_______; read(w);]

=:[()_______; read(w);];

>:[theta:=POP(OPTR);b:=POP(OPND);a:=POP(OPND);()_______]

ENDC;

RETURN(GETTOP(OPND));

ENDF;

．根据需要用适当的语句填入下面算法的_______中【北京邮电大学 四（分）】

问题设有n件物品重量分别为www…wn和一个能装载总重量为T的背包能否从n件物品中选择若干件恰好使它们的重量之和等于T若能则背包问题有解否则无解解此问题的算法如下

FUNCTION kanp_stack(VAR stackw:ARRAY[n] OF real; VAR top:integer; T:real):boolean; {w[n] 存放n件物品的重量依次从中取出物品放入背包中检查背包重量若不超过T则装入否则弃之取下一个物品试之若有解则返回函数值true否则返回false}

BEGIN

top:=; i:=; {i指示待选物品}

WHILE ()_______ AND()_______DO

[IF ()______ OR ()_______ AND (i<n)

THEN [top := ()_______ ;stack[top] :=i; {第i件物品装入背包}

T:=Tw[i]];

IF T= THEN RETURN (()_______) {背包问题有解}

ELSE [IF (i=n ) AND (top>)

THEN [i:=()_______; {取出栈顶物品}

top:= ()_______ T:= ()_______ ]; {恢复T值}

i:=i+ {准备挑选下一件物品}

];

];

RETURN(()_______) {背包无解}

END;

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []