資源簡介

專題17　鏈　表
學習目標　1.掌握鏈表的概念和鏈表的遍歷方法；
2.掌握鏈表頭節點的插入和刪除操作；
3.掌握鏈表除頭節點外的其他節點的插入和刪除操作.
鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表每個節點的結構是相同的，由數據區域和指針區域組成，其中指針區域指向下一個節點的索引。鏈表的訪問必須從頭節點開始，因此頭指針是鏈表必不可少的元素。
(2024年1月浙江省選考)使用列表d模擬鏈表結構(節點數大于0)，每個節點包含數據區域和指針區域，h為頭指針。鏈表中各節點已按數據區域中數值的絕對值由小到大排列，如圖a所示。現要修改該鏈表各節點的鏈接關系，使鏈表各節點按數據區域中的數值由小到大排列，結果如圖b所示。實現該功能的程序段如下，方框中應填入的正確代碼為(　　)
t＝h
p＝d[h][1]
while p ！＝ －1 ：
　 q＝d[p][1]
　　
　　p＝q
d[t][1]＝－1
重難點1　鏈表的遍歷
鏈表的遍歷必須從頭節點開始，每個節點包含數據區域和指針區域，數據區域可能有多個值，指針區域值往往在節點最后一個位置。若當前q指向頭指針head，那么a[q]是整個節點的值，a[q][0]是數據區域的值，a[q][1]是下一節點的索引，通過語句q＝a[q][1]，實現指針向后移動。
例題 某公交路線的站點名稱、經度、緯度和下一個站點序號(經緯度已轉換為平面坐標數據)存儲在數組 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.①③②
變式 使用鏈表結構模擬某景區游玩路線，鏈表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.②④③
重難點2　鏈表節點的刪除
在數組中刪除某個節點，往往需把該節點后面的值往前移，時間復雜度為線性階O(n)。鏈表節點的刪除分為頭節點的刪除和其他節點的刪除，頭節點的刪除只要移動頭指針到下一節點，即head＝a[head][1]即可，其他節點的刪除，只要修改該節點的前驅節點的指針區域值為該節點的后繼節點索引即可，時間復雜度為常量階O(1)。
例題 使用列表a模擬鏈表結構(節點數大于0)，每個節點包含數據區域和指針區域，head為頭指針，鏈表中各節點已按數據區域中數值的由小到大排列。現要修改該鏈表各節點的鏈接關系，刪除鏈表中數據區域數值相同的節點，使得鏈表各節點的數據區域值不重復。
實現該功能的程序段如下，方框中應填入的代碼段可行的是(　　)
p ＝ head
q ＝ a[p][1]
while q！＝－1：
　　
a[p][1]＝－1
A .if a[p][0]！＝a[q][0]:
a[p][1]＝q
p ＝ q
else：
p ＝ q
q＝a[q][1]
B .if [p][0]！＝a[q][0]：
a[p][1]＝q
p ＝ q
q＝a[q][1]
C .if a[p][0]＝＝a[q][0]：
p ＝ q
q＝a[q][1]
else：
a[p][1]＝q
p ＝ q
q＝a[q][1]
D .if [p][0]＝＝a[q][0]：
q＝a[q][1]
else：
p ＝ q
a[p][1]＝q
變式 使用列表模擬單向鏈表，鏈表中p節點的a[p][0]存儲數據，a[p][1]存儲其后繼節點的指針。編寫Python程序刪除鏈表中所有偶數項(頭節點為該鏈表的第1項)，部分代碼如下：
p＝head
while p！＝－1：
　　q＝a[p][1]
　　if ①________：
　 a[p][1]＝a[q][1]
　　②________
上述程序段劃線處可選語句為(　　)
A.①q！＝－1　　　 ②q＝a[q][1]
B.①q！＝－1　　　 ②p＝a[p][1]
C.①a[q][1]！＝－1　②q＝a[q][1]
D.①a[q][1]！＝－1　②p＝a[p][1]
例題 使用列表da和db模擬2個鏈表結構(節點數均大于0)，每個節點包含數據區域和指針區域，ha和hb分別為2個鏈表的頭指針。鏈表中各節點已按數據區域中數值由小到大排列，且鏈表da頭節點值小于鏈表db頭節點值。現要將鏈表db中數據合并到鏈表da中，且保持升序排列。實現該功能的程序段如下，方框中應填入的正確代碼為(　　)
t＝ha
while hb！＝－1：
　　q＝da[t][1]
　　
A.if q＝＝－1 or da[q][0]>db[hb][0]：
　　 da.append([db[hb][0]，q])
　　 da[t][1]＝len(da)－1
　　 hb＝db[hb][1]
t＝da[t][1]
B.if q＝＝－1 or da[q][0]>db[hb][0]：
　　 da.append([db[hb][0]，q])
　　 da[t][1]＝len(da)－1
　　 hb＝db[hb][1]
　　 t＝da[t][1]
C.if q＝＝－1 or da[q][0]>db[hb][0]：
　　 da.append([db[hb][0]，q])
　　 da[t][1]＝len(da)－1
　　 hb＝db[hb][1]
t＝q
D.if q＝＝－1 or da[q][0]>db[hb][0]：
　　 da.append([db[hb][0]，q])
　　 da[t][1]＝len(da)－1
hb＝db[hb][1]
t＝da[q][1]
變式 列表a存儲了兩個升序鏈表的節點，每個節點包含數據區域和指針區域，頭指針分別為ha、hb，且a[ha][0]q ＝ h ＝ ha
p ＝ a[ha][1]
k ＝ hb
while p ！＝ －1 and k ！＝ －1：
　 if a[p][0] <＝ a[k][0]：
　 q ＝ p
　 p ＝ a[q][1]
else：
　
if k！＝－1：
　 a[q][1] ＝ k
方框中應填入的正確代碼為(　　)
重難點4　循環鏈表及鏈表的簡單應用
循環鏈表是一種特殊的鏈式存儲結構，其中最后一個節點的指針指向頭節點，形成一個環。
例1 報數游戲。已知班上有n名學生(用編號1，2，3，……，n分別表示)，學生按照編號由小到大順時針圍成一個圓圈，從編號為1的學生開始順時針報數，報到m的同學出列；下一名同學又從1開始報數，報數為m的同學繼續出列；以此規律重復下去，直到剩下最后一位同學為止。
(1)當n＝6，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 ②________：　 #從1至m－1依次報數
　 p＝lst[p][1]
　　out＝lst[p][1]
　　③________
　　n＝n－1
print(″最后留下的同學的編號是：″，lst[p][0])
變式1 有如下Python程序段：
a＝[4，5，3]
d＝[[3，″A″，2]，[6，″B″，0]，[3，″C″，1]]
q＝head＝1
t，n＝2，3
ans＝″″
i＝0
while n>0 and i　 if d[q][0]>a[i]：
　　　d[q][0]－＝a[i]
　　　t＝d[t][2]
　　　i＋＝1
　 else：
　　　a[i]－＝d[q][0]
　　　d[t][2]＝d[q][2]
　　　n－＝1
　　　ans＋＝d[q][1]
　 q＝d[q][2]
執行該程序段后，ans的值是(　　)
A.″ABC″ B.″ACB″ C.″BAC″ D.″CBA″
例2 某編程興趣小組設計了一個點歌模擬程序，功能如下：
運行程序后，從鍵盤輸入“A”，則顯示已點的歌曲列表(歌單)；輸入“B”則可以自行輸入歌曲并添加到歌單以完成點歌；輸入“C”則可以將指定的歌曲置頂等待播放；輸入“D” 則播放當前第一首歌曲，并將該歌曲從列表中刪除；輸入“E”則關閉程序并退出。程序運行界面如圖所示。
請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A God Is a Girl　十年　年少有為　七里香　淡季動物園 請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：B 請輸入歌曲：蘭亭序 請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：B 請輸入歌曲：想自由 請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A God Is a Girl　十年　年少有為　七里香　淡季動物園　蘭亭序　想自由 請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：C 請輸入歌曲：七里香 請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A 七里香　God Is a Girl　十年　年少有為　淡季動物園　蘭亭序　想自由 請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：C 請輸入歌曲；想自由 請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A 想自由　七里香　God Is a Girl　十年　年少有為　淡季動物園　蘭亭序 請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：D 請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A 七里香　God Is a Girl　十年　年少有為　淡季動物園　蘭亭序 請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：E
Python代碼如下所示，請在劃線處填入合適的代碼。
data＝[[″十年″，4], [″淡季動物園″，－1], [″God Is a Girl″，0], [″七里香″，1], [″年少有為″，3]]
head＝2
tail＝1
while True：
　 cmd ＝input(″請輸入指令 A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：″)
　　if cmd＝＝″A″：
　 cur＝head
　 while cur！＝－1:
　　　　　print(data[cur][0]，end＝″″)
　　　　　cur＝data[cur][1]
　 print()
　　elif cmd＝＝″B″：
　 song＝input(″請輸入歌曲：″)
　 data.append([song，－1])
　 if head＝＝－1：
　　　　　head＝tail＝len(data)－1
　 else：
　　　　　①________
　　　　　tail＝len(data)－1
　　elif cmd＝＝″C″：
　 song＝input(″請輸入歌曲：″)
　 cur＝head
　 while cur！＝－1 and data[cur][0]！＝song:
　　　　　pre＝cur
　　　　　cur＝data[cur][1]
　if cur！＝－1 and cur！＝head：
　　　②________
　　　data[cur][1]＝head
　　　head＝cur
　　　if cur＝＝tail：
　　　 ③________
elif cmd＝＝″D″：
　if head＝＝tail:
　　 head＝tail＝－1
　else：
　　　④________
elif cmd＝＝″E″：
　break
變式2 已知一個有7個節點的單向鏈表，設有頭指針head和尾指針tail，如圖所示，下列操作需要遍歷多個節點的是(　　)
A.刪除該鏈表中的最后一個節點
B.刪除該鏈表中的第一個節點
C.在該鏈表第一個節點前插入一個新節點
D.在該鏈表最后一個節點后插入一個新節點
重難點1　鏈表的遍歷
1.下列關于單向鏈表的說法正確的是(　　)
A.必定有頭指針和尾指針
B.每個節點都有一個后繼節點
C.刪除一個節點，需要修改兩個指針
D.查找任一節點的算法時間復雜度為O(n)
2.使用列表模擬單鏈表，其存儲結構如圖所示，遍歷該鏈表，將訪問到的節點的數據域的字符依次連接，得到字符串‘LOVE’，則指針域中的索引值依次為(　　)
A.0 1 2 3 B.3 1 0 2
C.2 0 －1 1 D.2 0 1 －1
3.使用Python的二維列表來模擬單向鏈表，如下代碼創建一個擁有4個節點的鏈表a
a＝[[″cat″，1]，[″dog″，2]，[″pig″，－1]，[″rabbit″，0]]
head＝3
依次輸出各節點數據域的值，內容為(　　)
A.″cat″，″dog″，″pig″，″rabbit″
B.″pig″，″rabbit″，″cat″，″dog″
C.″pig″，″dog″，″cat″，″rabbit″
D.″rabbit″，″cat″，″dog″，″pig″
4.實現在鏈表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.②④
5.使用列表a模擬鏈表結構(節點數大于0)，每個節點包含數據區域和指針區域，head為頭指針。鏈表中各節點已按數據區域中的數值由小到大排列。現要計算鏈表中的中位數，處在鏈表最中間位置的數叫做中位數。說明：當數據元素為奇數個時中位數為最中間的數，偶數個時中位數為最中間兩個數的平均數。實現功能的Python程序如下，劃線處應填入的正確代碼為(　　)
fast＝slow＝head
while fast！＝－1 and ①________：
　 p＝slow
　 slow＝a[slow][1]
　 fast＝ a[a[fast][1]][1]
if ②________：
　 mid＝(a[p][0]＋a[slow][0])/2
else：
　 mid＝a[slow][0]
print(″中位數是：″， mid)
A.①slow！＝－1　　　 ②fast！＝－1
B.①a[slow][1]！＝－1 ②fast＝＝－1
C.①a[fast][1]！＝－1 ②fast！＝－1
D.①a[fast][1]！＝－1 ②fast＝＝－1
重難點2　鏈表節點的刪除
1.某單向鏈表如下圖所示，若要將數據 data3 和data4 同時從鏈表中移除，至少需要修改節點指針的數量是(　　)
A.1 B.2 C.3 D.4
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.使用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
4.用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.②①③
重難點3　鏈表節點的插入
1.小張準備去多個城市旅游，他設計的行程若采用鏈表結構表示，如圖a所示。若行程有變，需在“上海”與“成都”之間增加一站“杭州”，鏈表修改為如圖b所示，有以下可選操作：
①“上海”所在節點的next值賦為“杭州”節點的next值
②“上海”所在節點的next值賦為5
③“杭州”所在節點的next值賦為“上海”所在節點的next值
④“杭州”所在節點的next值賦為－1
鏈表更新順序正確的是(　　)
A.③① B.③② C.①④ D.②④
2.有如下Python程序：
def lnkid(n，head):
　 p＝head
　 while head ！＝－1 and ①________：
　 p＝head
　 head＝a[head][1]
　 return p
a＝[[2，2]，[5，3]，[1，－1]，[3，0]，[7，1]]
head＝4
n＝int(input())
p＝lnkid(n，head)
if n>a[head][0]：
　 a.append([n，head])
　 head＝len(a)－1
else：
　 a.append([n，a[p][1]])
　 ②________
用列表a模擬一個降序鏈表，運行程序，輸入自然數n，則鏈表增加一個新的節點，要使鏈表保持降序，則劃線①②處代碼分別為(　　)
A.①nB.①nC.①nD.①n>a[head][0] ②a[p][1]＝len(a)
3.有兩個降序序列的鏈表 a，b。現將鏈表 b 中的數據合并到鏈表 a，形成一個新的降序序列存于鏈表 a，實現數據合并的代碼段如下：
a ＝ [[98，1]，[96，2]，[95，3]，[93，4]，[90，－1]]
b ＝ [[99，1]，[97，2]，[94，3]，[93，4]，[92，－1]]
head_a ＝ head_b ＝ 0
pre ＝ p ＝ head_a；q ＝ head_b
while q！＝－1：
　 if p！＝－1 and ：
　 pre＝p
　 p＝a[p][1]
　 else：
　 a.append()
　 if p＝＝head_a：
　　　 pre＝head_a＝len(a)－1
　 else：
　　　 a[pre][1]＝
　　　 pre＝len(a)－1
　 q＝b[q][1]
上述程序段中可選填的語句為：①a[p][0]>＝ b[q][0]　②a[p][0]<＝ b[q][0]　③q　④len(a)－1　⑤[b[p][0]，q]　⑥[b[q][0]，p]
則加框處填寫的語句依次為(　　)
A.①⑥④ B.①⑤④ C.①⑥③ D.②⑥③
4.將兩個鏈表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.②③⑤
5.用鏈表模擬隊列操作(隊列長度大于1)，鏈表的每個節點包含數據區域和指針區域。指針head指向隊列的第一個元素，指針tail指向隊列的最后一個元素，如圖所示。現執行n次“出隊后立即入隊”操作，實現該功能的Python程序段如下：
k＝1
while k<＝n：
　　p＝head
　　
　　tail＝p
　　k＋＝1
上述程序段中方框處可選代碼有
①head＝que[head][1]　②que[tail][1]＝head
③que[head][1]＝－1　④que[p][1]＝－1
則方框內應填入的正確代碼順序為(　　)
A.①②③ B.①②④ C.②①③ D.②①④
重難點4　循環鏈表及鏈表的簡單應用
1.有如下程序段：
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
2.將A－K共13張黑桃撲克牌洗好后，把牌面朝下。第一張牌翻過來A，第2次將最上面第1張牌放到這疊牌的最下面，將第2張牌翻開，是黑桃2；第3次數將最上面第1、2張牌放到這疊牌的最下面，將第3張牌翻開，是黑桃3；依次類推將13張牌按從小到大的順序翻出。求這疊牌洗好后，從上到下的原始順序。
(1)程序運行結果如圖所示，結合下面代碼，當輸入撲克牌數量num為6時，撲克牌從上到下的初始順序最后輸出結果為：________。
請輸入撲克牌數量(1—13)：13 撲克牌從上到下的初始順序為： A，8，2，5，10，3，Q，J，9，4，7，6，K，
(2)實現題中所述功能的Python程序如下，請在程序中劃線處填入合適的代碼。
num ＝ int(input(″請輸入撲克牌數量(1－13)：″))
poker ＝ [[i ＋ 1，(i ＋ 1) % num　] for i in range(num)]　#創建循環鏈表
①________
cur ＝ poker[pre][1]
result ＝ []
for i in range(num)：
　 for j in ②________：
　 pre ＝ cur
　 cur ＝ poker[cur][1]
　 result.append(poker[cur][0])
　 poker[pre][1] ＝③________
　 cur ＝ poker[pre][1]
initial ＝ [0] * num
for k in range(num)：
　 initial[result[k]－1]＝④________
print(″撲克牌從上到下的初始順序為：″)
ajqk ＝ {1：″A″， 11：″J″， 12：″Q″， 13：″K″}
for m in initial：
　 if m > 10 or m ＝＝ 1：
　 print(ajqk[m], end＝″，″)
　 else：
　 print(m, end＝″，″)
重難點1　鏈表的遍歷
1.鏈表不具備的特點是(　　)
A.所需存儲空間與存儲元素個數成正比
B.插入、刪除操作不需要移動元素
C.無須事先估計存儲空間的大小
D.可隨機訪問任何一個元素
2.某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→
3.王老師用鏈表模擬某次比賽中運動員的出場次序，運動員號碼存儲如下： a＝[[″e56″，4]，[″134″，－1]，[″215″，5]，[″098″，0]，[″144″，2]，[″024″，1]]。假設head＝3，小明同學的號碼是“215”，則他的出場次序是(　　)
A.2 B.4 C.5 D.6
4.有如下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
5.利用列表模擬非循環鏈表a(可能存在已被刪除的節點)，下列程序運行完畢后，變量p表示尾節點的節點位置是(　　)
6.某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]
7.通過以下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.①②③
8.接力比賽男女生人數相等，男女隊員交替接力，實現該功能的Python程序段如下：
a＝[[″1號″，″女″]，[″2號″，″女″]，[″3號″，″男″]，[″4號″，″男″]，[″5號″，″男″]，[″6號″，″女″]，[″7號″，″女″]，[″8號″，″男″]]
print(a[0])　#輸出第一棒
pre＝0；i＝1
que＝[－1]*len(a)
head＝tail＝0
while i　 if head！＝tail：
if a[que[head]][1]！＝a[pre][1]:
　　　 print(a[que[head]])
　　　 pre＝que[head]
　　　 head＋＝1
　　①________ :
print(a[i])
pre＝i
　 else：　#性別與前一棒相同時則進入等待隊列
que[tail]＝i
tail＋＝1
　 i＋＝1
if head！＝tail：
　 print(②________)
上述程序段中劃線處應填寫的代碼是(　　)
A.①elif a[pre][1]！＝a[i][1]　②que[head])
B.①if a[pre][1]！＝a[i][1] ②que[head]
C.①elif a[pre][1]！＝a[i][1] ②a[que[head]]
D.①if a[pre][1]！＝a[i][1] ②a[que[head]]
9.將鏈表中的奇數節點和偶數節點分別排在一起，奇數節點和偶數節點的相對順序不變。如原始鏈表為，新鏈表為。部分程序如下：
#讀入鏈表，存儲在列表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.③①④②
重難點2　鏈表節點的刪除
1.由n個節點鏈接成的單鏈表如圖所示，其中head為頭指針。
使用列表link模擬該鏈表結構，每個節點包含數據域和指針域，如圖中最后一個節點可以表示為[98，－1]。現要刪除指針p所指向的節點，可以實現該操作的語句有(　　)
①link[p][1]＝－1　②link[head][1]＝q　③link[head][1]＝link[p][1]　④head＝link[p][1]
A.①② B.①③ C.②③ D.②④
2.有如下Python程序段：
a ＝ [[3，1], [2，2], [3，3], [3，4], [17，5], [2，6], [3，－1]]
p ＝ head ＝ 0
while p ！＝ －1:
　 q ＝ p
　　while q ！＝ －1:
　 t ＝ q
　 q ＝ a[q][1]
　 if q ！＝ －1 and a[q][0] ＝＝ a[p][0]：
　　　 a[t][1] ＝ a[q][1]
　　　　　 q ＝ t
　　p ＝ a[p][1]
p ＝ head
while p ！＝ －1：
　　print(a[p][0], end＝' ')
　　p ＝ a[p][1]
運行后程序的輸出結果是(　　)
A.3 2 17 B.3 2 17 2
C.3 2 17 2 3 D.17
3.有如下Python程序段：
def guess(cur)：
　 q＝cur
　 p＝a[cur][1]
　 while p！＝－1：
　　　 if a[p][0]＝＝a[cur][0]：
　　　 a[q][1]＝a[p][1]
　　　 else：
　　　 q＝p
　　　 p＝a[p][1]
a＝[[1，3]，[1，2]，[2，4]，[2，5]，[4，－1]，[3，1]]
head＝0；cur＝head
while cur！＝－1：
　　print(a[cur][0]，end＝″″)
　　if a[cur][1]！＝－1：
　　 guess(cur)
　　cur＝a[cur][1]
運行后，則輸出的結果是(　　)
A.1234 B.1122 C.11223 D.11224
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.現用鏈表lb存儲了一批會員信息，鏈表每個節點中的數據依次為會員名、手機號、會員積分和節點指針，數據存儲形式如[[“張三”，“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＝lb[p][3]　②p＝lb[p][3]　③lb[p][3]＝lb[q][3]　④lb[q][3]＝lb[p][3]
下列選項中順序正確的是(　　)
A.①③② B.②④① C.①④② D.③④②
6.使用列表 d 模擬鏈表結構(節點數大于 1)，每個節點包含數據區域(數據均為整型，范圍為 0～9)和指 針區域，h 為頭指針，如圖a所示。現要對該鏈表節點進行去重操作，只保留最后一次出現的節 點，結果如圖b所示。實現該功能的程序段如下，方框中應填入的正確代碼為(　　)
lst ＝ [0]*10
p ＝ h
while p ！＝ －1：
　　lst[d[p][0]] ＋＝ 1
　　p ＝ d[p][1]
q, p ＝ h, h
while d[p][1] ！＝ －1：
　　
　　p ＝ d[p][1]
7.使用列表d模擬鏈表結構(節點數大于0)，每個節點包含數據區域和指針區域，head為頭指針。現要刪除鏈表中數據值在[begin，end]范圍的節點，實現該功能的部分程序段如下，方框中應填入的正確代碼為：(　　)
d＝[[4，5]，[10，2]，[12，4]，[1，0]，[16，－1]，[7，1]]
head＝3
q＝head；p＝head
while p！＝－1：
　　if d[p][0]end：
　　　 q＝ p
　　　 p＝d[p][1]
　　else：
　　　
8.有如下Python程序，其功能為刪除無序鏈表(元素個數大于等于2)中的重復元素。
def dele (a, head) ：
　 pre＝head; p＝a[head][1]
　 while p！＝－1：
　　　 q＝head
　　　 flag＝False
　　　 while　(1)________：
　　　　　 if a[q][0]＝＝a[p][0]：
　　　　　 (2)________
　　　　　 p＝a[p][1]
　　　　　 flag＝True
　　　　　 break
　　　　　 q＝a[q][1]
　　　 if not flag：
　　　　　pre＝p
　　　　　p＝a[p][1]
a＝[[0，3]，[1，2]，[1，4]，[0，1]，[0，5]，[2，－1]]
dele(a, 0)
①q！＝－1　②q！＝p　③a[pre][1]＝a[p][1]　④a[pre][1]＝a[q][1]
方框中填入的正確代碼依次為(　　)
A.②④ B.②③ C.①④ D.①③
重難點3　鏈表節點的插入
1.下列Python程序的功能是：在鏈表中插入一個整數，鏈表中的數據仍保持有序。
data＝int(input(″請輸入一個整數：″))
link＝[[8，3]，[6，0]，[2，1]，[11，4]，[15，－1]]
head＝2
q＝head
if data<＝link[head][0]：
　 link.append([data，head])
　 ①________________
else：
　 while ②________：
　 p＝q
　 q＝link[q][1]
　 link.append([data，q])
　 link[p][1]＝len(link)－1
q＝head
while ③________：
　 print(link[q][0]，end＝″″)
　 q＝link[q][1]
劃線處應填入的代碼是(　　)
A.①head＝q　　②q！＝－1 and data>link[q][0] ③q！＝－1
B.①head＝q　②link[q]！＝－1 and data>link[q][0] ③link[q][1]！＝－1
C.①head＝len(link)－1　②link[q]！＝－1 and data>link[q][0]　③link[q][1]！＝－1
D.①head＝len(link)－1　②q！＝－1 and data>link[q][0]　③q！＝－1
2.有如下Python程序段：
a＝[[6，6]，[5，0]，[1，3]，[2，5]，[2，1]，[2，4]，[9，－1]]
key＝int(input())
p＝q＝head ＝2
while p！＝－1 and a[p][0]<＝key：
　 q＝p
　　p＝a[p][1]
if p＝＝head：
　　a.append([key，head] )
　　head＝len(a)－1
else：
　　a.append([key，p] )
　　a[q][1] ＝len(a)－1
print(a[－1])
程序段運行后，若輸入2，則輸出的結果是(　　)
A.[2，－1] B.[2，1]
C.[2，4] D.[2，5]
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>a[head][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.在升序鏈表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)
7.有如下Python程序段：
a＝[[7，3]，[5，0]，[2，1]，[9，－1]]
head＝2
key＝int(input(″輸入一個數字″))
p＝q＝head
while p！＝－1 and a[p][0]　 q＝p
　 p＝a[p][1]
if p＝＝head：
　 a.append([key，head])
　 head＝len(a)－1
else：
　 a.append([key，p])
　 a[q][1]＝len(a)－1
print(a[－1])
程序段運行后，若輸入2，則輸出的結果是(　　)
A.[2, －1] B.[2, 1] C.[2, 2] D.[2, 3]
8.某個正整數的每位數依次存儲在鏈表d中各節點的數據區域中。例如，正整數572存儲情況如圖a所示，h為d的頭指針。將該正整數翻倍后的計算結果(如572翻倍后的結果為1144)仍以這個鏈表存儲，最高位存儲于頭節點中，如圖b所示。實現該功能的程序段如下：
if d[h][0] > 4：
　 d.append([0，h])　#鏈表d新增一個節點
　 h ＝ len(d) － 1
p ＝ h
while p ！＝ －1：
　　d[p][0] ＝ d[p][0] * 2 % 10
　　cur ＝ d[p][1]
　　
　　p ＝ d[p][1]
方框中應填入的正確代碼為(　　)
A.if cur ！＝ －1 and d[cur][0] > 4：
　　 d[p][0] ＋＝ 1
B.if cur ！＝ －1 and d[p][0] > 4：
　　 d[cur][0]＝(d[p][0]*2＋1)∥10
C.if cur ！＝ －1 and d[cur][0] > 4：
　　 d[p][0]＋＝(d[cur][0]*2＋1)%10
D.if cur ！＝ －1 and d[p][0] > 4：
　　 d[cur][0] ＋＝ 1
9.流浪地球2演員表lnk是一個鏈表，對鏈表lnk處理成男女演員兩條鏈表。算法如下，遍歷鏈表，如果是第1位女演員則從男演員鏈表刪除該節點，如果不是第1位女演員，把該節點加入女演員鏈表的尾部，同時從男演員鏈表中刪除，最后輸出兩條鏈表，代碼如下：
lnk＝[['吳*'，'男'，1]，['劉**'，'男'，3]，['郭*'，'男'，4]，['朱***'，'女'，2]，['李**'，'男'，6]，['王*'，'女'，8]，['佟**'，'女'，7]，['沙*'，'男'，5]，['寧*'，'男'，－1]]
p＝q＝headA＝0　#headA為男演員鏈表頭指針
r＝headB＝3　#headB為女演員鏈表頭指針，r為尾指針
while p！＝－1：
　　if lnk[p][1]＝＝'男'：
　 q＝p　
　　elif headB！＝p：　#把p節點鏈入女性演員鏈表尾部
　　　
　　else：
　　　 lnk[q][2]＝lnk[p][2]
　　p＝lnk[p][2]
lnk[r][2]＝－1
#使用headA，headB分別作為男性演員、女性演員鏈表頭指針，遍歷輸出lnk，代碼略
加框處代碼由下列語句組成①lnk[q][2]＝lnk[p][2]
②lnk[r][2]＝p　③r＝lnk[r][2]　④lnk[q][2]＝－1則合適的順序是(　　)
A.④②③ B.③①② C.③②① D.②③①
重難點4　循環鏈表及鏈表的簡單應用
1.n個人排成一圈，從某個人開始，按順時針方向從No.1開始依次編號至No.n。從No.1的人開始順時針“1，2，3，…，m，1，2，3，…”報數，報到m(m>1)的人退出圈子。這樣不斷循環下去，輸出最后剩下的一個人的初始編號。實現該功能的Python程序段如下：
n＝int(input())
m＝int(input())
a＝[]
for i in range(n)：
　 a.append([″No.″＋str(i＋1)，(i＋1)%n])
head＝0；p＝head；cnt＝1
while p！＝a[p][1]：
　 pre＝p
　 p＝a[p][1]
　 cnt＋＝1
　 if cnt＝＝m：
　
print(a[p][0])
上述程序段中方框處可選代碼為
①a[p][1]＝a[pre][1]　②a[pre][1]＝a[p][1]　③p＝a[pre][1]　④p＝a[p][1]　⑤cnt＝1　⑥cnt＝0
則應填入的代碼依次為(　　)
A.①③⑤ B.②④⑤ C.①③⑥ D.②③⑥
2.某Python程序段如下：
b＝[[92，2]，[98，4]，[91，1]，[88，0]，[95，3]]
h＝p＝0
while b[p][1]！＝h：
　　print(b[p][0]，end＝″，″)
　　p＝b[p][1]
print(b[p][0])
運行該程序段，輸出的內容為(　　)
A.88，91，92，95，98 B.98，95，92，91，88
C.92，91，98，95，88 D.98，95，88，92，91
3.有如下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
4.小明設計了一個中華小曲庫，其中導入了10000首歌曲，包含4種類型(編號從0－3)，每首歌曲都有自己的歌曲編號，歌曲編號的第一位是其類型，比如某歌曲編號為00041，代表這是類型0的第42首歌。已知本曲庫有一個最近點播榜，分別記錄每種類型最近點播的5首歌，當點播歌曲時記錄規則如下：
①若榜單內不足5首歌，且被點播歌曲不在榜單上，則將其記錄在該類型樂曲榜單首位，如圖a所示，點播歌曲編號為20005，則在類型2的榜單榜首添加歌曲；若已在榜單上，則將其移至榜單首位，如圖b所示點播歌曲00021。
②若榜單內已有5首歌，則將榜尾的樂曲刪除，在榜首添加被點播歌曲，如圖c所示點播歌曲00006。
現有榜單： 00092##00008##00015##00001##00021## 10004##10018##10298##10022## 20001## 30065## 請輸入點播的歌曲：20005 現有榜單： 00092##00008##00015##00001##00021## 10004##10018##10298##10022## 20005##20001## 30065##
圖a
現有榜單： 00092##00008##00015##00001##00021## 10004##10018##10298##10022## 20005##20001## 30065## 請輸入點播的歌曲：00021 現有榜單： 00021##00092##00008##00015##00001## 10004##10018##10298##10022## 20005##20001## 30065##
圖b
現有榜單： 00021##00092##00008##00015##00001## 10004##10018##10298##10022## 20005##20001## 30065## 請輸入點播的歌曲：00006 現有榜單： 00006##00021##00092##00008##00015## 1000#10018##10298##10022## 20005##20001## 30065##
圖c
(1)如在圖c的基礎上繼續點播“00005，10002，00008，00005”，類型0的榜單中第2首歌的編號為________。
(2)已知列表lst中存放曲庫中每種類型歌曲的原始信息，列表中每一個數據元素由2個部分組成，如lst[7]＝[″消愁″，0]，第一個部分為歌曲名稱，第二個為歌曲類型(用數字0－3表示)，為了方便對所有歌曲進行管理與編號，現在需要以類型為主關鍵字，歌曲名稱為次關鍵字進行升序排序，代碼實現如下：
n＝ len(lst)
num ＝ 0
for i in range(n－1)：
　 for j in range(n－i－1)：
　 if lst[j][1]>lst[j＋1][1]：
　　　　 lst[j]，lst[j＋1] ＝ lst[j＋1]，lst[j]
　　　 num ＋＝1
　 elif lst[j][1]＝＝ lst[j＋1][1] and lst[j][0]>lst[j＋1][0]：
　　　　 lst[j]，lst[j＋1]＝lst[j＋1]，lst[j]
　　　　 num＋＝1
為測試程序正確性，小明設置測試了數據lst＝[[″bc″，2]，[″abc″，2]，[″aac″，1]，[″c″，2]，[″ac″，1]]，則程序運行后，num的值為________。
(3)程序“最近點播榜”代碼實現如下，請補全劃線處代碼。
def select(name，kind)：
　 head ＝ leader[kind][0]
　 if head ＝＝－1：
　 data.append([name，－1])
　 leader[kind][0]＝ len(data)－1
　 leader[kind][1]＋＝ 1
　 return
　 elif data[head][0]！＝ name：
　 q＝p＝head
　 ①________
　 while data[p][1]！＝－1:
　　　 if name ＝＝ data[data[p][1]][0]：
　　　　　 tmp＝ data[p][1]
　　　　　 data[p][1]＝data[tmp][1]
　　　　　 data[tmp][1]＝ head
　　　　　 leader[kind][0]＝ tmp
　　　　　 flag ＝ False
　　　　　 break
　　　 q＝p；p＝data[p][1]
　 if　②________：
　　　 data.append([name，head])
　　　 leader[kind][0] ＝ len(data)－1
　　　 leader[kind][1]＋＝1
　 elif flag：
　　　 data[q][1]＝－1
　　　 data[p][0]＝ name
　　 ③__________
　　 leader[kind][0]＝ p
　　return
leader ＝[]
for i in range(4)：
　　　leader.append([－1，0])
data＝[]
while True：
　　　#輸出各類型音樂點播榜單，代碼略
　　　name＝input(″請輸入點播的歌曲″)
　　　kind＝ int(name[0])
　　　select(name，kind)
5.某學校舉辦社團節，在一條直路的同側依次有n個社團展位，按展位到入口距離從1至n依次編號。從入口處走到第1個展位需要花費dis[0]單位時間，從第i個展位走到第i＋1個展位需要花費dis[i]單位時間。每個展位舉行若干活動，每參加一個活動需要5單位時間。對于第i個展位，第一次參加活動獲得a[i－1]個積分，第二次參加活動獲得a[i－1]－b[i－1]個積分，第三次參加活動獲得a[i－1]－2*b[i－1]個積分……以此類推。現在小明從入口處出發，他共有m單位時間自主選擇參與社團的活動并回到入口處。編寫程序實現規定時間內獲得最多積分的活動方案及獲得的積分數。
例：
展位 1 2 3
首次活動積分 10 15 20
每次下降的積分 4 6 4
與前一展位之間步行所花時間 1 3 4
若小明可用時間為28，部分方案如下：
方案1：參加前1個展位活動，有5次活動機會，可得積分為10＋6＋2＝18
方案2：參加前2個展位活動，有4次活動機會，可得積分為15＋10＋9＋6＝40
方案3：參加前3個展位活動，有2次活動機會，可得積分為20＋16＝36
則可獲得的最多積分為40，運行界面如圖所示。
展位數：3 可用時間：28 各展位首次參加活動可獲得的積分：10 15 20 各展位每次下降的積分：4 6 4 相鄰展位之間步行花費時間：1 3 4 能獲得的最多積分是：40 各展位參加的活動次數分別為：[2，2，0]
(1)若小明可用時間為32，按上表數據可得最多積分為________。
(2)定義如下insert(head, r)函數，功能是在首節點下標為head的鏈表中插入下標為r的節點，返回新的鏈首節點下標。data[i]存儲下標為i的節點數據，data[i][0]存儲目前參加活動能獲得的積分，data[i][1]存儲參加活動后要下降的積分，data[i][2]存儲后繼節點下標。
def insert(head, r)：
　 p ＝ q ＝ head
　 while ：
p ＝ q
q ＝ data[q][2]
　 if q ＝＝ head：
data[r][2] ＝ head
head ＝ r
　else：
data[p][2] ＝ r
data[r][2] ＝ q
　return head
若函數加框處代碼誤寫為″ data[r][0] < data[q][0]″，會導致某些情況下無法得到符合函數功能的結果。調用insert(head, r)函數，下列4組數據中能測試出這一問題的是________(單選，填字母)。
A.data＝[[6，6，－1]，[10，3，3]，[2，11，－1]，[7，5，2]]; head＝1; r＝0
B.data＝[[6，6，－1]，[10，3，3]，[2，11，－1]，[7，5，0]]; head＝1; r＝2
C.data＝[[6，6，2]，[10，3，0]，[2，11，－1]，[7，5，－1]]; head＝1; r＝3
D.data＝[[6，6，2]，[10，3，－1]，[2，11，－1]，[7，5，0]]; head＝3; r＝1
(3)實現上述功能的Python程序如下，請在劃線處填入合適的代碼。
'''
展位數存入變量n，可用時間存入變量m，各展位首次參加活動可獲得的積分存入a列表，各展位每參加一次活動要下降的積分存入b列表，相鄰展位之間步行花費時間存入dis列表，dis[0]為入口到第1個展位步行花費時間，dis[i](i>0)為第i個展位到第i＋1個展位步行花費時間，代碼略
'''
for i in range(1, n):
　 dis[i] ＝ ①________
data ＝ []
for i in range(n):
　 data.append([a[i], b[i], －1])
ans ＝ 0　#記錄能夠獲得的最多積分
best ＝ []　#記錄一種能夠獲得最多積分的活動方案
for i in range(n)：
　 head ＝ －1
　 for j in range(i ＋ 1)：
　 data[j][0] ＝ a[j]
　 head ＝ insert(head, j)
　 t ＝ (m － 2 * dis[i]) ∥ 5
　 if t <＝ 0: break
　 total ＝ 0
　 count ＝ [0] * n　#記錄臨時方案
　 while　②________ ：
p ＝ head
head ＝ data[head][2]
total ＋＝ data[p][0]
count[p] ＋＝ 1
data[p][0] ＝③________
if data[p][0] > 0：
　　　　　head ＝ insert(head, p)
　　　t －＝ 1
　 if total > ans：
#更新ans和best代碼略
#輸出代碼略
6.某工程的A項目有n個任務組(編號為0～n－1)，供料商每小時只提供1份原料，各組按到達時刻(到達時刻各不相同)陸續加入領料隊列，領取1份原料后到隊列末尾重新等待，直至領完所需原料，離開隊列。若多組同時入隊，則到達時刻早的優先入隊。編寫程序模擬領料過程，先篩選出屬于A項目的任務組，再計算每個任務組完成領料的時刻(時間單位：小時)，請回答下列問題：
任務組別 到達時刻 原料需求量
第0組 0 3
第1組 1 2
第2組 2 1
圖a
時刻 領料隊列 輪到領料的組別
0 0 0
1 0，1 0
2 1，0，2 1
3 0，2，1 0
4
5 1 1
注：領料隊列中數字代表任務組編號
圖b
(1)某項目任務組信息如圖a所示，部分領料過程如圖b所示，結合題意，第 4 時刻的領料隊列是________(單選，填字母：A.2，1，0/B.2，1/C.2，0，1)。
(2)定義如下 filte(task，st)函數：
def filte(task，st)：
　 i ＝ 0 ; j ＝ 0 ; n ＝ len(task)－1
　 while j <＝ n：
　　　 if task[j][0] ＝＝ st:
　　　 task[i] ＝ task[j]
　　　 i ＋＝ 1
　　　 j ＋＝ 1
　 return i
若task的值是[['A'，0，3]，['B'，1，3], ['B'，2，6], ['A'，3，4], ['A'，4，5]]，st 的值是'A'，執行語句 m＝ filte(task，st)后，m的值是________。
(3)編寫程序模擬任務組領料過程，輸出每個任務組完成領料的時刻，部分Python 程序如下，請在劃線處填入合適的代碼。
def proc(task, st)：
　 m ＝ filte(task, st)
　 for i in range(m)：
　 task[i].append(－1)
　 order ＝ [0] * m
　 i ＝ 0；ct ＝ 0；t＝0
　 while i < m or t　　　if i < m and task[i][1] <＝ ct:
　　　 if i＝＝t：
　　　　　 ①________
　　　　　 task[p][3] ＝ i
　　　 else：
　　　　　 task[i][3] ＝ task[p][3]
　　　　　　 task[p][3] ＝ i
　　　　 p ＝ i
　　　 i ＋＝ 1
　 if i>t：
　　　 ②______
　　　 task[k][2] ＝ task[k][2] － 1
　　　 if task[k][2]＝＝ 0：
　　　　　　 order[k] ＝ ct
　　　　　　 ③________
　　　　　　 t＋＝1
　　　 else：
　　　　　　 p ＝ task[p][3]
　 ct ＋＝ 1
　 return order
'''每個任務初始數據存入 task 列表，task[i]包含 3 項，task[i][0]為該組項目名稱，task[i][1]為該組到達時刻，task[i][2]為該組原料需求量，數據按到達時刻升序排列，代碼略'''
st ＝″A″
print(proc(task，st))　#輸出該項目中每個任務組完成領料的時刻
專題17　鏈　表
學習目標　1.掌握鏈表的概念和鏈表的遍歷方法；
2.掌握鏈表頭節點的插入和刪除操作；
3.掌握鏈表除頭節點外的其他節點的插入和刪除操作.
鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表每個節點的結構是相同的，由數據區域和指針區域組成，其中指針區域指向下一個節點的索引。鏈表的訪問必須從頭節點開始，因此頭指針是鏈表必不可少的元素。
(2024年1月浙江省選考)使用列表d模擬鏈表結構(節點數大于0)，每個節點包含數據區域和指針區域，h為頭指針。鏈表中各節點已按數據區域中數值的絕對值由小到大排列，如圖a所示。現要修改該鏈表各節點的鏈接關系，使鏈表各節點按數據區域中的數值由小到大排列，結果如圖b所示。實現該功能的程序段如下，方框中應填入的正確代碼為(　　)
t＝h
p＝d[h][1]
while p ！＝ －1 ：
　 q＝d[p][1]
　　
　　p＝q
d[t][1]＝－1
答案　C
解析　本題考查鏈表的頭插法和尾插法。程序實現的功能是從第2個節點開始，將遍歷到節點插入新鏈表的頭部或尾部。題圖a按絕對值升序排序數據，鏈表中數據依次為－11，14，16，17，－18，要求改變鏈接關系，使鏈表各節點按數據區域中的數值由小到大排列。若鏈表中只有1個節點，其值無論是正數還是負數，均是最小的數。同時他既是頭節點h，也是尾節點t。因此變量p從鏈表第2個節點開始遍歷各個節點，若遍歷到負數，則該數絕對值越大，其值就越小，需將該節點從原鏈表中刪除，并移動到頭節點的前面，進行的操作是將該前節點p指向原頭節點h，同時修改當前位置為頭指針。若為正數，將該節點鏈接到尾節點t的后面。
重難點1　鏈表的遍歷
鏈表的遍歷必須從頭節點開始，每個節點包含數據區域和指針區域，數據區域可能有多個值，指針區域值往往在節點最后一個位置。若當前q指向頭指針head，那么a[q]是整個節點的值，a[q][0]是數據區域的值，a[q][1]是下一節點的索引，通過語句q＝a[q][1]，實現指針向后移動。
例題 某公交路線的站點名稱、經度、緯度和下一個站點序號(經緯度已轉換為平面坐標數據)存儲在數組 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.①③②
思維點撥
明考向 本題考查鏈表的遍歷
精點撥 從當前鏈表的頭節點開始遍歷，與下一個節點p的距離，因此head要不斷地后移，head＝p，而p為新節點的后繼節點。當頭指針節點的后繼為－1時，表示遍歷完了
答案　A
變式 使用鏈表結構模擬某景區游玩路線，鏈表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.②④③
答案　D
解析　本題考查多條鏈表的遍歷。3條鏈表構建在數組a中，頭指針存儲在數組head中，需遍歷頭指針數組，從而來遍歷3條鏈表。(1)處為當前節點賦值為頭指針head[i]，變量s存儲所有節點游覽總時間。(2)(3)遍歷鏈表，并統計各個節點游覽時間和，由于當前節點已經計入總時間，因此先要跳轉到下一點，將下一節點的時間加入總時間，注意遍歷結束的條件是當遍歷到尾節點時，終止遍歷。
重難點2　鏈表節點的刪除
在數組中刪除某個節點，往往需把該節點后面的值往前移，時間復雜度為線性階O(n)。鏈表節點的刪除分為頭節點的刪除和其他節點的刪除，頭節點的刪除只要移動頭指針到下一節點，即head＝a[head][1]即可，其他節點的刪除，只要修改該節點的前驅節點的指針區域值為該節點的后繼節點索引即可，時間復雜度為常量階O(1)。
例題 使用列表a模擬鏈表結構(節點數大于0)，每個節點包含數據區域和指針區域，head為頭指針，鏈表中各節點已按數據區域中數值的由小到大排列。現要修改該鏈表各節點的鏈接關系，刪除鏈表中數據區域數值相同的節點，使得鏈表各節點的數據區域值不重復。
實現該功能的程序段如下，方框中應填入的代碼段可行的是(　　)
p ＝ head
q ＝ a[p][1]
while q！＝－1：
　　
a[p][1]＝－1
A .if a[p][0]！＝a[q][0]:
a[p][1]＝q
p ＝ q
else：
p ＝ q
q＝a[q][1]
B .if [p][0]！＝a[q][0]：
a[p][1]＝q
p ＝ q
q＝a[q][1]
C .if a[p][0]＝＝a[q][0]：
p ＝ q
q＝a[q][1]
else：
a[p][1]＝q
p ＝ q
q＝a[q][1]
D .if [p][0]＝＝a[q][0]：
q＝a[q][1]
else：
p ＝ q
a[p][1]＝q
思維點撥
明考向 本題考查鏈表節點的刪除
精點撥 當前節點q從第2個節點開始遍歷，節點p是一段連續重復的開始位置，若a[p][0]與a[q][0]相等，則q向后遍歷，否則讓p的直接指向q，同時更新當前p的值為q。如鏈表數據1，2，2，2，3，3，3，有多個2時，讓p指向第1個2位置，當q遍歷到值為3時，讓p直接指向3，刪除中間的2。若最后出現多個重復的值時，語句a[p][1]＝－1的功能是刪除后面重復的數據
答案　B
變式 使用列表模擬單向鏈表，鏈表中p節點的a[p][0]存儲數據，a[p][1]存儲其后繼節點的指針。編寫Python程序刪除鏈表中所有偶數項(頭節點為該鏈表的第1項)，部分代碼如下：
p＝head
while p！＝－1：
　　q＝a[p][1]
　　if ①________：
　 a[p][1]＝a[q][1]
　　②________
上述程序段劃線處可選語句為(　　)
A.①q！＝－1　　　 ②q＝a[q][1]
B.①q！＝－1　　　 ②p＝a[p][1]
C.①a[q][1]！＝－1　②q＝a[q][1]
D.①a[q][1]！＝－1　②p＝a[p][1]
答案　B
解析　本題考查鏈表節點的刪除。 p是當前節點，也是奇數節點，q是偶數節點。若q不為－1，采用語句a[p][1]＝a[q][1]刪除q節點，同時更改p的值為q的后繼。
重難點3　鏈表節點的插入
在數組中插入節點的時間復雜度為線性階O(n)。鏈表節點的插入分為在頭節點前的插入和其他節點前插入兩種，頭節點前插入新節點，該節點指向原頭節點，并要修改head指針。在當前節點q前插入新節點，該新節點的后續是q，將修改q的前驅節點指針區域值。
例題 使用列表da和db模擬2個鏈表結構(節點數均大于0)，每個節點包含數據區域和指針區域，ha和hb分別為2個鏈表的頭指針。鏈表中各節點已按數據區域中數值由小到大排列，且鏈表da頭節點值小于鏈表db頭節點值。現要將鏈表db中數據合并到鏈表da中，且保持升序排列。實現該功能的程序段如下，方框中應填入的正確代碼為(　　)
t＝ha
while hb！＝－1：
　　q＝da[t][1]
　　
A.if q＝＝－1 or da[q][0]>db[hb][0]：
　　 da.append([db[hb][0]，q])
　　 da[t][1]＝len(da)－1
　　 hb＝db[hb][1]
t＝da[t][1]
B.if q＝＝－1 or da[q][0]>db[hb][0]：
　　 da.append([db[hb][0]，q])
　　 da[t][1]＝len(da)－1
　　 hb＝db[hb][1]
　　 t＝da[t][1]
C.if q＝＝－1 or da[q][0]>db[hb][0]：
　　 da.append([db[hb][0]，q])
　　 da[t][1]＝len(da)－1
　　 hb＝db[hb][1]
t＝q
D.if q＝＝－1 or da[q][0]>db[hb][0]：
　　 da.append([db[hb][0]，q])
　　 da[t][1]＝len(da)－1
hb＝db[hb][1]
t＝da[q][1]
思維點撥
明考向 本題考查鏈表節點的插入
精點撥 t是新鏈表的尾指針，hb是鏈表db的當前節點指針。鏈表da頭節點是值最小的，成為新鏈表的頭節點，將鏈表db和原鏈表da第2個節點及后面所有節點采用尾插法合并到新鏈表da中。將鏈表db節點插入到新鏈表方法：當完成遍歷da鏈表或者da鏈表尾指針后面節點值比db鏈表當前節點值的大時，①將鏈表db當前節點值添加到鏈表da中，成為最后一個元素，新節點指向原鏈表da尾節點t的后繼q；②將尾節點t指向新添加的節點len(da)－1；③更新鏈表db的當前節點指針hb和鏈表da尾節點指針t。將鏈表da節點插入到新鏈表方法：由于鏈表的鏈接關系已經建立，只要更新尾節點t即可。新鏈表的尾節點無論是來自da還是db，均需要更新尾指針t，因此只要把這條語句放在判斷結構的下方即可
答案　A
變式 列表a存儲了兩個升序鏈表的節點，每個節點包含數據區域和指針區域，頭指針分別為ha、hb，且a[ha][0]q ＝ h ＝ ha
p ＝ a[ha][1]
k ＝ hb
while p ！＝ －1 and k ！＝ －1：
　 if a[p][0] <＝ a[k][0]：
　 q ＝ p
　 p ＝ a[q][1]
else：
　
if k！＝－1：
　 a[q][1] ＝ k
方框中應填入的正確代碼為(　　)
答案　B
解析　本題考查鏈表節點的插入。由于a[ha][0]小于a[hb][0]，因此p從ha所在鏈表第2個節點開始遍歷，q為p的前驅，k遍歷hb所在鏈表。當條件a[p][0]<＝ a[k][0]成立時，q和p繼續遍歷；若條件不成立，將節點k插入到節點p的前面。
重難點4　循環鏈表及鏈表的簡單應用
循環鏈表是一種特殊的鏈式存儲結構，其中最后一個節點的指針指向頭節點，形成一個環。
例1 報數游戲。已知班上有n名學生(用編號1，2，3，……，n分別表示)，學生按照編號由小到大順時針圍成一個圓圈，從編號為1的學生開始順時針報數，報到m的同學出列；下一名同學又從1開始報數，報數為m的同學繼續出列；以此規律重復下去，直到剩下最后一位同學為止。
(1)當n＝6，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 ②________：　 #從1至m－1依次報數
　 p＝lst[p][1]
　　out＝lst[p][1]
　　③________
　　n＝n－1
print(″最后留下的同學的編號是：″，lst[p][0])
思維點撥
明考向 本題考查循環鏈表的算法實現
精點撥 (1)3號和6號先出列，剩余編號為1245，4號和2號出列，接著5號出列，剩余1號。(2)①尾節點值為n，指向頭節點0。②從 1至m－1依次報數，共循環了m－1次。③當前節點指針從尾節點開始，連續進行m－1次報數后，下一個節點out將要被刪除，因此語句lst[p][1]＝lst[out][1]實現了刪除out節點的操作
答案　(1)1　(2)①[n，0]　②range(1，m)或range(m－1)　③lst[p][1]＝lst[out][1]
變式1 有如下Python程序段：
a＝[4，5，3]
d＝[[3，″A″，2]，[6，″B″，0]，[3，″C″，1]]
q＝head＝1
t，n＝2，3
ans＝″″
i＝0
while n>0 and i　 if d[q][0]>a[i]：
　　　d[q][0]－＝a[i]
　　　t＝d[t][2]
　　　i＋＝1
　 else：
　　　a[i]－＝d[q][0]
　　　d[t][2]＝d[q][2]
　　　n－＝1
　　　ans＋＝d[q][1]
　 q＝d[q][2]
執行該程序段后，ans的值是(　　)
A.″ABC″ B.″ACB″ C.″BAC″ D.″CBA″
答案　A
解析　本題考查循環鏈表以及隊列的算法實現。鏈表d構成一個循環鏈表，隊列依次為BAC，若a[i]的值能分配給隊首，則隊首元素出隊，否則更新剩余部分，再重新入隊。變量t是鏈表的尾指針，指針q從頭節點2開始遍歷，若當前節點d[q][0]大于a[i]，a[i]不夠分配，更新d[q][0]和尾指針t，同時i向后移動。若當前節點d[q][0]小于等于a[i]，刪除當前節點q，同時n的值減少1個，表示完成一個元素的分配，同時更新a[i]。″B″更新為2后入隊；″A″出隊，″C″更新為2后入隊；″B″出隊，″C″出隊。
例2 某編程興趣小組設計了一個點歌模擬程序，功能如下：
運行程序后，從鍵盤輸入“A”，則顯示已點的歌曲列表(歌單)；輸入“B”則可以自行輸入歌曲并添加到歌單以完成點歌；輸入“C”則可以將指定的歌曲置頂等待播放；輸入“D” 則播放當前第一首歌曲，并將該歌曲從列表中刪除；輸入“E”則關閉程序并退出。程序運行界面如圖所示。
請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A God Is a Girl　十年　年少有為　七里香　淡季動物園 請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：B 請輸入歌曲：蘭亭序 請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：B 請輸入歌曲：想自由 請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A God Is a Girl　十年　年少有為　七里香　淡季動物園　蘭亭序　想自由 請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：C 請輸入歌曲：七里香 請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A 七里香　God Is a Girl　十年　年少有為　淡季動物園　蘭亭序　想自由 請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：C 請輸入歌曲；想自由 請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A 想自由　七里香　God Is a Girl　十年　年少有為　淡季動物園　蘭亭序 請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：D 請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A 七里香　God Is a Girl　十年　年少有為　淡季動物園　蘭亭序 請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：E
Python代碼如下所示，請在劃線處填入合適的代碼。
data＝[[″十年″，4], [″淡季動物園″，－1], [″God Is a Girl″，0], [″七里香″，1], [″年少有為″，3]]
head＝2
tail＝1
while True：
　 cmd ＝input(″請輸入指令 A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：″)
　　if cmd＝＝″A″：
　 cur＝head
　 while cur！＝－1:
　　　　　print(data[cur][0]，end＝″″)
　　　　　cur＝data[cur][1]
　 print()
　　elif cmd＝＝″B″：
　 song＝input(″請輸入歌曲：″)
　 data.append([song，－1])
　 if head＝＝－1：
　　　　　head＝tail＝len(data)－1
　 else：
　　　　　①________
　　　　　tail＝len(data)－1
　　elif cmd＝＝″C″：
　 song＝input(″請輸入歌曲：″)
　 cur＝head
　 while cur！＝－1 and data[cur][0]！＝song:
　　　　　pre＝cur
　　　　　cur＝data[cur][1]
　if cur！＝－1 and cur！＝head：
　　　②________
　　　data[cur][1]＝head
　　　head＝cur
　　　if cur＝＝tail：
　　　 ③________
elif cmd＝＝″D″：
　if head＝＝tail:
　　 head＝tail＝－1
　else：
　　　④________
elif cmd＝＝″E″：
　break
明考向 本題考查鏈表的操作
精點撥 ①輸入“B”則可以自行輸入歌曲并添加到歌單，新節點插入在尾節點的后面，因此原尾節點應指向新插入的節點，同時更新尾節點。②輸入“C”則可以將指定的歌曲置頂，data[cur][0]值為song表示找到節點cur，pre為cur節點的前驅，將cur移動到頭節點前面，因此需要3步，第1步是將cur的前驅pre指向cur的后繼，第2步是將cur指向原頭節點，第3步是設置新的頭節點為cur。③若cur是原尾節點tail，將cur修改為頭節點后，新的尾節點為cur的前驅。④輸入“D” 則播放當前第一首歌曲，并將該歌曲從列表中刪除，條件head＝＝tail成立表示鏈表中只有一個節點，否則將頭指針向后移動，刪除頭節點
答案　①data[tail][1]＝len(data)－1
②data[pre][1]＝data[cur][1]　③tail＝pre
④head＝data[head][1]
變式2 已知一個有7個節點的單向鏈表，設有頭指針head和尾指針tail，如圖所示，下列操作需要遍歷多個節點的是(　　)
A.刪除該鏈表中的最后一個節點
B.刪除該鏈表中的第一個節點
C.在該鏈表第一個節點前插入一個新節點
D.在該鏈表最后一個節點后插入一個新節點
答案　A
解析　本題考查鏈表的遍歷、插入和刪除操作。A選項刪除該鏈表中的最后一個節點，需修改最后一個節點的前驅節點指針域，因此需遍歷多個節點。B選項只需修改頭指針。C選項修改當前節點的指針值指向原頭節點，并修改頭指針為當前節點。D選項讓原尾節點指向當前節點，并修改尾節點為當前節點。
重難點1　鏈表的遍歷
1.下列關于單向鏈表的說法正確的是(　　)
A.必定有頭指針和尾指針
B.每個節點都有一個后繼節點
C.刪除一個節點，需要修改兩個指針
D.查找任一節點的算法時間復雜度為O(n)
答案　D
解析　本題考查鏈表相關知識。A選項單向鏈表必定有頭指針，不一定要有尾指針。B選項尾結點沒有后繼節點。C選項單向鏈表刪除一個節點，只需修改刪除節點的前驅節點的后繼指針即可。D選項鏈表的訪問比較低效，每次遍歷都需要從 head 頭結點開始，故算法時間復雜度為 O(n)。
2.使用列表模擬單鏈表，其存儲結構如圖所示，遍歷該鏈表，將訪問到的節點的數據域的字符依次連接，得到字符串‘LOVE’，則指針域中的索引值依次為(　　)
A.0 1 2 3 B.3 1 0 2
C.2 0 －1 1 D.2 0 1 －1
答案　C
解析　本題考查鏈表的構建和遍歷。L的后繼節點為O，因此其指針區域值為1；O的后續為V，指針區域值為0; V的后續為E，指針區域值為2；E為尾節點，因此指針區域值為－1。
3.使用Python的二維列表來模擬單向鏈表，如下代碼創建一個擁有4個節點的鏈表a
a＝[[″cat″，1]，[″dog″，2]，[″pig″，－1]，[″rabbit″，0]]
head＝3
依次輸出各節點數據域的值，內容為(　　)
A.″cat″，″dog″，″pig″，″rabbit″
B.″pig″，″rabbit″，″cat″，″dog″
C.″pig″，″dog″，″cat″，″rabbit″
D.″rabbit″，″cat″，″dog″，″pig″
答案　D
解析　本題主要考查鏈表的操作。head＝3，即對應列表索引3，其值為“rabbit”，指向索引為0的節點，其值為“cat”，依此類推，依次輸出各節點數據域的值，內容為″rabbit″，″cat″，″dog″，″pig″，故本題選D選項。
4.實現在鏈表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.②④
答案　D
解析　本題考查鏈表遍歷和最值查找。當前節點從頭節點開始遍歷，最小值的初值為頭節點大小，因此需先移動到下一節點，再與最值進行比較，同時終止遍歷的條件是遍歷到尾節點馬上結束。
5.使用列表a模擬鏈表結構(節點數大于0)，每個節點包含數據區域和指針區域，head為頭指針。鏈表中各節點已按數據區域中的數值由小到大排列。現要計算鏈表中的中位數，處在鏈表最中間位置的數叫做中位數。說明：當數據元素為奇數個時中位數為最中間的數，偶數個時中位數為最中間兩個數的平均數。實現功能的Python程序如下，劃線處應填入的正確代碼為(　　)
fast＝slow＝head
while fast！＝－1 and ①________：
　 p＝slow
　 slow＝a[slow][1]
　 fast＝ a[a[fast][1]][1]
if ②________：
　 mid＝(a[p][0]＋a[slow][0])/2
else：
　 mid＝a[slow][0]
print(″中位數是：″， mid)
A.①slow！＝－1　　　 ②fast！＝－1
B.①a[slow][1]！＝－1 ②fast＝＝－1
C.①a[fast][1]！＝－1 ②fast！＝－1
D.①a[fast][1]！＝－1 ②fast＝＝－1
答案　D
解析　fast和slow分別表示快慢指針，fast每次遍歷2個節點，若遍歷完成后，fast的值為－1，表示節點數量為偶數，當a[fast][1]值為－1，遍歷到尾節點，節點數量為奇數，遍歷完成。
重難點2　鏈表節點的刪除
1.某單向鏈表如下圖所示，若要將數據 data3 和data4 同時從鏈表中移除，至少需要修改節點指針的數量是(　　)
A.1 B.2 C.3 D.4
答案　A
解析　只需修改data2的指針區域值修改為data4的指針區域值。
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
答案　D
解析　本題考查鏈表的基本操作。如果鏈表頭節點值為1，直接刪除頭節點，否則遍歷鏈表，語句a[pre][1]＝a[p][1]的作用讓節點p的前驅指向他的后繼，即刪除p節點。程序的功能是刪除元素值為1的節點。
3.使用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
答案　C
解析　本題考查遍歷鏈表及刪除節點操作。①x是鏈表中一個節點位置，從鏈表中被刪除的數據a[x][0]。②判斷當前節點a[q]的值是否是要刪除的數據data。③遍歷鏈表，如果當前節點是要刪除的數據，且該節點是頭節點，需要更新頭指針head的值，若不是頭節點，需讓前驅節點p指向當前節點q的后繼節點。若當前節點的數據域不是 data，則將當前節點 p 更新為前驅節點 q，并繼續檢查下一個節點。
4.用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.②①③
答案　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]。
重難點3　鏈表節點的插入
1.小張準備去多個城市旅游，他設計的行程若采用鏈表結構表示，如圖a所示。若行程有變，需在“上海”與“成都”之間增加一站“杭州”，鏈表修改為如圖b所示，有以下可選操作：
①“上海”所在節點的next值賦為“杭州”節點的next值
②“上海”所在節點的next值賦為5
③“杭州”所在節點的next值賦為“上海”所在節點的next值
④“杭州”所在節點的next值賦為－1
鏈表更新順序正確的是(　　)
A.③① B.③② C.①④ D.②④
答案　B
解析　本題考查的知識點是鏈表元素的插入。鏈表中插入新元素并不需要進行元素位置移動，只需要進行節點指針域的更改即可。在“上海”與“成都”之間增加一站“杭州”，需要先將新元素“杭州”的指針域設置為“成都”所在位置，再更改節點“上海”的指針域至節點“杭州”所在位置。
2.有如下Python程序：
def lnkid(n，head):
　 p＝head
　 while head ！＝－1 and ①________：
　 p＝head
　 head＝a[head][1]
　 return p
a＝[[2，2]，[5，3]，[1，－1]，[3，0]，[7，1]]
head＝4
n＝int(input())
p＝lnkid(n，head)
if n>a[head][0]：
　 a.append([n，head])
　 head＝len(a)－1
else：
　 a.append([n，a[p][1]])
　 ②________
用列表a模擬一個降序鏈表，運行程序，輸入自然數n，則鏈表增加一個新的節點，要使鏈表保持降序，則劃線①②處代碼分別為(　　)
A.①nB.①nC.①nD.①n>a[head][0] ②a[p][1]＝len(a)
答案　B
解析　本題考查鏈表的插入。①自定義函數lnkid的功能是查找n在鏈表中插入位置，head在不斷地向后移動，因此n將和a[head][0]進行比較，當比a[head][0]小時，不斷地向后查找位置。②語句p＝lnkid(n，head)將返回在節點p的后面插入新的數n，因此將修改a[p]節點指針區域值為當前插入點索引。
3.有兩個降序序列的鏈表 a，b。現將鏈表 b 中的數據合并到鏈表 a，形成一個新的降序序列存于鏈表 a，實現數據合并的代碼段如下：
a ＝ [[98，1]，[96，2]，[95，3]，[93，4]，[90，－1]]
b ＝ [[99，1]，[97，2]，[94，3]，[93，4]，[92，－1]]
head_a ＝ head_b ＝ 0
pre ＝ p ＝ head_a；q ＝ head_b
while q！＝－1：
　 if p！＝－1 and ：
　 pre＝p
　 p＝a[p][1]
　 else：
　 a.append()
　 if p＝＝head_a：
　　　 pre＝head_a＝len(a)－1
　 else：
　　　 a[pre][1]＝
　　　 pre＝len(a)－1
　 q＝b[q][1]
上述程序段中可選填的語句為：①a[p][0]>＝ b[q][0]　②a[p][0]<＝ b[q][0]　③q　④len(a)－1　⑤[b[p][0]，q]　⑥[b[q][0]，p]
則加框處填寫的語句依次為(　　)
A.①⑥④ B.①⑤④ C.①⑥③ D.②⑥③
答案　A
解析　本題考查鏈表元素的遍歷和插入操作。程序的功能將鏈表b中的數據合并到鏈表a，形成一個新的降序序列存于鏈表a。分別遍歷兩個鏈表，若鏈表a當前元素值a[p][0]大于等于鏈表b當前元素值b[q][0]，則鏈表a向后遍歷，否則把鏈表b當前元素值b[q][0]插入到鏈表a當前元素前面。由于是要把鏈表b中的數據合并到鏈表a，因此鏈表b遍歷完成后，結束程序。
4.將兩個鏈表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.②③⑤
答案　B
解析　本題考查鏈表節點的插入操作。程序將節點q插入到節點p的后面，因此q的指針域的值將發生變化，為了鏈表b正常遍歷，應先保存q的后繼。插入過程中，由于已經保存了q的后繼，因此可以先修改q的指向，再修改p的指向，最后將p移動到原插入節點q的后繼。
5.用鏈表模擬隊列操作(隊列長度大于1)，鏈表的每個節點包含數據區域和指針區域。指針head指向隊列的第一個元素，指針tail指向隊列的最后一個元素，如圖所示。現執行n次“出隊后立即入隊”操作，實現該功能的Python程序段如下：
k＝1
while k<＝n：
　　p＝head
　　
　　tail＝p
　　k＋＝1
上述程序段中方框處可選代碼有
①head＝que[head][1]　②que[tail][1]＝head
③que[head][1]＝－1　④que[p][1]＝－1
則方框內應填入的正確代碼順序為(　　)
A.①②③ B.①②④ C.②①③ D.②①④
答案　D
解析　先采用尾插法將原頭節點鏈接入鏈表，接著更新尾頭節點，同時將新尾節點的指針區域值設置為1。
重難點4　循環鏈表及鏈表的簡單應用
1.有如下程序段：
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
答案　B
解析　本題考查循環鏈表的算法實現。每遍歷一次，i增加1，實現計數。第1次刪除節點2，第2次刪除節點4，第3、4、5分別刪除節點6、3、1，鏈表中只剩下節點5。
2.將A－K共13張黑桃撲克牌洗好后，把牌面朝下。第一張牌翻過來A，第2次將最上面第1張牌放到這疊牌的最下面，將第2張牌翻開，是黑桃2；第3次數將最上面第1、2張牌放到這疊牌的最下面，將第3張牌翻開，是黑桃3；依次類推將13張牌按從小到大的順序翻出。求這疊牌洗好后，從上到下的原始順序。
(1)程序運行結果如圖所示，結合下面代碼，當輸入撲克牌數量num為6時，撲克牌從上到下的初始順序最后輸出結果為：________。
請輸入撲克牌數量(1—13)：13 撲克牌從上到下的初始順序為： A，8，2，5，10，3，Q，J，9，4，7，6，K，
(2)實現題中所述功能的Python程序如下，請在程序中劃線處填入合適的代碼。
num ＝ int(input(″請輸入撲克牌數量(1－13)：″))
poker ＝ [[i ＋ 1，(i ＋ 1) % num　] for i in range(num)]　#創建循環鏈表
①________
cur ＝ poker[pre][1]
result ＝ []
for i in range(num)：
　 for j in ②________：
　 pre ＝ cur
　 cur ＝ poker[cur][1]
　 result.append(poker[cur][0])
　 poker[pre][1] ＝③________
　 cur ＝ poker[pre][1]
initial ＝ [0] * num
for k in range(num)：
　 initial[result[k]－1]＝④________
print(″撲克牌從上到下的初始順序為：″)
ajqk ＝ {1：″A″， 11：″J″， 12：″Q″， 13：″K″}
for m in initial：
　 if m > 10 or m ＝＝ 1：
　 print(ajqk[m], end＝″，″)
　 else：
　 print(m, end＝″，″)
答案　(1)A，4，2，5，6，3　(2)①pre＝num－1　②range(i)　③poker[cur][1]或poker[poker[pre][1]][1]　④k ＋ 1
解析　本題考查循環鏈表的算法實現。(1)若輸入6張牌，那么每次翻牌的位置依次是1, 3, 6, 2, 4, 5。將這些位置依次填入數字1－6，
位置 1 3 6 2 4 5
牌 A 4 2 5 6 3
可以得到原始的位置牌的點數。(2)①pre是當前節點cur的前驅，其初始值為尾節點位置。②變量i從0循環至，第i次循環時，翻了i張牌，因此需循環i次。③每次循環結束，獲取當前翻開牌的位置，并依次存入數組result。變量k從0循環至num－1，result[k]表示第k＋1張牌的位置，result[k]－1表示原始位置數組initial的索引位置，其值為k＋1。
重難點1　鏈表的遍歷
1.鏈表不具備的特點是(　　)
A.所需存儲空間與存儲元素個數成正比
B.插入、刪除操作不需要移動元素
C.無須事先估計存儲空間的大小
D.可隨機訪問任何一個元素
答案　D
解析　本題考查鏈表相關知識點。鏈表的訪問必須從頭節點開始。通過指針依次訪問，不能隨機訪問任何一個元素。
2.某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→
答案　B
解析　沒有輸出尾結點，輸出前面4個節點的數據域，并以″→″結束，故答案為1→2→3→5→，選B。
3.王老師用鏈表模擬某次比賽中運動員的出場次序，運動員號碼存儲如下： a＝[[″e56″，4]，[″134″，－1]，[″215″，5]，[″098″，0]，[″144″，2]，[″024″，1]]。假設head＝3，小明同學的號碼是“215”，則他的出場次序是(　　)
A.2 B.4 C.5 D.6
答案　B
解析　本題考查鏈表的遍歷。head值為3，[″098″，0]為頭節點，接著是[″e56″，4] [″144″，2] ，[″215″，5], [″024″，1], [″134″，－1]。
4.有如下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
答案　C
解析　本題考查鏈表的遍歷。條件a[p][1]！＝－1表示當前節點的指針區域值為－1，即當前節點為尾節點。當遍歷到尾節點時，結束循環。
5.利用列表模擬非循環鏈表a(可能存在已被刪除的節點)，下列程序運行完畢后，變量p表示尾節點的節點位置是(　　)
答案　B
解析　本題考查鏈表的遍歷。A選項當前節點為p，當遍歷到節點為空時停止遍歷，因此遍歷結束后，p節點為空，其前驅t為尾節點。B選項當前節點為p，若當前節點的指針區域值為－1，結束遍歷，那么當前節點p為尾節點。C選項當前節點從頭節點開始遍歷，a[a[p][1]]指當前節點的后繼節點，若該節點的指針區域值為－1，表示該節點為尾節點，當前節點為尾節點的前驅。D選項鏈表a可能存在已被刪除的節點，因此len(a)的值可能大于節點總數。
6.某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]
答案　B
解析　本題考查鏈表應用。data是一個鏈表，t指針從鏈表的第二個節點開始遍歷，1a指針是t節點的前驅，t節點減去前驅節點la的值小于key時，c計數，c的初值為0，計數到3時結束，也就是整個過程計數3次就結束，執行程序后t的值為6，也就是遍歷到最后一個節點時程序才結束。
7.通過(共172張PPT)
專題17　鏈表
第三部分　數據的存儲與邏輯結構
1.掌握鏈表的概念和鏈表的遍歷方法；
2.掌握鏈表頭節點的插入和刪除操作；
3.掌握鏈表除頭節點外的其他節點的插入和刪除操作.
目 錄
CONTENTS
體系構建
01
真題再現
02
考點精練
03
當堂檢測
04
課后練習
05
體系構建
1
鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表每個節點的結構是相同的，由數據區域和指針區域組成，其中指針區域指向下一個節點的索引。鏈表的訪問必須從頭節點開始，因此頭指針是鏈表必不可少的元素。
真題再現
2
(2024年1月浙江省選考)使用列表d模擬鏈表結構(節點數大于0)，每個節點包含數據區域和指針區域，h為頭指針。鏈表中各節點已按數據區域中數值的絕對值由小到大排列，如圖a所示。現要修改該鏈表各節點的鏈接關系，使鏈表各節點按數據區域中的數值由小到大排列，結果如圖b所示。實現該功能的程序段如下，方框中應填入的正確代碼為(　　)
答案　C
解析　本題考查鏈表的頭插法和尾插法。程序實現的功能是從第2個節點開始，將遍歷到節點插入新鏈表的頭部或尾部。題圖a按絕對值升序排序數據，鏈表中數據依次為－11，14，16，17，－18，要求改變鏈接關系，使鏈表各節點按數據區域中的數值由小到大排列。若鏈表中只有1個節點，其值無論是正數還是負數，均是最小的數。同時他既是頭節點h，也是尾節點t。因此變量p從鏈表第2個節點開始遍歷各個節點，若遍歷到負數，則該數絕對值越大，其值就越小，需將該節點從原鏈表中刪除，并移動到頭節點的前面，進行的操作是將該前節點p指向原頭節點h，同時修改當前位置為頭指針。若為正數，將該節點鏈接到尾節點t的后面。
考點精練
3
重難點1　鏈表的遍歷
鏈表的遍歷必須從頭節點開始，每個節點包含數據區域和指針區域，數據區域可能有多個值，指針區域值往往在節點最后一個位置。若當前q指向頭指針head，那么a[q]是整個節點的值，a[q][0]是數據區域的值，a[q][1]是下一節點的索引，通過語句q＝a[q][1]，實現指針向后移動。
上述程序段劃線處可選的代碼為(　　)
①a[head][3]！＝－1　②head＝p　③p＝a[head][3]　④head！＝－1，則(1)、(2)、(3)處的代碼依次為(　　)
A.①②③ B.④②③ C.④③② D.①③②
A
思維點撥
明考向 本題考查鏈表的遍歷
精點撥 從當前鏈表的頭節點開始遍歷，與下一個節點p的距離，因此head要不斷地后移，head＝p，而p為新節點的后繼節點。當頭指針節點的后繼為－1時，表示遍歷完了
D
解析　本題考查多條鏈表的遍歷。3條鏈表構建在數組a中，頭指針存儲在數組head中，需遍歷頭指針數組，從而來遍歷3條鏈表。(1)處為當前節點賦值為頭指針head[i]，變量s存儲所有節點游覽總時間。(2)(3)遍歷鏈表，并統計各個節點游覽時間和，由于當前節點已經計入總時間，因此先要跳轉到下一點，將下一節點的時間加入總時間，注意遍歷結束的條件是當遍歷到尾節點時，終止遍歷。
重難點2　鏈表節點的刪除
在數組中刪除某個節點，往往需把該節點后面的值往前移，時間復雜度為線性階O(n)。鏈表節點的刪除分為頭節點的刪除和其他節點的刪除，頭節點的刪除只要移動頭指針到下一節點，即head＝a[head][1]即可，其他節點的刪除，只要修改該節點的前驅節點的指針區域值為該節點的后繼節點索引即可，時間復雜度為常量階O(1)。
答案　B
思維點撥
明考向 本題考查鏈表節點的刪除
精點撥 當前節點q從第2個節點開始遍歷，節點p是一段連續重復的開始位置，若a[p][0]與a[q][0]相等，則q向后遍歷，否則讓p的直接指向q，同時更新當前p的值為q。如鏈表數據1，2，2，2，3，3，3，有多個2時，讓p指向第1個2位置，當q遍歷到值為3時，讓p直接指向3，刪除中間的2。若最后出現多個重復的值時，語句a[p][1]＝－1的功能是刪除后面重復的數據
B
解析　本題考查鏈表節點的刪除。 p是當前節點，也是奇數節點，q是偶數節點。若q不為－1，采用語句a[p][1]＝a[q][1]刪除q節點，同時更改p的值為q的后繼。
重難點3　鏈表節點的插入
在數組中插入節點的時間復雜度為線性階O(n)。鏈表節點的插入分為在頭節點前的插入和其他節點前插入兩種，頭節點前插入新節點，該節點指向原頭節點，并要修改head指針。在當前節點q前插入新節點，該新節點的后續是q，將修改q的前驅節點指針區域值。
答案　A
思維點撥
明考向 本題考查鏈表節點的插入
精點撥 t是新鏈表的尾指針，hb是鏈表db的當前節點指針。鏈表da頭節點是值最小的，成為新鏈表的頭節點，將鏈表db和原鏈表da第2個節點及后面所有節點采用尾插法合并到新鏈表da中。將鏈表db節點插入到新鏈表方法：當完成遍歷da鏈表或者da鏈表尾指針后面節點值比db鏈表當前節點值的大時，①將鏈表db當前節點值添加到鏈表da中，成為最后一個元素，新節點指向原鏈表da尾節點t的后繼q；②將尾節點t指向新添加的節點len(da)－1；③更新鏈表db的當前節點指針hb和鏈表da尾節點指針t。將鏈表da節點插入到新鏈表方法：由于鏈表的鏈接關系已經建立，只要更新尾節點t即可。新鏈表的尾節點無論是來自da還是db，均需要更新尾指針t，因此只要把這條語句放在判斷結構的下方即可
變式 列表a存儲了兩個升序鏈表的節點，每個節點包含數據區域和指針區域，頭指針分別為ha、hb，且a[ha][0]方框中應填入的正確代碼為(　　)
B
解析　本題考查鏈表節點的插入。由于a[ha][0]小于a[hb][0]，因此p從ha所在鏈表第2個節點開始遍歷，q為p的前驅，k遍歷hb所在鏈表。當條件a[p][0]<＝ a[k][0]成立時，q和p繼續遍歷；若條件不成立，將節點k插入到節點p的前面。
重難點4　循環鏈表及鏈表的簡單應用
循環鏈表是一種特殊的鏈式存儲結構，其中最后一個節點的指針指向頭節點，形成一個環。
例1 報數游戲。已知班上有n名學生(用編號1，2，3，……，n分別表示)，學生按照編號由小到大順時針圍成一個圓圈，從編號為1的學生開始順時針報數，報到m的同學出列；下一名同學又從1開始報數，報數為m的同學繼續出列；以此規律重復下去，直到剩下最后一位同學為止。
(1)當n＝6，m＝3時，最后留下的同學的編號是________。
(2)下列代碼通過構造一個循環單向鏈表，模擬報數的過程，逐一刪除報數為m的節點，直到剩下一個節點為止。請在劃線處填入合適的代碼。
思維點撥
明考向 本題考查循環鏈表的算法實現
精點撥 (1)3號和6號先出列，剩余編號為1245，4號和2號出列，接著5號出列，剩余1號。(2)①尾節點值為n，指向頭節點0。②從 1至m－1依次報數，共循環了m－1次。③當前節點指針從尾節點開始，連續進行m－1次報數后，下一個節點out將要被刪除，因此語句lst[p][1]＝lst[out][1]實現了刪除out節點的操作
答案　(1)1　(2)①[n，0]　②range(1，m)或range(m－1)　③lst[p][1]＝lst[out][1]
A
解析　本題考查循環鏈表以及隊列的算法實現。鏈表d構成一個循環鏈表，隊列依次為BAC，若a[i]的值能分配給隊首，則隊首元素出隊，否則更新剩余部分，再重新入隊。變量t是鏈表的尾指針，指針q從頭節點2開始遍歷，若當前節點d[q][0]大于a[i]，a[i]不夠分配，更新d[q][0]和尾指針t，同時i向后移動。若當前節點d[q][0]小于等于a[i]，刪除當前節點q，同時n的值減少1個，表示完成一個元素的分配，同時更新a[i]。″B″更新為2后入隊；″A″出隊，″C″更新為2后入隊；″B″出隊，″C″出隊。
例2 某編程興趣小組設計了一個點歌模擬程序，功能如下：
運行程序后，從鍵盤輸入“A”，則顯示已點的歌曲列表(歌單)；輸入“B”則可以自行輸入歌曲并添加到歌單以完成點歌；輸入“C”則可以將指定的歌曲置頂等待播放；輸入“D” 則播放當前第一首歌曲，并將該歌曲從列表中刪除；輸入“E”則關閉程序并退出。程序運行界面如圖所示。
請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A
God Is a Girl　十年　年少有為　七里香　淡季動物園
請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：B
請輸入歌曲：蘭亭序
請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：B
請輸入歌曲：想自由
請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A
God Is a Girl　十年　年少有為　七里香　淡季動物園　蘭亭序　想自由
請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：C
請輸入歌曲：七里香
請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A
七里香　God Is a Girl　十年　年少有為　淡季動物園　蘭亭序　想自由
請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：C
請輸入歌曲；想自由
請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A
想自由　七里香　God Is a Girl　十年　年少有為　淡季動物園　蘭亭序
請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：D
請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A
七里香　God Is a Girl　十年　年少有為　淡季動物園　蘭亭序
請輸入指令　A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：E
思維點撥
明考向 本題考查鏈表的操作
精點撥 ①輸入“B”則可以自行輸入歌曲并添加到歌單，新節點插入在尾節點的后面，因此原尾節點應指向新插入的節點，同時更新尾節點。②輸入“C”則可以將指定的歌曲置頂，data[cur][0]值為song表示找到節點cur，pre為cur節點的前驅，將cur移動到頭節點前面，因此需要3步，第1步是將cur的前驅pre指向cur的后繼，第2步是將cur指向原頭節點，第3步是設置新的頭節點為cur。③若cur是原尾節點tail，將cur修改為頭節點后，新的尾節點為cur的前驅。④輸入“D” 則播放當前第一首歌曲，并將該歌曲從列表中刪除，條件head＝＝tail成立表示鏈表中只有一個節點，否則將頭指針向后移動，刪除頭節點
答案　①data[tail][1]＝len(data)－1
②data[pre][1]＝data[cur][1]　③tail＝pre
④head＝data[head][1]
A.刪除該鏈表中的最后一個節點
B.刪除該鏈表中的第一個節點
C.在該鏈表第一個節點前插入一個新節點
D.在該鏈表最后一個節點后插入一個新節點
A
解析　本題考查鏈表的遍歷、插入和刪除操作。A選項刪除該鏈表中的最后一個節點，需修改最后一個節點的前驅節點指針域，因此需遍歷多個節點。B選項只需修改頭指針。C選項修改當前節點的指針值指向原頭節點，并修改頭指針為當前節點。D選項讓原尾節點指向當前節點，并修改尾節點為當前節點。
當堂檢測
4
重難點1　鏈表的遍歷
重難點2　鏈表節點的刪除
重難點3　鏈表節點的插入
重難點4　循環鏈表及鏈表的簡單應用
1.下列關于單向鏈表的說法正確的是(　　)
A.必定有頭指針和尾指針
B.每個節點都有一個后繼節點
C.刪除一個節點，需要修改兩個指針
D.查找任一節點的算法時間復雜度為O(n)
D
解析　本題考查鏈表相關知識。A選項單向鏈表必定有頭指針，不一定要有尾指針。B選項尾結點沒有后繼節點。C選項單向鏈表刪除一個節點，只需修改刪除節點的前驅節點的后繼指針即可。D選項鏈表的訪問比較低效，每次遍歷都需要從 head 頭結點開始，故算法時間復雜度為 O(n)。
C
解析　本題考查鏈表的構建和遍歷。L的后繼節點為O，因此其指針區域值為1；O的后續為V，指針區域值為0; V的后續為E，指針區域值為2；E為尾節點，因此指針區域值為－1。
2.使用列表模擬單鏈表，其存儲結構如圖所示，遍歷該鏈表，將訪問到的節點的數據域的字符依次連接，得到字符串‘LOVE’，則指針域中的索引值依次為(　　)
A.0 1 2 3 B.3 1 0 2
C.2 0 －1 1 D.2 0 1 －1
D
解析　本題主要考查鏈表的操作。head＝3，即對應列表索引3，其值為“rabbit”，指向索引為0的節點，其值為“cat”，依此類推，依次輸出各節點數據域的值，內容為″rabbit″，″cat″，″dog″，″pig″，故本題選D選項。
3.使用Python的二維列表來模擬單向鏈表，如下代碼創建一個擁有4個節點的鏈表a
a＝[[″cat″，1]，[″dog″，2]，[″pig″，－1]，[″rabbit″，0]]
head＝3
依次輸出各節點數據域的值，內容為(　　)
A.″cat″，″dog″，″pig″，″rabbit″ B.″pig″，″rabbit″，″cat″，″dog″
C.″pig″，″dog″，″cat″，″rabbit″ D.″rabbit″，″cat″，″dog″，″pig″
D
解析　本題考查鏈表遍歷和最值查找。當前節點從頭節點開始遍歷，最小值的初值為頭節點大小，因此需先移動到下一節點，再與最值進行比較，同時終止遍歷的條件是遍歷到尾節點馬上結束。
4.實現在鏈表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.②④
答案　D
解析　fast和slow分別表示快慢指針，fast每次遍歷2個節點，若遍歷完成后，fast的值為－1，表示節點數量為偶數，當a[fast][1]值為－1，遍歷到尾節點，節點數量為奇數，遍歷完成。
A
解析　只需修改data2的指針區域值修改為data4的指針區域值。
1.某單向鏈表如下圖所示，若要將數據 data3 和data4 同時從鏈表中移除，至少需要修改節點指針的數量是(　　)
A.1 B.2 C.3 D.4
D
解析　本題考查鏈表的基本操作。如果鏈表頭節點值為1，直接刪除頭節點，否則遍歷鏈表，語句a[pre][1]＝a[p][1]的作用讓節點p的前驅指向他的后繼，即刪除p節點。程序的功能是刪除元素值為1的節點。
C
解析　本題考查遍歷鏈表及刪除節點操作。①x是鏈表中一個節點位置，從鏈表中被刪除的數據a[x][0]。②判斷當前節點a[q]的值是否是要刪除的數據data。③遍歷鏈表，如果當前節點是要刪除的數據，且該節點是頭節點，需要更新頭指針head的值，若不是頭節點，需讓前驅節點p指向當前節點q的后繼節點。若當前節點的數據域不是 data，則將當前節點 p 更新為前驅節點 q，并繼續檢查下一個節點。
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]。
1.小張準備去多個城市旅游，他設計的行程若采用鏈表結構表示，如圖a所示。若行程有變，需在“上海”與“成都”之間增加一站“杭州”，鏈表修改為如圖b所示，有以下可選操作：
①“上海”所在節點的next值賦為“杭州”節點的next值
②“上海”所在節點的next值賦為5
③“杭州”所在節點的next值賦為“上海”所在節點的next值
④“杭州”所在節點的next值賦為－1
鏈表更新順序正確的是(　　)
A.③① B.③② C.①④ D.②④
B
解析　本題考查的知識點是鏈表元素的插入。鏈表中插入新元素并不需要進行元素位置移動，只需要進行節點指針域的更改即可。在“上海”與“成都”之間增加一站“杭州”，需要先將新元素“杭州”的指針域設置為“成都”所在位置，再更改節點“上海”的指針域至節點“杭州”所在位置。
B
解析　本題考查鏈表的插入。①自定義函數lnkid的功能是查找n在鏈表中插入位置，head在不斷地向后移動，因此n將和a[head][0]進行比較，當比a[head][0]小時，不斷地向后查找位置。②語句p＝lnkid(n，head)將返回在節點p的后面插入新的數n，因此將修改a[p]節點指針區域值為當前插入點索引。
A
解析　本題考查鏈表元素的遍歷和插入操作。程序的功能將鏈表b中的數據合并到鏈表a，形成一個新的降序序列存于鏈表a。分別遍歷兩個鏈表，若鏈表a當前元素值a[p][0]大于等于鏈表b當前元素值b[q][0]，則鏈表a向后遍歷，否則把鏈表b當前元素值b[q][0]插入到鏈表a當前元素前面。由于是要把鏈表b中的數據合并到鏈表a，因此鏈表b遍歷完成后，結束程序。
已知鏈表b的長度不超過鏈表a，則下列選項中，代碼順序正確的是(　　)
A.①④⑤ B.②③⑥ C.①④⑥ D.②③⑤
B
解析　本題考查鏈表節點的插入操作。程序將節點q插入到節點p的后面，因此q的指針域的值將發生變化，為了鏈表b正常遍歷，應先保存q的后繼。插入過程中，由于已經保存了q的后繼，因此可以先修改q的指向，再修改p的指向，最后將p移動到原插入節點q的后繼。
5.用鏈表模擬隊列操作(隊列長度大于1)，鏈表的每個節點包含數據區域和指針區域。指針head指向隊列的第一個元素，指針tail指向隊列的最后一個元素，如圖所示。現執行n次“出隊后立即入隊”操作，實現該功能的Python程序段如下：
上述程序段中方框處可選代碼有
①head＝que[head][1]　②que[tail][1]＝head
③que[head][1]＝－1　④que[p][1]＝－1
則方框內應填入的正確代碼順序為(　　)
A.①②③ B.①②④ C.②①③ D.②①④
D
解析　先采用尾插法將原頭節點鏈接入鏈表，接著更新尾頭節點，同時將新尾節點的指針區域值設置為1。
B
解析　本題考查循環鏈表的算法實現。每遍歷一次，i增加1，實現計數。第1次刪除節點2，第2次刪除節點4，第3、4、5分別刪除節點6、3、1，鏈表中只剩下節點5。
2.將A－K共13張黑桃撲克牌洗好后，把牌面朝下。第一張牌翻過來A，第2次將最上面第1張牌放到這疊牌的最下面，將第2張牌翻開，是黑桃2；第3次數將最上面第1、2張牌放到這疊牌的最下面，將第3張牌翻開，是黑桃3；依次類推將13張牌按從小到大的順序翻出。求這疊牌洗好后，從上到下的原始順序。
(1)程序運行結果如圖所示，結合下面代碼，當輸入撲克牌數量num為6時，撲克牌從上到下的初始順序最后輸出結果為：________。
請輸入撲克牌數量(1—13)：13
撲克牌從上到下的初始順序為：
A，8，2，5，10，3，Q，J，9，4，7，6，K，
解析　本題考查循環鏈表的算法實現。(1)若輸入6張牌，那么每次翻牌的位置依次是1, 3, 6, 2, 4, 5。將這些位置依次填入數字1－6，
位置 1 3 6 2 4 5
牌 A 4 2 5 6 3
可以得到原始的位置牌的點數。(2)①pre是當前節點cur的前驅，其初始值為尾節點位置。②變量i從0循環至，第i次循環時，翻了i張牌，因此需循環i次。③每次循環結束，獲取當前翻開牌的位置，并依次存入數組result。變量k從0循環至num－1，result[k]表示第k＋1張牌的位置，result[k]－1表示原始位置數組initial的索引位置，其值為k＋1。
課后練習
5
重難點1　鏈表的遍歷
重難點2　鏈表節點的刪除
重難點3　鏈表節點的插入
重難點4　循環鏈表及鏈表的簡單應用
D
解析　本題考查鏈表相關知識點。鏈表的訪問必須從頭節點開始。通過指針依次訪問，不能隨機訪問任何一個元素。
B
解析　沒有輸出尾結點，輸出前面4個節點的數據域，并以″→″結束，故答案為1→2→3→5→，選B。
3.王老師用鏈表模擬某次比賽中運動員的出場次序，運動員號碼存儲如下： a＝[[″e56″，4]，[″134″，－1]，[″215″，5]，[″098″，0]，[″144″，2]，[″024″，1]]。假設head＝3，小明同學的號碼是“215”，則他的出場次序是(　　)
A.2 B.4 C.5 D.6
B
解析　本題考查鏈表的遍歷。head值為3，[″098″，0]為頭節點，接著是[″e56″，4] [″144″，2] ，[″215″，5], [″024″，1], [″134″，－1]。
4.有如下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
C
解析　本題考查鏈表的遍歷。條件a[p][1]！＝－1表示當前節點的指針區域值為－1，即當前節點為尾節點。當遍歷到尾節點時，結束循環。
B
5.利用列表模擬非循環鏈表a(可能存在已被刪除的節點)，下列程序運行完畢后，變量p表示尾節點的節點位置是(　　)
解析　本題考查鏈表的遍歷。A選項當前節點為p，當遍歷到節點為空時停止遍歷，因此遍歷結束后，p節點為空，其前驅t為尾節點。B選項當前節點為p，若當前節點的指針區域值為－1，結束遍歷，那么當前節點p為尾節點。C選項當前節點從頭節點開始遍歷，a[a[p][1]]指當前節點的后繼節點，若該節點的指針區域值為－1，表示該節點為尾節點，當前節點為尾節點的前驅。D選項鏈表a可能存在已被刪除的節點，因此len(a)的值可能大于節點總數。
已知執行上述程序后，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]
B
解析　本題考查鏈表應用。data是一個鏈表，t指針從鏈表的第二個節點開始遍歷，1a指針是t節點的前驅，t節點減去前驅節點la的值小于key時，c計數，c的初值為0，計數到3時結束，也就是整個過程計數3次就結束，執行程序后t的值為6，也就是遍歷到最后一個節點時程序才結束。
解析　本題考查鏈表的遍歷。p為當前節點，從頭節點開始遍歷鏈表，將遍歷的新節點以頭插法的形式重新構建鏈表。q為新鏈表的頭節點，保存當前節點p的后續索引為tmp，先讓新鏈表的頭節點指向新鏈表的頭節點，再將頭指針指向p，p從原后續繼續遍歷原鏈表。
上述程序段中劃線處應填寫的代碼是(　　)
A.①elif a[pre][1]！＝a[i][1]　②que[head])
B.①if a[pre][1]！＝a[i][1] ②que[head]
C.①elif a[pre][1]！＝a[i][1] ②a[que[head]]
D.①if a[pre][1]！＝a[i][1] ②a[que[head]]
D
解析　程序借助隊列結構完成接力比賽男女隊員的交替接力。對隊列隊首隊員的性別和最近進入接力序列隊員的性別進行比較，若不同，則將隊列隊首元素出隊，否則繼續對a數組進行遍歷，若取到符合性別要求的元素則設定為下一趟性別比較的前驅，若性別與前一棒相同時則將該元素的索引置入等待隊列。
上述程序段中方框處可選的語句為：
①odd＝a[odd][1]　②even＝a[even][1]　③a[odd][1]＝a[even][1]　④a[even][1]＝a[odd][1]則方框處語句依次為(　　)
A.①③②④ B.①②③④
C.③②④① D.③①④②
D
解析　本題考查鏈表的插入。先分別獲取奇數節點連接而成的鏈表和偶數節點連接而成的鏈表；再連接兩個鏈表得到新鏈表。
1.由n個節點鏈接成的單鏈表如圖所示，其中head為頭指針。
C
解析　刪除指針p所指向的節點需修改其前驅head的指針區域，將該指針區域修改為p的后繼。
使用列表link模擬該鏈表結構，每個節點包含數據域和指針域，如圖中最后一個節點可以表示為[98，－1]。現要刪除指針p所指向的節點，可以實現該操作的語句有(　　)
①link[p][1]＝－1　②link[head][1]＝q　③link[head][1]＝link[p][1]　④head＝link[p][1]
A.①② B.①③ C.②③ D.②④
A
解析　本題考查鏈表的操作。當a[q]節點上的值與a[p]節點上的值相同時，q指針往后移一位。程序的功能是將與p指針所指示的節點值相同的a[q]節點刪除。指針t的作用是維護了去重后鏈表最后一個節點的位置。輸出鏈表的所有非重復節點。
A
解析　本題考查鏈表節點的刪除。在自定義函數guess中，當前節點p從cur節點的后繼開始，如果后面的元素與cur節點元素值相等，則刪除節點p，因此是從當前節點鏈表中刪除重復的元素。
D
解析　本題考查鏈表節點的刪除。①循環遍歷整個鏈表 。②q為當前元素指針，p是當前節點q的前驅，要刪除q節點，只需要修改p的指針為q的后繼。
C
解析　本題考查鏈表元素的刪除操作。該程序的算法思想為：遍歷鏈表，查找待刪除節點，找到后根據該節點為第一個節點或中間節點執行不同的刪除操作。
6.使用列表 d 模擬鏈表結構(節點數大于 1)，每個節點包含數據區域(數據均為整型，范圍為 0～9)和指 針區域，h 為頭指針，如圖a所示。現要對該鏈表節點進行去重操作，只保留最后一次出現的節 點，結果如圖b所示。實現該功能的程序段如下，方框中應填入的正確代碼為(　　)
答案　B
解析　考查鏈表節點的刪除。先遍歷將鏈表元素按數值放入 lst 數組中，lst 數組實現統計每個元素出現的個數。若個數小于 2 個，則保留，若大于等于兩個，則通過鏈表元素刪除，保留最后一次出現的節點。刪除鏈表節點分為兩種情況：1.刪除頭節點，通過修改頭指針為 h＝ d[h][1]實現；刪除非頭指針，q 為前驅節點，p 為當前節點，通過修改前驅節點指針域 d[q][1] ＝ d[p][1]，刪除當前 p 指向的節點。
答案　A
解析　當前節點p從頭節點開始遍歷鏈表d，q為節點p的前驅，若d[p][0]不在[begin，end]范圍內，更新當前指針p和前驅指針q。若d[p][0]在[begin，end]范圍內，分是否是頭節點兩種情況。如果是頭節點，更新head p的后繼d[p][1]，否則采用語句d[q][1]＝d[p][1]刪除當前節點p。無論刪除的是否是頭節點，均需要更新當前指針p。
B
解析　p的初值為第2個節點，因此程序的功能是若p節點前面存在一個節點的值與他相等，將他前面的節點刪除，因此(1)q從頭節點開始，遍歷到節點p為止。(2)如果兩個節點的數據區域值相等，刪除節點q。
D
解析　①處采用頭插法新增一個節點，頭指針為len(link)－1。②當前節點q從頭節點開始，不斷地向后查找小于或等于data的第1個節點。③當前節點q從頭節點開始遍歷，直到q為－1時，停止遍歷。
B
解析　原鏈表a存儲一個升序的數列，值依次為1，2，2，2，5，6，9，輸入一個數key，先在鏈表中查找大于key的第一個位置，并將該數插入到鏈表中，求插入的節點。
D
解析　本題考查鏈表的插入和進制轉換。程序的功能是十進制數轉成二進制數，并把結果取反。代碼a.append([r，head]); head＝len(a)－1的功能利用頭插法生成鏈表。
D
解析　先遍歷鏈表，找到pb的位置，tmp指向頭指針，pb>0表示不可能是頭指針，因此要和他下一個節點的值a[a[tmp][1]][0]進行比較。插入節點指向tmp的后繼。
D
解析　本題考查鏈表。先查找序列中最大數的位置maxp和該節點的前驅節點maxpre，pre為最后一個節點位置。再刪除最大數節點，分兩種情況，最大數節點為第一個節點或其他位置節點。如果是其他位置節點，需將該最大數節點的前驅節點指針區域指向該最大數節點的后繼節點位置，即a[maxpre][1]＝a[maxp][1]。最后將最大數節點插入鏈尾，原最后一個節點指針區域需指向最大數節點，最大數節點為新的最后一個節點，其指針區域為－1，即p，所以②a[maxp][1]＝p。
B
解析　考查鏈表中數據查找和插入操作。p、q 是二個前后相鄰的節點。根據 data>a[q][0]，可以推測出①為q！＝－1。循環結束后，應該在p節點之后插入節點，所以②處代碼是：a[p][1]＝len(a)。
解析　本題考查鏈表的相關知識。先建立了一個升序鏈表，接下來從head開始，查找key插入的位置。若key>a[p][0]則繼續向后找。本題key＝2，一開始就不滿足循環條件，2應插到鏈表頭部。首先向列表中追加key，并將指針指向head，同時調整head指針位置，故a[－1][0]＝2，指針a[－1][1]＝2。
C
8.某個正整數的每位數依次存儲在鏈表d中各節點的數據區域中。例如，正整數572存儲情況如圖a所示，h為d的頭指針。將該正整數翻倍后的計算結果(如572翻倍后的結果為1144)仍以這個鏈表存儲，最高位存儲于頭節點中，如圖b所示。實現該功能的程序段如下：
A
解析　當最高位數d[p][0]大于4(即5以上)時，其翻倍后的數將產生進位，因此需要新增加一個節點(默認在數據域插入0)，并將其作為新的頭節點h。p為高位節點，cur為p的后繼節點(節點cur是節點p的低位)。該利用鏈表實現的乘法算法的順序和常規乘法是相反的：先計算高位p然后再計算低位cur。p節點的數據域是本位數d[p][0]的2倍然后%10后的值，但這還不是d[p][0]的終值，還要看p的低位cur有沒有產生進位，若cur的數據域d[cur][0]大于4，則還會向p節點的數據域產生進位，由于最大的單位數9的2倍，其進位也只是1，因此每次在p節點原先的數據域d[p][0]基礎上加1。
D
解析　考查鏈表的基本操作。遍歷鏈表，將找到的女演員節點依次鏈接形成一個單獨的鏈表，同時將女演員節點從原鏈表刪除。操作完成后，原鏈表就是一個只有男演員的單向鏈表。指針q、r指向p的前驅和女演員鏈表的尾節點。將節點從原鏈表刪除前，先要鏈接到女演員鏈表尾節點。
B
解析　pre是p的前驅節點，p向后遍歷，當遍歷到第m個節點，需用語句a[pre][1]＝a[p][1]將節點p刪除。同時節點p需向后再遍歷一個節點，否則該節點將不存在，同時將計數器恢復至1。條件p！＝a[p][1]成立，表示鏈表中只剩下一個節點。
C
解析　本題考查循環鏈表的遍歷。h表示頭節點，值為0，在鏈表中有一個節點指向0，因此判定該鏈表為循環鏈表。當前節點p從頭節點開始遍歷，若當前節點指針區域值為頭節點，結束遍歷，即遍歷到尾節點終止循環，沒有輸出尾節點的值，循環結束后，再次輸出尾節點的值。
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。
4.小明設計了一個中華小曲庫，其中導入了10000首歌曲，包含4種類型(編號從0－3)，每首歌曲都有自己的歌曲編號，歌曲編號的第一位是其類型，比如某歌曲編號為00041，代表這是類型0的第42首歌。已知本曲庫有一個最近點播榜，分別記錄每種類型最近點播的5首歌，當點播歌曲時記錄規則如下：
①若榜單內不足5首歌，且被點播歌曲不在榜單上，則將其記錄在該類型樂曲榜單首位，如圖a所示，點播歌曲編號為20005，則在類型2的榜單榜首添加歌曲；若已在榜單上，則將其移至榜單首位，如圖b所示點播歌曲00021。
②若榜單內已有5首歌，則將榜尾的樂曲刪除，在榜首添加被點播歌曲，如圖c所示點播歌曲00006。
現有榜單：
00092##00008##00015##00001##00021##
10004##10018##10298##10022##
20001##
30065##
請輸入點播的歌曲：20005
現有榜單：
00092##00008##00015##00001##00021##
10004##10018##10298##10022##
20005##20001##
30065##
圖a
現有榜單：
00092##00008##00015##00001##00021##
10004##10018##10298##10022##
20005##20001##
30065##
請輸入點播的歌曲：00021
現有榜單：
00021##00092##00008##00015##00001##
10004##10018##10298##10022##
20005##20001##
30065##
圖b
現有榜單：
00021##00092##00008##00015##00001##
10004##10018##10298##10022##
20005##20001##
30065##
請輸入點播的歌曲：00006
現有榜單：
00006##00021##00092##00008##00015##
1000#10018##10298##10022##
20005##20001##
30065##
圖c
答案　(1)00008　(2)6　(3)①flag＝True
②flag and leader[kind][1]<5　③data[p][1]＝head
解析　(1)00005不在榜單中，且已有5首，刪除00015；00008和00005在榜單內，因此依次移到榜首，第2首歌的編號為0008。(2)num表示交換的次數，排序后的結果為[['ac'，1]，['ac'，1]，['abc'，2]，['bc'，2]，['c'，2]]，只要找出逆序對就可以求得num的值。[″bc″，2]與后面[″abc″，2]，[″ac″，1]，[″ac″，1]三對數據是逆序的。[″abc″，2]與[″c″，2]，[″ac″，1]是逆序對，[″c″，2]，[″ac″，1]是逆序對，因此需交換6次。(3)①自定義函數select中參數name表示點播歌曲名稱，kind表示類型，每種類型的歌曲建立一個鏈表，leader數組存儲每條鏈表的頭指針。點播歌曲時，首先要查找點播的歌曲是否在榜間內。若在榜單首位，不用任何操作，否則當前p從頭節點開始遍歷當前類型的鏈表，
判斷后繼data[data[p][1]]節點是否是當前點播歌曲name，若在榜單，則將該節點移到隊首，對flag賦值為False，因此①處應對flag賦初值為True。②滿足條件將該歌曲插入到榜單隊首，同時該類型的歌曲數量leader[kind][1]，那么其條件是當前歌曲不在榜單且該類型的歌曲數量小于5。③若歌曲不在榜單且該類型的歌曲已經超過5首，那么循環條件data[p][1]！＝－1不成立時，p節點是尾節點，q為尾節點前驅，語句data[q][1]＝－1功能是刪除尾節點p，將尾節點的值修改為當前點播歌曲，并指向原隊首head，更新leader[kind][0]后，該歌曲成為榜單的隊首節點。
5.某學校舉辦社團節，在一條直路的同側依次有n個社團展位，按展位到入口距離從1至n依次編號。從入口處走到第1個展位需要花費dis[0]單位時間，從第i個展位走到第i＋1個展位需要花費dis[i]單位時間。每個展位舉行若干活動，每參加一個活動需要5單位時間。對于第i個展位，第一次參加活動獲得a[i－1]個積分，第二次參加活動獲得a[i－1]－b[i－1]個積分，第三次參加活動獲得a[i－1]－2*b[i－1]個積分……以此類推。現在小明從入口處出發，他共有m單位時間自主選擇參與社團的活動并回到入口處。編寫程序實現規定時間內獲得最多積分的活動方案及獲得的積分數。
例：
展位 1 2 3
首次活動積分 10 15 20
每次下降的積分 4 6 4
與前一展位之間步行所花時間 1 3 4
若小明可用時間為28，部分方案如下：
方案1：參加前1個展位活動，有5次活動機會，可得積分為10＋6＋2＝18
方案2：參加前2個展位活動，有4次活動機會，可得積分為15＋10＋9＋6＝40
方案3：參加前3個展位活動，有2次活動機會，可得積分為20＋16＝36
則可獲得的最多積分為40，運行界面如圖所示。
展位數：3
可用時間：28
各展位首次參加活動可獲得的積分：10 15 20
各展位每次下降的積分：4 6 4
相鄰展位之間步行花費時間：1 3 4
能獲得的最多積分是：40
各展位參加的活動次數分別為：[2，2，0]
(1)若小明可用時間為32，按上表數據可得最多積分為________。
答案　(1)51　(2)B　(3)① dis[i] ＋ dis[i － 1]
②t > 0 and head ！＝ －1　③data[p][0] – data[p][1]或者data[p][0]－b[p]
解析　(1)第3個展臺距離入口所花時間為1＋3＋4＝8，往返需16，還可以有32－16＝16的時間用于活動，即可以完成3個活動，積分最大的20＋16＋15＝51。(2)insert函數功能是在首節點下標為head的鏈表中插入下標為r的節點，返回新的鏈首節點下標。當節點r數據區域值小于尾節點，條件data[r][0] < data[q][0]恒成立，q將越界。B選項鏈表的值依次為10，7，6，現將2插入到鏈表中。(3)①相鄰展位之間步行花費時間存入dis列表，從入口先到展位1，再到展位2，再到展位3，因此第i個展位需累加前面各個dis列表的值。②可用時間m減去返回時間2 * dis[i]得到可以參加活動時間，因此t表示參加活動數量。各展位首次參加活動可獲得的積分存入a列表，各展位每參加一次活動要下降的積分存入b列表，data數組中保存這兩組數據。并形成一個降序排列的鏈表。臨時方案是data數組中查找t個活動，因此需要2個條件。③每次在i個展位中找到一個最大的積分，因此將頭節點的值累加到total，同時去除該鏈表的頭節點。展位p每參加一次該活動，下一次參加該活動所得的積分減少b[p]，修改該節點的值，并重新生成一個新的降序鏈表。
6.某工程的A項目有n個任務組(編號為0～n－1)，供料商每小時只提供1份原料，各組按到達時刻(到達時刻各不相同)陸續加入領料隊列，領取1份原料后到隊列末尾重新等待，直至領完所需原料，離開隊列。若多組同時入隊，則到達時刻早的優先入隊。編寫程序模擬領料過程，先篩選出屬于A項目的任務組，再計算每個任務組完成領料的時刻(時間單位：小時)，請回答下列問題：
任務組別 到達時刻 原料需求量
第0組 0 3
第1組 1 2
第2組 2 1
圖a
時刻 領料隊列 輪到領料的組別
0 0 0
1 0，1 0
2 1，0，2 1
3 0，2，1 0
4
5 1 1
注：領料隊列中數字代表任務組編號
圖b
答案　(1)B　(2)3　(3)①p＝i　②k＝task[p][3]
③task[p][3]＝task[k][3]
解析　本題考查循環隊列的鏈式存儲運算。(1)領料組0已經完成領料，不再入隊，因此隊列中為2，1，正在領料的是2。(2)變量j從0開始遍歷，當條件task[j][0] ＝＝ st成立時，執行i ＋＝ 1，因此i表示st 的值是'A'的數量。(3)①ct表示當前時間，當條件task[i][1] <＝ ct成立，表示將索引i的task元素入隊。從條件task[k][2]＝＝ 0來看，表示該組任務完成，因此t表示完成任務的數量。當i和t相等時，表示鏈表隊列中數量為0，task[i]入隊后，當前隊列中只有一個元素，語句task[p][3] ＝ i表示節點p的后繼是i，訪元素的后繼是本身，這就符合循環隊列的特征，隊尾指向隊首。單向隊列中若已知隊尾可以得到隊首位置，已知隊首須遍歷鏈表才能得到隊尾，因此p為隊尾，初值為i。②當i大于t時，表示入隊的元素數量大于完成數量，需進行出隊操作，k為隊首指針，其值為隊尾p的后繼。③當隊首完成領料后，需從鏈表中刪除頭節點。

展開更多......

收起↑