资源简介

课时9　双指针遍历
【学业要求】
知识点 学业水平等级
1.能依据解决问题的需求来界定关键问题、抽象建模及设计算法,运用三种控制结构和算法描述方法合理地表示算法。 4
2.理解迭代算法的思想,应用迭代算法处理实际的问题。 4
　　本节课的目的是提取浙江选考真题的填空题(第13、14和15题)中用两个指针分别从一个数据集的头和尾依次遍历各个元素,并进行相应的处理。如2023年6月浙江选考的删除非依赖关系中,把后面有依赖关系的数据替换前面没有依赖的元素。也可以两个指针分别遍历两个不同的数据集,如2024年6月浙江选考中,在data中查找所有与Ri相同的子序列,就使用了2个指针,需要关注两个指针指向值的关系。
(2023年6月浙江选考)某工程包含n个任务(编号为0~n-1),每天可以有多个任务同时进行。某些任务之间有依赖关系,如图a所示,任务4依赖于任务1,任务1依赖于任务2。即任务2完成后才可以开始任务1,任务1完成后才可以开始任务4。不存在一个任务依赖于多个任务,或多个任务依赖于同一个任务的情况。现已对该工程的依赖关系进行了梳理,结果如图b所示,标记“T”表示依赖关系需保留,标记“F”表示依赖关系需删除。
任务A 任务B 标记
0 5 T
5 4 F
4 1 T
1 2 T
2 3 F
注:任务A依赖于任务B。
图b
定义如下erase(lst)函数,参数lst列表的每个元素表示一个依赖关系。函数的功能是删除标记为“F”的依赖关系,返回保留的依赖关系的个数。
def erase(lst):
　i=0
　j = len(lst)-1
　while i<= j:
　　　if lst[i][2]== 'T':
　　　　　i+=1
　　　else:
　　　　　if lst[j][2] == 'T':
　　　　　　 lst[i]=lst[j]
　　　　　　 i + = 1
　　　　　j - = 1
　return i
若lst列表依次存储图b所示的依赖关系,如lst[0]为[0,5,'T'],调用erase(lst)的数,则语句“lst[i] =lst[j]”的执行次数为　　　　。
答案　1
解析　本题考查数组的遍历、链表的遍历、创建等操作。变量i和j分别指向数组lst的头尾元素位置,从头元素开始遍历,若遍历的元素lst[i][2]不是'T',将尾元素为'T'的元素覆盖当前元素,并将变量j向前移动。在图b中,当i值为1时,标记为F,由于尾元素也不是T,因此仅仅变量j向前移动,变量i并未增加,再次遍历时,将一条为T的元素覆盖,因此该语句只执行了一次。
1.双指针遍历通过使用　　　　个指针来遍历同一数据集合,或两个不同的数据集合,有效地解决一些需要同时考虑多个元素的问题。
2.两个指针可能同时　　　　,也可能按某种规则独立移动。
3.确保双指针初始化正确,理解每个指针的　　　。
4.明确指针移动的　　　　以及停止遍历数据集合的条件
自我校对:1.两　2.移动　3.作用　4.条件
【典例1】 现有两个升序数组a和数组b,现在要求将数组b合并数组a,依旧保持数组a升序。实现的代码如下。
a=[2,3,5,7,9,11];b=[2,4,6]
for i in range(len(b)):
　a=a+[0]
i=len(a)-len(b)-1;j=len(b)-1
k=len(a)-1
while ①　　　　:
　if　②　　　　:
　　　a[k]=a[i]; i-=1
　else:
　　　a[k]=b[j]; j-=1
　③　　　
print(a)
(1)请将空白处填写完整。
(2)若①处代码填写为k>=0,会导致某些情况下无法得到预期的结果。下列4组数据中能测试出这一问题的是　　　　。
A.a=[2,4,6];b=[3,7] B.a=[4];b=[3,7]
C.a=[6];b=[2,3,4] D.a=[2,5,6];b=[1]
思维点拨
明考向 本题考查双指针遍历数组的算法实现
精点拨 (1)程序的功能是将b中有序数据插入到a中,先在a中扩展len(b)个空间,将a和b中数据依次移动到a数组从后面开始的位置中。①若将b中全部数据移动到a中,a中原来数据是有序的,不管a中数据有没有遍历完,合并后的数据肯定是有序的。②为移动a前面数据的条件,当a[i]大于b[j]且a中数据没有合并完,否则就将b的数据移动到a中。③无论移动a还是移动b中数据,k的指针始终会往前移动。(2)在比较过程中,要确保数据a[i]和b[j]是一个有效的位置上数据,因此②中不能缺少i>=0,当b中数据全部移动到a中后,j的值为-1,此时k还没有到达0,因此再将比较时,j就不是原来的有效位置了
答案　(1)①j>=0　②i>=0 and a[i]③k-=1　(2)A
【变式1】 数组a中存储着n个范围为[0,n-1]的随机整数,现要在数组a中找到一个最长的区间,使得该区间里没有重复的元素,输出该区间的长度。提示:用flag数组记录各个数字最后出现的位置,用变量left记录区间的左边界。遍历数组a,若当前数字出现位置大于等于左边界,说明该数字在区间内,需更新左边界。
#随机产生n个范围为[0,n-1]的随机整数并存储在数组a中,代码略
n=len(a)
flag=[-1]*n
length=left=0
for i in range(0,len(a)):
　if ①　　　　 :
　　　if i-left+1>length:
　　　　length=i-left+1
　　　　②　　　
　else:
　　　left=flag[a[i]]+1
　③　　　
print("该区间的最大长度为:",length,",区间内的值为:",a[beg:beg+length])
(1)请将空白处填写完整。
(2)若将程序加框处代码修改为flag=[0]*n,可能得不到正确答案,下列能测试出这个错误的一组数据为　　　　。
A.[0, 3, 0, 2, 1] B.[1, 1, 2]
C.[1, 3, 0, 2] D.[0, 0, 3, 3, 2]
答案　(1)①flag[a[i]]③flag[a[i]]=i　(2)C
解析　本题考查双指针遍历数组的算法实现。
(1)①若遍历到的数a[i]没有出现过(flag[a[i]]值为-1)或者上次出现的位置比左边界小,那么说明该数字不在区间中,可以进行最大长度区间的统计。②根据输出语句中区间内的值可知该处将对beg赋值。③若该数字出现在区间中,那么应更新这个区间的左边界。更新该数字出现的位置。(2)flag初值为-1表示未出现过该字符,若用0表示未出现过,与位置0混淆,因此当索引位置0的数字再次出现时,不能判断出是未出现过还是位置在0。A、B和D选项最长区间的开始位置均不为0。
【典例2】 自定义函数f的功能是实现列表a中所有x的倍数移动到左边,如数组a为[5,9,4,3,6],执行f(a,3)后,其值为[6,9,3,4,5],代码如下:
def f(a,x):
　i=0;j=len(a)-1
　while i　　　if　　　　　　　　　　　　　:
　　　　　a[i],a[j]=a[j],a[i]
　　　　　i+=1;j-=1
　　　elif a[i]%x==0:
　　　　　i+=1
　　　else:
　　　　　j-=1
　return a
则划线处代码为(　　)
A.a[i]%x==0 and a[j]%x==0
B.a[i]%x!=0 and a[j]%x==0
C.a[i]%x==0 and a[j]%x!=0
D.a[i]%x!=0 and a[j]%x!=0
思维点拨
明考向 本题考查双指针遍历数组的算法实现
精点拨 指针i指向列表a的第1个位置,指针j指向列表a的最后一个位置,若前面的数不能x整除,且后面的数能被x整除,交换两个数的位置;若前面的数能被x整除,指针i向后移动;否则就是两个数均不能被x整除,指针j向前移动。重复这个过程,直到i大于等于j
答案　B
【变式2】 (2026年1月浙江选考)有如下Python程序段:
#获取a的初始值,代码略
i=1
for j in range(1, len(a)):
　　if a[j]　　　　a[i], a[j]=a[j], a[i]
　　　　i+=1
a[0], a[i-1]=a[i-1], a[0]
执行该程序段后,a的值为[2,4,3,5,6,9,7],则下列选项中不可能为a[0]的初始值的是 (　　)
A.2 B.5
C.6 D.7
答案　D
解析　本题考查排序算法思想。变量i的初值为1,指针j从索引1开始遍历数组a,若满足条件a[j]　　指针往往就是数据集元素或数据项的下标,首先要明确每个指针指向哪个列表,即表示是哪个数组中的对象,再用图示画出这个数据结构,帮助理解指针移动过程,理解遍历的顺序。理解每个指针的作用,根据指针移动的条件,这两个指针可以同时移动,也可以独立移动。往往根据指针的移动情况,确定遍历数据集合的条件。
1.有如下Python程序段:
a=[1]*6
b=[96,88,84,91,99,80]
for i in range(5):
　for j in range(i+1,6):
　 　　if b[j] > b[i]:
　　 　 　a[i]+=1
　　 　else:
　　 　 　a[j]+=1
print(a)
该程序段运行后,列表a的值为(　　)
A.[5,3,2,4,6,1] B.[2,4,5,3,1,6]
C.[10,6,4,8,12,2] D.[4,8,10,6,2,12]
答案　B
解析　数组a记录b中对应数字的名次。 变量i从0开始遍历到4,变量j从i+1遍历到最后,若数组b中后面的数b[j]比当前的数b[i],则对a[i]进行计数,表示后面比他大的数的个数。以96为例,后面比他大的数只有99,因此他的位次为2。
2.有如下Python程序段:
s1="1324";s2="abcdefgh"
j,m=0,0
c=""
for i in s2:
　k=int(s1[j])
　c+=s2[m+k]
　j+=1
　if j>3:
　　　j=1
　　　m=m+2
print(c)
运行程序,输出结果是 (　　)
A.acbdefeg B.bdcefegh
C.bcdefegh D.bdceefgh
答案　B
解析　将字符串s2看成前面4个字符和后面4个字符各2组,本题考查字符串处理知识。可以使用模拟法解题,答案是B。
3.有如下Python程序段:
p={};s=input()
for i in range(len(s)):
　p[s[i]]=i
i=0
while i　 n=p[s[i]]
　 j=i+1
　while j<=n:
　　 　if p[s[j]]>n:
　　　 　　n=p[s[j]]
　　 　j=j+1
　print(s[i:j])
　i=j
若输入“arrayiybi”,则输出结果的最后一行内容是(　　)
A.arra B.yiy
C.iybi D.yiybi
答案　D
解析　将输入的字符串划分为几个子串,同一个字母只出现在同一个子串中并分段输出。字典p记录每种字母的最大索引值,字符串“arrayiybi”分成“arra”和“yiybi” 2个子串。
4.下列程序执行后的结果为(　　)
L=[1,-2,3,7,-8,9,10]
i,j=0,len(L)-1
while i　while L[i]>=0:
　　　i=i+1
　while L[j]<0:
　　　j=j-1
　if i　　　L[i],L[j] = L[j],L[i]
print(L[6])
A.3 B.9
C.-2 D.-8
答案　C
解析　在左边找到第1个小于0的数的位置i,在右边找到大于等于0的数的位置j,若i小于j,则交换两个位置上的数。程序的功能是把左边小于0的数交换到右边。第一次是-2和10交换,第2次是-8和9交换,交换后的序列为[1, 10, 3, 7, 9, -8, -2]。
5.如下 Python 程序段的功能是:删除数组 a(元素个数为 n)中重复元素并输出,例:a=[2,3,3,1,5,1,8],则输出 [2,3,1,5,8]。从1,5,1,8变为1,5,8来看,删除后面重复的数字。
i=0
while i　r=i+1
　for j in range(i+1,n):
　　　if (1)　　　　:
　　　　　(2)　　　
　　　　　r+=1
　n=r
　i+=1
print(a[:r])
则划线处应填入的代码为(　　)
A.(1)a[i]==a[j]　(2)a[r]=a[j]
B.(1)a[i]==a[j] (2)a[i]=a[r]
C.(1)a[i]!=a[j] (2)a[r]=a[j]
D.(1)a[i]!=a[j] (2)a[i]=a[r]
答案　C
解析　从1,5,1,8变为1,5,8来看,删除后面重复的数字。从输入语句来看,r表示不重复数字个数。a[i]与a[j]不相等的时候,表示目前不重复的数据将增加一个,将a[j]往前移动到r的位置;若a[i]与a[j]相等,则j向后移动,而r并没有向后移动。
6.某市要组织高中生参加竞技比赛。现要求在报名的n名学生中挑选出身高大于等于175 cm的学生,被挑选出的学生两两组队,且队内两名成员的体重之和不能超过140公斤,找出最多的组合数量。(提示:在符合身高要求下,按体重降序排列,体重最大的和体重最轻的组合,达到组合数量最多。)
实现上述功能的Python程序如下,请在划线处填上合适的代码。
#将学生的姓名,身高和体重依次存储到数组a中,代码略
n=len(a)
for i in range(n-1):
　　for j in range(n-1,i,-1):
　　　　if a[j][2]>a[j-1][2] and (a[j][1]>=175 and a[j-1][1]>=175):
　　　　　　a[j],a[j-1]=a[j-1],a[j]
　　　　elif ①　　　　:
　　　　　　a[j],a[j-1]=a[j-1],a[j]
　　if a[i][1]<175:
　　　　nlen=②　　　
　　　　break
i=0;j=nlen
while i　　if a[i][2]+a[j][2]<=140:
　　　　print(a[i],a[j])
　　　　i+=1
　　　　j-=1
　　else:
　　　　③　　　
答案　①a[j][1]>=175 and a[j-1][1]<175　
②i-1　③i+=1
解析　本题考查多个过程的重复遍历。选出身高大于等于175 cm的学生,队内两名成员的体重之和不能超过140公斤,找出最多的组合数量,应挑选出身高大于等于175且按体重降序排列,体重最大的和体重最轻的组合,达到组合数量最多。①把身高达到要求的学生尽量往前排,即后面的身高大于等于175,后面的没有达到要求,不论体重。均要向前交换。②由于从后往前冒泡,前面的数据先有序,当条件a[i][1]<175成立时,表示索引i-1的数据中身高是大于等于175的。③当条件a[i][2]+a[j][2]<=140不成立时,意味着较重体重的选手不可能匹配到更轻体重的选手,因此要找下一位选手。
1.有如下Python程序:
#输入包含5个不重复元素的数组a,代码略
i,c=0,0
key=int(input("key="))
for i in range(len(a)):
　if a[i]%key==0:
　　　c+=1
　else:
　　　j=i-c
　　　a[j]=a[i]
print(a)
运行该程序,若输入key为2,则输出的a不可能为(　　)
A.[3,7,5,4,5] B.[3,7,1,5,5]
C.[3,5,0,3,5] D.[9,7,4,7,3]
答案　D
解析　遍历数组a,变量c表示a[j]整除key(偶数)个数,若不是偶数,将其放在前面。A选项a初始值是[3,7,偶,4,5],偶表示该位置上是一个偶数。B选项第4个是偶数,则后面的5覆盖而来。C选项a初始值是[偶,偶,0,3,5]。D选项第2个是偶数,则7覆盖第2个数,但3一定要覆盖4。
2.有下列Python程序段:
s1="pytorch";s2="python";s=""
i=0;j=0
while i　　if s1[i] > s2[j] :
　　 　s=s+s1[i]
　　else:
　　 　j+=1
　　i+=1
执行以上程序段后,s中的值是(　　)
A."or" B."ch"
C."on" D."to"
答案　A
解析　用指针i和j分别遍历字符串s1和s2的各个位置,在两个字符串都没有遍历完前,指针i每次向后移动一个位置,当s1[i]大于s2[j],则将s1[i]连接入s中,指针j向后移动一个位置。前面3个字符均相等,"o"大于"h","r"大于"o","c"和"h"均小于"o",结束循环。
3.有如下Python程序段:
s=[3,4,3,2,1, 5,4,5,8,7,5,6,1,2]
ans=0
for i in range(0,(len(s)-1)∥4*4,4):
　tmp=s[i]
　for j in range(1,4):
　　　if s[i+j]>tmp:
　　　　tmp=s[i+j]
　ans+=tmp
执行该程序段后,变量ans的值为(　　)
A.17 B.19
C.8 D.9
答案　A
解析　每4个数据为一组,依次找出每组中最大值,并将这些最大值进行累加。
4.有如下Python程序段:
s1='blgr';s2='bollymgpric'
i=0;j=0;s3=''
while i<=len(s1)-1 and j<=len(s2)-1:
　if s1[i]==s2[j]:
　　　i+=1
　else:
　　　s3=s3+s2[j]
　j+=1
print(s3)
执行该程序段后,输出的内容为(　　)
A.oymp B.olymp
C.olympic D.oympic
答案　B
解析　指针i和j分别遍历s1和s2字符串,只要有一个字符串遍历完,结束程序运行。指针j每次向后移动一个位置,变量i只有当s1[i]和s2[j]相等时才移动,若不相等,则将s2[j]连接到s3中。
5.已排序的列表a有n个整型元素,现要删除a中重复出现的元素,使每个元素只出现一次,并输出去重后的结果。实现该功能的程序段如下:
p,q=0,1
while (1)　　　　:
　if a[p] != a[q]:
　　　(2)　　　　
　　　p+=1
　q+=1
print( (3)　　　　)
上述程序段中方框处可选代码为:
①q则(1)(2)(3)处代码依次为(　　)
A.①③⑥ B.①④⑤
C.②③⑤ D.②④⑥
答案　A
解析　语句q+=1每循环一次就执行一次,因此q表示当前位置,所以(1)中填写q6.有如下Python程序段:
def half_s(s):
　n=len(s);result=""
　i,j=0,n-1
　while i=n∥2:
　　　if s[i]>s[j]:
　　　 　　result+=s[i];i+=1
　　　elif s[i]　　　 　　result+=s[j];j-=1
　　　else:
　　 　　　i+=1;j-=1
　return result
执行语句v=half_s("welcome"),变量v的值是(　　)
A."come" B."wmol"
C."www" D."emo"
答案　B
解析　变量i从前往后遍历,变量j从后往前遍历,将s[i]和s[j]中较大者拼接到result中,若两者相等,直接略过。w和e比较,w大;e和e相等;l小于m;o大于l;l大于c;此时i的值为3,不满足条件i7.下列程序段是数组a中的数据分为被3整除、除3余1和除3余2共三部分:
#列表 a 初始值略
i=k=0;j=len(a)-1
while k<=j:
　if a[k]%3==0:
　　　a[i],a[k]=a[k],a[i]
　　　i+=1
　elif a[k]%3!=1:
　　　a[j],a[k]=a[k],a[j]
　　　k-=1;j-=1
　k+=1
运行该程序段后,这三部分对应的列表依次是(　　)
A.a[:i],a[i:j],a[k:]
B.a[:i+1],a[i:j+1],a[j+1:]
C.a[:i],a[i:k],a[k:]
D.a[:i+1],a[i:j],a[k+1:]
答案　C
解析　指针i和j分别指向数组的头和尾,变量k从0开始遍历数组,当条件a[k]%3==0成立时,交接a[i]和a[k],指针i向后移动,即把3的倍数交接到位置i的前面。当a[k]%3的值为2时,交接a[j]和a[k],指针j向前移动,即把除3余2的数交接到位置j的后面。当k等于j+1时,结束循环。因此[0,i-1]区间是3的倍数。[i,j]或[i,k-1]区间保存除3余1的数,j+1或k开始的数是除3余2。
8.对一组正整数的奇偶数进行交换。交换后偶数在前,奇数在后,并保持相对顺序不变。
a=[5,10,21,7,24,14,9,11,36,37]
n=len(a);b=[0]*n
num=0;k=0
while k 　　if　①　　　　:
　　　　b[num]=a[k]
　　　　num+=1
　　else:
　　　　②　　　
　　k+=1
for j in range(n-num,n):
　　③　　　
print(a)
(1)请将空白处填写完整。
(2)若将加框处修改为for j in range(num):,则③处应填写为 　　　　。
答案　(1)①a[k]%2==1　②a[k-num]=a[k]　③a[j]=b[j-(n-num)]　(2)a[n-num+j]=b[j]
解析　(1)①遍历数组a,若为奇数,将其移动到b数组中,若为偶数,将其移动到前面的位置。②遍历到索引位置k时,共遍历到数有k+1个中,其中有num个奇数,有k+1-num个偶数,最后一个偶数的索引位置为k-num。③遍历一次后,n-num个偶数已经放在[0,n-num-1]的位置上,因此需将所有的奇数转换到从n-num开始的位置中,因此变量j表示其在数组a中位置[n-num,n-1],数组b的下标为[0,num-1],两个下标的差值始终为n-num,设b中下标为x,则有j-x=n-num,可以得到b中下标。(2)加框处修改为for j in range(num),则j表示在数组b中位置,那么设数组a中下标为x,则有x-j= n-num,可以得到a中下标。
9.有2组器件要用一台检测设备检测。每个送检器件的信息包含送达时间、检测时长和优先级。每个器件的送达时间各不相同,编写程序合并2组器件的数据,为后续检定做准备。已知,lst1和lst2的每个元素由送达时间、检测时长和优先级3项构成,例如某送检器件的送达时间为8点整,检测时长为1小时,优先级为2,则存储元素的格式为["08:00", 1, 2]。 lstl和lst2均已按送达时间升序排列,合并后保持按送达时间升序。
(1)实现功能的程序如下,请在划线处填入合适的代码。
lst=[]
i=j=0
while i 　　if　①　　　　:
　　　 　lst.append(lst1[i])
　　　 　i+=1
　　else:
　　 　　lst.append(lst2[j])
　　 　　②　　　
print("数据合并后,数组元素为:",lst)
(2)while语句的条件“i A.能　　　　B.不能
答案　(1)①j==len(lst2) or 1st1[i][0]解析　(1)①将lst1[i]添加到lst中去的条件有2个,一是lst2已经遍历完,二是lst1[i][0]小于lst2[j][0]。②j是lst2的指针,每添加一个指针向后移动一个位置。(2)条件i必修一　数据与计算
课时9　双指针遍历
知识点 学业水平等级
1.能依据解决问题的需求来界定关键问题、抽象建模及设计算法,运用三种控制结构和算法描述方法合理地表示算法。 4
2.理解迭代算法的思想,应用迭代算法处理实际的问题。 4
目 录
CONTENTS
真题剖析
01
知识梳理
02
课堂突破
03
当堂检测
04
课后作业
05
真题剖析
1
　　本节课的目的是提取浙江选考真题的填空题(第13、14和15题)中用两个指针分别从一个数据集的头和尾依次遍历各个元素,并进行相应的处理。如2023年6月浙江选考的删除非依赖关系中,把后面有依赖关系的数据替换前面没有依赖的元素。也可以两个指针分别遍历两个不同的数据集,如2024年6月浙江选考中,在data中查找所有与Ri相同的子序列,就使用了2个指针,需要关注两个指针指向值的关系。
(2023年6月浙江选考)某工程包含n个任务(编号为0~n-1),每天可以有多个任务同时进行。某些任务之间有依赖关系,如图a所示,任务4依赖于任务1,任务1依赖于任务2。即任务2完成后才可以开始任务1,任务1完成后才可以开始任务4。不存在一个任务依赖于多个任务,或多个任务依赖于同一个任务的情况。现已对该工程的依赖关系进行了梳理,结果如图b所示,标记“T”表示依赖关系需保留,标记“F”表示依赖关系需删除。
定义如下erase(lst)函数,参数lst列表的每个元素表示一个依赖关系。函数的功能是删除标记为“F”的依赖关系,返回保留的依赖关系的个数。
任务A 任务B 标记
0 5 T
5 4 F
4 1 T
1 2 T
2 3 F
注:任务A依赖于任务B。
图b
def erase(lst):
　i=0
　j = len(lst)-1
　while i<= j:
　　　if lst[i][2]== 'T':
　　　　　i+=1
　　　else:
　　　　　if lst[j][2] == 'T':
　　　　　　 lst[i]=lst[j]
　　　　　　 i + = 1
　　　　　j - = 1
　return i
若lst列表依次存储图b所示的依赖关系,如lst[0]为[0,5,'T'],调用erase(lst)的数,则语句“lst[i] =lst[j]”的执行次数为　　　　。
答案　1
解析　本题考查数组的遍历、链表的遍历、创建等操作。变量i和j分别指向数组lst的头尾元素位置,从头元素开始遍历,若遍历的元素lst[i][2]不是'T',将尾元素为'T'的元素覆盖当前元素,并将变量j向前移动。在图b中,当i值为1时,标记为F,由于尾元素也不是T,因此仅仅变量j向前移动,变量i并未增加,再次遍历时,将一条为T的元素覆盖,因此该语句只执行了一次。
知识梳理
2
1.双指针遍历通过使用　　　　个指针来遍历同一数据集合,或两个不同的数据集合,有效地解决一些需要同时考虑多个元素的问题。
2.两个指针可能同时　　　　,也可能按某种规则独立移动。
3.确保双指针初始化正确,理解每个指针的　　　。
4.明确指针移动的　　　　以及停止遍历数据集合的条件
两
移动
作用
条件
课堂突破
3
【典例1】 现有两个升序数组a和数组b,现在要求将数组b合并数组a,依旧保持数组a升序。实现的代码如下。
a=[2,3,5,7,9,11];b=[2,4,6]
for i in range(len(b)):
　a=a+[0]
i=len(a)-len(b)-1;j=len(b)-1
k=len(a)-1
while ①　　　　:
　if　②　　　　:
　　　a[k]=a[i]; i-=1
　else:
　　　a[k]=b[j]; j-=1
　③　　　
print(a)
(1)请将空白处填写完整。
(2)若①处代码填写为k>=0,会导致某些情况下无法得到预期的结果。下列4组数据中能测试出这一问题的是　　　　。
A.a=[2,4,6];b=[3,7] B.a=[4];b=[3,7]
C.a=[6];b=[2,3,4] D.a=[2,5,6];b=[1]
答案　(1)①j>=0　②i>=0 and a[i]思维点拨
明考向 本题考查双指针遍历数组的算法实现
精点拨 (1)程序的功能是将b中有序数据插入到a中,先在a中扩展len(b)个空间,将a和b中数据依次移动到a数组从后面开始的位置中。①若将b中全部数据移动到a中,a中原来数据是有序的,不管a中数据有没有遍历完,合并后的数据肯定是有序的。②为移动a前面数据的条件,当a[i]大于b[j]且a中数据没有合并完,否则就将b的数据移动到a中。③无论移动a还是移动b中数据,k的指针始终会往前移动。(2)在比较过程中,要确保数据a[i]和b[j]是一个有效的位置上数据,因此②中不能缺少i>=0,当b中数据全部移动到a中后,j的值为-1,此时k还没有到达0,因此再将比较时,j就不是原来的有效位置了
【变式1】 数组a中存储着n个范围为[0,n-1]的随机整数,现要在数组a中找到一个最长的区间,使得该区间里没有重复的元素,输出该区间的长度。提示:用flag数组记录各个数字最后出现的位置,用变量left记录区间的左边界。遍历数组a,若当前数字出现位置大于等于左边界,说明该数字在区间内,需更新左边界。
#随机产生n个范围为[0,n-1]的随机整数并存储在数组a中,代码略
n=len(a)
flag=[-1]*n
length=left=0
for i in range(0,len(a)):
　if ①　　　　 :
　　　if i-left+1>length:
　　　　length=i-left+1
　　　　②　　　
　else:
　　　left=flag[a[i]]+1
　③　　　
print("该区间的最大长度为:",length,",区间内的值为:",a[beg:beg+length])
(1)请将空白处填写完整。
(2)若将程序加框处代码修改为flag=[0]*n,可能得不到正确答案,下列能测试出这个错误的一组数据为　　　　。
A.[0, 3, 0, 2, 1] B.[1, 1, 2]
C.[1, 3, 0, 2] D.[0, 0, 3, 3, 2]
答案　(1)①flag[a[i]]解析　本题考查双指针遍历数组的算法实现。
(1)①若遍历到的数a[i]没有出现过(flag[a[i]]值为-1)或者上次出现的位置比左边界小,那么说明该数字不在区间中,可以进行最大长度区间的统计。②根据输出语句中区间内的值可知该处将对beg赋值。③若该数字出现在区间中,那么应更新这个区间的左边界。更新该数字出现的位置。(2)flag初值为-1表示未出现过该字符,若用0表示未出现过,与位置0混淆,因此当索引位置0的数字再次出现时,不能判断出是未出现过还是位置在0。A、B和D选项最长区间的开始位置均不为0。
【典例2】 自定义函数f的功能是实现列表a中所有x的倍数移动到左边,如数组a为[5,9,4,3,6],执行f(a,3)后,其值为[6,9,3,4,5],代码如下:
def f(a,x):
　i=0;j=len(a)-1
　while i　　　if　　　　　　　　　　　　　:
　　　　　a[i],a[j]=a[j],a[i]
　　　　　i+=1;j-=1
　　　elif a[i]%x==0:
　　　　　i+=1
　　　else:
　　　　　j-=1
　return a
则划线处代码为(　　)
A.a[i]%x==0 and a[j]%x==0
B.a[i]%x!=0 and a[j]%x==0
C.a[i]%x==0 and a[j]%x!=0
D.a[i]%x!=0 and a[j]%x!=0
答案　B
思维点拨
明考向 本题考查双指针遍历数组的算法实现
精点拨 指针i指向列表a的第1个位置,指针j指向列表a的最后一个位置,若前面的数不能x整除,且后面的数能被x整除,交换两个数的位置;若前面的数能被x整除,指针i向后移动;否则就是两个数均不能被x整除,指针j向前移动。重复这个过程,直到i大于等于j
【变式2】 (2026年1月浙江选考)有如下Python程序段:
#获取a的初始值,代码略
i=1
for j in range(1, len(a)):
　　if a[j]　　　　a[i], a[j]=a[j], a[i]
　　　　i+=1
a[0], a[i-1]=a[i-1], a[0]
执行该程序段后,a的值为[2,4,3,5,6,9,7],则下列选项中不可能为a[0]的初始值的是 (　　)
A.2 B.5
C.6 D.7
D
解析　本题考查排序算法思想。变量i的初值为1,指针j从索引1开始遍历数组a,若满足条件a[j]　　指针往往就是数据集元素或数据项的下标,首先要明确每个指针指向哪个列表,即表示是哪个数组中的对象,再用图示画出这个数据结构,帮助理解指针移动过程,理解遍历的顺序。理解每个指针的作用,根据指针移动的条件,这两个指针可以同时移动,也可以独立移动。往往根据指针的移动情况,确定遍历数据集合的条件。
当堂检测
4
1.有如下Python程序段:
a=[1]*6
b=[96,88,84,91,99,80]
for i in range(5):
　for j in range(i+1,6):
　 　　if b[j] > b[i]:
　　 　 　a[i]+=1
　　 　else:
　　 　 　a[j]+=1
print(a)
该程序段运行后,列表a的值为(　　)
A.[5,3,2,4,6,1] B.[2,4,5,3,1,6]
C.[10,6,4,8,12,2] D.[4,8,10,6,2,12]
B
解析　数组a记录b中对应数字的名次。 变量i从0开始遍历到4,变量j从i+1遍历到最后,若数组b中后面的数b[j]比当前的数b[i],则对a[i]进行计数,表示后面比他大的数的个数。以96为例,后面比他大的数只有99,因此他的位次为2。
2.有如下Python程序段:
s1="1324";s2="abcdefgh"
j,m=0,0
c=""
for i in s2:
　k=int(s1[j])
　c+=s2[m+k]
　j+=1
　if j>3:
　　　j=1
　　　m=m+2
print(c)
运行程序,输出结果是 (　　)
A.acbdefeg B.bdcefegh
C.bcdefegh D.bdceefgh
B
解析　将字符串s2看成前面4个字符和后面4个字符各2组,本题考查字符串处理知识。可以使用模拟法解题,答案是B。
3.有如下Python程序段:
p={};s=input()
for i in range(len(s)):
　p[s[i]]=i
i=0
while i　 n=p[s[i]]
　 j=i+1
　while j<=n:
　　 　if p[s[j]]>n:
　　　 　　n=p[s[j]]
　　 　j=j+1
　print(s[i:j])
　i=j
若输入“arrayiybi”,则输出结果的最后一行内容是(　　)
A.arra B.yiy
C.iybi D.yiybi
D
解析　将输入的字符串划分为几个子串,同一个字母只出现在同一个子串中并分段输出。字典p记录每种字母的最大索引值,字符串“arrayiybi”分成“arra”和“yiybi” 2个子串。
4.下列程序执行后的结果为(　　)
L=[1,-2,3,7,-8,9,10]
i,j=0,len(L)-1
while i　while L[i]>=0:
　　　i=i+1
　while L[j]<0:
　　　j=j-1
　if i　　　L[i],L[j] = L[j],L[i]
print(L[6])
A.3　　　　　　B.9　　　　　　C.-2　　　　　　D.-8
C
解析　在左边找到第1个小于0的数的位置i,在右边找到大于等于0的数的位置j,若i小于j,则交换两个位置上的数。程序的功能是把左边小于0的数交换到右边。第一次是-2和10交换,第2次是-8和9交换,交换后的序列为[1, 10, 3, 7, 9, -8, -2]。
5.如下 Python 程序段的功能是:删除数组 a(元素个数为 n)中重复元素并输出,例:a=[2,3,3,1,5,1,8],则输出 [2,3,1,5,8]。从1,5,1,8变为1,5,8来看,删除后面重复的数字。
i=0
while i　r=i+1
　for j in range(i+1,n):
　　　if (1)________:
　　　　　(2)______
　　　　　r+=1
　n=r
　i+=1
print(a[:r])
则划线处应填入的代码为(　　)
A.(1)a[i]==a[j] (2)a[r]=a[j]
B.(1)a[i]==a[j] (2)a[i]=a[r]
C.(1)a[i]!=a[j] (2)a[r]=a[j]
D.(1)a[i]!=a[j] (2)a[i]=a[r]
C
解析　从1,5,1,8变为1,5,8来看,删除后面重复的数字。从输入语句来看,r表示不重复数字个数。a[i]与a[j]不相等的时候,表示目前不重复的数据将增加一个,将a[j]往前移动到r的位置;若a[i]与a[j]相等,则j向后移动,而r并没有向后移动。
6.某市要组织高中生参加竞技比赛。现要求在报名的n名学生中挑选出身高大于等于175 cm的学生,被挑选出的学生两两组队,且队内两名成员的体重之和不能超过140公斤,找出最多的组合数量。(提示:在符合身高要求下,按体重降序排列,体重最大的和体重最轻的组合,达到组合数量最多。)
实现上述功能的Python程序如下,请在划线处填上合适的代码。
#将学生的姓名,身高和体重依次存储到数组a中,代码略
n=len(a)
for i in range(n-1):
　　for j in range(n-1,i,-1):
　　　　if a[j][2]>a[j-1][2] and (a[j][1]>=175 and a[j-1][1]>=175):
　　　　　　a[j],a[j-1]=a[j-1],a[j]
　　　　elif ①________:
　　　　　　a[j],a[j-1]=a[j-1],a[j]
　　if a[i][1]<175:
　　　　nlen=②______
　　　　break
i=0;j=nlen
while i　　if a[i][2]+a[j][2]<=140:
　　　　print(a[i],a[j])
　　　　i+=1
　　　　j-=1
　　else:
　　　　③______
答案　①a[j][1]>=175 and a[j-1][1]<175　②i-1　③i+=1
解析　本题考查多个过程的重复遍历。选出身高大于等于175 cm的学生,队内两名成员的体重之和不能超过140公斤,找出最多的组合数量,应挑选出身高大于等于175且按体重降序排列,体重最大的和体重最轻的组合,达到组合数量最多。①把身高达到要求的学生尽量往前排,即后面的身高大于等于175,后面的没有达到要求,不论体重。均要向前交换。②由于从后往前冒泡,前面的数据先有序,当条件a[i][1]<175成立时,表示索引i-1的数据中身高是大于等于175的。③当条件a[i][2]+a[j][2]<=140不成立时,意味着较重体重的选手不可能匹配到更轻体重的选手,因此要找下一位选手。
课时作业
5
1.有如下Python程序:
#输入包含5个不重复元素的数组a,代码略
i,c=0,0
key=int(input("key="))
for i in range(len(a)):
　if a[i]%key==0:
　　　c+=1
　else:
　　　j=i-c
　　　a[j]=a[i]
print(a)
D
解析　遍历数组a,变量c表示a[j]整除key(偶数)个数,若不是偶数,将其放在前面。A选项a初始值是[3,7,偶,4,5],偶表示该位置上是一个偶数。B选项第4个是偶数,则后面的5覆盖而来。C选项a初始值是[偶,偶,0,3,5]。D选项第2个是偶数,则7覆盖第2个数,但3一定要覆盖4。
2.有下列Python程序段:
s1="pytorch";s2="python";s=""
i=0;j=0
while i　　if s1[i] > s2[j] :
　　 　s=s+s1[i]
　　else:
　　 　j+=1
　　i+=1
执行以上程序段后,s中的值是(　　)
A."or" B."ch"
C."on" D."to"
A
解析　用指针i和j分别遍历字符串s1和s2的各个位置,在两个字符串都没有遍历完前,指针i每次向后移动一个位置,当s1[i]大于s2[j],则将s1[i]连接入s中,指针j向后移动一个位置。前面3个字符均相等,"o"大于"h","r"大于"o","c"和"h"均小于"o",结束循环。
3.有如下Python程序段:
s=[3,4,3,2,1, 5,4,5,8,7,5,6,1,2]
ans=0
for i in range(0,(len(s)-1)∥4*4,4):
　tmp=s[i]
　for j in range(1,4):
　　　if s[i+j]>tmp:
　　　　tmp=s[i+j]
　ans+=tmp
执行该程序段后,变量ans的值为(　　)
A.17 B.19
C.8 D.9
A
解析　每4个数据为一组,依次找出每组中最大值,并将这些最大值进行累加。
4.有如下Python程序段:
s1='blgr';s2='bollymgpric'
i=0;j=0;s3=''
while i<=len(s1)-1 and j<=len(s2)-1:
　if s1[i]==s2[j]:
　　　i+=1
　else:
　　　s3=s3+s2[j]
　j+=1
print(s3)
执行该程序段后,输出的内容为(　　)
A.oymp B.olymp
C.olympic D.oympic
B
解析　指针i和j分别遍历s1和s2字符串,只要有一个字符串遍历完,结束程序运行。指针j每次向后移动一个位置,变量i只有当s1[i]和s2[j]相等时才移动,若不相等,则将s2[j]连接到s3中。
5.已排序的列表a有n个整型元素,现要删除a中重复出现的元素,使每个元素只出现一次,并输出去重后的结果。实现该功能的程序段如下:
上述程序段中方框处可选代码为:
①q则(1)(2)(3)处代码依次为(　　)
A.①③⑥ B.①④⑤
C.②③⑤ D.②④⑥
A
解析　语句q+=1每循环一次就执行一次,因此q表示当前位置,所以(1)中填写q6.有如下Python程序段:
def half_s(s):
　n=len(s);result=""
　i,j=0,n-1
　while i=n∥2:
　　　if s[i]>s[j]:
　　　 　　result+=s[i];i+=1
　　　elif s[i]　　　 　　result+=s[j];j-=1
　　　else:
　　 　　　i+=1;j-=1
　return result
执行语句v=half_s("welcome"),变量v的值是(　　)
A."come" B."wmol"
C."www" D."emo"
B
解析　变量i从前往后遍历,变量j从后往前遍历,将s[i]和s[j]中较大者拼接到result中,若两者相等,直接略过。w和e比较,w大;e和e相等;l小于m;o大于l;l大于c;此时i的值为3,不满足条件i7.下列程序段是数组a中的数据分为被3整除、除3余1和除3余2共三部分:
#列表 a 初始值略
i=k=0;j=len(a)-1
while k<=j:
　if a[k]%3==0:
　　　a[i],a[k]=a[k],a[i]
　　　i+=1
　elif a[k]%3!=1:
　　　a[j],a[k]=a[k],a[j]
　　　k-=1;j-=1
　k+=1
运行该程序段后,这三部分对应的列表依次是(　　)
A.a[:i],a[i:j],a[k:] B.a[:i+1],a[i:j+1],a[j+1:]
C.a[:i],a[i:k],a[k:] D.a[:i+1],a[i:j],a[k+1:]
C
解析　指针i和j分别指向数组的头和尾,变量k从0开始遍历数组,当条件a[k]%3==0成立时,交接a[i]和a[k],指针i向后移动,即把3的倍数交接到位置i的前面。当a[k]%3的值为2时,交接a[j]和a[k],指针j向前移动,即把除3余2的数交接到位置j的后面。当k等于j+1时,结束循环。因此[0,i-1]区间是3的倍数。[i,j]或[i,k-1]区间保存除3余1的数,j+1或k开始的数是除3余2。
8.对一组正整数的奇偶数进行交换。交换后偶数在前,奇数在后,并保持相对顺序不变。
a=[5,10,21,7,24,14,9,11,36,37]
n=len(a);b=[0]*n
num=0;k=0
while k 　　if　①________:
　　　　b[num]=a[k]
　　　　num+=1
　　else:
　　　　②______
　　k+=1
for j in range(n-num,n):
　　③______
print(a)
(1)请将空白处填写完整。
(2)若将加框处修改为for j in range(num):,则③处应填写为 ________。
答案　(1)①a[k]%2==1　②a[k-num]=a[k]　③a[j]=b[j-(n-num)]　
(2)a[n-num+j]=b[j]
解析　(1)①遍历数组a,若为奇数,将其移动到b数组中,若为偶数,将其移动到前面的位置。②遍历到索引位置k时,共遍历到数有k+1个中,其中有num个奇数,有k+1-num个偶数,最后一个偶数的索引位置为k-num。③遍历一次后,n-num个偶数已经放在[0,n-num-1]的位置上,因此需将所有的奇数转换到从n-num开始的位置中,因此变量j表示其在数组a中位置[n-num,n-1],数组b的下标为[0,num-1],两个下标的差值始终为n-num,设b中下标为x,则有j-x=n-num,可以得到b中下标。(2)加框处修改为for j in range(num),则j表示在数组b中位置,那么设数组a中下标为x,则有x-j= n-num,可以得到a中下标。
9.有2组器件要用一台检测设备检测。每个送检器件的信息包含送达时间、检测时长和优先级。每个器件的送达时间各不相同,编写程序合并2组器件的数据,为后续检定做准备。已知,lst1和lst2的每个元素由送达时间、检测时长和优先级3项构成,例如某送检器件的送达时间为8点整,检测时长为1小时,优先级为2,则存储元素的格式为["08:00", 1, 2]。 lstl和lst2均已按送达时间升序排列,合并后保持按送达时间升序。
(1)实现功能的程序如下,请在划线处填入合适的代码。
lst=[]
i=j=0
while i 　　if　①________:
　　　 　lst.append(lst1[i])
　　　 　i+=1
　　else:
　　 　　lst.append(lst2[j])
　　 　　②______
print("数据合并后,数组元素为:",lst)
(2)while语句的条件“i A.能　　　　B.不能
答案　(1)①j==len(lst2) or 1st1[i][0]解析　(1)①将lst1[i]添加到lst中去的条件有2个,一是lst2已经遍历完,二是lst1[i][0]小于lst2[j][0]。②j是lst2的指针,每添加一个指针向后移动一个位置。(2)条件i

展开更多......

收起↑