数据结构专项精讲课程讲义-第三部分-第4章队列.pdfVIP

数数据据结结构构专专项项精精讲讲课课程程讲讲义义-第第三三部部分分-第第4章章队队列列

⼀选择题

1.假设以数组A[m]存放循环队列的素,其头尾指针分别为front和rear，则当前队列中的素个数为（A）。

A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m2.循环队列A[0..m-1]存放其素值，⽤front和

rear分别表⽰队头和队尾，则当前队列中的素是(A)。

A.(rear-front+m)%m

B.rear-front+1

C.rear-front-1

D.rear-front

3.循环队列存储在数组A[0..m]中，则⼊队时的操作为（D）。

A.rear=rear+1

B.rear=(rear+1)mod(m-1)

C.rear=(rear+1)modm

D.rear=(rear+1)mod(m+1)

4.若⽤⼀个⼤⼩为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除⼀个素，再加⼊两个素

后，rear和front的值分别为多少？(B)

A.1和5

B.2和4

C.4和2

D.5和1

5.⽤单链表表⽰的链式队列的队头在链表的（A）位置。

A．链头B．链尾C．链中

⼆判断题

1.队列是⼀种插⼊与删除操作分别在表的两端进⾏的线性表，是⼀种先进后出型结构。（）

2.通常使⽤队列来处理函数或过程的调⽤。（）

3.队列逻辑上是⼀个下端和上端既能增加⼜能减少的线性表。（√）

4.循环队列通常⽤指针来实现队列的头尾相接。（）

5.循环队列也存在空间溢出问题。（√）

6.队列和栈都是运算受限的线性表，只允许在表的两端进⾏运算。（）

7.栈和队列都是线性表，只是在插⼊和删除时受到了⼀些限制。（√）

三应⽤题

1.简要叙述循环队列的数据结构，并写出其初始状态、队列空、队列满时的队⾸指针与队尾指针的值。

解：

typedefstructnode

{elemtypeelemcq[m];//m为队列最⼤可能的容量。

intfront,rear;//front和rear分别为队头和队尾指针。

}cqnode;

cqnodecq;

(1)初始状态

cq.front=cq.rear=0;

(2)队列空

cq.front==cq.rear;

(3)队列满

(cq.rear+1)%m==cq.front;

2.设⼀个双端队列，素进⼊该队列的次序为a，b，c，d。求既不能由输⼊受限的双端队列得到,⼜不能由输出受限的双端队

列得到的输出序列。

答：既不能由输⼊受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是dbca

分析：

4个输⼊受限有：cdba，dacb，dabd，dcab

4个输出受限有：cdba，dacb，dbac，dcab

既不能由输⼊受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是dbca。

3.若以1、2、3、4作为双端队列的输⼊序列，试分别求出以下条件的输出序列：

（1）能由输⼊受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；

（2）能由输出受限的双端队列得到，但不能由输⼊受限的双端队列得到的输出序列；

（3）既不能由输⼊受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。

答：4个输⼊受限有：4321，4123，4132，4312

4个输出受限有：4321，4123，4213，4312

（2）能由输出受限的双端队列得到，但不能由输⼊受限的双端队列得到的输出序列；

答：4个输出受限有：4321，4123，4213，4312

4个输⼊受限有：4321，4123，4132，4312

（3）既不能由输⼊受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。答：输出受限与输⼊受限都得不到

4231。

试题分析：若以1234作为双端队列的输⼊序列.问:能由输⼊受限的双端队列得到,但是不能由输出受限的双端队列得到的输出序

列是什么?

双端队列确是好像两个栈底靠在⼀起的栈，但这两个栈底⼜是互通的。它确是很灵活，因此不可能出现的出队的序列只可能是

四个车厢都已经⼊队的情况，因为如果队列中只有1

个或2个或3个都是能调度过来的，但当4个都进去之后就受⼀定限制了，对于输⼊受限的双端队列此时队列中车厢的排列必定

是123