資源簡介

一．選擇題（共27小題）
1．有如下 python 程序段：
from random import*
s＝''
for i in range（1，4）：
k＝int（random（　　）*3+1）
c＝chr（96+k）
if i%2＝＝k%2：
s＝s+c
else：
s＝c+s
print（s）
若該段程序執行以后，s 的值不可能的是（　　）
A．'abc' B．'bbc' C．'aab' D．'caa'
2．有如下python程序段：（注：字母ASCII碼＞數字ASCII碼，小寫字母ASCII碼＞大寫字母ASCII碼）
import random
s＝“olympicGames2021“；ans＝““；i＝0
while i＜len（s）﹣2：
t＝int（random.random（　　）*2）+1
x＝s[i]；y＝s[i+t]
if x＞y：
ans+＝x
else：
ans+＝y
i＝i+t+1
print（ans）
執行程序后，輸出結果可能為（　　）
A．oyies B．ymcms2 C．oypcms2 D．ypces1
3．有如下Python程序段：
s＝“ABCDEF“
ch＝““
for i in range（0，len（s））：
a＝int（input（　　））；b＝（a+2）%6
ch＝ch+chr（ord（s[b]）+32）
print（ch）
運行程序后，依次輸入3、1、4、5、2、6，輸出ch的值是（　　）
A．cadebf B．fdabec C．aabbab D．ecfadb
4．有如下Python程序段：
s＝input（“請輸入一串字符串：”）
m＝cnt＝1
for i in range（1，len（s））：
if s[i]＞s[i﹣1]：
cnt+＝1
if cnt＞m：
m＝cnt
else：
cnt＝1
print（m）
該程序段的功能是（　　）
A．輸出字符串s中最大的字符的索引
B．輸出字符串s中最大的字符
C．輸出字符串s中最長的遞增序列
D．輸出字符串s中最長的遞增序列長度
5．有如下Python程序段：
s＝input（“請輸入一串字符串：”）
f＝True
for i in range（0，len（s）//2）：
if s[i]!＝s[len（s）﹣i﹣1]：
f＝False
break
print（f）
若執行該程序后，輸出的結果是“True”，那么輸入的值可能是（　　）
A．onion B．hello C．278 D．111
6．一個棧的入棧序列為1，2，3，4，5，則其出棧序列不可能為（　　）
A．1，2，3，4，5 B．4，5，3，2，1 C．4，3，5，1，2 D．3，2，1，5，4
7．一個棧的輸入序列為“12345“，輸出的第一個元素為“4“，則輸出的第3個元素不可能的是（　　）
A．1 B．2 C．3 D．5
8．某Python程序如下：
s＝“xyAB#Fk”；k＝x＝“”；flag＝True
for i in range（len（s））：
If“a”＜＝s[i]＜＝“z”and flag：
x＝chr（（（ord（s[i]）﹣95））%26+97）#字符“a”的ASCⅡ碼值為97
elif“A”＜＝s[i]＜＝“Z”and flag：
x＝chr＞（（（Cord（s[i]）﹣41））%26+65）#字符“A”的 ASCⅡ碼值為65
flag＝False
else：
x＝s[i]；flag＝True
k＝k+x
print（k）
執行該程序后，輸出值為（　　）
A．ZAyb#dK B．yzYZ#Dm C．zaYB#Dk D．zaYZ#Dm
9．創建一個容量為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
10．已知一個棧的入棧序列是a，c，e，h，r，t，e，其出棧序列可能的是（　　）
A．c，h，c，a，t，e，r B．h，e，c，t，a，r，e
C．t，e，a，c，h，e，r D．r，e，t，e，a，c，h
11．一個棧的入棧序列為“6、9、5、7、8、3”，其出棧序列不可能是（　　）
A．3、8、7、5、9、6 B．7、5、9、8、6、3
C．6、5、7、9、3、8 D．5、9、6、3、7、8
12．一個棧的入棧序列為1，2，3，4，5，其出棧序列為sl，s2，s3，s4，s5。若s2是3，則s1不可能是（　　）
A．1 B．2 C．4 D．5
13．在某餐廳點餐系統中，利用隊列來儲存當前正在排隊顧客的編號，head指向隊首元素，tail指向隊尾元素的下一個位置，若tail＝head+3，則現在排隊的顧客數量為（　　）
A．2 B．3 C．4 D．5
14．依次在初始為空的隊列中插入元素 a，b，c，d 以后，緊接著做了兩次刪除操作，此時的隊首元素是（　　）
A．a B．b C．c D．d
15．用棧的數據結構編寫進制轉換中的“除二取余法”的程序段如下：
方框處的代碼由以下四部分組成：
①n＝n//2
②top+＝1
③x＝n%2
④st[top]＝x
下列選項中，代碼順序正確的是（　　）
A．③④②① B．③①②④ C．①②③④ D．①③④②
16．某隊列的數據結構如圖所示，head 和 tail 分別為隊列的頭、尾指針。現對該隊列進行以下操作：①隊首元素出隊輸出②隊首元素出隊再入隊，重復①②操作直到隊列為空。
若隊列數據元素為“LUCKY”，則輸出順序是（　　）
A．LYUKC B．LCYUK C．LCYKU D．LUCKY
17．若用1表示進棧操作，用0表示出棧操作，若元素的進棧順序是“q，w，e，r，t”，為了得到出棧序列“ewrtq”，則應進行的操作序列為（　　）
A．1101010100 B．1110010100 C．1110011000 D．1110010100
18．下列有關棧和隊列說法，正確的是（　　）
A．棧的特點是先進先出，隊列的特點是先進后出
B．棧只允在一端進行插入，在另一端進行刪除
C．隊列限定僅能在一端進行插入和刪除操作
D．棧和隊列均為操作受限的線性表
19．已知變量s＝“2029106“，則下列Python表達式計算結果中最大的是（　　）
A．len（s） B．int（s[4]）
C．int（s）%100 D．int（s）//10**6
20．有一入棧序列為“ABCD”，以下以“C”開頭的出棧序列中不正確的是（　　）
A．CABD B．CBAD C．CBDA D．CDBA
21．以下有關棧和隊列的說法正確的是（　　）
A．棧和隊列都是先進后出
B．棧和隊列都是先進先出
C．隊列元素前面只有一個，后面有多個
D．棧和隊列只允許在端點插入和刪除數據
22．一個序列的入棧順序為 a，b，c，d，e，則該序列的出棧順序不可能為（　　）
A．b，a，d，c，e B．d，c，b，a，e C．d，c，e，a，b D．c，b，a，e，d
23．一個序列的入棧順序為1，2，3，4，5，6，若4第一個出棧，則下列出棧序列中不可能的是（　　）
A．4，2，3，1，5，6 B．4，6，5，3，2，1
C．4，3，5，2，6，1 D．4，5，3，6，2，1
24．check函數的功能是檢查字符串s是否符合相應要求。如果符合返回True，否則返回False。要求。包括大寫字母、小寫字母、數字以及其它字符。請找出下面代碼的兩處錯誤（　　）
A．①② B．②③ C．③④ D．①④
25．一個棧的初始狀態為空，若它的輸入序列為a、b、c、d，則它的輸出序列為（　　）
A．a、b、c、d B．d、c、b、a C．b、a、c、d D．d、b、a、c
26．設計一個判別表達式中括號是否配對的算法，采用（　　）數據結構最佳。
A．順序表 B．鏈表 C．隊列 D．棧
27．五節車廂以編號1，2，3，4，5順序進入鐵路調度站（棧），可以得到（　　）的編組。
A．3，4，5，1，2 B．2，4，1，3，5 C．3，5，4，2，1 D．1，3，5，2，4
二．簡答題（共3小題）
28．字符串分段。輸入一串僅由小寫字母組成的字符串s，將這個字符串劃分為盡可能多的小片段，要求同一個字母只出現在其中的一個片段中，并按照分段順序逐行輸出分段結果。程序運行界面如圖所示。
（1）實現上述功能的Python程序如下，請在橫線處填入合適的代碼。
s＝input（“請輸入一串僅包含小寫字母的字符串：”）
c＝0
p＝[﹣1]*52#數組p用來記錄各個小寫字母出現的起始位置和結束位置
#a[0]記錄a出現的起始位置，a[1]記錄a出現的結束位置，依次類推
for i in range（0，len（s））：#記錄各字符第一次和最后一次出現的位置
a＝①　 　
if p[2*a]＝＝﹣1：
p[2*a]＝i
else：
p[2*a+1]＝i
for i in range（0，26）：
if p[2*i]＞p[2*i+1]：
p[2*i+1]＝p[2*i]#只出現一次的字符，起始位置就是結束位置
if p[2*i]!＝﹣1：
c+＝1
for i in range（o，c）：將字符位置按照出現的起始位置升序排序
for j in range（25，i，﹣1）：
if p[2*j]＞﹣1：
if p[2*（j﹣1]＞p[2*j]or②　 　：
p[2*（j﹣1）]，p[2*j]＝p[2*j]，p[2*（j﹣1）]
p[2*（j﹣1）+1]，p[2*j+1]＝p[2*j+1]，p[2*（j﹣1）+1]
t1，t2＝p[0]，p[1]#字符串分段
for i in range（1，c）：
if p[2*i]＜t2 and p[2*i+1]＞t2：
③　 　
elif p[2*i]＞t2：
print（s[t1：t2+1]）
tl，t2＝p[2*i]，p[2*i+1]
print（s[t1：t2+1]）
（2）運行程序后，若輸入的字符串s為“hshjhqueeqabaa”，輸出的結果一共有 　 　行，其中，第二行顯示結果為 　 　。
29．為四則運算式“6+（8﹣2）*2÷3”轉逆波蘭表達“682﹣2*3÷+”設計算法，編程實現。
分析：在數學運算表達式中，運算符總是置于與之相關的兩個運算對象之間，在計算結果時，要考慮括號、運算符號的優先性。為了程序實現的方便，波蘭邏輯學家J.Lukasiewicz提出了另一種表示法，將運算符置于其運算對象之后，沒有括號，不用考慮運算符號的優先性。這種表達式稱為后綴表達式，又叫逆波蘭表達式。
如表達式“682﹣2*3÷+”是四則運算式“6+（8﹣2）*2÷3”的逆波蘭表達式。為了處理方便，規定表達式中的數均為小于10的正整數，運算符為+、﹣、*、÷。
（1）抽象建模
設計兩個棧bds、fh，棧bds用來存放表達式，棧fh用來暫時存放運算符。從左往右掃描四則運算式，遇到數字時，入棧bds；遇到運算符號時，根據運算符號的優先級設計進棧與出棧。
四則運算式“6+（8﹣2）*2÷3”轉換規則的模擬過程如表所示：
結合表格的操作過程，用棧bds和棧fh記錄每個操作后的棧內情況（見圖），那么在操作2中棧fh里有內容為 　 　（請從棧底到棧頂順序書寫）。
（2）設計算法
基于問題的抽象與建模，解決該問題的主要算法描述如下：
從左往右遍歷四則運算式s（設中間變量為ch）：
1）當ch是數字，直接入棧bds；
2）當ch是運算符：
a.若ch為左括號時，直接入棧fh；
b.若ch為右括號時，則將棧fh元素彈出，壓入棧bds，直到遇到左括號（左括號只
彈出，不壓入棧bds）；
c.若ch為其它運算符時，如果運算符ch優先級大于棧fh中棧頂元素的優先級（或棧fh為空），直接入棧fh；否則，將棧fh元素依次彈出，并壓入棧bds，直到運算符ch優先級大于棧fh中棧頂元素的優先級（或棧fh為空）；
3）將棧bds中元素依次出棧，即為該四則運算s的后綴表達式。
（3）編寫程序
實現上述功能的Python代碼如下，請在橫線處填入合適代碼。
30．【加試題】要求將某一字符串中指定的字符改寫成小寫或大寫（如果原先是大寫就改成小寫，反之改成大寫），并將處理后的字符重新輸出．
程序界面如下圖所示，在Text1中輸入原始字符串，在Text2中輸入需要改變的字符，單擊“改變”按鈕后，在Text3中輸出處理后的結果．
程序代碼如下：
Private Sub Command1_Click （　　）
Dim s As String，result As String，k As String
Dim zs As String，n As Integer
result＝“”
s＝Text1．Text
k＝Text2．Text
For n＝1To Len（s）
　 　
If zs＝k Then
If Asc（zs）＞＝65And Asc（zs）＜＝90Then
zs＝Chr（Asc（zs）+32）
Else lf Asc（zs）＞＝97And Asc（zs）＜＝122Then
zs＝Chr（Asc（zs）﹣32）
End If
End If
　 　
Next n
　 　
End Sub
在程序①、②、③橫線處填入適當的語句或表達式，把程序補充完整．
（1）程序中①橫線處應填入 　 　．
（2）程序中②橫線處應填入 　 　．
（3）程序中③橫線處應填入 　 　．
參考答案與試題解析
一．選擇題（共27小題）
1．【解答】閱讀程序可知，i的取值范圍是[1，3]，k的取值范圍為[1，3]，當k與i奇偶性相同時實行s＝s+c否則執行s＝c+s，選項A，當k依次取1，2，3可得，選項B，當k依次取2，2，3可得，選項D，當k依次取1，3，1可得。
故選：C。
2．【解答】程序中變量t的值只能是1或者2，因此每次是位置i與i+1或i與i+2的字符進行判斷。
故選：B。
3．【解答】根據ASCII碼值表可知，大小寫字母之間的差值為32，閱讀程序可知，根據依次輸入的數字進行加2，然后除以6取余數轉化在轉化為小寫字母，所以依次輸入3、1、4、5、2、6，輸出ch的值是f、d、a、b、e、c，所以選項B符合題意。
故選：B。
4．【解答】閱讀程序可知用變量i歷遍字符串，如果滿足字符串中的元素是遞增的，那么變量cnt增自動加1，將變量cnt的值賦值給m，否則不滿足遞增時，cnt＝1，最后輸出的m是字符串中元素遞增的長度。
故選：D。
5．【解答】如果輸入為onion，len（s）＝5，i的取值范圍為[0，2]，當I＝0時不滿足s[i]!＝s[len（s）﹣i﹣1]，f＝Flase，輸出為Flase，同理分析選項B和C均不符合題意。
故選：D。
6．【解答】選項A，進一個出一個可是實現1，2，3，4，5的出棧順序；
選項B，先進棧1，2，3，4，然后出4，再進5，然后依次出5，3，2，1，可以實現；
選項C，先進1，2，3，4，然后出4，3，然后再進5，最后依次出棧5，2，1，所以該項錯誤；
選項D，先進棧1，2，3然后依次出棧為3，2，1，然后進棧4，5此時再依次出棧5，4，故該順序可以實現。
故選：C。
7．【解答】一個棧的輸入序列為“12345“，輸出的第一個元素為“4“，那么此時可以繼續進棧5，然后執行出棧，順序為5，3，2，1；還可以出棧3，然后再進棧5，此時出棧順序為5，2，1；還可以出棧3，2，在進棧5，此時出棧順序為5，1；依次類推，無論如何1的出棧順序要么為4，要么為5，不可能是3.
故選：A。
8．【解答】通過閱讀程序可知，當提取到的字母為小寫字母時，那么得到的x則向后移動兩位得到對應的小寫字母，如果提取到的為大寫字母時，flag為交替變化的，當為True時，則向后移動24位得到的大寫字母，同時flag的取值發生變化，當提取到其他字符時，直接累加到字符串k上即可，由此得到的結果為zaYB#Dk。
故選：C。
9．【解答】由于容量為3的隊列，所以最初棧里的元素為2，3，5，當1進入棧時，若當前隊列已滿，將隊首元素出隊列，變為3，5，1，當入棧為3和5時，由于棧中 有該元素，跳過。當入棧為2時，當前隊列已滿，將隊首元素出隊列，變為5，1，2.故選：D。
10．【解答】根據棧的特點“先進后出”的原則，可知入棧序列是a，c，e，h，r，t，e，其出棧序列可能的是c，h，c，a，t，e，r。
故選：A。
11．【解答】根據先進后出的原則，可知入棧序列為“6、9、5、7、8、3”，7、8、3的出棧順序有783，387，783但不可能出現378的順序。
故選：D。
12．【解答】根據“先進后出”的原則，如果s2是3的話，那么相鄰的s1不可能是5，因為中間有間隔，所以出棧的時候也必須間隔一個。故選：D。
13．【解答】有題意可知tail＝head+3，指向隊尾元素的下一個位置所以 實際的顧客數為head+3﹣1，故為三個人。
故選：B。
14．【解答】隊列數據結構的特點是先進先出。進入的順序是abcd，刪除就是出數據，刪除兩次分別出數據a和b。剩下cd，并且開頭是c。故選C。
15．【解答】根據題意“除二取余法”可知先要執行取余，然后才能整除2。top默認值是﹣1，st[﹣1]表示列表最后一個元素。下一次循環top為0，就成列表第一個元素。余數就不連貫存儲在列表了。因此先top+＝1，然后st[top]＝x。按以上規則選B。故選B。
16．【解答】根據題意先執行①輸出L。接著執行②，U為隊首出隊加入隊尾。字符串為CKYU。再次執行①輸出C。接著執行②，K為隊首出隊加入隊尾。字符串為YUK。第三次執行①輸出Y。接著執行②，U為隊首出隊加入隊尾。字符串為KU。
第四次執行①輸出K。接著執行②，U為隊首出隊加入隊尾。字符串為U。
第五次執行①輸出U。
因此輸出字符串為LCYKU。故選C。
17．【解答】若元素的進棧順序是“q，w，e，r，t”，為了得到出棧序列“ewrtq”則順序應該為q進，w進，e進，e出，w出，r進r出，t進t出，最后q出，故表示為1110010100。故選：B。
18．【解答】棧的特點是先進先出，隊列的特點是先進先出；棧和隊列是操作位置受限的線性表，即對插入和刪除的位置加以限制。棧是僅允許在表的一端進行插入和刪除的線性表，因而是后進先出表。隊列是只允許在表的一端進行插入，另一端進行刪除操作的線性表，因而是后進先出表。故選：D。
19．【解答】已知變量s＝“2029106“則len（s）＝7，int（s[4]）＝1，int（s）%100＝6，int（s）//10**6＝2。故選：A。
20．【解答】以“C”開頭的出棧可以 為CBAD，CDBA，CBDA。故選：A。
21．【解答】棧和隊列都是先進后出，隊頭只允許刪除元素，隊尾只允許插入元素，而棧只允許在棧頂插入和刪除數據。故選：A。
22．【解答】根據進出棧的規則，可知進棧兩個字母以上的，出棧時，后進的字母一定先出，根據這一原則，選項C中，不可能先出a再出b。故選：C。
23．【解答】一個序列的入棧順序為1，2，3，4，5，6，若4第一個出棧，可以出3，可以進5出5，可以進56出65，由于進棧是1234，所以出棧必須是4321中間可以夾進出56，但無法先出2再出3.故選：A。
24．【解答】flag是列表，取列表中的數據用下標索引的方式。②處應該是c＝c+flag[j]。python判斷是否相等用＝＝賦值用＝。③處應該是if c＝＝4：故選B。
25．【解答】根據棧的規律先入后出，后入先出，輸入序列為a、b、c、d，則它的輸出序列為d、c、b、a故選：B。
26．【解答】設計一個判別表達式中左、右括號是否配對出現的算法，采用棧數據結構最佳。原因：棧是一種具有記憶能力的線性表，存取規則是先進后出。故選：D。
27．【解答】棧按后進先出 123入棧，3出棧，45入棧，5出棧，4出棧，2出棧，1出棧。故選：C。
二．簡答題（共3小題）
28．【解答】（1）在ASC表中，小寫字母a的值為97，ord（　　） 函數以一個字符（長度為1的字符串）作為參數，返回對應的 ASCII 數值，所以①處填寫為ord（s[i]）﹣97；p[2*（j﹣1]＞p[2*j]的同等條件為p[2*（j﹣1）]＝﹣1，在字符串分段中，如果p[2*i]＜t2 and p[2*i+1]＞t2條件乘以，則執行t2＝p[2*i+1]，在后面的輸出語句中可以找到；
（2）運行程序后，若輸入的字符串s為“hshjhqueeqabaa”，輸出的結果一共有3行，第二行顯示為queeq。
故答案為：（1）①ord（s[i]）﹣97 ②p[2*（j﹣1）]＝﹣1 ③t2＝p[2*i+1]
（2）3 queeq
29．【解答】①由表1中的操作2可知，棧fh里有內容為+（﹣。 ②若ch為右括號時，則將棧fh元素彈出，壓入棧bds，直到遇到左括號（左括號只彈出，不壓入棧bds），即退出循環，故此處填break。 ③如果topfh不等于﹣l或者fh[topfh]不等于“（“，說明fh棧中有其他運算符，則此處需要判斷ch的優先級與fh[topfh]的優先級大小，由代碼“fh[opfh]﹣ch”可知此處填yxij[ch]＞yxj[h[opf]。④此處循環結束后，已經將fh棧中比ch優先級高的運算符移到了bds棧中，此處將ch放到fh棧中，故此處填fh[topfh]﹣＝ch。
30．【解答】（1）根據題意，此處要求將從文本框輸入的字符串s一個一個地取出，所以需要使用Mid 函數結合for語句中的循環變量n，每次取一個字符，然后將結果賦值給變量zs，因此答案是zs＝Mid（s，n，1）．
（2）將s中的值進行逐個比較和處理后，還必須按照順序再組合回去，結果放在變量result中．所以此處填result＝result&zs（注意不能寫成result＝zs&result）．
（3）本題的要求是在Text3中輸出處理后的結果result，需要將result的值賦給Text3的Text，因而此處填寫Text3．Text＝result．
故答案為：（1）zs＝Mid（s，n，1）；（2）result＝result+zs或result＝result&zs；（3）Text3．Text＝result

展開更多......

收起↑