资源简介

二、 队列及其基本操作
1. 有如下Python程序段:
from random import randint
q = [1,2,14,5,6,7,9,10]
head = 0; tail = len(q)－ 1
ans = 0
m = randint(1,3)
q ＋= [0] * m
for i in range(m):
　for j in range(2 ** i － 1):
　　　head ＋= 1
　ans ＋= q[head]
　q[tail] = q[head]
　head ＋=1; tail ＋= 1
执行该程序段后,变量ans的值不可能是(　D　)
A. 1 B. 15
C. 24 D. 34
【解析】 本题考查队列的操作知识。当m为1时,i只取0,此时队列头元素为1,ans为1。当m为2时,i分别取0,1,为0时ans为1;当i为1时j为1,出队一次(2出队),队头元素是14,ans为15(14＋1)。当m为3时,分析i取2时,j为3,此时5、6、7依次出队,队头是9,ans为24(15＋9)。所以ans的值不可能是34,D符合题意。
2. 下列关于队列的说法,正确的是(　C　)
A. 队列的特点是先进后出
B. 在队列中,允许插入的一端称为队首,允许删除的一端称为队尾
C. 刚建立的队列,队首指针和队尾指针均为0
D. 出队操作时,先将队首指针加1,再让队首元素出队
【解析】 队列的特点是先进先出,A错误;允许插入的一端称为队尾,允许删除的一端称为队首,B错误;出队操作时,先将队首元素出队,然后将队首指针加1,D错误;刚建立的队列,队首指针和队尾指针均指向下标为0的元素,即队首指针和队尾指针均为0,C正确。
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,A正确。
4. 在汽车站候车室,信息提示屏上显示某个班车已做好准备,该车次的旅客可以检票上车。旅客q1与q2依次排队等待检票,工作人员在检票时,旅客q3、q4也排队等待检票。旅客q1检完票后准备上车,这时应该接受工作人员检票的旅客是(　B　)
A. q1 B. q2
C. q3 D. q4
【解析】 排队上车是一个队列。当前队列的次序为q1,q2,q3,q4。因此旅客q1检完票后应对旅客q2进行检票,B正确。
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,即为3。front指针的值为5,出队一个元素需要将front指针加1。由于5为循环队列最大的下标,则其下一个下标应为0。B正确。
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取余操作。D正确。
7. 有如下Python程序段:
import random
s = AB#C#D#
q = [ ]*len(s)
head = tail = 0
ans =
for i in range(len(s)):
　　op=random.randint(0,1)
　　　　(1)　　
　　if 　　(2)　　 and 　　(3)　　:
　　　　q[tail] = s[i]; tail ＋= 1; 　　(4)　　
　　elif 　　(5)　　 and head != tail and 　　(6)　　:
　　　　ch = q[head]; head ＋= 1
　　ans ＋= ch
print(ans)
执行该程序段后,输出结果为 0B#0A0C 。上述程序段方框处可选代码如下:
①ch == # 　②ch != # 　③op == 0　④op == 1　⑤ch = s[i]　⑥ch = str(op)
则(1)至(6)处代码依次是(　B　)
A. ⑤③①⑥②④ B. ⑤③②⑥①④
C. ⑥①④⑤②③ D. ⑥③①⑤④②
【解析】 本题考查队列的相关操作以及代码的分析理解能力。本题可以利用代码特点,采用排除法、结合逻辑推理可以较快得出正确答案。由于输出结果中有字符‘0’,而字符串s中是没有这个字符的,那么(4)处的代码必定是⑥ch=str(op),此时也必有条件③op ==0。(1)处只能是⑤ch=s[i],C、D错误。再分析第二个字符‘B’,如字符‘B’一旦入队,那么结果ans中,字符‘A’一定在‘B’之前,所以此时不能满足入队条件。那么入队条件之一是:①ch == # ,另外一个条件是:④op ==1,A错误,B正确。
8. 有如下Phython程序段:
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。B正确。
9. 在某银行排队叫号系统中,利用队列来储存当前正在排队顾客的编号,head指向队首元素,tail指向队尾元素的下一个位置。若现在队列的顾客数量为4,关于head和tail的关系,下列说法中正确的是(　D　)
A. head=tail＋3 B. head=tail＋4
C. tail=head＋3 D. tail=head＋4
【解析】 本题考查队列知识。head指向队列的第一个元素,tail指向队列元素的下一个元素,假设当队列为空时,head和tail都指向0,此时队列中的顾客数量为4,相当于执行了4次入队操作,此时tail的值为 4,则tail=head＋4。D正确。
10. 若用一个规模为8的数组来实现循环队列,且当前队头指针head与队尾指针tail的值分别为5和7。当从队列中删除一个元素,再加入两个元素后,head和tail的值分别是(　B　)
A. 5和2 B. 6和1
C. 5和9 D. 6和9
【解析】 本题考查循环队列。循环队列是首尾相连的队列,从队列中删除一个元素后,head的值为6,加入两个元素后,tail的值为1。B正确。
11. 循环队列SQ(rear为队尾指针,front为队首指针,maxlen为循环队列的长度)队满的条件是(　B　)
A. rear=SQ B. (rear＋1)%maxlen=front
C. rear=0 D. front=0
【解析】 在循环队列中,若队尾指针再下移1个位置就与队首指针重叠在一起,说明队列已满。由于是在循环队列中,队首与队尾指针的值都在0至maxlen－1之间。因此将队尾指针下移后还需要对其值进行取余操作。B正确。
12. 在一个循环队列中进行入队操作,输入“＋n”表示入队操作,入队元素为n,输入“－”表示出队操作,输入“@”表示操作结束。实现上述功能的Python程序如下:
m=int(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,C正确。
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
①　t=nextL[head]　
while nextL[t]!=head:　　#找队尾
　　②　t=nextL[t]　
nextL[t]=wz
③　nextL[wz]=head　
t=head
print(data[t],end=" ")
while nextL[t]!=head:　　#输出添加后的队列
　　　t=nextL[t]
print(data[t],end=" ")
【解析】 本题的循环队列是采用单向链表来实现的。列表data用于记录链表节点中元素的值,列表nextL用于记录当前元素的下一个元素在data列表中的存储位置。新元素要插入到单向链表的尾部,首先要找到单向链表的表尾。在本单向链表中只知道链表的表头,所以必须从表头逐一向后查找表尾,表尾的特征是它的下一个是表头。查找表头时,当前指针向下移的条件为当前指针的下一个节点不是表头。找到链表尾后,需要做的工作是将尾节点的指针指向需插入的节点,插入节点的指针指向表头。
14. 某英文逐词翻译软件,不区分大小写。为了加快翻译速度,在翻译的过程中,软件会将最近出现过的一些单词存入内存。若内存中有该单词,则直接翻译,否则查外存词典并将该单词存入内存。内存中每个单元存储一个单词,存满时会清空最早进入内存的单词,腾出单元存放新单词。编程模拟软件的翻译过程:输入一个仅含英文、逗号或空格字符的英语句子,以句号结束,计算翻译软件需要去外存查找多少次词典。在翻译开始前,内存中没有任何单词。运行界面如图所示。请回答下列问题:
请输入内存容量:5
请输入英语句子:If you have an apple and I have an apple,we both have one apple.
需要去外存查找12次词典
(1)若上图中的内存容量改为7,则需要去外存查找　10　次词典。
(2)实现上述功能的Python程序如下,请在画线处填入合适的代码。
m=int(input("请输入内存容量:"))
s=input("请输入英语句子:")
dic={}
head = tail = 0
word =
for ch in s:
　　if ch ==" " or ch ==","or ch ==".":
　　　　if word not in dic or ①　dic[word]< head　:
　　　　　　　if tail － head == m:
　　　　　　　　　head = head ＋ 1
　　　　　　　dic[word]= tail
　　　　　　　tail ＋=1
　　　　　　　word =""
　　else:
　　　　if "A"<= ch <= "Z"
　　　　　　ch =②　chr(ord(ch)＋32)或ch.lower()　
　　　　word ＋= ch
print("需要去外存查找",③　tail或str(tail)　,"次词典")
【解析】 本题考查队列及字符串知识。(1)经过模拟可知,最后队列当中的单词是apple and I we both one,共7＋3=10次。(2)①此处是对扫描到的word单词进行判断,如果是首次出现,则需要翻译,否则判断是否存在于内存中;结合代码dic[word]=tail,可判断出首次出现过的单词若出队,则dic[word]应小于head。②根据题意不区分大小写,很明显此处是大写转换成小写,故chr(ord(ch)＋32)。③由代码dic[word]=tail可知,每次翻译的word对应入队的位置。第一个word对应的是0,第二个word对应的是1,最后一个word对应的是tail;又由代码tail＋=1可知,最后一个单词翻译完毕之后,tail本身已经加1,所以翻译次数就是tail。
15. 某货运码头采用了智能卸货引导系统,系统将根据一天内所有货轮的到达时间与装载的集装箱数量综合排序,将到达时间早的货轮排在前面,若到达时间相同,则将集装箱数量少的货轮排在前面。排序之后,假设有k个吊桥进行卸货,当有吊桥空闲时,下一艘到达的货轮将会被系统安排至编号最小的空闲吊桥;当没有吊桥空闲时,下一艘到达的货轮将会被系统安排至等待时间最少的吊桥,若有多个吊桥的等待时间均为最少,货轮也会被安排至编号最小的吊桥。一个吊桥在单位时间内能卸下一个集装箱,且不计其他时间损耗,涉及的所有时间均以单位时间计算。现编程模拟上述过程,输出当天所有货轮卸完货所需的时间,以及所有货轮中最久等待时间。实现上述功能的Python代码如下:
# 货轮信息列表s,子列表的数据分别为[到达时间,集装箱数量]
s = [[31, 2], [10, 5], [2, 10], [10, 3], [1, 61], [30, 18], [0, 20], [31, 25], [1, 15]]
k = int(input( 请输入吊桥数量: ))
time = [0 for i in range(k)]
max_waittime = 0
def order(a, b):
　　if a[0] < b[0]:
　　　　①　return False　
　　if a[0] > b[0]:
　　　　return True
　　if a[1] > b[1]:
　　　　return True
　　return False
for i in range(len(s)－1):
　　for j in range(0, ②　len(s)－i－1或len(s)－1　):
　　　　if order(s[j], s[j＋1]):
　　　　　　s[j], s[j＋1] = s[j＋1], s[j]
while len(s)> 0:
　　flag = 0
　　min_time = 9999
　　index = 0
　　p = s.pop(0)
　　for i in range(k):
　　　　if time[i] <= p[0]:　# 有空闲窗口
　　　　　　time[i] = ③　p[0]＋p[1]或sum(p[0],p[1])　
　　　　　　flag = 1
　　　　　　break
　　　　if min_time >= time[i] :
　　　　　　min_time = time[i]
　　　　　　index = i
　　if flag == 1:
　　　　continue
　　if p[0] >= time[index]:
　　　　time[index] = p[0]
　　else:
　　　　wt = ④　time[index]－p[0]　
　　　　max_waittime = max(wt, max_waittime)
　　time[index] ＋= p[1]
print( 所有货轮卸完货的时间为: , max(time))
print( 等待最久的货轮需要等待的时间为 , max_waittime)
请回答下列问题:
(1)请在画线处填入合适的代码。
(2)加框处代码有错误,请改正。
【答案】 min_time > time[i]
【解析】 本题考查队列知识。(1)①根据代码可知,order函数用于排序条件判断,排序时将到达时间早的货轮排在前面,若到达时间相同,则将集装箱数量少的货轮排在前面,易知a[0]、b[0]为两艘货轮的到达时间,当a[0]b[0]时,说明a货轮比b货轮到得晚,需要交换。order函数中的第三个条件a[1]> b[1],当运行到此处时,隐含说明a货轮与b货轮同时到达,因此只需要比较集装箱数量即可。②根据代码可知,此处为冒泡排序,因此内循环的排序范围为0到len(s)－1,也可使用len(s)－i－1进行优化,减少循环判断次数。③经综合判断可知,time列表记录了每个吊桥当前排队卸货完成的总时长,也就是吊桥恢复空闲的时间,p[0]为排队队列队首的货轮的到达时间,因此time[i]<=p[0]说明有吊桥恢复空闲的时间早于下一艘货轮的到达时间,因此该货轮无须等待,第i个吊桥下一次恢复空闲的时间自然为该货轮卸完货的时间,也就是到达时间＋卸货时间,即p[0]＋p[1]。④综合判断可知,max_waittime变量记录了等待最久的货轮需要等待的时间。当货轮的到达时间早于等待时间最少的吊桥恢复空闲时间时,也就是p[0]=,当有多个吊桥等待均为最少时,系统找到的是编号最大的吊桥,将编号赋值给index,不符合题意,因此须将条件改为>。(共27张PPT)
二、 队列及其基本操作
第三章　字符串、队列和栈
信息技术 选择性必修1 数据与数据结构
必备知识练
1. 有如下Python程序段:
from random import randint
q = [1,2,14,5,6,7,9,10]
head = 0; tail = len(q)－ 1
ans = 0
m = randint(1,3)
q ＋= [0] * m
for i in range(m):
　for j in range(2 ** i － 1):
　　　head ＋= 1
　ans ＋= q[head]
　q[tail] = q[head]
　head ＋=1; tail ＋= 1
执行该程序段后,变量ans的值不. 可. 能. 是(　　)
A. 1 B. 15
C. 24 D. 34
【解析】 本题考查队列的操作知识。当m为1时,i只取0,此时队列头元素为 1,ans为1。当m为2时,i分别取0,1,为0时ans为1;当i为1时j为1,出队一次(2出队),队头元素是14,ans为15(14＋1)。当m为3时,分析i取2时,j为3,此时5、6、7依次出队,队头是9,ans为24(15＋9)。所以ans的值不可能是34,D符合题意。
D
2. 下列关于队列的说法,正确的是(　　)
A. 队列的特点是先进后出
B. 在队列中,允许插入的一端称为队首,允许删除的一端称为队尾
C. 刚建立的队列,队首指针和队尾指针均为0
D. 出队操作时,先将队首指针加1,再让队首元素出队
【解析】 队列的特点是先进先出,A错误;允许插入的一端称为队尾,允许删除的一端称为队首,B错误;出队操作时,先将队首元素出队,然后将队首指针加1,D错误;刚建立的队列,队首指针和队尾指针均指向下标为0的元素,即队首指针和队尾指针均为0,C正确。
C
3. 小王在使用队列解决问题的过程中,初始时,队列为空,队列的首指针和尾指针分别为head、tail,接着小王开始进行了一系列的操作,操作如下:入队、入队、入队、出队、入队、入队、出队、出队、出队、入队、入队,则操作结束时,head和tail的值分别是
(　　)
A. 4　7 B. 4　8
C. 5　7 D. 5　8
【解析】 初始时,队列为空,队首指针head和队尾指针tail的值均为0,队列不为空时,队首指针指向队首元素,队尾指针指向队尾元素的下一个位置,本题中共进行了7次入队操作和4次出队操作,因此最终head和tail的值分别为4、7,A正确。
A
4. 在汽车站候车室,信息提示屏上显示某个班车已做好准备,该车次的旅客可以检票上
车。旅客q1与q2依次排队等待检票,工作人员在检票时,旅客q3、q4也排队等待检票。
旅客q1检完票后准备上车,这时应该接受工作人员检票的旅客是(　　)
A. q1 B. q2
C. q3 D. q4
【解析】 排队上车是一个队列。当前队列的次序为q1,q2,q3,q4。因此旅客q1检完票后应对旅客q2进行检票,B正确。
B
5. 若用能存放6个元素(索引用0~5表示)的数组来实现循环队列,当前尾指针rear和头指针front的值分别为1和5时,从队列中出队一个元素再入队两个元素后,rear和front的值分别是(　　)
A. 3和4 B. 3和0
C. 5和0 D. 5和1
【解析】 循环队列下标n－1的后一个为0。 rear指针的值为1,加入2个元素后rear指针的值需要增加2,即为3。front指针的值为5,出队一个元素需要将front指针加1。由于5为循环队列最大的下标,则其下一个下标应为0。B正确。
B
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)
【解析】 出队操作需要将队首指针后移(即将队首指针值＋1)。由于当前队列是一个循环队列,一共有m＋1个元素,其下标为0至m。如果队首指针落在m处,此时出队指针值＋1的话,队首指针会落在m＋1处,但实际上不存在该位置,指针应该落在0处。所以队首指针＋1后,还需对其进行除以m＋1取余操作。D正确。
D
7. 有如下Python程序段:
import random
s = AB#C#D#
q = [ ]*len(s)
head = tail = 0
ans =
for i in range(len(s)):
　　op=random.randint(0,1)
　　　　(1)　　
　　if 　　(2)　　 and 　　(3)　　:
　　　　q[tail] = s[i]; tail ＋= 1; 　　(4)　　
　　elif 　　(5)　　 and head != tail and 　　(6)　　:
　　　　ch = q[head]; head ＋= 1
　　ans ＋= ch
print(ans)
执行该程序段后,输出结果为 0B#0A0C 。上述程序段方框处可选代码如下:
①ch == # 　②ch != # 　③op == 0　④op == 1　⑤ch = s[i]　⑥ch = str(op)
则(1)至(6)处代码依次是(　　)
A. ⑤③①⑥②④ B. ⑤③②⑥①④
C. ⑥①④⑤②③ D. ⑥③①⑤④②
【解析】 本题考查队列的相关操作以及代码的分析理解能力。本题可以利用代码特点,采用排除法、结合逻辑推理可以较快得出正确答案。由于输出结果中有字符‘0’,而字符串s中是没有这个字符的,那么(4)处的代码必定是⑥ch=str(op),此时也必有条件③op ==0。(1)处只能是⑤ch=s[i],C、D错误。再分析第二个字符‘B’,如字符‘B’一旦入队,那么结果ans中,字符‘A’一定在‘B’之前,所以此时不能满足入队条件。那么入队条件之一是:①ch == # ,另外一个条件是:④op ==1,A错误,B正确。
B
8. 有如下Phython程序段:
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
B
【解析】 此程序为循环队列的应用,队首定位在5号索引位,队尾定位在4号索引位。每次出队后,队首指针向后移动1位,当队首指针超过最后1个字符时,就要指向索引号为0的位置,因此队首指针值计算时需要对字符串长度进行取余。当队首指针与队尾指针重合时就停止出队,所以s的长度比原队列的长度少1。B正确。
9. 在某银行排队叫号系统中,利用队列来储存当前正在排队顾客的编号,head指向队首元素,tail指向队尾元素的下一个位置。若现在队列的顾客数量为4,关于head和tail的关系,下列说法中正确的是(　　)
A. head=tail＋3 B. head=tail＋4
C. tail=head＋3 D. tail=head＋4
【解析】 本题考查队列知识。head指向队列的第一个元素,tail指向队列元素的下一个元素,假设当队列为空时,head和tail都指向0,此时队列中的顾客数量为4,相当于执行了4次入队操作,此时tail的值为 4,则tail=head＋4。D正确。
D
关键能力练
10. 若用一个规模为8的数组来实现循环队列,且当前队头指针head与队尾指针tail的值分别为5和7。当从队列中删除一个元素,再加入两个元素后,head和tail的值分别是(　　)
A. 5和2 B. 6和1
C. 5和9 D. 6和9
【解析】 本题考查循环队列。循环队列是首尾相连的队列,从队列中删除一个元素后,head的值为6,加入两个元素后,tail的值为1。B正确。
B
11. 循环队列SQ(rear为队尾指针,front为队首指针,maxlen为循环队列的长度)队满的条件是(　　)
A. rear=SQ B. (rear＋1)%maxlen=front
C. rear=0 D. front=0
【解析】 在循环队列中,若队尾指针再下移1个位置就与队首指针重叠在一起,说明队列已满。由于是在循环队列中,队首与队尾指针的值都在0至maxlen－1之间。因此将队尾指针下移后还需要对其值进行取余操作。B正确。
B
12. 在一个循环队列中进行入队操作,输入“＋n”表示入队操作,入队元素为n,输入“－”表示出队操作,输入“@”表示操作结束。实现上述功能的Python程序如下:
m=int(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
【解析】 循环队列中的tail指针、head指针每次移动时,都对队列元素的个数取模运算,“＋”表示进行入队操作,因此划线处代码为tail=(tail＋1)%m,C正确。
C
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=head
print(data[t],end=" ")
while nextL[t]!=head:　　#输出添加后的队列
　　　t=nextL[t]
print(data[t],end=" ")
t=nextL[head]
t=nextL[t]
nextL[wz]=head
【解析】 本题的循环队列是采用单向链表来实现的。列表data用于记录链表节点中元素的值,列表nextL用于记录当前元素的下一个元素在data列表中的存储位置。新元素要插入到单向链表的尾部,首先要找到单向链表的表尾。在本单向链表中只知道链表的表头,所以必须从表头逐一向后查找表尾,表尾的特征是它的下一个是表头。查找表头时,当前指针向下移的条件为当前指针的下一个节点不是表头。找到链表尾后,需要做的工作是将尾节点的指针指向需插入的节点,插入节点的指针指向表头。
14. 某英文逐词翻译软件,不区分大小写。为了加快翻译速度,在翻译的过程中,软件会将最近出现过的一些单词存入内存。若内存中有该单词,则直接翻译,否则查外存词典并将该单词存入内存。内存中每个单元存储一个单词,存满时会清空最早进入内存的单词,腾出单元存放新单词。编程模拟软件的翻译过程:输入一个仅含英文、逗号或空格字符的英语句子,以句号结束,计算翻译软件需要去外存查找多少次词典。在翻译开始前,内存中没有任何单词。运行界面如图所示。请回答下列问题:
请输入内存容量:5
请输入英语句子:If you have an apple and I have an apple,we both have one apple.
需要去外存查找12次词典
(1)若上图中的内存容量改为7,则需要去外存查找__________次词典。
10
(2)实现上述功能的Python程序如下,请在画线处填入合适的代码。
m=int(input("请输入内存容量:"))
s=input("请输入英语句子:")
dic={}
head = tail = 0
word =
for ch in s:
　　if ch ==" " or ch ==","or ch ==".":
　　　　if word not in dic or ①_________________:
　　　　　　　if tail － head == m:
　　　　　　　　　head = head ＋ 1
　　　　　　　dic[word]= tail
　　　　　　　tail ＋=1
　　　　　　　word =""
　　else:
　　　　if "A"<= ch <= "Z"
　　　　　　ch =②_______________________________
　　　　word ＋= ch
print("需要去外存查找",③__________________,"次词典")
dic[word]< head
chr(ord(ch)＋32)或ch.lower()
tail或str(tail)
【解析】 本题考查队列及字符串知识。(1)经过模拟可知,最后队列当中的单词是apple and I we both one,共7＋3=10次。(2)①此处是对扫描到的word单词进行判断,如果是首次出现,则需要翻译,否则判断是否存在于内存中;结合代码dic[word]=tail,可判断出首次出现过的单词若出队,则dic[word]应小于head。②根据题意不区分大小写,很明显此处是大写转换成小写,故chr(ord(ch)＋32)。③由代码dic[word]=tail可知,每次翻译的word对应入队的位置。第一个word对应的是0,第二个word对应的是1,最后一个word对应的是tail;又由代码tail＋=1可知,最后一个单词翻译完毕之后,tail本身已经加1,所以翻译次数就是tail。
15. 某货运码头采用了智能卸货引导系统,系统将根据一天内所有货轮的到达时间与装载的集装箱数量综合排序,将到达时间早的货轮排在前面,若到达时间相同,则将集装箱数量少的货轮排在前面。排序之后,假设有k个吊桥进行卸货,当有吊桥空闲时,下一艘到达的货轮将会被系统安排至编号最小的空闲吊桥;当没有吊桥空闲时,下一艘到达的货轮将会被系统安排至等待时间最少的吊桥,若有多个吊桥的等待时间均为最少,货轮也会被安排至编号最小的吊桥。一个吊桥在单位时间内能卸下一个集装箱,且不计其他时间损耗,涉及的所有时间均以单位时间计算。现编程模拟上述过程,输出当天所有货轮卸完货所需的时间,以及所有货轮中最久等待时间。实现上述功能的Python代码如下:
# 货轮信息列表s,子列表的数据分别为[到达时间,集装箱数量]
s = [[31, 2], [10, 5], [2, 10], [10, 3], [1, 61], [30, 18], [0, 20],
[31, 25], [1, 15]]
k = int(input( 请输入吊桥数量: ))
time = [0 for i in range(k)]
max_waittime = 0
def order(a, b):
　　if a[0] < b[0]:
　　　　①__________________
　　if a[0] > b[0]:
　　　　return True
　　if a[1] > b[1]:
　　　　return True
　　return False
for i in range(len(s)－1):
　　for j in range(0, ②______________________):
　　　　if order(s[j], s[j＋1]):
　　　　　　s[j], s[j＋1] = s[j＋1], s[j]
while len(s)> 0:
　　flag = 0
　　min_time = 9999
　　index = 0
　　p = s.pop(0)
return False
len(s)－i－1或len(s)－1
　　for i in range(k):
　　　　if time[i] <= p[0]:　# 有空闲窗口
　　　　　　time[i] = ③___________________________
　　　　　　flag = 1
　　　　　　break
　　　　if min_time >= time[i] :
　　　　　　min_time = time[i]
　　　　　　index = i
　　if flag == 1:
　　　　continue
　　if p[0] >= time[index]:
　　　　time[index] = p[0]
　　else:
　　　　wt = ④_________________________
　　　　max_waittime = max(wt, max_waittime)
　　time[index] ＋= p[1]
print( 所有货轮卸完货的时间为: , max(time))
print( 等待最久的货轮需要等待的时间为 , max_waittime)
请回答下列问题:
(1)请在画线处填入合适的代码。
(2)加框处代码有错误,请改正。
【答案】 min_time > time[i]
p[0]＋p[1]或sum(p[0],p[1])
time[index]－p[0]
【解析】 本题考查队列知识。(1)①根据代码可知,order函数用于排序条件判断,排序时将到达时间早的货轮排在前面,若到达时间相同,则将集装箱数量少的货轮排在前面,易知a[0]、b[0]为两艘货轮的到达时间,当a[0]b[0]时,说明a货轮比b货轮到得晚,需要交换。order函数中的第三个条件a[1]> b[1],当运行到此处时,隐含说明a货轮与b货轮同时到达,因此只需要比较集装箱数量即可。②根据代码可知,此处为冒泡排序,因此内循环的排序范围为0到len(s)－1,也可使用len(s)－i－1进行优化,减少循环判断次数。③经综合判断可知,time列表记录了每个吊桥当前排队卸货完成的总时长,也就是吊桥恢复空闲的时间,p[0]为排队队列队首的货轮的到达时间,因此time[i]<=p[0]说明有吊桥恢复空闲的时间早于下一艘货轮的到达时间,因此该货轮无须等待,第i个吊桥下一次恢复空闲的时间自然为该货轮卸完货的时间,也就是到达时间＋卸货时间,即p[0]＋p[1]。④综合判断可知,max_waittime变量记录了等待最久的货轮需要等待的时间。当货轮的到达时间早于等待时间最少的吊桥恢复空闲时间时,也就是p[0]=,当有多个吊桥等待均为最少时,系统找到的是编号最大的吊桥,将编号赋值给index,不符合题意,因此须将条件改为>。

展开更多......

收起↑