栈和队列练习

A 一、选择题 1.栈结构通常采用的两种存储结构是（ ）。 A．顺序存储结构和链表存储结构 B．散列方式和索引方式 C．链表存储结构和数组 1.栈结构通常采用的两种存储结构是（ ）。 A．顺序存储结构和链表存储结构 B．散列方式和索引方式 C．链表存储结构和数组 D．线性链表结构和非线性存储结构 A

D 2.在栈操作中，输入序列为（A，B，C，D），不可能得到的输出数列是（ ）。 A．（A，B，C，D） B．（D，C，B，A） C．（A，C，D，B） D．（C，A，B，D） D

B 3.设栈ST用顺序存储结构表示，则栈ST为空的条件是（ ）。 A．ST.top-ST.base<>0　　　　B．ST.top-ST.base==0 C．ST.top-ST.base<>n　　　　D．ST.top-ST.base==n B

C 4.向一个栈顶指针为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; C

C 5.从一个栈顶为HS的链接中删除一个结点，用x保存被删结点的值，则执行（ ）。 A．x=HS;HS=HS->next; B．HS=HS->next;x=HS->data; C．x=HS->data;HS=HS->next; D．s->next=HS;HS=HS->next; C

6.表达式a*(b+c)-d的后缀表达式是（　）。 A．abcdd+- B．abc+*d- C．abc*+d- D．-+*abcd B

D 7.中缀表达式A-(B+C/D)*E的后缀形式是（ ）。 A．AB-C+D/E* B．ABC+D/E* C．ABCD/E*+- D．ABCD/+E*- D

B 8.一个队列的入列序列是1，2，3，4，则队列的输出序列是（ ）。 A．4, 3, 2, 1 B．1, 2, 3, 4 8.一个队列的入列序列是1，2，3，4，则队列的输出序列是（　　　）。 A．4, 3, 2, 1 B．1, 2, 3, 4 C．1, 4, 3, 2 D．3, 2, 4, 1 B

9.循环队列SQ采用数组空间SQ.base[0,n－1]存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列Q为空的条件是（　　　）。 A．Q.rear-Q.front==n B．Q.rear-Q.front-1==n C．Q.front==Q.rear D．Q.front==Q.rear+1 C

10.循环队列SQ采用数组空间SQ.base[0,n－1]存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列Q为满队列的条件是（　　　）。 A．Q.front==Q.rear B．Q.front!=Q.rear C．Q.front==(Q.rear+1)%n D．Q.front!=(Q.rear+1)%n C

11.若在一个大小为6的数组上实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（　　　）。 A．1和5 B．2和4 C．4和2 D．5和1 A

12.用单链表表示的链式队列的队头在链表的（　　　）位置。 A．链头 B．链尾 C．链中 A

A 13.判定一个链队列Q（最多元素个数为n）为空的条件是（ ）。 A．Q.front==Q.rear B．Q.front!=Q.rear C．Q.front==(Q.rear+1)%n D．Q.front!=(Q.rear+1)%n A

B 14.在链队列Q中，插入s所指结点需顺序执行的指令是（ ）。 A．Q.front->next=s;f=s; B．Q.rear->next=s;Q.rear=s; C．s->next=Q.rear;Q.rear=s; D．s->next=Q.front;Q.front=s; B

C 15.在一个链队列Q中，删除一个结点需要执行的指令是（ ）。 A．Q.rear=Q.front->next; B．Q.rear->next=Q.rear->next->next; C．Q.front->next=Q.front->next->next; D．Q.front=Q.rear->next; C

D 16.用不带头结点的单链表存储队列，其对头指针指向对头结点，对尾指针指向队尾结点，则在进行出队操作时（ ）。 A．仅修改队头指针 16.用不带头结点的单链表存储队列，其对头指针指向对头结点，对尾指针指向队尾结点，则在进行出队操作时（　　　）。 A．仅修改队头指针 B．仅修改队尾指针 C．队头、队尾指针都要修改 D．队头、队尾指针都可能要修改 D

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

B 18.消除递归（ ）需要使用栈。 A．一定 B．不一定

二、填空题 1.栈的特点是＿＿＿＿＿＿，队列的特点是＿＿＿＿＿＿。 先进后出； 先进先出

2.线性表、栈和队列都是＿＿＿＿＿＿结构，可以在线性表的＿＿＿＿＿＿位置插入和删除元素；对于栈只能在＿＿＿＿＿＿位置插入和删除元素；对于队列只能在＿＿＿＿＿＿插入和在＿＿＿＿＿＿删除元素。 任何 栈顶 队尾 队首

stack 3.有程序如下，则此程序的输出结果（其中栈的元素类型SelemType为char）是＿＿＿＿＿＿。 void main() char x,y; initstack (s); x=’c’;y=’k’; push(s,x);push(s,’a’);push(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); } stack

4.在栈顶指针为HS的链栈中，判定栈空的条件是＿＿＿＿＿＿。 HS==NULL

存入元素 5.向栈中压入元素和操作是先＿＿＿＿＿＿，后＿＿＿＿＿＿。 移动栈顶指针

6.对栈进行退栈时的操作是先＿＿＿＿＿，后＿＿＿＿＿＿。 移动栈顶指针 取出元素

7.用循环链表表示和队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是＿＿和＿＿；若只设尾指针，则出队和入队的时间复杂度分别是＿＿和＿＿。 1 1 1

8.从循环队列中，删除一个元素时，其操作是＿＿＿＿＿＿。 先取出元素，后移动队尾指针

9.在一个循环队列中，队首指针指向队首元素的＿＿＿＿＿＿。 前一个位置

10.在具有n 个单元的循环队列中，队满时共有＿＿＿＿＿＿个元素。

11.在HQ的链队列中，判定只有一个结点的条件是＿＿＿＿＿＿＿＿＿＿＿＿ 。 HQ.front==HQ.rear

12.设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f依次通过栈S，一个元素出栈后即进入队列Q，若这6个元素出队列的顺序是b、d、c、f、e、a则栈S的容量至少应该是＿＿＿＿＿＿。 3

char 13.有程序如下，则此程序的输出结果（其中队列的元素类型QSelemType为char）是＿＿＿＿。 void main() { char x=’e’;y=’c’; enqueue(q,’h’);enqueue(q,’r’);enqueue(q,y); dequeue(q,x);enqueue(q,x); dequeue(q,x);enqueue(q,’a’) while(!queueempty(q)) {dequeue(q,y);printf(y);} Printf(x); } char

18 14.有如递归函数： 执行语句printf(“%d\n”,dunno(3));的结果是 ＿＿＿＿＿＿。 int dunno(int m) { int value; if(m==0) value=3; else value=dunno(m-1)+5; return(value); } 执行语句printf(“%d\n”,dunno(3));的结果是 ＿＿＿＿＿＿。 18

15.设a 是含有N个分量的整数数组，写出求n个整数之和的递归定义＿＿＿＿＿＿，写出个整数之积的递归定义＿＿＿＿＿＿。 f(n)= f(n-1)+a[n] n≥1 a[0] n=1 g(n)= g(n-1)*a[n] n≥1

OK