資源簡介

2023-2024學年高二上學期浙教版(2019)選修一3.3棧
一、選擇題
1．有1個棧初始為空，其元素入棧順序依次為a，b，c，d，e，f，g，經若干次入棧和出棧操作后，棧底至棧頂元素分別為b，d，f，則第3個出棧元素為（ ）
A．g B．c C．e D．a
2．有如下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']
3．隊列Q和棧S的初始值均為空，數字入棧先后順序為1、2、3、4、5。P表示入棧，T表示元素出棧以后入隊。在進行一系列P、T操作后，隊列中從隊首到隊尾的元素依次為2、1、4、5，則對應的P、T操作是（ ）
A．PPTTPPTPT B．PTPTPPPTT C．PPTTPPPTT D．PPTTPTPPT
4．棧s的最大長度為3，初始為空，經過一系列的入棧、出棧操作，若元素入棧的順序是a，b，c，d，e，則可能的出棧序列為（ ）
A．a，e，d，c，b B．c，a，b，d，e
C．a，d，c，e，b D．e，d，c，b，a
5．用一帶蓋的玻璃筒來放取乒乓球，放、取球只能在帶蓋的一端進行（另一端為封閉狀態），且筒的直徑只允許一個乒乓球進出。若放入球的編號序列為1、2、3、4，則取出球的編號序列不可能的是（ ）
A．1、2、3、4 B．2、3、4、1 C．4、2、3、1 D．3、2、1、4
6．設初始輸入序列為1，2，3，4，5，利用一個棧產生輸出序列，下列輸出序列不可能通過棧產生的是（ ）
A．1,2,3,4,5 B．5,3,4,1,2 C．4,3,2,1,5 D．3,4,5,2,1
7．已知字符″a″的ASCⅡ碼值為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’]
8．棧S1從棧底到棧頂的元素順序由1，2，3改為3，2，1，可借助初始均為空、長度均為3的棧S2、棧S3出入棧操作來實現，則需要出棧操作的總次數至少是（ ）
A．6 B．7 C．8 D．9
9．有如下程序段：
import random
a=[1.2.3.4.5]
stack=[a[0]]
i=1
res=[]
while i if random.randint（0.1）==0 or len（stack）==0：
stack.append（a[i]）
else：
res.append（stack.pop（））
i-=1
i+=1
while len（stack）>0：
res.append（stack.pop（））
print（res）
程序運行后，輸出的結果不可能是（ ）
A．[1.2.3.4.5] B．[2.1.4.3.5] C．[1.4.2.3.5] D．[1.5.4.3.2]
10．由元素1，2，3，4，5，6，7，8依次入棧、出棧，要求每次出棧之前至少有兩次連續入棧操作，出棧時可以出棧一個元素，也可以出棧多個元素直至?？眨瑒t數據的出棧序列可能是（ ）
A．3，4，2，5，7，6，1，8 B．2，4，3，1，8，7，6，5
C．5，7，6，4，8，3，2，1 D．4，3，5，2，1，6，8，7
11．棧s的最大長度為3，初始為空，經過一系列入棧、出棧操作，若元素出棧的順序是e，c，b，a，d，則可能的入棧序列為（ ）
A．a，b，c，d，e B．a，e，c，b，d C．e，b，a，c，d D．d，e，a，b，c
12．一個序列的入棧順序為9,8,7,6,5,4。若7第一個出棧，則下列出棧序列中不可能的是（ ）
A．7,8,9,6,5,4 B．7,8,9,5,6,4
C．7,9,8,4,5,6 D．7,8,9,6,4,5
13．有如下Python程序段：
st=[0]*10
a=[4，6，1，7，2，8，6]
top=0；st[top]=a[0]
for i in range(1,len(a))：
while top！=-1 and a[i] top-=1
top+=1
st[top]=a[i]
執行該程序段后，變量top的值為（ ）
A．-1 B．1 C．2 D．3
14．數據結構棧的特點是（ ）
A．先進先出 B．先進后出
C．可以在棧的任意位置取出元素 D．可以在棧的任意位置插入元素
15．現有棧S和隊列Q，初始狀態均為空，令數據元素b1，b2，b3，b4，b5，b6依次通過棧S，規定某元素出棧后立即進入隊列Q，若出隊的順序為b2，b5，b4，b6，b3，b1，則棧S的容量至少應該為（ ）
A．2 B．3 C．4 D．5
二、填空題
16．有一維數組1、2、3、4、5，依次按照某一線性存儲，請回答以下問題：
（1）如果該線性結構是隊列，寫出出隊序列。
（2）如果該線性結構是棧，輸出序列可能是4、3、5、1、2嗎？為什么？
（3）在一維數組A中有5個元素：8、12、20、25、33，采用二分查找25，請寫出每次查找的過程？
17．數據結構中的棧是一種特殊的列表，它只允許在 進行數據的添加和刪除操作。
18．棧是一種 數據結構，遵循 的原則。
19．在數據結構中，棧是一種 的數據結構，遵循后進先出（LIFO）原則。
三、操作題
20．電路板布線問題。電路板的水平直線上，從左向右分布著 n個針腳（1，2，3，…，n），用于連接導線。連線（p，q）表示針腳p和q之間通過一根導線連接，導線只允許從水平直線的下方相連，對于給定的一組連線（p1，q1），（p2，q2），…，（pm，qm）（確保各pi與qi均互不相同，且pi編寫程序，對于給定的n個針腳和m條連線，判定這組連線是否可布線。
請回答下列問題：
（1）若有8個針腳，并有一組連線（2，5），（1，6），（3，4），（7，8），則該組連線 （單選，填字母：A．可以/B．不可以）布線。
（2）實現上述功能的部分Python 程序如下，請在劃線處填入合適的代碼。
#讀取針腳數量與這組連線數量，分別存入n、m中，代碼略。
#將連線情況存入a，a=[[p1，q1]，[p2，q2]…]，代碼略。
for i in range（1，m）：#按連線左端點升序排序
for j in range（m-1，i-1，-1）：
if① ：
a[j]，a[j-1]=a[j-1]，a[j]
st=[0]*m；top=-1
②
for i in range（m）：
while top>=0 and st[top]<=a[i][0]：
top-=1
if top>=0 and③ ：
flag=False
top+=1
st[top]=a[i][1]
if flag：
print（“YES”）
else：
print（“NO”）
21．小陳同學高一結束后需要換寢室，他將全部物品打包成6個箱子并編號疊放在一起（如圖1所示）。為了搬運物品方便，他借了一輛手推車，該手推車一次最多能疊放3個箱子（如圖2所示）。箱子從上往下依次疊放在小推車上（假定每次只放一個箱子），小推車每次可以疊放1、2或3個箱子，小推車上的箱子也是從上往下依次拿取（假定每次只取一個箱子），搬運后的箱子仍舊疊放在一起。
（1）在搬運中，與手推車上箱子疊放和拿取的過程相似的數據結構是 。
（2）若搬運完畢后箱子的疊放順序是2、1、3、4、6、5（從下往上），則每趟手推車至多需要搬運的箱子數是 個。
圖1 圖2
四、簡答題
22．請簡述什么是堆棧（Stack）數據結構，并說明其特點。
23．解釋什么是棧數據結構，并說明其后進先出（LIFO）的特性。
參考答案：
1．C
2．B
3．A
4．C
5．C
6．B
7．A
8．B
9．C
10．B
11．B
12．C
13．C
14．B
15．C
16． 1、2、3、4、5
不可能，因為：4是第一出棧字符，說明1,2已別壓入棧內；并且壓入棧的次序為12345;由以上得出：12出棧的順序只能是2、1，而不是1、2。所以，出棧序列4,3,5,1,2是不可能的 第一次查找，找到的元素為20，此時20小于目標數，所以在列表的后半部分查找，第二次查找到的元素為25，此時找到，所以共需要兩次找到
17．頂端（或頂部）
18． 后進先出（LIFO） 后進先出
19．線性
20． A a[j][0]21． 棧 2
22．堆棧是一種后進先出（LIFO）的數據結構，其特點是只能在一端（棧頂）進行數據的添加（push）和刪除（pop）操作。
23．棧是一種遵循后進先出（LIFO）原則的數據結構，最后添加的元素將是第一個被移除的。這意味著元素只能從棧頂添加或移除。

展開更多......

收起↑