8. 多个栈共存时，最好用__链式存储结构_____作为存储结构。【南京理工大学 2001 二、7（2分）】
9．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_____S×SS×S××__。【西南交通大学 2000 一、5】
10. 顺序栈用data[1..n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是_data[++top]=x_____。
【合肥工业大学 2001 三、2 （2分）】 11．表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是___23.12.3*2-4/34.5*7/++108.9/+（注：表达式中的点(.)表示将数隔开，如23.12.3是三个数）____。【中山大学 1998 一、4（1分）】 12. 循环队列的引入，目的是为了克服__假溢出时大量移动数据元素_____。【厦门大学 2001 一、1 （14/8分）】 13．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是：M：=_____(M+1) MOD N __（填PASCAL语言，C语言的考生不填）； M= ____(M+1)% N___（填C语言，PASCAL语言的考生不填）。【西南交通大学 2000 一、7】
14．_______队列_又称作先进先出表。【重庆大学 2000 一、7】 15. 队列的特点是____先进先出___。【北京理工大学 2000 二、2（2分）】
16．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_先进先出______。
【北方交通大学 2001 二、5】
17. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是___s=(LinkedList)malloc(sizeof(LNode))； ____。
【合肥工业大学 2000 三、3（2分）】
18．区分循环队列的满与空，只有两种方法，它们是_牺牲一个存储单元_____和___设标记___。【北京邮电大学2001 二、2（4分）】
19．设循环队列用数组A[1..M]表示，队首、队尾指针分别是FRONT和TAIL，判定队满的条件为___、（TAIL+1）MOD M=FRONT (数组下标0到M-1，若一定使用1到M，则取模为0者，值改取M____。
【山东工业大学 1995 一、1（1分）】
20. 设循环队列存放在向量sq.data[0:M]中，则队头指针sq.front在循环意义下的出队操作可表示为____sq.front=(sq.front+1)%(M+1)___，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_____return(sq.data(sq.front))；(sq.rear+1)%(M+1)==sq.front__。
【长沙铁道学院 1997 二、4 (4分)】
21．表达式求值是__栈_____应用的一个典型例子。【重庆大学 2000 一、10】
22．循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是_、（rear-front+m）% m；______。【厦门大学 2000 六、1（16%/3分）】
23．设Q[0..N-1]为循环队列，其头、尾指针分别为P和R，则队Q中当前所含元素个数为___、（R-P+N）% N；____。
【北京科技大学 1997 一、4】 24．完善下面算法。【中山大学 1998 四、2（6分）】
后缀表达式求值，表达式13/25+61的后缀表达式格式为： 13, 25/61, +
FUNC compute(a):real; 后缀表达式存储在数组a[1..m]中。 BEGIN
setnull(s)；i:=1；ch:= (1a[i]或a[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)_ a[i]_；
_____;
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;
ENDCASE
push(s,x)；i:=i+1；ch:=a[i]； END;
comput:= (3) pop（s）或s[1]；
__ pop（s）_____； END;
25. 算术表达式求值的流程，其中OPTR为算术符栈，OPND为操作数栈，precede(oper1，oper2)是比较运算符优先级别的函数，operate(opnd1,oper,opnd2)为两操作数的运算结果函数。（#表示运算起始和终止符号）【西北工业大学 1999 六、2 (7分)】 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)_PUSH(OPTR,w)______; read(w);] '=':[(2)_POP(OPTR)______; read(w);];
'>':[theta:=POP(OPTR);b:=POP(OPND);a:=POP(OPND);(3)PUSH(OPND,operate（a，the ta,b）)_______；] ENDC;
RETURN(GETTOP(OPND)); ENDF;
26．根据需要，用适当的语句填入下面算法的_______中：
问题：设有n件物品，重量分别为w1,w2,w3,?,wn和一个能装载总重量为T的背包。能否从n件物品中选择若干件恰好使它们的重量之和等于T。若能，则背包问题有解，否则无
解。解此问题的算法如下：
FUNCTION kanp_stack(VAR stack,w:ARRAY[1..n] OF real; VAR top:integer; T:real):boolean;
{w[1：n] 存放n件物品的重量，依次从中取出物品放入背包中，检查背包重量，若不超过T，则装入，否则弃之，取下一个物品试之。若有解则返回函数值true,否则返回false}
BEGIN
top:=0; i:=1; { i指示待选物品} WHILE (1)_ T>0______ AND(2)__ i [IF (3)_ T>0_____ OR (4)_ T>0______ AND (i THEN [top := (5) top+1_______ ;stack[top] :=i;{第i件物品装入背包} T:=T-w[i]]; IF T=0 THEN RETURN ((6) true_______) {背包问题有解} ELSE [IF (i=n ) AND (top>0) THEN [i:=(7)_ i-1______;{取出栈顶物品} top:= (8)_ top-1______ ；T:= (9) T+w[i]_______ ]; {恢复T值} i:=i+1 {准备挑选下一件物品} ]; ]; RETURN((10)_ false______) {背包无解} END; 【北京邮电大学 1996 四（10分）】 四 应用题 1. 名词解释：栈: 栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出（LIFO）表。【燕山大学 1999 一、1（2分）】【吉林工业大学 1999 一、3（2分）】 2. 名词解释：队列: 队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开（删除），故队列也常称先进先出（FIFO）表【大连海事大学 1996 一、6 ( 1分 )】 3. 什么是循环队列？ 用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度（容量）。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。【哈尔滨工业大学 2001 三、2（3分）】【河南大学 1998 一、4（3分）】 4. 假设以S和X分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S和X组成的序列表示（如SXSX）。 （1）试指出判别给定序列是否合法的一般规则。 通常有两条规则。第一是给定序列中S的个数和X的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S的个数要大于或等于X的个数。 （2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列？如能得到，请举列说明。 可以得到相同的输出元素序列。例如，输入元素为A，B，C，则两个输入的合法序列ABC 和BAC均可得到输出元素序列ABC。对于合法序列ABC，我们使用本题约定的S×S×S×操作序列；对于合法序列BAC，我们使用SS××S×操作序列。 【东南大学 1992 二（10分）】 5. 有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？【西南交通大学 2000 二、1】 三个：CDEBA，CDBEA，CDBAE 6. 如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6;请说明为什么不能或如何才能得到。【武汉交通科技大学 1996 二、3 (3分)】 输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。 得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426 7. 若元素的进栈序列为：A、B、C、D、E，运用栈操作，能否得到出栈序列B、C、A、E、D和D、B、A、C、E？为什么？【北京科技大学 1998 一、2】 能得到出栈序列B、C、A、E、D，不能得到出栈序列D、B、A、C、E。其理由为：若出栈序列以D开头，说明在D之前的入栈元素是A、B和C，三个元素中C是栈顶元素，B和A不可能早于C出栈，故不可能得到D、B、A、C、E出栈序列。 8. 设输入序列为a,b,c,d,试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。 借助栈结构，n个入栈元素可得到1/(n+1)((2n）！/（n!*n!）)种出栈序列。本题4个元素，可有14种出栈序列，abcd和dcba就是其中两种。但dabc和adbc是不可能得到的两种 【北京科技大学 2001 一、4（2分）】 9. 设输入序列为2，3，4，5，6，利用一个栈能得到序列2，5，3，4，6吗？栈可以用单链表实现吗？ 【山东师范大学 1996 五、4（2分）】 不能得到序列2，5，3，4，6。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点 10. 试证明：若借助栈由输入序列1,2,?,n得到输出序列为P1,P2,?,Pn（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着i 如果i 11. 设一数列的输入顺序为123456，若采用堆栈结构，并以A和D分别表示入栈和出栈操作，试问通过入出栈操作的合法序列。 （1） 能否得到输出顺序为325641的序列。能得到325641。在123依次进栈后，3和2出栈，得部分输出序列32；然后4，5入栈，5出栈，得部分出栈序列325；6入栈并出栈，得部分输出序列3256；最后退栈，直到栈空。得输出序列325641。其操作序列为AAADDAADADDD。（5分） （2） 能否得到输出顺序为154623的序列。（5分） 【北方交通大学 1995 一（10分）】 不能得到输出顺序为154623的序列。部分合法操作序列为ADAAAADDAD，得到部分输出序 列1546后，栈中元素为23，3在栈顶，故不可能2先出栈，得不到输出序列154623 12.（1） 什么是递归程序？ （2） 递归程序的优、缺点是什么？ （3） 递归程序在执行时，应借助于什么来完成？ （4） 递归程序的入口语句、出口语句一般用什么语句实现？【大连海事大学 1996二、4(4分)】 12、（1）一个函数在结束本函数之前，直接或间接调用函数自身，称为递归。例如，函数f在执行中，又调用函数f自身，这称为直接递归；若函数f在执行中，调用函数g，而g在执行中，又调用函数f，这称为间接递归。在实际应用中，多为直接递归，也常简称为递归。 （2）递归程序的优点是程序结构简单、清晰，易证明其正确性。缺点是执行中占内存空间较多，运行效率低。 （3）递归程序执行中需借助栈这种数据结构来实现。 （4）递归程序的入口语句和出口语句一般用条件判断语句来实现。递归程序由基本项和归纳项组成。基本项是递归程序出口，即不再递归即可求出结果的部分；归纳项是将原来问题化成简单的且与原来形式一样的问题，即向着“基本项”发展，最终“到达”基本项。 13. 设有下列递归算法: FUNCTION vol(n:integer):integer; VAR x :integer: BEGIN IF n=0 THEN vol:=0 ELSE BEGIN read(x)；vol:=vol(n-1)+x；END； END； 如该函数被调用时，参数n值为4,读入的x值依次为5,3,4,2，函数调用结束时返回值vol为多少?用图示描述函数执行过程中，递归工作栈的变化过程。【北京工业大学 1998 四 (10分)】 13、函数调用结束时vol=14。执行过程图示如下： vol（4） vol(4)=vol(3)+5 14 =vol(2)+3+5 =vol(1)+4+3+5 vol（3）+5 =vol(0)+2+4+3+5 9 =0+2+4+3+5 =14 vol（2）+3 6 vol（1）+4 2 vol（0）+2 0 14. 当过程P递归调用自身时，过程P内部定义的局部变量在P的2次调用期间是否占用同一数据区？为什么？【山东师范大学 1999 一、4 （4分）】