资源简介

(共66张PPT)
选修一　数据与数据结构
课时21　数　组
知识点 学业水平等级
1.知道数组的概念和特性,能够辨别程序设计中数据的组织形式,领会数据结构对数据处理的重要性。 3
2.针对生活中简单的实际问题,根据数据及其关系特征,选择数组组织、存储数据,编写程序实现相关操作,并能迁移到与之相关的其他问题中解决。 4
目 录
CONTENTS
真题剖析
01
知识梳理
02
课堂突破
03
当堂检测
04
课后作业
05
真题剖析
1
　　存储在数组中的数据,每个元素有固定的下标,可以通过下标快速地访问,数据元素相对简单的情况下,采用数组更加有利于数据处理。在2023年6月和2024年6月第13题中,均用数组存储相关数据,并遍历数组,提取相应的结果。在2023年1月和2024年1月的信息搭建和利用pandas处理数据时,数据也是存储在数组中,对这些结构化数据进行处理。
(2024年6月浙江选考)数组元素a[0]至a[n-1]依次存放着n个数据,现需要将元素a[n-1]插入在下标为x(0≤xtemp=a[n-1]
for i in range(n-2,x-1,-1):

a[x]=temp
A.a[i+1]=a[i] B.a[i-1]=a[i]
C.a[i]=a[i+1] D.a[i]=a[i-1]
A
解析　本题考查插入排序的算法实现。先将7保存在a[n-1],变量i从n-2遍历到x,将当前位置i后面的值移动到当前位置。
知识梳理
2
1.计算机中数据的存储结构主要分为　　　　存储结构和非顺序存储结构。
2.顺序存储结构是将逻辑上相邻的数据节点存储在物理位置　　　　的存储单元中,典型代表为数组。
3.非顺序存储结构的形式就是链式存储结构,在链式存储结构中可以将逻辑上相邻的数据节点在内存中分开存储,节点之间的前后关系由每个节点中的
　　　　确定,典型代表为链表。
4.数组名和　　　　组成数组的各个变量称为数组的分量,也称为数组元素。
5.一维数组只有　　　　个下标,下标用来表示数据元素在该序列中的位置。
顺序
相邻
指针
下标
一
6.二维数组有　　　　个下标,表示数据元素在该序列中的行、列位置,二维数组有行优先存储和列优先存储。
7.用列表来模拟数组,通过列表名和下标对数组元素的值直接进行访问。列表的索引(下标)支持负数,如luck[-1]指向数组luck中最后一个元素。
8.数组使用前往往要先初始化数组元素的值,如创建一个值全为0的8个元素的数组lst的语句为lst=　　　　　。如创建一个值依次为0-7的8个元素的数组lst的语句为lst=[　　　　for i in range(8)]。
9.二维数组的创建需用双重循环来实现,如创建一个4行5列,每行值依次为0-4的二维数组,语句为lst=[[　　 for j in range(5)]for i in range(　　)]。
两
[0]*8
i
j
4
课堂突破
3
【典例1】 用数组a和b存储两个降序序列,用数组c存储合并后的降序序列。如a=[19,16,12,8,5],b=[20,15,14,10,6],c=[20,19,16,15,14,12,10,8,6,5]。实现该功能的程序段如下:
c=[- 1]*(len(a)+len(b))
p=0;tot=len(a)
for i in range(len(a)):
　(1)　　　
for i in range(len(b)):
　while b[i]　　 p += 1
　if c[p]==-1:
　　 c[p]=b[i]
　else:
　　　for j in range( (2)　　　　):
　　　 　c[j+1] = c[j]
　　 c[p] = b[i]
　tot+=1
上述程序段划线处(1)(2)可选代码为:
①c.append(a[i])　②c[i]=a[i]　③tot,p-1,-1　④tot,p,-1　⑤tot-1,p-1,- 1
则(1)(2)处的代码依次为(　　)
A.①③ B.①④
C.②⑤ D.②③
答案　C
思维点拨
明考向 本题考查数组元素的合并
精点拨 (1)将数组a中数据写入数组c中,由于数组c中已经有len(a)+len(b)个-1,因此不用再用append方法添加。(2)遍历数组b,并将元素插入到数组c中。tot的初值为len(a),每添加一个数组b的元素,tot值加1,因此tot表示已经合并元素的个数。p表示数组元素b要插入到c中的位置。语句c[j+1] = c[j]是把当前位置j元素移动到后面一个位置,因此j的初值为tot-1,终值为p。range是一个左闭右开的区间,若要取到p,终值需加上步长
【变式1】 数组元素a[0]至a[n-1]依次存放着n个整数,现要用last将数组元素划分成两部分,小于key的整数均位于last的左侧。例如:n为5,数组a为[3,9,7,4,8],key为7,完成划分后last为2,数组a为[4,3,7,9,8]。实现该功能的程序段如下:
from random import randint
k=randint(0,n-1);key=a[k]　#从数组a中随机选择一个整数赋值给key
a[0],a[k]=a[k],a[0]
上述程序段方框中(1)(2)(3)可选代码为:
①last=-1　②last=0　③a[last],a[i]=a[i],a[last]　④last+=1　⑤a[last]=a[i]
则(1)(2)(3)处的代码依次为(　　)
A.①③④ B.①④⑤
C.②④③ D.②⑤③
解析　本题结合快排处理中数据划分思想,考查学生在代码应用中的逻辑推理能力。从数组a中任选一个数作为key,换到a[0]位置,接着扫描后面所有的数,若a[i]C
【典例2】 有如下Python程序段:
a=[[1,3,6,9],[2,4,7,5],[5,2,3,8]]
b=[1]; n=len(a)
for i in range(n):　　
　 for j in range(n+1):
　　　if i　　　　 b.append(a[i][j])　#b追加一个元素a[i][j]
执行该程序阶段后,数组b中的元素为(　　)
A.[1,3,6,9,7,5,8] B.[3,6,9,7,5,8]
C.[1,3,6,9,2,4,7,5,8] D.[1,3,6,9,4,7,5,8]
答案　A
思维点拨
明考向 本题考查二维数组的应用
精点拨 将二维数组a中下标i【变式2】 有如下Python程序段:
b=[];n=len(a)
for i in range(n):
　for j in range(len(a[i])):
　　　if i　　　 　b.append(a[i][j])
C
解析　本题考查二维数组的应用。程序的功能是在矩阵的右外角中查找不重复的数。A、B和D选项程序运行后,数组b的值均为[3,6,7,9]。C选项程序运行后,数组b的值为[3,6,7,9,8]。
　　数组是典型的顺序存储结构,是将逻辑上相邻的数据节点存储在物理位置相邻的存储单元中,最大特点是可以通过下标来直接访问某个数组元素,因此访问数组元素较快。若要删除数组中间位置某个元素,必须将该元素后面的元素一个个往前移动,若在中间位置前插入一个新元素,必须将其后面的元素一个个往后移动,因此插入或删除元素的效率较低。
m行n列的二维数组可以看成有n个一维数组共享m个下标的集合,在数据加工处理时,效率会比一维数组高。在处理二维数组的题目时,先要画出二维数组的结构,理解每个数组元素的含义,理解如何定位到某个数据项。
当堂检测
4
1.已知列表a=[2,3,4,5],要将列表a更新为[1,2,3,4,5],则下列可实现该功能的操作是(　　)
A.a="1"+a B.a.append(1)
C.a=[1]+a D.a=1+a
C
解析　本题考查向列表中添加元素。要向列表添加元素,主要有两种方法,1.append(),但该方法在列表的末尾添加元素,不符合题目要求;2.通过列表相加得到新列表,即如C所示,可以实现该功能。
2.有如下Python程序段:
s="Secret";t=[1,0,2]
r=[""]*len(s)
for i in range (len(s)):
　m=t[i % len(t)]　
　if i　　　r[m]=s[i]
　else:
　　　r[m+len(t)]=s[i]
print ("".join(r))　#将列表r中的元素连接起来,并返回一个新字符串
运行该程序段后,输出的结果是(　　)
A.Secret B.eScert
C.retSec D.ceSter
B
解析　变量m在数组t索引中循环,即m的依次为0,1,2,0,1,2。程序的功能是将字符串s分成两组,每组将原来0,1,2位置依次存储1,0,2的位置。
3.有如下Python程序段:
#随机产生5个整数,存储在列表a中
for i in range(1,5):
　k=a[i]
　j=i-1
　while j >= 0 and abs(a[j]-2)>abs(k-2):
　　　a[j+1]=a[j]
　　　j-=1
　a[j+1]=k
执行该程序段后,列表a的值可能是(　　)
A.[-5,-2,4,0,1] B.[3,-1,0,2,-3]
C.[1,2,3,4,5] D.[0,4,0,-2,-4]
D
解析　程序功能是按abs(a[i]-2)升序排序,即最后每个数据项减2后求绝对值应为升序。
4.已知列表a中包含100个随机数(随机数的范围为0-9),现要输出每个数字在序列中的排名,数字越小,排名靠前(从1开始计数),且当数字大小相同时,排名相同,下一组数字的排名为当前数字排名加上当前数字的数量,如列表a中部分数据为[9,2,1,6,2,6,1,9,7,2],则其排名依次为“9 3 1 6 3 6 1 9 8 3”,实现该功能的程序段如下,方框中应填入的正确代码为(　　)
b=[0]*10
for i in a:
　b[i]+=1

print(s)
B
解析　本题考查数组基本操作以及桶的思想。b数组存储0-9每个数字出现的次数,c数组存储每个数字在数组中的名次。下一组数字的排名为当前数字排名加上当前数字的数量,执行c[i]=b[i-1]+c[i-1],对名次进行累加。最后输出100个数字对应的在此数组的名次,由于名次从1计数,而c数组每个元素初始值为0,故输出时每个名次加1。
5.有如下Python程序段:
n=6
a=[[0]*n for i in range(n)]
for i in range(n):
　 for j in range(i+1):
　　 if j!=0 and j != i:
　　　 　a[i][j]=a[i-1][j-1] + a[i-1][j]
　　 else:
　　　 　a[i][j]=1
程序执行后,a[4]的值是(　　)
A.[1,3,3,1,0,0] B.[1,4,6,6,4,1]
C.[1,4,6,4,1,0] D.[1,5,10,10,5,1]
C
解析　本题考查二维数组的创建和遍历。先创建一个6行6列的二维数组,遍历二维数组的每一行,内循环从0至i,因此只对二维数组的左下半部分进行赋值。将第1列和主对角线(i和j相等)的数据全部赋值为1,其他数据为上一行的前一个和上一行的当前列之和,因此程序的功能是构建一个杨辉三角。
6.有如下Python程序:
a=[43,23,87,67,80]
queinfo=[]
for item in a:
　k=0
　while k　　 　if item>=queinfo[k][-1]:
　　 　　break
　　 　k+=1
　if k==len(queinfo):
　　 　queinfo.append([item])
　else:
　　 　queinfo[k].append(item)
print(len(queinfo))
执行该程序段后,输出的结果是(　　)
A.1 B.2
C.3 D.4
B
解析　queinfo初值为空,语句queinfo.append([item])是将一个列表添加到queinfo,因此他是一个二维数组。遍历列表a,在queinfo数组从第0个元素开始,与每个元素最后一个数据项进行比较,如果大于等于元素最后一个数据项,结束比较,此时j肯定在0至len(queinfo)-1之间,若j的值为len(queinfo),说明该元素比queinfo中每个元素的最后一个值均小,则新成一组。queinfo的值为[[43, 87], [23, 67, 80]]。
7.将数组b合并到非降序数组a中,依旧保持数组a有序。则划线处应填写的代码是(　　)
for i in range(len(b)):
　a.append(0)
for i in range(len(b)):
　 ①　　　
　 while j>=0 and a[j]>b[i] :
　　　a[j+1]=a[j]
　　　j-=1
　 ②　　　
D
A.①j=len(a)-len(b)　②a[j]=b[i]
B.①j=len(a)-len(b)+i　②a[j+1]=b[i]
C.①j=len(a)-len(b)-1+i　②a[j]=b[i]
D.①j=len(a)-len(b)-1+i　②a[j+1]=b[i]
解析　本题考查数组元素的移动。①程序的功能采用插入排序,将数组b中数据插入到数组a中,保持数组a为一个升序的序列。语句j=len(a)-len(b)-1+i的作用是取出数组a中最后有序的位置,while的功能是在数组a中找到b[i]应插入的位置,因此查找的条件是a[j]大于b[i],但同时保证j的位置是有效的。②找到第1个不符合条件位置j,那么数据b[i]应插入的位置是j+1。
8.(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.ia[i+1]
C.ia[i+1] D.i<=n-1 or t>a[i]
B
解析　本题考查顺序查找和插入排序。先将a[pos]+1的值存入变量t,即要将t插入到正确的位置以确保数组仍然有序。因原数组元素已升序排列,所以从pos位置开始向后顺序查找正确位置,并在查找的同时进行数组元素的前移操作,以便空出t应该在的位置。整个while循环即使实现上述功能,循环条件应为:确保语句a[i]=a[i+1]不能超出数组范围(即i+1<=n-1或ia[i+1])。C选项语句t=a[pos]+1中,并没有改变a数组元素的值,因此a[i]>a[i+1]不可能成立。
课时作业
5
1.有如下Python程序段:
c,m=0,0
for i in range(2,len(a)):
　if a[i-2]+a[i-1]==a[i]:
　　　c+=1
　　　if c>m:
　　　　 m=c
　else:
　　　c=0
若列表a=[2,1,3,4,5,9,14,23],执行该程序段后,变量m的值是(　　)
A.0 B.1
C.2 D.3
D
解析　从第3个位置开始遍历,若该位置上值是前两个位置上数之和,统计连续符合这些条件的数据个数c,并找出c的最大值m。数据3,4符合条件,共连续2个数。数据9,14,23符合条件,共连续3个数。
2.有如下Python程序段,功能为删除非降序序列中的重复数:
a=[2,2,2,5,5,5,8 ]
k=i=0
while (1)　　　　:
　if a[i]!=a[i+1]:
　　　k+=1
　　　(2)　　　
　i+=1
print(a[:k+1])
该程序执行结果为[2,5,8],划线处可选代码为
①i则(1)(2)处代码依次为(　　)
A.①③ B.①④
C.②③ D.②④
C
解析　从输出语句print(a[:k+1])来看,k表示删除重复后数字个数。a[i]和a[i+1]比较,因此i的最大位置只能为len(a)-2。k的初值为0,保存了第1个数字,当条件a[i]!=a[i+1]成立时,k先加1,因此将a[i+1]保存到a[k]中。
3.有如下Python程序段:
a=[3, 3, 7, 8, 8, 10, 12, 99]
j=k=res=0
for i in range(len(a)-1):
　while a[j]-a[i]<5:
　　　 j=j+1
　while a[k]-a[i]<= 5:
　　　 k=k+1
　if a[j] - a[i] == 5 and a[k-1] - a[i] == 5:
　　　 res+=k-j
执行程序后,变量res 的值是(　　)
A.2 B.3
C.4 D.5
D
解析　程序统计两个数相减等于5的不同位置上数对的数量。当i为0时,j和k的值为3和5,res值为2;当i为1时,j和k的值不变,res累加为 4;i为2时,j和k的值为6和7,res值为5;再往后遍历,res值不变。
4.有如下Python程序:
#输入包含5个不重复元素的数组a,代码略
i,c=0,0
key=int(input("key="))
for j in range(len(a)):
　if a[j]%key==0:
　　　c+=1
　else:
　　　a[j-c]=a[j]
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。
5.已排好序的列表 a 有 n 个元素,下标为 0~n-1,现要实现去重,并输出去重后的结果。如:1,2,2,3,输出 1,2,3。实现该功能的程序段如下,方框中应填入的代码为(　　)
#输入列表 a 的元素,并排好序
cnt=0
n=len(a)
A
A.for i in range(1,n):
　 　if a [i]!=a[i-1]:
　　　　cnt+=1
　　　　a[cnt]=a[i]
B.for i in range (n-1):
　 　if a [i]!=a[i+1]:
　　　　a[cnt]=a[i]
　　　　cnt+=1
C.i=0
　while i　　 if a[i]!=a[i+1]:
　　　　cnt+=1
　　　　a[cnt]=a[i]
　i+=1
D.i=1
　while i　　if a[i]!=a[i-1]:
　　　　cnt+=1
　　　　a[i]=a[cnt]
　　i+=1
解析　本题考查数据的去重。A选项当数组前后两个值不同时,进行计数,并将该数保存a[cnt]中。C选项当a[0]和a[1]不同时,赋值语句功能为a[1]=a[0],即重复地将第一个数据存入到下个为止。D选项当a[0]和a[1]不同时,赋值语句功能为a[1]=a[1],此时若第二个不同出现在a[2]和a[3],则赋值成a[3]=a[2],不满足将不同的值列下,即输入的数据为[1,2,2,3]时,输出结果为[1,2,2] 。
6.有如下程序段:
p=0
for i in range(len(a)):
　if not("a"<=a[i]<="z"):
　　　j=i;pt=a[i]
　　　while j>p:
　　　 　a[j]=a[j-1]
　　　 　j=j-1
　　　p=j;a[j]=pt
print(a[4])
若列表a=["-","p","y","-","t","h","o","n","-"],则运行该程序段后,输出的值为(　　)
A."-" B."p"
C."y" D."t"
C
解析　程序功能是将所有非小写字母字符向前移动,到所有小写字母以前,且小写字母相对位置不发生改变。故a运行结果为["-","-","-","p","y","t","h","o","n"]。
7.有如下Python程序段:
#生成5个随机整数,保存列表a元素a[0]~a[4]中,代码略
maxs=tmp=0
left=right=0
while right<5:
　tmp+=a[right]
　while left<=right and tmp>0:
　　　tmp-=a[left]
　　　left+=1
　if right-left+1>maxs:
　　　maxs=right-left+1
　right+=1
print(maxs)
执行该程序段后,输出结果为3,则a[0]~a[4]的值可能为(　　)
A.[4,0,0,-2,-3] B.[-2,-3,-4,6,7]
C.[-7,7,1,2,3] D.[-6,2,-1,6,0]
D
解析　本题考查Python程序设计。程序功能寻找列表a中连续子数组元素和小于或等于0的最大长度。right指针表示窗口右端点,left指针表示窗口左端点,窗口长度为right-left+1,更新最大长度maxs。将区间内的值不断地累加到tmp中,且tmp的值大于0,将左端点向后移动,同时在tmp中减去原左端点的值。A和B选项最大长度为4。C选项最大长度为2。D选项[-6,2,-1]之和小于0,最大长度为3。
8.有如下Python程序段:
n=4
a=[[i*n+j+1 for j in range(n)]for i in range(n)]
for i in range(n∥2):
　 for j in range(1 , n, 2):
　　　a[i][j], a[n-i-1][n-j-1]=a[n-i-1][n-j-1], a[i][j]
则程序执行后,a[1][1]和 a[2][0]的值分别为(　　)
A.6和9 B.8和9
C.11和9 D.11和8
D
解析　创建一个[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]的二维数组,遍历前2行,对其中偶数列按对称行和对称列进行交换。a[1][1]是原a[2][2]的值,a[2][0] 是原a[1][3]的值。
9.有Python代码段如下:
a=[11,4,2,13,6,5,3,6,19,1]
for i in range(1,len(a)):
　 key=a[i] ;j=i
　 while (1)　　　　 :
　　　a[j]=a[j-1]
　　　j-=1
　 (2)　　　
划线处(1)、(2)处可选代码如下:
①j>0 and key=0 and key为使得数组a实现升序排序,则划线处代码正确的是(　　)
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 key10.(2025年1月浙江选考)列表c长度为100,如图所示,其中c[10]~c[89]各元素的值均为10以内的随机正整数。执行如下程序段,输出的最后一行是(　　)
B
i 0 1 2 3 4 5 6 7 8 9 …… 90 91 92 93 94 95 96 97 98 99
c[i] 1 1 1 1 2 3 2 3 2 3 …… 2 3 2 2 2 2 1 1 1 1
pa=[0,0,0,0,0]
pb=[0,0,0,0,0]
h,t=0,4
tmp=0
for k in range(100):
　　pa[t]=c[k]
　　pb[t]=tmp+pa[t]-pa[h]
　　print(pb[h],pb[t],k,pa,pb,h,t)
　　tmp=pb[t]
　　h=(h+1) % 5
　　t=(t+1) % 5
A.5　4 B.8　4
C.9　5 D.9　9
解析　本题考查数据的累加求和循环列表的应用。指针h和t都是pb的下标,通过求余操作,当其值为5时,又回到0,即值在0至4的范围内循环,且t与h始终相差4,是一个循环列表。若三条语句pa[t]=c[k]、pb[t]=tmp+pa[t]和tmp=pb[t]在for语句内循环,则其功能是对c数组中数据进行累加求和,而pb[t]的值为tmp+pa[t]-pa[h],即累加求和的基础上减去pa[h],当k小于4时,pa[h]的值均为0,即pb的前4项依次为c数组累加和,pb[4]的值为c[0]至c[4]五项的和减去c[0]的值,因此pb[t]为第t项以及前4项的和。最后一次循环时,前4项的和是1+1+1+1=4,而h的值为t-4,该位置的前4项和为2+2+2+2=8。
11.生成n颗(n<=30)地雷随机放置在10×10的方格中,方块中出现地雷用#表示,出现数字,则表示在其周围相邻的方块中共有多少颗地雷,中间位置有8个方块相邻,边上位置有5个方块相邻,角上位置有3个方块相邻。程序运行的结果如图所示:
def Check(a,x,y):　#统计第x行第y列四周雷的个数
　count=0
　for i in range(x-1,x+2):
　　 for j in range(y-1,y+2):
　　 　if ①　　　　:
　　　　 if a[i][j]==9:
　　　　　　count+=1
　return count
import random
n=10
a=[[0 for j in range(10)]for i in range(10)]
m=int(input("输入地雷的个数"))
i=0
while i　x=random.randint(0, 9)
　y=random.randint(0, 9)
　if a[x][y]==0:
　　　a[x][y]=9
　　　②　　　
for i in range(n):
　for j in range(n):
if a[i][j]!=9:
　 　　　③　　　
for i in range(n):
　s=""
　 for j in range(n):
　　 if a[i][j]==9:
　 　　　s=s+"# "
　　 else:
　 　　　s=s+str(a[i][j])+" "
　print(s)
答案　①0<=i<10 and 0<=j<10　②i+=1　③a[i][j]=Check(a,i,j)
解析　本题考查二维数组和枚举算法。程序共分3部分,第1部分生成10×10的矩阵,并随机生成m个地雷,第2部分是统计不是地雷的格子周围有多少地雷,第3部分是输出。②随机生成x,y坐标,若该位置不是雷,则将雷的数量增加1,因此答案为i+=1。①采用枚举算法检测坐标x,y的上一行、当前行和下一行中,左右3列中雷的个数。但要注意边界问题,即必须在矩阵内。③调用自定义函数来检测坐标i,j周围雷的个数。课时21　数　组
【学业要求】
知识点 学业水平等级
1.知道数组的概念和特性,能够辨别程序设计中数据的组织形式,领会数据结构对数据处理的重要性。 3
2.针对生活中简单的实际问题,根据数据及其关系特征,选择数组组织、存储数据,编写程序实现相关操作,并能迁移到与之相关的其他问题中解决。 4
　　存储在数组中的数据,每个元素有固定的下标,可以通过下标快速地访问,数据元素相对简单的情况下,采用数组更加有利于数据处理。在2023年6月和2024年6月第13题中,均用数组存储相关数据,并遍历数组,提取相应的结果。在2023年1月和2024年1月的信息搭建和利用pandas处理数据时,数据也是存储在数组中,对这些结构化数据进行处理。
(2024年6月浙江选考)数组元素a[0]至a[n-1]依次存放着n个数据,现需要将元素a[n-1]插入在下标为x(0≤xtemp=a[n-1]
for i in range(n-2,x-1,-1):
a[x]=temp
A.a[i+1]=a[i] B.a[i-1]=a[i]
C.a[i]=a[i+1] D.a[i]=a[i-1]
答案　A
解析　本题考查插入排序的算法实现。先将7保存在a[n-1],变量i从n-2遍历到x,将当前位置i后面的值移动到当前位置。
1.计算机中数据的存储结构主要分为　　　　存储结构和非顺序存储结构。
2.顺序存储结构是将逻辑上相邻的数据节点存储在物理位置　　　　的存储单元中,典型代表为数组。
3.非顺序存储结构的形式就是链式存储结构,在链式存储结构中可以将逻辑上相邻的数据节点在内存中分开存储,节点之间的前后关系由每个节点中的　　　　确定,典型代表为链表。
4.数组名和　　　　组成数组的各个变量称为数组的分量,也称为数组元素。
5.一维数组只有　　　　个下标,下标用来表示数据元素在该序列中的位置。
6.二维数组有　　　　个下标,表示数据元素在该序列中的行、列位置,二维数组有行优先存储和列优先存储。
7.用列表来模拟数组,通过列表名和下标对数组元素的值直接进行访问。列表的索引(下标)支持负数,如luck[-1]指向数组luck中最后一个元素。
8.数组使用前往往要先初始化数组元素的值,如创建一个值全为0的8个元素的数组lst的语句为lst=　　　　　。如创建一个值依次为0-7的8个元素的数组lst的语句为lst=[　　　　for i in range(8)]。
9.二维数组的创建需用双重循环来实现,如创建一个4行5列,每行值依次为0-4的二维数组,语句为lst=[[　　 for j in range(5)]for i in range(　　)]。
自我校对:1.顺序　2.相邻　3.指针　4.下标　5.一
6.两　8.[0]*8　i　9.j　4
【典例1】 用数组a和b存储两个降序序列,用数组c存储合并后的降序序列。如a=[19,16,12,8,5],b=[20,15,14,10,6],c=[20,19,16,15,14,12,10,8,6,5]。实现该功能的程序段如下:
c=[- 1]*(len(a)+len(b))
p=0;tot=len(a)
for i in range(len(a)):
　(1)　　　
for i in range(len(b)):
　while b[i]　　 p += 1
　if c[p]==-1:
　　 c[p]=b[i]
　else:
　　　for j in range( (2)　　　　):
　　　 　c[j+1] = c[j]
　　 c[p] = b[i]
　tot+=1
上述程序段划线处(1)(2)可选代码为:
①c.append(a[i])　②c[i]=a[i]　③tot,p-1,-1
④tot,p,-1　⑤tot-1,p-1,- 1
则(1)(2)处的代码依次为(　　)
A.①③ B.①④
C.②⑤ D.②③
思维点拨
明考向 本题考查数组元素的合并
精点拨 (1)将数组a中数据写入数组c中,由于数组c中已经有len(a)+len(b)个-1,因此不用再用append方法添加。(2)遍历数组b,并将元素插入到数组c中。tot的初值为len(a),每添加一个数组b的元素,tot值加1,因此tot表示已经合并元素的个数。p表示数组元素b要插入到c中的位置。语句c[j+1] = c[j]是把当前位置j元素移动到后面一个位置,因此j的初值为tot-1,终值为p。range是一个左闭右开的区间,若要取到p,终值需加上步长
答案　C
【变式1】 数组元素a[0]至a[n-1]依次存放着n个整数,现要用last将数组元素划分成两部分,小于key的整数均位于last的左侧。例如:n为5,数组a为[3,9,7,4,8],key为7,完成划分后last为2,数组a为[4,3,7,9,8]。实现该功能的程序段如下:
from random import randint
k=randint(0,n-1);key=a[k]　#从数组a中随机选择一个整数赋值给key
a[0],a[k]=a[k],a[0]
(1)　　　　
for i in range(1,n):　　
　if a[i] < key:
　　(2)　　　　
　　(3)　　　　
a[0],a[last]=a[last],a[0]
上述程序段方框中(1)(2)(3)可选代码为:
①last=-1　②last=0　③a[last],a[i]=a[i],a[last]　④last+=1　⑤a[last]=a[i]
则(1)(2)(3)处的代码依次为(　　)
A.①③④ B.①④⑤
C.②④③ D.②⑤③
答案　C
解析　本题结合快排处理中数据划分思想,考查学生在代码应用中的逻辑推理能力。从数组a中任选一个数作为key,换到a[0]位置,接着扫描后面所有的数,若a[i]【典例2】 有如下Python程序段:
a=[[1,3,6,9],[2,4,7,5],[5,2,3,8]]
b=[1]; n=len(a)
for i in range(n):　　
　 for j in range(n+1):
　　　if i　　　　 b.append(a[i][j])　#b追加一个元素a[i][j]
执行该程序阶段后,数组b中的元素为(　　)
A.[1,3,6,9,7,5,8] B.[3,6,9,7,5,8]
C.[1,3,6,9,2,4,7,5,8] D.[1,3,6,9,4,7,5,8]
思维点拨
明考向 本题考查二维数组的应用
精点拨 将二维数组a中下标i答案　A
【变式2】 有如下Python程序段:
b=[];n=len(a)
for i in range(n):
　for j in range(len(a[i])):
　　　if i　　　 　b.append(a[i][j])
执行该程序段后,若数组b的值为[3,6,7,9],那么数组a的值不可能的是(　　)
A.[[1,3,6,7],[2,4,7,9],[5,2,3,7]]
B.[[1,3,6,7],[1,3,6,7],[1,3,6,9]]
C.[[1,3,6,7],[2,4,9,7],[5,2,3,8]]
D.[[1,3,6,7],[2,6,9,7],[5,2,3,3]]
答案　C
解析　本题考查二维数组的应用。程序的功能是在矩阵的右外角中查找不重复的数。A、B和D选项程序运行后,数组b的值均为[3,6,7,9]。C选项程序运行后,数组b的值为[3,6,7,9,8]。
　　数组是典型的顺序存储结构,是将逻辑上相邻的数据节点存储在物理位置相邻的存储单元中,最大特点是可以通过下标来直接访问某个数组元素,因此访问数组元素较快。若要删除数组中间位置某个元素,必须将该元素后面的元素一个个往前移动,若在中间位置前插入一个新元素,必须将其后面的元素一个个往后移动,因此插入或删除元素的效率较低。
m行n列的二维数组可以看成有n个一维数组共享m个下标的集合,在数据加工处理时,效率会比一维数组高。在处理二维数组的题目时,先要画出二维数组的结构,理解每个数组元素的含义,理解如何定位到某个数据项。
1.已知列表a=[2,3,4,5],要将列表a更新为[1,2,3,4,5],则下列可实现该功能的操作是(　　)
A.a="1"+a B.a.append(1)
C.a=[1]+a D.a=1+a
答案　C
解析　本题考查向列表中添加元素。要向列表添加元素,主要有两种方法,1.append(),但该方法在列表的末尾添加元素,不符合题目要求;2.通过列表相加得到新列表,即如C所示,可以实现该功能。
2.有如下Python程序段:
s="Secret";t=[1,0,2]
r=[""]*len(s)
for i in range (len(s)):
　m=t[i % len(t)]　
　if i　　　r[m]=s[i]
　else:
　　　r[m+len(t)]=s[i]
print ("".join(r))　#将列表r中的元素连接起来,并返回一个新字符串
运行该程序段后,输出的结果是(　　)
A.Secret B.eScert
C.retSec D.ceSter
答案　B
解析　变量m在数组t索引中循环,即m的依次为0,1,2,0,1,2。程序的功能是将字符串s分成两组,每组将原来0,1,2位置依次存储1,0,2的位置。
3.有如下Python程序段:
#随机产生5个整数,存储在列表a中
for i in range(1,5):
　k=a[i]
　j=i-1
　while j >= 0 and abs(a[j]-2)>abs(k-2):
　　　a[j+1]=a[j]
　　　j-=1
　a[j+1]=k
执行该程序段后,列表a的值可能是(　　)
A.[-5,-2,4,0,1] B.[3,-1,0,2,-3]
C.[1,2,3,4,5] D.[0,4,0,-2,-4]
答案　D
解析　程序功能是按abs(a[i]-2)升序排序,即最后每个数据项减2后求绝对值应为升序。
4.已知列表a中包含100个随机数(随机数的范围为0-9),现要输出每个数字在序列中的排名,数字越小,排名靠前(从1开始计数),且当数字大小相同时,排名相同,下一组数字的排名为当前数字排名加上当前数字的数量,如列表a中部分数据为[9,2,1,6,2,6,1,9,7,2],则其排名依次为“9 3 1 6 3 6 1 9 8 3”,实现该功能的程序段如下,方框中应填入的正确代码为(　　)
b=[0]*10
for i in a:
　b[i]+=1
print(s)
答案　B
解析　本题考查数组基本操作以及桶的思想。b数组存储0-9每个数字出现的次数,c数组存储每个数字在数组中的名次。下一组数字的排名为当前数字排名加上当前数字的数量,执行c[i]=b[i-1]+c[i-1],对名次进行累加。最后输出100个数字对应的在此数组的名次,由于名次从1计数,而c数组每个元素初始值为0,故输出时每个名次加1。
5.有如下Python程序段:
n=6
a=[[0]*n for i in range(n)]
for i in range(n):
　 for j in range(i+1):
　　 if j!=0 and j != i:
　　　 　a[i][j]=a[i-1][j-1] + a[i-1][j]
　　 else:
　　　 　a[i][j]=1
程序执行后,a[4]的值是(　　)
A.[1,3,3,1,0,0] B.[1,4,6,6,4,1]
C.[1,4,6,4,1,0] D.[1,5,10,10,5,1]
答案　C
解析　本题考查二维数组的创建和遍历。先创建一个6行6列的二维数组,遍历二维数组的每一行,内循环从0至i,因此只对二维数组的左下半部分进行赋值。将第1列和主对角线(i和j相等)的数据全部赋值为1,其他数据为上一行的前一个和上一行的当前列之和,因此程序的功能是构建一个杨辉三角。
6.有如下Python程序:
a=[43,23,87,67,80]
queinfo=[]
for item in a:
　k=0
　while k　　 　if item>=queinfo[k][-1]:
　　 　　break
　　 　k+=1
　if k==len(queinfo):
　　 　queinfo.append([item])
　else:
　　 　queinfo[k].append(item)
print(len(queinfo))
执行该程序段后,输出的结果是(　　)
A.1 B.2
C.3 D.4
答案　B
解析　queinfo初值为空,语句queinfo.append([item])是将一个列表添加到queinfo,因此他是一个二维数组。遍历列表a,在queinfo数组从第0个元素开始,与每个元素最后一个数据项进行比较,如果大于等于元素最后一个数据项,结束比较,此时j肯定在0至len(queinfo)-1之间,若j的值为len(queinfo),说明该元素比queinfo中每个元素的最后一个值均小,则新成一组。queinfo的值为[[43, 87], [23, 67, 80]]。
7.将数组b合并到非降序数组a中,依旧保持数组a有序。则划线处应填写的代码是(　　)
for i in range(len(b)):
　a.append(0)
for i in range(len(b)):
　 ①　　　
　 while j>=0 and a[j]>b[i] :
　　　a[j+1]=a[j]
　　　j-=1
　 ②　　　
A.①j=len(a)-len(b)　②a[j]=b[i]
B.①j=len(a)-len(b)+i　②a[j+1]=b[i]
C.①j=len(a)-len(b)-1+i　②a[j]=b[i]
D.①j=len(a)-len(b)-1+i　②a[j+1]=b[i]
答案　D
解析　本题考查数组元素的移动。①程序的功能采用插入排序,将数组b中数据插入到数组a中,保持数组a为一个升序的序列。语句j=len(a)-len(b)-1+i的作用是取出数组a中最后有序的位置,while的功能是在数组a中找到b[i]应插入的位置,因此查找的条件是a[j]大于b[i],但同时保证j的位置是有效的。②找到第1个不符合条件位置j,那么数据b[i]应插入的位置是j+1。
8.(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.iB.ia[i+1]
C.ia[i+1]
D.i<=n-1 or t>a[i]
答案　B
解析　本题考查顺序查找和插入排序。先将a[pos]+1的值存入变量t,即要将t插入到正确的位置以确保数组仍然有序。因原数组元素已升序排列,所以从pos位置开始向后顺序查找正确位置,并在查找的同时进行数组元素的前移操作,以便空出t应该在的位置。整个while循环即使实现上述功能,循环条件应为:确保语句a[i]=a[i+1]不能超出数组范围(即i+1<=n-1或ia[i+1])。C选项语句t=a[pos]+1中,并没有改变a数组元素的值,因此a[i]>a[i+1]不可能成立。
1.有如下Python程序段:
c,m=0,0
for i in range(2,len(a)):
　if a[i-2]+a[i-1]==a[i]:
　　　c+=1
　　　if c>m:
　　　　 m=c
　else:
　　　c=0
若列表a=[2,1,3,4,5,9,14,23],执行该程序段后,变量m的值是(　　)
A.0 B.1
C.2 D.3
答案　D
解析　从第3个位置开始遍历,若该位置上值是前两个位置上数之和,统计连续符合这些条件的数据个数c,并找出c的最大值m。数据3,4符合条件,共连续2个数。数据9,14,23符合条件,共连续3个数。
2.有如下Python程序段,功能为删除非降序序列中的重复数:
a=[2,2,2,5,5,5,8 ]
k=i=0
while (1)　　　　:
　if a[i]!=a[i+1]:
　　　k+=1
　　　(2)　　　
　i+=1
print(a[:k+1])
该程序执行结果为[2,5,8],划线处可选代码为
①i则(1)(2)处代码依次为(　　)
A.①③ B.①④
C.②③ D.②④
答案　C
解析　从输出语句print(a[:k+1])来看,k表示删除重复后数字个数。a[i]和a[i+1]比较,因此i的最大位置只能为len(a)-2。k的初值为0,保存了第1个数字,当条件a[i]!=a[i+1]成立时,k先加1,因此将a[i+1]保存到a[k]中。
3.有如下Python程序段:
a=[3, 3, 7, 8, 8, 10, 12, 99]
j=k=res=0
for i in range(len(a)-1):
　while a[j]-a[i]<5:
　　　 j=j+1
　while a[k]-a[i]<= 5:
　　　 k=k+1
　if a[j] - a[i] == 5 and a[k-1] - a[i] == 5:
　　　 res+=k-j
执行程序后,变量res 的值是(　　)
A.2 B.3
C.4 D.5
答案　D
解析　程序统计两个数相减等于5的不同位置上数对的数量。当i为0时,j和k的值为3和5,res值为2;当i为1时,j和k的值不变,res累加为 4;i为2时,j和k的值为6和7,res值为5;再往后遍历,res值不变。
4.有如下Python程序:
#输入包含5个不重复元素的数组a,代码略
i,c=0,0
key=int(input("key="))
for j in range(len(a)):
　if a[j]%key==0:
　　　c+=1
　else:
　　　a[j-c]=a[j]
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。
5.已排好序的列表 a 有 n 个元素,下标为 0~n-1,现要实现去重,并输出去重后的结果。如:1,2,2,3,输出 1,2,3。实现该功能的程序段如下,方框中应填入的代码为(　　)
#输入列表 a 的元素,并排好序
cnt=0
n=len(a)
A.for i in range(1,n):
　 　if a [i]!=a[i-1]:
　　　　cnt+=1
　　　　a[cnt]=a[i]
B.for i in range (n-1):
　 　if a [i]!=a[i+1]:
　　　　a[cnt]=a[i]
　　　　cnt+=1
C.i=0
　while i　　 if a[i]!=a[i+1]:
　　　　cnt+=1
　　　　a[cnt]=a[i]
　i+=1
D.i=1
　while i　　if a[i]!=a[i-1]:
　　　　cnt+=1
　　　　a[i]=a[cnt]
　　i+=1
答案　A
解析　本题考查数据的去重。A选项当数组前后两个值不同时,进行计数,并将该数保存a[cnt]中。C选项当a[0]和a[1]不同时,赋值语句功能为a[1]=a[0],即重复地将第一个数据存入到下个为止。D选项当a[0]和a[1]不同时,赋值语句功能为a[1]=a[1],此时若第二个不同出现在a[2]和a[3],则赋值成a[3]=a[2],不满足将不同的值列下,即输入的数据为[1,2,2,3]时,输出结果为[1,2,2] 。
6.有如下程序段:
p=0
for i in range(len(a)):
　if not("a"<=a[i]<="z"):
　　　j=i;pt=a[i]
　　　while j>p:
　　　 　a[j]=a[j-1]
　　　 　j=j-1
　　　p=j;a[j]=pt
print(a[4])
若列表a=["-","p","y","-","t","h","o","n","-"],则运行该程序段后,输出的值为(　　)
A."-" B."p"
C."y" D."t"
答案　C
解析　程序功能是将所有非小写字母字符向前移动,到所有小写字母以前,且小写字母相对位置不发生改变。故a运行结果为["-","-","-","p","y","t","h","o","n"]。
7.有如下Python程序段:
#生成5个随机整数,保存列表a元素a[0]~a[4]中,代码略
maxs=tmp=0
left=right=0
while right<5:
　tmp+=a[right]
　while left<=right and tmp>0:
　　　tmp-=a[left]
　　　left+=1
　if right-left+1>maxs:
　　　maxs=right-left+1
　right+=1
print(maxs)
执行该程序段后,输出结果为3,则a[0]~a[4]的值可能为(　　)
A.[4,0,0,-2,-3] B.[-2,-3,-4,6,7]
C.[-7,7,1,2,3] D.[-6,2,-1,6,0]
答案　D
解析　本题考查Python程序设计。程序功能寻找列表a中连续子数组元素和小于或等于0的最大长度。right指针表示窗口右端点,left指针表示窗口左端点,窗口长度为right-left+1,更新最大长度maxs。将区间内的值不断地累加到tmp中,且tmp的值大于0,将左端点向后移动,同时在tmp中减去原左端点的值。A和B选项最大长度为4。C选项最大长度为2。D选项[-6,2,-1]之和小于0,最大长度为3。
8.有如下Python程序段:
n=4
a=[[i*n+j+1 for j in range(n)]for i in range(n)]
for i in range(n∥2):
　 for j in range(1 , n, 2):
　　　a[i][j], a[n-i-1][n-j-1]=a[n-i-1][n-j-1], a[i][j]
则程序执行后,a[1][1]和 a[2][0]的值分别为(　　)
A.6和9 B.8和9
C.11和9 D.11和8
答案　D
解析　创建一个[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]的二维数组,遍历前2行,对其中偶数列按对称行和对称列进行交换。a[1][1]是原a[2][2]的值,a[2][0] 是原a[1][3]的值。
9.有Python代码段如下:
a=[11,4,2,13,6,5,3,6,19,1]
for i in range(1,len(a)):
　 key=a[i] ;j=i
　 while (1)　　　　 :
　　　a[j]=a[j-1]
　　　j-=1
　 (2)　　　
划线处(1)、(2)处可选代码如下:
①j>0 and key②j>=0 and key③a[j]=key　④a[j-1]=key
为使得数组a实现升序排序,则划线处代码正确的是(　　)
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 key10.(2025年1月浙江选考)列表c长度为100,如图所示,其中c[10]~c[89]各元素的值均为10以内的随机正整数。执行如下程序段,输出的最后一行是(　　)
i 0 1 2 3 4 5 6 7 8 9 …… 90 91 92 93 94 95 96 97 98 99
c[i] 1 1 1 1 2 3 2 3 2 3 …… 2 3 2 2 2 2 1 1 1 1
pa=[0,0,0,0,0]
pb=[0,0,0,0,0]
h,t=0,4
tmp=0
for k in range(100):
　　pa[t]=c[k]
　　pb[t]=tmp+pa[t]-pa[h]
　　print(pb[h],pb[t],k,pa,pb,h,t)
　　tmp=pb[t]
　　h=(h+1) % 5
　　t=(t+1) % 5
A.5　4 B.8　4
C.9　5 D.9　9
答案　B
解析　本题考查数据的累加求和循环列表的应用。指针h和t都是pb的下标,通过求余操作,当其值为5时,又回到0,即值在0至4的范围内循环,且t与h始终相差4,是一个循环列表。若三条语句pa[t]=c[k]、pb[t]=tmp+pa[t]和tmp=pb[t]在for语句内循环,则其功能是对c数组中数据进行累加求和,而pb[t]的值为tmp+pa[t]-pa[h],即累加求和的基础上减去pa[h],当k小于4时,pa[h]的值均为0,即pb的前4项依次为c数组累加和,pb[4]的值为c[0]至c[4]五项的和减去c[0]的值,因此pb[t]为第t项以及前4项的和。最后一次循环时,前4项的和是1+1+1+1=4,而h的值为t-4,该位置的前4项和为2+2+2+2=8。
11.生成n颗(n<=30)地雷随机放置在10×10的方格中,方块中出现地雷用#表示,出现数字,则表示在其周围相邻的方块中共有多少颗地雷,中间位置有8个方块相邻,边上位置有5个方块相邻,角上位置有3个方块相邻。程序运行的结果如图所示:
def Check(a,x,y):　#统计第x行第y列四周雷的个数
　count=0
　for i in range(x-1,x+2):
　　 for j in range(y-1,y+2):
　　 　if ①　　　　:
　　　　 if a[i][j]==9:
　　　　　　count+=1
　return count
import random
n=10
a=[[0 for j in range(10)]for i in range(10)]
m=int(input("输入地雷的个数"))
i=0
while i　x=random.randint(0, 9)
　y=random.randint(0, 9)
　if a[x][y]==0:
　　　a[x][y]=9
　　　②　　　
for i in range(n):
　for j in range(n):
if a[i][j]!=9:
　 　　　③　　　
for i in range(n):
　s=""
　 for j in range(n):
　　 if a[i][j]==9:
　 　　　s=s+"# "
　　 else:
　 　　　s=s+str(a[i][j])+" "
　print(s)
答案　①0<=i<10 and 0<=j<10　②i+=1　③a[i][j]=Check(a,i,j)
解析　本题考查二维数组和枚举算法。程序共分3部分,第1部分生成10×10的矩阵,并随机生成m个地雷,第2部分是统计不是地雷的格子周围有多少地雷,第3部分是输出。②随机生成x,y坐标,若该位置不是雷,则将雷的数量增加1,因此答案为i+=1。①采用枚举算法检测坐标x,y的上一行、当前行和下一行中,左右3列中雷的个数。但要注意边界问题,即必须在矩阵内。③调用自定义函数来检测坐标i,j周围雷的个数。

展开更多......

收起↑