資源簡介

第三章　字符串、隊列和棧
課時1　字符串
一、基礎鞏固
1.已知x＝″2.0＋3＝5.0″，下列表達式成立的是(　　)
A.len(x)＝＝8 B.x[0]>x[2]
C.x[：2]＝＝″2.0″ D.x[6：：]＝＝″5″
2.字符串變量s＝″2022jiaxing″，則表達式s[1：len(s)∥2]＋s[2]*2的值是(　　)
A.″20224″ B.″2026″ C.″022j22″ D.″022j4″
3.通過鍵盤輸入一串字符串，程序輸出該字符串的所有子串。例如，下面程序段當輸入“the”時，將輸出['t'，'th'，'the'，'h'，'he'，'e']。
s＝input(″請輸入一個字符串：″)
a＝[]
for i in range(len(s))：
　 for j in range((1)________________)：
a.append((2)________________)
　print(a)
為實現上述功能，上述程序段(1)(2)處的語句分別是(　　)
A.①i，len(s)　　　 ②s[i：j＋1]
B.①i，len(s)－i＋1 ②s[i：j＋i]
C.①i，len(s)－i＋1 ②s[i：j＋1]
D.①i，len(s) ②s[j：j＋i]
4.某RGB色彩模式圖像信息存儲在文本文件中，文件的一行存儲圖像的一個像素，現對圖像中連續的0或1進行壓縮，某個像素的壓縮算法如下：
def change(s): #對連續多個0或1進行壓縮，字符串s中不含換行符
　 i＝1；j＝0；result＝″″
　 sd＝″0123456789ABCDEF″
　 while i　 while i　　　 　i＋＝1
　 d＝i－j
　 s1＝s[j]＋sd[d%16]
　 if d>16：
　　　　s1＝s[j]＋sd[0]＋s1
　 result＋＝s1
　 j＝i
return result
若某個像素點的信息為“111100000000000000000001”，則壓縮后的信息為(　　)
A.41003011 B.140003 C.14000311 D.140F0411
5.有如下程序段：
s1＝″232″
s2＝″abcdef″
for i in s1：
　 m＝int(i)
　 c＝s2[m：m＋1]
　 s2＝s2[1：m＋1]＋c＋s2[m＋1：]
print(s2)
執行該程序段后，變量s2的值是(　　)
A.″eef″ B.″cdddef″ C.″dcdcdcdef″ D.″abccccdef ″
6.有如下程序段：
s＝″aabbbcc″
i＝3
while ij＝i－2
if s[i－1]＝＝s[i] and s[j]＝＝s[j－1]：
　 s＝s[：i]＋s[i＋1：]
else：
　 i＋＝1
print(s)
執行該程序段后，變量 s 的值是(　　)
A.″abc″ B.″aabbc″ C.″aabc″ D.″aabcc″
7.有如下 Python 程序段：
s＝″5A9C3B0E7D″
ans＝″″； i＝0
while s[i]！＝″0″：
　 t＝int(s[i])
　　ans＋＝s[t]
　　i＝t－1
print(ans)
運行該程序段后，變量 ans 的值是(　　)
A.″BCDEA″ B.″BCD″ C.″ABCD″ D.″BCDE″
二、能力提升
8.下列 Python 程序段功能為：輸入由英文字母組成的字符串，若字符串中有連續升序段(相鄰字符 ASCII 碼值增量為 1)，則把該升序段縮寫為“首字符－尾字符”構成的新字符串。例如：字符串為“abcbxy”，則縮寫成“a－cbx－y”。
s＝input(″請輸入字符串：″)
k＝len(s)；flag＝False；result＝″″
for i in range(0，k－1)：
　 if ①________________ :
　 result＝result＋s[i]＋″－″
　 flag＝True
　 elif ord(s[i])！＝ord(s[i＋1])－1:
　 result＝result＋s[i]
　 flag＝False
②________________
print(″縮寫后的字符串為″，result)
則劃線處應填入的代碼為(　　)
A.①ord(s[i])＝＝ord(s[i＋1])－1 and flag 　　　②result＝result＋s[i]
B.① ord(s[i])＝＝ord(s[i＋1])－1 and not flag 　②result＝result＋s[i]
C.① ord(s[i])＝＝ord(s[i＋1])－1 and flag 　　　②result＝result＋s[i＋1]
D.① ord(s[i])＝＝ord(s[i＋1])－1 and not flag 　②result＝result＋s[i＋1]
9.某字符串s是由一個原始字符串反復重疊形成的。例如字符串″abcababcababcab″的是由原始字符串″abcab″重疊而成。檢測的算法：將該字符串劃分成若干段，若字符串每一段與第一段相同，則認為該字符串是由這段字符重疊而成。為查找字符串s的原始字符串，有如下程序段：
s＝″abcababcababcababcababcab″
n＝len(s)；ans＝″″
for i in range(1，n∥2＋1)：
　 if ①________________
　for j in range(i，n，i)：
　 　 if ②________________
　　 　　　break
　　 else：
　　　　ans＝s[：i]
print(″原始串是：″，ans)
將劃線處填寫完整。
10.有Python程序段如下：
s＝'I Love You HangZhou！'
s1＝''
for i in range(0，len(s)，3)：
　 c＝s[i]
　 if ord(c)>＝ord('a')：
　 c＝chr(ord(c)－ord('a')＋ord('A'))
　 s1＝c＋s1
print(s1)
程序運行后，輸出的值是(　　)
A.OUAZU B.OUAU C.UZAUO D.UAUO
11.有如下Python程序段：
s＝″abbaddcab″
k＝0；r＝″″
b＝[″″]*6
for i in s：
　 if i＝＝b[k]：
　k－＝1
　 else：
　 k＋＝1
　b[k]＝i
for i in range(1，k＋1)：
　 print(b[i]，end＝″″)
執行該程序段后，輸出的內容是(　　)
A.abdc B.aacab C.c D.cab
12.判斷兩個字符串是否相等：規定字符“？”為萬能字符，即可與任意一個字符相等，在忽略字符串中空格以及不區分大小寫的前提下，判斷兩個字符串是否相同。Python程序運行界面如圖所示。
請輸入一個字符串：？？ a d ？？dad wd 請輸入另一個字符串：a a c？d？d w 兩個字符串相同
(1)根據以上規則字符串’？？ad？？dad wd’和字符串’a？？？c？d？d？d’是否相等____(填：是/否)。
(2)實現上述功能的Python程序如下，請在劃線處填入適當的代碼。
s1＝input(″請輸入一個字符串：″)
s2＝input(″請輸入另一個字符串：″)
s1＝s1.upper()
s2＝s2.upper()
s＝″″
#將字符串s1中的空格去掉
for i in s1：
if i ！＝″″：
①________________
s1＝s
#同上，將字符串s2中的空格去掉，代碼略
i＝0
if len(s1)！＝len(s2)：
print(″兩個字符串不相同″)
else：
while i　　c1＝s1[i]；c2＝s2[i]
　 　if c1＝＝c2：
　　 　 ②________________
　　else：
　　　 if ③________________：
　　　　 　 i＋＝1
　　　 else：
　　　 　　break
if i＝＝len(s1)：
print(″兩個字符串相同″)
else：
print(″兩個字符串不相同″)
13.小張參加學校舉行的密碼破解攻防比賽，他需要在規定時間破解對手密碼。比賽時，小張發現對方密文可能采用凱撒加密，這是一種簡單且廣為人知的加密技術，方法是將明文中的所有字母都在字母表上向后(或向前)按照一個固定數目進行偏移后被替換成密文，非字母保持原狀。例如，當偏移量是3的時候，所有的字母A將被替換成D，B變成E，Z變成C，以此類推。
小張為了增加破解難度，決定在凱撒加密基礎上，引入密鑰字符串，密鑰字符及對應的偏移量如下表所示，密鑰字符串長度不夠時，可循環使用。
密鑰 A B C D E F G H I J K L M
偏移量 0 1 2 3 4 5 6 7 8 9 10 11 12
密鑰 N O P Q R S T U V W X Y Z
偏移量 13 14 15 16 17 18 19 20 21 22 23 24 25
例如：若輸入明文為：Hello，輸入密鑰為：ABC，則得到密文為：Hfnlp
(1)若明文：ZhouShan密鑰為：LOVE，則密文為：________
(2)引入密鑰后的加密算法的Python程序代碼如下：
def change(x)：
ek＝[]
for c in x：
　　if ' a'<＝c<＝'z'：
　　　　①________
　 　elif ' A'<＝c<＝'Z'：
　　 　　#與小寫字母相似處理，代碼略
return ek
s＝input(″輸入原文：″)
key＝input(″輸入秘鑰：″)
keyn＝change(key)
ch＝″″
for i in range(len(s))：
k＝keyn[②________]
if ' a'<＝s[i]<＝'z'：
　ch＝③________
　result＝result＋ch
elif 'A'<＝s[i]<＝'Z'：
　#與小寫字母相似處理，代碼略
else：
　result＝result＋s[i]
print(result)
(2)在劃線處填寫合適代碼，完善程序。
(3)程序調試過程中，出現如下錯誤提示“NameError：name' result' is not defined”，產生此錯誤的原因是___________________________________________________。
14.查找包含26個小寫字母的最短字符串：輸入任意一串包含小寫字母的字符串(長度n>＝26)，要求找到長度最小的一段區間，能夠包含全部26個小寫英文字母。小王設計了Python程序用于搜索最短字符串，若無解，則輸出“無解！”，反之輸出該最小區間的長度以及字符的開始位置，并輸出相應的最短字符串，程序界面如圖所示：
請輸入字符串內容：wurfabcdefghijklmnopqrstuvwxyzzsdf 包含26個字母的字符串為：abcdefghijklmnopqrstuvw 最短長度：26　開始位置：4
本題的算法思想是：
①確定初始右邊界：從第1個字符開始，向右搜索到包含全部26個字母的子串，并因此而確定右邊界，同時記錄每個字母在子串中出現過的次數。
②調整子串左邊界：若左邊界有重復的字母則表明該子串可縮短，故左邊可右移1位，……直到找到一個符合條件的子串并記錄，然后子串左邊界再右移1位。
③調整子串右邊界：子串右邊界繼續右移，在新子串符合條件后，記錄并進行比較。
重復②各調整步驟，直至遍歷完整個字符串，獲得并輸出滿足條件的最小長度字符串。
實現上述功能的Python程序如下，請回答下列問題。
text＝input(″請輸入字符串內容：″)
n＝len(text)
s＝[0 for i in range(n)]
for i in range(n)：
①________________
res＝″″
k＝left＝pos＝0
length＝n
f＝[0]*26
for i in range(n)：
if f[s[i]]＝＝0：
　　　　k＝k＋1
f[s[i]]＝f[s[i]]＋1
while ②________________：
f[s[pos]]＝f[s[pos]]－1
if ③________________：
　　　　k－＝1
　　　　if i－pos＋1　　　　　　length＝i－pos＋1
　　　　　　res＝text[pos：pos＋length]
　　　　　　left＝pos
pos＋＝1
if res ！＝″″：
print(″包含26個字母的字符串為：″，res)
print(″最短長度：″，length，″開始位置：″，left)
else：
print(″無解！″)
(1)對于字符串“abfabcfdeefed”，包含字母“abcdef”的最短字符串長度為________(填數字)。
(2)請在劃線處填入合適的代碼。
課時1　字符串
1.B　[本題主要考查的是字符串的函數及基本運算。len(x)的值為9，因此A選項錯誤；x[：2]的值為″2.″，因此C選項錯誤；x[6：：]的值為″5.0″，因此D選項錯誤；x[0]的值為″2″，x[2]的值為″0″，因為″2″>″0″，因此x[0]>x[2]，故答案為B。]
2.C　[本題主要考查的是字符串切片和運算。s[1：len(s)∥2]表示從第2個字符位置取到中間位置的前一個字符，結果為“022j”，s[2]*2表示索引第3個字符“2”重復2次，結果為“22”，最后連接兩個字符串，因此，答案為C。]
3.A　[本題考查雙重循環和字符串的切片。i表示切片的開始位置，j表示切片的結束位置。]
4.C　[本題考查字符串處理。變量j表示出現相同字符的起點位置，變量i表示結束位置后面第1個位置，s[i]＝＝s[i－1]表示有多個重復，s[j]＝＝s[i]表示單個，不重復。d表示重復的長度，由于一個點的像素，長度為24個二進制位，當d>16條件成立時，d∥16－1的值為0。字符串中包含4個1，19個0和1個1。]
5.B　[本題考查字符串的切片。s2的值從″bccdef″、″ccddef″變化到″cdddef″。]
6.D　[本題主要考查字符串的處理，即字符的比較和字符的刪除操作。變量s從″aabbcc″變化到″aabcc″。]
7.D　[變量t的值依次為5，3，9，7，對應s[t]的值依次為B、C、D、E。當i的值為6時，s[i]的值為0，結束循環。]
8.D　[本題考查字符串操作。①語句result＝result＋s[i]＋″－″是連接首字母，接著flag為True，因此flag表示是否找到起點，該空表示的是連續升序且為起點。②循環的條件for i in range(0，k－1)，只處理前k－1個字符，最后一個字符沒有處理。]
9.①n %i＝＝0　②s[j：j＋i]！＝s[：i]
解析　本題考查雙重遍歷的算法思想。一個原始字符串反復重疊，該原始字符串長度必定能被n整除，條件n %i＝＝0成立表示該長度i是n的因子，可能是原始字符串s[：i＋1]的長度，字符串s從第0個位置開始，到i－1位置是原始字符串，從i開始，每i個長度的字符串s[j：j＋i]是否是原始字符串，如果不是說明這段中不符合原始字符串。
10.D　[本題考查range函數的使用以及程序基本代碼的閱讀能力。根據range函數的參數，是從字符串s中從索引0開始，依次取出下標為0、3、6……位置的字符，如果字符是小寫，將它轉為大寫，并按逆序依次拼接。答案為D。]
11.D　[本題考查程序結構的靈活應用。程序算法為：依次從左向右提取s中每一個字符，如果與b[k]中字符不一致，則將該字符存儲到b[k＋1]中，如果一致，則k＝k－1。]
12.(1)是　(2)①s＝s＋i　②i＋＝1　③c1＝＝″？″ or c2＝＝″？″
解析　本題主要考查字符串的綜合應用。(1)依照題意，‘？’作為萬能字符與任意字符相等，問題中的兩個字符串依次比較是相等的。
(2)填空①處實現去掉字符串s1的空格，所以遍歷字符串時為非空格的時候，進行字符的連接，因此①處答案是s＝s＋i；填空②處當遍歷至相同位置的字符相等時，則進行下一個位置的字符比較，因此②處答案是i＋＝1；填空③處當兩個相同位置的字符不相等時，則考慮“？”作為萬能字符情況，因此③處答案是c1＝＝″？″ or c2＝＝″？″。
13.(1)KvjyDvvr　(2)①ek.append(ord(c)－ord(″a″))　②i%len(keyn)　③chr(ord(s[i])－ord(″a″)＋k)%26＋ord(″a″))　(3)變量result沒有賦初始值
解析　本題主要考查字符串的綜合應用。(1)根據表中提供數據，密鑰LOVE對應的偏移量分別是11，14，21，17，可得ZhouShan的密文是KvjyDvvr；
(2)①自定義函數change(x)將密鑰字符轉成對應的偏移量，結果存放在數組ek中，根據表中字母對應的偏移量，所以此處應填ek.append(ord(c)－ord(″a″))；
②遍歷明文字符應取密鑰列表中的每一個偏移量，由于密鑰長度可能小于明文長度，需循環使用，所以此處應填i%len(keyn)；③將原字符的字母按照密鑰的偏移值進行位移，由于需在字母范圍內進行循環位移，因此此處答案為chr(ord(s[i]－ord(″a″)＋k)%26＋ord(″a″))；
(3)在python中變量沒有賦初始值，表示沒有定義。
14.(1)6　 (2)①s[i]＝ord(text[i])－97或s[i]＝ord(text[i])－ord(″a″)　② k>＝26　或 k＝＝26　③f[s[pos]]＝＝0
解析　本題主要考查字符串的綜合應用。(1)包括字母“abcdef”的最短字符串為“abcfde”，長度為6。(2)①處代碼表示求每個輸入的小寫字母在字母表中的位置，其中字母“a”的位置為0，其他字母依次類推，因此①處代碼為s[i]＝ord(text[i])－ord(″a″)，小寫字母a的ASCII為97，故也可以寫為s[i]＝ord(text[i])－97；②處代碼表示當前字符串已包含26個字母時的處理， 變量k表示字母的種類數，如果字符串中已包含26個字母，則進行優化處理，看能否調整字符串的左邊界，因此②處代碼為k>＝26或 k＝＝26；③處代碼表示條件左邊界不能再調整的情況，表示該子串不可再縮短，因此③處代碼為f[s[pos]]＝＝0。課時2　隊　列
一、基礎鞏固
1.下列有關隊列的說法正確的是(　　)
A.隊列是一種先進先出的線性表，插入一端為隊首，刪除一端稱隊尾
B.隊列的存儲結構，可用數組實現，也可用鏈表實現
C.一隊列隊頭指針head，隊尾指針tail，則tail－1－head表示隊列中元素個數
D.學生排隊就餐與軟件連續撤消操作都是數據結構“隊列”的應用實例
2.有1個隊列，現有元素依次為1，2，3，4。約定：P操作是指1個入隊，T操作是指隊列中1個元素出隊后再入隊，Q操作是指隊列中1個元素出隊。則經過PPTQTPQ系列操作后，隊列中隊首到隊尾的元素依次為(　　)
A.1 B.1，3 C.3，4 D.3
3.創建一個容量為 3 的隊列，元素 2，3，5，1，3，5，2 依次等待入隊。入隊規則為：
①若當前待入隊元素已經在隊列中，則跳過該元素，否則轉②
②若當前隊列已滿，將隊首元素出隊列，否則轉③
③將當前待入隊元素入隊列
操作完成后，隊列中的元素為(　　)
A.2，3，5，1 B.1，2，3，5
C.2，3，5 D.5，1，2
4.某種特殊的隊列 Q，支持以下3個操作：操作Q1，若隊列非空，隊首元素出隊，并輸出；操作Q2，若隊列非空，隊首元素出隊；操作Q3，一個元素入隊；以上任意一種操作后，若隊列非空，新的隊首元素仍為隊列中所有元素的最小值。若隊列 Q 初始狀態為空，依次進行 Q3、Q2、Q1、Q2、Q3、Q1、Q3 七次操作后，下列說法正確的是(　　)
A.當前隊列中的元素個數為 2
B.輸出的元素個數為 2
C.第一個輸出的元素肯定比當前隊首元素大
D.隊列初始狀態是否為空對輸出結果有影響
5.假設隊列空間足夠，隊列中的元素個數為 5。約定：T 為入隊操作，Q 為出隊操作，則經過 TTQQTQTQQ一系列操作之后，隊首指針 head，隊尾指針 tail 的值可能為(　　)
A.head＝11，tail＝7 B.head＝7，tail＝11
C.head＝9，tail＝12 D.head＝12，tail＝9
6.列表q長度為20，q[0]到q[7]的值依次為'a'，'b'，'c'，'a'，'c'，'d'，'d'，'e'，執行如下程序段后，輸出的結果為(　　)
head＝tail＝0
for i in range(8)：
if q[i]＝＝q[head] and head！＝tail:
　 tail＋＝1
　 head＝tail
else：
　　tail＋＝1
print(q[head：tail])
A.cdde B.acdde C.eddc D.e
7.有如下程序段：
m＝3；n＝7
head＝tail＝0；ans＝0
vis＝[0]*10；q＝[0]*10
for i in range(n)：
　x＝int(input())
　 if (vis[x]＝＝0):
　 ans＋＝1
　if (tail－head>＝m):
　　　vis[q[head]]＝0
　 　　head＋＝1
　 q[tail]＝x
　 tail＋＝1
　vis[x]＝1
print(ans)
運行該程序段，依次輸入x的值：1，2，1，5，4，4，1。則程序運行完成后ans的值是(　　)
A.3 B.4 C.5 D.6
8.執行如下程序段后，輸出的結果是(　　)
q＝[6，8，9，7，4，5，2，3]
pre＝10
head，tail＝0，len(q)
while head！＝tail：
　if pre>q[head]:
pre＝q[head]
print(q[head]，end＝' ')
head＋＝1
A.6 8 9 B.6 4 2 C.6 5 3 D.6
9.有如下Python程序段：
a＝[3，6，10，5，9，4]
q＝[0]*len(a)
k＝int(input(″輸入k的值：″))
head＝tail＝0
s＝ans＝0
for i in a：
　 q[tail]＝i
　 tail＝tail＋1
　s＋＝i
　if ansans＝s
　while ik：
s－＝q[head]
head＝head＋1
執行該程序段后，輸入k的值為2，變量ans的值是(　　)
A.18 B.19 C.21 D.22
二、能力提升
10.有如下Python程序段：
Q＝[0]*10
cnt，head，tail＝0，0，0
S＝input()
for i in range(0，9，2)：
　 t＝S[i]
　n＝int(S[i＋1])
　if t＝＝'A'：
　 for j in range(n)：
　　　 Q[tail]＝cnt
　 　　tail＋＝1
　　 　cnt＋＝1
elif t＝＝″D″：
　while head！＝tail and n>0：
　　 head＋＝1
　　 n－＝1
print(Q[head : tail])
若輸入S的值為″A2D1A1D3A2″，則程序的輸出結果是 (　　)
A.[3，4，5] B.[3，4] C.[4，5] D.[4]
11.有如下程序段：
s＝input()
head＝0; tail＝0; ans＝0; tmp＝″
q＝[″]*100
flag＝True
for i in range(len(s))：
　　　if s[i]＝＝'，':
while head！＝tail：
　　　tmp＋＝q[head]
　　　head＋＝1
　　　if flag and head　　　　　　head＋＝1
　　　flag＝not flag
　ans＋＝int(tmp)
　tmp＝″； flag＝True
　elif '0'<＝s[i]<＝'9'：
　q[tail]＝s[i]
　tail＋＝1
若輸入s為“1－500，2023900－，”，執行該程序段，變量ans的值為(　　)
A.100 B.22300 C.22351 D.22400
12.某市舉辦科技嘉年華活動，為了激發學生的參與積極性，舉辦方推出了玩游戲得積分，積分兌換禮物的活動。活動中游戲分為簡單和困難兩種，參與游戲就可以獲得相應的積分，當完成困難游戲時，除了獲得相應積分外，還可獲得一張“積分翻倍卡”，一張“積分翻倍卡”可用于一個簡單游戲，使簡單游戲的積分翻倍。
“積分翻倍卡”使用規則如下：
1)當簡單游戲開始時，如果有“積分翻倍卡”可用，則一定會使用。
2)“積分翻倍卡”需在15分鐘內使用。比如困難游戲完成時間是9：15分，則獲得的“積分翻倍卡”將在9：15分激活，且超過9：30分將失效。
3)如果有多張“積分翻倍卡”，則優先使用最早的“積分翻倍卡”。
某同學的游戲記錄如圖a所示(類型0表示困難游戲，類型1表示簡單游戲)，小明讀取游戲記錄，編寫Python程序計算出該同學游戲的最終得分。程序運行結果如圖b 所示，請回答下列問題：
序號 類型 積分 開始時間 完成時間
1 0 10 9：10 9：15
2 1 3 9：15 9：28
3 1 5 9：38 9：42
4 0 12 9：58 10：05
5 1 3 10：20 10：36
6 0 15 10：48 10：55
7 1 3 11：25 11：29
圖a
(1)若某同學參加游戲的記錄如圖c所示，則他獲得的積分是________分。
(2)定義如下函數 change(t)，參數t為游戲時間，函數功能是將時間t轉換為分鐘并返回。如：t＝″9：20″時，轉換為整數(分鐘)值是560，函數返回值為560。
函數代碼如下，請在劃線處填入合適的語句。
def change(t): #參數t的時間格式為：″小時：分鐘″
m＝t.split(″：″)　　
s＝____________
return s
(3)計算游戲積分的部分Python程序如下，請在劃線處填入合適的代碼。
從Excel文件中讀取游戲過程記錄，存儲在列表s 中，如s＝[[1，0，10，550，565]，[2，1，3，565，568]，...]，s[i]表示第i個游戲記錄，s[i][0]，s[i][1]，s[i][2]，s[i][3]，s[i][4]依次存儲游戲的序號、類型、積分、開始時間，完成時間；當游戲類型s[i][1]值為日時表示困難游戲，為1則表示簡單游戲；
將困難游戲取出存入列表a中，列表 a按游戲完成時間升序排序；
將簡單游戲取出存入列表b中，列表b按游戲開始時間升序排序，代碼略
que＝[－1]*(len(a)＋len(b)＋1)
head＝tail＝0
total＝0
for i in range(len(a)): #累加游戲積分，將“積分翻倍卡”激活時間加入隊列
total＋＝a[i][2]
①____________
tail＋＝1
for i in range(len(b)) ：
　 while head　 print(que[head]∥60，″： ″，que[head] % 60，″時刻生效的″＋″積分翻倍卡過期；″)
　 head＋＝1
　　if head　 print(b[i][3]∥60，″：″，b[i][3]%60，″時刻使用了積分翻倍卡；″)
　③____________
　head＋＝1
　　else：
　total＋＝b[i][2]
print(″總共獲得積分為： ″，total，″分，″，″剩余積分卡有： ″，tail－head，″張。″)
13.某文本編輯軟件可以把所做的文本編輯操作記錄下來，并通過撤銷和恢復命令來撤銷一步操作或恢復一步撤銷的操作，也可以通過數字命令一次性撤銷最近的多步文本編輯操作，如圖所示。
設計算法模擬該功能。約定：①操作記錄只存儲文本編輯指令；②存儲步數最多為 5步，存滿后早期的操作記錄將被覆蓋；③程序只顯示操作記錄的可“撤銷”記錄，可 “恢復”記錄不顯示；④一旦有新的文本編輯操作，則清空所有可“恢復”記錄。
人機交互的指令如下(所有操作示例都基于上一個示例結果繼續操作)：
類型 指令 示例 程序輸出結果
文本 編輯 “T1”、“T2”、“T3”、“T4”表示四種文本編輯操作 對文本依次做“ T1 ” 、 “T2”、“T3”、“T4” 操作后，再輸入指令“T2” 請輸入操作指令：T2 指令B可用：指令F不可用 可撤銷記錄：T1/T2/T3/T4/T2/
撤銷 “B”表示撤銷 1 步操作 輸入“B” 結果：撤銷最近一步操作 “T2” 請輸入操作指令：B 指令B可用：指令F可用 可撤銷記錄：T1/T2/T3/T4/
數字“1”～“5”表示撤銷多步操作 輸入“3” 結果：撤銷最近 3 步操作 “T4”、“T3”和“T2” 請輸入操作指令：3 指令B可用：指令F可用 可撤銷記錄：T1/
恢復 “F”表示恢復 1 步撤銷的文本編輯操作 輸入“F” 結果：恢復最近的 1 步文本編輯操作“T2” 請輸入操作指令：F 指令B可用；指令F可用 可撤銷記錄：T1/T2/
文本 編輯 在撤銷或恢復操作之后繼續新的文本編輯操作 輸入“T1” 結果： 可“ 恢復” 記錄 “T3”、“T4”、“T2” 被清空 請輸入操作指令：T1 指令B可用；指令F不可用 可撤銷記錄：T1/T2/T1/
所有指令均可使用多次。每次輸入一個指令后都輸出“F”指令和“B”指令是否可用以及當前可撤銷記錄。所有無效操作指令輸入后均提示“Input Error！”。輸入“#”則結束程序。請回答下列問題：
(1)由題意可知，當依次執行指令“T2”、“T2”、“T1”、“T3”、“T1”、“T4”，則最終可撤銷記錄共有__________個。
(2)模擬實現該功能的 Python 代碼如下，請在劃線處填入合適的代碼。
def printh(head，cur)：
　print(f[flag[0]*2＋flag[1]])
　 s＝″可撤銷記錄：″
　 while head！＝cur＋1:
　s＝s＋hist[head]＋″/″
　①____________
　print(s)
opera＝[″T1″，″T2″，″T3″，″T4″]
f＝{0：″指令 B 不可用；指令 F 不可用″，1：″指令 B 不可用；指令 F 可用″，2：″指令 B 可用；指令 F 不可用″，3：″指令 B 可用；指令 F 可用″}
maxn＝5 #歷史記錄最多存儲的步數
maxsize＝100 #設定最多輸入文本編輯指令 100 次
hist＝[″″]*maxsize
cur＝－1；tail＝0；head＝0
flag＝[0，0] #記錄指令 B 與指令 F 的狀態
while True：
　d＝input(″請輸入操作指令：″)
　if d＝＝″#″： break
　if d in opera：
　if ②____________：
　　　head＝head＋1
　cur＝cur＋1；hist[cur]＝d
　tail＝cur＋1
　flag＝[1，0]
　printh(head，cur)
　　elif ″1″<＝d<＝str((cur－head＋1)):
　 cur＝③____________
　if cur＝＝head－1:
　　　flag[0]＝0
　flag[1]＝1
printh(head，cur)
　　elif d＝＝″F ″and tail！＝cur＋1:
　#恢復功能代碼略
　　elif
　if cur＝＝head：
　　　flag[0]＝0
　flag[1]＝1
cur＝cur－1
　printh(head，cur)
　else：
　print(″Input Error! ″)
(3)若加框處代碼誤寫為“d＝＝″B″”，會導致某些情況下無法得到符合判斷功能的結果。下列 4 組數據中能測試出這一問題的是__________(多選，填字母)
選項 依次輸入下列操作指令
A “B”
B “T1”、“B”、“B”
C “T1”、“1”、“B”
D “T1”、“T2”、“B”
課時2　隊　列
1.B　[本題考查隊列的性質。A選項隊列在隊尾插入，在隊首刪除；C選項隊尾指針tail指向隊尾元素的下一個位置，所以tail－head表示隊列中元素個數；D選項軟件連續撤銷操作是撤銷前一步操作，是棧的應用實例。]
2.D　[元素1，2入隊，1出隊后入隊，隊列為2，1。2出隊，1出隊后入隊，3入隊，1出隊，因此隊列中只有元素3。]
3.D　[本題考查隊列性質。2，3，5入隊，隊滿。2出隊，1入隊，隊列為3，5，1；3和5在隊列中，跳過該元素。3出隊，才能讓2入隊，隊列中元素為5，1，2。]
4.D　[操作Q3、Q2之后，隊列為空。Q3、Q1，隊列為空。因此隊列中元素個數為1，Q1操作出隊并輸出元素，輸出的元素個數為1。C選項沒有可比性。D選項若隊列不為空，則Q3、Q2、Q1、Q2輸出的結果不一樣。]
5.B　[本題考查隊列基本操作。經過4次入隊，5次出隊，因此隊列中共有4個元素。由于隊列空間足夠，因此隊尾指針大于隊首指針。A選項隊尾應大于隊首。B選項隊列中元素個數為11－7＝4，符合題目要求。C選項隊尾應大于隊首。D選項隊列中元素個數為12－9＝3，不符合題目要求。]
6.A　[分析程序段可知，該程序段實現的是一種消消樂游戲，即若新遍歷到的元素和隊首的元素不同或者隊列為空，則將新元素入隊。若新遍歷到的元素和隊首的元素相同，則將所有隊列中的元素清空。因此隊列中最后剩余的元素為 c，d，d，e。]
7.C　[本題考查隊列的算法實現。vis是一個標志數組，當其元素值為0時，可以入隊，保證隊列中數據是唯一的。當隊列中元素個數大于等于3時，將進行出隊操作。ans統計入隊次數。輸入x的值1，2入隊，接著1不能入隊，5入隊，當輸入4時，讓1出隊，4入隊。第2個4不能入隊，最后一個1入隊。]
8.B　[本題考查隊列的基本操作。程序的功能是查找隊列中最小值，pre初值為10，每次出隊一個元素，出隊元素與pre比較，記錄其最小值的過程。]
9.C　[遍歷數組a并累加數組元素值，求隊列的最大值；當遍歷到的當前值小于隊首或是長度大于k，將隊首元素出隊。s的值依次為[3，6，10]＝19，[6，10，5]＝21，[5，9]＝14，[5，9，4]＝18。]
10.B　[本題考查隊列的入隊與出隊操作。字符串S中兩個字符為一組，第1個元素t代表入隊或出隊，第2個元素代表n入隊或出隊的次數。A是入隊，D是出隊，若出隊過程中隊空，則中止出隊。]
11.D　[本題考查隊列的程序實現。在for循環中，當s[i]的值為數字字符時，將s[i]放入隊列中；當s[i]為’，’時，將隊列中的字符出隊并連接。當flag為True時，字符出隊但不連接到tmp中；其余字符忽略不處理。因此當輸入的字符串為“1－500，2023900－，”時，遇到第一個’，’字符，則ans加上100，然后再對于進入隊列中的字符串“2023900”進行計算，故最后的結果為22400。]
12.(1)40　(2)int(m[0])*60＋int(m[1])　(3)①que[tail]＝a[i][4]　②que[head]＋15解析　本題考查隊列的基本操作。(1)完成困難游戲獲得積分翻倍卡，一張積分翻倍卡使簡單游戲的積分翻倍，但積分卡在15分鐘內有效，14：47激活卡，15：10已經過期。積分為10＋5*2＋15＋5。(2)將時間按冒號分隔，得到一個列表，列表中有兩個值，分別為m[0]和m[1]。(3)①將積分卡激活時間加入隊列，困難游戲完成時間就是卡激活時間。②遍歷列表b，簡單游戲一開始就可以使用翻倍卡，因此計算翻倍卡的激活時間與當前簡單游戲開始時間的時間差，該時間差大于15分鐘時，卡失效。③使用翻倍卡，積分將翻倍。
13.(1)5　(2)① head＋＝1　②cur－head＋1＝＝maxn或tail＝＝cur＋l and tail－head＝＝maxn　③cur－int(d)　(3)ABC
解析　本題考查隊列的基本操作。(1)存儲步數最多為 5步，存滿后早期的操作記錄將被覆蓋。(2)①head表示隊首，cur表示最后一個元素指針，每輸出一個元素，就要出隊。②當d是文本編輯指令時，存儲步數最多為 5步，超出隊首元素將不能撤消。cur初值為－1，一個元素入隊后，值為0，因此cur表示列隊中最后一個元素，因此隊列總共元素個數為cur＋1－head。③當d為撤消步數時，cur表示撤消后的元素位置，因此cur將減去int(d)的值。(3)A選項cur小于head無法輸出。B選項撤消一步后，效果同A。C選項1表示撤消一步，效果同B。D選項有兩個元素，可以輸出。課時3　棧
一、基礎鞏固
1.棧s的最大長度為4，初始已有兩個元素在棧內，棧底為a，棧頂為b，經過一系列入棧、出棧操作，若元素入棧的順序是c，d，e，f，則可能的出棧序列為(　　)
A.c，a，b，e，f，d B.b，d，f，e，c，a
C.a，b，d，c，e，f D.b，e，f，c，d，a
2.有一個隊列和一個棧，其中隊列中隊首到隊尾的元素依次為3，15，8，7，棧中棧頂到棧底的元素依次為6，9，12，10。現在有兩種操作，操作S是指隊列中1個元素出隊后入棧，操作Q是棧中1個元素出棧后入隊。則經過QSSQSQQS操作后，隊列中隊首到隊尾的元素依次是(　　)
A.6，15，8，3 B.10，15，8，3
C.3，6，15，7 D.3，10，15，7
3.用“除二取余”法將十進制轉換為二進制數，用棧的方法操作，需要把得到的余數依次入棧，除盡后再把余數出棧即可。若要將十進制數n(0≤n<64)轉換為二進制數，則設置棧的長度至少為(　　)
A.3 B.4 C.5 D.6
4.已知棧k的入棧順序為2，7，3，1，6，9，第2個出棧的是6，第5個出棧的是2，則最后出棧的元素是(　　)
A.7 B.3 C.1 D.9
5.已知字符“a”的ASCII碼值為97，有如下Python程序段：
que＝[″″]*20
head，tail＝0，0
for i in range(3)：
　que[tail]＝chr(97＋i)
　 tail＋＝1
st＝[″b″，″c″，″d″，″a″]
top＝3
while head－1:
　if st[top]＝＝que[head]：
head＋＝1
　else：
que[tail]＝st[top]
tail＋＝1
　top－＝1
print(que[head：tail])
執行該程序段，則輸出的結果是(　　)
A.['c'，'d'，'c'] B.['c'，'c'，'d']
C.['c'，″，'d'] D.['c'，'d']
6.用棧的思想編寫進制轉換中的“除二取余法”的Python程序如下：
st＝[－1]*100
top＝－1
n＝int(input(″請輸入一個十進制數″))
while n>0：
n∥＝2
while top！＝－1：
　　print(st[top]，end＝″″)
　　top－＝1
方框處的代碼由以下三條語句組成：①st[top]＝x　②x＝n%2　③top＋＝1下列語句順序正確的是(　　)
A.①②③ B.①③② C.②①③ D.②③①
7.有如下Python程序段：
s＝input(″請輸入一個僅由小寫英文字母組成的字符串：″)
st＝[″″]*len(s)
top＝－1
t＝[－1]*26
for i in range(len(s)):
　id＝ord(s[i])－97
　 if t[id]＝＝－1：
　top＋＝1
　st[top]＝s[i]
　t[id]＝top
　else：
　 first＝t[id]
　while top>＝first and top！＝－1:
　　num＝ord(st[top])－97
　　t[num]＝－1; top－＝1
print(st[：top＋1])
若從鍵盤輸入的值為″hellopython″，則輸出的值為(　　)
A.['o'，'n']
B.['h'，'e'，'n']
C.['h'，'e'，'l'，'o'，'p'，'y'，'t'，'n']
D.['h'，'e'，'o'，'p'，'y'，'t'，'h'，'o'，'n']
8.有如下Python程序段：
import random
s＝[3，2，7，6，9]
st＝[0]*len(s)
top＝－1；i＝0
while i　op＝random.randint(0，1)
　if top＝＝－1 or op＝＝0 and s[i]>st[top]：
　top＋＝1
　st[top]＝s[i]
　elif top>＝1 and op＝＝1 and s[i]>st[top－1]：
　st[top]＝s[i]
　i＋＝1
while top！＝－1：
　　　print(st[top]，end＝″ ″)
　　　top－＝1
執行該程序段后，輸出的結果不可能是(　　)
A.3 B.9 6 2　 C.9 6 3 D.9 7 3
9.如下Python 程序段的功能是判斷一個表達式中的括號(只有小括號)是否匹配，
exp＝input(″請輸入表達式：″)
top＝－1；n＝len(exp)∥2；flag＝True
stack＝[″″]*n
for ch in exp:
　if ch＝＝″(″：
　 if ①____________：
　　　flag＝False；break
top＋＝1；stack[top]＝″(″
　　elif ch＝＝″)″：
　if top<0：
　　　　flag＝False；break
top－＝1
if ②____________：
　print(″括號匹配″)
else：
　　print(″括號不匹配″)
則劃線處應填入的代碼是(　　)
A.① top>＝n ② flag and top＝＝0
B.① top＝＝n－1 ② flag and top＝＝0
C.① top>＝n ② flag and top＝＝－1
D.① top＝＝n－1 ② flag and top＝＝－1
二、能力提升
10.某棧入棧序列為“A、B、C、D、E”，若第一個出棧的元素為“C”，最后一個出棧的元素為“E”，則可能的出棧序列有(　　)
A.3種 B.4種 C.5種 D.6種
11.有如下 Python 程序：
s1＝[0]*5; s2＝[0]*5; top1＝－1；top2＝－1
a＝[9，2，5，6，1]
for i in range (len(a))：
　while top1！＝－1 and a[i]　 top2＋＝1
　s2[top2]＝s1[top1]
　top1－＝1
　top1＋＝1; s1[top1]＝a[i]
　while top2！＝1：
　top1＋＝1
　s1[top1]＝s2[top2]
　top2－＝1
print (s1[top1])
執行程序后的輸出結果是(　　)
A.1 B.5 C.6 D.9
12.有如下 Python 程序段：
import random
lst＝['A'，'B'，'C'，'D']
st＝[0] * len(lst)
i，top＝0，－1
while i　k＝random.randint(0，1)
　 if k＝＝0：
　 top＋＝1
　st[top]＝lst[i]
　i＋＝1
　　elif top！＝－1：
　lst[i]＝st[top]
　top－＝1
執行該程序段后，lst 的值不可能是(　　)
A.['A'，'B'，'C'，'D'] B.['A'，'B'，'A'，'C']
C.['A'，'A'，'C'，'D'] D.['A'，'A'，'C'，'A']
13.有如下 Python 程序段：
a＝{'<'：0，'('：1，'['：2，'{'：3，'>'：4，')'：5，']'：6，
'}'：7}
s1＝input()
s＝[8，0，0，0，0，0，0，0，0]
top＝0；flag＝True
for x in s1：
　 k＝a[x]
　if k<4：
if s[top]　　 flag＝False
　　　break
top＋＝1
s[top]＝k
else：
if s[top]！＝k－4:
　　　flag＝False
　　　break
top－＝1
if flag and top＝＝0:
　print(″YES″)
else：
　　　print(″NO″)
若輸出結果為“NO”，則 s1 輸入的值是(　　)
A.{}[]()<> B.[()]{<>} C.{[<()>]} D.{()[<>]}
14.有如下Python程序段：
import random
s＝″Happy″
stk＝[″″]*len(s)；top＝－1
i＝0；res＝″″
while i　 if random.randint(0，1)＝＝0 or top＝＝－1：
　top＋＝1；stk[top]＝s[i]
　elif s[i]>stk[top]：
　res＋＝stk[top]；top－＝1
　i－＝1
　i＋＝1
while top>＝0：
　res＋＝stk[top]；top－＝1
print(res)
執行該程序段后，res的值不可能是(　　)
A.″Hpapy″ B.″Happy″ C.″yppaH″ D.″Hpay″
15.判斷某序列b是否是入棧序列a＝[1，2，3，4，5]的出棧序列，程序如下：
a＝[1，2，3，4，5]
b＝list(map(int，input().split()))
stack＝[]
i＝j＝0
while i　 stack.append(①____________)
　 i＋＝1
　 while len(stack)>0 and ②____________：
　stack.pop()
　j＋＝1
if len(stack)＝＝0 and j＝＝len(a):
　print(b，'是'，a，'的出棧序列')
else：
　　print(b，'不是'，a，'的出棧序列')
劃線處應填寫的語句是(　　)
A.①a[i]　②stack[－1]＝＝a[j]
B.①a[i]　②stack[－1]＝＝b[j]
C.①b[i]　②stack[－1]＝＝b[i]
D.①b[i]　②stack[－1]＝＝a[j]
16.自從學習了不同進制之后，小明設計了一個計算不同進制數的加法器，并用Python編程實現。輸入一個加法算式，加數可以是十進制數、二進制數或者十六進制數，程序的功能是輸出它們的和。例如輸入形如“1010B＋1DH＋109D＝”的加法算式后，執行程序輸出“和是148”的結果。Python程序如下：
s＝input('輸入一個混合進制的加法算式：')
dic＝{'B'：2，'D'：10，'H'：16}
st＝[″]*100
top，i，x，m＝－1，0，0，0
while i　　　if s[i]＝＝'＋' or s[i]＝＝'＝'：
　　　 m＝①____________
　　　top＝top－1
　　　t＝0
　　　while top！＝－1：
　　　if st[top]>＝'A' and st[top]<＝'F'：
　　　　　　　st[top]＝ord(st[top])－ord('A')＋10
　　　else：
　　　　　　st[top]＝int(st[top])
　　　②____________
　　　t＝t＋1
　　　top＝top－1
　else：
　　　③____________
　　　st[top]＝s[i]
　i＝i＋1
print('和是'，x)
(1)將劃線處代碼補充完整。
(2)若輸入”101B＋DH＋100D”，輸出的結果是________。
17.某種密碼設計方法如下：給定兩個數組，數組元素由數字 1～9 組成，從中選出 k(k 小于等于兩個數組長度之和)個數字拼接成一個新的數，同一數組中取出的數字保持其在原數組中的相對順序，每個數組中至少有 1 個數被選中，滿足該條件的最大數即為密碼，程序運行界面如圖所示。
請輸入數組1：3　4　6　5　7　8 請輸入數組2：9　1　2　5　8　3　4 請輸入k：6 密碼為：987834
請回答下列問題：
(1)程序部分代碼如下，請在劃線處填入正確的代碼。
def select_num(nums，k):
　stack＝[0]*len(nums)；top＝－1；cnt＝len(nums)－k
　for num in nums:
　 while cnt>0 and top！＝－1 and stack[top]　　　top－＝1；cnt－＝1
　top＋＝1
　①____________
　while cnt>0：
　 top－＝1；cnt－＝1
　return stack[0：top＋1]
def merge(a，b)：
　　c＝″；i＝0；j＝0
　　while ：
if j＝＝len(b) or i＝b[j]:
　　　　 c＋＝str(a[i])；i＋＝1
elif i＝＝len(a) or j　　　　　c＋＝str(b[j])；j＋＝1
　　return int(c)
num1＝input(″請輸入數組 1：″)
num2＝input(″請輸入數組 2：″)
num1＝list(map(int，num1.split(″ ″)))
num2＝list(map(int，num2.split(″ ″)))
k＝int(input(″請輸入 k：″))
②____________
for i in range(1，k):
　a＝select_num(num1，i)
　③____________
　c＝merge(a，b)
　if c>m：
m＝c
print(″密碼為：″＋str(m))
(2)加框處的程序代碼有誤，請改正。
課時3　棧
1.B　[A選項和C選項都出現了 a 在 b 前面出棧的情況，因此選項錯誤；D選項f 出棧時棧內的元素為(棧底)c，d(棧頂)，因此不可能 c 出棧，選項錯誤。]
2.A　[隊列特征為先進先出，有4次出隊，因此隊列中3，15，8，7全部出隊。Q出棧入隊，因此6先入隊，15和3在棧中，接著15入隊，8出隊入棧，因此后面是8和3。]
3.D　[十進制數n(0≤n＜64)轉換為二進制數，得到最大的是6位二進制數。]
4.D　[2是第1個入棧，當2出棧時，棧為空，只有9入棧再出棧。]
5. A　[第1個循環讓abc依次入隊。當隊列和棧不為空時，如果棧頂元素和隊首元素相同，則進行出隊和出棧操作，否則將棧頂元素出棧并入隊。棧頂和隊首均為″a″，出隊和出棧操作，接著″d″入隊，″d″出棧，接著″c″入隊，″c″出棧，隊列中元素為″bcdc″，接著″b″出隊和出棧。]
6.D　[入棧必先移動top指針，入棧元素為x，先對x進行除2的余數賦值。]
7.A　[遍歷字符串s，將每個字母轉換成0～25之間對應的數字。t列表是每個字母出現在棧中位置的桶。若字母不在棧中，將該字母入棧，同時記錄該字母為當前棧頂位置。若該字母已經存在于棧中，將后入棧的字母進行出棧操作，并在桶中作－1的標記。最后一個h讓前面所有字母出棧，因此棧中只有o和n。]
8.B　[本題考查棧的應用。當棧空入棧，因此3肯定在棧中。當op為0且s[i]>st[top]時，s[i]入棧，若產生op的值一直為1，則棧中只有3；入棧的元素比棧中元素大，2小于3，因此2不可能入棧，若7沒有入棧，則6可能入棧。]
9.D　[本題考查棧的基本操作。n值為len(exp)∥2，如果是″(″，進行入棧操作，如果棧頂指針為n，若再入棧，則左括號超出總字符串長度的一半，說明左括號的數量大于右括號。否則進行出棧操作，一個右括號匹配一個左括號，若在出棧前，棧為空，說明左括號少了。遍歷完后，用右括號對左括號進行出棧操作，如果棧為空，說明兩者數量相等。]
10.A　[C要出棧，棧中有A和B，E最后一個出棧，因此E最后入棧并馬上出棧，那么D可能在A前面，AB之間和B之后三個位置出棧。]
11.D　[本題考查棧的相關知識。若 a[i]12.B　[當k的值為0時，進行入棧操作；當k的值為1且棧不為空，進行出棧并替換lst[i]操作。由于i＋＝1操作發生在入棧過程中，因此必須要有4個元素出棧，但棧中可能有元素未出棧。A選項當隨機數4次均為0，全部元素均在棧中。C選項隨機數依次為0，1，0，0，有兩個元素在棧中。D選項隨機數依次為0，1，0，1，A先入棧，出棧后替換B，原B位置上的A再次入棧，最后替換D。B選項當i的值為2時，AB在棧中，應該B先出棧。]
13.C　[本題考查棧的操作。遍歷字符串s1并取出在字典中的值k，如果是符號的左半部分，并且棧頂元素大于等于k，將k值入棧。若k大于等于4，且棧頂元素等于k－4，出棧一個元素。當flag為True且棧中只剩下一個元素，輸出YES，否則輸出NO。A選項{在字典中鍵值為3，入棧，}在字典中鍵值為7，滿足條件棧頂元素等于k－4，讓棧頂元素出棧，其他符號均成對，相同方法處理。B選項[和(對應的鍵值分別為2和1，2入棧后，1小于棧頂2，1也入棧，接著)和]讓1和2依次出棧。{鍵值大于<鍵值，相同方法處理。C選項<和(對應的鍵值分別為0和1，當遍歷到(時s[top]14.A　[分為產生隨機數為0、隨機數為1且s[i]>stk[top]和隨機數為1且s[i]<＝stk[top]三種情況，在第2種情況中，讓較小的元素先出棧，同時i減1。第3種情況既不入棧，也不出棧，因此s中可能有部分元素未入棧。B選項H入棧，a讓H先出棧，a入棧，p讓a入棧，p和p均入棧，y分兩種讓兩個p出棧，最后在while結構中y出棧。C選項產生的隨機數均為0。D選項a讓H出棧，a入棧，隨機數為0，p入棧，第2個p隨機數為1，不入棧。y讓p和a出棧。A選項a不可能讓p出棧。]
15.B　[本題考查棧的操作與程序實現。由第6行的添加操作和第9行的刪除操作可以判斷stack用于存儲棧元素。可以通過將a元素不斷入棧，看能否形成和b一樣的出棧序列。第①空應該讓a中的元素入棧，填寫a[i]。而出棧時，需要判定棧頂元素是否和b序列中當前元素是否一致，一致才能出棧，盡可能形成與b一樣的序列。]
16.(1)①dic[st[top]]　 ②x＝x＋st[top]*m**t　 ③ top＝top＋1　(2)118
解析　程序可知st列表中保存著當前加數的每一位。如對于式子“1010B＋1DH＋109D＝”，當讀到第一個加號時，st列表的值為[‘1’，‘0’，’1’，’0’，’B’]，讀到第二加號時，st的值是[‘1’，‘D’，‘H’]，讀到最后’＝’號時，st的值是[‘1’，‘0’，‘9’，‘D’]。①st列表的最后一位是進制編號，讀取st最后一位，通過字典dic得到進制值。②使用權值法把st列表中保存的進制數轉化為十進制數。③讀取到加數的每一位數字，都保存在st列表中的相應位置。(2)由于式子中的最后一位不是’＋’或者’＝’， 所以st列表中的最后一個數字沒有加上。
17.(1)①stack[top]＝num　②m＝0　③b＝select_num(num2，k－i)　(2)i解析　本題考查棧和數據的歸并。(1)①函數select_num的功能是在數字串nums取出的數字位置不變的k個長度子串。cnt初值為len(nums)－k，即需要去除的數字個數，遍歷數字串nums并將數字入棧，若當前的數字比棧頂數字大，則需將棧中數字出棧，讓棧中形成一個遞減的系列，每出棧一個cnt減1，當cnt值為0時，則不再出棧。②對m賦初值0。③主程序外循環i的值從1循環到k，采用枚舉的思想，分別從一個數組num1中選出1到k－1個數字，則從另一個數組2中選出k－1到1個數字，所以第③空應填入b＝select_num(num2，k－i)。(2)自定義函數merge(a，b)用于將a、b兩個數組的值合并按順序合并成最大數，變量 i、j分別指向ab兩個數組中待合并區間的初始位置，根據if j＝＝len(b) or i＝b[j]可知當只剩下a列表中的數據未處理或者a數組的值大于b數組的值則c＋＝a[i]，否則當 i＝＝len(a) or j

展開更多......

收起↑