资源简介

第二章　数组与链表
课时1　数　组
一、基础巩固
1. 有如下Python程序段：
a＝[4，4，4，9，4，9，6，4，4]
s＝[0，0，0，0，0，0，0，0，0]
for i in range(0，len(a)，2)：
　 s[a[i]]＋＝1
print(s[4])
执行程序段，输出结果的是(　　)
A.6 B.5 C.4 D.3
2.已知二维数组a＝[[1，3，5]，[2，4，6]，[7，8，9]]，执行语句s＝a[1][2]＋a[2][1]后，变量s的值为(　　)
A.5 B.11 C.13 D.14
3.有如下Python程序段：
b＝[11，4，17，19，3，8，19，5]
k＝0
for i in range(1，len(b))：
if b[i]>b[k]：
k＝i
b.pop(k)
程序段执行后，数组b中的元素为(　　)
A.11，4，17，19，3，8，19，5
B.11，4，17，3，8，19，5
C.11，4，17，19，3，8，5
D.11，4，17，19，3，8，19
4.有如下Python程序段：
s＝0
a＝[[2，8，3]，[1，6，4]，[5，7，9]]
for i in range(3)：
for j in range(3)：
if i＝＝j：
　　　　 s＝s＋a[i][j]
程序段执行后，变量s的值为(　　)
A.11 B.14 C.17 D.21
5.有如下Python程序段：
a＝[[i＋1 for i in range(4)] for j in range(3)]
for i in range(3)：
for j in range(4)：
a[i][j]＝a[i][j]＋4*i
则程序执行后，a[1][2]的值为(　　)
A.2 B.4 C.7 D.8
6.有如下Python程序段：
num＝[0]*10
n＝36
s＝0
for i in range(n)：
　 j＝9
　 num[j]＋＝1
　while num[j]＝＝2：
num[j]＝0
j－＝1
num[j]＋＝1
for i in range(10)：
　 s＋＝num[i]
print(s)
执行此代码后，变量s的值为(　　)
A.2 B.3 C.4 D.5
7.查找素数能够很好地体现出计算机解决某些数学问题的速度优势，除了计算机性能以外，设计更加简单的算法也能够提高计算机解决某些问题的速度。某种素数算法就是通过“开关”的思想，例如求100以内的所有素数，采用数组来表示[1，1，1，……，1，1，1]，数组的索引值表示0～99中的每个数，1表示“开”即为素数(先假设都为素数))，从2(0和1不是素数)开始，因为索引2号对应的值为1，则2是素数，再将后面能够被2整除的索引对应的值都改为0，依次类推……以下程序就是采用这种思路编写的输出1000以内的所有素数的程序：
lst1＝[]　　　　　# 存放每个数的开关
lst2＝[] # 存放找到的素数
lst1＝[1]*1000 # 初始化开关列表
for i in range(2，1000)：
if lst 1[i]＝＝1：
lst2.append(i)
________：
　　 lst1[j]＝0
print(lst2)　 # 输出所有1000以内的素数
上述程序横线处的合适代码为(　　)
A.if lst1[j]%i＝＝0
B.if lst1[i]%i＝＝0
C.for j in range(i，1000，i)
D.for j in range(i＋1，1000，i)
8.某次测试的答题结果存储在asht.txt文件中，该文件每行记录1个考生10道单选题的答案，每题有A，B，C，D四个选项，空白的答案标记为'K'。评分标准：正确得3分，错误得－1分，空白得0分。实现评分的Python程序如下。
ANS＝'ACBBCDADBC' #ANS 为标准答案
score＝[]
for line in open('asht.txt'，'r'):
　 score.append(0)
　 i＝len(score)－1
　 j＝0
　 while j　 if ①____________：
　　　 score[i]＋＝3
　 elif line[j]！＝'K'：
　　　 ②______________
j＋＝1
print(score)
(1)若标准答案为：'ACBBCDADBC'，则答案'ACBBDDADKC'的得分为________。
(2)完善上述①②处代码。
二、能力提升
9.下列程序的功能是：输入一个由大小写字母和数字组成的字符串，统计字符串中出现次数最多的小写字母。
程序运行界面如下图所示：
实现上述功能的Python程序如下，请在程序划线处填入合适的代码。
s＝input(″输入字符串：″)
a＝[0]*26
for i in range(len(s))：
if ″z″>＝s[i]>＝″a″：
①________________
a[n]＋＝1
max＝0
for i in range(26)：
if a[i]>max：
max＝a[i]
②________________
print(chr(ord(″a″)＋posi)，″times：″，max)
10.某物品柜有5层，每层有10个格子，每个格子只能放一个物品。输入一组物品的高度值(按降序排列)，将这些物品放在同一层的连续格子中。第一步：查找存放物品的格子。从第1层开始查找，若该层物品柜连续空格数量小于物品数量，则查找下一层。查找5层后还是不能找到连续存放位置，输出“不能连续存放”。若在某一层中找到符合要求的连续空格子，则进行第二步：将物品按中间高两端低的原则存放物品。先将高度最高的物品存放在连续空格的中间位置(若空格数量为偶数，则放在中间靠左位置)，接着依次将物品按先右后左的顺序依次存放。如输入物品高度为8，5，2，1，则依次放在第1排的第5，6，4，7的位置。第一排各个格子存放物品高度如图所示，其中0表示未存放物品。
0 0 0 2 8 5 1 0 0 0
(1)输入第1组物品高度依次为8，5，2，第2组依次为9，6，3，1，则高度为3的物品存放在第1排第__________(填数字)个格子中。
(2)实现该功能的Python程序段如下，请在程序划线处填入合适的代码。
#将已经存放的物品高度存储在数组a中，如：
[[0，9，6，2，8，5，1，0，0，0]，[0，0，1，7，10，9，2，0，0，0]，……]，代码略。
s＝input(″输入一组降序的物品高度，用逗号分开：″)
wp＝list(map(int，s.split(″，″))) #输入的数字转换成列表
flag＝False；i＝0
while i<5 and not flag：
　 beg＝0　
　 for j in range(10)：
　 if a[i][j]＝＝0: #物品柜格子为0表示没有存放物品
　　　 if j－beg＋1>＝len(wp)：
　　　　hang＝i；end＝j；flag＝True
　 else：
　　　 if flag ：
　　　　 break
　　　 ①______________
i＋＝1
if flag：
②____________
a[hang][wz]＝wp[0]
i＝1
while iif ③____________：
　　　　 wz－＝i
else：
　　　　wz＋＝i
a[hang][wz]＝wp[i]
i＋＝1
else：
print(″不能连续存放″)
#输出物品柜的存放情况，代码略
11.杨辉三角，是二项式系数在三角形中的一种几何排列，在我国南宋数学家杨辉1261年所编写的《详解九章算法》一书中出现。我们可以把杨辉三角看作这样的图形：最左侧一列数字和右边的斜边数字均为1，内部其他位置上的每个数字均为上一行同一列的数字与上一行前一列数字之和，前10行的杨辉三角如图所示。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
为了在计算机存储和处理上述的数据，可用数组表示。实现输出该图形的代码如下，在程序划线处填入适当的语句或表达式，将程序补充完整。
n＝int(input(″请输入行数n＝：″))
pa＝[1]*100
k＝1　　#变量k存储上一行的下标起始位置
for i in range(2，n)：
t＝k＋i＋1　#变量t存储当前行的下标起始位置
for j in range(i－1)：
　　 　pa[t＋j]＝pa[k＋j]＋①____________
k＝k＋i
k＝0
for i in range(n)：　 #输出第0到n－1共n行的数据
s＝″″
for j in range(i＋1)：
　s＝s＋″　″＋　②__________________
　　k＋＝1
print(s)
12.编写“矩形面积”程序，实现如下功能：随机生成一个包含0或1的10×10的二维数组a；当数组元素的值为0时表示没有障碍物，当数组元素的值为1时有障碍物。寻找阵列中构造出的最大面积的矩形面积和起点坐标。程序运行界面如图所示。
(1)实现上述功能的Python程序如下，请在划线处填入合适的代码。
(2)程序中加框处代码有错，请改正。　
实现上述功能的Python代码如下：
def Check(a，x，y): #在数组a中从点x，y开始向右向下查找最大矩形面积
i＝x；maxx＝0；n＝10；jn＝10
while iif ①____________：
　　　　 break
j＝y＋1；s＝0
while j　　　 　j＋＝1
②____________
jn＝j #更新右边界，从该位置开始，右边的区域不能计算面积
if s>maxx：
　　　 maxx＝s
i＋＝1
return maxx
#产生一个10*10的初值为0的二维数组a，并随机产生若干个障碍物，将数组a中的值修改为1，代码略
n＝0；maxx＝0；px＝0；py＝0；t＝0
for i in range(n)：
for j in range(n)：
　 if ：
　　　 ③____________
　if t>maxx：
　　　　　maxx＝t
　　　　　px＝i＋1
　　　　　py＝j＋1
print(″构成的最大面积是：″，maxx，″。起点坐标为：″，px，py)
课时1 数组
1.C　[本题考查记数统计。统计奇数位置上4的个数。]
2.D　[本题主要考查的是二维数组的运算。a[1][2]是指数组a中第2行第3个元素，即a[1][2]＝6, a[2][1]是指数组a中第3行第2个元素，即a[2][1]＝8，因此s＝14，答案为D。]
3.B　[本题主要考查的是一维数组的操作。本程序的功能是找出数组b中值最大的元素所在的位置，然后将该位置上的元素从数组b中删除，根据程序代码可知，若值最大的元素有多个时，k记录的是第一个最大值的位置，因此，操作后数组b中的元素为“11，4，17，3，8，19，5”，故答案为B。]
4.C　[本题主要考查的是二维数组的操作。本程序的功能是求二维数组中正对角线上的元素之和，即s＝2＋6＋9＝17，因此答案为C。]
5.C　[本题主要考查的是二维数组的定义与赋值。本程序的功能首先为3行4列的二维数组a赋值 [[1，2，3，4]，[1，2，3，4]，[1，2，3，4]]，然后依次给二维数组a加4*i，a[1][2]即为第2行第3列的值为7，故答案为C。]
6.A　[本题主要考查的是数组的应用。题目中的程序实现的是进制数的转换，变量i从 0循环到35，每次循环j从9开始，对该位置上的值加1，当该位置上的值满2时，该位置上的值变为0，向j－1位置上进1。因此程序的功能是将36转成二进制，其值为100100，将二进制位置上的各值进行累加，和为2，答案为A。]
7.C　[本题主要考查的是数组的应用。按照题意，程序的外层for循环列举所有1000以内的可能素数，作为数组lst1的下标位置，如果该位置对应的数组元素值为1，作为素数存入数组lst2，同时按照素数的性质排除后面的为该素数的整数倍的整数判定为非素数，所以划线处即列举该数的倍数整数，答案为C。]
8. (1)23　(2)①line[j]＝＝ANS[j]　 ②score[i]－＝1
解析　本题考查顺序查找算法。line表示asht.txt文件中每一条记录，每条记录有10道单选题答案。语句score.append(0)表示每读取一条记录，该列表增加一个值为0的元素，i表示score列表中最后一个元素的索引值。j初值为0，终值为len(ANS)－1，表示在标准答案中比对当前记录中答案，如果line[j]＝＝ANS[j]表示当前答案与标准答案一致，得3分，不正确将扣1分。
9.①n＝ord(s[i])－ord(″a″)　 ②posi＝i
解析　本题主要考查的是数组的综合应用。本题的算法思想是：将小写字母a～z出现的次数依次记录在数组元素a[0]～a[25]中，然后求出a[0]～a[25]中的最大值，并记录在变量max中，将字母序号记录在变量posi中，从而求得问题的解。①处代码的功能是求出当前小写字母在字母表中的序号n，因此①处代码为n＝ord(s[i])－ord(″a″)。划线②处代码的功能是用posi记录当前出现次数最多的字母在字母表的序号，因此②处代码为posi＝i。
10.(1)7　(2)①beg＝j＋1　②wz＝(beg＋end)∥2　③i%2＝＝0
解析　本题考查二维数组的遍历和在一个序列中查找最值。(1)高度8，5，2依次存放第5、6、4的格子中，因此左边还有3个空格，右边有4个空格。高度9，6，3，1依次存放第8、9、7、10的格子中。(2)①确定连续空格子的最左边位置beg，若格子为空，计算连续空格子数量为j－beg＋1，若数量达到存放物品数量时，将flag设置为True。若格子不为空，则下一个空格子的位置只能在当前j的下一个位置。②中间位置的计算方法类似于二分查找，将左右位置相加再整除以2。③语句a[hang][wz]＝wp[0]的功能是放置最中间的物品，接下来放在i为1的物品，在中间的右边，即wz等于i＋1，当i的值为2时，放在左边的前面2个位置中，因此通过判断变量i的奇偶性来决定存放的位置。
11.①pa[k＋j＋1]　②str(pa[k])
解析　本题主要考查的是数组的综合应用。根据题意分析可知，计算数组的新值可通过上一行两个连续的数组值相加获得，前一个值为pa[k＋j]，因此①处代码为pa[k＋j＋1]；②处为每一行数据的输出，变量s存储每一行的数据，注意数组pa的类型，需使用str()函数进行转换。
12.(1)①a[i][y]＝＝1　②s＝(i－x＋1)*(j－y)　③t＝Check(a，i，j)　(2)a[i][j]！＝1
解析　本题考查二维数组和枚举算法。将矩阵的每个点作为起点，从该点开始，不断地向右检测，找到能构成矩形的最右边界，向下检测，找到下边界，计算矩形面积，并找出最大面积。自定义函数功能在数组a中从点x，y开始向右向下查找最大矩形面积，终点坐标是(i，j)，先不断地向右查找，若找到1停止，此时的右边界为j－1，再向下一行枚举，若下一行的y位置是1，则不能向下构成矩形，结束查找，因此①表示检测到新行的第1列就是障碍物。②计算矩形面积，表示第x行与第i行，第y列与第j－1列构成的矩形面积。③调用自定义函数计算该坐标开始的最大矩形面积。(2)起点不能是障碍物。课时2　链　表
一、基础巩固
1.下列有关链表的说法中，正确的是(　　)
A.每个链表的表头一定有一个头指针，以实现对链表的引用和边界处理
B.在单向链表中，最后一个节点的指针指向第一个节点
C.链表一旦创建好后，它占用的空间将固定
D.链表的头指针指向第一个节点，因此不能删除第一个节点
2.设指针变量p指向单向链表lst的某中间节点，如图所示，则删除该节点的后继节点的正确操作是(　　)
A.lst[p][next]＝lst[p][next] [next]
B.p＝lst[p][next][next]
C.lst[p][next]＝lst[lst[p][next]][next]
D.t＝lst[p][next]；p＝lst[t][next]
3.某公交路线的站点名称、经度、纬度和下一个站点序号(经纬度已转换为平面坐标 数据)存储在数组 a 中，现计算相邻两个站点距离的总和。
import math
a＝[[″廊桥″，3，2，3]，[″徐岙″，6，11，2]，[″北门″，13，8，－1]，[″上通″，3，7，1]]
head＝0 ; s＝0 p＝a[head][3]
while (1)________：
s＋＝math.sqrt((a[p][1]－a[head][1])**2＋(a[p][2]－a[head][2])**2)
(2)________
(3)________
print(s)
上述程序段划线处可选的代码为：
①a[head][3]！＝－1　②head＝p　③p＝a[head][3] ④head！＝－1
则(1)、(2)、(3)处的代码依次为(　　)
A.①②③ B.④②③ C.④③② D.①③②
4.已知链表 a 中的每个节点包含数据区域和指针区域两部分，下列 Python 程序段的功能是在链表 a 中删除数据值为 key 的所有节点。
key＝int(input(″输入要删除的数据：″))
head＝0
while head！＝－1 and a[head][0]＝＝key ：
　　head＝a[head][1]
p＝q＝head
if head！＝－1:
　　q＝a[q][1]
　　while ①____________：
if a[q][0]＝＝key：
　　　　　②____________
else：
　　　 p＝a[p][1]
　　　q＝a[q][1]
则划线①②处的代码分别为(　　)
A.①a[q][1]！＝－1　 ②a[p][1]＝a[q][1]
B.①a[q][1]！＝－1 ②a[q][1]＝a[p][1]
C.①q！＝－1 ②a[q][1]＝a[p][1]
D.①q！＝－1 ②a[p][1]＝a[q][1]
5.使用Python的二维列表来模拟单向链表，每个节点都是一个列表，其第一个元素存储数据，第二个元素存储指向后继节点的指针。若要删除节点a[p]的后继节点，则需执行语句(　　)
A.p＝a[p][1]
B.a[a[p][1]][1]＝a[p][1]
C.a[p][0]＝a[a[p][1]][0]
D.a[p][1]＝a[a[p][1]][1]
6.用Python程序实现删除链表的倒数第n(n不大于链表长度)个节点，如n＝2时，链表
更新为
部分代码如下：
#读入链表存储在列表s中，head存储链表的头节点，代码略
n＝int(input())
p1＝p2＝head
while p2！＝－1：
　　if n>＝0：
(1)____
n－＝1
　　else：
(2)____
p2＝s[p2][1]
if p1＝＝head and n>＝0：
　head＝s[head][1]
else：
　　(3)____
上述程序段中划线处可选的语句为：
①p1＝s[p1][1]　②p2＝s[p2][1]
③s[p1][1]＝s[s[p1][1]][1]
④s[p2][1]＝s[s[p2][1]][1]
则(1)～(3)划线处语句依次为(　　)
A.①③④ B.①④③ C.②①④ D.②①③
7.在升序链表 a 中插入一个不重复数据 data，仍保持链表的升序状态。使用 python 程序实现插入操作，代码如下：
data＝[[20，4]，[6，3]，[35，5]，[18，0]，[27，2]，[59，－1]]
p＝head＝1
data＝int(input())
if data<＝a[head][0]:
　a.append([data，head])
　head＝len(a)－1
else：
　　q＝a[p][1]
　　while ①____and data>a[q][0]：
　p＝q
　q＝a[p][1]
　　②____
a.append([data，q])
则划线处的代码为(　　)
A.①p！＝－1　②a[p][1]＝len(a)－1
B.①q！＝－1 ②a[p][1]＝len(a)
C.①q！＝－1 ②a[q][1]＝len(a)－1
D.①p！＝－1 ②a[q][1]＝len(a)
8.实现在链表 c 中找出最小值 m 的 Python 程序如下：
head＝3；p＝head；m＝c[head][0]
while (1)____：
(2)____
if c[p][0]m＝c[p][0]
上述程序段中方框处可选代码为：①p！＝－1
②c[p][1]！＝－1　 ③p＝p＋1　④p＝c[p][1]
则程序段中(1)、(2)处代码依次为(　　)
A.①③ B.②③ C.①④ D.②④
9.将两个链表a(A→B→C)和b(D→E)按照间隔次序合并为一个链表，并将结果保存到链表a(A→D→B→E→C)中，部分程序如下：
#读取链表a和b，均存储在列表data中，其中ha表示a的头指针，hb表示b的头指针p，p，q＝ha，hb
while p！＝－1 and q！＝－1：　　
r＝data[q][1]
q＝r
填入方框处的可选代码有：①data[p][1]＝data[q][1]
②data[q][1]＝data[p][1]　③data[p][1]＝q
④data[q][1]＝p　⑤p＝data[p][1]　⑥p＝data[q][1] 已知链表 b 的长度不超过链表 a，则下列选项中，代码顺序正确的是(　　)
A.①④⑤ B.②③⑥ C.①④⑥ D.②③⑤
二、能力提升
10.使用链表结构模拟某景区游玩路线，链表a中每一个节点包含3个数据，第1个为景点名称，第2个为预计游玩时间(单位：分钟)，第3个为下一个景点指针。景区可以从多个景点的大门进入，但只能从″天梯″离开，输出显示各大门进入路线及预计总时间的代码如下。
a＝[[″迎客松″，21，2]，[″激流勇进″，40，2]，[″天空栈道″，50，5]，[″一线天″，30，4]，[″飞来峰″，60，5]，[″天梯″，20，－1]]
head＝[0，1，3]
for i in range(len(head))：
(1)__________
s＝a[p][1]
while a[p][2]！＝－1：
　　　　print(a[p][0]，end＝″→″)
(2)________
(3)________
print(a[p][0])
print(″预计时间：″，s，″分钟″)
上述程序划线处的可选代码有： ①p＝head
②p＝head[i]　 ③s＋＝a[p][1]　 ④ p＝a[p][2]
则(1)(2)(3)处代码依次为(　　)
A.①③④ B.①④③ C.②③④ D.②④③
11.有如下Python程序：
from random import *
a＝[[″e″，4]，[″g″，8]，[″h″，5]，[″h″，0]，[″n″，1]，[″o″，7]，[″S″，3]，[″u″，6]，[″Z″，2]]
k＝randint(1，4)*2＋1
p＝q＝6
while k>0：
　　p＝a[p][1]
　　k－＝1
while p！＝1：
　q＝a[q][1]
　p＝a[p][1]
print(a[q][0])
运行后，输出值不可能是(　　)
A.g B.h C.u D.o
12.使用列表d模拟链表结构(节点数大于0)，每个节点包含数据区域和指针区域，h为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列，如图a所示。现要修改该链表各节点的链接关系，使链表各节点按数据区域中的数值由小到大排列，结果如图b所示。实现该功能的程序段如下，方框中应填入的正确代码为(　　)
t＝h
p＝d[h][1]
while p！＝－1 ：
q＝d[p][1]
p＝q
d[t][1]＝－1
13.有如下 Python 程序段，为实现在链表中插入一个[6，50]区间内的随机数后，链表 data 中的数据仍然有序。
import random
x＝random.randint(6，50)
print(″在链表 data 中插入一个值为″，x，″的数″)
data＝[[14，1]，[26，4]，[5，0]，[49，－1]，[37，3]]
head＝2; q＝head
while q！＝－1：
if x>data[q][0]：
p＝①________
q＝data[q][1]
else：
break
data.append(②________)
data[p][1]＝len(data)－1
q＝head
while q！＝－1：
print(data[q][0]，end＝'')
q＝data[q][1]
请为①②两处选择正确的程序代码(　　)
A.①data[q][1]　　②[x，p]
B.①data[q][1] ②[x，data[p][1]]
C.① q ②[x，p]
D.①q ②[x，data[p][1]]
14.报数游戏。已知班上有n名学生(用编号1，2，3，……n分别表示)，学生按照编号由小到大顺时针围成一个圆圈，从编号为1的学生开始顺时针报数，报到m的同学出列；下一名同学又从1开始报数，报数为m的同学继续出列；以此规律重复下去，直到剩下最后一位同学为止。
(1)当n＝12，m＝3时，最后留下的同学的编号是______。
(2)下列代码通过构造一个循环单向链表，模拟报数的过程，逐一删除报数为m的节点，直到剩下一个节点为止。请在划线处填入合适的代码。
n＝int(input(″n＝″))
m＝int(input(″m＝″))
lst＝[]
for i in range(n－1):
　 lst.append([i＋1，i＋1])
lst.append(①______________) #将尾节点的指针指向头节点，构成循环单向链表
p＝len(lst)－1
while n>1：
　 for i in range(1，m): #从 1～(m－1)依次报数
p＝lst[p][1]
out＝lst[p][1]
②____________
n＝n－1
print(″最后留下的同学的编号是： ″，lst[p][0])
15.张三是一名计算机专业的大学生，为了帮助同学们学习专业相关的英语词汇，编写一个简易字典程序。该程序中存放词汇数据库，在学习中输入英文单词，可以获得中文翻译结果。程序中的词汇数据库采用链表方式存储，首字母相同时按升序排序。查找单词时，首先根据首字母找到同首字母最小单词所在链表，再按照链表顺序查找该单词。
(1)根据题意，部分的单词库数据逻辑结构如图所示，查找单词”byte”的过程是”binary”→”bit”→”byte”，补充图中空白单元格的值为__________。
列表索引 数据区域 指针区域
0 audio 音频 －1
1 binary 二进制数 6
2 byte 字节 －1
3 cursor 光标 －1
4 access 存取 1
5 cache 高速缓存 3
6 bit 比特 ____▲____
(2)wordlist(data，info)函数实现将词汇数据库 data 以链表的方式按字母序升序排列。info表示词汇数据库中各字母开头的最小单词位置，如 info[0]表示字母 a 开头的最小单词在词汇数据库 data 中的位置。实现该功能的程序如下，请在划线处填入合适的代码。
info＝[]
def wordlist(data，info):
　 n＝len(data)
　　for i in range(n)：
data[i].append(－1)
　#data[i]追加一个元素－1
for i in range(n):
　　 　d＝data[i][0]
　　　 ①______________
　　　 if info[k]＝＝－1:
　　　 info[k]＝i
　　　else：
　 　　head＝info[k]
　　　q＝head
　　　while ②____________ ：
　　 　　　p＝q
　　　　　q＝data[q][2]
　　　if q！＝head：
　　 　　　data[p][2]＝i
　　　　　data[i][2]＝q
　　　else：
　　　　　data[i][2]＝head
　　　　　③____________
return data，info
(3)searchword(data，info，key)函数实现单词的查找。程序如下，请在划线处填入合适的代码。
def searchword(data，info，key):
　 k＝ord(key[0])－ord(″a″)
　　head＝info[k]
　　p＝head
　　while p！＝－1：
　 if data[p][0]＝＝key:
　　　　 return ________
　p＝data[p][2]
　　return ″没有找到该单词″
读取词汇数据库，存入列表 data 中，列表的每个元素包含 2 个数据项，分别为英文单词和中文翻译，如 data＝[['audio'，'音频']，['binary'，'二进制数'] …], 数据读取存入的代码略。
info＝[－1] * 26
data，info＝wordlist(data，info)
key＝input(″请输入查找单词：″).lower()
#转化为小写字母
res＝searchword(data，info，key)
print(key，″查找结果是：″，res)
课时2　链　表
1.A　[本题主要考查是链表的特性。链表的头指针指向第一个节点，要删除第一个节点，只需将头指针移动到第一个节点指针的指向即可，因此可以删除第一个节点，故答案为A。]
2.C　[本题主要考查链表的删除操作。删除该节点的后继节点，需将后继节点的指针域赋值为当前节点的指针域值，实现当前节点连接后继节点的后面节点。lst[p][next]表示后继节点的指针，lst[lst[p][next]]表示后继节点。]
3.A　[本题考查链表的遍历。从当前链表的头节点开始遍历，与他下一个节点p的距离，因此head要不断地后移，head＝p，而p为新节点的后继节点。当头指针节点的后继为－1时，表示遍历完了。]
4.D　[本题考查链表节点的删除。①循环遍历整个链表。②q 为当前元素指针，p是当前节点q的前驱，要删除 q 节点，只需要修改 p 的指针为 q 的后继。]
5.D　[语句a[p][1]＝a[a[p][1]][1]是修改节点p的后继指针，使其指向后继节点的后继，以实现删除节点p后继节点的功能。]
6.D　[本题考查链表的删除。while循环查找待删除节点的前驱节点位置。通过p1和p2遍历链表，前n次只遍历p2，后续同时遍历p1和p2，当p2遍历结束时，p1刚好指向倒数第n＋1个节点。所以(1)处选p2＝s[p2][1]，(2)处选p1＝s[p1][1]。确定p1位置后，执行删除操作。如果p1指向头节点head，要删除头节点，即更新head指向原头节点指针区域对应的节点；否则删除p1的后继节点，即p1的指针区域更新为p1后继节点的指针区域，(3)处应选s[p1][1]＝s[s[p1][1]][1]。]
7.B　[本题考查链表中数据查找和插入操作。p、q 是两个前后相邻的节点。根据 data>a[q][0]，可以推测出①为q！＝－1。循环结束后，应该在p节点之后插入节点，所以②处代码是：a[p][1]＝len(a)。]
8.D　[本题考查链表遍历和最值查找。当前节点从头节点开始遍历，最小值的初值为头节点大小，因此需先移动到下一节点，再与最值进行比较，同时终止遍历的条件是遍历到尾节点马上结束。]
9.B　[本题考查链表节点的插入操作。程序将节点q插入到节点p的后面，因此q的指针域的值将发生变化，为了链表b正常遍历，应先保存q的后继。插入过程中，由于已经保存了q的后继，因此可以先修改q的指向，再修改p的指向，最后将p移动到原插入节点q的后继。]
10.D　[本题考查多条链表的遍历。3条链表构建在数组a中，头指针存储在数组head中，需遍历头指针数组，从而来遍历3条链表。(1)处为当前节点赋值为头指针head[i]，变量s存储所有节点游览总时间。(2)(3)遍历链表，并统计各个节点游览时间和，由于当前节点已经计入总时间，因此先要跳转到下一点，将下一节点的时间加入到总时间，注意遍历结束的条件是当遍历到尾节点时，终止遍历。]
11.D　[本题考查循环链表的操作，根据p＝q＝6可以得出链表为S－h－e－n－g－Z－h－o－u，k的范围为[3，5，7，9]，p和q相差k个节点，p为1时输出a[q][0]，即p指向g，q的可能有h、u、g。]
12.C　[题图a按绝对值升序排序数据，链表中数据依次为－11，14，16，17，
－18，要求改变链接关系，使链表各节点按数据区域中的数值由小到大排列。若链表中只有1个节点，其值无论是正数还是负数，均是最小的数。同时他既是头节点h，也是尾节点t。因此变量p从链表第2个节点开始遍历各个节点，若遍历到负数，则该数绝对值越大，其值就越小，需将该节点从原链表中删除，并移动到头节点的前面，进行的操作是将该前节点p指向原头节点h，同时修改当前位置为头指针。若为正数，将该节点链接到尾节点t的后面。]
13.D　[本题考查链表的插入。在有序链表中插入一个节点x，x 的范围在6到50之间，故只需要考虑中间插入或者尾插，q 指向的就是小于 x 的最大节点，让插入的节点 x 指向 p 节点的后继节点 q，语句 data[p][1]＝len(data)－1实现让p节点指向新插入的节点 x。]
14.(1)10　(2)①[n，0]　②lst[p][1]＝lst[out][1]
解析　(1)依次出队的序号为3，6，9，12，4，8，1，7，2，11，5，最后留下10号。
(2)①循环队列的特点是队尾指向队首，因此最后一个学生的编号为n，指针指向0。 ②节点p从最后一个节点开始，range(1，m)循环了m－1次，因此向后遍历了m－1个节点，下一个节点lst[p][1]就是要删除的节点，因此将当前节点的指针指向下一节点的后继，就删除了下一节点。
15.(1)2　(2)①k＝ord(d[0])－ord(″a″)　②q！＝－1 and d>data[q][0]　③info[k]＝i　(3)data[p][1]
解析　本题考查链表的构建、遍历和节点的插入。
(1)采用链表方式存储字母，首字母相同时按升序排序。单词bit的下一个单词为byte，因此其指针区域值为索引2。(2)①将单词d首字母转换为字母表中对应数字，info[0]表示字母 a 开头的最小单词，因此k为字母a－z对应0－25的索引号。②遍历data链表，找到单词d位置。当前节点q从头节点开始，当q值不为－1，且满足d比当前节点数据区域值大。(3)返回单词key对应的中文。每个元素包含英文单词和中文翻译。

展开更多......

收起↑