队列专项练习习题
一、选择题
已知队列（13,2,11,34,41,77,5,7,18,26,15），第一个进入队列的元素是13，第五个出队列的元素是( A )
A.41 B.5 C.77 D.18
解析：第五个出队列的元素就是第五个进队列的元素
2.下列对队列的描述，正确的是（ C ）
A.队列的特点是先进后出
B.在队列中，允许插入的一端称为队首，允许删除的一端称为队尾
C.刚建立的队列，队首指针和队尾指针均为0
D.出队操作时，先将队首指针加1，然后再将队首元素出队
解析：队列的特点是先进先出，因此A选项错误；允许插入的一端称为队尾，允许删除的一端称为队首，因此B选项错误；出队操作时，先将队首元素出队，然后将队首指针加1，因此D选项错误；刚建立的队列，队首指针和队尾指针均指向下标为0的元素，即队首指针和队尾指针均为0。
3.小王在使用队列解决问题的过程中，初始时，队列为空，队列的首指针和尾指针分为为head、tail，接着小王开始进行了一系列的操作，操作序列为：入队、入队、入队、出队、入队、入队、出队、出队、出队、入队、入队，则操作结束时head和tail的值分别为（ A ）
A.4 7 B.4 8 C.5 7 D.5 8
解析：初始时，队列为空，队首指针head和队尾指针tail的值均为0，队列不为空时，队首指针指向队首元素，队尾指针指向队尾元素的下一个位置，本题中共进行了7次入队操作和4次出队操作，因此最终head和tail的值分别为4、7。
4.在汽车站候车室，信息提示屏上显示某个班车已做好准备，该车次的旅客可以检票上车。旅客q1与q2依次排队等待检票，工作人员在检票时，旅客q3,q4也排队等待检票。旅客q1检完票后准备上车，这时应该接受工作人员检票的旅客是（B）
A.q1 B.q2 C.q3 D.q4
解析：排队上车是一个队列。由于当前队列的次序为q1，q2，q3,
q4。因此q1检完票后应对q2进行检票。
5.若用能存放6个元素（索引用0-5表示）的数组来实现循环队列，当前尾指针rear和头指针front的值分别为1和5，当从队列中出队一个元素再入队两个元素后，rear和front的值分别为（B）
A.3和4 B.3和0 C.5和0 D.5和1
解析：循环队列下标n-1的后一个为0.rear指针的值为1，加入2个元素后rear指针的值需要增加2。front指针的值为5，出队一个元素需要将front指针加1。由于5为循环队列最大的下标，则其下一个脚标应为0。
6.使用有m+1个元素的列表data作为循环队列SQ的存储空间，front为队列头指针，rear为队列尾指针，则执行出队操作的语句为（D）
A.front=front+1
B.front=(front+1)%m
C.rear=(rear+1)%(m+1)
D.front=(front+1)%(m+1)
解析：出队操作需要将队首指针后移（即将队首指针值+1）。由于当前队列是一个循环队列，一共有m+1个元素，其下标为0至m。如果队首指在m处，此时出队指针值+1的话，队首指针会落在m+1处，但实际上不存在该位置，指针应该落在0处。所以队首指针+1后还需对其进行除以m+1取余操作。
7.设循环队列中数组的下标范围是1-n，其头、尾指针分别为f和r，则该队列元素个数为（D）
A.r-f B.r-f+1 C.(r-f)%n+1 D.(r-f+n)%n
解析：循环队列在经过进队、出队操作后，队首指针f与队尾指针r所指向的数值可能会产生两种情况：①fr。当fr时，r-f的值为负，当其实际数量为r-f+n。将两种情况合在一起时，其结果为（r-f+n）%n。
8.有如下程序：
qu=“thonepy”
h=5
t=4
s=“”
while h!=t:
s=s+qu[h]
h=(h+1)%len(qu)
print(s)
运行后，变量s的值为（ B ）
A.pythone B.python C.epython D.epytho
解析：此程序为循环队列的应用，队首定位在5号索引位，队尾定位在4号索引位。每次出队后，队首指针向后移动1位，当队首指针超过最后1个字符时，就要指向索引号为0的位置，因此队首指针值计算时需要对字符串长度进行取余。当队首指针与队尾指针重合时就停止出队，所以s的长度比原队列的长度少1。
9.某诊所叫号系统中，利用队列来存储当前正在排队病人的编号，head指向队首元素，tail指向队尾元素的下一个位置。若当前没有病人，则head与tail的值分别为（ C ）
A.head!=tail B.head>tail C.head==tail D.head解析：head、tail分别是队首和队尾指针，当队列为空时，指针head和tail指向同一个位置。
10.若用一个规模为8的数组来实现循环队列，且当前队头指针head与队尾指针tail的值分别为5和7，当从队列中删除一个元素，再加入两个元素后，head和tail的值分别为（ B ）
A.5和2 B.6和2 C.5和9 D.6和9
解析：本题考查的是循环队列。循环队列是首尾相连的队列，从队列中删除一个元素后，head的值为6，加入两个元素后，tail的值为2。
11.循环队列SQ（rear为队尾指针，front为队首指针，maxlen为循环队列的长度）队满的条件是（B）
A.rear==SQ B.(rear+1)%maxlen==front
C.rear==0 D.front==0
解析：在循环队列中，若队尾指针再下移1个就与队首指针重叠在一起，说明队列已满。由于是在循环队列中，队首与队尾指针的值都在0至maxlen-1之间。因此将队尾指针下移后还需要对其值进行取余操作。
12.下列程序的功能是在一个循环队列中进行入队操作，输入“+n”表示入队操作，入队元素为n，输入“-”表示出队操作，输入“@”时表示操作结束，部分程序如下：
m=int(input(‘please input m:’)) #输入队列的规模m
que=[‘’]*m
head=tail=0
data=input(‘please input data:’)
while data!=’@’:
if data[0]==”+”:
que[tail]=data[1:]
____________
则程序中划线处应填入的代码为（ C ）
A.head+=1
B.tail+=1
C.tail=(tail+1)%m
D.tail=tail%m+1
解析：循环队列中的tail指针、head指针每次移动时，都对队列元素的个数取模运算，“+”表示进行入队操作，因此划线处代码为tail=(tail+1)%m。
二、非选择题
13.小王在学习循环队列后发现循环队列的本质就是将队列空间的队列尾指针连接队列空间的队列首指针。小王想用循环单向链表表示一个循环队列，小王知道该队列的首指针head的位置，想尝试向循环队列的队尾增加一个值为x的元素。小王写了如下程序代码，请完善代码。
data=[34,21,64,23,76,54]
nextL=[5,3,4,0,1,2]
head=1
x=80
data.append(x);nextL.append(-1) #添加元素
wz=len(data)-1
_______①________
while nextL[t]!=head: #找队尾
_______②______
nextL[t]=wz
______③___________
t=h
print(data[t],end=””)
while nextL[t]!=head: #输出添加后的队列
t=nextL[t]
print(data[t],end=””)
答案：①t=nextL[head] ②t=nextL[t] ③nextL[wz]=h
解析：本题的循环队列是采用单向链表来实现的。列表data用于记录链表节点中元素的值，列表nextL用于记录当前元素的下一个元素在data列表中的存储位置。新元素要插入到单向链表的尾部，首先要找到单向链表的表尾。在本单向链表中只知道链表的表头，所以必须从表头逐一向后查找表尾，表尾的特征是它的下一个是表头。查找表头时当前指针向下移的条件为当前指针的下一个节点不是表头。找到链表尾后，需要做的工作是将尾节点的指针指向需插入的节点，插入节点的指针指向表头。队列专项练习习题
一、选择题
已知队列（13,2,11,34,41,77,5,7,18,26,15），第一个进入队列的元素是13，第五个出队列的元素是（ ）
A.41 B.5 C.77 D.18
2.下列对队列的描述，正确的是（ ）
A.队列的特点是先进后出
B.在队列中，允许插入的一端称为队首，允许删除的一端称为队尾
C.刚建立的队列，队首指针和队尾指针均为0
D.出队操作时，先将队首指针加1，然后再将队首元素出队
3.小王在使用队列解决问题的过程中，初始时，队列为空，队列的首指针和尾指针分为为head、tail，接着小王开始进行了一系列的操作，操作序列为：入队、入队、入队、出队、入队、入队、出队、出队、出队、入队、入队，则操作结束时head和tail的值分别为（ ）
A.4 7 B.4 8 C.5 7 D.5 8
4.在汽车站候车室，信息提示屏上显示某个班车已做好准备，该车次的旅客可以检票上车。旅客q1与q2依次排队等待检票，工作人员在检票时，旅客q3,q4也排队等待检票。旅客q1检完票后准备上车，这时应该接受工作人员检票的旅客是（ ）
A.q1 B.q2 C.q3 D.q4
5.若用能存放6个元素（索引用0-5表示）的数组来实现循环队列，当前尾指针rear和头指针front的值分别为1和5，当从队列中出队一个元素再入队两个元素后，rear和front的值分别为（ ）
A.3和4 B.3和0 C.5和0 D.5和1
6.使用有m+1个元素的列表data作为循环队列SQ的存储空间，front为队列头指针，rear为队列尾指针，则执行出队操作的语句为（ ）
A.front=front+1
B.front=(front+1)%m
C.rear=(rear+1)%(m+1)
D.front=(front+1)%(m+1)
7.设循环队列中数组的下标范围是1-n，其头、尾指针分别为f和r，则该队列元素个数为（ ）
A.r-f B.r-f+1 C.(r-f)%n+1 D.(r-f+n)%n
8.有如下程序：
qu=“thonepy”
h=5
t=4
s=“”
while h!=t:
s=s+qu[h]
h=(h+1)%len(qu)
print(s)
运行后，变量s的值为（ ）
A.pythone B.python C.epython D.epytho
9.某诊所叫号系统中，利用队列来存储当前正在排队病人的编号，head指向队首元素，tail指向队尾元素的下一个位置。若当前没有病人，则head与tail的值分别为（ ）
A.head!=tail B.head>tail C.head==tail D.head10.若用一个规模为8的数组来实现循环队列，且当前队头指针head与队尾指针tail的值分别为5和7，当从队列中删除一个元素，再加入两个元素后，head和tail的值分别为（ ）
A.5和2 B.6和2 C.5和9 D.6和9
11.循环队列SQ（rear为队尾指针，front为队首指针，maxlen为循环队列的长度）队满的条件是（ ）
A.rear==SQ B.(rear+1)%maxlen==front
C.rear==0 D.front==0
12.下列程序的功能是在一个循环队列中进行入队操作，输入“+n”表示入队操作，入队元素为n，输入“-”表示出队操作，输入“@”时表示操作结束，部分程序如下：
m=int(input(‘please input m:’)) #输入队列的规模m
que=[‘’]*m
head=tail=0
data=input(‘please input data:’)
while data!=’@’:
if data[0]==”+”:
que[tail]=data[1:]
____________
则程序中划线处应填入的代码为（ ）
A.head+=1
B.tail+=1
C.tail=(tail+1)%m
D.tail=tail%m+1
二、非选择题
13.小王在学习循环队列后发现循环队列的本质就是将队列空间的队列尾指针连接队列空间的队列首指针。小王想用循环单向链表表示一个循环队列，小王知道该队列的首指针head的位置，想尝试向循环队列的队尾增加一个值为x的元素。小王写了如下程序代码，请完善代码。
data=[34,21,64,23,76,54]
nextL=[5,3,4,0,1,2]
head=1
x=80
data.append(x);nextL.append(-1) #添加元素
wz=len(data)-1
_______①________
while nextL[t]!=head: #找队尾
_______②______
nextL[t]=wz
______③___________
t=h
print(data[t],end=””)
while nextL[t]!=head: #输出添加后的队列
t=nextL[t]
print(data[t],end=””)
