输入序列为CBA，若用S表示入栈，X表示出栈操作，则得到ABC输出序列要经过的栈操作序列为（）：

A.SXSXSX

B.SXSSXX

C.SSXSX

D.SSSXXX

设有一个递归算法如下

        int fact(int n) {  //n大于等于0

             if(n<=0) return 1;

             else return n*fact(n-1);        }

则计算fact(n)需要调用该函数的次数为（  ）。 

A． n+1              

B． n-1              

C． n                  

D． n+2

设计一个判别表达式左右括号是否配对出现的算法，采用（  ）数据结构最佳。

A.线性表的顺序存储结构

B.队列

C.栈

D.线性表的链式存储结构

若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（  ）。

A．i               

B．n-i               

C．n-i+1            

D．不确定

设有一顺序栈已经含有3个元素，如图所示，元素a4正等待进栈，下列不可能出现的出栈序列是

A. a3,a1,a4,a2

B. a3,a2,a4,a1

C. a3,a4,a2,a1

D. a4,a3,a2,a1

数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（  ）。

A．r-f             

B．(n+f-r)%n       

C．n+r-f           

D．（n+r-f)%n

若栈采用顺序存储方式存储，现两栈共享空间V[1...m],tp[i]代表第i个栈（i=1,2)栈顶，栈1的底在V[1]，栈2的底在V[m]，则栈满的条件是

A.tp[2]-tp[1]=0

B. tp[1]+1=tp[2]

C. tp[1]+tp[2]=m

D.tp[1]=tp[2]

A. 5 4 3 6 1 2

B. 3 4 6 5 2 1 

C. 4 5 3 1 2 6

D. 2 3 4 1 5 6

设有一个空栈，栈顶指针为 1000H(十六进制)，每个元素需要 2 个单位的存储空间， 则执行 PUSH，PUSH，POP，PUSH，POP，PUSH，POP，PUSH 操作后，栈顶指针值为 ( ) 。

A．1002H B．1003H C．1004H D．1005H

设有一顺序栈，若有6个元素按s1,s2,s3,s4,s5,s6的顺序进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少需要的单元空间个数应该是（）

A.2

B.6

C.5

D.3

链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（  ）。

A．x=top->data;top=top->link；      B．top=top->link;x=top->link；    

C．x=top;top=top->link；        D．x=top->link；

A. 2 

B. 4 

C. 8 

D. 无限递归

向一个栈顶指针为 h 的带头结点链栈中插入指针 s 所指向节点时，应该执行()。 

A．h->next = s; 

B．s->next = h; 

C．s->next = h; h->next = s; 

D．s->next = h->next; h->next = s;

一个栈的入栈序列{1,2,3,4,5}，栈不可能的输出序列是( )。

A．{5,4,3,2,1} B．{4,5,3,2,1} C．{4,3,5,1,2} D．{1,2,3,4,5}

设有一个顺序栈S，元素s1, s2 , s3, s4, s5, s6 依次进栈，如果6 个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则
顺序栈的容量至少应为

写出下列程序段的输出结果（栈的元素类型SElem Type 为char）。

void main( ){
Stack S;
Char x,y;
InitStack(S);
x=’ c’ ;y= ’ k’;
Push(S,x); Push(S, ’a’Pu);s h(S,y);
Pop(S,x); Push(S, ’ t ’ ); Push(S,x);
Pop(S,x); Push(S, ’ s’ );
while(!StackEmpty(S)){ Pop(S,y);printf(y); };
Printf(x);
}

以下运算实现在链栈上的初始化，请在 ________________处用请适当句子予以填充。 

void InitStacl(LstackTp *ls)

{ ________1________;}

若进栈序列为 ABCD ，请写出至少6种可能的出栈序列和不可能的出栈序列。

如果想将输入的一个字符序列逆序输出，如输入“abcdef”输出“fedcba”，请分析用堆栈、队列方式正确输出的可能性。