栈和队列
一、选择题
1．栈的特点是 B ，简称 C 的线性表；队列的特点是 A ，简称 D 的线性表。
A．先进先出 B．后进先出 C．LIFO D．FIFO 2．栈和队列的共同点是 C 。
A．都是先进后出 B．都是先进先出 C．只允许在端点处插入和删除元素 D．没有共同点
3．一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 C 。
A．edcba B．decba C．dceab D．abcde
4．设有一个栈，元素依次进栈的顺序为A、B、C、D、E。下列 B 是可能的出栈序列。
A．D,B,C,A,E B．B,C,D,E,A C．E,A,B,C,D D．E,D,C,A,B
6．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1＝n，则pi为 C 。
A．i B．n－i C．n－i＋1 D．不确定
7．设计一个判别表达式中左、右括号是否配对出现的算法，采用 D 数据结构最佳。
A．线性表的顺序存储结构 B．队列 C．线性表的链式存储结构 D．栈 9．一个队列的入队序列是1，2，3，4，则队列的输出序列是 B 。
A．4，3，2，1 B．1，2，3，4 C．1，4，3，2 D．3，2，4，1
10．判定一个循环队列qu（最多元素为MaxSize）为空的条件是 C 。
A．qu->rear – qu->front ==MaxSize B．qu->rear – qu->front -1==MaxSize C．qu->rear ==qu->front D． qu->rear =qu->front -1
11．若用一个循环队列空间大小为6，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为 B 。
A．1和5 B．2和4 C．4和2 D．5和1
12．向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行 D 操作。
A．h->next=s ; B．s->next=h ;
C．s->next=h ;h =s ; D．s->next=h->next ;h->next=s ;
13．输入序列为ABC，若用S表示入栈，X表示出栈操作，则得到CBA输出序列要经过的栈操作序列为 B 。
A． SXSXSX B． SSSXXX C． SSXSX D． SXSSXX 14．和顺序栈相比，链栈有一个比较明显的优势是 A 。
A．通常不会出现栈满的情况 B． 通常不会出现栈空的情况 C．插入操作更容易实现 D．删除操作更容易实现
15．若一个顺序栈中元素为n个,做进栈运算时发生上溢,则说明该栈的最大容量为( B )。
A. n-1 B. n C. n+1 D. n/2 17．对于循环队列 D 。
A．无法判断队列是否为空 B．无法判断队列是否为满 C．队列不可能满 D．以上说法都不对 19．队列的“先进先出”特性是指 D 。
A．最早插入队列中的元素总是最后被删除 B．当同时进行插入、删除操作时，总是插入操作优先 C．每当有删除操作时，总是要先做一次插入操作
D．每次从队列中删除的总是最早插入的元素
20．若一个循环队列，其最多元素个数为MAXSIZE，front为头指针，rear为尾指针，则判定满队列的条件是 A 。
A．(rear+1)%MAXSIZE==front B． rear+1==front
C．rear==front D．(front+1)%MAXSIZE==rear 21．队列是一种 A 的线性表。
A．先进先出 B．先进后出 C．只能插入 D．只能删除
B．3，2，5，6，4，1 D．1，5，4，6，2，3
22．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为 B 。 A．5，3，4，6，1，2
C． 3，1，2，5，4，6 条件是 B
A、ST.top-ST.base<>0 C、ST.top-ST.base<>n 栈序列是 A
A、a3,a1,a4,a2
B、 a3,a2,a4,a1
C、 a3,a4,a2,a1
D、 a4,a3,a2,a1
B、ST.top-ST.base==0 D、ST.top-ST.base==n
26．设栈ST 用顺序存储结构表示，若top、base分别为指向栈顶和栈底的指针，则栈ST 为空的
27．设有一顺序栈已经含有3 个元素，如图2.1 所示元素a4 正等待进栈。下列不可能出现的出
图2.1
28．设有一顺序栈S，若有6个元素按s1，s2，s3，s4，s5，s6 的顺序依次进栈，如果6 个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少需要的单元空间个数应该是 B 。
A、2
二、填空题（每空1分，共25分）
1． 栈 是限定仅在表的一端进行插入或删除操作的线性表，其运算遵循 后进先出 的原则。 5．设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储___ M-1__个队列元素。
6．栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__ LIFO 表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为___ FIFO __表。
7．设F和R分别表示顺序循环队列的头指针和尾指针，或F指向队头元素的前一个位置，R指向队尾元素则判断该循环队列为空的条件为 F==R 。
9.若addQ(n)表示元素n入队列Q的入队运算，delQ( )表示队列Q的出队运算，当前队列状态为空，则经过addQ(1)，addQ(2)， delQ( )，addQ(5)，addQ(7)， delQ( )，addQ(9)操作后，队头元素为 5 ，队尾元素为 9 ；若使队列中剩余元素全部出队，还需经过 3 次 delQ( ) 操作。
10.栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。
12. 设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则判断该循环队列满的条件为 (R+1)%M==F 。
B、3
C、 5
D、 6
13. 对于顺序存储结构的栈，在做入栈运算时应先判断栈是否 栈满 ；在做出栈运算时应先判断栈是否 空栈 ；当栈中元素为n个，做入栈运算时发生上溢，则说明该栈的最大容量为 n 个元素空间。
数据结构第三章栈和队列1答案
