资源简介

专题12　链　表
知识点一　链表的遍历
1.在一个包含n(n>1)个节点的单链表上，设有头和尾两个指针，下列操作需要遍历多个节点的是(　　)
A.删除该链表中的第一个节点
B.删除该链表中的最后一个节点
C.在该链表第一个节点前插入一个新节点
D.在该链表最后一个节点后插入一个新节点
2.下列关于单向链表的说法正确的是(　　)
A.必定有头指针和尾指针
B.每个节点都有一个后继节点
C.删除一个节点，需要修改两个指针
D.查找任一节点的算法时间复杂度为O(n)
3.链表不具备的特点是(　　)
A.所需存储空间与存储元素个数成正比
B.插入、删除操作不需要移动元素
C.无须事先估计存储空间的大小
D.可随机访问任何一个元素
4.王老师用链表模拟某次比赛中运动员的出场次序，运动员号码存储如下：a＝[[″e56″，4]，[″134″，－1]，[″215″，5]，[″098″，0]，[″144″，2]，[″024″，1]]。假设head＝3，小明同学的号码是“215”，则他的出场次序是(　　)
A.2 B.4
C.5 D.6
5.使用列表模拟单链表，其存储结构如图所示，遍历该链表，将访问到的节点的数据域的字符依次连接，得到字符串‘LOVE’，则指针域中的索引值依次为(　　)
A.0 1 2 3 B.3 1 0 2
C.2 0 －1 1 D.2 0 1 －1
6.某Python程序如下：
head＝4
a＝[[2，2]，[5，3]，[3，1]，[6，－1]，[1，0]]
p＝head
while a[p][1]！＝－1：
print(a[p][0]，end＝″→″)
p＝a[p][1]
程序运行后，输出的结果是(　　)
A.1→2→3→5 B.1→2→3→5→
C.1→2→3→5→6 D.1→2→3→5→6→
7.有如下Python程序段：
a＝[]
h＝－1
for i in range(4)：
t＝int(input())
a.append([t，h])　#为列表 a 添加一个新元素
h＋＝1
while a[h][1]！＝－1：
print(a[h][0]，end＝″→″)
h＝a[h][1]
执行该程序段，依次输入 1、2、3、4 之后，输出的是(　　)
A.″1→2→3→4→″ B.″1→2→3→″
C.″4→3→2→1→″ D.″4→3→2→″
8.某超市举办特卖活动，限定对n种商品进行打折大优惠，顾客可通过一体机输入所选商品的条形码信息，查询哪些商品能参加本次特卖。将n种商品的条形码信息存数组a；将顾客所选商品信息存数组b，其中b[i][0]表示某种商品的条形码信息，b[i][1]表示该种商品的名称。查询过程的Python程序部分代码如下：
p＝len(b)
i＝0
while ifor j in range(n)：
if b[i][0]＝＝a[j]：
　　　 　print(b[i][1])
i＝i＋1
以下说法不正确的是(　　)
A.该程序采用了枚举算法
B.p值越大，程序运行时间越长
C.n值的大小与该程序的算法效率无关
D.将原用数组存储的数据改用链表存储，会占用更多存储单元
9.有如下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
10.某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]
11.采用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
12.通过以下Python程序段，将原链表转换为逆序链表。如原链表为'A'→'B'→'C'，转换为逆序链表后，'C'→'B'→'A'。
L＝[['尚书'，4]，['春秋'，－1]，['诗经'，0]，['周易'，1]，['礼记'，3]]
head＝2　#head为原链表头指针
q＝－1
p＝head
while p ！＝－1：
tmp＝L[p][1]
head＝q
程序段中方框处可选的语句是：①p＝tmp　②q＝p　③L[p][1]＝q
为实现上述功能，方框处语句依次是(　　)
A.③①② B.③②①
C.①③② D.①②③
知识点二　链表节点的删除
1.使用Python程序在链表a中删除一个数据data，代码如下：
import random
a＝[[87，1]，[93，3]，[97，5]，[95，2]，[80，0]，[98，－1]]
head＝4
x＝random.randint(0，len(a)－1) #randint(a，b)返回[a，b]区间内的一个随机整数
data＝①________
q＝head
while q！＝－1：
if ②________：
if q＝＝head：
　　 head＝a[q][1]
else：
　　　 　 a[p][1]＝a[q][1]
break
else：
③________
q＝a[q][1]
则划线处的代码为(　　)
A.①a[0][x]　②data＝＝a[q][0]　③p＝q
B.①a[0][x]　②data！＝a[q][0]　③p＝head
C.①a[x][0]　②data＝＝a[q][0]　③p＝q
D.①a[x][0]　②data！＝a[q][0]　③q＝head
2.有下列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
3.现用链表1b存储了一批会员信息，链表每个节点中的数据依次为会员名、手机号、会员积分和节点指针，数据存储形式如[[“张三”，“13282825678”，280，1]，[“小明”，“13256787678”，500，3]，...]。现要实现删除某个手机号的会员节点，已知链表头指针head与要删除会员手机号phone，实现删除节点的代码如下：
p＝head
q＝p
while p！＝－1：
if b[p][1]＝＝phone：
if p＝＝head：
　　　　 ①________
else：
　　　　 ②________
q＝p
③________
划线处的代码由以下代码组成：
①head＝1b[p][3]　②p＝1b[p][3]　③1b[p][3]＝1b[q][3]　④1b[q][3]＝1b[p][3]下列选项中顺序正确的是(　　)
A.①③② B.②④①
C.①④② D.③④②
4.有如下程序段：
people＝[[1，1]，[2，2]，[3，3]，[4，4]，[5，5]，[6，0]]
k＝int(input())
n＝len(people)
q＝head＝0
i＝1
while n>1：
i＋＝1
if i＝＝k：
p＝people[q][1]
people[q][1]＝people[p][1]
if p＝＝head：
　　　 　head＝people[q][1]
i＝1
n－＝1
q＝people[q][1]
print(people[head][0])
该程序段运行后，若输入 2，则输出的结果为(　　)
A.3 B.5
C.6 D.2
5.下列Python程序段的功能是在链表link1中删除数据为key的所有节点，link1链表中的每个节点由一个数据域和一个指针域组成。
#建立链表link1，代码略
key＝int(input(″输入要删除的数据：″))
head＝0
while link1[head][0]＝＝key and head！＝－1：
head＝link1[head][1]
p＝q＝head
if head＝＝－1：
print(″全部数据删除″)
else：
q＝link1[q][1]
while ①________：
if link1[q][0]＝＝key：
　　　 　②________
else：
　　 　　p＝link1[p][1]
q＝link1[q][1]
则划线①②处的代码分别为(　　)
A.①link1[q][1]！＝－1 ②link1[p][1]＝link1[q][1]
B.①link1[q][1]！＝－1 ②link1[q][1]＝link1[p][1]
C.①q！＝－1 ②link1[q][1]＝link1[p][1]
D.①q！＝－1 ②link1[p][1]＝link1[q][1]
6.“抢单”是外卖骑手的日常，当外卖平台上一个新的订单出现时，骑手需要在短时间内考虑是否抢单。平台根据骑手的实际信息，给出是否抢单的建议，若建议抢单则给出到达各个取送点的顺序。
平台判断是否抢单的算法设计如下：
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.在升序链表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)
2.将链表中的奇数节点和偶数节点分别排在一起，奇数节点和偶数节点的相对顺序不变。如原始链表为，新链表为。部分程序如下：
#读入链表，存储在列表a中，head存储链表的头节点
odd＝head
even＝a[odd][1]
tmp＝even
while a[odd][1]！＝－1 and a[even][1]！＝－1：
a[odd][1]＝tmp
上述程序段中方框处可选的语句为：
①odd＝a[odd][1]　②even＝a[even][1]　③a[odd][1]＝a[even][1]　④a[even][1]＝a[odd][1]则方框处语句依次为(　　)
A.①③②④ B.①②③④
C.③②④① D.③①④②
3.有如下Python程序段：
n＝int(input(″输入一个数：″))
a＝[]；head＝－1
while n>0：
r＝1－n%2
n//＝2
a.append([r，head])
head＝len(a)－1
p＝head
while p！＝－1：
print(a[p][0]，end＝″″)
p＝a[p][1]
运行上述程序段后，如果输入11，则输出结果是(　　)
A.1101 B.1011
C.0010 D.0100
4.已知链表结构a[i][0]表示元素，a[i][1]表示下一个元素的下标，head表示头元素，在已知有序的链表a中插入数值pb(pb>0)。代码如下。
a＝[[0，1]，[3，2]，[5，3]，[6，－1]]
head＝0
p＝4
tmp＝head
while a[tmp][1]！＝－1 and ①________：
tmp＝a[tmp][1]
a.append([p，②________ ])
a[tmp][1]＝len(a)－1
请在划线处依次填上合适代码(　　)
①a[tmp][0]A.①③ B.①④
C.②③ D.②④
5.找出序列中的最大数，并将其放到序列的最后面。实现上述功能的代码如下：
#链表a中存储了序列数据，head为其头指针，代码略
pre＝p＝head
maxpre＝maxp＝head
while p！＝－1：
if a[p][0]>a[maxp][0]：
maxp＝p；maxpre＝pre
pre＝p
p＝a[p][1]
if maxp＝＝head：
head＝a[head][1]
elif maxp！＝pre：
①________
a[pre][1]＝maxp
②________
#遍历输出链表 a
划线处的代码应为(　　)
A.①a[maxp][1]＝a[maxpre][1] ②a[maxp][1]＝a[p][1]
B.①a[maxp][1]＝a[maxpre][1] ②a[maxp][1]＝p
C.①a[maxpre][1]＝a[maxp][1] ②a[maxp][1]＝a[p][1]
D.①a[maxpre][1]＝a[maxp][1] ②a[maxp][1]＝p
6.有如下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]]
7.小王在某政府接待窗口工作，该单位的共有ABCDEF六个窗口，民众在具体窗口办事，都会取到一个编号如A001(窗口编号＋三位数字)。当民众完成一个办事后，都会按“确认”键报送给小王。小王的工作是每间隔30分钟，公布一次各窗口累计处理事务单，统计结果按照窗口序号及编号升序输出。如：某30分钟内，小王接收到一批数据：″A001″，″A002″，″B001″，″B002″，″D001″，″C003″，″C002″。现小王采用链表方式将这批数据插入。程序结果运行如下：
具体Python程序代码如下，请在划线处填入合适的代码。
(1)实现对链表a按序输出功能
def output(h，a)：
________
while p！＝－1：
print(a[p][0]，end＝″″)
p＝a[p][1]
(2)实现对列表b进行排序整理
def sort_lst(b)：
for i in range(len(b)－1)：
for j in range(1，len(b)－i)：
　　　　 if________：
　　　　　　 b[j]，b[j－1]＝b[j－1]，b[j]
return b
(3)实现将列表b中的数据有序插入到a链表中，并保持有序性
def insert_lst(a，head，b)：
p＝－1
for i in b：
a.append([i，－1])
n＝len(a)－1
if a[head][0]>i：
　　　 　a[n][1]＝head
　　　 　head＝n
①________
p＝q
q＝a[p][1]
while ②________：
　　　　 p＝q
　　　　q＝a[p][1]
③________
a[p][1]＝n
q＝n
return head
lst1＝[[″F001″，－1]，[″B003″，3]，[″E001″，0]，[″C001″，2]]　#已有数据
lst2＝[″A001″，″A002″，″B001″，″B002″，″D001″，″C003″，″C002″]　#新接收数据
lst2＝sort_lst(lst2)
head＝1
head＝insert_lst(lst1，head，lst2)
print(″各窗口累计处理事务单：″)
output(head，lst1)　#输出整理后的有序的链表
8.某工厂安排了若干条生产计划，数据存储在Excel文件“task.x1sx”中，数据格式如图a所示，数据以链表形式存储，现要对生产计划进行合理性检查。
检查结果分为如下三种情况(以完成的任务数m＝5为例说明)：
①安排合理：完成的任务数大于等于m，且执行过程中无重复任务。例如：计划1完成任务的顺序为：任务0→任务6→任务4→任务1→任务5→结束(－1)，共安排了5个任务。
②任务不足：完成的任务数小于m。例如：计划2完成任务的顺序为：任务6→任务2→任务0→任务1→结束(－1)，只安排了4个任务，出错任务为任务1。
③任务重复：任务安装中存在重复任务。例如：计划3完成任务的顺序为：任务7→任务3→任务5→任务1→任务0→任务3→结束，其中任务3重复，出错任务为任务0。
(1)根据题意，图a中计划4的检查结果为________(单选，填字母：A.安排合理/B.任务不足/C.任务重复)。
(2)主程序如下，请在划线处填入合适代码。
import pandas as pd
m＝int(input('请输入完成的最少任务数：'))
df＝pd.read_excel('task.xlsx')
name＝list(df.columns[2：])
plan＝list(df.计划号)
task＝list(df.values)
#task中保存df中的数据，不含标题。格式如图b所示
for i in range(len(task))：
head＝task[i][1]
①________
stat，k＝check_up(link，head)
if stat＝＝2：
print(plan[i]，'：安排合理，共完成'，k，'项任务')
elif ②________：
print(plan[i]，'：任务重复，出错任务为'，name[k])
else：
print(plan[i]，'：任务不足，出错任务为'，name[k])
(3)函数 check_up 的功能是用于检查一条生产计划是否合理，并返回检查结果，请在划线处填入合适代码。
def check_up(link，head)：
cnt＝1
p＝link[head]
pre＝p
①________
while p ！＝－1 and p not in finished：
finished.append(p)
pre＝p
②________
cnt＋＝1
if p＝＝－1：
if cnt　　　 　return 1，pre
else：
　　 　　return 2，cnt
elif p in finished：
return 0，pre
专题12　链　表
知识点一
1.B　[B选项删除最后一个节点需修改最后一个节点前驱的指针区域值，因此需遍历多个节点找到其前驱。]
2.D　[本题考查链表相关知识。A选项单向链表必定有头指针，不一定要有尾指针。B选项尾结点没有后继节点。C选项单项链表删除一个节点，只需修改删除节点的前驱节点的后继指针即可。D选项链表的访问比较低效，每次遍历都需要从head头结点开始，故算法时间复杂度为O(n)。]
3.D　[本题考查链表相关知识点。链表的访问必须从头节点开始。通过指针依次访问，不能随机访问任何一个元素。]
4.B　[本题考查链表的遍历。head值为3，[″098″，0]为头节点，接着是[″e56″，4][″144″，2]，[″215″，5]，[″024″，1]，[″134″，－1]。]
5.C　[本题考查链表的构建和遍历。L的后继节点为0，因此其指针区域值为1；O的后续为V，指针区域值为0；V的后续为E，指针区域值为2；E为尾节点，因此指针区域值为－1。]
6.B　[没有输出尾结点，输出前面4个节点的数据域，并以″→″结束，故答案为1→2→3→5→，选B。]
7.D　[本题考查链表元素插入和遍历。语句a.append([t，h])表示增加一个元素并且该元素的后继是原头节点，因此属于头插法产生链表，链表的值依次为4、3、2、1。循环结束条件为a[h][1]！＝－1，尾节点的标志是其指针区域值为－1，即当遍历到尾节点时，不输出该节点，马上结束循环。]
8.C　[程序段遍历数组a，查找参加本次特卖的商品，采用了枚举算法；p越大，循环需要执行的次数越多，则程序运行时间越长；n的值越大，程序运行时间也越长，则时间复杂度越大，即算法效率越低；若采用链表存储，除了要存储数据本身，还要存储后继节点的位置，会占用更多的存储单元。]
9.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。]
10.B　[本题考查链表应用。data是一个链表，t指针从链表的第二个节点开始遍历，1a指针是t节点的前驱，t节点减去前驱节点la的值小于key时，c计数，c的初值为0，计数到3时遍历结束，也就是整个过程计数3次就结束，执行程序后t的值为6，也就是遍历到最后一个节点时程序才结束。]
11.A　[本题考查链表的基本操作。p的初值为a[head][1]，即head的后继，进入循环后，语句p＝a[p][1]的功能是向后遍历，让该节点指向头节点，p再向后遍历。A后继的后继是C，当前头节点为C，C指向A；C后继的后继是E，当前头节点为E，E指向C。]
12.B　[本题考查链表的遍历。p为当前节点，从头节点开始遍历链表，将遍历的新节点以头插法的形式重新构建链表。q为新链表的头节点，保存当前节点p的后续索引为tmp，先让新链表的头节点指向新链表的头节点，再将头指针指向p，p从原后续继续遍历原链表。]
知识点二
1.C　[本题考查遍历链表及删除节点操作。①x是链表中一个节点位置，从链表中被删除的数据a[x][0]。②判断当前节点a[q]的值是否是要删除的数据data。③遍历链表，如果当前节点是要删除的数据，且该节点是头节点，需要更新头指针head的值，若不是头节点，需让前驱节点p指向当前节点q的后继节点。若当前节点的数据域不是data，则将当前节点p更新为前驱节点q，并继续检查下一个节点。]
2.D　[本题考查链表的基本操作。如果链表头节点值为1，直接删除头节点，否则遍历链表，语句a[pre][1]＝a[p][1]的作用让节点p的前驱指向他的后继，即删除p节点。程序的功能是删除元素值为1的节点。]
3.C　[本题考查链表元素的删除操作。该程序的算法思想为：遍历链表，查找待删除节点，找到后根据该节点为第一个节点或中间节点执行不同的删除操作。]
4.B　[本题考查循环链表的算法实现。每遍历一次，i增加1，实现计数。第1次删除节点2，第2次删除节点4，第3、4、5分别删除节点6、3、1，链表中只剩下节点5。]
5.D　[本题考查链表节点删除的算法实现。先判断当前节点的数据域是否为key，如果是，则删除当前节点，即将p节点的指针域指向q节点的指针域，如果不是，则将p指向下一个节点，q也指向下一个节点。最后，程序通过while循环遍历链表并输出每个节点的数据域。]
6.(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。
知识点三
1.B　[本题考查链表中数据查找和插入操作。p、q是二个前后相邻的节点。根据data>a[q][0]，可以推测出①为q！＝－1。循环结束后，应该在p节点之后插入节点，所以②处代码是：a[p][1]＝len(a)。]
2.D　[本题考查链表的插入。先分别获取奇数节点连接而成的链表和偶数节点连接而成的链表；再连接两个链表得到新链表。]
3.D　[本题考查链表的插入和进制转换。程序的功能是十进制数转成二进制数，并把结果取反。代码a.append([r，head])；head＝len(a)－1的功能利用头插法生成链表。]
4.D　[先遍历链表，找到pb的位置，tmp指向头指针，pb>0表示不可能是头指针，因此要和他下一个节点的值a[a[tmp][1]][0]进行比较。插入节点指向tmp的后继。]
5.D　[本题考查链表。先查找序列中最大数的位置maxp和该节点的前驱节点maxpre，pre为最后一个节点位置。再删除最大数节点，分两种情况，最大数节点为第一个节点或其他位置节点。如果是其他位置节点，需将该最大数节点的前驱节点指针区域指向该最大数节点的后继节点位置，即a[maxpre][1]＝a[maxp][1]。最后将最大数节点插入链尾，原最后一个节点指针区域需指向最大数节点，最大数节点为新的最后一个节点，其指针区域为－1，即p，所以②a[maxp][1]＝p。]
6.D　[本题考查链表的插入。在有序链表中插入一个节点x，x的范围在6到50之间，故只需要考虑中间插入或者尾插，q指向的就是小于x的最大节点，让插入的节点x指向p节点的后继节点q，语句data[p][1]＝len(data)－1实现让p节点指向新插入的节点x。]
7.(1)p＝h　(2)b[j]解析　本题考查冒泡排序和链表节点遍历、插入等操作。(1)对当前节点q赋初值。链表需从头节点开始依次访问，需对其赋初值。(2)确定冒泡排序的条件。由语句b[j]，b[j－1]＝b[j－1]，b[j]可知比较对象为b[j]和b[j－1]，从程序的输出结果来看，实现升序排列，因此条件为后面的数据小于或小于等于前面的数据。(3)①更新当前q的值。当条件a[head][0]>i成立时，将在头节点前面插入数据i，因此需更新当前节点q的位置。②确定查找的条件。当前节点q的值与数据i进行比较，当前节点值a[q][0]大于i时结束查找，将i插入到q的前面，但同时要注意当前节点q的界限。③新增节点链入链表中。变量n的值为len(a)－1，即新增加节点的位置，该节点的后继是当前节点q，因此需对指针区域进行赋值。
8.(1)C　(2)①link＝task[i][2：]　②stat＝＝0 (3)①finished＝[head]　②p＝link[p]
解析　(1)根据题意以及链表访问的顺序，任务4依次是：任务2→任务6→任务5→任务0→任务3→任务2，此时发现任务2重复，选C。(2)①根据下面一条语句，这里应该是对变量link赋值。再查看函数check_up中与link相关的语句p＝link[head]，结合图a，对应的链表应该是task[i][2：]，所以这里对应的代码是：link＝task[i][2：]。②根据函数相应的代码，stat可能获得的值1、2、0，分别对应任务不足、安排合理、任务重复。所以这里的条件是：stat＝＝0。(3)①对finished赋值，根据语句finished.append(p)和p not in finished，finished是一个列表，主要用于判断链表节点是否重复访问了。由于循环代码是利用指针变量p遍历链表依次访问节点，且p＝link[head]，是从第二个节点开始的，所以这里列表finished应该包含第一个节点。相应代码：finished＝[head]。②依次访问链表的每个节点，代码：p＝link[p]。

展开更多......

收起↑