插入排序及程序实现一轮复习课件-2025-2026学年浙江省高三信息技术选择性必修一

插入排序及程序实现 1 知识过关 2 1. 插入排序的算法思想 有一个已经有序的数据序列,在这个已经排好的数据序列中插入一个数,要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,该算法适用于少量数据的排序。 插入排序的基本思想是每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中适当的位置上,直到全部插入完为止。 在待排序的元素中,假设前面n－1(n≥2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入,直到整个序列变为有序的过程,称为插入排序。 3 插入排序法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一 个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待 插入元素)。在第一部分排序完成后,再将这个最后的元素插入到已排好序的第一部分中。 在有序序列(数组)中插入数据“9”(注意顺序不能颠倒) 4 2. 插入排序(升序)的核心代码 def insert_sort(a): 　　for i in range(1,len(a)):　　　　　　#小于i的为有序部分,i~len－1为无序部分 　　　　tmp = a[i]　　　　　 #无序部分取值 　　　　pos = i－1 　　　　while pos>=0 and a[pos]>tmp:　 #在有序部分寻找插入位置 　　　　　　a[pos+1] = a[pos]　　　　　 #逐位后移 　　　　　　pos －= 1 　　　　a[pos+1] = tmp　　 #将值插入有序部分 　　return a d = [6, 0, 9, 5, 8, 3, 4, 7, 1, 2] print(insert_sort(d)) 5 程序运行结果如下: 初始　:[6, 0, 9, 5, 8, 3, 4, 7, 1, 2] 第1轮:[0, 6, 9, 5, 8, 3, 4, 7, 1, 2] 第2轮:[0, 6, 9, 5, 8, 3, 4, 7, 1, 2] 第3轮:[0, 5, 6, 9, 8, 3, 4, 7, 1, 2] 第4轮:[0, 5, 6, 8, 9, 3, 4, 7, 1, 2] 第5轮:[0, 3, 5, 6, 8, 9, 4, 7, 1, 2] 第6轮:[0, 3, 4, 5, 6, 8, 9, 7, 1, 2] 第7轮:[0, 3, 4, 5, 6, 7, 8, 9, 1, 2] 第8轮:[0, 1, 3, 4, 5, 6, 7, 8, 9, 2] 第9轮:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 6 典例精选 7 【例1】 (2025·浙江1月选考)数组元素a[0]~a[n－1]已按升序排列,现要将 a[pos](0≤pos≤n－1)的值加1,并保持数组的有序性不变,实现该功能的程序段如下。 方框中应填入的代码是(　　) t = a[pos]+1 i = pos while 　　　　: 　　a[i] = a[i+1] 　　i += 1 a[i] = t A. i < n－1 B. i < n－1 and t > a[i+1] C. i < n－1 and a[i] > a[i+1] D. i <= n－1 or t > a[i] 【解析】 本题考查数组的插入排序。根据代码可知,由于代码中a[j+1],因此i的取值范围不能等于n－1,否则下标越界,D错误。还需保持数组升序,要增加附加条件,A错误。根据代码,待排序数已存入t中,因此t应与后面元素a[j+1]比较,C错误。 B 【例2】 现有1个有序序列为7,10,13,16,19。有一个数14,插入上述有序序列中,从而得到一个新的有序序列为7,10,13,14,16,19。 其思路如下:首先找到14的插入位置。从右到左开始查找,由于14小于19,先将19右移一个位置,然后14又小于16,因此再将16右移一个位置。接下来再将14与下一个数进行比较,当14大于等于数组中的数据时,记录该位置,然后把14插入即可。程序界面如图所示,输出原始数据以及插入后的数据。 请输入待插入数:14 原始数据为:[7,10,13,16,19] 插入后数据:[7,10,13,14,16,19] 实现上述功能的Python程序如下,请在画线处填入合适的代码。 a=[7,10,13,16,19] x = int(input("请输入待插入数:")) print("原始数据为:",a) i = len(a)－1 a.append(0)　#先给列表a最后增加一个空值 while ①___________________ :  　　　 ②________________  　　　i = i － 1 a[i+1] = x print("插入后数据:",a) 【解析】 本题考查插入算法。①根据题意,a[i]> x时,该数往后移动,且还要考虑循环变量i的范围,必须确保i>=0。②插入排序,必须从后往前找到正确的插入位置,在找位置的过程中还需要一边将数据往后移动,找到位置后,把x插入即可。因此答案是a[i + 1]=x。 a[i]> x and i>=0 a[i + 1]=a[i] 【例3】 插入排序,其基本算法的思想如下:每次将一个待排序的数据,按其大小插入到前面已排好序的数据序列中,使数据序列依然有序,直到所有待排序数据全部插入完成。 如一组数据(n=5)15,54,8,45,21,其升序的排序过程如下: 初始态:【15】　54　8　45　21 第1趟:【15　54】　8　45　21 第2趟:【8　15　54】　45　21 第3趟:【8　15　45　54】　21 第4趟:【8　15　21　45　54】 小王根据上述算法,编写了一个Python程序,运行界面如图所示。生成n个范围是1~99之间的随机整数,用插入排序将待排序数据按升序排序后输出。 排序前数据:[64,65,99,34,39,24,38,22,16,58] 排序后数据:[16,22,24,34,38,39,58,64,65,99] 实现上述功能的Python程序代码如下,请在画线处填入合适的代码。 import random n=10 a=[random.randint(1,99)for i in range(n)] print("排序前数据:",a) for i in range(1,n): 　　tmp = a[i] 　　j = i － 1　 　　while ①_______________________:  　　　　　a[j+1]=a[j] 　　　　　j = j － 1 　　②______________  print("排序后数据:",a) tmp < a[j]and j>=0 a[j+1]=tmp 【解析】 本题考查插入排序算法。①该算法的思想是:从后往前检查,若待插入数tmp小于a[j],则将该数组元素a[j]往前移动,故此处答案是tmp < a[j]and j>=0。然后继续往前(j=j－1)检查,直到遇到比tmp小的数组元素为止。②当退出while循环时,返回的值j是比tmp小的数组元素下标,故应该插入的位置是a[j+1],因此答案是a[j+1]=tmp。 自我检测 14 1. 有如下Python程序段: for i in range(1,4): 　　tmp = a[i] 　　j = i－1 　　while tmp < a[j] and j >=0: 　　　　a[j+1] = a[j] 　　　　j = j － 1 　　a[j+1] = tmp 已知列表a=[19,8,96,92,85,88],经过该程序段处理后,列表元素的值依次为(　　) A. 8,19,92,96,85,88 B. 8,19,85,88,92,96 C. 19,8,92,96,85,88 　 D. 19,8,85,92,96,88 【解析】 本题考查插入排序。先后将元素a[1]、a[2]和a[3]作为待插入数据进行排序,因此插入排序结束后,前四个数据有序(升序),而后面两个数据不变,A正确。 A 15 2. 有如下Python程序段,已知列表a是随机产生的数,要求实现升序排序。 for i in range(1,5): 　　 ①   　　key = a[j] 　　while a[j－1] > key and j > 0: 　　　　　a[j] = a[j － 1] 　　　　　j = j － 1 　　 ②   则画线处的代码应该是(　　) A. ①j = i　　　　 ②a[j+1] = key B. ①j = i－1　　 ②a[j+1] = key C. ①j = i　　　 ②a[j] = key D. ①j = i－1　　 ②a[j] = key 【解析】 本题考查插入排序算法。完整进行插入排序后,数据实现升序排序。由于插入的条件是a[j－1]> key and j > 0,因此插入的位置应该是a[j],C正确。 C 16 3. 有如下Python程序段: for i in range(3 ,1 ,－1): 　　if a[i] < a[i－1]: 　　　 tmp = a[i] 　　　 for j in range(i － 1 , 1 , －1): 　　　　　　if tmp > a[j]: 　　　　　　　　break 　　　　　 a[j + 1] = a[j] 　　　 a[j + 1] = tmp 已知列表a=[19,8,96,92,85,88],经过该程序段处理后,列表元素的值依次为(　　) A. 8,19,92,96,85,88 B. 8,19,85,88,92,96 C. 19,8,92,96,85,88 　 D. 19,8,85,92,96,88 【解析】 本题考查插入排序。先后将元素a[3]=92作为待插入数据进行排序,由于是从后往前找位置,因此找到位置后插入数据8的后面。而其他数据不变,C正确。 C 17 必备知识练 18 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 　　　　　②　　　 19 要使程序实现上述功能,则方框中的语句分别是(　　) 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 21 运行该程序段后,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<a[j－1]　②j>=0 and key<a[j－1]　③a[j]=key　④a[j－1]=key 则画线处的代码正确的是(　　) A. ①③ B. ①④ C. ②③ D. ②④ A 23 【解析】 本题考查插入排序的算法实现。本题中插入排序的思路为将第i个元素插入至已有序的范围[0,i],故而需要将a[i]的元素和范围[0,i－1]的元素进行比较,程序中a[i]的值存入key中,[0,i－1]采用j－1来进行枚举,所以j的取值最多只能取到1,当j的值为0时,不再执行循环,故(1)处为j>0 and key<a[j－1],key应该插入在a[j－1]的后一个位置,(2)处为a[j]=key。A正确。 4. 有如下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 25 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 26 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] 27 实现上述功能的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。 关键能力练 30 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 31 (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<ed: 　　　　tmp=data[st:m＋1];i=0;j=m＋1 　　　　while i<len(tmp): 　　　　　　if j>ed: 　　　　　　　　data[st]=tmp[i] 　　　　　　　　i＋=1 　　　　　　elif tmp[i]<data[j]: 　　　　　　　　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所示。 35 图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 36 图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 37 编写程序模拟接待过程,输出各窗口接待的客户序列,如图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]<d[j＋1][0] or d[j][1]<=d[j＋1][1]: 　　　　　 　　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 38 用以下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中删除 39 #读取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<n: 　　cur=min(wins)　　　　#min函数返回列表wins中的最小值 　　if cur<d[i][0]: 　　　　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<n and d[i][0]<=cur: 　　　　　　　　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<n and d[i][2]==－1 40 【解析】 本题考查插入排序、队列、二维数组等知识。(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<n and d[i][2]==－1。 41 $