文档库 最新最全的文档下载
当前位置:文档库 › 第3章 栈和队列

第3章 栈和队列

第3章 栈和队列
第3章 栈和队列

第三章栈和队列

基本概念

1、栈的定义、特点

2、顺序栈和链栈的进栈和退栈操作;栈空和栈满的判定条件

3、队列的定义和特点

4、循环队列、链队列的出队和入队操作、判定队列为空、队列为满的条件

一、选择题

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 大小为6的数组:下标从0-5;从前面出队,从后面入队

front(前面)=3

rear(后面)=0

当出队列中删除一个元素,也就是出队,即front+1:=4

再插入两个元素,即rear+2= 2

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 )。

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、设计一个判别表达式中左右括号是否配对出现的算法,采用( C )数据结构最佳。

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

B. 队列

C. 栈

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

21、当用大小为N的数组存储顺序循环队列时,该队列的最大长度为(C )。

A. N

B. N+1

C. N-1

D. N-2

22、队列的删除操作是在( A )。

A. 队首

B. 队尾

C. 队前

D. 队后

23、若让元素1,2,3依次进栈,则出栈次序不可能是( C )。

A. 3,2,1

B. 2,1,3

C. 3,1,2

D. 1,3,2

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

A. (rear-front+m)%m

B. rear-front+1

C. rear-front-1

D. rear-front

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

A. 堆栈

B. 队列

C. 数组

D. 线性表

26、栈和队列都是(C )。

A. 链式存储的线性结构

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

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

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

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

A. front=front->next

B. rear= rear->next

C. rear->next=front

D. front->next=rear

28、队和栈的主要区别是( D )。

A. 逻辑结构不同

B. 存储结构不同

C. 所包含的运算个数不同

D. 限定插入和删除的位置不同

2. 栈结构通常采用的两种存储结构是____。

A. 顺序存储结构和链式存储结构

B. 散列方式和索引方式

C. 链表存储结构和数组

D.线性存储结构和非线性存储结构

4. 判定一个顺序栈ST(最多元素为m0)为空的条件是____。

A. top !=0

B. top= =0

C. top !=m0

D. top= =m0-1

5. 判定一个顺序栈ST(最多元素为m0)为栈满的条件是____。

A. top!=0

B. top= =0

C. top!=m0

D. top= =m0-1

7. 向一个栈顶指针为HS的链栈中插入一个s所指结点时,则执行__ __。

(不带空的头结点)

A.HS—>next=s;

B. s—>next= HS—>next; HS—>next=s;

C. s—>next= HS; HS=s;

D. s—>next= HS; HS= HS—>next;

8. 从一个栈顶指针为HS的链栈中删除一个结点时,用x保存被删结点的值,则执行__ __。(不带空的头结点)

A. x=HS; HS= HS—>next;

B. x=HS—>data;

C. HS= HS—>next; x=HS—>data;

D. x=HS—>data; HS= HS—>next;

10. 判定一个循环队列QU(最多元素为m0)为空的条件是____。

A. rear - front= =m0

B. rear-front-1= =m0

C. front= = rear

D. front= = rear+1

11. 判定一个循环队列QU(最多元素为m0, m0= =Maxsize-1)为满队列的条件是____。

A. ((rear- front)+ Maxsize)% Maxsize = =m0

B. rear-front-1= =m0

C. front= =rear

D. front= = rear+1

13. 栈和队列的共同点是____。

A. 都是先进后出

B. 都是先进先出

C. 只允许在端点处插入和删除元素

D. 没有共同点

二、填空题

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

答案:3

设栈长度为s,起始为0

因为栈后进先出,队列先进先出。

又因为元素E1.。E6是顺序入栈,那么分析过程如下:

按照出栈过程分析,因为给定出栈顺序:E2,E4,E3,E6,E5,E1,

E2要进栈,所以E1必须进栈,进栈顺序:E1,E2,所以s为2

下面E2出栈,打印出E2,剩余结果为E4,E3,E6,E5,E1,

因为E2出栈了,所以当前栈容量为2,但是只是用了1个,存放E1,下面继续

E3进栈,E4进栈,此时s为3,根据出栈结果,那么E4出栈,E3出栈,此时栈容量为3 但是只有E1在栈中,剩余结果为E6,E5,E1,

同理,E5进栈,E6进栈,此时栈被填满,容量为3,后E6出栈,E5出栈,E1出栈,栈空,容量为3.所以S的容量至少为3.

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

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

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

答案:n-1

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

答案:61

元素数量=

(rear+max-front) 当front > rear

(front+max-rear) 当rear > front

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

三、判断题

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

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

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

四、程序分析填空题

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,试给出全部可能的输出序列。4,1,4,1,2,1,1

答案:出栈的可能序列:

ABCD ABDC ACDB ACBD ADCB BACD BADC BCAD BCDA BDCA

CBDA CBAD CDBA DCBA

16. 有一字符串序列为5*-x-y/x+2,利用栈的运算将其输出结果变为5x-*yx+/-2,试写出该操作的入栈和出栈过程(采用push(a)表示a入栈,pop(a)表示a出栈)。

相关文档