資源簡介

第二章　數組與鏈表
課時1　數　組
一、基礎鞏固
1. 有如下Python程序段：
a＝[4，4，4，9，4，9，6，4，4]
s＝[0，0，0，0，0，0，0，0，0]
for i in range(0，len(a)，2)：
　 s[a[i]]＋＝1
print(s[4])
執行程序段，輸出結果的是(　　)
A.6 B.5 C.4 D.3
2.已知二維數組a＝[[1，3，5]，[2，4，6]，[7，8，9]]，執行語句s＝a[1][2]＋a[2][1]后，變量s的值為(　　)
A.5 B.11 C.13 D.14
3.有如下Python程序段：
b＝[11，4，17，19，3，8，19，5]
k＝0
for i in range(1，len(b))：
if b[i]>b[k]：
k＝i
b.pop(k)
程序段執行后，數組b中的元素為(　　)
A.11，4，17，19，3，8，19，5
B.11，4，17，3，8，19，5
C.11，4，17，19，3，8，5
D.11，4，17，19，3，8，19
4.有如下Python程序段：
s＝0
a＝[[2，8，3]，[1，6，4]，[5，7，9]]
for i in range(3)：
for j in range(3)：
if i＝＝j：
　　　　 s＝s＋a[i][j]
程序段執行后，變量s的值為(　　)
A.11 B.14 C.17 D.21
5.有如下Python程序段：
a＝[[i＋1 for i in range(4)] for j in range(3)]
for i in range(3)：
for j in range(4)：
a[i][j]＝a[i][j]＋4*i
則程序執行后，a[1][2]的值為(　　)
A.2 B.4 C.7 D.8
6.有如下Python程序段：
num＝[0]*10
n＝36
s＝0
for i in range(n)：
　 j＝9
　 num[j]＋＝1
　while num[j]＝＝2：
num[j]＝0
j－＝1
num[j]＋＝1
for i in range(10)：
　 s＋＝num[i]
print(s)
執行此代碼后，變量s的值為(　　)
A.2 B.3 C.4 D.5
7.查找素數能夠很好地體現出計算機解決某些數學問題的速度優勢，除了計算機性能以外，設計更加簡單的算法也能夠提高計算機解決某些問題的速度。某種素數算法就是通過“開關”的思想，例如求100以內的所有素數，采用數組來表示[1，1，1，……，1，1，1]，數組的索引值表示0～99中的每個數，1表示“開”即為素數(先假設都為素數))，從2(0和1不是素數)開始，因為索引2號對應的值為1，則2是素數，再將后面能夠被2整除的索引對應的值都改為0，依次類推……以下程序就是采用這種思路編寫的輸出1000以內的所有素數的程序：
lst1＝[]　　　　　# 存放每個數的開關
lst2＝[] # 存放找到的素數
lst1＝[1]*1000 # 初始化開關列表
for i in range(2，1000)：
if lst 1[i]＝＝1：
lst2.append(i)
________：
　　 lst1[j]＝0
print(lst2)　 # 輸出所有1000以內的素數
上述程序橫線處的合適代碼為(　　)
A.if lst1[j]%i＝＝0
B.if lst1[i]%i＝＝0
C.for j in range(i，1000，i)
D.for j in range(i＋1，1000，i)
8.某次測試的答題結果存儲在asht.txt文件中，該文件每行記錄1個考生10道單選題的答案，每題有A，B，C，D四個選項，空白的答案標記為'K'。評分標準：正確得3分，錯誤得－1分，空白得0分。實現評分的Python程序如下。
ANS＝'ACBBCDADBC' #ANS 為標準答案
score＝[]
for line in open('asht.txt'，'r'):
　 score.append(0)
　 i＝len(score)－1
　 j＝0
　 while j　 if ①____________：
　　　 score[i]＋＝3
　 elif line[j]！＝'K'：
　　　 ②______________
j＋＝1
print(score)
(1)若標準答案為：'ACBBCDADBC'，則答案'ACBBDDADKC'的得分為________。
(2)完善上述①②處代碼。
二、能力提升
9.下列程序的功能是：輸入一個由大小寫字母和數字組成的字符串，統計字符串中出現次數最多的小寫字母。
程序運行界面如下圖所示：
實現上述功能的Python程序如下，請在程序劃線處填入合適的代碼。
s＝input(″輸入字符串：″)
a＝[0]*26
for i in range(len(s))：
if ″z″>＝s[i]>＝″a″：
①________________
a[n]＋＝1
max＝0
for i in range(26)：
if a[i]>max：
max＝a[i]
②________________
print(chr(ord(″a″)＋posi)，″times：″，max)
10.某物品柜有5層，每層有10個格子，每個格子只能放一個物品。輸入一組物品的高度值(按降序排列)，將這些物品放在同一層的連續格子中。第一步：查找存放物品的格子。從第1層開始查找，若該層物品柜連續空格數量小于物品數量，則查找下一層。查找5層后還是不能找到連續存放位置，輸出“不能連續存放”。若在某一層中找到符合要求的連續空格子，則進行第二步：將物品按中間高兩端低的原則存放物品。先將高度最高的物品存放在連續空格的中間位置(若空格數量為偶數，則放在中間靠左位置)，接著依次將物品按先右后左的順序依次存放。如輸入物品高度為8，5，2，1，則依次放在第1排的第5，6，4，7的位置。第一排各個格子存放物品高度如圖所示，其中0表示未存放物品。
0 0 0 2 8 5 1 0 0 0
(1)輸入第1組物品高度依次為8，5，2，第2組依次為9，6，3，1，則高度為3的物品存放在第1排第__________(填數字)個格子中。
(2)實現該功能的Python程序段如下，請在程序劃線處填入合適的代碼。
#將已經存放的物品高度存儲在數組a中，如：
[[0，9，6，2，8，5，1，0，0，0]，[0，0，1，7，10，9，2，0，0，0]，……]，代碼略。
s＝input(″輸入一組降序的物品高度，用逗號分開：″)
wp＝list(map(int，s.split(″，″))) #輸入的數字轉換成列表
flag＝False；i＝0
while i<5 and not flag：
　 beg＝0　
　 for j in range(10)：
　 if a[i][j]＝＝0: #物品柜格子為0表示沒有存放物品
　　　 if j－beg＋1>＝len(wp)：
　　　　hang＝i；end＝j；flag＝True
　 else：
　　　 if flag ：
　　　　 break
　　　 ①______________
i＋＝1
if flag：
②____________
a[hang][wz]＝wp[0]
i＝1
while iif ③____________：
　　　　 wz－＝i
else：
　　　　wz＋＝i
a[hang][wz]＝wp[i]
i＋＝1
else：
print(″不能連續存放″)
#輸出物品柜的存放情況，代碼略
11.楊輝三角，是二項式系數在三角形中的一種幾何排列，在我國南宋數學家楊輝1261年所編寫的《詳解九章算法》一書中出現。我們可以把楊輝三角看作這樣的圖形：最左側一列數字和右邊的斜邊數字均為1，內部其他位置上的每個數字均為上一行同一列的數字與上一行前一列數字之和，前10行的楊輝三角如圖所示。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
為了在計算機存儲和處理上述的數據，可用數組表示。實現輸出該圖形的代碼如下，在程序劃線處填入適當的語句或表達式，將程序補充完整。
n＝int(input(″請輸入行數n＝：″))
pa＝[1]*100
k＝1　　#變量k存儲上一行的下標起始位置
for i in range(2，n)：
t＝k＋i＋1　#變量t存儲當前行的下標起始位置
for j in range(i－1)：
　　 　pa[t＋j]＝pa[k＋j]＋①____________
k＝k＋i
k＝0
for i in range(n)：　 #輸出第0到n－1共n行的數據
s＝″″
for j in range(i＋1)：
　s＝s＋″　″＋　②__________________
　　k＋＝1
print(s)
12.編寫“矩形面積”程序，實現如下功能：隨機生成一個包含0或1的10×10的二維數組a；當數組元素的值為0時表示沒有障礙物，當數組元素的值為1時有障礙物。尋找陣列中構造出的最大面積的矩形面積和起點坐標。程序運行界面如圖所示。
(1)實現上述功能的Python程序如下，請在劃線處填入合適的代碼。
(2)程序中加框處代碼有錯，請改正。　
實現上述功能的Python代碼如下：
def Check(a，x，y): #在數組a中從點x，y開始向右向下查找最大矩形面積
i＝x；maxx＝0；n＝10；jn＝10
while iif ①____________：
　　　　 break
j＝y＋1；s＝0
while j　　　 　j＋＝1
②____________
jn＝j #更新右邊界，從該位置開始，右邊的區域不能計算面積
if s>maxx：
　　　 maxx＝s
i＋＝1
return maxx
#產生一個10*10的初值為0的二維數組a，并隨機產生若干個障礙物，將數組a中的值修改為1，代碼略
n＝0；maxx＝0；px＝0；py＝0；t＝0
for i in range(n)：
for j in range(n)：
　 if ：
　　　 ③____________
　if t>maxx：
　　　　　maxx＝t
　　　　　px＝i＋1
　　　　　py＝j＋1
print(″構成的最大面積是：″，maxx，″。起點坐標為：″，px，py)
課時1 數組
1.C　[本題考查記數統計。統計奇數位置上4的個數。]
2.D　[本題主要考查的是二維數組的運算。a[1][2]是指數組a中第2行第3個元素，即a[1][2]＝6, a[2][1]是指數組a中第3行第2個元素，即a[2][1]＝8，因此s＝14，答案為D。]
3.B　[本題主要考查的是一維數組的操作。本程序的功能是找出數組b中值最大的元素所在的位置，然后將該位置上的元素從數組b中刪除，根據程序代碼可知，若值最大的元素有多個時，k記錄的是第一個最大值的位置，因此，操作后數組b中的元素為“11，4，17，3，8，19，5”，故答案為B。]
4.C　[本題主要考查的是二維數組的操作。本程序的功能是求二維數組中正對角線上的元素之和，即s＝2＋6＋9＝17，因此答案為C。]
5.C　[本題主要考查的是二維數組的定義與賦值。本程序的功能首先為3行4列的二維數組a賦值 [[1，2，3，4]，[1，2，3，4]，[1，2，3，4]]，然后依次給二維數組a加4*i，a[1][2]即為第2行第3列的值為7，故答案為C。]
6.A　[本題主要考查的是數組的應用。題目中的程序實現的是進制數的轉換，變量i從 0循環到35，每次循環j從9開始，對該位置上的值加1，當該位置上的值滿2時，該位置上的值變為0，向j－1位置上進1。因此程序的功能是將36轉成二進制，其值為100100，將二進制位置上的各值進行累加，和為2，答案為A。]
7.C　[本題主要考查的是數組的應用。按照題意，程序的外層for循環列舉所有1000以內的可能素數，作為數組lst1的下標位置，如果該位置對應的數組元素值為1，作為素數存入數組lst2，同時按照素數的性質排除后面的為該素數的整數倍的整數判定為非素數，所以劃線處即列舉該數的倍數整數，答案為C。]
8. (1)23　(2)①line[j]＝＝ANS[j]　 ②score[i]－＝1
解析　本題考查順序查找算法。line表示asht.txt文件中每一條記錄，每條記錄有10道單選題答案。語句score.append(0)表示每讀取一條記錄，該列表增加一個值為0的元素，i表示score列表中最后一個元素的索引值。j初值為0，終值為len(ANS)－1，表示在標準答案中比對當前記錄中答案，如果line[j]＝＝ANS[j]表示當前答案與標準答案一致，得3分，不正確將扣1分。
9.①n＝ord(s[i])－ord(″a″)　 ②posi＝i
解析　本題主要考查的是數組的綜合應用。本題的算法思想是：將小寫字母a～z出現的次數依次記錄在數組元素a[0]～a[25]中，然后求出a[0]～a[25]中的最大值，并記錄在變量max中，將字母序號記錄在變量posi中，從而求得問題的解。①處代碼的功能是求出當前小寫字母在字母表中的序號n，因此①處代碼為n＝ord(s[i])－ord(″a″)。劃線②處代碼的功能是用posi記錄當前出現次數最多的字母在字母表的序號，因此②處代碼為posi＝i。
10.(1)7　(2)①beg＝j＋1　②wz＝(beg＋end)∥2　③i%2＝＝0
解析　本題考查二維數組的遍歷和在一個序列中查找最值。(1)高度8，5，2依次存放第5、6、4的格子中，因此左邊還有3個空格，右邊有4個空格。高度9，6，3，1依次存放第8、9、7、10的格子中。(2)①確定連續空格子的最左邊位置beg，若格子為空，計算連續空格子數量為j－beg＋1，若數量達到存放物品數量時，將flag設置為True。若格子不為空，則下一個空格子的位置只能在當前j的下一個位置。②中間位置的計算方法類似于二分查找，將左右位置相加再整除以2。③語句a[hang][wz]＝wp[0]的功能是放置最中間的物品，接下來放在i為1的物品，在中間的右邊，即wz等于i＋1，當i的值為2時，放在左邊的前面2個位置中，因此通過判斷變量i的奇偶性來決定存放的位置。
11.①pa[k＋j＋1]　②str(pa[k])
解析　本題主要考查的是數組的綜合應用。根據題意分析可知，計算數組的新值可通過上一行兩個連續的數組值相加獲得，前一個值為pa[k＋j]，因此①處代碼為pa[k＋j＋1]；②處為每一行數據的輸出，變量s存儲每一行的數據，注意數組pa的類型，需使用str()函數進行轉換。
12.(1)①a[i][y]＝＝1　②s＝(i－x＋1)*(j－y)　③t＝Check(a，i，j)　(2)a[i][j]！＝1
解析　本題考查二維數組和枚舉算法。將矩陣的每個點作為起點，從該點開始，不斷地向右檢測，找到能構成矩形的最右邊界，向下檢測，找到下邊界，計算矩形面積，并找出最大面積。自定義函數功能在數組a中從點x，y開始向右向下查找最大矩形面積，終點坐標是(i，j)，先不斷地向右查找，若找到1停止，此時的右邊界為j－1，再向下一行枚舉，若下一行的y位置是1，則不能向下構成矩形，結束查找，因此①表示檢測到新行的第1列就是障礙物。②計算矩形面積，表示第x行與第i行，第y列與第j－1列構成的矩形面積。③調用自定義函數計算該坐標開始的最大矩形面積。(2)起點不能是障礙物。課時2　鏈　表
一、基礎鞏固
1.下列有關鏈表的說法中，正確的是(　　)
A.每個鏈表的表頭一定有一個頭指針，以實現對鏈表的引用和邊界處理
B.在單向鏈表中，最后一個節點的指針指向第一個節點
C.鏈表一旦創建好后，它占用的空間將固定
D.鏈表的頭指針指向第一個節點，因此不能刪除第一個節點
2.設指針變量p指向單向鏈表lst的某中間節點，如圖所示，則刪除該節點的后繼節點的正確操作是(　　)
A.lst[p][next]＝lst[p][next] [next]
B.p＝lst[p][next][next]
C.lst[p][next]＝lst[lst[p][next]][next]
D.t＝lst[p][next]；p＝lst[t][next]
3.某公交路線的站點名稱、經度、緯度和下一個站點序號(經緯度已轉換為平面坐標 數據)存儲在數組 a 中，現計算相鄰兩個站點距離的總和。
import math
a＝[[″廊橋″，3，2，3]，[″徐岙″，6，11，2]，[″北門″，13，8，－1]，[″上通″，3，7，1]]
head＝0 ; s＝0 p＝a[head][3]
while (1)________：
s＋＝math.sqrt((a[p][1]－a[head][1])**2＋(a[p][2]－a[head][2])**2)
(2)________
(3)________
print(s)
上述程序段劃線處可選的代碼為：
①a[head][3]！＝－1　②head＝p　③p＝a[head][3] ④head！＝－1
則(1)、(2)、(3)處的代碼依次為(　　)
A.①②③ B.④②③ C.④③② D.①③②
4.已知鏈表 a 中的每個節點包含數據區域和指針區域兩部分，下列 Python 程序段的功能是在鏈表 a 中刪除數據值為 key 的所有節點。
key＝int(input(″輸入要刪除的數據：″))
head＝0
while head！＝－1 and a[head][0]＝＝key ：
　　head＝a[head][1]
p＝q＝head
if head！＝－1:
　　q＝a[q][1]
　　while ①____________：
if a[q][0]＝＝key：
　　　　　②____________
else：
　　　 p＝a[p][1]
　　　q＝a[q][1]
則劃線①②處的代碼分別為(　　)
A.①a[q][1]！＝－1　 ②a[p][1]＝a[q][1]
B.①a[q][1]！＝－1 ②a[q][1]＝a[p][1]
C.①q！＝－1 ②a[q][1]＝a[p][1]
D.①q！＝－1 ②a[p][1]＝a[q][1]
5.使用Python的二維列表來模擬單向鏈表，每個節點都是一個列表，其第一個元素存儲數據，第二個元素存儲指向后繼節點的指針。若要刪除節點a[p]的后繼節點，則需執行語句(　　)
A.p＝a[p][1]
B.a[a[p][1]][1]＝a[p][1]
C.a[p][0]＝a[a[p][1]][0]
D.a[p][1]＝a[a[p][1]][1]
6.用Python程序實現刪除鏈表的倒數第n(n不大于鏈表長度)個節點，如n＝2時，鏈表
更新為
部分代碼如下：
#讀入鏈表存儲在列表s中，head存儲鏈表的頭節點，代碼略
n＝int(input())
p1＝p2＝head
while p2！＝－1：
　　if n>＝0：
(1)____
n－＝1
　　else：
(2)____
p2＝s[p2][1]
if p1＝＝head and n>＝0：
　head＝s[head][1]
else：
　　(3)____
上述程序段中劃線處可選的語句為：
①p1＝s[p1][1]　②p2＝s[p2][1]
③s[p1][1]＝s[s[p1][1]][1]
④s[p2][1]＝s[s[p2][1]][1]
則(1)～(3)劃線處語句依次為(　　)
A.①③④ B.①④③ C.②①④ D.②①③
7.在升序鏈表 a 中插入一個不重復數據 data，仍保持鏈表的升序狀態。使用 python 程序實現插入操作，代碼如下：
data＝[[20，4]，[6，3]，[35，5]，[18，0]，[27，2]，[59，－1]]
p＝head＝1
data＝int(input())
if data<＝a[head][0]:
　a.append([data，head])
　head＝len(a)－1
else：
　　q＝a[p][1]
　　while ①____and data>a[q][0]：
　p＝q
　q＝a[p][1]
　　②____
a.append([data，q])
則劃線處的代碼為(　　)
A.①p！＝－1　②a[p][1]＝len(a)－1
B.①q！＝－1 ②a[p][1]＝len(a)
C.①q！＝－1 ②a[q][1]＝len(a)－1
D.①p！＝－1 ②a[q][1]＝len(a)
8.實現在鏈表 c 中找出最小值 m 的 Python 程序如下：
head＝3；p＝head；m＝c[head][0]
while (1)____：
(2)____
if c[p][0]m＝c[p][0]
上述程序段中方框處可選代碼為：①p！＝－1
②c[p][1]！＝－1　 ③p＝p＋1　④p＝c[p][1]
則程序段中(1)、(2)處代碼依次為(　　)
A.①③ B.②③ C.①④ D.②④
9.將兩個鏈表a(A→B→C)和b(D→E)按照間隔次序合并為一個鏈表，并將結果保存到鏈表a(A→D→B→E→C)中，部分程序如下：
#讀取鏈表a和b，均存儲在列表data中，其中ha表示a的頭指針，hb表示b的頭指針p，p，q＝ha，hb
while p！＝－1 and q！＝－1：　　
r＝data[q][1]
q＝r
填入方框處的可選代碼有：①data[p][1]＝data[q][1]
②data[q][1]＝data[p][1]　③data[p][1]＝q
④data[q][1]＝p　⑤p＝data[p][1]　⑥p＝data[q][1] 已知鏈表 b 的長度不超過鏈表 a，則下列選項中，代碼順序正確的是(　　)
A.①④⑤ B.②③⑥ C.①④⑥ D.②③⑤
二、能力提升
10.使用鏈表結構模擬某景區游玩路線，鏈表a中每一個節點包含3個數據，第1個為景點名稱，第2個為預計游玩時間(單位：分鐘)，第3個為下一個景點指針。景區可以從多個景點的大門進入，但只能從″天梯″離開，輸出顯示各大門進入路線及預計總時間的代碼如下。
a＝[[″迎客松″，21，2]，[″激流勇進″，40，2]，[″天空棧道″，50，5]，[″一線天″，30，4]，[″飛來峰″，60，5]，[″天梯″，20，－1]]
head＝[0，1，3]
for i in range(len(head))：
(1)__________
s＝a[p][1]
while a[p][2]！＝－1：
　　　　print(a[p][0]，end＝″→″)
(2)________
(3)________
print(a[p][0])
print(″預計時間：″，s，″分鐘″)
上述程序劃線處的可選代碼有： ①p＝head
②p＝head[i]　 ③s＋＝a[p][1]　 ④ p＝a[p][2]
則(1)(2)(3)處代碼依次為(　　)
A.①③④ B.①④③ C.②③④ D.②④③
11.有如下Python程序：
from random import *
a＝[[″e″，4]，[″g″，8]，[″h″，5]，[″h″，0]，[″n″，1]，[″o″，7]，[″S″，3]，[″u″，6]，[″Z″，2]]
k＝randint(1，4)*2＋1
p＝q＝6
while k>0：
　　p＝a[p][1]
　　k－＝1
while p！＝1：
　q＝a[q][1]
　p＝a[p][1]
print(a[q][0])
運行后，輸出值不可能是(　　)
A.g B.h C.u D.o
12.使用列表d模擬鏈表結構(節點數大于0)，每個節點包含數據區域和指針區域，h為頭指針。鏈表中各節點已按數據區域中數值的絕對值由小到大排列，如圖a所示。現要修改該鏈表各節點的鏈接關系，使鏈表各節點按數據區域中的數值由小到大排列，結果如圖b所示。實現該功能的程序段如下，方框中應填入的正確代碼為(　　)
t＝h
p＝d[h][1]
while p！＝－1 ：
q＝d[p][1]
p＝q
d[t][1]＝－1
13.有如下 Python 程序段，為實現在鏈表中插入一個[6，50]區間內的隨機數后，鏈表 data 中的數據仍然有序。
import random
x＝random.randint(6，50)
print(″在鏈表 data 中插入一個值為″，x，″的數″)
data＝[[14，1]，[26，4]，[5，0]，[49，－1]，[37，3]]
head＝2; q＝head
while q！＝－1：
if x>data[q][0]：
p＝①________
q＝data[q][1]
else：
break
data.append(②________)
data[p][1]＝len(data)－1
q＝head
while q！＝－1：
print(data[q][0]，end＝'')
q＝data[q][1]
請為①②兩處選擇正確的程序代碼(　　)
A.①data[q][1]　　②[x，p]
B.①data[q][1] ②[x，data[p][1]]
C.① q ②[x，p]
D.①q ②[x，data[p][1]]
14.報數游戲。已知班上有n名學生(用編號1，2，3，……n分別表示)，學生按照編號由小到大順時針圍成一個圓圈，從編號為1的學生開始順時針報數，報到m的同學出列；下一名同學又從1開始報數，報數為m的同學繼續出列；以此規律重復下去，直到剩下最后一位同學為止。
(1)當n＝12，m＝3時，最后留下的同學的編號是______。
(2)下列代碼通過構造一個循環單向鏈表，模擬報數的過程，逐一刪除報數為m的節點，直到剩下一個節點為止。請在劃線處填入合適的代碼。
n＝int(input(″n＝″))
m＝int(input(″m＝″))
lst＝[]
for i in range(n－1):
　 lst.append([i＋1，i＋1])
lst.append(①______________) #將尾節點的指針指向頭節點，構成循環單向鏈表
p＝len(lst)－1
while n>1：
　 for i in range(1，m): #從 1～(m－1)依次報數
p＝lst[p][1]
out＝lst[p][1]
②____________
n＝n－1
print(″最后留下的同學的編號是： ″，lst[p][0])
15.張三是一名計算機專業的大學生，為了幫助同學們學習專業相關的英語詞匯，編寫一個簡易字典程序。該程序中存放詞匯數據庫，在學習中輸入英文單詞，可以獲得中文翻譯結果。程序中的詞匯數據庫采用鏈表方式存儲，首字母相同時按升序排序。查找單詞時，首先根據首字母找到同首字母最小單詞所在鏈表，再按照鏈表順序查找該單詞。
(1)根據題意，部分的單詞庫數據邏輯結構如圖所示，查找單詞”byte”的過程是”binary”→”bit”→”byte”，補充圖中空白單元格的值為__________。
列表索引 數據區域 指針區域
0 audio 音頻 －1
1 binary 二進制數 6
2 byte 字節 －1
3 cursor 光標 －1
4 access 存取 1
5 cache 高速緩存 3
6 bit 比特 ____▲____
(2)wordlist(data，info)函數實現將詞匯數據庫 data 以鏈表的方式按字母序升序排列。info表示詞匯數據庫中各字母開頭的最小單詞位置，如 info[0]表示字母 a 開頭的最小單詞在詞匯數據庫 data 中的位置。實現該功能的程序如下，請在劃線處填入合適的代碼。
info＝[]
def wordlist(data，info):
　 n＝len(data)
　　for i in range(n)：
data[i].append(－1)
　#data[i]追加一個元素－1
for i in range(n):
　　 　d＝data[i][0]
　　　 ①______________
　　　 if info[k]＝＝－1:
　　　 info[k]＝i
　　　else：
　 　　head＝info[k]
　　　q＝head
　　　while ②____________ ：
　　 　　　p＝q
　　　　　q＝data[q][2]
　　　if q！＝head：
　　 　　　data[p][2]＝i
　　　　　data[i][2]＝q
　　　else：
　　　　　data[i][2]＝head
　　　　　③____________
return data，info
(3)searchword(data，info，key)函數實現單詞的查找。程序如下，請在劃線處填入合適的代碼。
def searchword(data，info，key):
　 k＝ord(key[0])－ord(″a″)
　　head＝info[k]
　　p＝head
　　while p！＝－1：
　 if data[p][0]＝＝key:
　　　　 return ________
　p＝data[p][2]
　　return ″沒有找到該單詞″
讀取詞匯數據庫，存入列表 data 中，列表的每個元素包含 2 個數據項，分別為英文單詞和中文翻譯，如 data＝[['audio'，'音頻']，['binary'，'二進制數'] …], 數據讀取存入的代碼略。
info＝[－1] * 26
data，info＝wordlist(data，info)
key＝input(″請輸入查找單詞：″).lower()
#轉化為小寫字母
res＝searchword(data，info，key)
print(key，″查找結果是：″，res)
課時2　鏈　表
1.A　[本題主要考查是鏈表的特性。鏈表的頭指針指向第一個節點，要刪除第一個節點，只需將頭指針移動到第一個節點指針的指向即可，因此可以刪除第一個節點，故答案為A。]
2.C　[本題主要考查鏈表的刪除操作。刪除該節點的后繼節點，需將后繼節點的指針域賦值為當前節點的指針域值，實現當前節點連接后繼節點的后面節點。lst[p][next]表示后繼節點的指針，lst[lst[p][next]]表示后繼節點。]
3.A　[本題考查鏈表的遍歷。從當前鏈表的頭節點開始遍歷，與他下一個節點p的距離，因此head要不斷地后移，head＝p，而p為新節點的后繼節點。當頭指針節點的后繼為－1時，表示遍歷完了。]
4.D　[本題考查鏈表節點的刪除。①循環遍歷整個鏈表。②q 為當前元素指針，p是當前節點q的前驅，要刪除 q 節點，只需要修改 p 的指針為 q 的后繼。]
5.D　[語句a[p][1]＝a[a[p][1]][1]是修改節點p的后繼指針，使其指向后繼節點的后繼，以實現刪除節點p后繼節點的功能。]
6.D　[本題考查鏈表的刪除。while循環查找待刪除節點的前驅節點位置。通過p1和p2遍歷鏈表，前n次只遍歷p2，后續同時遍歷p1和p2，當p2遍歷結束時，p1剛好指向倒數第n＋1個節點。所以(1)處選p2＝s[p2][1]，(2)處選p1＝s[p1][1]。確定p1位置后，執行刪除操作。如果p1指向頭節點head，要刪除頭節點，即更新head指向原頭節點指針區域對應的節點；否則刪除p1的后繼節點，即p1的指針區域更新為p1后繼節點的指針區域，(3)處應選s[p1][1]＝s[s[p1][1]][1]。]
7.B　[本題考查鏈表中數據查找和插入操作。p、q 是兩個前后相鄰的節點。根據 data>a[q][0]，可以推測出①為q！＝－1。循環結束后，應該在p節點之后插入節點，所以②處代碼是：a[p][1]＝len(a)。]
8.D　[本題考查鏈表遍歷和最值查找。當前節點從頭節點開始遍歷，最小值的初值為頭節點大小，因此需先移動到下一節點，再與最值進行比較，同時終止遍歷的條件是遍歷到尾節點馬上結束。]
9.B　[本題考查鏈表節點的插入操作。程序將節點q插入到節點p的后面，因此q的指針域的值將發生變化，為了鏈表b正常遍歷，應先保存q的后繼。插入過程中，由于已經保存了q的后繼，因此可以先修改q的指向，再修改p的指向，最后將p移動到原插入節點q的后繼。]
10.D　[本題考查多條鏈表的遍歷。3條鏈表構建在數組a中，頭指針存儲在數組head中，需遍歷頭指針數組，從而來遍歷3條鏈表。(1)處為當前節點賦值為頭指針head[i]，變量s存儲所有節點游覽總時間。(2)(3)遍歷鏈表，并統計各個節點游覽時間和，由于當前節點已經計入總時間，因此先要跳轉到下一點，將下一節點的時間加入到總時間，注意遍歷結束的條件是當遍歷到尾節點時，終止遍歷。]
11.D　[本題考查循環鏈表的操作，根據p＝q＝6可以得出鏈表為S－h－e－n－g－Z－h－o－u，k的范圍為[3，5，7，9]，p和q相差k個節點，p為1時輸出a[q][0]，即p指向g，q的可能有h、u、g。]
12.C　[題圖a按絕對值升序排序數據，鏈表中數據依次為－11，14，16，17，
－18，要求改變鏈接關系，使鏈表各節點按數據區域中的數值由小到大排列。若鏈表中只有1個節點，其值無論是正數還是負數，均是最小的數。同時他既是頭節點h，也是尾節點t。因此變量p從鏈表第2個節點開始遍歷各個節點，若遍歷到負數，則該數絕對值越大，其值就越小，需將該節點從原鏈表中刪除，并移動到頭節點的前面，進行的操作是將該前節點p指向原頭節點h，同時修改當前位置為頭指針。若為正數，將該節點鏈接到尾節點t的后面。]
13.D　[本題考查鏈表的插入。在有序鏈表中插入一個節點x，x 的范圍在6到50之間，故只需要考慮中間插入或者尾插，q 指向的就是小于 x 的最大節點，讓插入的節點 x 指向 p 節點的后繼節點 q，語句 data[p][1]＝len(data)－1實現讓p節點指向新插入的節點 x。]
14.(1)10　(2)①[n，0]　②lst[p][1]＝lst[out][1]
解析　(1)依次出隊的序號為3，6，9，12，4，8，1，7，2，11，5，最后留下10號。
(2)①循環隊列的特點是隊尾指向隊首，因此最后一個學生的編號為n，指針指向0。 ②節點p從最后一個節點開始，range(1，m)循環了m－1次，因此向后遍歷了m－1個節點，下一個節點lst[p][1]就是要刪除的節點，因此將當前節點的指針指向下一節點的后繼，就刪除了下一節點。
15.(1)2　(2)①k＝ord(d[0])－ord(″a″)　②q！＝－1 and d>data[q][0]　③info[k]＝i　(3)data[p][1]
解析　本題考查鏈表的構建、遍歷和節點的插入。
(1)采用鏈表方式存儲字母，首字母相同時按升序排序。單詞bit的下一個單詞為byte，因此其指針區域值為索引2。(2)①將單詞d首字母轉換為字母表中對應數字，info[0]表示字母 a 開頭的最小單詞，因此k為字母a－z對應0－25的索引號。②遍歷data鏈表，找到單詞d位置。當前節點q從頭節點開始，當q值不為－1，且滿足d比當前節點數據區域值大。(3)返回單詞key對應的中文。每個元素包含英文單詞和中文翻譯。

展開更多......

收起↑