资源简介

2023-2024学年高二上学期浙教版(2019)选修一3.2队列
一、选择题
1．有2个队列a和b，队首到队尾的元素依次分别为“5，7，9”和“6，4，8”。约定：T操作是指队列a中1个元素先出队，若大于队列b的队首元素则再入b队列，否则不入；Q操作是指队列b中1个元素先出队，若大于队列b的队尾元素则再入b队列，否则不入。则经过TTQQQQT系列操作后，队列b中的元素个数为（ ）
A．1 B．2 C．3 D．4
2．在数据结构中，队列的特点是（ ）
A．先进先出 B．先进后出 C．后进先出 D．后进后出
3．若用一个规模为8的数组来实现循环队列，且当前队头指针head和队尾指针tail的值分别为5和7，当从队列中删除一个元素，再加入两个元素后，head和tail的值分别为（ ）
A．5和1 B．6和1 C．5和9 D．6和9
4．在某餐厅点餐系统中， 利用队列来储存当前正在排队顾客的编号，head 指向队首元素，tail 指向队尾元素的下一个位置， 若 tail=head+3，则现在排队的顾客数量为（ ）
A．2 B．3 C．4 D．5
5．某已知队列元素的的个数为5，则队首指针head和队尾指针（指向队尾一个元素的后一个位置）tail的值不可能是（ ）
A．head=1, tail=6 B．head=6, tail=1 C．head=2, tail=3 D．head=3, tail=2
6．栈和队列的共同特点是（ ）
A．都是线性表 B．都只允许在表的一端进行插入或删除
C．操作受限的线性表 D．允许在两端进行插入和删除
7．某队列使用head记录队首元素所在的位置，tail记录队尾元素的下一个位置，若head=4，tail=8，则该队列中元素的个数是（ ）
A．3 B．4 C．5 D．8
8．有一个非循环队列S如图所示，其中指针head指向队首元素的位置，指针tail指向队尾元素的下一个位置。
关于该队列说法正确的是（ ）
A．队列中元素个数为tail-head+1 B．新元素入队时，指针head向右移动
C．元素出队时，指针tail向右移动 D．当tail==len（S）时，无法再入队新元素
9．某队列中存有12张扑克牌，如题图所示，游戏规则如下：①取队首扑克牌，然后加入到队尾，②打出队首扑克牌；重复①、②两个操作，直到队列为空。
若要根据上述规则用扑克牌打出“一条龙”游戏（注：总共13张牌，从队列中出牌的次序为“A2345678910JQK” ）。请你设计游戏，将扑克牌“10”放到初始队列中正确的位置（ ）
A．放置在扑克牌6的后面 B．放置在扑克牌5与扑克牌K之间
C．放置在扑克牌2与扑克牌8之间 D．以上说法均错误
10．某队列经过“出队”“入队”操作后，队首指针head=2，队尾指针tail=6，则该队列中剩余的元素个数是（ ）
A．2 B．4 C．5 D．6
11．队列Q初始从队首到队尾分别是abc，栈S中有de，e为栈顶。约定：操作1是指一个元素出栈后入队，操作2是指一个元素出队后再入队。经过21221系列操作后，队列中队首到队尾的元素依次为素（ ）
A．aebcd B．edabc C．aedcb D．cbde
12．假设队列空间足够，队列中的元素个数为5。约定：T为入队操作，Q为出队操作，则经过TTQQTQTQQ
一系列操作之后，队首指针head，队尾指针tail的值可能为（ ）
A．head=11，tail=7 B．head=7，tail=11 C．head=9，tail=12 D．head=12，tail=9
13．有如下Python程序段：
st = [″h″,″a″,″p″,″*″,″p″,″Y″]
que = [0]*20; key = 2
head,tail = 0, 0
for i in range (len(st)):
if ″a″ <= st[i] <= ″z″:
que[tail] = chr((ord(st[i]) - ord(″a″) + key)%26 + ord(″a″))
tail += 1
else:
head += 1
while head != tail:
print (que[head],end =″ ″)
head += 1
程序运行后，输出的结果是（ ）
A．r r B．p p C．c r r a D．c r r A
14．队列属于（ ）
A．线性结构 B．树结构 C．图结构 D．以上均不是
15．用列表模拟队列对数据进行操作，python程序如下
a=[3,4,5,6,7]
head=0;tail=len(a)
a+=[0]*100
while head+2<=tail:
if a[head]%2==0
a[tail]=a[head]//2
head+=1;tail+=1
elif a[head]<=5:
head+=1
else:
a[head]-=5
print(a[head])
程序运行后输出的结果是（ ）
A．0 B．1 C．2 D．3
二、填空题
16．队列是一种有限制的 结构。特点是数据元素只能在 依次添加（称为进队），在另一端依次删除（称为 ）。
17．在数据结构中， 是一种特殊的线性表，只允许在表的两端进行插入和删除操作。
18．在计算机编程中， 是一种用于存储和管理数据的集合，它允许数据项以有序的方式添加和删除。
三、操作题
19．为鼓励绿色出行，某市推出了优惠方案：乘一次地铁后可以获得一张优惠券，在有效期45分钟内(含)可免费搭乘一次公交车。有效期指乘公交车与乘地铁的开始时刻之差。搭乘公交车时，可以使用优惠券则一定会使用，如果有多张优惠券满足条件，则优先消费获得最早的优惠券。有人用Python编写程序计算出行的费用。他的某次出行过程如图a所示，程序运行结果如图b所示。

请回答下列问题：
（1）请在划线处填入合适的代码。
def Ctime(t):
# 自定义函数Ctime功能为将时间转为分钟计存入变量s，代码略。
return s
'''
读取出行记录，存储在列表a中，a[i][0]、a[i][1]、a[i][2]依次存储交通工具类型、票价、乘坐开始时刻。交通工具类型a[i][0]值为0表示地铁，1表示公交车。代码略。
'''
n = len(a)
for i in range(n):
a[i][2] = Ctime(a[i][2])
for i in range(n - 1):
for j in range(n - 1, i, -1):
a[j], a[j - 1]= a[j - 1], a[j]
# 输出出行记录，代码略。
total = 0
head = tail = 0
q = [-1] * n
for i in range(n):
if a[i][0] == 0:
total += a[i][1]
tail += 1
else:
while head < tail and q[head] < a[i][2] - 45:
head += 1
if :
total += a[i][1]
else:
print(a[i][2],"时刻使用了优惠券")
print("总共花费为:", total)
（2）程序中加框处代码有错，请改正。
（3）该程序主要应用的数据结构类型是 (选填：队列 / 栈 / 链表 / 二叉树)。
20．杨辉三角，是二项式系数在三角形中的一种几何排列，其最左侧一列数字和右边的斜边数字均为1，内部其他位置上的每个数字均为上一行同一列数字与上一行前一列数字之和，前8行的杨辉三角如第图a所示。
图a杨辉三角 图b三角形数垒
（1）如果用数据结构中的队列构建杨辉三角，编写输出前n行杨辉三角的python程序代码如下，请在程序划线处填入合适的代码。
n=int(input("输入行数:"))
que=[0]*1000
head=tail=0
que[tail]=1
print(que[tail]);tail=tail+1
for i in range(2,n+1):
print(que[tail],end="");tail=tail+1
for j in range(① ):
que[tail]=②
print(que[tail],end="");tail=tail+1
head=head+1
print(que[tail]);tail=tail+1
③
（2）三角形数垒（如图b所示），是杨辉三角的变形，与杨辉三角不同的是最左侧一列数字和右边的斜边数字均为1、2…n。若要使得程序能输出三角形数垒，可通过将第（1）小题程序中的两条加框语句que[tail]=1都修改为 实现。
（3）在上述程序中，给队列que分配的最大空间为1000，存在空间浪费问题。为了提高空间利用效率，小北将队列que改为了循环队列，即将第2条语句que=[0]*1000修改为que=[0]*n，同时将程序中所有的head=head+1和tail=tail+1进行了修改，其中head=head+1应修改为 。
参考答案：
1．B
2．A
3．B
4．B
5．C
6．C
7．B
8．D
9．A
10．B
11．A
12．B
13．A
14．A
15．C
16． 线性数据 队尾 出队
17．队列
18．队列
19． q[tail]=a[i][2] head==tail 或 q[head]==-1 head+=1 a[j][2] < a[j - 1][2] 队列
20． i-2 或 1，i-1 que[head]+que[head+1] head=head+1 que[tail]=i head=(head+1)%n

展开更多......

收起↑