资源简介

(共52张PPT)
第二章　数组与链表
验收卷(一)　数组与链表
(考试时间40分钟　满分50分)
一、选择题(本题共12小题，每小题2分，共24分)
B
解析　本题主要考查的是数组和链表的特性。查找特定元素，使用单向链表查找时，只能通过头指针进入链表并通过指针链接依次访问，直到找到特定元素，而使用数组查找时，只要使用数组名和下标就能直接访问特定元素，因此，查找特定元素，使用数组比使用单向链表更方便。
A.对于需要频繁插入和删除元素的情况，使用单向链表比使用数组合适
B.查找特定元素，使用单向链表比使用数组方便
C.数组适用于最大元素个数容易确定的情况
D.存储相同的元素，使用单向链表比使用数组方便
D
2.下列关于数组和链表的存储结构与逻辑结构关系的说法，正确的是(　　)
解析　链表的节点结构包括数据域与指针域，指针表示各节点的连接前后顺序，即链表数据的逻辑结构由指针表示，D选项正确。
A.链表的存储结构与逻辑结构一致
B.数组的存储结构对逻辑结构没有影响
C.存放相同数据的数组存储空间大于链表
D.链表数据的逻辑结构由指针表示
A
3.利用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]
解析　赋值对象为qp[j][i]，即i表示列，j表示行，意味着是按列遍历矩阵，因此第1列为1－6，第2列为m*6＋6－j，即12－7递减，第3列为13－18。
D
4.下列关于链表的叙述中，正确的是(　　)
解析　单链表存储方式地址不连续，元素顺序是任意的，因此答案为D。
A.线性链表中的各元素在存储空间中的位置必须是连续的
B.线性链表中的表头元素一定存储在其他元素的前面
C.线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面
D.线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的
C
A.节点的数据区域用于存放实际需要处理的数据元素
B.节点的指针区域用于存放该节点相邻节点的存储地址
C.单向链表必须带有数据区域为空的头节点和尾节点
D.单向链表中的各个节点在内存中可以非顺序存储
解析　选项单向链表的头节点和尾节点可以是单独的数据区域为空的节点，也可以将节点序列中的第1个和最后一个节点作为头节点和尾节点。在Python程序设计时我们通常使用第二种方式，即直接使用带数据区域的节点作为头节点或尾节点来标记和使用。
C
6.有如下Python程序段：
解析　本题考查链表的遍历。条件a[p][1]！＝－1表示当前节点的指针区域值为－1，即当前节点为尾节点。当遍历到尾节点时，结束循环。
a＝[[2，2]，[5，3]，[3，1]，[6，－1]，[1，0]，[4，2]]
p＝5
while a[p][1]！＝－1：
　　print(a[p][0]，end＝″→″)
　　p＝a[p][1]
则运行程序后，控制台输出的结果是(　　)
A.4→3→5 B.4→3→2→5→
C.4→3→5→ D.4→3→2→5
7.有下列Python程序段：
a＝[[1，3]，[1，0]，[7，1]，[4，5]，[1，－1]，[6，4]]
x＝1
p＝pre＝head＝2
if x＝＝a[head][0]：
head＝a[head][1]
else：
while p！＝－1 ：
if x＝＝a[p][0]：
　　　　a[pre][1]＝a[p][1]
解析　本题考查链表的基本操作。如果链表头节点值为1，直接删除头节点，否则遍历链表，语句a[pre][1]＝a[p][1]的作用让节点p的前驱指向他的后继，即删除p节点。程序的功能是删除元素值为1的节点。
else：
　　　　pre＝p
p＝a[p][1]
运行该段程序后，a[2][1]的值为(　　)
A.－1 B.0 C.1 D.3
D
8.采用Python二维列表模拟链表，
a＝[['A'，1]，['B'，2]，['C'，3]，['D'，4]，['E'，5]，
['F'，－1]]表示链表为：
A→B→C→D→E→F→None，有以下Python程序：
a＝[['A'，1]，['B'，2]，['C'，3]，['D'，4]，['E'，5]，
['F'，－1]]
head＝0；p＝a[head][1]
a[head][1]＝－1
while p！＝－1：
p＝a[p][1]
if p＝＝－1：
break
解析　本题考查链表的基本操作。p的初值为a[head][1]，即head的后继，进入循环后，语句p＝a[p][1]的功能是向后遍历，让该节点指向头节点，p再向后遍历。A后继的后继是C，当前头节点为C，C指向A；C后继的后继是E，当前头节点为E，E指向C。
t＝a[p][1]
a[p][1]＝head
head＝p
p＝t
执行以上程序后，以head为首的链表结构为(　　)
A.E→C→A B.A→C→E
C.B→D→F D.F→D→B
A
9.有如下 Python 程序：
a＝[43，23，87，67，80]
queinfo＝[]
for item in a：
　k＝0
　 while kif item>＝queinfo[k][－1]：
　　　 　break
k＋＝1
　　if k＝＝len(queinfo)：
queinfo.append([item])
解析　queinfo初值为空，语句queinfo.append([item])是将一个列表添加到queinfo，因此他是一个二维数组。遍历列表a，在queinfo数组从第0个元素开始，与每个元素最后一个数据项进行比较，如果大于等于元素最后一个数据项，结束比较，此时j肯定在0至len(queinfo)－1之间，若j的值为len(queinfo)，说明该元素比queinfo中每个元素的最后一个值均小，则新成一组。Queinfo的值为[[43，87]，[23，67，80]]。
　　　else：
queinfo[k].append(item)
print(len(queinfo))
执行该程序段后，输出的结果是(　　)
A.1 B.2 C.3 D.4
B
10.有如下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
C
程序执行后，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，其他数据为上一行的前一个和上一行的当前列之和，因此程序的功能是构建一个杨辉三角。
11.有如下 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 ib.append(a[i][j])#b追加一个元素a[i][j]
A
执行该程序执段后，数组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中下标i12.某Python程序如下：
data＝[]
for i in range(len(a))：
　data.append([a[i]，i＋1])
data[－1][1]＝－1
la＝head＝0
t＝data[head][1]
key，c＝2，0
while c<3 and t！＝－1：
　 if data[t][0]－data[la][0]　 c＋＝1
　la＝t
　t＝data[t][1]
B
已知执行上述程序后，t的值为6，则数组a的值可能(　　)
A.[4，3，1，6，3，9，3] B.[2，6，5，1，6，4，0]
C.[7，5，2，3，2，7，5] D.[2，4，0，1，0，8，4]
解析　本题考查链表应用。data是一个链表，t指针从链表的第二个节点开始遍历，1a指针是t节点的前驱，t节点减去前驱节点la的值小于key时，c计数，c的初值为0，计数到3时历结束，也就是整个过程计数3次就结束，执行程序后t的值为6，也就是遍历到最后一个节点时程序才结束。
二、非选择题(本题共4小题，共26分)
13.(6分)大部分社交软件都有好友推荐的功能，当用户A和用户B不为好友，但他们的共同好友数量超过阈值m时，由系统向用户A推荐用户B。
编写Python程序，实现好友推荐功能。生成一个二维数组a记录两者关系，当a[0][2]的值为1时，表示ID1和ID3是好友，值为0则不是好友。运行程序，输入用户ID和共同好友数量超过阈值m，显示每个用户ID的好友及向目标用户推荐的好友列表。程序运行界面如图：
共同好友数量超过阈值m：2
1ID号的好友有：2，3，4，5，6，7，9
2ID号的好友有：1，3，4，5，6，7，10
3ID号的好友有：1，2，5，6，7，8，9
4ID号的好友有：1，2，5，6，7，8，9，10
5ID号的好友有：1，2，3，4，6，8
6ID号的好友有：1，2，3，4，5，7，9，10
7ID号的好友有：1，2，3，4，6，8
8ID号的好友有：3，4，5，7，9，10
9ID号的好友有：1，3，4，6，8
10ID号的好友有：2，4，6，8
向用户ID1推荐的共同好友有：[8，10]
编写的代码如下：
n＝10
#产生一个n*n的二维数组a，存储两人之间的关系。
def Check(a，x，y): #向用户ID为x推荐的阈值为y的好友列表。
n＝10；ans＝0
nothy＝[]
for i in range(n): #查找与x不是好友的朋友编号
　 if ①____________：
　　　 　nothy.append(i)
hy＝[]
for i in nothy：
　 t＝0
　 for j in range(n)：
　 if ②____________：
　　　 　t＋＝1
if t>y：
　 hy.append(i＋1)
return hy　
hm＝int(input(″输入用户ID：″))
m＝int(input(″共同好友数量超过阈值m：″))　
for i in range(n)：
　 s＝str(i＋1)＋″ID号的好友有：″
　 for j in range(n)：
　 if a[i][j]＝＝1：
　　　　s＝s＋str(j＋1)＋″，″
　print(s[：－1])
③____________
print(″向用户ID″，hm，″推荐的共同好友有：″，p)
(1)输入用户ID为7，阈值m为4，则推荐的好友是________。
(2)请在程序划线处填入合适的代码。
答案　(1)5，9　(2)①a[i][x]＝＝0 and x！＝i
②a[x][j]＝＝1 and a[i][j]＝＝1
③p＝Check(a，hm，m)
解析　(1)在不是好友中选择共同好友超过4的ID，ID10与ID7的共同好友只有4个。(2)①查找与x不是好友的朋友编号，在各个编号中遍历，相当在于二维表格的第x行查找0的列号，但列号不能是x自己。②寻找共同好友，即第x第i行中，值均为1的列号数量。③调用自定义函数查找共同好友。
已知
14.(6分)某影平台上架新影片时，需要先确定该影片的类型，如喜剧片、动作片、爱情片。确定某影片的类型，可根据已有的样本数据(如图a所示)进行分类。
图a
电影名称 搞笑镜头 拥抱镜头 打斗镜头 影片类型
宝贝当家 45 2 9 喜剧片
唐人街探案 23 3 17 喜剧片
我的特工 爷爷 6 4 21 动作片
…… …… …… …… ……
泰坦尼克号 9 39 8 爱情片
罗马假日 9 38 2 爱情片
新步步惊心 8 34 17 爱情片
图b
电影名称 搞笑 镜头 拥抱 镜头 打斗 镜头 影片
类型
美人鱼 19 18 5 ？
距离最近的前5部影片为：
唐人街探案19.62，罗马假日22.56，新步步惊心22.83，泰坦尼克号23.45，我的特工爷爷24.92，
图c
请回答下列问题：
(1)与《美人鱼》距离最近的前5部影片如图c所示，则该影片属于________(单选，填字母：A.喜剧片 /B.动作片 /C.爱情片)。
(2)定义如下mvmin(result，flag)函数，参数result列表存储距离，flag列表存储标记。若result＝[43，33，18，25，65]，flag＝[False，False，True，True，False]，则函数的返回值为________。
def mvmin(result，flag)：
mv＝10000　#假定result列表元素值不超过10000
for i in range(len(result))：
　　 　if mv>result[i] and flag[i]＝＝False：
　　　 mv＝result[i]
　　　pos＝i
return pos
(3)实现电影分类的部分Python程序如下，请在划线处填入合适的代码。
读取样本影片的镜头数据，存储在data中，每个元素包含5个数据项，分别对应电影名称、搞笑镜头、打斗镜头、拥抱镜头、影片类型。
如data＝[[″宝贝当家″，45，2，9，″喜剧片″]，……]，代码略。
x＝[″美人鱼″，19，18，5]
dic＝{″喜剧片″：0，″动作片″：0，″爱情片″：0}
k＝5　
result＝[0]*len(data)
for i in range(len(data))：
d＝0
for j in range(1，4)：
　　tmp＝①________
　 　d＋＝tmp**2　
result[i]＝round(d**0.5，2) #结果保留2位小数
flag＝[False]*len(result)
print(″距离最近的前″，k，″部影片为：″)
while k>0：
p＝mvmin(result，flag)
flag[p]＝True
②________
print(data[p][0]，result[p]，end＝″，″)
③________
#统计前k个最近距离的影片中出现频次最多的类型，并输出该影片类型，代码略
答案　(1)C　(2)1　(3)①data[i][j]－x[j] 或 x[j]－data[i][j] 　②dic[data[p][4]]＋＝1　③k－＝1
解析　(1)距离最近的5部影片中，喜剧片1部，爱情片3部分，动作片1部，因此该影片类型为爱情片。(2)在存储标记为False的位置中，查找最小值的索引，43，33，65三个数中最小值索引为1。(3)①遍历所有的样本数据data，计算出“美人鱼”与样本中所有影片的距离。data[i][1]、data[i][2]、data[i][3]分别表示样本数据中搞笑镜头、打斗镜头、拥抱镜头的值，用变量j表示这些下标，计算与x[j]的平方差的和。②调用mvmin函数计算最小距离的索引p，即对应的样本的索引，在数组元素data[p][4]中存储的是该影片的类型，需要对该类型的数量增加1。③处理下一个样本数据。
15.(7分)某学校工会举行飞镖大赛，共有n位老师报名参赛，每位选手共掷5支镖，每镖得分为0至10分，选手总分为 5镖成绩之和，每位选手的比赛数据记录在文本文件中，如图a所示。
处理要求：数据读入数组 data 中，计算出每位选手的总分，在不改变数据在原数组 data 中的位置的条件下，按总分从高到低输出选手的编号和总分。
(1)主程序。采用链表结构处理数据。程序运行结果如图 b所示。请在程序中划线处填入合适的代码。
data＝readdata(″scores.txt″) #读取数据，计算总分
print(″处理前的数据为：\\n″，data)
n＝len(data)
flag＝[True]*n #标记数据被使用情况
head＝findmax() #返回 data 中可使用状态最大数的位置
k＝head
for i in range(1，n):
　 posi＝findmax()
　 data[k].append(posi)
　______________
data[k].append(－1)
print(″处理后的数据为：\\n″，data)
print(″从高分到低分输出为：″)
output(head)
(2)编写readdata函数，功能为从文本文件读取数据，计算出总分，返回列表。代码如下，请在程序中划线处填入合适的代码。
def readdata(filename):
　 f＝open(filename)
　 line＝f.readline()
　　lst＝[]
　　while line: #获取每位选手的编号和总分数据
　　 　line＝line.split(″，″)
　　　s＝0
　 　　for i in range(1，len(line))：
　　 　__________
　　　lst.append([line[0]，s])
　 　　line＝f.readline()
return lst
(3)编写findmax函数，功能为返回 data 中可使用状态最大数的位置pos，并设置该数的使用状态为 False。请在程序中划线处填入合适的代码。
def findmax()：
　maxnum＝0
　 for i in range(n)：
　 if ①____________：
　　　 maxnum＝data[i][1]
　　　 pos＝i
　　　②____________
　　　return pos
答案　(1)k＝posi　(2)s＋＝int(line[i])
(3)①maxnum②flag[pos]＝False　(4)q！＝－1
解析　(1)查找数组中的最大值的位置，利用位置关系串成一个降序链表，最后遍历链表输出。k 是当前元素的位置，posi 是下一个元素的位置，找到的数应该在节点 posi 后面。(2)readdata函数功能是读取“scores.txt”文件，生成一个二维列表。变量s累计的总分。(3)findmax函数找到最大数所在位置，同时将该位置设置为 False。
(4)遍历链表，输出节点相关数据域的内容。
16.(7分)“抢单”是外卖骑手的日常，当外卖平台上一个新的订单出现时，骑手需要在短时间内考虑是否抢单。平台根据骑手的实际信息，给出是否抢单的建议，若建议抢单则给出到达各个取送点的顺序。
平台判断是否抢单的算法设计如下：
1)在不改变已有订单各取送点顺序的前提下，将新订单按先取餐后送餐的顺序分别插入原来的路线中，枚举所有新路线；
2)计算新路线路程，并进行判断：每个取送点都有一个系统指定时间，若骑手到达该位置时，时间晚于系统指定时间，则该方案无效；
3)对新路线进行计算和判断后，删除此次枚举的两个插入位置，还原为初始状态，再继续进行下一次枚举；
4)在所有有效方案中，输出总路程最小的方案，若无有效方案，则输出不接单的建议。
如果骑手目前无订单在派送中，则插入订单A的方案只有1种，骑手→取餐点A→送餐点A；如果骑手订单中已有1个送餐点A和1个送餐点B，则新订单C有6种插入方案，如下所示，
方案1：骑手→取餐点C→送餐点C→送餐点A→送餐点B
方案2：骑手→取餐点C→送餐点A→送餐点C→送餐点B
方案3：骑手→取餐点C→送餐点A→送餐点B→送餐点C
方案4：骑手→送餐点A→取餐点C→送餐点C→送餐点B
方案5：骑手→送餐点A→取餐点C→送餐点B→送餐点C
方案6：骑手→送餐点A→送餐点B→取餐点C→送餐点C
(1)若骑手仅剩3份餐未送(已取餐)，路线为：骑手→送餐点A→送餐点B→送餐点C，新的订单出现后，有________种插入方案。
(2)定义如下con(tim)函数进行时间格式转换，将24小时制的“时：分”转换为分，如02：30转换为150，请在划线处填上合适代码。
def con(tim)：
　t＝__________＋int(tim[3：])
　　return　t
(3)定义totd(riderlist，h)函数，其功能为从头指针h进入链表riderlist，按节点先后顺序计算总路程，并判断能否在系统指定时间内到达各取送点，若到达某一取送点时超时返回－1。若链表riderlist如下，
riderlist＝[[″u1001″，″119.906033″，″31.014597″，″11：30″，2]，
[″s″，″119.921439″，″31.023022″，″11：55″，3]，
[″t″，″119.887850″，″31.022861″，″11：40″，1]，
[″s″，″119.953836″，″31.021122″，″12：10″，－1]]
第1个元素中″u1001″为骑手编号，″119.906033″和″31.014597″，表示骑手实时位置，″11：30″为实时时间，2为下一节点指针，第2个元素开始，第1项若为″t″表示此元素为取餐点信息，若为″s″表示此元素为送餐点信息。调用函数totd(riderlist，h)，risderlist的值如上，h为0，则加框处语句最多被执行______次，若将此条件语句改为riderlist[pre][4]！＝－1，______(选填：影响/不影响)程序执行。
total＋＝d
if total/speed>con(riderlist[cur][3])－con(riderlist[h][3])：
　　　　return －1
else：
　　　　 pre＝cur
　　　　 cur＝riderlist[pre][4]
return round(total，2)
(4)实现是否接单判断的Python部分程序如下，请在划线处填入合适的代码。
def add(oldlist，x，c)：　#在x所指节点后插入新节点c
c[4]＝oldlist[x][4]
oldlist.append(c)
oldlist[x][4]＝len(oldlist)－1
return oldlist
#读取骑手信息，存储在lit中，代码略
tc＝[″t″，″119.936506″，″31.008933″，″12：05″，－1]　#新订单取餐信息　
sc＝[″s″，″119.919839″，″31.020183″，″12：22″，－1]　#新订单送餐信息
ans＝[－1，－1，10000]
head＝0
p＝head
while p！＝－1：
lit＝add(lit，p，tc)
①____________
while q！＝－1：
lit＝add(lit，q，sc)
tot＝totd(lit，head)
if tot！＝－1 and ②____________ ：
　　　ans＝[p，q，tot]
lit[q][4]＝lit[lit[q][4]][4]
q＝lit[q][4]
lit[p][4]＝lit[lit[p][4]][4]
p＝lit[p][4]
if ans[2]＝＝10000：
print(″不建议接单，不能在系统指定时间内送达。″)
else：
print(″可以接单，建议各取送点到达顺序依次为：″)
#按顺序输出各取送点代码略
答案　(1)10 (2)int(tim[0：2])*60 或 int(tim[：2])*60 (3)4　 不影响
(4)①q＝lit[p][4] 或 q＝lit[p][－1]
②tot解析　本题考查链表的遍历和插入等操作。(1)取餐点一定在送餐点的前面，若有3个送餐点，则可以分别在这3个点的4个地方依次插入取送餐点，则分别有4＋3＋2＋1＝10种方案。(2)获取字符串中小时并转换成分钟。(3)4个取送餐点有3段距离，但循环条件需判断4次。cur是当前节点，pre为当前节点的前驱，当前节点为－1时，其前驱的指针区域值也为－1。(4)①节点p遍历链表，在节点p的后面插入取送餐点，因此q的初值为节点p的后继。②变量ans存储了插入点位置及距离，语句ans＝[p，q，tot]表示更新了其值，因此条件是新的距离tot小于最短距离ans。验收卷(一)　数组与链表
(考试时间40分钟　满分50分)
一、选择题(本题共12小题，每小题2分，共24分)
1.单向链表与数组都属于线性表，它们都用于存储具有相同属性的数据，下列说法不正确的是(　　)
A.对于需要频繁插入和删除元素的情况，使用单向链表比使用数组合适
B.查找特定元素，使用单向链表比使用数组方便
C.数组适用于最大元素个数容易确定的情况
D.存储相同的元素，使用单向链表比使用数组方便
2.下列关于数组和链表的存储结构与逻辑结构关系的说法，正确的是(　　)
A.链表的存储结构与逻辑结构一致
B.数组的存储结构对逻辑结构没有影响
C.存放相同数据的数组存储空间大于链表
D.链表数据的逻辑结构由指针表示
3.利用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]
4.下列关于链表的叙述中，正确的是(　　)
A.线性链表中的各元素在存储空间中的位置必须是连续的
B.线性链表中的表头元素一定存储在其他元素的前面
C.线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面
D.线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的
5.关于单向链表的节点结构，下列说法不正确的是(　　)
A.节点的数据区域用于存放实际需要处理的数据元素
B.节点的指针区域用于存放该节点相邻节点的存储地址
C.单向链表必须带有数据区域为空的头节点和尾节点
D.单向链表中的各个节点在内存中可以非顺序存储
6.有如下Python程序段：
a＝[[2，2]，[5，3]，[3，1]，[6，－1]，[1，0]，[4，2]]
p＝5
while a[p][1]！＝－1：
　　print(a[p][0]，end＝″→″)
　　p＝a[p][1]
则运行程序后，控制台输出的结果是(　　)
A.4→3→5 B.4→3→2→5→
C.4→3→5→ D.4→3→2→5
7.有下列Python程序段：
a＝[[1，3]，[1，0]，[7，1]，[4，5]，[1，－1]，[6，4]]
x＝1
p＝pre＝head＝2
if x＝＝a[head][0]：
head＝a[head][1]
else：
while p！＝－1 ：
if x＝＝a[p][0]：
　　　　a[pre][1]＝a[p][1]
else：
　　　　pre＝p
p＝a[p][1]
运行该段程序后，a[2][1]的值为(　　)
A.－1 B.0 C.1 D.3
8.采用Python二维列表模拟链表，
a＝[['A'，1]，['B'，2]，['C'，3]，['D'，4]，['E'，5]，
['F'，－1]]表示链表为：
A→B→C→D→E→F→None，有以下Python程序：
a＝[['A'，1]，['B'，2]，['C'，3]，['D'，4]，['E'，5]，
['F'，－1]]
head＝0；p＝a[head][1]
a[head][1]＝－1
while p！＝－1：
p＝a[p][1]
if p＝＝－1：
break
t＝a[p][1]
a[p][1]＝head
head＝p
p＝t
执行以上程序后，以head为首的链表结构为(　　)
A.E→C→A B.A→C→E
C.B→D→F D.F→D→B
9.有如下 Python 程序：
a＝[43，23，87，67，80]
queinfo＝[]
for item in a：
　k＝0
　 while kif 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
10.有如下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]
11.有如下 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 ib.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]
12.某Python程序如下：
data＝[]
for i in range(len(a))：
　data.append([a[i]，i＋1])
data[－1][1]＝－1
la＝head＝0
t＝data[head][1]
key，c＝2，0
while c<3 and t！＝－1：
　 if data[t][0]－data[la][0]　 c＋＝1
　la＝t
　t＝data[t][1]
已知执行上述程序后，t的值为6，则数组a的值可能(　　)
A.[4，3，1，6，3，9，3] B.[2，6，5，1，6，4，0]
C.[7，5，2，3，2，7，5] D.[2，4，0，1，0，8，4]
二、非选择题(本题共4小题，共26分)
13.(6分)大部分社交软件都有好友推荐的功能，当用户A和用户B不为好友，但他们的共同好友数量超过阈值m时，由系统向用户A推荐用户B。
编写Python程序，实现好友推荐功能。生成一个二维数组a记录两者关系，当a[0][2]的值为1时，表示ID1和ID3是好友，值为0则不是好友。运行程序，输入用户ID和共同好友数量超过阈值m，显示每个用户ID的好友及向目标用户推荐的好友列表。程序运行界面如图：
共同好友数量超过阈值m：2 1ID号的好友有：2，3，4，5，6，7，9 2ID号的好友有：1，3，4，5，6，7，10 3ID号的好友有：1，2，5，6，7，8，9 4ID号的好友有：1，2，5，6，7，8，9，10 5ID号的好友有：1，2，3，4，6，8 6ID号的好友有：1，2，3，4，5，7，9，10 7ID号的好友有：1，2，3，4，6，8 8ID号的好友有：3，4，5，7，9，10 9ID号的好友有：1，3，4，6，8 10ID号的好友有：2，4，6，8 向用户ID1推荐的共同好友有：[8，10]
编写的代码如下：
n＝10
#产生一个n*n的二维数组a，存储两人之间的关系。
def Check(a，x，y): #向用户ID为x推荐的阈值为y的好友列表。
n＝10；ans＝0
nothy＝[]
for i in range(n): #查找与x不是好友的朋友编号
　 if ①____________：
　　　 　nothy.append(i)
hy＝[]
for i in nothy：
　 t＝0
　 for j in range(n)：
　 if ②____________：
　　　 　t＋＝1
if t>y：
　 hy.append(i＋1)
return hy　
hm＝int(input(″输入用户ID：″))
m＝int(input(″共同好友数量超过阈值m：″))　
for i in range(n)：
　 s＝str(i＋1)＋″ID号的好友有：″
　 for j in range(n)：
　 if a[i][j]＝＝1：
　　　　s＝s＋str(j＋1)＋″，″
　print(s[：－1])
③____________
print(″向用户ID″，hm，″推荐的共同好友有：″，p)
(1)输入用户ID为7，阈值m为4，则推荐的好友是________。
(2)请在程序划线处填入合适的代码。
14.(6分)某影平台上架新影片时，需要先确定该影片的类型，如喜剧片、动作片、爱情片。确定某影片的类型，可根据已有的样本数据(如图a所示)进行分类。
某分类算法如下：计算该影片与样本中各影片分镜头的相似度，相似度可用距离公式来表示，例如“美人鱼”各分镜头数据如图b所示，其与“宝贝当家”影片的距离为。用该方法计算出“美人鱼”与样本中所有影片的距离，选取前k个最近距离的影片，统计出现频次最多的影片类型，即为该影片的类型。
电影名称 搞笑镜头 拥抱镜头 打斗镜头 影片类型
宝贝当家 45 2 9 喜剧片
唐人街 探案 23 3 17 喜剧片
我的特工 爷爷 6 4 21 动作片
…… …… …… …… ……
泰坦尼克号 9 39 8 爱情片
罗马假日 9 38 2 爱情片
新步步惊心 8 34 17 爱情片
图a
电影名称 搞笑 镜头 拥抱 镜头 打斗 镜头 影片 类型
美人鱼 19 18 5 ？
图b
距离最近的前5部影片为： 唐人街探案19.62，罗马假日22.56，新步步惊心22.83，泰坦尼克号23.45，我的特工爷爷24.92，
图c
请回答下列问题：
(1)与《美人鱼》距离最近的前5部影片如图c所示，则该影片属于________(单选，填字母：A.喜剧片 /B.动作片 /C.爱情片)。
(2)定义如下mvmin(result，flag)函数，参数result列表存储距离，flag列表存储标记。若result＝[43，33，18，25，65]，flag＝[False，False，True，True，False]，则函数的返回值为________。
def mvmin(result，flag)：
mv＝10000　#假定result列表元素值不超过10000
for i in range(len(result))：
　　 　if mv>result[i] and flag[i]＝＝False：
　　　 mv＝result[i]
　　　pos＝i
return pos
(3)实现电影分类的部分Python程序如下，请在划线处填入合适的代码。
读取样本影片的镜头数据，存储在data中，每个元素包含5个数据项，分别对应电影名称、搞笑镜头、打斗镜头、拥抱镜头、影片类型。
如data＝[[″宝贝当家″，45，2，9，″喜剧片″]，……]，代码略。
x＝[″美人鱼″，19，18，5]
dic＝{″喜剧片″：0，″动作片″：0，″爱情片″：0}
k＝5　
result＝[0]*len(data)
for i in range(len(data))：
d＝0
for j in range(1，4)：
　　tmp＝①________
　 　d＋＝tmp**2　
result[i]＝round(d**0.5，2) #结果保留2位小数
flag＝[False]*len(result)
print(″距离最近的前″，k，″部影片为：″)
while k>0：
p＝mvmin(result，flag)
flag[p]＝True
②________
print(data[p][0]，result[p]，end＝″，″)
③________
#统计前k个最近距离的影片中出现频次最多的类型，并输出该影片类型，代码略
15.(7分)某学校工会举行飞镖大赛，共有n位老师报名参赛，每位选手共掷5支镖，每镖得分为0至10分，选手总分为 5镖成绩之和，每位选手的比赛数据记录在文本文件中，如图a所示。
处理要求：数据读入数组 data 中，计算出每位选手的总分，在不改变数据在原数组 data 中的位置的条件下，按总分从高到低输出选手的编号和总分。
(1)主程序。采用链表结构处理数据。程序运行结果如图 b所示。请在程序中划线处填入合适的代码。
data＝readdata(″scores.txt″) #读取数据，计算总分
print(″处理前的数据为：\\n″，data)
n＝len(data)
flag＝[True]*n #标记数据被使用情况
head＝findmax() #返回 data 中可使用状态最大数的位置
k＝head
for i in range(1，n):
　 posi＝findmax()
　 data[k].append(posi)
　______________
data[k].append(－1)
print(″处理后的数据为：\\n″，data)
print(″从高分到低分输出为：″)
output(head)
(2)编写readdata函数，功能为从文本文件读取数据，计算出总分，返回列表。代码如下，请在程序中划线处填入合适的代码。
def readdata(filename):
　 f＝open(filename)
　 line＝f.readline()
　　lst＝[]
　　while line: #获取每位选手的编号和总分数据
　　 　line＝line.split(″，″)
　　　s＝0
　 　　for i in range(1，len(line))：
　　 　__________
　　　lst.append([line[0]，s])
　 　　line＝f.readline()
return lst
(3)编写findmax函数，功能为返回 data 中可使用状态最大数的位置pos，并设置该数的使用状态为 False。请在程序中划线处填入合适的代码。
def findmax()：
　maxnum＝0
　 for i in range(n)：
　 if ①____________：
　　　 maxnum＝data[i][1]
　　　 pos＝i
　　　②____________
　　　return pos
(4)编写output函数，功能为从高分到低分输出选手的信息。代码如下，加框处的代码有误，请改正。
def output(q)：
　　while　：
　 print(data[q][0：2]，end＝″>>″)
　q＝data[q][2]
print(″NULL″)　#表示结束
16.(7分)“抢单”是外卖骑手的日常，当外卖平台上一个新的订单出现时，骑手需要在短时间内考虑是否抢单。平台根据骑手的实际信息，给出是否抢单的建议，若建议抢单则给出到达各个取送点的顺序。
平台判断是否抢单的算法设计如下：
1)在不改变已有订单各取送点顺序的前提下，将新订单按先取餐后送餐的顺序分别插入原来的路线中，枚举所有新路线；
2)计算新路线路程，并进行判断：每个取送点都有一个系统指定时间，若骑手到达该位置时，时间晚于系统指定时间，则该方案无效；
3)对新路线进行计算和判断后，删除此次枚举的两个插入位置，还原为初始状态，再继续进行下一次枚举；
4)在所有有效方案中，输出总路程最小的方案，若无有效方案，则输出不接单的建议。
如果骑手目前无订单在派送中，则插入订单A的方案只有1种，骑手→取餐点A→送餐点A；如果骑手订单中已有1个送餐点A和1个送餐点B，则新订单C有6种插入方案，如下所示，
方案1：骑手→取餐点C→送餐点C→送餐点A→送餐点B
方案2：骑手→取餐点C→送餐点A→送餐点C→送餐点B
方案3：骑手→取餐点C→送餐点A→送餐点B→送餐点C
方案4：骑手→送餐点A→取餐点C→送餐点C→送餐点B
方案5：骑手→送餐点A→取餐点C→送餐点B→送餐点C
方案6：骑手→送餐点A→送餐点B→取餐点C→送餐点C
(1)若骑手仅剩3份餐未送(已取餐)，路线为：骑手→送餐点A→送餐点B→送餐点C，新的订单出现后，有________种插入方案。
(2)定义如下con(tim)函数进行时间格式转换，将24小时制的“时：分”转换为分，如02：30转换为150，请在划线处填上合适代码。
def con(tim)：
　t＝__________＋int(tim[3：])
　　return　t
(3)定义totd(riderlist，h)函数，其功能为从头指针h进入链表riderlist，按节点先后顺序计算总路程，并判断能否在系统指定时间内到达各取送点，若到达某一取送点时超时返回－1。若链表riderlist如下，
riderlist＝[[″u1001″，″119.906033″，″31.014597″，″11：30″，2]，
[″s″，″119.921439″，″31.023022″，″11：55″，3]，
[″t″，″119.887850″，″31.022861″，″11：40″，1]，
[″s″，″119.953836″，″31.021122″，″12：10″，－1]]
第1个元素中″u1001″为骑手编号，″119.906033″和″31.014597″，表示骑手实时位置，″11：30″为实时时间，2为下一节点指针，第2个元素开始，第1项若为″t″表示此元素为取餐点信息，若为″s″表示此元素为送餐点信息。调用函数totd(riderlist，h)，risderlist的值如上，h为0，则加框处语句最多被执行______次，若将此条件语句改为riderlist[pre][4]！＝－1，______(选填：影响/不影响)程序执行。
def totd(riderlist，h):
speed＝0.3　#speed为骑手每分钟公里数
total＝0
pre＝h
cur＝riderlist[pre][4]
while ：
#计算pre与cur两个节点所在位置间的路程，存储在变量d中
total＋＝d
if total/speed>con(riderlist[cur][3])－con(riderlist[h][3])：
　　　　return －1
else：
　　　　 pre＝cur
　　　　 cur＝riderlist[pre][4]
return round(total，2)
(4)实现是否接单判断的Python部分程序如下，请在划线处填入合适的代码。
def add(oldlist，x，c)：　#在x所指节点后插入新节点c
c[4]＝oldlist[x][4]
oldlist.append(c)
oldlist[x][4]＝len(oldlist)－1
return oldlist
#读取骑手信息，存储在lit中，代码略
tc＝[″t″，″119.936506″，″31.008933″，″12：05″，－1]　#新订单取餐信息　
sc＝[″s″，″119.919839″，″31.020183″，″12：22″，－1]　#新订单送餐信息
ans＝[－1，－1，10000]
head＝0
p＝head
while p！＝－1：
lit＝add(lit，p，tc)
①____________
while q！＝－1：
lit＝add(lit，q，sc)
tot＝totd(lit，head)
if tot！＝－1 and ②____________ ：
　　　ans＝[p，q，tot]
lit[q][4]＝lit[lit[q][4]][4]
q＝lit[q][4]
lit[p][4]＝lit[lit[p][4]][4]
p＝lit[p][4]
if ans[2]＝＝10000：
print(″不建议接单，不能在系统指定时间内送达。″)
else：
print(″可以接单，建议各取送点到达顺序依次为：″)
#按顺序输出各取送点代码略
验收卷(一)　数组与链表
1.B　[本题主要考查的是数组和链表的特性。查找特定元素，使用单向链表查找时，只能通过头指针进入链表并通过指针链接依次访问，直到找到特定元素，而使用数组查找时，只要使用数组名和下标就能直接访问特定元素，因此，查找特定元素，使用数组比使用单向链表更方便。]
2.D　[链表的节点结构包括数据域与指针域，指针表示各节点的连接前后顺序，即链表数据的逻辑结构由指针表示，D选项正确。]
3.A　[赋值对象为qp[j][i]，即i表示列，j表示行，意味着是按列遍历矩阵，因此第1列为1－6，第2列为m*6＋6－j，即12－7递减，第3列为13－18。]
4.D　[单链表存储方式地址不连续，元素顺序是任意的，因此答案为D。]
5.C　[选项单向链表的头节点和尾节点可以是单独的数据区域为空的节点，也可以将节点序列中的第1个和最后一个节点作为头节点和尾节点。在Python程序设计时我们通常使用第二种方式，即直接使用带数据区域的节点作为头节点或尾节点来标记和使用。]
6.C　[本题考查链表的遍历。条件a[p][1]！＝－1表示当前节点的指针区域值为－1，即当前节点为尾节点。当遍历到尾节点时，结束循环。]
7.D　[本题考查链表的基本操作。如果链表头节点值为1，直接删除头节点，否则遍历链表，语句a[pre][1]＝a[p][1]的作用让节点p的前驱指向他的后继，即删除p节点。程序的功能是删除元素值为1的节点。]
8.A　[本题考查链表的基本操作。p的初值为a[head][1]，即head的后继，进入循环后，语句p＝a[p][1]的功能是向后遍历，让该节点指向头节点，p再向后遍历。A后继的后继是C，当前头节点为C，C指向A；C后继的后继是E，当前头节点为E，E指向C。]
9.B　[queinfo初值为空，语句queinfo.append([item])是将一个列表添加到queinfo，因此他是一个二维数组。遍历列表a，在queinfo数组从第0个元素开始，与每个元素最后一个数据项进行比较，如果大于等于元素最后一个数据项，结束比较，此时j肯定在0至len(queinfo)－1之间，若j的值为len(queinfo)，说明该元素比queinfo中每个元素的最后一个值均小，则新成一组。Queinfo的值为[[43，87]，[23，67，80]]。]
10.C　[本题考查二维数组的创建和遍历。先创建一个6行6列的二维数组，遍历二维数组的每一行，内循环从0至i，因此只对二维数组的左下半部分进行赋值。将第1列和主对角线(i和j相等)的数据全部赋值为1，其他数据为上一行的前一个和上一行的当前列之和，因此程序的功能是构建一个杨辉三角。]
11.A　[本题考查二维数组的应用.将二维数组a中下标i12.B　[本题考查链表应用。data是一个链表，t指针从链表的第二个节点开始遍历，1a指针是t节点的前驱，t节点减去前驱节点la的值小于key时，c计数，c的初值为0，计数到3时历结束，也就是整个过程计数3次就结束，执行程序后t的值为6，也就是遍历到最后一个节点时程序才结束。]
13.(1)5，9　(2)①a[i][x]＝＝0 and x！＝i
②a[x][j]＝＝1 and a[i][j]＝＝1
③p＝Check(a，hm，m)
解析　(1)在不是好友中选择共同好友超过4的ID，ID10与ID7的共同好友只有4个。(2)①查找与x不是好友的朋友编号，在各个编号中遍历，相当在于二维表格的第x行查找0的列号，但列号不能是x自己。②寻找共同好友，即第x第i行中，值均为1的列号数量。③调用自定义函数查找共同好友。
14.(1)C　(2)1　(3)①data[i][j]－x[j] 或 x[j]－data[i][j]
②dic[data[p][4]]＋＝1　③k－＝1
解析　(1)距离最近的5部影片中，喜剧片1部，爱情片3部分，动作片1部，因此该影片类型为爱情片。(2)在存储标记为False的位置中，查找最小值的索引，43，33，65三个数中最小值索引为1。(3)①遍历所有的样本数据data，计算出“美人鱼”与样本中所有影片的距离。data[i][1]、data[i][2]、data[i][3]分别表示样本数据中搞笑镜头、打斗镜头、拥抱镜头的值，用变量j表示这些下标，计算与x[j]的平方差的和。②调用mvmin函数计算最小距离的索引p，即对应的样本的索引，在数组元素data[p][4]中存储的是该影片的类型，需要对该类型的数量增加1。
③处理下一个样本数据。
15.(1)k＝posi　(2)s＋＝int(line[i])
(3)①maxnum(4)q！＝－1
解析　(1)查找数组中的最大值的位置，利用位置关系串成一个降序链表，最后遍历链表输出。k 是当前元素的位置，posi 是下一个元素的位置，找到的数应该在节点 posi 后面。(2)readdata函数功能是读取“scores.txt”文件，生成一个二维列表。变量s累计的总分。(3)findmax函数找到最大数所在位置，同时将该位置设置为 False。
(4)遍历链表，输出节点相关数据域的内容。
16.(1)10　(2)int(tim[0：2])*60 或 int(tim[：2])*60　(3)4　 不影响　(4)①q＝lit[p][4] 或 q＝lit[p][－1]　 ②tot解析　本题考查链表的遍历和插入等操作。(1)取餐点一定在送餐点的前面，若有3个送餐点，则可以分别在这3个点的4个地方依次插入取送餐点，则分别有4＋3＋2＋1＝10种方案。(2)获取字符串中小时并转换成分钟。(3)4个取送餐点有3段距离，但循环条件需判断4次。cur是当前节点，pre为当前节点的前驱，当前节点为－1时，其前驱的指针区域值也为－1。(4)①节点p遍历链表，在节点p的后面插入取送餐点，因此q的初值为节点p的后继。②变量ans存储了插入点位置及距离，语句ans＝[p，q，tot]表示更新了其值，因此条件是新的距离tot小于最短距离ans。

展开更多......

收起↑