一、单项选择题

————————————————————

————————————————————

解析：缓冲区是用队列实现的，先进先出，A、B、C都是栈的典型应用。

正确答案：D

————————————————————

————————————————————

解析：后缀表达式中，每个计算符号均直接位于其两个操作数的后面，按照这样的方式逐步根据计算的优先级将每个计算式进行变换，即可得到后缀表达式。

正确答案：B

————————————————————

————————————————————

解析：先进先出（First In First Out，FIFO）算法的核心是更换最早进入内存的页面。先进先出是任何人都能直观想到的办法，因为它是人类的天性。FIFO页面替换算法用到了队列。其余的都只用到了栈。

正确答案：D

————————————————————

————————————————————

解析：利用栈求表达式的值时,可以分别设立运算符栈和运算数栈，其原理不变。选项B中A入栈，B入栈，计算得R1，c入栈，计算得R2，D入栈，计算得R3，由此得栈深为2。A、C、D依次计算得栈深为4、3、3。因此选B。

正确答案：B

————————————————————

————————————————————

解析：栈与递归有着紧密的联系。递归模型包括递归出口和递归体两个方面。递归出口是递归算法的出口，即终止递归的条件。递归体是一个递推的关系式。根据题意有
f(0)=2;
f(1)=1*f(0)=2;
f(f(1))=f(2)=2*f(1)=4。

正确答案：B

————————————————————

————————————————————

解析：

由图可知，递归函数F()调用的次数为9。

正确答案：C

————————————————————

————————————————————

解析：首先，执行内层参数func(5)=func(3)+func(1)=4，共执行3次func函数。然后，执行func(func (5))=func(4)=func(2)+func(0)=4，因此第4个被执行的func函数是func(4)。也可以采用画出递归调用树的方式，即某个函数的执行次序等于其在递归调用树的层次遍历中的次序。

正确答案：C

————————————————————

————————————————————

解析：通常情况下，递归算法在计算机实际执行的过程中包含很多的重复计算，所以效率会低。

正确答案：B

————————————————————

————————————————————

解析：调用函数时，系统会为调用者构造一个由参数表和返回地址组成的活动记录，并将记录压入系统提供的栈中，若被调用函数有局部变量，也要压入栈中。

正确答案：C

————————————————————

————————————————————

解析：图的广度优先搜索类似于树的层序遍历，都要借助于队列。

正确答案：B

————————————————————

————————————————————

解析：使用栈可以模拟递归的过程，以此来消除递归，但对于单向递归和尾递归而言，可以用迭代的方式来消除递归，A正确。不同的进栈和出栈组合操作，会产生许多不同的输出序列，B错误。通常使用栈来处理函数或过程调用，C错误。队列和栈都是操作受限的线性表，但只有队列允许在表的两端进行运算，而栈只允许在栈顶方向进行操作，D错误。

正确答案：A

————————————————————

————————————————————

解析：在提取数据时必须保持原来数据的顺序，所以缓冲区的特性是先进先出。

正确答案：B

————————————————————

————————————————————

解析：

正确答案：A

————————————————————

————————————————————

解析：

正确答案：B

————————————————————

————————————————————

解析：递归调用函数时，在系统栈中保存的函数信息需满足先进后出的特点，依次调用了main (),s(1),s(0)，所以栈底到栈顶的信息依次是main ( ),s(1),s(0)。

正确答案：A

————————————————————

————————————————————

解析：根据题意:入队顺序为8,4,2,5,3,9,1,6,7，出队顺序为1~9。入口和出口之间有多个队列(n条轨道)，且每个队列(轨道)可容纳多个元素（多列列车)，为便于区分，队列用字母编号。分析如下:显然先入队的元素必须小于后入队的元素（否则，若8和4入同一个队列，8在4前面，则出队时也只能8在4前面)，这样8入队列A，4入队列B，2入队列C，5入队列B(按照前述原则“大的元素在小的元素后面”也可将5入队列C，但这时剩下的元素3就必须放入一个新的队列中，无法确保“至少”)，3入队列C，9入队列A，这时共占了3个队列，后面还有元素1，直接再用一个新的队列D，1从队列D出队后，剩下的元素6和7或入队列B，或入队列C。综上，共占用了4个队列。当然还有其他的入队、出队情况，请读者自己推演，但要确保满足:①队列中后面的元素大于前面的元素;②确保占用最少(即满足题意中“至少”)的队列。

正确答案：C

————————————————————

————————————————————

解析：Ⅰ的反例:计算斐波拉契数列迭代实现只需要一个循环即可实。Ⅲ的反例：入栈序列为1,2进行Push, Push, Pop, Pop操作，出栈次序为2,1;进行Push,Pop, Push, Pop操作，出栈次序为1,2。IV，栈是一种受限的线性表，只允许在一端进行操作。Ⅱ正确。

正确答案：C

————————————————————

————————————————————

解析：

正确答案：B

二、综合应用题

————————————————————

————————————————————

解答：