资源简介

五、 插入排序及程序实现
1. 小王编写程序实现把数据tmp=55插入到升序序列列表a中,得到一个新的升序序列,升序序列元素已依次存放在数组元素 a[1]、a[2]、……、a[n]中。其 Python 程序代码如下:
tmp = 55
n=len(a)－1
if tmp >= a[n]:
　　a.append(tmp)　#在数组a末尾增加元素tmp
else:
　　a.append(0)　　#在列表a末尾添加一个元素0
　　j = n ＋ 1
　　while j >= 1 and tmp < a[j － 1]:
　　　　　　　①　　　
　　　　j = j － 1
　　　　　②　　　
要使程序实现上述功能,则方框中的语句分别是(　B　)
A. ①a[j ＋ 1] = a[j]　②a[j] = tmp
B. ①a[j] = a[j － 1]　②a[j] = tmp
C. ①a[j ＋ 1] = a[j]　②a[j ＋ 1] = tmp
D. ①a[j] = a[j － 1]　②a[j ＋ 1] = tmp
【解析】 若插入元素 tmp>=a[n],把 tmp 插入到序列的末尾,否则从右往左依次比较 tmp 和 a[j－1],若 tmp < a[j－1],则把 a[j－1]后移到 a[j],继续往左边比较,直至 tmp >=a[j－1]或 j=1,最后把 tmp 插入到 a[j]中,B正确。
2. 有如下Python程序段:
a = [3,4,9,12,25,33]
b = [2,7,15,17,19,45]
n = len(a); a = a ＋ b　# 列表连接
for i in range(n,len(a)):
　　j = i
　　while　　　　　　　　　:
　　　　a[j－1],a[j] = a[j],a[j－1]
　　　　j －= 1
运行该程序段后,a为[2,3,4,7,9,12,15,17,19,25,33,45],则画线处应填入的代码是(　A　)
A. j > 0 and a[j－1] > a[j]
B. j >= 0 and a[j－1] > a[j]
C. j > 0 and a[j－1] < a[j]
D. j >= 0 and a[j－1] < a[j]
【解析】 本题考查插入排序算法知识。由于代码中有a[j－1],因此j不能为0,B、D错误。最后的结果是升序,所以交换的条件是:a[j－1]> a[j],A正确,C错误。
3. 实现正整数序列a升序排列的Python程序代码段如下:
a=[7,4,2,13,6,5,3,6,17,1]
for i in range(1,len(a)):
　　key=a[i]
　　j=i
　　while 　　　(1)　　　:
　　　　a[j]=a[j－1]
　　　　j－=1
　　(2)　　
画线处可选代码如下:
①j>0 and key=0 and key则画线处的代码正确的是(　A　)
A. ①③ B. ①④
C. ②③ D. ②④
【解析】 本题考查插入排序的算法实现。本题中插入排序的思路为将第i个元素插入至已有序的范围[0,i],故而需要将a[i]的元素和范围[0,i－1]的元素进行比较,程序中a[i]的值存入key中,[0,i－1]采用j－1来进行枚举,所以j的取值最多只能取到1,当j的值为0时,不再执行循环,故(1)处为j>0 and key4. 有如下Python程序段:
a=[98,25,13,8,56]
for i in range(1,5):
　　j = i; key = a[j]
　　while j > 0 and a[j－1] < key:
　　　　　a[j] = a[j － 1]
　　　　　j = j － 1
　　a[j] = key
执行该程序段后,列表a的值是(　B　)
A. [8,13,25,56,98] B. [98,56,25,13,8]
C. [56,25,13,8,98] D. [98,8,13,25,56]
【解析】 本题考查插入排序算法。完整进行插入排序后,数据实现降序排序,B正确。
5. 有如下Python程序段:
n=4;a = [0]*5; x = 6
for i in range(n＋1):
　　a[i]=2*i＋1
for j in range(n－1,2,－1):
　　a[j＋1]=a[j]
a[3]=x
print(a[3],a[n])
程序执行完毕后,输出的结果是(　D　)
A. 7和9 B. 6和0
C. 3和5 D. 6和7
【解析】 本题考查插入算法知识。数组a的原始数据为[1, 3, 5, 7, 9],然后将后一个7往后覆盖元素9,最后再用6将第一个7覆盖,因此最后数组a变为[1, 3, 5, 6, 7],D正确。
6. 某排序算法思路如下:每一趟将一个待排序的记录,按其关键字的大小插入到已经排好序的一组记录的适当位置上,直到所有待排序记录全部插入。例如,(9,3,1,4)升序排序:第一步,“3”插入到有序记录(9),得到(3,9);第二步,“1”插入到有序记录(3,9),得到(1,3,9);第三步,“4”插入到有序记录(1,3,9),得到最终的有序记录为“1,3,4,9”。
为此,小明编写了一个Python程序,功能为:运行程序,随机产生n个随机整数,并显示排序前的数据,且输出经过上述排序算法后的数据,运行结果如图所示。
待排序数据:[39,94,68,27,62,67,6,71,73,10]
排序后数据:[6,10,27,39,62,67,68,71,73,94]
实现上述功能的Python代码如下,但加框处的代码有错误,请改正。
import random
n = 10　　　　　#变量n存储待排序数据个数
a=[random.randint(1,99)for i in range(n)]
print("待排序数据:",a)
for i in range(1,n):
　　　t = a[i]
　　　j = i － 1
　　　while t < a[j]:
　　　　　　a[j ＋ 1] = a[j]
　　　　　　j = j － 1
　　　　　　if j == 0 :　　　　#①
　　　　　　　　break
　　　a[j] = t　　　　#②
print("排序后数据:",a)
【答案】 ①j < 0或j=－1　②a[j＋1]=t
【解析】 本题主要考查插入排序算法知识。①根据题意和代码可知,插入排序时先要将插入的数据保存到变量t中,然后通过while循环从后往前查找正确的插入位置,并依次从最后面一个数据往后移动,以便为待插入的数腾出空位。此处的if用于判断当j<0时退出循环,从而避免下标越界。②找到正确的插入位置a[j＋1]后,将临时保存在t中的值赋值给a[j＋1]即可,故此处为a[j＋1]=t。
7. 某大数据序列data中包含了n个正整数,现在要对data进行升序排列,排序规则如下:
①以长度h(32≤h≤64)为标准对data进行划分子序列,h满足划分后的子序列个数为偶数且最后一个子序列长度最接近h(例如,序列data长度为65,则长度h为33,子序列1长度为33,子序列2长度为32,比以其他偶数子序列个数划分更符合划分要求)。
②依次将子序列内部按数值大小升序排列,对长度相同的子序列两两有序合并。
③若剩余子序列长度不同,则依次两两合并,直到序列完全升序。
例如,数据序列有100个正整数,则将序列划分为2个长度为50的子序列,依次排序后两两合并为1个完全升序的序列,排序结束。请回答下列问题:
(1)若数据序列有165个正整数,则h为　42　。
(2)两个有序子序列合并为一个有序序列的megsort函数如下,其中data为数据序列,st为第1个子序列的起始位置,m为第1个子序列的终止位置,ed为第2个子序列的终止位置。
def megsort(data,st,m,ed):
　　while data[m＋1]>=data[st] and st<=m:
　　　　st＋=1
　　while ed>m and data[m]<=data[ed]:
　　　　ed－=1
　　if st　　　　tmp=data[st:m＋1];i=0;j=m＋1
　　　　while i　　　　　　if j>ed:
　　　　　　　　data[st]=tmp[i]
　　　　　　　　i＋=1
　　　　　　elif tmp[i]　　　　　　　　data[st]=tmp[i]
　　　　　　　　i＋=1
　　　　　　else:
　　　　　　　　data[st]=data[j]
　　　　　　　　j＋=1
　　　　　　st＋=1
　　return data
若在模拟环境下,data 为[1,3,3,4,5,7,3,4,5,5,6,9],st 为 0,m 为 5,ed 为 11,调用该函数后,加框处的语句执行的次数为　2　次。
(3)实现上述功能的部分 Python 程序如下,请在画线处填入合适的代码。
def rsort(data,st,ed):
　　　for i in range(st＋1,ed＋1):
　　　　　tmp=data[i]
　　　　　j=i－1
　　　　　while j>=st and data[j]>tmp:
　　　　　　　　①　data[j＋1]=data[j]　
　　　　　　　　j－=1
　　　　　data[j＋1]=tmp
　　　return data
#计算子序列划分长度 h,代码略
stack=[0]*(len(data)//h)
top=－1
for i in range(0,n,h):
　　　start=i
　　　end=i＋h－1
　　　if i＋h>n:
　　　　　end=n－1
　　　data=rsort(data,start,end)
　　　t=h
　　　while top!=－1 and stack[top][2]==t:
　　　　　start=stack[top][0]
　　　　　mid=stack[top][1]
　　　　　②　t＋=stack[top][2]　
　　　　　top－=1
　　　　　data=megsort(data,start,mid,end)
　　　③　top＋=1　
　　　stack[top]=[start,end,t]
#处理后续长度不相同的子序列,使之合并成 1 个有序序列,代码略
【解析】 (1)数据序列长度为165,至少需要划分为3段,最多划分为5段,题干要求划分为的子序列个数为偶数,因此只能为4段,若划分为4段,则长度h为42,划分后的序列长度分别为42、42、42、39。(2)函数中前两个 while 循环用于缩小参与排序的数据范围,根据参数,最后参与排序的范围为[4,5,7,3,4,5,5,6],第1个序列为[4,5,7],第2个序列为[3,4,5,5,6],此时进入排序后第 1 个序列中的 4 和 5 通过加框语句完成排序,而元素 7 则通过第一个if语句完成排序。因此加框语句一共执行2次。(3)①此处为插入排序的赋值语句,其目的为将前方数据挪到后方,为待排序元素挪出空位。故此处为 data[j＋1]=data[j]。②此处为序列合并,序列利用栈结构进行两两合并,注意此时的 for 循环处理的是长度相同的序列,因此在合并的过程中当两个序列合并后,若与栈顶元素长度相同则栈内元素出栈与合并后的序列合并,再检查与栈顶元素的长度是否相同,直到长度不同才处理 data 中的下一段序列,因此在合并过程中序列长度需要不断更新,故答案为 t＋=stack[top][2]。③此处为将合并后的序列信息入栈,因此答案为 top＋=1。
8. 银行有k个办理业务的窗口(编号 0~k－1),窗口分为普通和 VIP 两种类型。VIP 窗口在没有VIP客户的时候,也可以接待普通客户。各窗口按客户到达的先后顺序为他们办理业务,若客户到达时刻相同,则先接待服务时长短的客户。办理规则如下:
①如果有空闲的VIP窗口,先安排已到达的VIP客户办理业务。
②如果没有空闲的VIP窗口,VIP客户可到其他窗口办理业务,但需要和普通客户一起按到达的先后顺序办理业务。
③有多个空闲窗口时,把客户安排到编号小的窗口办理。
以k=3,窗口2为 VIP 窗口为例,客户信息如图1所示。到达时刻0,3个窗口均空闲,A和B两个客户已到达(类型0指普通客户,1指VIP客户)。VIP客户B按规则①到VIP窗口2,客户A按规则③到编号较小的窗口0。到达时刻5,VIP 客户C按规则②到窗口1办理业务。全部接待顺序如图2所示。
到达时刻 服务时长 类型 客户名称
0 12 0 A
0 15 1 B
5 16 1 C
5 18 0 D
5 20 0 E
11 13 1 F
图1
办理时刻 窗口0、1、2结束服务时间 说明
0 【12,0,15】 B到窗口2、A到窗口0
5 【12,21,15】 C到窗口1
12 【30,21,15】 D到窗口0
15 【30,21,28】 F到窗口2
21 【30,41,28】 E到窗口1
图2
窗口0接待:A,D
窗口1接待:C,E
窗口2接待:B,F
图3
编写程序模拟接待过程,输出各窗口接待的客户序列,如图3所示。请回答下列问题:
(1)若客户F的到达时刻是50,则窗口2接待的客户序列是　B、E、F　。
(2)定义如下的 sortD(d)函数,列表d的每个元素存储客户信息,由到达时刻、服务时长、类型和客户名称四个数据项组成,且列表d已经按到达时间升序排序。函数的功能是将客户信息进一步加工为到达时刻相同时,按服务时长升序排列。
def sortD(d):
　　for i in range(1,len(d)):
　　　　j=i－1
　　　　while i>=0:
　　　　　　if d[j][0]　　　　　 　　break
　　　　　　d[j],d[j＋1]=d[j＋1],d[j]# ①
　　　　　　j－=1
　　return
用以下3组数据测试 sortD(d),①处语句执行次数最少的是　C　(单选,填字母)。
A. [[0,16,0, A ], [0,18,0, B ], [2,20,0, C ], [2,23,0, D ],[2,12,0, E ], [2,15,0, F ]]
B. [[0,16,0, A ], [0,18,0, B ], [2,20,0, C ], [2,12,0, E ], [2,23,0, D ], [2,15,0, F ]]
C. [[0,18,0, B ], [0,16,0, A ], [2,12,0, E ], [2,20,0, C ],[2,15,0, F ],[2,23,0, D ]]
(3)实现窗口接待客户的Python程序段如下,请在画线处填入合适的代码。
函数与方法 功能
viper.append(x) 在列表viper末尾添加元素x
t=viper.pop(x) 将列表x位置元素赋值给t,并将其从viper中删除
#读取n条客户信息存储到列表d,元素由到达时刻、服务时长、类型和客户名称组成,代码略
sortD(d)
k=6　　　　　　　　　　　　#窗口总数
vipwin=[2,4,5]　　　　　　#VIP 窗口编号
wins=[0]*k
lst=[[]for i in range(k)]　　#lst[i]存放编号为i的窗口接待客户序列
viper=[]
for i in range(n):
　　if d[i][2]==1:
　　　　　①　viper. append(i)　
i=0
while i　　cur=min(wins)　　　　　　#min函数返回列表wins中的最小值
　　if cur　　　　cur=d[i][0]
　　for j in vipwin:
　　　　if wins[j]<=cur:　#按规则①
　　　　　　if len(viper)>0 and d[viper[0]][0]<=cur:
　　　　　　　　t=viper.pop(0)
　　　　　　　　②　wins[j]=cur＋d[t][1]　
　　　　　　　　lst[j].append(d[t][3])
　　　　　　　　d[t][2]=－1
　　　　　　else:
　　　　　　　　break
　　for j in range(k):
　　　　if wins[j]<=cur:
　　　　　　while ③　i　　　　　　　　i＋=1
　　　　　　if i　　　　　　　　if d[i][2]==1:
　　　　　　　　　　　viper.pop(0)
　　　　　　　　wins[j]=cur＋d[i][1]
　　　　　　　　lst[j].append(d[i][3])
　　　　　　　　i＋=1
#输出各窗口的接待客户序列,代码略
【解析】 本题考查插入排序、队列、二维数组等知识。(1)若客户F的到达时刻是50,在办理时刻15时,E到窗口2,在办理时刻50时,F到窗口2。所以窗口2的接待序列为:B、E、F。(2)本题考查插入排序,结合代码,3组测试数据可知,①处语句执行次数分别为4,3,2,C符合题意。(3)①viper用来存储列表d中的vip客户索引值,通过遍历客户类型将vip客户的索引值添加至列表viper中(入队操作),所以答案为 viper. append(i)。②此处程序段的主要功能是优先安排vip客户。分析程序可得,列表wins存储每个窗口结束当前服务的时间,cur表示当前客户办理业务的开始时间。当某个vip窗口出现空闲,将优先安排队列viper中最早到达的vip客户到编号为j的vip窗口办理业务(出队操作),变量t存储出队的vip客户在列表d中的索引,并且将d[t][2]设为－1,表示该客户已安排,同时需要更新编号为j的vip窗口的结束服务时间:即开始办理时间＋服务时长。③此处程序段的主要功能是安排剩余的普通客户和未安排完成的VIP客户。当出现一个结束当前服务的窗口,需要在剩余的客户中查找未安排的客户,此处的循环语句i=i＋1表示跳过当前已经安排的vip客户。故答案为i五、 插入排序及程序实现
第五章　数据结构与算法
信息技术 选择性必修1 数据与数据结构
必备知识练
1. 小王编写程序实现把数据tmp=55插入到升序序列列表a中,得到一个新的升序序列,升
序序列元素已依次存放在数组元素 a[1]、a[2]、……、a[n]中。其 Python 程序代码
如下:
tmp = 55
n=len(a)－1
if tmp >= a[n]:
　　a.append(tmp)　#在数组a末尾增加元素tmp
else:
　　a.append(0)　　#在列表a末尾添加一个元素0
　　j = n ＋ 1
　　while j >= 1 and tmp < a[j － 1]:
　　　　　　　①　　　
　　　　j = j － 1
　　　　　②　　　
要使程序实现上述功能,则方框中的语句分别是(　　)
A. ①a[j ＋ 1] = a[j]　②a[j] = tmp
B. ①a[j] = a[j － 1]　②a[j] = tmp
C. ①a[j ＋ 1] = a[j]　②a[j ＋ 1] = tmp
D. ①a[j] = a[j － 1]　②a[j ＋ 1] = tmp
【解析】 若插入元素 tmp>=a[n],把 tmp 插入到序列的末尾,否则从右往左依次比较 tmp 和 a[j－1],若 tmp < a[j－1],则把 a[j－1]后移到 a[j],继续往左边比较,直至 tmp >=a[j－1]或 j=1,最后把 tmp 插入到 a[j]中,B正确。
B
2. 有如下Python程序段:
a = [3,4,9,12,25,33]
b = [2,7,15,17,19,45]
n = len(a); a = a ＋ b　# 列表连接
for i in range(n,len(a)):
　　j = i
　　while　____________________:
　　　　a[j－1],a[j] = a[j],a[j－1]
　　　　j －= 1
运行该程序段后,a为[2,3,4,7,9,12,15,17,19,25,33,45],则画线处应填入的代码是
(　　)
A. j > 0 and a[j－1] > a[j]
B. j >= 0 and a[j－1] > a[j]
C. j > 0 and a[j－1] < a[j]
D. j >= 0 and a[j－1] < a[j]
【解析】 本题考查插入排序算法知识。由于代码中有a[j－1],因此j不能为0,B、D错误。最后的结果是升序,所以交换的条件是:a[j－1]> a[j],A正确,C错误。
A
3. 实现正整数序列a升序排列的Python程序代码段如下:
a=[7,4,2,13,6,5,3,6,17,1]
for i in range(1,len(a)):
　　key=a[i]
　　j=i
　　while (1) :
　　　　a[j]=a[j－1]
　　　　j－=1
(2)
画线处可选代码如下:
①j>0 and key=0 and key则画线处的代码正确的是(　　)
A. ①③ B. ①④
C. ②③ D. ②④
A
【解析】 本题考查插入排序的算法实现。本题中插入排序的思路为将第i个元素插入至已有序的范围[0,i],故而需要将a[i]的元素和范围[0,i－1]的元素进行比较,程序中a[i]的值存入key中,[0,i－1]采用j－1来进行枚举,所以j的取值最多只能取到1,当j的值为0时,不再执行循环,故(1)处为j>0 and key4. 有如下Python程序段:
a=[98,25,13,8,56]
for i in range(1,5):
　　j = i; key = a[j]
　　while j > 0 and a[j－1] < key:
　　　　　a[j] = a[j － 1]
　　　　　j = j － 1
　　a[j] = key
执行该程序段后,列表a的值是(　　)
A. [8,13,25,56,98] B. [98,56,25,13,8]
C. [56,25,13,8,98] D. [98,8,13,25,56]
【解析】 本题考查插入排序算法。完整进行插入排序后,数据实现降序排序,B正确。
B
5. 有如下Python程序段:
n=4;a = [0]*5; x = 6
for i in range(n＋1):
　　a[i]=2*i＋1
for j in range(n－1,2,－1):
　　a[j＋1]=a[j]
a[3]=x
print(a[3],a[n])
程序执行完毕后,输出的结果是(　　)
A. 7和9 B. 6和0
C. 3和5 D. 6和7
【解析】 本题考查插入算法知识。数组a的原始数据为[1, 3, 5, 7, 9],然后将后一个7往后覆盖元素9,最后再用6将第一个7覆盖,因此最后数组a变为[1, 3, 5, 6, 7],D正确。
D
6. 某排序算法思路如下:每一趟将一个待排序的记录,按其关键字的大小插入到已经排好序的一组记录的适当位置上,直到所有待排序记录全部插入。例如,(9,3,1,4)升序排序:第一步,“3”插入到有序记录(9),得到(3,9);第二步,“1”插入到有序记录(3,9),得到(1,3,9);第三步,“4”插入到有序记录(1,3,9),得到最终的有序记录为“1,3,4,9”。
为此,小明编写了一个Python程序,功能为:运行程序,随机产生n个随机整数,并显示排序前的数据,且输出经过上述排序算法后的数据,运行结果如图所示。
待排序数据:[39,94,68,27,62,67,6,71,73,10]
排序后数据:[6,10,27,39,62,67,68,71,73,94]
实现上述功能的Python代码如下,但加框处的代码有错误,请改正。
import random
n = 10　　　　　#变量n存储待排序数据个数
a=[random.randint(1,99)for i in range(n)]
print("待排序数据:",a)
for i in range(1,n):
　　　t = a[i]
　　　j = i － 1
　　　while t < a[j]:
　　　　　　a[j ＋ 1] = a[j]
　　　　　　j = j － 1
　　　　　　if j == 0 :　　　　#①
　　　　　　　　break
　　　a[j] = t　　　　#②
print("排序后数据:",a)
【答案】 ①j < 0或j=－1　②a[j＋1]=t
【解析】 本题主要考查插入排序算法知识。①根据题意和代码可知,插入排序时先要将插入的数据保存到变量t中,然后通过while循环从后往前查找正确的插入位置,并依次从最后面一个数据往后移动,以便为待插入的数腾出空位。此处的if用于判断当j<0时退出循环,从而避免下标越界。②找到正确的插入位置a[j＋1]后,将临时保存在t中的值赋值给a[j＋1]即可,故此处为a[j＋1]=t。
关键能力练
7. 某大数据序列data中包含了n个正整数,现在要对data进行升序排列,排序规则如下:
①以长度h(32≤h≤64)为标准对data进行划分子序列,h满足划分后的子序列个数为偶数且最后一个子序列长度最接近h(例如,序列data长度为65,则长度h为33,子序列1长度为33,子序列2长度为32,比以其他偶数子序列个数划分更符合划分要求)。
②依次将子序列内部按数值大小升序排列,对长度相同的子序列两两有序合并。
③若剩余子序列长度不同,则依次两两合并,直到序列完全升序。
例如,数据序列有100个正整数,则将序列划分为2个长度为50的子序列,依次排序后两两合并为1个完全升序的序列,排序结束。请回答下列问题:
(1)若数据序列有165个正整数,则h为__________。
42
(2)两个有序子序列合并为一个有序序列的megsort函数如下,其中data为数据序列,st为第1个子序列的起始位置,m为第1个子序列的终止位置,ed为第2个子序列的终止位置。
def megsort(data,st,m,ed):
　　while data[m＋1]>=data[st] and st<=m:
　　　　st＋=1
　　while ed>m and data[m]<=data[ed]:
　　　　ed－=1
　　if st　　　　tmp=data[st:m＋1];i=0;j=m＋1
　　　　while i　　　　　　if j>ed:
　　　　　　　　data[st]=tmp[i]
　　　　　　　　i＋=1
　　　　　　elif tmp[i]　　　　　　　　data[st]=tmp[i]
　　　　　　　　i＋=1
　　　　　　else:
　　　　　　　　data[st]=data[j]
　　　　　　　　j＋=1
　　　　　　st＋=1
　　return data
若在模拟环境下,data 为[1,3,3,4,5,7,3,4,5,5,6,9],st 为 0,m 为 5,ed 为 11,调用该函数后,加框处的语句执行的次数为__________次。
2
(3)实现上述功能的部分 Python 程序如下,请在画线处填入合适的代码。
def rsort(data,st,ed):
　　　for i in range(st＋1,ed＋1):
　　　　　tmp=data[i]
　　　　　j=i－1
　　　　　while j>=st and data[j]>tmp:
　　　　　　　　①____________________
　　　　　　　　j－=1
　　　　　data[j＋1]=tmp
　　　return data
#计算子序列划分长度 h,代码略
stack=[0]*(len(data)//h)
top=－1
for i in range(0,n,h):
　　　start=i
　　　end=i＋h－1
　　　if i＋h>n:
　　　　　end=n－1
　　　data=rsort(data,start,end)
　　　t=h
　　　while top!=－1 and stack[top][2]==t:
　　　　　start=stack[top][0]
　　　　　mid=stack[top][1]
　　　　　②_______________________
　　　　　top－=1
　　　　　data=megsort(data,start,mid,end)
　　　③_____________
　　　stack[top]=[start,end,t]
#处理后续长度不相同的子序列,使之合并成 1 个有序序列,代码略
data[j＋1]=data[j]
t＋=stack[top][2]
top＋=1
【解析】 (1)数据序列长度为165,至少需要划分为3段,最多划分为5段,题干要求划分为的子序列个数为偶数,因此只能为4段,若划分为4段,则长度h为42,划分后的序列长度分别为42、42、42、39。(2)函数中前两个 while 循环用于缩小参与排序的数据范围,根据参数,最后参与排序的范围为[4,5,7,3,4,5,5,6],第1个序列为[4,5,7],第2个序列为[3,4,5,5,6],此时进入排序后第 1 个序列中的 4 和 5 通过加框语句完成排序,而元素 7 则通过第一个if语句完成排序。因此加框语句一共执行2次。(3)①此处为插入排序的赋值语句,其目的为将前方数据挪到后方,为待排序元素挪出空位。故此处为 data[j＋1]=data[j]。②此处为序列合并,序列利用栈结构进行两两合并,注意此时的 for 循环处理的是长度相同的序列,因此在合并的过程中当两个序列合并后,若与栈顶元素长度相同则栈内元素出栈与合并后的序列合并,再检查与栈顶元素的长度是否相同,直到长度不同才处理 data 中的下一段序列,因此在合并过程中序列长度需要不断更新,故答案为 t＋=stack[top][2]。③此处为将合并后的序列信息入栈,因此答案为 top＋=1。
8. 银行有k个办理业务的窗口(编号 0~k－1),窗口分为普通和 VIP 两种类型。VIP 窗口在没有VIP客户的时候,也可以接待普通客户。各窗口按客户到达的先后顺序为他们办理业务,若客户到达时刻相同,则先接待服务时长短的客户。办理规则如下:
①如果有空闲的VIP窗口,先安排已到达的VIP客户办理业务。
②如果没有空闲的VIP窗口,VIP客户可到其他窗口办理业务,但需要和普通客户一起按到达的先后顺序办理业务。
③有多个空闲窗口时,把客户安排到编号小的窗口办理。
以k=3,窗口2为 VIP 窗口为例,客户信息如图1所示。到达时刻0,3个窗口均空闲,A和B两个客户已到达(类型0指普通客户,1指VIP客户)。VIP客户B按规则①到VIP窗口2,客户A按规则③到编号较小的窗口0。到达时刻5,VIP 客户C按规则②到窗口1办理业务。全部接待顺序如图2所示。
图1
到达时刻 服务时长 类型 客户名称
0 12 0 A
0 15 1 B
5 16 1 C
5 18 0 D
5 20 0 E
11 13 1 F
图2
办理时刻 窗口0、1、2结束服务时间 说明
0 【12,0,15】 B到窗口2、A到窗口0
5 【12,21,15】 C到窗口1
12 【30,21,15】 D到窗口0
15 【30,21,28】 F到窗口2
21 【30,41,28】 E到窗口1
编写程序模拟接待过程,输出各窗口接待的客户序列,如图3所示。请回答下列问题:
(1)若客户F的到达时刻是50,则窗口2接待的客户序列是__________。
(2)定义如下的 sortD(d)函数,列表d的每个元素存储客户信息,由到达时刻、服务时长、类型和客户名称四个数据项组成,且列表d已经按到达时间升序排序。函数的功能是将客户信息进一步加工为到达时刻相同时,按服务时长升序排列。
def sortD(d):
　　for i in range(1,len(d)):
　　　　j=i－1
　　　　while i>=0:
　　　　　　if d[j][0]　　　　　 　　break
　　　　　　d[j],d[j＋1]=d[j＋1],d[j]# ①
　　　　　　j－=1
　　return
B、E、F
窗口0接待:A,D
窗口1接待:C,E
窗口2接待:B,F
图3
用以下3组数据测试 sortD(d),①处语句执行次数最少的是__________(单选,填字母)。
A. [[0,16,0, A ], [0,18,0, B ], [2,20,0, C ], [2,23,0, D ],[2,12,0, E ], [2,15,0, F ]]
B. [[0,16,0, A ], [0,18,0, B ], [2,20,0, C ], [2,12,0, E ], [2,23,0, D ], [2,15,0, F ]]
C. [[0,18,0, B ], [0,16,0, A ], [2,12,0, E ], [2,20,0, C ],[2,15,0, F ],[2,23,0, D ]]
C
(3)实现窗口接待客户的Python程序段如下,请在画线处填入合适的代码。
函数与方法 功能
viper.append(x) 在列表viper末尾添加元素x
t=viper.pop(x) 将列表x位置元素赋值给t,并将其从viper中删除
#读取n条客户信息存储到列表d,元素由到达时刻、服务时长、类型和客户名称组成,代码略
sortD(d)
k=6　　　　　　　　　　　　#窗口总数
vipwin=[2,4,5]　　　　　　#VIP 窗口编号
wins=[0]*k
lst=[[]for i in range(k)]　　#lst[i]存放编号为i的窗口接待客户序列
viper=[]
for i in range(n):
　　if d[i][2]==1:
　　　　　①_____________________
i=0
while i　　cur=min(wins)　　　　#min函数返回列表wins中的最小值
　　if cur　　　　cur=d[i][0]
　　for j in vipwin:
　　　　if wins[j]<=cur:　#按规则①
　　　　　　if len(viper)>0 and d[viper[0]][0]<=cur:
　　　　　　　　t=viper.pop(0)
　　　　　　　　②___________________
　　　　　　　　lst[j].append(d[t][3])
　　　　　　　　d[t][2]=－1
　　　　　　else:
　　　　　　　　break
　　for j in range(k):
　　　　if wins[j]<=cur:
　　　　　　while ③______________________:
　　　　　　　　i＋=1
　　　　　　if i　　　　　　　　if d[i][2]==1:
　　　　　　　　　　　viper.pop(0)
　　　　　　　　wins[j]=cur＋d[i][1]
　　　　　　　　lst[j].append(d[i][3])
　　　　　　　　i＋=1
#输出各窗口的接待客户序列,代码略
viper. append(i)
wins[j]=cur＋d[t][1]
i【解析】 本题考查插入排序、队列、二维数组等知识。(1)若客户F的到达时刻是50,在办理时刻15时,E到窗口2,在办理时刻50时,F到窗口2。所以窗口2的接待序列为:B、E、F。(2)本题考查插入排序,结合代码,3组测试数据可知,①处语句执行次数分别为4,3,2,C符合题意。(3)①viper用来存储列表d中的vip客户索引值,通过遍历客户类型将vip客户的索引值添加至列表viper中(入队操作),所以答案为 viper. append(i)。②此处程序段的主要功能是优先安排vip客户。分析程序可得,列表wins存储每个窗口结束当前服务的时间,cur表示当前客户办理业务的开始时间。当某个vip窗口出现空闲,将优先安排队列viper中最早到达的vip客户到编号为j的vip窗口办理业务(出队操作),变量t存储出队的vip客户在列表d中的索引,并且将d[t][2]设为－1,表示该客户已安排,同时需要更新编号为j的vip窗口的结束服务时间:即开始办理时间＋服务时长。③此处程序段的主要功能是安排剩余的普通客户和未安排完成的VIP客户。当出现一个结束当前服务的窗口,需要在剩余的客户中查找未安排的客户,此处的循环语句i=i＋1表示跳过当前已经安排的vip客户。故答案为i

展开更多......

收起↑