資源簡介

專題12　鏈　表
學業要求 知　識　點 學業水平等級
1.能結合鏈表的應用案例，掌握鏈表的概念，了解鏈表組織、存儲結構的原理與特性 3
2.能根據問題特點規劃節點的數據域和指針域，完成創建鏈表、訪問、刪除、插入鏈表節點的操作 4
知識點一　鏈表的遍歷
【知識梳理】
1.鏈表是將需要處理的數據對象以________的形式，通過指針串聯在一起的一種數據結構。
2.同一個鏈表中每個節點的________均相同，由數據區域和指針區域組成。
3.每個鏈表都有一個________指針head，是鏈表的入口，也便于循環鏈表在數據處理時的邊界判斷和處理。
4.鏈表可以根據每個節點中指針的數量分為________向鏈表和________向鏈表。
5.若鏈表data每個節點只有一個值和一個指針，當前節點為q，則他的后繼節點即下一個節點的索引是________。
6.前節點q初值為頭指針head，通過語句q＝data[q][1]遍歷整個鏈表，當q的值為________時結束鏈表遍歷。
7.當鏈表遍歷結束后，q的值為－1，其前驅為________節點。
【經典案例】
單向鏈表是由節點構成，head指針指向第一個成為表頭節點，而終止于最后一個指向－1的指針。對鏈表的訪問要通過順序讀取從頭部開始。鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表的遍歷必須從頭節點開始，每個節點包含數據區域和指針區域，數據區域可能有多個值，指針區域值往往在節點最后一個位置。若當前q指向頭指針head，那么a[q]是整個節點的值，a[q][0]是數據區域的值，a[q][1]是下一節點的索引，通過語句q＝a[q][1]，實現指針向后移動。
【例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時，表示遍歷完了
聽課筆記：____________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式1】 某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
【例2】 使用鏈表結構模擬某景區游玩路線，鏈表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.②④③
思維點撥
明考向 本題考查多條鏈表的遍歷
精點撥 3條鏈表構建在數組a中，頭指針存儲在數組head中，需遍歷頭指針數組，從而來遍歷3條鏈表。(1)處為當前節點賦值為頭指針head[i]，變量s存儲所有節點游覽總時間。(2)(3)遍歷鏈表，并統計各個節點游覽時間和，由于當前節點已經計入總時間，因此先要跳轉到下一點，將下一節點的時間加入到總時間，注意遍歷結束的條件是當遍歷到尾節點時，終止遍歷
聽課筆記：___________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式2】 實現在鏈表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.②④
知識點二　鏈表節點的刪除
【知識梳理】
1.鏈表占用的空間不穩定，可根據需求增刪________，提高空間的利用率。
2.刪除鏈表頭節點往往修改頭指針的值，將頭指針指向原頭指針的________即可。
3.若鏈表data每個節點只有一個值和一個指針，其頭指針為head，則刪除頭指針的語句為head＝________。
4.刪除鏈表其他節點含尾節點的方法是：修改刪除節點的前驅節點指針區域值，使其前驅節點直接指向刪除節點的________。
5.若鏈表data每個節點只有一個值和一個指針，當前節點q的前驅節點為pre，則刪除當前節點q的語句為________________。
【經典案例】
在數組中刪除某個節點，往往需把該節點后面的值往前移，時間復雜度為線性階O(n)。鏈表節點的刪除分為頭節點的刪除和其他節點的刪除，頭節點的刪除只要移動頭指針到下一節點，即head＝a[head][1]即可，其他節點的刪除，只要修改該節點的前驅節點的指針區域值為該節點的后繼節點索引即可，時間復雜度為常量階O(1)。
【例題】 有如下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
思維點撥
明考向 本題考查鏈表節點的刪除
精點撥 在自定義函數guess中，當前節點p從cur節點的后繼開始，如果后面的元素與cur節點元素值相等，則刪除節點p，因此是從當前節點鏈表中刪除重復的元素
聽課筆記：___________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式】 已知鏈表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]
知識點三　鏈表節點的插入
【知識梳理】
1.新節點插入往往通過append方法，將新增加節點添加到數組data最后位置，其節點索引值為________。
2.可以在原鏈表的頭節點前插入一個值為x的新節點，步驟一新增一個節點并讓該節點的指針區域值為原________節點data.append([x，head])，步驟二修改頭指針head的值為新節點索引head＝len(data)－1。
3.在當前節點q(q不是頭節點)前插入一個值為x的新節點，步驟一新增一個節點并讓該節點的指針區域值為該節點索引data.append([x，q])，步驟二修改當前節點的________節點指針區域值為新節點索引data[pre][1]＝len(data)－1。
4.在實現鏈式隊列時，往往增加一個尾指針來指向鏈表最后一個節點，若有新節點增加到尾節點后面時，只要將原________節點指向新增節點，同時修改尾指針即可，語句分為data.append([x，－1])，data[tail][1]＝len(data)－1。
【經典案例】
在數組中插入節點的時間復雜度為線性階O(n)，與數組相比，只能通過頭指針進入鏈表，鏈表節點的訪問效率較低，但是插入節點的時間復雜度為常量階O(1)。鏈表節點的插入分為在頭節點前的插入和其他節點前插入兩種，頭節點前插入新節點，該節點指向原頭節點，并要修改head指針。在當前節點q前插入新節點，該新節點的后續是q，將修改q的前驅節點指針區域值。
【例1】 某電影演員表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.②③①
思維點撥
明考向 本題考查鏈表的基本操作
精點撥 遍歷鏈表，將找到的女演員節點依次鏈接形成一個單獨的鏈表，同時將女演員節點從原鏈表刪除。操作完成后，原鏈表就是一個只有男演員的單向鏈表。指針q、r指向p的前驅和女演員鏈表的尾節點。將節點從原鏈表刪除前，先要鏈接到女演員鏈表尾節點
聽課筆記：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式】 有如下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)
【例2】 某編程興趣小組設計了一個點歌模擬程序，功能如下：
運行程序后，從鍵盤輸入“A”，則顯示已點的歌曲列表(歌單)；輸入“B”則可以自行輸入歌曲并添加到歌單以完成點歌；輸入“C”則可以將指定的歌曲置頂等待播放；輸入“D”則播放當前第一首歌曲，并將該歌曲從列表中刪除；輸入“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成立表示鏈表中只有一個節點，否則將頭指針向后移動，刪除頭節點
聽課筆記：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
1.對于鏈表的描述，下列說法不正確的是(　　)
A.同一鏈表中每個節點的結構均相同
B.每個鏈表必定有一個頭指針
C.鏈表占用的空間不固定
D.創建的新鏈表中至少要有一個節點
2.使用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″
3.利用列表模擬非循環鏈表a(可能存在已被刪除的節點)，下列程序運行完畢后，變量p表示尾節點的節點位置是(　　)
A.head＝0
p＝head
while p！＝－1：
t＝p
p＝a[p][1]
B.head＝0
p＝head
while a[p][1]！＝－1：
p＝a[p][1]
C.head＝0
p＝head
while a[a[p][1]][1]！＝－1：
p＝a[p][1]
D.head＝0；p＝head
n＝len(a)
while n>1：
p＝a[p][1]
n－1＝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
5.有如下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
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所示。
若行程有變，需在“上海”與“成都”之間增加一站“杭州”，鏈表修改為如圖b所示，有以下可選操作：
①“上海”所在節點的next值賦為“杭州”節點的next值
②“上海”所在節點的next值賦為5
③“杭州”所在節點的next值賦為“上海”所在節點的next值
④“杭州”所在節點的next值賦為－1鏈表更新順序正確的是(　　)
A.③① B.③② C.①④ D.②④
8.有兩個降序序列的鏈表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.②⑥③
9.在一個單向鏈表(如圖)中，若在尾指針tail所指節點之后插入新節點(r所指節點)，則執行的操作是(　　)
A.tail所指節點的data3值賦為r所指節點的data4值
B.r所指節點的next值賦為tail
C.r所指節點的next值賦為－1
D.tail所指節點的next賦為r，r所指節點的next值賦為－1
10.將兩個鏈表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.②③⑤
專題12　鏈　表
知識點一
知識梳理
1.節點　2.結構　3.頭　4.單　雙　5.data[q][1] 6.－1　7.尾
經典案例
例1　A
變式1　C　[本題考查循環鏈表的遍歷。h表示頭節點，值為0，在鏈表中有一個節點指向0，因此判定該鏈表為循環鏈表。當前節點p從頭節點開始遍歷，若當前節點指針區域值為頭節點，結束遍歷，即遍歷到尾節點終止循環，沒有輸出尾節點的值，循環結束后，再次輸出尾節點的值。]
例2　D
變式2　D　[本題考查鏈表遍歷和最值查找。當前節點從頭節點開始遍歷，最小值的初值為頭節點大小，因此需先移動到下一節點，再與最值進行比較，同時終止遍歷的條件是遍歷到尾節點馬上結束。]
知識點二
知識梳理
1.節點　2.后繼　3.data[head][1]　4.后繼 5.data[pre][1]＝data[q][1]
經典案例
例題　A
變式　D　[本題考查鏈表節點的刪除。①循環遍歷整個鏈表。②q為當前元素指針，p是當前節點q的前驅，要刪除q節點，只需要修改p的指針為q的后繼。]
知識點三
知識梳理
1.len(data)－1　2.頭　3.前驅　4.尾
經典案例
例1　D
變式　B　[本題考查鏈表的插入。①自定義函數lnkid的功能是查找n在鏈表中插入位置，head在不斷地向后移動，因此n將和a[head][0]進行比較，當比a[head][0]小時，不斷地向后查找位置。②語句p＝lnkid(n，head)將返回在節點p的后面插入新的數n，因此將修改a[p]節點指針區域值為當前插入點索引。]
例2　①data[tail][1]＝len(data)－1　②data[pre][1]＝data[cur][1]　③tail＝pre　④head＝data[head][1]
當堂過關檢測
1.D　[本題考查鏈表的基本性質。A選項鏈表節點包含數據區域和指針區域，每個節點中的數據區域中數據類型是相同的。B選項訪問鏈表的某一節點，只能從頭指針開始，依次訪問。C選項鏈表通過指針相連，相信節點存儲時不需要連續空間，因此鏈表空間是不固定的。D選項可以是空鏈表，數據區域為空，頭指針為－1。]
2.D　[本題主要考查鏈表的操作。head＝3，即對應列表索引3，其值為“rabbit”，指向索引為0的節點，其值為“cat”，依次類推，依次輸出各節點數據域的值，內容為″rabbit″，″cat″，″dog″，″pig″。]
3.B　[本題考查鏈表的遍歷。A選項當前節點為p，當遍歷到節點為空時停止遍歷，因此遍歷結束后，p節點為空，其前驅t為尾節點。B選項當前節點為p，若當前節點的指針區域值為－1，結束遍歷，那么當前節點p為尾節點。C選項當前節點從頭節點開始遍歷，a[a[p][1]]指當前節點的后繼節點，若該節點的指針區域值為－1，表示該節點為尾節點，當前節點為尾節點的前驅。D選項鏈表a可能存在已被刪除的節點，因此len(a)的值可能大于節點總數。]
4.C　[本題考查鏈表的遍歷。條件a[p][1]！＝－1表示當前節點的指針區域值為－1，即當前節點為尾節點。當遍歷到尾節點時，結束循環。]
5.A　[本題考查鏈表的操作。當a[q]節點上的值與a[p]節點上的值相同時，q指針往后移一位。程序的功能是將與p指針所指示的節點值相同的a[q]節點刪除。指針t的作用是維護了去重后鏈表最后一個節點的位置。輸出鏈表的所有非重復節點。]
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　[本題考查的知識點是鏈表元素的插入。鏈表中插入新元素并不需要進行元素位置移動，只需要進行節點指針域的更改即可。在“上海”與“成都”之間增加一站“杭州”，需要先將新元素“杭州”的指針域設置為“成都”所在位置，再更改節點“上海”的指針域至節點“杭州”所在位置。]
8.A　[(1)將鏈表b中的數據合并到鏈表a，兩個節點數據區域值比較，如果鏈表a中值大于等于鏈表b中值，無需合并。(2)將鏈表b中的數據添加到鏈表a時，添加數據區域值為b[p][0]，指向p。(3)將前驅指向新增節點位置。]
9.D　[本題主要考查鏈表的操作。鏈表中尾結點的next指針為－1，若在尾指針tail所指節點之后插入新節點(r所指節點)，則執行的操作是：tail所指節點的next賦為r，r所指節點的next值賦為－1。]
10.B　[本題考查鏈表節點的插入操作。程序將節點q插入到節點p的后面，因此q的指針域的值將發生變化，為了鏈表b正常遍歷，應先保存q的后繼。插入過程中，由于已經保存了q的后繼，因此可以先修改q的指向，再修改p的指向，最后將p移動到原插入節點q的后繼。]

展開更多......

收起↑