資源簡介

(共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，即當前節點為尾節點。當遍歷到尾節點時，結束循環。
a＝[[2，2]，[5，3]，[3，1]，[6，－1]，[1，0]，[4，2]]
p＝5
while a[p][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?。剑?：
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?。絠：
　　　 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?。絠
②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] ?、赿ic[data[p][4]]＋＝1?、踜－＝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)查找數組中的最大值的位置，利用位置關系串成一個降序鏈表，最后遍歷鏈表輸出。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]?。剑?，______(選填：影響/不影響)程序執行。
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?。剑?：
lit＝add(lit，p，tc)
①____________
while q?。剑?：
lit＝add(lit，q，sc)
tot＝totd(lit，head)
if tot！＝－1 and ②____________ ：
　　　ans＝[p，q，tot]
lit[q][4]＝lit[lit[q][4]][4]
q＝lit[q][4]
lit[p][4]＝lit[lit[p][4]][4]
p＝lit[p][4]
if ans[2]＝＝10000：
print(″不建議接單，不能在系統指定時間內送達?！?
else：
print(″可以接單，建議各取送點到達順序依次為：″)
#按順序輸出各取送點代碼略
答案　(1)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.有如下Python程序段：
count＝0
st＝list(″Python″)
s＝″″
for i in st：
s＝i＋s
count＋＝1
print(count，s)
程序段執行后，輸出的結果是(　　)
A.5 Python B.6 Python
C.6 nohtyP D.6 'nohtyP'
2.有如下Python程序段：
s＝input(″輸入一個字符串″)
a＝[″″]*6；t＝0
a[0]＝s[0]
for i in range(1，len(s))：
if t>＝0 and s[i]＝＝a[t]：
t＝t－1
else：
t＋＝1
a[t]＝s[i]
print(t)
運行程序段，輸入以下字符串，運行后變量 t 的值與其它三項不同的是(　　)
A.AABAB B.AAABA C.BAABA D.BBABA
3.輸入一個數字字符串 s，輸出刪除其中 k 個數字字符，并且數字的次序不能交換，輸出刪除后的最大數字字符串。如：輸入數字字符串“38726”，若 k＝1，則刪除其中 1 個數字字符后的最大數字字符串是“8726”，若k＝3，則刪除其中 3 個數字字符后的最大數字字符串是“87”。實現上述功能的Python程序段如下：
s＝input(″請輸入數字串″)
k＝int(input(″請輸入要刪除的數字個數″))
while k>0：
i＝0
while is[i＋1]：
i＋＝1
if i＝＝0：
　　
else：
　　
k－＝1
print(s)
上述程序段中加框處可選語句為：①s＝s[i＋1：]?、趕＝s[i＋1：len(s)－1]?、踫＝s[：i]＋s[i＋1：len(s)－1]　④s＝s[：i]＋s[i＋1：]
則(1)(2)處語句依次是(　　)
A.①④ B.③② C.③④ D.①②
4.隊列Q從隊首到隊尾的元素依次是1，3，5，棧S從棧底到棧頂的元素依次是2，4，6，現約定：A操作是指元素出隊后入棧，B操作是指元素出棧后入隊。經過BAAB系列操作后，隊列中隊首到隊尾的元素依次為(　　)
A.5，2，1 B.5，2，4 C.5，6，1 D.5，6，3
5.某Python程序如下：
q＝[″″]*50
head＝tail＝0
s＝″ningbo″
for i in s：
　q[tail]＝i
　tail＋＝1
while head　 print(q[head]，end＝″″)
　head＋＝1
　for i in range(3)：
　 q[tail]＝q[head]
　head＋＝1
　tail＋＝1
執行該程序段后，輸出結果為(　　)
A.nbgoni B.nbogni C.goninb D.ningbo
6. 有如下Python程序：
a＝[4，2，5，1，9]
que＝[0]*7
head，tail＝0，0
que[tail]＝a[0]
tail＋＝1
for i in range(1，len(a)):
　if a[i]>que[tail－1]:
　 que[tail]＝a[i]
　tail＋＝1；head＋＝1
　elif a[i]　 que[tail]＝a[i]
　tail＋＝1
print(que[head：tail])
執行以上程序段后，輸出結果是(　　)
A.4，7 B.5，1，9
C.2，5，1，9 D.4，7，2，5，1，9
7.有如下Python程序段：
a＝[2，4，5，10，8，13，11，7，2，6]
que＝[0]*len(a)
k＝int(input())
key＝int(input())
msq＝0；sq＝0
head，tail＝0，0
for i in a：
　 que[tail]＝i
　 sq＝sq＋i
　 tail＝tail＋1
　 while sq>key or tail－head>＝k：
　 sq＝sq－que[head]
head＝head＋1
　 if sq>msq：
　msq＝sq
若輸入k的值為3、key的值為20，則程序運行后，變量msq的值為(　　)
A.18 B.19 C.20 D.21
8.用>表示進棧操作，<表示出棧操作，若元素進棧的順序為“＋/*\”，出棧順序為“＋\〔%/”，則由>和<表示的操作串是(　　)
A.><>>><<><< B.><>><><<><
C.>>>><<><<< D.><>>>><<<<
9.棧底至棧頂依次存放元素 A、B、C、D，在第五個元素E入棧前，棧中元素可能出棧，則 5 個元素全部出棧后，出棧的序列可能是(　　)
A.ABCED B.DBCEA C.CDABE D.DCBEA
10.有如下Python程序段：
w＝input()
flag＝True
st＝[″″]；top＝－1
c＝0
for i in w ：
　 if flag and i＝＝″(″：
　top＝top＋1
　 st[top]＝i
　flag＝False
　 elif not flag and i＝＝″)″：
　top＝top－1
　c＝c＋1
　flag＝True
print(c)
若輸入w的值為″()()(()()))″，則以上程序運行后，輸出結果為(　　)
A.6 B.3 C.4 D.5
11.有如下 Python 程序段：
s＝[0]*10；q＝[0]*10
a＝[6，3，2，4，2，1，5]
n，top，head，tail＝len(a)，0，0，0
s[top]＝a[0]
for i in range(1，n)：
　 while top！＝－1 and a[i]>s[top]：
　 q[tail]＝s[top]
　tail＋＝1
　top－＝1
　 top＋＝1
　 s[top]＝a[i]
while top?。剑?：
　 print(s[top]，end＝' ')
　 top－＝1
print() #輸出換行
while head?。絫ail：
　 print(q[head]，end＝' ')
　 head＋＝1
程序段運行后， 輸出的結果第2行第3個數字為(　　)
A.1 B.2 C.3 D.4
12.有如下Python程序段：
que＝[1，5，3，2，7]＋[0]*100　　　#構建列表que，形如[1，5，3，2，7，0，0，0，…]
head＝0；tail＝5
st＝[0]*len(que)　　　　　　　　#構建棧st
top＝－1
while head?。絫ail：
　 while top?。剑? and que[head]>st[top]：
　que[tail]＝st[top]
　tail＋＝1
　top－＝1
top＋＝1　　
　 st[top]＝que[head]
　 head＋＝1
執行該程序段后，棧st從棧頂到棧底的元素依次為(　　)
A.7，5，3，2，1 B.1，2，3，5，7
C.0，1，2，3，5，7 D.7，5，3，2，1，0
二、非選擇題(本題共4小題，共26分)
13.(6分)甲乙雙方進行一場球類比賽，一局計分的規則是：贏1球得1分，用“1”表示；輸1球失1分，用“0”表示。當任一方得分大于等于6分，且領先對方2分及以上，領先方贏一局。如甲選手一局比賽數據為“101110101”，表示甲選手得6分失3分，局比分6∶3。
小王用一個字符串記錄了甲選手多局比賽數據，其中有一處錯誤，位于連續多個“0”的最后一個。為了找出錯誤，小王的處理方法如圖a所示，對示例中疑似錯誤位置6和20分別修改數據，并統計每局比分。他編寫了Python程序，功能如下：輸入記錄數據，輸出修改位置以及修改后每局的比分。程序運行界面如圖b所示。
圖a
輸入記錄數據： 1000001110101010100101010101101011 分析結果為： 修改位置　修改后每局的比分 6 /18：16 20 /4：6/6：4/8：6
圖b
實現上述功能的Python程序如下， 請回答下列問題：
rec＝input(″輸入記錄數據：″)
s＝list(rec)
①________________
k＝m＝i＝0
pos＝[]
while ik＝i
while s[i]＝＝″0″ and ii＝i＋1
if ②________________：
m＋＝1
pos.append(i－1)
i＝i＋1
print(″分析結果為：″)
print(″修改位置″，″修改后每局的比分″)
for i in range(m)：
f1＝f2＝0
k＝pos[i]
s[k]＝″1″
sp＝″　 ″＋str(k)＋″　　″
for j in range(n)：
if s[j]＝＝″1″：
　　　f1＋＝1
else：
　　　f2＋＝1
if ：
　　　sp＝sp＋″/″＋str(f1)＋″：″＋str(f2)
　　　f1＝f2＝0
if f1＋f2>0：
sp＝sp＋″/″＋str(f1)＋″：″＋str(f2)
print(sp)
③________________
(1)請在劃線處填入合適的代碼。
劃線①處應填入的代碼為_____________________________________________；
劃線②處應填入的代碼為______________________________________________；
劃線③處應填入的代碼為________________________________________________。
(2)程序中加框處代碼有錯，請改正。
14.(6分)某APP為增加用戶活躍度，采用“簽到得積分換獎品”的形式來吸引用戶。簽到積分的規則與玩法如下：
①第一天簽到得1分，第二天簽到得2分，第三天簽到得3分，……第7天及7天以上簽到得7分；一旦中途漏簽，簽到積分從1分開始重新計算；積分每年最后一天結束時清零?，F在用“1”和“0”表示簽到和未簽到，如某用戶下載APP后第一天到第九天的簽到記錄為“101111011”，則這9天共獲得14個積分。
②APP每年會給用戶一次補簽一天的機會，補簽之后積分的連續性可以持續，例如上面的9天中如果補簽第七天增加積分最多，補簽后9天的簽到記錄將變為“101111111”，積分將達到29分。為了找出一年中最佳的補簽日，設計如下程序：從文件中讀取一年365天(2月以28天計)的簽到記錄并以字符串形式輸出，然后統計出全年的積分，并分析出補簽增加積分最多那天的日期及將這一天補簽后可增加積分數，程序輸出效果如圖所示。
全年簽到記錄：01100011011001000100111111101101 0101111100110111000011100101111001000000111001 1001101110110011110001011011101111001001010010 1010011000110011011101100110111100111010100001 1000101010100011111100101010011001101000010000 1001000010010111011010001101000000111110100011 0011010101001010111111000111111110111010001011 0110010101010011011111111101100110101111011011 010011100 年積分：426 補簽10月25日增加積分最多！可增加22分。
(1)若第1天到第18天的簽到記錄為“101110111001101111”，則補簽第________天可增加積分最多。
(2)請在劃線處填入合適的代碼。
def tongji(s)：　#統計字符串中的積分
sum，pre＝0，0
　 for i in range(len(s))：
　 if s[i]＝＝″1″：
　　 　if pre<7：
　　　　 　pre＋＝1
　　　sum＋＝pre
　else：
　　?、賍_______________
return sum
def check(ss)：
　 month＝{1：31，2：28，3：31，4：30，5：31，6：30，7：31，8：31，9：30，10：31，11：30，12：31}
　 max，index＝0，0
　 for i in range(len(ss))：
　 if ss[i]＝＝″0″：
　　　 head＝i－1
　　　tail＝i＋1
　　 while head>＝0 and ss[head]＝＝″1″：
　　　　　 head－＝1
　　　while tail<＝len(ss)－1 and ss[tail]＝＝″1″：
　　　　　tail＋＝1
　　　s1＝ss[head＋1：tail]
　　　②________________
　　　jfzj＝tongji(s2)－tongji(s1)
　　　if jfzj>max：
　　　　　max＝jfzj
　　　　　index＝i
　 k＝1
　 day＝index＋1
　 while ③________________：
　day＝day－month[k]
　k＋＝1
　 result＝″補簽″＋str(k)＋″月″＋str(day)＋″日增加積分最多！可增加″＋str(max)＋″分。″
　 return result
15.(7分)某餐廳餐桌設置如下表：
餐桌型號 2 人 小桌 4 人 方桌 6 人 大方桌 12 人 大圓桌
餐桌數量 8 15 10 4
平均就餐時間(分鐘) 25 45 60 80
有客人來就餐時其叫號系統會自動生成一個號碼，并根據人數安排餐桌型號；當對應餐桌型號有空桌時，按餐桌編號(由小到大)即時分配餐桌安排客人就餐；當對應餐桌型號沒有空桌時， 客人按先后順序排隊。程序部分運行界面如下：
11號客人，給您安排的是4人桌，前面還有0人在等位。 11號客人請用餐→4人桌2號 12號客人，給您安排的是2人桌，前面還有1人在等位。 13號客人，給您安排的是2人桌，前面還有2人在等位。
(1)定義如下 gettype函數，功能為輸入客人人數，返回對應桌型，請在程序劃線處填入合適代碼。
def gettype(num):
　type＝－1
　 for i in range(len(size)):
　 if num<＝size[i]：
　　　type＝i
　 　　__________
　　return type
(2)定義如下 checktable()函數，功能為輸入桌型，返回對應桌型空桌的編號，返回值類型為列表，請在程序劃線處填入合適代碼。
def checktable(n):
　ans＝[]
　for i in range(nums[n])：
　 if ____________：
　　　ans.append(i)
　return ans
(3)解決上述問題的主程序如下，請在程序劃線處填入合適代碼。
size＝[2，4，6，12] #每種桌型最大就餐人數
nums＝[8，15，10，4] #每種桌型的餐桌數量
times＝[25，45，60，80] #每種桌型平均就餐時間
flags＝[[True]*nums[i] for i in range(4)] #標記每張桌子的初始狀態
s_time＝10*60*60 #開始營業時間——10 點整，轉化為秒
e_time＝14*60*60 #結束營業時間——14 點整，轉化為秒
maxn＝50 #假設隊列已經足夠深
qc＝[[0]*maxn for i in range(4)] #循環隊列
now_time＝s_time
id＝0
head，tail＝[0]*4，[0]*4
while now_time　　number＝getinfo() #調用函數 getinfo()，獲取客人人數
if number>0：
　 id＋＝1
　type＝gettype(number) #根據就餐人數確定餐桌類型
　if type?。剑?：
　 　qc[type][tail[type]]＝id
　　 tail[type]＝(tail[type]＋1)%maxn
　　 qc_len＝①____________
　　　print(id，″號客人，給您安排的是″，size[type]，″人桌，前面還有″，qc_len－1，″人在等位″)
　else：
　　　print(id，″號客人，非常抱歉，沒有適合您的桌型！″)
　　　for i in range(4)：
　tables＝checktable(i)
　if ②____________：
　　　　　flags[i][tables[0]]＝False #入座第一個空桌
　　　　print(qc[i][head[i]]，″號客人請用餐→″，size[i]，″人桌″，tables[0]，″ 號″)
　　 　　　head[i]＝(head[i]＋1)%maxn
　　　now_time＋＝1
　　　#更新每張餐桌的就餐情況，代碼略
16.(7分)消消樂游戲。隨機產生5排(每排10個)a－e之間的隨機字母，相鄰兩個字母之間互不相同。玩家輸入一個字母，在第一排從左至右查找第1個與之相同的字母，消去該字母，左面的字母自動向右靠攏，若重組后相鄰兩個字母也相同，則消除相同的字母。如第1次輸入字母“a”，得到結果所圖b所示。若第1排找不到輸入的字母，則在前10個位置查找，如第2次輸入字母“a”，得到結果所圖c所示。前10個位置中找不到輸入的字母，則將該字母添加在最左邊，如第3次輸入字母“b”，得到結果所圖d所示。
ecebecaceb dedbabdecd edaeabdbec dabebcaeba cdcdcabceb 　　　 ece dedbabdecd edaeabdbec dabebcaeba cdcdcabceb 　　ecedcd edaeabdbec dabebcaeba cdcdcabceb 　 becedcd edaeabdbec dabebcaeba cdcdcabceb
圖a 圖b 圖c 圖d
編制Python程序實現游戲功能，代碼如下
def display(st，t，n)：
　 #按蛇形走線每排n個字母的方式顯示棧st中各個元素，代碼略。
#將產生的字符串入棧st1并顯示，代碼略。
st2＝[″″]*(n＋1) #臨時存儲棧st1頂部不能被消除的元素
top2＝－1
k＝0；chs＝[″a″，″b″，″c″，″d″，″e″]
while top1?。剑?：
k＋＝1
ch＝input(″輸入要消除的字母：″)
if ch not in chs：
continue
t＝0
while t#在棧st1頂部前n個元素中查找ch，若沒有找到，移動到棧st2中
　　
if t①________________
while st1[top1]＝＝st2[top2] and top1>－1 and top2>－1: #消除相同的字母
　　　　top1－＝1
　　　　top2－＝1
while top2?。剑?：
top1＋＝1
②________________
top2－＝1
if ③________________：
top1＋＝1
st1[top1]＝ch
display(st1，top1，n)
print(″恭喜你，大獲全勝，嘗試的次數有：″，k)
(1)當剩余的字母為“ababdaeababa”時，把全部字母消除完至少還要輸入的次數是________。
(2)實現查找將移動元素功能的方框處可能的語句有：
①top1－＝1　②top2＋＝1
③st2[top2]＝st1[top1]　④t＋＝1。
按程序執行的先后順序，可以選擇其中的語句和順序是：________。
(3)根據程序的功能，完善程序劃線處①②③的代碼。
(4)若輸入要消除的字母為“p”，________(填：是 /否)會對程序的運行結果有影響。
驗收卷(二)　字符串、隊列和棧
1.C　[本題主要考查的是字符串操作。本題的功能是統計循環的次數及將列表st中的字符進行反向拼接，列表中共有6個元素，因此循環次數為6，將列表st中的字符進行反向拼接后的結果為'nohtyP'，print輸出時字符串內容沒有引號，因此，答案為C。]
2.C　[本題考查字符串操作的相關知識。觀察代碼，t 初值為 0，a[t]為第 1 個字符，從第 2 個字符開始判斷： 若與 a(t)相同且 t>＝0，則 t＝t－1；若與 a(t)不同或 t<0，則 t＝t＋1，a(t)跟蹤新字符依據算法，ABD選項 t 值變化：－1，0，1，2，而C選項t 值變化：1，0，－1，0，可見 C 選項與其余三項不同，選 C。]
3.A　[本題考查程序代碼的閱讀理解能力，以及字符串相關函數的書寫。刪掉某個位置上的數字，使得剩下的數字構成的數最大。簡單的思路就是，從前往后找。發現某個數字比后面的數字小，將這個數字刪除即可。如果沒有這樣的情況，將最后的那個刪掉即可。]
4.D　[6出棧后入隊，1和3出隊后入棧，3出棧后入隊，因此隊列中有原來的5和入隊后的6、3。]
5.A　[操作過程：隊首出隊，緊接著3個入隊尾后出隊，直至隊列為空。ningbo→boing→goin→oin→ni→i。]
6.B　[隊列中初始1個元素，值為4。遍歷列表a中位置1到len(a)－1的元素，若遍歷的元素值比隊尾元素大，則將隊首出隊后再將a[i]入隊。若遍歷的元素值小于隊首，直接將a[i]入隊。隊列中元素變化情況為[4，2]、[2，5]、[2，5，1]、[5，1，9]。]
7.A　[本題考查隊列的操作。語句que[tail]＝i的功能是將數組a中數據依次入隊，并將隊列的數進行累加到sq中，當條件sq>key or tail－head>＝k時，依次出隊，并在sq中減去隊首的值，msq是出隊后(隊列中最多只包含k－1個元素)累加和的最大值。最大值為4＋5＝9、5＋10＝15、10＋8＝18、8＋13－8＝13(累加和大于20，還要出隊)。]
8.A　[本題考查棧的操作。＋入后馬上出，/*\\入，\〔出，棧中只有/，%入后馬上出，/再出。]
9.D　[本題考查出入棧相關知識點。四個元素的出棧順序是一定是DCBA。]
10.C　[本題考查棧的操作。當讀取到″(″進行入棧操作，并且flag值為False；當棧不為空，且讀取到″)″時，進行出棧操作。前面2對括號依次入棧出棧，c為2。連續讀取2個左括號，第2個左括號時，flag值為False，只有一個括號入棧。2對括號依次入棧出棧。讀取最后兩個右括號時，棧中無元素，不能出棧操作。]
11.A　[程序首先建立兩個長度為 10 的列表 s 與 q，將a[0]入隊。從索引位 1 開始向后遍歷列表 a，將s 列表小于a[i]的值出棧，加入到隊列 q 中。輸出時第一行為 s 中的元素，第二行是隊列 q 中的元素，輸出2 3 1 2 4。]
12.B　[程序功能是利用隊列將棧中的元素進行升序排列。若棧不為空，當隊首元素大于棧頂元素的值時，將棧中元素入隊并出棧，否則將隊首元素入棧并將隊首進行出隊操作。]
13.(1)①n＝len(rec)或 n＝len(s)?、趇－k>＝2　③s[k]＝″0″
(2)(f1>＝6 or f2>＝6) and abs(f1－f2)>＝2
解析　本題主要考查的是字符串的綜合應用。(1)本題的算法思想是首先找出01串中連續2個及以上“0”的位置(在列表中的索引位置)，然后根據記錄的位置，分別將記錄的位置上的“0”修改為“1”，統計比分，記得統計好比分后，應將記錄位置上的字符恢復為“0”。劃線①處的功能是求01串中字符的個數，因此代碼為n＝len(rec)，等價于 n＝len(s)；②處代碼的功能是判斷連續“0”的個數是否為2個及以上，k為連續“0”字符串中的起始位置，i為連續“0”字符串后的第1個“1”的位置，則連續“0”的個數為i－k，因此②處代碼為i－k>＝2；③處代碼的功能是恢復s[k]元素的值為“0”，因此代碼為s[k]＝″0″。(2)加框處的代碼表示一局比賽結束的條件，根據題意可知當任一方得分大于等于6分，且領先對方2分及以上時一局比賽結束，因此加框處語句應修改為(f1>＝6 or f2>＝6) and abs(f1－f2)>＝2。
14.(1)6　(2)①pre＝0?、趕2＝ss[head＋1：i]＋″1″＋ss[i＋1：tail]?、踕ay>month[k]
解析　本題考查字符串的相關知識。(1)修改第6天的值，連續1的天數最多。(2)①遇到“0”則重新開始計分，pre恢復初值。②check函數用于統計積分改變后的差值最大值。s2為將第i位字符改為“1”后的字符串：故②空建立s2字符串，填：s2＝ss[head＋1：i]＋″1″＋ss[i＋1：tail].③check函數最終返回的是一年中的某一天，接下來要計算出day對應的年月日。方法是通過day＝day－month[k]不斷向后計算月份，直到無法減出完整月份，③空填：day>month[k]。
15.(1)break　(2)flags[n][i]＝＝True　(3)①(tail[type]－head[type]＋maxn)%maxn　②len(tables)>0 and head[i]?。?br/>tail[i] 或 tables and head[i]?。絫ail[i]
解析　本題考查循環隊列的基本應用。(1)gettype 函數功能為輸入客人人數，返回對應桌型。size 數組存儲每種桌型最大就餐人數，從小桌開始枚舉，找到相應的規格就結束查找。
(2)checktable 函數功能找到對應桌型的空桌編號。nums 每種桌型的餐桌數量，flags 二維數組標記每種桌型每張桌子的初始狀態，n為桌型編號，nums[n]表示該種桌型中最多就餐桌位，在 flags[n] 列表中從頭開始(循環變量 i 從 0 至 nums[n]－1 中枚舉)查找值為 True(空桌)的編號，并將這些編號添加到列表 ans 中，因此答案為 flag[n][j]＝＝True。(3)①求隊列長度，qc 存儲循環列表的信息，type 表示餐桌類型，qc[type]就是存儲該類型的循環列表，循環隊列長度公式(tail－head＋maxn)% maxn，因此①答案為(tail[type]－head[type]＋maxn) % maxn。②輸出安排就餐情況。變量 i 表示每種桌型，安排座位的條件有兩個，一是這種桌型有客人來，即qc[i]隊列不為空；二是這種桌型有空位，tables 調用checktable(i)函數，獲取空位列表。
16.(1)2　(2)②③①保持順序不變，④可以在任何地方。
(3)①top1－＝1　②st1[top1]＝st2[top2]?、踭＝＝n　(4)會
解析　本題考查棧的基本操作。(1)第1次消除d，剩余“ababaeababa”，第2次消除e。(2)在棧st1頂部前n個元素中查找ch，若沒有找到，移動到棧st2中。指針top指向棧頂第1個元素，出棧時，先取出數據，再向前移動指針。入棧時，先向后移動指針，再存入數據。語句②top2＋＝1必定在語句③st2[top2]＝st1[top1]的后面，存入數據后，再出棧。變量t是統計比較的字符個數，可以在循環體的任意位置。(3)①當條件t

展開更多......

收起↑