資源簡介

專題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]?。剑?：
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?。?：
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?。剑?：
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 ?。剑?：
tmp＝L[p][1]
head＝q
程序段中方框處可選的語句是：①p＝tmp?、趒＝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]?、赿ata＝＝a[q][0]?、踦＝q
B.①a[0][x]　②data！＝a[q][0]　③p＝head
C.①a[x][0]?、赿ata＝＝a[q][0]?、踦＝q
D.①a[x][0]?、赿ata?。絘[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]，...]?，F要實現刪除某個手機號的會員節點，已知鏈表頭指針head與要刪除會員手機號phone，實現刪除節點的代碼如下：
p＝head
q＝p
while p?。剑?：
if b[p][1]＝＝phone：
if p＝＝head：
　　　　 ①________
else：
　　　　 ②________
q＝p
③________
劃線處的代碼由以下代碼組成：
①head＝1b[p][3]?、趐＝1b[p][3]?、?b[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?。剑?：
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]?。剑? ②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?。剑?：
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?。剑?②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]?。剑? and a[even][1]?。剑?：
a[odd][1]＝tmp
上述程序段中方框處可選的語句為：
①odd＝a[odd][1]?、趀ven＝a[even][1]?、踑[odd][1]＝a[even][1]?、躠[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?。剑?：
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?。絧re：
①________
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″?，F小王采用鏈表方式將這批數據插入。程序結果運行如下：
具體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 ?。剑? 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，即當遍歷到尾節點時，不輸出該節點，馬上結束循環。]
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：]?、趕tat＝＝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]。

展開更多......

收起↑