資源簡介

(共52張PPT)
第二章　數組與鏈表
驗收卷(一)　數組與鏈表
(考試時間40分鐘　滿分50分)
一、選擇題(本題共12小題，每小題2分，共24分)
B
解析　本題主要考查的是數組和鏈表的特性。查找特定元素，使用單向鏈表查找時，只能通過頭指針進入鏈表并通過指針鏈接依次訪問，直到找到特定元素，而使用數組查找時，只要使用數組名和下標就能直接訪問特定元素，因此，查找特定元素，使用數組比使用單向鏈表更方便。
A.對于需要頻繁插入和刪除元素的情況，使用單向鏈表比使用數組合適
B.查找特定元素，使用單向鏈表比使用數組方便
C.數組適用于最大元素個數容易確定的情況
D.存儲相同的元素，使用單向鏈表比使用數組方便
D
2.下列關于數組和鏈表的存儲結構與邏輯結構關系的說法，正確的是(　　)
解析　鏈表的節點結構包括數據域與指針域，指針表示各節點的連接前后順序，即鏈表數據的邏輯結構由指針表示，D選項正確。
A.鏈表的存儲結構與邏輯結構一致
B.數組的存儲結構對邏輯結構沒有影響
C.存放相同數據的數組存儲空間大于鏈表
D.鏈表數據的邏輯結構由指針表示
A
3.利用5列6行的二維數組qp來記錄某試場中的座位編號1～30，m＝0
qp＝[[0 for i in range(5)] for j in range(6)] #建立二維數組并初始賦值為0
for i in range(5)：
　for j in range(6)：
　 if i %2＝＝0：
　　　 qp[j][i]＝m*6＋j＋1
　else：
　　　qp[j][i]＝m*6＋6－j
　m＝m＋1
運行上述程序段后，編號17所在的數組元素為(　　)
A.qp[4][2] B.qp[2][4] C.qp[5][3] D.qp[6][1]
解析　賦值對象為qp[j][i]，即i表示列，j表示行，意味著是按列遍歷矩陣，因此第1列為1－6，第2列為m*6＋6－j，即12－7遞減，第3列為13－18。
D
4.下列關于鏈表的敘述中，正確的是(　　)
解析　單鏈表存儲方式地址不連續，元素順序是任意的，因此答案為D。
A.線性鏈表中的各元素在存儲空間中的位置必須是連續的
B.線性鏈表中的表頭元素一定存儲在其他元素的前面
C.線性鏈表中的各元素在存儲空間中的位置不一定是連續的，但表頭元素一定存儲在其他元素的前面
D.線性鏈表中的各元素在存儲空間中的位置不一定是連續的，且各元素的存儲順序也是任意的
C
A.節點的數據區域用于存放實際需要處理的數據元素
B.節點的指針區域用于存放該節點相鄰節點的存儲地址
C.單向鏈表必須帶有數據區域為空的頭節點和尾節點
D.單向鏈表中的各個節點在內存中可以非順序存儲
解析　選項單向鏈表的頭節點和尾節點可以是單獨的數據區域為空的節點，也可以將節點序列中的第1個和最后一個節點作為頭節點和尾節點。在Python程序設計時我們通常使用第二種方式，即直接使用帶數據區域的節點作為頭節點或尾節點來標記和使用。
C
6.有如下Python程序段：
解析　本題考查鏈表的遍歷。條件a[p][1]！＝－1表示當前節點的指針區域值為－1，即當前節點為尾節點。當遍歷到尾節點時，結束循環。
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
7.有下列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]
解析　本題考查鏈表的基本操作。如果鏈表頭節點值為1，直接刪除頭節點，否則遍歷鏈表，語句a[pre][1]＝a[p][1]的作用讓節點p的前驅指向他的后繼，即刪除p節點。程序的功能是刪除元素值為1的節點。
else：
　　　　pre＝p
p＝a[p][1]
運行該段程序后，a[2][1]的值為(　　)
A.－1 B.0 C.1 D.3
D
8.采用Python二維列表模擬鏈表，
a＝[['A'，1]，['B'，2]，['C'，3]，['D'，4]，['E'，5]，
['F'，－1]]表示鏈表為：
A→B→C→D→E→F→None，有以下Python程序：
a＝[['A'，1]，['B'，2]，['C'，3]，['D'，4]，['E'，5]，
['F'，－1]]
head＝0；p＝a[head][1]
a[head][1]＝－1
while p！＝－1：
p＝a[p][1]
if p＝＝－1：
break
解析　本題考查鏈表的基本操作。p的初值為a[head][1]，即head的后繼，進入循環后，語句p＝a[p][1]的功能是向后遍歷，讓該節點指向頭節點，p再向后遍歷。A后繼的后繼是C，當前頭節點為C，C指向A；C后繼的后繼是E，當前頭節點為E，E指向C。
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
A
9.有如下 Python 程序：
a＝[43，23，87，67，80]
queinfo＝[]
for item in a：
　k＝0
　 while kif item>＝queinfo[k][－1]：
　　　 　break
k＋＝1
　　if k＝＝len(queinfo)：
queinfo.append([item])
解析　queinfo初值為空，語句queinfo.append([item])是將一個列表添加到queinfo，因此他是一個二維數組。遍歷列表a，在queinfo數組從第0個元素開始，與每個元素最后一個數據項進行比較，如果大于等于元素最后一個數據項，結束比較，此時j肯定在0至len(queinfo)－1之間，若j的值為len(queinfo)，說明該元素比queinfo中每個元素的最后一個值均小，則新成一組。Queinfo的值為[[43，87]，[23，67，80]]。
　　　else：
queinfo[k].append(item)
print(len(queinfo))
執行該程序段后，輸出的結果是(　　)
A.1 B.2 C.3 D.4
B
10.有如下Python程序段：
n＝6
a＝[[0]*n for i in range(n)]
for i in range(n)：
　for j in range(i＋1)：
　 if j！＝0 and j！＝i：
　　　 a[i][j]＝a[i－1][j－1]＋a[i－1][j]
　else：
　　　a[i][j]＝1
C
程序執行后，a[4]的值是(　　)
A.[1，3，3，1，0，0] B.[1，4，6，6，4，1]
C.[1，4，6，4，1，0] D.[1，5，10，10，5，1]
解析　本題考查二維數組的創建和遍歷。先創建一個6行6列的二維數組，遍歷二維數組的每一行，內循環從0至i，因此只對二維數組的左下半部分進行賦值。將第1列和主對角線(i和j相等)的數據全部賦值為1，其他數據為上一行的前一個和上一行的當前列之和，因此程序的功能是構建一個楊輝三角。
11.有如下 Python程序段：
a＝[[1，3，6，9]，[2，4，7，5]，[5，2，3，8]]；b＝[1]
n＝len(a)
for i in range(n)：　　
　　　for j in range(n＋1)：
　 if ib.append(a[i][j])#b追加一個元素a[i][j]
A
執行該程序執段后，數組b 中的元素為(　　)
A.[1，3，6，9，7，5，8] B.[3，6 ，9，7 ，5，8]
C.[1，3，6，9，2，4，7，5，8] D.[1，3，6，9，4，7，5，8]
解析　本題考查二維數組的應用.將二維數組a中下標i12.某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]
B
已知執行上述程序后，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]
解析　本題考查鏈表應用。data是一個鏈表，t指針從鏈表的第二個節點開始遍歷，1a指針是t節點的前驅，t節點減去前驅節點la的值小于key時，c計數，c的初值為0，計數到3時歷結束，也就是整個過程計數3次就結束，執行程序后t的值為6，也就是遍歷到最后一個節點時程序才結束。
二、非選擇題(本題共4小題，共26分)
13.(6分)大部分社交軟件都有好友推薦的功能，當用戶A和用戶B不為好友，但他們的共同好友數量超過閾值m時，由系統向用戶A推薦用戶B。
編寫Python程序，實現好友推薦功能。生成一個二維數組a記錄兩者關系，當a[0][2]的值為1時，表示ID1和ID3是好友，值為0則不是好友。運行程序，輸入用戶ID和共同好友數量超過閾值m，顯示每個用戶ID的好友及向目標用戶推薦的好友列表。程序運行界面如圖：
共同好友數量超過閾值m：2
1ID號的好友有：2，3，4，5，6，7，9
2ID號的好友有：1，3，4，5，6，7，10
3ID號的好友有：1，2，5，6，7，8，9
4ID號的好友有：1，2，5，6，7，8，9，10
5ID號的好友有：1，2，3，4，6，8
6ID號的好友有：1，2，3，4，5，7，9，10
7ID號的好友有：1，2，3，4，6，8
8ID號的好友有：3，4，5，7，9，10
9ID號的好友有：1，3，4，6，8
10ID號的好友有：2，4，6，8
向用戶ID1推薦的共同好友有：[8，10]
編寫的代碼如下：
n＝10
#產生一個n*n的二維數組a，存儲兩人之間的關系。
def Check(a，x，y): #向用戶ID為x推薦的閾值為y的好友列表。
n＝10；ans＝0
nothy＝[]
for i in range(n): #查找與x不是好友的朋友編號
　 if ①____________：
　　　 　nothy.append(i)
hy＝[]
for i in nothy：
　 t＝0
　 for j in range(n)：
　 if ②____________：
　　　 　t＋＝1
if t>y：
　 hy.append(i＋1)
return hy　
hm＝int(input(″輸入用戶ID：″))
m＝int(input(″共同好友數量超過閾值m：″))　
for i in range(n)：
　 s＝str(i＋1)＋″ID號的好友有：″
　 for j in range(n)：
　 if a[i][j]＝＝1：
　　　　s＝s＋str(j＋1)＋″，″
　print(s[：－1])
③____________
print(″向用戶ID″，hm，″推薦的共同好友有：″，p)
(1)輸入用戶ID為7，閾值m為4，則推薦的好友是________。
(2)請在程序劃線處填入合適的代碼。
答案　(1)5，9　(2)①a[i][x]＝＝0 and x！＝i
②a[x][j]＝＝1 and a[i][j]＝＝1
③p＝Check(a，hm，m)
解析　(1)在不是好友中選擇共同好友超過4的ID，ID10與ID7的共同好友只有4個。(2)①查找與x不是好友的朋友編號，在各個編號中遍歷，相當在于二維表格的第x行查找0的列號，但列號不能是x自己。②尋找共同好友，即第x第i行中，值均為1的列號數量。③調用自定義函數查找共同好友。
已知
14.(6分)某影平臺上架新影片時，需要先確定該影片的類型，如喜劇片、動作片、愛情片。確定某影片的類型，可根據已有的樣本數據(如圖a所示)進行分類。
圖a
電影名稱 搞笑鏡頭 擁抱鏡頭 打斗鏡頭 影片類型
寶貝當家 45 2 9 喜劇片
唐人街探案 23 3 17 喜劇片
我的特工 爺爺 6 4 21 動作片
…… …… …… …… ……
泰坦尼克號 9 39 8 愛情片
羅馬假日 9 38 2 愛情片
新步步驚心 8 34 17 愛情片
圖b
電影名稱 搞笑 鏡頭 擁抱 鏡頭 打斗 鏡頭 影片
類型
美人魚 19 18 5 ？
距離最近的前5部影片為：
唐人街探案19.62，羅馬假日22.56，新步步驚心22.83，泰坦尼克號23.45，我的特工爺爺24.92，
圖c
請回答下列問題：
(1)與《美人魚》距離最近的前5部影片如圖c所示，則該影片屬于________(單選，填字母：A.喜劇片 /B.動作片 /C.愛情片)。
(2)定義如下mvmin(result，flag)函數，參數result列表存儲距離，flag列表存儲標記。若result＝[43，33，18，25，65]，flag＝[False，False，True，True，False]，則函數的返回值為________。
def mvmin(result，flag)：
mv＝10000　#假定result列表元素值不超過10000
for i in range(len(result))：
　　 　if mv>result[i] and flag[i]＝＝False：
　　　 mv＝result[i]
　　　pos＝i
return pos
(3)實現電影分類的部分Python程序如下，請在劃線處填入合適的代碼。
讀取樣本影片的鏡頭數據，存儲在data中，每個元素包含5個數據項，分別對應電影名稱、搞笑鏡頭、打斗鏡頭、擁抱鏡頭、影片類型。
如data＝[[″寶貝當家″，45，2，9，″喜劇片″]，……]，代碼略。
x＝[″美人魚″，19，18，5]
dic＝{″喜劇片″：0，″動作片″：0，″愛情片″：0}
k＝5　
result＝[0]*len(data)
for i in range(len(data))：
d＝0
for j in range(1，4)：
　　tmp＝①________
　 　d＋＝tmp**2　
result[i]＝round(d**0.5，2) #結果保留2位小數
flag＝[False]*len(result)
print(″距離最近的前″，k，″部影片為：″)
while k>0：
p＝mvmin(result，flag)
flag[p]＝True
②________
print(data[p][0]，result[p]，end＝″，″)
③________
#統計前k個最近距離的影片中出現頻次最多的類型，并輸出該影片類型，代碼略
答案　(1)C　(2)1　(3)①data[i][j]－x[j] 或 x[j]－data[i][j] 　②dic[data[p][4]]＋＝1　③k－＝1
解析　(1)距離最近的5部影片中，喜劇片1部，愛情片3部分，動作片1部，因此該影片類型為愛情片。(2)在存儲標記為False的位置中，查找最小值的索引，43，33，65三個數中最小值索引為1。(3)①遍歷所有的樣本數據data，計算出“美人魚”與樣本中所有影片的距離。data[i][1]、data[i][2]、data[i][3]分別表示樣本數據中搞笑鏡頭、打斗鏡頭、擁抱鏡頭的值，用變量j表示這些下標，計算與x[j]的平方差的和。②調用mvmin函數計算最小距離的索引p，即對應的樣本的索引，在數組元素data[p][4]中存儲的是該影片的類型，需要對該類型的數量增加1。③處理下一個樣本數據。
15.(7分)某學校工會舉行飛鏢大賽，共有n位老師報名參賽，每位選手共擲5支鏢，每鏢得分為0至10分，選手總分為 5鏢成績之和，每位選手的比賽數據記錄在文本文件中，如圖a所示。
處理要求：數據讀入數組 data 中，計算出每位選手的總分，在不改變數據在原數組 data 中的位置的條件下，按總分從高到低輸出選手的編號和總分。
(1)主程序。采用鏈表結構處理數據。程序運行結果如圖 b所示。請在程序中劃線處填入合適的代碼。
data＝readdata(″scores.txt″) #讀取數據，計算總分
print(″處理前的數據為：\\n″，data)
n＝len(data)
flag＝[True]*n #標記數據被使用情況
head＝findmax() #返回 data 中可使用狀態最大數的位置
k＝head
for i in range(1，n):
　 posi＝findmax()
　 data[k].append(posi)
　______________
data[k].append(－1)
print(″處理后的數據為：\\n″，data)
print(″從高分到低分輸出為：″)
output(head)
(2)編寫readdata函數，功能為從文本文件讀取數據，計算出總分，返回列表。代碼如下，請在程序中劃線處填入合適的代碼。
def readdata(filename):
　 f＝open(filename)
　 line＝f.readline()
　　lst＝[]
　　while line: #獲取每位選手的編號和總分數據
　　 　line＝line.split(″，″)
　　　s＝0
　 　　for i in range(1，len(line))：
　　 　__________
　　　lst.append([line[0]，s])
　 　　line＝f.readline()
return lst
(3)編寫findmax函數，功能為返回 data 中可使用狀態最大數的位置pos，并設置該數的使用狀態為 False。請在程序中劃線處填入合適的代碼。
def findmax()：
　maxnum＝0
　 for i in range(n)：
　 if ①____________：
　　　 maxnum＝data[i][1]
　　　 pos＝i
　　　②____________
　　　return pos
答案　(1)k＝posi　(2)s＋＝int(line[i])
(3)①maxnum②flag[pos]＝False　(4)q！＝－1
解析　(1)查找數組中的最大值的位置，利用位置關系串成一個降序鏈表，最后遍歷鏈表輸出。k 是當前元素的位置，posi 是下一個元素的位置，找到的數應該在節點 posi 后面。(2)readdata函數功能是讀取“scores.txt”文件，生成一個二維列表。變量s累計的總分。(3)findmax函數找到最大數所在位置，同時將該位置設置為 False。
(4)遍歷鏈表，輸出節點相關數據域的內容。
16.(7分)“搶單”是外賣騎手的日常，當外賣平臺上一個新的訂單出現時，騎手需要在短時間內考慮是否搶單。平臺根據騎手的實際信息，給出是否搶單的建議，若建議搶單則給出到達各個取送點的順序。
平臺判斷是否搶單的算法設計如下：
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，______(選填：影響/不影響)程序執行。
total＋＝d
if total/speed>con(riderlist[cur][3])－con(riderlist[h][3])：
　　　　return －1
else：
　　　　 pre＝cur
　　　　 cur＝riderlist[pre][4]
return round(total，2)
(4)實現是否接單判斷的Python部分程序如下，請在劃線處填入合適的代碼。
def add(oldlist，x，c)：　#在x所指節點后插入新節點c
c[4]＝oldlist[x][4]
oldlist.append(c)
oldlist[x][4]＝len(oldlist)－1
return oldlist
#讀取騎手信息，存儲在lit中，代碼略
tc＝[″t″，″119.936506″，″31.008933″，″12：05″，－1]　#新訂單取餐信息　
sc＝[″s″，″119.919839″，″31.020183″，″12：22″，－1]　#新訂單送餐信息
ans＝[－1，－1，10000]
head＝0
p＝head
while p！＝－1：
lit＝add(lit，p，tc)
①____________
while q！＝－1：
lit＝add(lit，q，sc)
tot＝totd(lit，head)
if tot！＝－1 and ②____________ ：
　　　ans＝[p，q，tot]
lit[q][4]＝lit[lit[q][4]][4]
q＝lit[q][4]
lit[p][4]＝lit[lit[p][4]][4]
p＝lit[p][4]
if ans[2]＝＝10000：
print(″不建議接單，不能在系統指定時間內送達。″)
else：
print(″可以接單，建議各取送點到達順序依次為：″)
#按順序輸出各取送點代碼略
答案　(1)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。驗收卷(一)　數組與鏈表
(考試時間40分鐘　滿分50分)
一、選擇題(本題共12小題，每小題2分，共24分)
1.單向鏈表與數組都屬于線性表，它們都用于存儲具有相同屬性的數據，下列說法不正確的是(　　)
A.對于需要頻繁插入和刪除元素的情況，使用單向鏈表比使用數組合適
B.查找特定元素，使用單向鏈表比使用數組方便
C.數組適用于最大元素個數容易確定的情況
D.存儲相同的元素，使用單向鏈表比使用數組方便
2.下列關于數組和鏈表的存儲結構與邏輯結構關系的說法，正確的是(　　)
A.鏈表的存儲結構與邏輯結構一致
B.數組的存儲結構對邏輯結構沒有影響
C.存放相同數據的數組存儲空間大于鏈表
D.鏈表數據的邏輯結構由指針表示
3.利用5列6行的二維數組qp來記錄某試場中的座位編號1～30，m＝0
qp＝[[0 for i in range(5)] for j in range(6)] #建立二維數組并初始賦值為0
for i in range(5)：
　for j in range(6)：
　 if i %2＝＝0：
　　　 qp[j][i]＝m*6＋j＋1
　else：
　　　qp[j][i]＝m*6＋6－j
　m＝m＋1
運行上述程序段后，編號17所在的數組元素為(　　)
A.qp[4][2] B.qp[2][4] C.qp[5][3] D.qp[6][1]
4.下列關于鏈表的敘述中，正確的是(　　)
A.線性鏈表中的各元素在存儲空間中的位置必須是連續的
B.線性鏈表中的表頭元素一定存儲在其他元素的前面
C.線性鏈表中的各元素在存儲空間中的位置不一定是連續的，但表頭元素一定存儲在其他元素的前面
D.線性鏈表中的各元素在存儲空間中的位置不一定是連續的，且各元素的存儲順序也是任意的
5.關于單向鏈表的節點結構，下列說法不正確的是(　　)
A.節點的數據區域用于存放實際需要處理的數據元素
B.節點的指針區域用于存放該節點相鄰節點的存儲地址
C.單向鏈表必須帶有數據區域為空的頭節點和尾節點
D.單向鏈表中的各個節點在內存中可以非順序存儲
6.有如下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
7.有下列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
8.采用Python二維列表模擬鏈表，
a＝[['A'，1]，['B'，2]，['C'，3]，['D'，4]，['E'，5]，
['F'，－1]]表示鏈表為：
A→B→C→D→E→F→None，有以下Python程序：
a＝[['A'，1]，['B'，2]，['C'，3]，['D'，4]，['E'，5]，
['F'，－1]]
head＝0；p＝a[head][1]
a[head][1]＝－1
while p！＝－1：
p＝a[p][1]
if p＝＝－1：
break
t＝a[p][1]
a[p][1]＝head
head＝p
p＝t
執行以上程序后，以head為首的鏈表結構為(　　)
A.E→C→A B.A→C→E
C.B→D→F D.F→D→B
9.有如下 Python 程序：
a＝[43，23，87，67，80]
queinfo＝[]
for item in a：
　k＝0
　 while kif item>＝queinfo[k][－1]：
　　　 　break
k＋＝1
　　if k＝＝len(queinfo)：
queinfo.append([item])
　　　else：
queinfo[k].append(item)
print(len(queinfo))
執行該程序段后，輸出的結果是(　　)
A.1 B.2 C.3 D.4
10.有如下Python程序段：
n＝6
a＝[[0]*n for i in range(n)]
for i in range(n)：
　for j in range(i＋1)：
　 if j！＝0 and j！＝i：
　　　 a[i][j]＝a[i－1][j－1]＋a[i－1][j]
　else：
　　　a[i][j]＝1
程序執行后，a[4]的值是(　　)
A.[1，3，3，1，0，0] B.[1，4，6，6，4，1]
C.[1，4，6，4，1，0] D.[1，5，10，10，5，1]
11.有如下 Python程序段：
a＝[[1，3，6，9]，[2，4，7，5]，[5，2，3，8]]；b＝[1]
n＝len(a)
for i in range(n)：　　
　　　for j in range(n＋1)：
　 if ib.append(a[i][j])#b追加一個元素a[i][j]
執行該程序執段后，數組b 中的元素為(　　)
A.[1，3，6，9，7，5，8]
B.[3，6 ，9，7 ，5，8]
C.[1，3，6，9，2，4，7，5，8]
D.[1，3，6，9，4，7，5，8]
12.某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]
二、非選擇題(本題共4小題，共26分)
13.(6分)大部分社交軟件都有好友推薦的功能，當用戶A和用戶B不為好友，但他們的共同好友數量超過閾值m時，由系統向用戶A推薦用戶B。
編寫Python程序，實現好友推薦功能。生成一個二維數組a記錄兩者關系，當a[0][2]的值為1時，表示ID1和ID3是好友，值為0則不是好友。運行程序，輸入用戶ID和共同好友數量超過閾值m，顯示每個用戶ID的好友及向目標用戶推薦的好友列表。程序運行界面如圖：
共同好友數量超過閾值m：2 1ID號的好友有：2，3，4，5，6，7，9 2ID號的好友有：1，3，4，5，6，7，10 3ID號的好友有：1，2，5，6，7，8，9 4ID號的好友有：1，2，5，6，7，8，9，10 5ID號的好友有：1，2，3，4，6，8 6ID號的好友有：1，2，3，4，5，7，9，10 7ID號的好友有：1，2，3，4，6，8 8ID號的好友有：3，4，5，7，9，10 9ID號的好友有：1，3，4，6，8 10ID號的好友有：2，4，6，8 向用戶ID1推薦的共同好友有：[8，10]
編寫的代碼如下：
n＝10
#產生一個n*n的二維數組a，存儲兩人之間的關系。
def Check(a，x，y): #向用戶ID為x推薦的閾值為y的好友列表。
n＝10；ans＝0
nothy＝[]
for i in range(n): #查找與x不是好友的朋友編號
　 if ①____________：
　　　 　nothy.append(i)
hy＝[]
for i in nothy：
　 t＝0
　 for j in range(n)：
　 if ②____________：
　　　 　t＋＝1
if t>y：
　 hy.append(i＋1)
return hy　
hm＝int(input(″輸入用戶ID：″))
m＝int(input(″共同好友數量超過閾值m：″))　
for i in range(n)：
　 s＝str(i＋1)＋″ID號的好友有：″
　 for j in range(n)：
　 if a[i][j]＝＝1：
　　　　s＝s＋str(j＋1)＋″，″
　print(s[：－1])
③____________
print(″向用戶ID″，hm，″推薦的共同好友有：″，p)
(1)輸入用戶ID為7，閾值m為4，則推薦的好友是________。
(2)請在程序劃線處填入合適的代碼。
14.(6分)某影平臺上架新影片時，需要先確定該影片的類型，如喜劇片、動作片、愛情片。確定某影片的類型，可根據已有的樣本數據(如圖a所示)進行分類。
某分類算法如下：計算該影片與樣本中各影片分鏡頭的相似度，相似度可用距離公式來表示，例如“美人魚”各分鏡頭數據如圖b所示，其與“寶貝當家”影片的距離為。用該方法計算出“美人魚”與樣本中所有影片的距離，選取前k個最近距離的影片，統計出現頻次最多的影片類型，即為該影片的類型。
電影名稱 搞笑鏡頭 擁抱鏡頭 打斗鏡頭 影片類型
寶貝當家 45 2 9 喜劇片
唐人街 探案 23 3 17 喜劇片
我的特工 爺爺 6 4 21 動作片
…… …… …… …… ……
泰坦尼克號 9 39 8 愛情片
羅馬假日 9 38 2 愛情片
新步步驚心 8 34 17 愛情片
圖a
電影名稱 搞笑 鏡頭 擁抱 鏡頭 打斗 鏡頭 影片 類型
美人魚 19 18 5 ？
圖b
距離最近的前5部影片為： 唐人街探案19.62，羅馬假日22.56，新步步驚心22.83，泰坦尼克號23.45，我的特工爺爺24.92，
圖c
請回答下列問題：
(1)與《美人魚》距離最近的前5部影片如圖c所示，則該影片屬于________(單選，填字母：A.喜劇片 /B.動作片 /C.愛情片)。
(2)定義如下mvmin(result，flag)函數，參數result列表存儲距離，flag列表存儲標記。若result＝[43，33，18，25，65]，flag＝[False，False，True，True，False]，則函數的返回值為________。
def mvmin(result，flag)：
mv＝10000　#假定result列表元素值不超過10000
for i in range(len(result))：
　　 　if mv>result[i] and flag[i]＝＝False：
　　　 mv＝result[i]
　　　pos＝i
return pos
(3)實現電影分類的部分Python程序如下，請在劃線處填入合適的代碼。
讀取樣本影片的鏡頭數據，存儲在data中，每個元素包含5個數據項，分別對應電影名稱、搞笑鏡頭、打斗鏡頭、擁抱鏡頭、影片類型。
如data＝[[″寶貝當家″，45，2，9，″喜劇片″]，……]，代碼略。
x＝[″美人魚″，19，18，5]
dic＝{″喜劇片″：0，″動作片″：0，″愛情片″：0}
k＝5　
result＝[0]*len(data)
for i in range(len(data))：
d＝0
for j in range(1，4)：
　　tmp＝①________
　 　d＋＝tmp**2　
result[i]＝round(d**0.5，2) #結果保留2位小數
flag＝[False]*len(result)
print(″距離最近的前″，k，″部影片為：″)
while k>0：
p＝mvmin(result，flag)
flag[p]＝True
②________
print(data[p][0]，result[p]，end＝″，″)
③________
#統計前k個最近距離的影片中出現頻次最多的類型，并輸出該影片類型，代碼略
15.(7分)某學校工會舉行飛鏢大賽，共有n位老師報名參賽，每位選手共擲5支鏢，每鏢得分為0至10分，選手總分為 5鏢成績之和，每位選手的比賽數據記錄在文本文件中，如圖a所示。
處理要求：數據讀入數組 data 中，計算出每位選手的總分，在不改變數據在原數組 data 中的位置的條件下，按總分從高到低輸出選手的編號和總分。
(1)主程序。采用鏈表結構處理數據。程序運行結果如圖 b所示。請在程序中劃線處填入合適的代碼。
data＝readdata(″scores.txt″) #讀取數據，計算總分
print(″處理前的數據為：\\n″，data)
n＝len(data)
flag＝[True]*n #標記數據被使用情況
head＝findmax() #返回 data 中可使用狀態最大數的位置
k＝head
for i in range(1，n):
　 posi＝findmax()
　 data[k].append(posi)
　______________
data[k].append(－1)
print(″處理后的數據為：\\n″，data)
print(″從高分到低分輸出為：″)
output(head)
(2)編寫readdata函數，功能為從文本文件讀取數據，計算出總分，返回列表。代碼如下，請在程序中劃線處填入合適的代碼。
def readdata(filename):
　 f＝open(filename)
　 line＝f.readline()
　　lst＝[]
　　while line: #獲取每位選手的編號和總分數據
　　 　line＝line.split(″，″)
　　　s＝0
　 　　for i in range(1，len(line))：
　　 　__________
　　　lst.append([line[0]，s])
　 　　line＝f.readline()
return lst
(3)編寫findmax函數，功能為返回 data 中可使用狀態最大數的位置pos，并設置該數的使用狀態為 False。請在程序中劃線處填入合適的代碼。
def findmax()：
　maxnum＝0
　 for i in range(n)：
　 if ①____________：
　　　 maxnum＝data[i][1]
　　　 pos＝i
　　　②____________
　　　return pos
(4)編寫output函數，功能為從高分到低分輸出選手的信息。代碼如下，加框處的代碼有誤，請改正。
def output(q)：
　　while　：
　 print(data[q][0：2]，end＝″>>″)
　q＝data[q][2]
print(″NULL″)　#表示結束
16.(7分)“搶單”是外賣騎手的日常，當外賣平臺上一個新的訂單出現時，騎手需要在短時間內考慮是否搶單。平臺根據騎手的實際信息，給出是否搶單的建議，若建議搶單則給出到達各個取送點的順序。
平臺判斷是否搶單的算法設計如下：
1)在不改變已有訂單各取送點順序的前提下，將新訂單按先取餐后送餐的順序分別插入原來的路線中，枚舉所有新路線；
2)計算新路線路程，并進行判斷：每個取送點都有一個系統指定時間，若騎手到達該位置時，時間晚于系統指定時間，則該方案無效；
3)對新路線進行計算和判斷后，刪除此次枚舉的兩個插入位置，還原為初始狀態，再繼續進行下一次枚舉；
4)在所有有效方案中，輸出總路程最小的方案，若無有效方案，則輸出不接單的建議。
如果騎手目前無訂單在派送中，則插入訂單A的方案只有1種，騎手→取餐點A→送餐點A；如果騎手訂單中已有1個送餐點A和1個送餐點B，則新訂單C有6種插入方案，如下所示，
方案1：騎手→取餐點C→送餐點C→送餐點A→送餐點B
方案2：騎手→取餐點C→送餐點A→送餐點C→送餐點B
方案3：騎手→取餐點C→送餐點A→送餐點B→送餐點C
方案4：騎手→送餐點A→取餐點C→送餐點C→送餐點B
方案5：騎手→送餐點A→取餐點C→送餐點B→送餐點C
方案6：騎手→送餐點A→送餐點B→取餐點C→送餐點C
(1)若騎手僅剩3份餐未送(已取餐)，路線為：騎手→送餐點A→送餐點B→送餐點C，新的訂單出現后，有________種插入方案。
(2)定義如下con(tim)函數進行時間格式轉換，將24小時制的“時：分”轉換為分，如02：30轉換為150，請在劃線處填上合適代碼。
def con(tim)：
　t＝__________＋int(tim[3：])
　　return　t
(3)定義totd(riderlist，h)函數，其功能為從頭指針h進入鏈表riderlist，按節點先后順序計算總路程，并判斷能否在系統指定時間內到達各取送點，若到達某一取送點時超時返回－1。若鏈表riderlist如下，
riderlist＝[[″u1001″，″119.906033″，″31.014597″，″11：30″，2]，
[″s″，″119.921439″，″31.023022″，″11：55″，3]，
[″t″，″119.887850″，″31.022861″，″11：40″，1]，
[″s″，″119.953836″，″31.021122″，″12：10″，－1]]
第1個元素中″u1001″為騎手編號，″119.906033″和″31.014597″，表示騎手實時位置，″11：30″為實時時間，2為下一節點指針，第2個元素開始，第1項若為″t″表示此元素為取餐點信息，若為″s″表示此元素為送餐點信息。調用函數totd(riderlist，h)，risderlist的值如上，h為0，則加框處語句最多被執行______次，若將此條件語句改為riderlist[pre][4]！＝－1，______(選填：影響/不影響)程序執行。
def totd(riderlist，h):
speed＝0.3　#speed為騎手每分鐘公里數
total＝0
pre＝h
cur＝riderlist[pre][4]
while ：
#計算pre與cur兩個節點所在位置間的路程，存儲在變量d中
total＋＝d
if total/speed>con(riderlist[cur][3])－con(riderlist[h][3])：
　　　　return －1
else：
　　　　 pre＝cur
　　　　 cur＝riderlist[pre][4]
return round(total，2)
(4)實現是否接單判斷的Python部分程序如下，請在劃線處填入合適的代碼。
def add(oldlist，x，c)：　#在x所指節點后插入新節點c
c[4]＝oldlist[x][4]
oldlist.append(c)
oldlist[x][4]＝len(oldlist)－1
return oldlist
#讀取騎手信息，存儲在lit中，代碼略
tc＝[″t″，″119.936506″，″31.008933″，″12：05″，－1]　#新訂單取餐信息　
sc＝[″s″，″119.919839″，″31.020183″，″12：22″，－1]　#新訂單送餐信息
ans＝[－1，－1，10000]
head＝0
p＝head
while p！＝－1：
lit＝add(lit，p，tc)
①____________
while q！＝－1：
lit＝add(lit，q，sc)
tot＝totd(lit，head)
if tot！＝－1 and ②____________ ：
　　　ans＝[p，q，tot]
lit[q][4]＝lit[lit[q][4]][4]
q＝lit[q][4]
lit[p][4]＝lit[lit[p][4]][4]
p＝lit[p][4]
if ans[2]＝＝10000：
print(″不建議接單，不能在系統指定時間內送達。″)
else：
print(″可以接單，建議各取送點到達順序依次為：″)
#按順序輸出各取送點代碼略
驗收卷(一)　數組與鏈表
1.B　[本題主要考查的是數組和鏈表的特性。查找特定元素，使用單向鏈表查找時，只能通過頭指針進入鏈表并通過指針鏈接依次訪問，直到找到特定元素，而使用數組查找時，只要使用數組名和下標就能直接訪問特定元素，因此，查找特定元素，使用數組比使用單向鏈表更方便。]
2.D　[鏈表的節點結構包括數據域與指針域，指針表示各節點的連接前后順序，即鏈表數據的邏輯結構由指針表示，D選項正確。]
3.A　[賦值對象為qp[j][i]，即i表示列，j表示行，意味著是按列遍歷矩陣，因此第1列為1－6，第2列為m*6＋6－j，即12－7遞減，第3列為13－18。]
4.D　[單鏈表存儲方式地址不連續，元素順序是任意的，因此答案為D。]
5.C　[選項單向鏈表的頭節點和尾節點可以是單獨的數據區域為空的節點，也可以將節點序列中的第1個和最后一個節點作為頭節點和尾節點。在Python程序設計時我們通常使用第二種方式，即直接使用帶數據區域的節點作為頭節點或尾節點來標記和使用。]
6.C　[本題考查鏈表的遍歷。條件a[p][1]！＝－1表示當前節點的指針區域值為－1，即當前節點為尾節點。當遍歷到尾節點時，結束循環。]
7.D　[本題考查鏈表的基本操作。如果鏈表頭節點值為1，直接刪除頭節點，否則遍歷鏈表，語句a[pre][1]＝a[p][1]的作用讓節點p的前驅指向他的后繼，即刪除p節點。程序的功能是刪除元素值為1的節點。]
8.A　[本題考查鏈表的基本操作。p的初值為a[head][1]，即head的后繼，進入循環后，語句p＝a[p][1]的功能是向后遍歷，讓該節點指向頭節點，p再向后遍歷。A后繼的后繼是C，當前頭節點為C，C指向A；C后繼的后繼是E，當前頭節點為E，E指向C。]
9.B　[queinfo初值為空，語句queinfo.append([item])是將一個列表添加到queinfo，因此他是一個二維數組。遍歷列表a，在queinfo數組從第0個元素開始，與每個元素最后一個數據項進行比較，如果大于等于元素最后一個數據項，結束比較，此時j肯定在0至len(queinfo)－1之間，若j的值為len(queinfo)，說明該元素比queinfo中每個元素的最后一個值均小，則新成一組。Queinfo的值為[[43，87]，[23，67，80]]。]
10.C　[本題考查二維數組的創建和遍歷。先創建一個6行6列的二維數組，遍歷二維數組的每一行，內循環從0至i，因此只對二維數組的左下半部分進行賦值。將第1列和主對角線(i和j相等)的數據全部賦值為1，其他數據為上一行的前一個和上一行的當前列之和，因此程序的功能是構建一個楊輝三角。]
11.A　[本題考查二維數組的應用.將二維數組a中下標i12.B　[本題考查鏈表應用。data是一個鏈表，t指針從鏈表的第二個節點開始遍歷，1a指針是t節點的前驅，t節點減去前驅節點la的值小于key時，c計數，c的初值為0，計數到3時歷結束，也就是整個過程計數3次就結束，執行程序后t的值為6，也就是遍歷到最后一個節點時程序才結束。]
13.(1)5，9　(2)①a[i][x]＝＝0 and x！＝i
②a[x][j]＝＝1 and a[i][j]＝＝1
③p＝Check(a，hm，m)
解析　(1)在不是好友中選擇共同好友超過4的ID，ID10與ID7的共同好友只有4個。(2)①查找與x不是好友的朋友編號，在各個編號中遍歷，相當在于二維表格的第x行查找0的列號，但列號不能是x自己。②尋找共同好友，即第x第i行中，值均為1的列號數量。③調用自定義函數查找共同好友。
14.(1)C　(2)1　(3)①data[i][j]－x[j] 或 x[j]－data[i][j]
②dic[data[p][4]]＋＝1　③k－＝1
解析　(1)距離最近的5部影片中，喜劇片1部，愛情片3部分，動作片1部，因此該影片類型為愛情片。(2)在存儲標記為False的位置中，查找最小值的索引，43，33，65三個數中最小值索引為1。(3)①遍歷所有的樣本數據data，計算出“美人魚”與樣本中所有影片的距離。data[i][1]、data[i][2]、data[i][3]分別表示樣本數據中搞笑鏡頭、打斗鏡頭、擁抱鏡頭的值，用變量j表示這些下標，計算與x[j]的平方差的和。②調用mvmin函數計算最小距離的索引p，即對應的樣本的索引，在數組元素data[p][4]中存儲的是該影片的類型，需要對該類型的數量增加1。
③處理下一個樣本數據。
15.(1)k＝posi　(2)s＋＝int(line[i])
(3)①maxnum(4)q！＝－1
解析　(1)查找數組中的最大值的位置，利用位置關系串成一個降序鏈表，最后遍歷鏈表輸出。k 是當前元素的位置，posi 是下一個元素的位置，找到的數應該在節點 posi 后面。(2)readdata函數功能是讀取“scores.txt”文件，生成一個二維列表。變量s累計的總分。(3)findmax函數找到最大數所在位置，同時將該位置設置為 False。
(4)遍歷鏈表，輸出節點相關數據域的內容。
16.(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。

展開更多......

收起↑