資源簡介

(共55張PPT)
第三章　字符串、隊列和棧
驗收卷(二)　字符串、隊列和棧
(考試時間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'
解析　本題主要考查的是字符串操作。本題的功能是統計循環的次數及將列表st中的字符進行反向拼接，列表中共有6個元素，因此循環次數為6，將列表st中的字符進行反向拼接后的結果為'nohtyP'，print輸出時字符串內容沒有引號，因此，答案為C。
C
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)
C
運行程序段，輸入以下字符串，運行后變量 t 的值與其它三項不同的是(　　)
A.AABAB B.AAABA C.BAABA D.BBABA
解析　本題考查字符串操作的相關知識。觀察代碼，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.輸入一個數字字符串 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
A
k－＝1
print(s)
上述程序段中加框處可選語句為：①s＝s[i＋1：]　②s＝s[i＋1：len(s)－1]　③s＝s[：i]＋s[i＋1：len(s)－1]　④s＝s[：i]＋s[i＋1：]
則(1)(2)處語句依次是(　　)
A.①④ B.③② C.③④ D.①②
解析　本題考查程序代碼的閱讀理解能力，以及字符串相關函數的書寫。刪掉某個位置上的數字，使得剩下的數字構成的數最大。簡單的思路就是，從前往后找。發現某個數字比后面的數字小，將這個數字刪除即可。如果沒有這樣的情況，將最后的那個刪掉即可。
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
解析　6出棧后入隊，1和3出隊后入棧，3出棧后入隊，因此隊列中有原來的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＝″″)
A
　head＋＝1
　for i in range(3)：
　 q[tail]＝q[head]
　head＋＝1
　tail＋＝1
執行該程序段后，輸出結果為(　　)
A.nbgoni B.nbogni C.goninb D.ningbo
解析　操作過程：隊首出隊，緊接著3個入隊尾后出隊，直至隊列為空。ningbo→boing→goin→oin→ni→i。
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
B
　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
解析　隊列中初始1個元素，值為4。遍歷列表a中位置1到len(a)－1的元素，若遍歷的元素值比隊尾元素大，則將隊首出隊后再將a[i]入隊。若遍歷的元素值小于隊首，直接將a[i]入隊。隊列中元素變化情況為[4，2]、[2，5]、[2，5，1]、[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
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，還要出隊)。
A
8.用>表示進棧操作，<表示出棧操作，若元素進棧的順序為“＋/*\”，出棧順序為“＋\〔%/”，則由>和<表示的操作串是(　　)
A.><>>><<><< B.><>><><<><
C.>>>><<><<< D.><>>>><<<<
解析　本題考查棧的操作。＋入后馬上出，/*\\入，\〔出，棧中只有/，%入后馬上出，/再出。
D
9.棧底至棧頂依次存放元素 A、B、C、D，在第五個元素E入棧前，棧中元素可能出棧，則 5 個元素全部出棧后，出棧的序列可能是(　　)
A.ABCED B.DBCEA C.CDABE D.DCBEA
解析　本題考查出入棧相關知識點。四個元素的出棧順序是一定是DCBA。
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
C
解析　本題考查棧的操作。當讀取到″(″進行入棧操作，并且flag值為False；當棧不為空，且讀取到″)″時，進行出棧操作。前面2對括號依次入棧出棧，c為2。連續讀取2個左括號，第2個左括號時，flag值為False，只有一個括號入棧。2對括號依次入棧出棧。讀取最后兩個右括號時，棧中無元素，不能出棧操作。
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！＝－1：
　 print(s[top]，end＝' ')
　 top－＝1
print() #輸出換行
while head！＝tail：
　 print(q[head]，end＝' ')
　 head＋＝1
程序段運行后， 輸出的結果第2行第3個數字為(　　)
A.1 B.2 C.3 D.4
A
解析　程序首先建立兩個長度為 10 的列表 s 與 q，將a[0]入隊。從索引位 1 開始向后遍歷列表 a，將s 列表小于a[i]的值出棧，加入到隊列 q 中。輸出時第一行為 s 中的元素，第二行是隊列 q 中的元素，輸出2 3 1 2 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！＝tail：
　 while top！＝－1 and que[head]>st[top]：
　que[tail]＝st[top]
　tail＋＝1
B
　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
圖b
輸入記錄數據：
1000001110101010100101010101101011
分析結果為：
修改位置　修改后每局的比分
6 /18：16
20 /4：6/6：4/8：6
實現上述功能的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＝sp＋″/″＋str(f1)＋″：″＋str(f2)
print(sp)
③________________
(1)請在劃線處填入合適的代碼。
劃線①處應填入的代碼為_____________________________________________；
劃線②處應填入的代碼為______________________________________________；
劃線③處應填入的代碼為_____________________________________________。
(2)程序中加框處代碼有錯，請改正。
答案　(1)①n＝len(rec)或 n＝len(s) ②i－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.(6分)某APP為增加用戶活躍度，采用“簽到得積分換獎品”的形式來吸引用戶。簽到積分的規則與玩法如下：
①第一天簽到得1分，第二天簽到得2分，第三天簽到得3分，……第7天及7天以上簽到得7分；一旦中途漏簽，簽到積分從1分開始重新計算；積分每年最后一天結束時清零。現在用“1”和“0”表示簽到和未簽到，如某用戶下載APP后第一天到第九天的簽到記錄為“101111011”，則這9天共獲得14個積分。
全年簽到記錄：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
答案　(1)6　(2)①pre＝0　②s2＝ss[head＋1：i]＋″1″＋ss[i＋1：tail]　
③day>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.(7分)某餐廳餐桌設置如下表：
餐桌型號 2 人 小桌 4 人 方桌 6 人 大方桌 12 人
大圓桌
餐桌數量 8 15 10 4
平均就餐時間(分鐘) 25 45 60 80
有客人來就餐時其叫號系統會自動生成一個號碼，并根據人數安排餐桌型號；當對應餐桌型號有空桌時，按餐桌編號(由小到大)即時分配餐桌安排客人就餐；當對應餐桌型號沒有空桌時， 客人按先后順序排隊。程序部分運行界面如下：
(1)定義如下 gettype函數，功能為輸入客人人數，返回對應桌型，請在程序劃線處填入合適代碼。
def gettype(num):
　type＝－1
　 for i in range(len(size)):
11號客人，給您安排的是4人桌，前面還有0人在等位。
11號客人請用餐→4人桌2號
12號客人，給您安排的是2人桌，前面還有1人在等位。
13號客人，給您安排的是2人桌，前面還有2人在等位。
　 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！＝－1：
　 　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
　　　#更新每張餐桌的就餐情況，代碼略
答案　(1)break　(2)flags[n][i]＝＝True
(3)①(tail[type]－head[type]＋maxn)%maxn
②len(tables)>0 and head[i]！＝tail[i] 或 tables and head[i]！＝tail[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.(7分)消消樂游戲。隨機產生5排(每排10個)a－e之間的隨機字母，相鄰兩個字母之間互不相同。玩家輸入一個字母，在第一排從左至右查找第1個與之相同的字母，消去該字母，左面的字母自動向右靠攏，若重組后相鄰兩個字母也相同，則消除相同的字母。如第1次輸入字母“a”，得到結果所圖b所示。若第1排找不到輸入的字母，則在前10個位置查找，如第2次輸入字母“a”，得到結果所圖c所示。前10個位置中找不到輸入的字母，則將該字母添加在最左邊，如第3次輸入字母“b”，得到結果所圖d所示。
編制Python程序實現游戲功能，代碼如下
def display(st，t，n)：
　 #按蛇形走線每排n個字母的方式顯示棧st中各個元素，代碼略。
#將產生的字符串入棧st1并顯示，代碼略。
ecebecaceb dedbabdecd edaeabdbec dabebcaeba cdcdcabceb 　　　 ece dedbabdecd edaeabdbec dabebcaeba cdcdcabceb 　　ecedcd edaeabdbec dabebcaeba cdcdcabceb 　 becedcd
edaeabdbec
dabebcaeba
cdcdcabceb
圖a 圖b 圖c 圖d
st2＝[″″]*(n＋1) #臨時存儲棧st1頂部不能被消除的元素
top2＝－1
k＝0；chs＝[″a″，″b″，″c″，″d″，″e″]
while top1！＝－1：
k＋＝1
ch＝input(″輸入要消除的字母：″)
if ch not in chs：
continue
t＝0
while ttop2－＝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。
按程序執行的先后順序，可以選擇其中的語句和順序是：________。
答案　(1)2　(2)②③①保持順序不變，④可以在任何地方。　(3)①top1－＝1
②st1[top1]＝st2[top2]　③t＝＝n　(4)會
(3)根據程序的功能，完善程序劃線處①②③的代碼。
(4)若輸入要消除的字母為“p”，________(填：是 /否)會對程序的運行結果有影響。
解析　本題考查棧的基本操作。(1)第1次消除d，剩余“ababaeababa”，第2次消除e。(2)在棧st1頂部前n個元素中查找ch，若沒有找到，移動到棧st2中。指針top指向棧頂第1個元素，出棧時，先取出數據，再向前移動指針。入棧時，先向后移動指針，再存入數據。語句②top2＋＝1必定在語句③st2[top2]＝st1[top1]的后面，存入數據后，再出棧。變量t是統計比較的字符個數，可以
在循環體的任意位置。(3)①當條件t(考試時間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＝s[i＋1：len(s)－1]　③s＝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！＝－1：
　 print(s[top]，end＝' ')
　 top－＝1
print() #輸出換行
while head！＝tail：
　 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！＝tail：
　 while top！＝－1 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分開始重新計算；積分每年最后一天結束時清零。現在用“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！＝－1：
　 　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！＝－1：
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！＝－1：
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)　②i－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　②s2＝ss[head＋1：i]＋″1″＋ss[i＋1：tail]　③day>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]！＝
tail[i] 或 tables and head[i]！＝tail[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]　③t＝＝n　(4)會
解析　本題考查棧的基本操作。(1)第1次消除d，剩余“ababaeababa”，第2次消除e。(2)在棧st1頂部前n個元素中查找ch，若沒有找到，移動到棧st2中。指針top指向棧頂第1個元素，出棧時，先取出數據，再向前移動指針。入棧時，先向后移動指針，再存入數據。語句②top2＋＝1必定在語句③st2[top2]＝st1[top1]的后面，存入數據后，再出棧。變量t是統計比較的字符個數，可以在循環體的任意位置。(3)①當條件t

展開更多......

收起↑