資源簡介

棧
一 、選擇題(每小題列出的四個備選項中只有一個是符合題目要求
的，不選、多選、錯選均不得分)
1.下列關于棧的說法，不正確的是 ( )
A.出棧操作時，先將棧頂元素出棧，同時棧頂指針變量值減1
B.入棧或出棧操作時不需要移動其他元素
C.棧不空時，當前只能取出棧頂元素
D.棧為空時，棧頂指針變量值為0
2.用一個帶蓋的玻璃筒來放取乒乓球，放、取只能在帶蓋的一端進行
(另一端為封閉狀態),且筒的直徑只允許一個乒乓球進出。若放
入球的編號序列為1、2、3、4,則取出球的編號序列不可能是( )
A.1 、2 、3 、4
B.2 、3 、4 、1
C.4 、2 、3 、1
D.3 、2 、1 、4
3.有7個羽毛球分別用1～7進行編號，若將7個羽毛球按一定順序裝
入棧結構的球罐中。已知取出羽毛球的順序用編號表示為2,4,3,
1,6,5,7,則放入羽毛球的編號順序不可能是 ( )
A.7,5,6,1,3,4,2
B. 1,2,3,4,5,6,7
C.7,6,5,4,3,2,1
D.2,4,3,1,6,5,7
4.設棧S 和隊列Q 的初始狀態為空，元素el,e2,e3,e4,e5,e6依次通
過 棧S,一個元素出棧后隨即進入隊列Q, 若6個元素出隊的序列是
e2,e4,e3,e6,e5,el,則棧S 的容量至少是 ( )
A.6 B.4
C.3 D.2
5.已知序列8,25,14,87,51,90,6,19,20,將這些元素全部入棧后再全部出
棧，若要使出棧的順序滿足8在51的前面，90在87的后面，20在14的后
面，25在6的前面，19在90的后面，則這些元素的進棧順序可能是( )
A.20,6,8,51,90,25,14,19,87
B.51,6,19,20,14,8,87,90,25
C. 19,20,90,8,6,25,51,14,87
D.6,25,51,8,20,19,90,87,14
6. 元素x1、x2、x3、x4、x5入棧的順序為x1、x2、x3、x4、x5。如果第1個 出棧的是x3,則第2個出棧的不可能是 ( )
A.x1 B.x2
C.x4 D.x5
7. 當棧為空時，棧頂top=- 1 。 利用棧計算逆波蘭表達式“682-2* 3/+”的過程中，當即將計算“8-2”時，top的值是 ( )
A.0 B.1
C.2 D.3
8. 某Python程序如下：
import random as rd
st=[0]*10
st[0]=2
top=0
for iin range(5):
if top==- 1:
break
num=rd.randint(1,6)
if num>=st[top]:
top+=1
st[top]=num
elif num%2==0:
top-=1
for i in range(top+1):
print(st[i],end="")
程序運行后，輸出的結果可能是 ( )
A.2245566 B.255
C.2464 D.2342
9. 用Python列表自帶的函數和方法來模擬棧，代碼如下：
import random
a=[1,2,3,4,5]
stack=[a[0]]
i=1
res=[]
while iif 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,5,4,3,2]
D.[1,4,2,3,5]
10. 有如下創建棧及進行棧操作的Python 程序：
class Stack():
def def def inil (self): self.my stack=[] push(self,data): self.my stack.append(data) pop(self): return self.my stack.pop()
La=[]
stack=Stack()
stack.push("r1")
La.append(stack.pop()
stack.push("r2")
stack.push("r3")
La.append(stack.pop()
stack.push("r4")
La.append(stack.pop()
stack.push("r5")
print(La)
程序運行后，輸出的內容是
A.["r2","r5"]
B.["r5","r2"]
C.["r4","r3","r1"]
D.["r1","r3","r4"]
( )
( )
二、非選擇題
11. 利用棧的“先進后出”的特點可以實現數的進制轉換。某Python 程序如下，實現的是十進制數轉換為二進制數的功能。運行界
面如圖所示。請在劃線處填入合適的代碼。
請輸入一個整數：27
11011
s=[0]*100
top=- 1
n=int(input("請輸入一個整數：")
while n>0:
top+=1
①
n=n//2
while top>- 1:
print(s[top],end="")
②
12. 單調棧是保證棧中元素具有單調性的數據結構，如已知棧中元素 從棧底到棧頂依次為：2、4、4、8、9,保證了棧中具有單調不下降的 性質，如果此時有新元素4入棧，則為了保證棧的單調性，將會把
8、9出棧，令4入棧，棧中元素更新為2、4、4、4。小王利用Python 編寫的程序如下，對于已有的整數單調棧s,將數據new 入棧，同 時保證棧中元素的單調不下降性。請在劃線處填入合適的代碼。 s=[0]*100
n=int(input("請輸入已有單調遞增棧中的元素數量：")
i=0
while is[i]=int(input("請依次輸入棧中的元素：")
i+=1
top=n- 1
def push(x):
global top #定義全局變量top
while ① :
top-=1
top+=1
②
new=int(input("請輸入新入棧的元素：")
push(new)
for i in range(top+1):
print(s[i].end=”")
13. 字符串如"CBAABC" 稱為回文字符串，而字符串"ABC"則不是回 文字符串。可以利用棧來檢查字符串是否為回文字符串，實現上 述功能的Python程序如下，運行界面如圖所示。請在劃線處填入
合適的代碼
請輸入字符串：abcdcba 是回文字符串
st=[“”]]*100
top=- 1
1
s=input("請輸入字符串：")
k=len(s)//2
fori in range(k):
top+=1
st[top]=s[i]
if ② **
k=k+1
for i in range(k,len(s)):
ch=st[top]
top-=1
if 3 :
flag=False:break
if flag:
print("是回文字符串")
else:
print("不是回文字符串")
14. 有一個背包，它的最大承載質量為m 公斤(kg),現有n 件物品，并 已知這n 件物品的質量，編寫一個Python程序找出所有能將背包 裝滿的方案。程序運行后，首先輸入背包的最大承載質量m, 接 著輸入物品的數量n 及n 件物品的質量，輸出能裝滿背包的所有 方案。實現上述功能的Python程序如下，運行界面如圖所示。請
在劃線處填入合適的代碼。
輸入背包的最大承載質量：20 輸入物品數量：6 輸入物品質量(用逗號隔開):12,5.8,9.3.16 裝滿背包的方案有 [0,1,4] [0,2] [2,3,4]
def cal(t,w):
n=len(w)
stack=[
k=0
while stack or kwhile ①
if t>=int(w[k]):
stack.append(k)
②
k+=1
if t==0:
print(stack)
#若無方案，則將當前物品出棧，退回一步嘗試其他物品
k=stack.pop()
t+=int(w[k])
k+=1
m=int(input("輸入背包的最大承載質量：")
n=int(input("輸入物品數量：")
weight=input("輸入物品質量(用逗號隔開):")
wplist=weight.split(",")
print("裝滿背包的方案有：")
③
參考答案
1.D 2.C 3.C 4.C 5.D 6.A 7.D 8.B 9.D 10.D
① s[top]=n%2
② top-=1
① x=0
② s[top]=x
① flag=true
② len(s)%2==1
③ ch!=s[i]
① t>0 and k②t-=int(w[k]) 或 t=t-int(w[k])
③ cal(m,wplist)

展開更多......

收起↑