一、选择题

1、一个栈的输入序列为：a，b，c，d，e，则栈的不可能输出的序列是（   ）。

A. a,b,c,d,e              B. d,e,c,b,a           

C. d,c,e,a,b              D. e,d,c,b,a

2、判断一个循环队列Q（最多n个元素）为满的条件是（   ）。

A. Q->rear==Q->front               B. Q->rear==Q->front+1     

C. Q->front==(Q->rear+1)%n         D. Q->front==(Q->rear-1)%n

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

A. 顺序表          B. 链表           C. 队列        D. 栈

4、带头结点的单链表head为空的判定条件是（   ）。

A. head==NULL　          B. head->next==NULL     

C. head->next!=NULL  D. head!=NULL

5、一个栈的输入序列为：1,2,3,4，则栈的不可能输出的序列是（   ）。

A. 1243          B. 2134       C. 1432        D. 4312      E. 3214

6、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0，3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（   ）。

A. 1和5              B. 2和4       C. 4和2       D. 5和1

7、队列的插入操作是在（   ）。

A. 队尾               B. 队头        C. 队列任意位置    D. 队头元素后

8、循环队列的队头和队尾指针分别为front和rear，则判断循环队列为空的条件是（   ）。

A. front==rear            B. front==0     

C. rear==0             D. front=rear+1

9、一个顺序栈S，其栈顶指针为top，则将元素e入栈的操作是（   ）。

A. *S->top=e;S->top++;          B. S->top++;*S->top=e;  

C. *S->top=e                    D. S->top=e;

10、表达式a*(b+c)-d的后缀表达式是（   ）。

A. abcd+-　       B. abc+*d-    C. abc*+d-    D. -+*abcd

11、将递归算法转换成对应的非递归算法时，通常需要使用（   ）来保存中间结果。

A. 队列        B. 栈         C. 链表           D. 树

12、栈的插入和删除操作在（   ）。

    A. 栈底         B. 栈顶        C.  任意位置        D. 指定位置

13、五节车厢以编号1，2，3，4，5顺序进入铁路调度站（栈），可以得到（   ）的编组。

    A. 3，4，5，1，2           B. 2，4，1，3，5     

C. 3，5，4，2，1          D. 1，3，5，2，4

14、判定一个顺序栈S（栈空间大小为n）为空的条件是（   ）。

A. S->top==0         B. S->top!=0         

C. S->top==n         D. S->top!=n

15、在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（   ）。

A. front=front->next       B. s->next=rear;rear=s

C. rear->next=s;rear=s;     D. s->next=front;front=s;

16、一个队列的入队序列是1，2，3，4，则队列的出队序列是（   ）。

    A. 1，2，3，4　                  B. 4，3，2，1 

    C. 1，4，3，2                   D. 3，4，1，2

17、依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操作，此时的队头元素是（   ）。

A. a           B. b              C. c           D. d

18、正常情况下，删除非空的顺序存储结构的堆栈的栈顶元素，栈顶指针top的变化是（   ）。

A. top不变         B. top=0      C. top=top+1      D. top=top-1

19、判断一个循环队列Q（空间大小为M）为空的条件是（   ）。

A. Q->front==Q->rear            B. Q->rear-Q->front-1==M   

C. Q->front+1=Q->rear            D. Q->rear+1=Q->front

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

A. 线性表的顺序存储结构    B. 队列    C. 栈          D. 线性表的链式存储结构

21、当用大小为N的数组存储顺序循环队列时，该队列的最大长度为（   ）。

A. N　        B. N+1        C. N-1        D. N-2

22、队列的删除操作是在（   ）。

A. 队首　         B. 队尾        C. 队前        D. 队后

23、若让元素1，2，3依次进栈，则出栈次序不可能是（   ）。

A. 3，2，1　       B. 2，1，3     C. 3，1，2         D. 1，3，2

24、循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（   ）。

    A. (rear-front+m)%m          B. rear-front+1     

C. rear-front-1             D. rear-front

25、在解决计算机主机和打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（   ）结构。

A. 堆栈        B. 队列        C. 数组        D. 线性表

26、栈和队列都是（   ）。

A. 链式存储的线性结构              B. 链式存储的非线性结构          

C. 限制存取点的线性结构           D. 限制存取点的非线性结构

27、在一个链队列中，假定front和rear分别为队头指针和队尾指针，删除一个结点的操作是（   ）。

A. front=front->next        B. rear= rear->next        

C. rear->next=front         D. front->next=rear

28、队和栈的主要区别是（   ）。

A. 逻辑结构不同                    B. 存储结构不同

C. 所包含的运算个数不同            D. 限定插入和删除的位置不同

二、填空题

1、设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈的容量至少应该是            。

答案：3

2、一个循环队列Q的存储空间大小为M,其队头和队尾指针分别为front和rear，则循环队列中元素的个数为：           。

答案：(rear-front+M)%M

3、在具有n个元素的循环队列中，队满时具有          个元素。

答案：n-1

4、设循环队列的容量为70，现经过一系列的入队和出队操作后，front为20，rear为11，则队列中元素的个数为           。

答案：61

5、已知循环队列的存储空间大小为20，且当前队列的头指针和尾指针的值分别为8和3，且该队列的当前的长度为_______。

三、判断题

1、栈和队列都是受限的线性结构。P

2、在单链表中，要访问某个结点，只要知道该结点的地址即可；因此，单链表是一种随机存取结构。O

3、以链表作为栈的存储结构，出栈操作必须判别栈空的情况。P

四、程序分析填空题

1、已知栈的基本操作函数：

    int InitStack(SqStack *S); //构造空栈

    int StackEmpty(SqStack *S);//判断栈空

    int Push(SqStack *S,ElemType e);//入栈

    int Pop(SqStack *S,ElemType *e);//出栈

函数conversion实现十进制数转换为八进制数，请将函数补充完整。

void conversion(){

    InitStack(S);

    scanf(“%d”,&N);

    while(N){

             （1）           ;

       N=N/8;

}

while(      （2）       ){

    Pop(S,&e);

    printf(“%d”,e);

}

}//conversion

答案：（1）Push(S,N%8)       （2）!StackEmpty(S)

2、写出算法的功能。

int  function(SqQueue *Q,ElemType *e){

    if(Q->front==Q->rear)

       return ERROR;

    *e=Q->base[Q->front];

    Q->front=(Q->front+1)%MAXSIZE;

    return OK;

}

3、阅读算法f2,并回答下列问题：

（1）设队列Q=（1，3，5，2，4，6）。写出执行算法f2后的队列Q;

（2）简述算法f2的功能。

void  f2(Queue *Q){

   DataType   e;

   if (!QueueEmpty(Q)){

     e=DeQueue(Q);

     f2(Q);

     EnQueue(Q,e);

   }

}

答案：（1）6,4,2,5,3,1                （2）将队列倒置

五、综合题

1、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列算法（用函数实现）。

答案：void EnQueue(Lnode *rear, ElemType e)

  {  Lnode *new;

     New=(Lnode *)malloc(sizeof(Lnode));

If(!new) return ERROR;

new->data=e; new->next=rear->next;

rear->next=new; rear =new;

  }

2、已知Q是一个非空队列，S是一个空栈。编写算法，仅用队列和栈的ADT函数和少量工作变量，将队列Q的所有元素逆置。

栈的ADT函数有：

void makeEmpty(SqStack s);  置空栈

void push(SqStack s,ElemType e);   元素e入栈

ElemType pop(SqStack s); 出栈，返回栈顶元素

int isEmpty(SqStack s);  判断栈空

队列的ADT函数有：

void enQueue(Queue q,ElemType e);  元素e入队

ElemType deQueue(Queue q);  出队，返回队头元素

int isEmpty(Queue q);    判断队空

答案：void QueueInvent(Queue q)

  {  ElemType x;

     makeEmpty(SqStack s);

while(!isEmpty(Queue q))

{x=deQueue(Queue q);

push(SqStack s, ElemTypex);}

while(!isEmpty(SqStack s))

{x=pop(SqStack s);

enQueue(Queue q, ElemType x);}

  }

3、对于一个栈，给出输入项A,B,C,D，如果输入项序列为A,B,C,D，试给出全部可能的输出序列。

答案：出栈的可能序列：

  ABCD  ABDC  ACDB  ACBD  ADCB  BACD  BADC  BCAD  BCDA

  CBDA  CBAD  CDBA  DCBA