1~5 C C D A A 6~10 D A B C D 11~15 D D B C B

（1）若让元素1， 2， 3 ， 4， 5 依次进栈，则出栈次序不可能出现在（C）种情况。 A．5， 4， 3， 2， 1 B．2， 1， 5 ，4， 3 C．4， 3， 1 ，2， 5 D．2， 3， 5 ，4， 1

栈是后进先出的线性表，所以可以还原其入栈顺序 栈底–>—>----->------>---->—>栈顶 A. 1->2->3->4->5 满足依次入栈顺序 B. 1->2 然后 2 出栈 1 出栈 ->3->4->5 满足依次入栈顺序 C. 2->1->3->4 依次再出栈 ->5 不满足题意 D. 1->2 2 出栈 ->3 3 出栈->4->5 满足依次入栈顺序

（2）若已知一个栈的入栈序列是1，2 ，3，…， n，其输出序列为p1， p2，p3，…， pn，若p1=n ，则pi 为（C） 。 A. i B. n-i C. n-i+1 D. 不确定

栈是后进先出的线性表 一个栈的入栈序列是1， 2， 3，… ， n ，且输出序列的第一个元素为n ，说明1 ，2，3 ，, ， n 一次性全部进栈， 再进行出栈 所以p1=n ，p2=n-1 ，…，pi=n-i+1 。

（3）数组Ｑ[ｎ]用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（D） 。 A. r - f B. ( n + f - r ) % n C. n + r - f D. （ n + r - f ) % n

对于非循环队列，尾指针和头指针的差值便是队列的长度 对于循环队列，差值可能为负数， 所以需要将差值加上MAXQSIZE （ n ），然后与MAXQSIZE （ n ）求余，即（ n + r - f ) % n 。

（4）链式栈结点为： (data,link) ，top 指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到 x 中,则应执行操作（A） 。 A．x=top->data;top=top->link ； B．top=top->link;x=top->link ； C．x=top;top=top->link ； D．x=top->link ；

先储存栈顶的data，再将栈顶指向下一个结点 x=top->data；top=top->link；

（5）设有一个递归算法如下： int fact ( int n ) { //n 大于等于0 if(n1 进栈时 top 指针先下移，之后再将元素x 存储在V[top] 。

（10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（D）数据结构最佳。 A．线性表的顺序存储结构 B．队列 C．线性表的链式存储结构 D．栈

利用栈的后进先出原则。 先将所有的左括号储存起来，遇见右括号时匹配栈顶元素，如果匹配，做出栈操作，不匹配结束或栈顶元素出栈继续匹配。

（11）用链接方式存储的队列，在进行删除运算时（D）。 A． 仅修改头指针 B．仅修改尾指针 C． 头、尾指针都要修改 D．头、尾指针可能都要修改

进行删除时，也会使用队列的先进先出性质。 所以一般情况下只修改头指针，但是，当删除的是队列中最后一个元素时，队尾指针也丢失了，因此需对队尾指针重新赋值，让其指向头结点。

（12）循环队列存储在数组A[0…m] 中，则入队时的操作为（D）。 A．rear=rear+1 B．rear=(rear+1)%(m-1) C．rear=(rear+1)%m D．rear=(rear+1)%(m+1)

入队时，rear先+1再对数组长度取余。 数组A[0…m] 中共含有 m+1 个元素，故在求模运算时应为 %（m+1）。

（13）最大容量为n 的循环队列， 队尾指针是rear ，队头是front ，则队空的条件是（B）。 A. (rear+1)%nfront B. rearfront C． rear+1front D. (rear-l)%nfront

最大容量为 n 的循环队列， 队满条件是(rear+1)%nfront ， 队空条件是rearfront 。

（14）栈和队列的共同点是（C）。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点

栈只允许在栈顶处进行插入和删除元素，队列只允许在队尾插入元素和在队头删除元素。

（15）一个递归算法必须包括（B）。 A. 递归部分B. 终止条件和递归部分 C. 迭代部分 D. 终止条件和迭代部分

递归算法是函数内部继续调用这个函数，所以它必须要有终止条件，而另一部分是它的递归部分

（1）将编号为0 和1 的两个栈存放于一个数组空间V[m] 中，栈底分别处于数组的两端。当第0 号栈的栈顶指针top[0] 等于-1 时该栈为空，当第1 号栈的栈顶指针top[1] 等于m 时该栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判断栈空、栈满、进栈和出栈等算法的函数。双栈数据结构的定义如下： Typedef struct {int top[2],bot[2]; // 栈顶和栈底指针 SElemType V; // 栈数组 int m; // 栈最大可容纳元素个数 }DblStack

[ 题目分析] 两栈共享向量空间，将两栈栈底设在向量两端，初始时，左栈顶指针为-1 ，右栈顶为m。 两栈顶指针相邻时为栈满。两栈顶相向、迎面增长，栈顶指针指向栈顶元素。

[ 算法描述]