第3章习题（带答案）

1.链式栈与顺序栈相比，一个比较明显的优点是 ( )。 A. 插入操作更加方便 C. 不会出现栈空的情况

B. 通常不会出现栈满的情况 D. 删除操作更加方便

2.在一个顺序存储的循环队列中，队头指针指向队头元素的 ( )。 A. 前一个位置

B. 后一个位置

D. 队尾元素的前一位置

C. 队头元素位置

3.设S表示进栈，X表示出栈，则将CABDB执行操作序列SSXXSSXXSX后得到 ACDBB 。

4.设循环队列中数组的下标范围是0至m-1，其头尾指针分别为f和r,则其元素个数为 。

A. r-f B. r-f+1 C. (r-f)%m+1 D. (r-f+m)%m

5.判定一个循环队列Q（数组元素为m0个）队满的条件为 。 A．Q.front==Q.rear B. Q.front!=Q.rear C. Q.front==(Q.rear+1)%m0 D. Q.front!=(Q.rear+1)%m0

6.长度为m的循环队列q的队满条件为 q.front==(q.rear+1)%m ，队空条件为 q.front==q.rear。

7.队列是一种特殊的线性表，它的特点是后进先出。（ 错 ）

8.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（对） 9. 循环队列采用的存储结构为 顺序存储结构 ，其引入的目的是为了克服__假溢出的现象 _____。

10.有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）

A. 543612 B. 453126 C. 346521 D. 234156

11. 栈和队列都是线性表，只是在插入和删除时受到了一些限制。（对） 12. 链栈通常不会出现满的情况。（对）

13.往顺序栈中插入一个元素时，栈顶指针是( )。

A) 加1

B) 减1

C) 不变 D) 清0

14.栈和队列的共同点是( )。

A)都是先进后出 B)都是先进先出 C)只允许在端点处插入和删除元素 D)没有共同点

15.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印缓冲区，主机将要打印的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据，该缓冲区的逻辑结构应该是：

A.栈 B. 图 C.树 D. 队列

16.线性表、栈和队列都是( 线性 )结构，可以在线性表的( 任意 )位置插入和删除元素；对于栈只能在( 栈顶 )插入和删除元素；对于队列只能在( 队尾 )插入和( 队头 )删除元素。

17.设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是( )。

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

18.在具有n个单元的循环队列中，队满时共有( n-1 )个元素。 19．若一个栈的输入序列为1，2，…，100，则其输出序列的第2个元素为100的输出序列的种数是 99 。

20．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。

A. 不确定 B. n-i+1 C. i D. n-i

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

A、1，5 B、2, 4 C、4，2 D、5，1

22．栈的特点是___先进后出____，队列的特点是___先进先出__________。 23．引起循环队列队尾位置发生变化的操作是( )。

A.入队列 B.出队列 C.取队尾元素 D.取队头元素

24．设循环队列Q采用顺序存储结构，其最大存储容量为MAX，其头指针和尾指针分别为Q.front和Q.rear，则队列Q为空的条件为 _ Q.front==Q.rear，队列为满的条件为____ Q.front==(Q.rear+1)%MAX__________。 25．在栈中，出栈操作的时间复杂度为( )。 A.O(log2n) B.O(1) C.O(n) D.O(n2) 26．引起循环队列队头位置发生变化的操作是( )。

A.出队列 B.入队列 C.取队头元素 D.取队尾元素 27．在栈中，入栈操作的时间复杂度为( )。

A.O(n) B.O(n) C.O(log2n) D.O(1) 28、栈结构通常采用的两种存储结构是（ ）。

A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构

29、设栈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

30、向一个栈顶指针为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;

31、从一个栈顶指针为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; 32、消除递归（ ）需要使用栈。 A、一定 B、不一定

33、用单链表表示的链式队列的队头在链表的（ ）位置 A、链头 B、链尾 C、链中

34、判定一个链队列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

35、在链队列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; 36、在一个链队列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;

2

本文来源：https://www.bwwdw.com/article/pozv.html