资源简介

专题11　数　组
学业要求 知　识　点 学业水平等级
1.能结合数组的应用案例，了解数组概念、结构、特性，并根据要求创建数组 3
2.学会通过数组名和下标访问数组元素，并能根据需求插入、删除数组元素 4
知识点一　一维数组
【知识梳理】
1.数组是由相同________的变量构成的一个序列，常用的数组有一维数组和________数组。
2.数组使用数组名(标识符)和下标(索引)区分数组内的各个变量。由数组名和下标组成数组的各个变量称为数组的分量，即数组________。
3.数组元素的类型相同，通过数组名和下标对数组中任意________的数据元素进行高效的访问，数组的存储空间固定不变。
4.数组的创建实质是在系统内存中划分一块________区域，用来保存数组包含的所有数据元素。
5.在数组中某个位置插入一个新的元素，必须先将该位置及其后的所有元素依次向________移动一个位置，以空出该位置，用于存放新元素。
6.在数组中，删除某个位置上的数据元素，需要将该位置元素后的所有元素依次向________移一个位置。
7.数组创建时就分配好存储空间，访问数组元素不能________，删除数组占用的空间不变(除非采用pop方法删除)。
8.一维数组指只有一个________，下标用来表示数据元素在该序列中的位置。
9.在创建一个数组时，既要分配数组元素的个数，又要确定数组元素的________。如语句list1＝[0]*10功能是创建一个包含10个整数类型的数组元素，初值均为0。
10.采用for循环将一个序列中值赋值给一个________，如list1＝[int(i) for i in ″6，52，44，12″.split(″，″)]表示将数字串的数字按逗号分隔并转换成数值类型，再将这些数字存储到数组list1中。
11.统计数组list1中元素的________语句len(list1)。
12.在数组list1最后一个元素后面新增一个元素x语句________，数组空间增加一个。
13.删除数组list1最后一个元素语句________，数组空间减少一个。
【经典案例】
数组的元素个数是固定的，存储单元在数组定义时分配，元素顺序关系由元素在数组中的位置(即下标)确定，对于不是固定长度的列表，用可能最大长度的数组来描述，会浪费许多内存空间。并且数组元素插入和删除时，需要不断移动数据元素。数组的优点：随机访问性强，查找速度快。主要缺点：插入和删除效率低。
【例1】 现有两个升序数组a和数组b，现在要求将两个数组合并，依旧保持升序。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】 lst1和lst2都是升序排序的列表，执行如下Python程序段：
result＝[]
i＝0　#用于遍历lst1
j＝0　#用于遍历lst2
while iif lst1[i]result.append(lst1[i])
i＋＝1
else：
result.append(lst2[j])
j＋＝1
while iresult.append(lst1[i])#②
i＋＝1
while jresult.append(lst2[j])#③
j＋＝1
下列说法不正确的是(　　)
A.程序段①执行后，result可能与lst1相同
B.程序段①执行后，result可能与lst2相同
C.在一次程序运行中，②处代码和③处代码可能都被执行
D.程序执行后，列表result中的元素升序排序
【例2】 某酒店的房间编号为1到1000，对于空余的房间的记录，采用连续空房间的起始房间编号和连续空房间数量进行记录，例如：有空房间1、2、3、6、7、9号时，记录的方法为：(1，3)，(6，2)，(9，1)，共3条记录。当有人退房时，一般出现4种情况：
·若退出房间号为4时，属于“上靠”情况，则第1条记录修改为(1，4)；
·若退出房间号为5时，属于“下靠”情况，则第1条记录修改为(5，3)；
·若退出房间号为8时，属于“上下靠”情况，则第2条、第3条记录合并，修改为(6，4)；
·若退出房间号为12时，属于“不靠”情况，则新增1条记录为(12，1)。
请回答下列问题：
(1)当已有的空房间记录为(3，5)，(9，5)，(16，3)，(30，2)，当退出房间号为8时，空房间记录修改为________。
(2)实现上述功能的部分Python程序如下，请在划线下填入合适的代码。
″ ″ ″
读入已有的空房间记录，个数为n，这些记录已按房间起始号升序排好，每条记录的房间起始号存入数组room，对应的连续空房间的个数存入数组num，下标均为0到n－1
″ ″ ″
x＝int(input(″请输入退出房间号：″))
pos＝0
while ①________：
pos＋＝1
if pos>0 and pos<＝n－1 and room[pos－1]＋num[pos－1]＝＝x and x＋1＝＝room[pos]：
②________
for i in range(pos，n－1)：
num[i]＝num[i＋1]
room[i]＝room[i＋1]
n－＝1
elif pos>0 and room[pos－1]＋num[pos－1]＝＝x：
num[pos－1]＋＝1
elif ③________：
room[pos]＝x
num[pos]＋＝1
else：
for i in range(n－1，pos－1，－1)：
room[i＋1]＝room[i]
num[i＋1]＝num[i]
room[pos]＝x
num[pos]＝1
④________
for i in range(n)：
print(room[i]，″ ″，num[i])
思维点拨
明考向 本题考查数组元素的插入和删除
精点拨 (1)退房前的空房间情况为3－7，9－13，8号房间退出，符合上下靠的情况，更改为3－13，16－18，30－31。(2)①找到起始空房间号room[pos]大于x房间号，为pos确保是有效索引，加上条件pos听课笔记：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式2】 以下是实现正整数序列arr升序排列的程序代码段：
for i in range(1，len(arr))：
key＝arr[i]
j＝i－1
while ①________：
arr[j＋1]＝arr[j]
j－＝1
②________
print(″排序后的数组：″)
for i in range(len(arr))：
print(″%d″ %arr[i])　#依次输出 arr 中的每个元素
则划线部分代码正确的是(　　)
A.①j>＝0 and keyB.①j>＝0 and keyC.①j>＝0 and key>arr[j]　②arr[j]＝key
D.①j>＝0 and key>arr[j]　②arr[j＋1]＝key
知识点二　二维数组
【知识梳理】
1.二维数组有________个下标，表示数据元素在该序列中的行、列位置。
2.二维数组list1的一行称为一个元素，因此可以用表达式________来表示数组中元素的个数，即数组的大小。
3.可以对数组元素进行切片，取出数组元素中每个________项，如list1[i]表示二维数组第i行数据元素，list1[i][j]表示二维数组第i行第j列数据项。
4.二维数组往往采用________循环分别对二维数组的行和列分别进行赋值。如list1＝[[i*j for j in range(4)]for i in range(3)]表示创建一个3行4列的二维数组。
【经典案例】
二维数组在本质上仍然为一段连续的线性空间，和一维数组相同，根据下标进行访问时，算法时间复杂度仍然是常数阶。二维数组能很方便地存储结构化数据，数据按行存储，每列的数据类型往往是相同的，可以通过双重循环来遍历二维数组中每个数据项。二维数组可以存储多个队列，多个栈，也可以表示一个链表中多个节点。
【例题】 有如下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]
思维点拨
明考向 本题考查二维数组的创建和遍历
精点拨 先创建一个6行6列的二维数组，遍历二维数组的每一行，内循环从0至i，因此只对二维数组的左下半部分进行赋值。将第1列和主对角线(i和j相等)的数据全部赋值为1，其他数据为上一行的前一个和上一行的当前列之和，因此程序的功能是构建一个杨辉三角
听课笔记：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式】 有如下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]
1.若长度为n的线性表采用数组a(a[0]～a[n－l])存储，要删除第t个位置上(存储在a[t－1])的元素，对应的Python程序如下：
for i in range(t－1，n－1)：
________________
划线处的代码应是(　　)
A.a[t]＝a[i] B.a[i]＝a[i＋1]
C.a[i]＝a[i－1] D.a[i－1]＝a[i]
2.有如下Python程序段：
a＝[18，2，－1，－7，16，－2，12，8]
k1，k2＝1，1
for i in range(len(a))：
if a[i]>a[k1]：
k2＝k1；k1＝i
elif a[i]>a[k2]：
k2＝i
该程序段运行后，变量k1，k2的值分别为(　　)
A.2，5 B.4，0
C.5，2 D.0，4
3.已知a数组存储了10位学生的身高信息(范围为150厘米～190厘米之间)，现要找出所有身高超过170厘米学生中最矮的那位学生的编号及其身高数据，运行结果如图所示。
[180，152，168，152，160，173，151，155，165，181] 下标为5号，身高为173
实现该功能的程序如下：
from random import randint
a＝[randint(150，190) for i in range (10)]
if max(a)<171：
print(″所有人身高均小于 171! ″)
else：
f＝True；k＝0
for i in range(10)：
if a[i]>170：
　　　　 if ：
　　　　　 　k＝i
　　　　　 　f＝False
print (a)
print(″下标为″，k，″号，身高为″，a[k])
程序加框处代码有错，正确的语句应为(　　)
A.a[i]C.a[i]4.已知6行4列的二维数组a以行优先的方式存储在k个连续存储单元中，每个数组元素占8个存储单元，如果已知a[0][0]的首地址为1000，则a[3][2]的首地址为(　　)
A.1112 B.1160
C.1104 D.1080
5.小刚将我国部分省会城市及其对应的市花存储到二维数组中，并依次输出各省会城市名及其市花，例如：杭州的市花是桂花。相关代码如下：
a＝[[″杭州市″，″桂花″]，[″广州市″，″木棉″]，[″郑州市″，″月季″]，[″武汉市″，″梅花″]，[″长沙市″，″杜鹃″]，[″济南市″，″荷花″]]
for p in a：
print(f″{__①__}的市花是{__②__}″)
则划线①和②处分别应填写的代码为(　　)
A.①p[1]；②p[0] B.①p[0]；②p[1]
C.①a[p][0]；②a[p][1] D.①p[1]；②p[2]
6.利用5列6行的二维数组qp来记录某试场中的座位编号1～30，m＝0
qp＝[[0 for i in range(5)] for j in range(6)]　#建立二维数组并初始赋值为0
for i in range(5)：
for j in range(6)：
if i %2＝＝0：
qp[j][i]＝m*6＋j＋1
else：
　　　　 qp[j][i]＝m*6＋6－j
m＝m＋1
运行上述程序段后，编号17所在的数组元素为(　　)
A.qp[4][2] B.qp[2][4]
C.qp[5][3] D.qp[6][1]
7.小明需要根据订单的取件距离依次安排快递员取件。快递员出发后不能中途折返，但可以接更远距离的快递订单。当小明新接到一个取件订单，他会依次安排可以取件的快递员取件，若该订单距离小于所有已出发的快递员的最远距离，则安排新的快递员出发取件。编写Python程序，实现上述功能。程序运行时，输入订单距离(各数值之间用“，”隔开)，显示每位快递员的收取情况。
快递坐标：[243，123，167，309，229，183，87，333，183] 第1分组：[243，309，333] 第2分组：[123，167，229] 第3分组：[183，183] 第4分组：[87]
(1)若新派件一个快递，坐标为229，则应该为第________个分组去取件。
(2)实现的程序代码如下，请将空白处填写完整
s＝input(″依次输入快递坐标，用逗号分隔：″)
dd＝[int(i) for i in s.split(″，″)]
print(″快递坐标：″，dd)
x＝0；n＝len(dd)
fp＝[[0] for i in range(n)]　#建立n个分组
for i in range(①________)：
j＝0
while ②________：
j＋＝1
fp[j].append(③________)
if ④________：
x＋＝1
for i in range(x)：
print(″第″＋str(i＋1)＋″分组：″，fp[i][1：])
8.去除一个数组中重复的元素算法思想：变量i从第1个元素开始遍历，变量j遍历位置i后面的所有的元素，两个元素进行比较，如果相等，将数组最后的元素替换索引位置j的元素，数组总长度减少1个，为了防止原最后一个元素与元素i相等，位置i与第j个元素进行第2次比较(j减1)。
(1)数组a的原始值为[3，3，4，2，4，3]，采用该算法去重后为[________]。
(2)实现该功能的算法如下，请将空白处填写完整
a＝[5，6，4，7，5，7，6，5，7，2]
i＝0；n＝len(a)－1
while i①________
while j<＝n：
if a[i]＝＝a[j]：
　　　 　a[j]＝a[n]
　　　 　②________
　　　 　j－＝1
③________
i＋＝1
for i in range(n＋1)：
print(a[i]，end＝″″)
9.为分析数组a中各元素依次变化的情况，进行如下定义：
变化段：数组中相邻两个元素构成一个变化段。变化段有上升段(a[i]>a(i－1))、下降段(a[i]波峰：从上升段转到下降段形成一个波峰。波峰的起点是峰顶前所有连续上升段中的第1个，终点是峰顶后所有连续下降段中的最后1个。
对称波峰：上升段与下降段个数相同的波峰称为对称波峰。
下图为一组数据的变化段及波峰示意图。
现要求统计数组a各元素依次变化过程中“对称波峰”的个数。小李依据上述描述设计如下Python程序。请回答下列问题：
(1)数组元素“1，4，3，3，2，6，8，7，9，3，4，7，9，6，3，1”依次变化过程中“对称波峰”的个数为________。
(2)把划线处的代码补充完整。
def IsSymPeak(f，s)：
if ①________：
return True
else：
return False
#读取数据，并存储到数组a中，代码略
flag＝0　#存储变化段的状态：1表示升，－1表示降，0表示平
steps＝0　#上升段与下降段个数
count＝0　#对称波的个数
for i in range(②________)：
if a[i]>a[i－1]：
if IsSymPeak(flag，steps)：
　　　 　count＋＝1
if flag＝＝0 or flag＝＝－1：
　 　　　③________
else：
　　　 　steps＋＝1
flag＝1
elif a[i]＝＝a[i－1]：
if IsSymPeak(flag，steps)：
　　　 　count＋＝1
steps＝0
flag＝0
else：
steps －＝1
flag＝－1
if IsSymPeak(flag，steps)：
count＋＝1
print(″共有对称波个数为″，count)
专题11　数　组
知识点一
知识梳理
1.数据类型　二维　2.元素　3.位置　4.连续 5.后　6.前　7.越界　8.下标　
9.类型　10.数组 11.个数　12.list1.append(x)　13.list1.pop()
经典案例
例1　(1)①j>＝0　②i>＝0 and a[i]变式1　C　[本题考查两个升序数组的归并。用两个指针分别遍历两个数组，第一个循环条件i例2　(1)(3，11)，(16，3)，(30，2)　(2)①posroom[pos]　②num[pos－1]＋＝1＋num[pos] ③x＋1＝＝room[pos]　④n＋＝1
变式2　A　[从第2个元素开始遍历arr数组，将数组元素arr[i]插入到0至i－1合适位置，形成一个升序的序列，最后整个数组是有序的。内循环中j从i－1开始与key比较，为保证arr[j]有效，j必须大于等于0，同时当key小于被比较的数时，将当前j的数据向后移动，再向前继续查找，当条件不成立时，key的插入位置为j＋1。]
知识点二
知识梳理
1.两　2.len(list1)　3.数据　4.双重
经典案例
例题　C
变式　A　[本题考查二维数组的应用.将二维数组a中下标i当堂过关检测
1.B　[从索引t－1开始遍历到n－1，将他后面位置(i＋1)的数据赋值给当前位置，最终数组元素的个数为n－1。]
2.D　[k1是最大数的下标，k2是第二大数的下标。]
3.B　[找出所有身高超过170厘米学生中最矮的那位学生，f的初值为True，先找到满足a[i]>170的第1位学生，将最值k的初值赋值为该学生的索引，同时将f的值置为False。]
4.A　[本题考查二维数组的相关知识。以行优先的方式存储，每行共4个数据项，a[3][2]前共有3行2列，因此共3*4＋2＝14个数据项，共占14*8＝112个存储单元，首元素地址为1000。]
5.B　[p是数组a中元素，即是一个列表。]
6.A　[赋值对象为qp[j][i]，即i表示列，j表示行，意味着是按列遍历矩阵，因此第1列为1－6，第2列为m*6＋6－j，即12－7递减，第3列为8－18。]
7.(1)2　(2)①len(dd)或n　②j③dd[i]　④j＝＝x
解析　(1)第2个分组最后一个坐标等于该坐标，可以取。(2)①对dd数组n个坐标逐一进行遍历。②查找dd[i]在哪个分组，每一个分组最后一个数字为最大值，若快递大于等于该值，表示可以取快递。遍历各个坐标时，查找该坐标应插入的组别。组类别j总是从第0组开始，当第i个坐标小于该组最后一个值，再查找下一组。③将该坐标添加到fp的第j组。④x表示总共的组别，当j在[0，x－1]中找到插入位置，说明目前有小哥可以取快递，若j超出这个范围，则需要新开一组。
8.(1)3，4，2　(2)①j＝i＋1　②n－＝1　③j＋＝1
解析　(1)数组[3，3，4，2，4，3]→[3，3，4，2，4]→[3，4，4，2，4]→[3，4，4，2]→[3，4，2]。(2)①变量j从i的下一个位置开始，与之进行比较。②找到一个相同，总数n减少一个。③同时为了防止原最后一个元素与元素i相等，位置i与第j个元素进行第2次比较(j减1)。
9.(1)3　(2)①f＝＝－1 and s＝＝0　②1，len(a) ③steps＝1
解析　本题考查枚举算法和多支选择结构。(1)根据题目描述，对称波的两个要素是在下降段且步长为0。从第2个数据点开始的steps值分别为1，0，0，－1，1，2，1，1，0，1，2，3，2，1，0。第1个对称波是1，4，3，上升下降段各1。第2个对称波是7，9，3。第3个对称波是4，7，9，6，3，1。(2)②比较对象是a[i]和a[i－1]，因此i的初值为1，终值为len(a)－1。③当条件a[i]>a[i－1]成立时，表示处于上升的开始点，若原来是平行波段和下降波段，则上升波段数为1。①对称波的两个要素是在下降段且步长为0。

展开更多......

收起↑