資源簡介

第三章 字符串、隊列和棧 章節測試
一、選擇題
1．元素1，2，3，4，5，6依次入棧，若第1個出棧的元素是4，則不可能是第3個出棧的元素是（ ）
A．1 B．2 C．3 D．5
2．下列關于隊列和棧的說法，不正確的是（ ）
A．隊列是一種先進先出的線性表，可在隊尾進行插入操作
B．棧的特性是″先進后出，后進先出″
C．某棧的入棧的順序為″abc″，出棧順序只有3種
D．隊列和棧都是線性數據結構，都可以用數組來實現
3．有一空棧S，對待進棧的數據元素序列a，b，c，d，e，f依次進棧、進棧、出棧、進棧、進棧、出棧的操作，操作完成后，棧S的棧頂元素是（ ）
A．c B．d C．e D．f
4．在某餐廳點餐系統中， 利用隊列來儲存當前正在排隊顧客的編號，head 指向隊首元素，tail 指向隊尾元素的下一個位置， 若 tail=head+3，則現在排隊的顧客數量為（ ）
A．2 B．3 C．4 D．5
5．有1個隊列，隊首到隊尾的元素依次為8，3，2，9，5。約定：T操作是指隊列中1個元素出隊后再入隊，Q操作是指隊列中l個元素出隊。則經過TTTQTTQ系列操作后，隊列中隊首到隊尾的元素依次為（ ）
A．2，9，5 B．2，5，8 C．5，8，2 D．8，3，2
6．設棧S和隊列Q的初始狀態為空，元素w1、w2、w3、w4、w5依次通過棧S，一個元素出棧后即進入隊列Q，下列不可能是出隊序列的是（ ）
A．w5、w4、w3、w2、w1 B．w3、w2、w1、w4、w5
C．w4、w2、w1、w3、w5 D．w1、w2、w3、w4、w5
7．有1個隊列，隊首到隊尾的元素依次為1，2，3，4，5。約定：T操作是指隊列中1個元素出隊后再入隊，Q操作是指隊列中1個元素出隊。則經過TTQTTQTTQ系列操作后，隊列中隊首到隊尾的元素依次為：（　　）
A．4，5 B．5，4 C．2，4 D．4，2
8．有如下 Python 程序段：
s = input('請輸入一串小寫字母')
head = 0; tail = 0; top = -1
s1 = [""]*((len(s)+1)//2)
s2 = [""]*(len(s)//2)
for i in range(len(s)):
if i % 2 == 0:
s1[tail] = s[i]
tail += 1
else:
top += 1
s2[top] = s[i]
x = ""
while head < tail and top > -1:
x = s1[head] + x
head += 1
x = x + s2[top]
top -= 1
print(x)
執行該程序段，輸入字符串“abcdefg”，則輸出的結果是（ ）
A．acegbdf B．acegfdb C．gecafdb D．ecafdb
9．有如下程序段：
bt=["A","B","C","D",None,"E","F"]
result=[]
stack=[]
i=0
while stack or (i if i < len(bt) and bt[i] is not None:
stack.append(i)
i=2*i+1
else:
i=stack.pop()
result.append(bt[i])
i=2*i+2
print("-".join(result))
則程序運行后輸出的結果為（ ）
A．A-B-D-C-E-F B．D-B-E-F-C-A C．D-B-A-E-C-F D．A-B-C-D-E-F
10．用棧的數據結構編寫進制轉換中的“除二取余法”的程序段如下：
st=[-1]*100
top=-1
n=int(input("請輸入一個十進制數： "))
while n>0:
while top!=-1:
print(st[top],end="")
top-=1
方框處的代碼由以下四部分組成：
①n=n//2 ②top+=1 ③x=n%2 ④st[top]=x
下列選項中，代碼順序正確的是（ ）
A．③④②① B．③①②④ C．①②③④ D．①③④②
11．一個序列的入棧順序為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
12．有如下Python程序段：
w=[12，5，8，9，3，16]
n=len(w)；stack=[0]*n
top=-1；k=0；t=25
while top!=-l or kwhile t>0 and kif t>=w[k]：
top+=l；stack[top]=k
t-=w[k]
k+=l
if t==0：
print（stack[:top+1]）
k=stack[top]；top-=l
t+=w[k]：k+=l
執行該程序段后，輸出第一組列表是（ ）
A．[0，1，2] B．[1，2，3，4] C．[3，5] D．[12，5，8]
13．某Python程序如下：
from random import randint
a=[1,8,3,6,7,2,9,0,5,1,3]
s=[-1]*100;top=-1
i=0
x=randint（5,8）
while i while top!=-1 and a[i] < s[top]:
top-=1
top+=1;s[top]=a[i]
i+=1
while top!=-1:
print(s[top],end="")
top-=1
執行該程序段后，輸出的結果不可能是（ ）
A．0 B．21 C．631 D．921
14．在日常幻燈片的放映中，可以通過超級鏈接方式進行幻燈片之間的任意跳轉。和這種跳轉方式相似的數據結構是（　　）
A．數 B．鏈表 C．隊列 D．棧
15．一個棧的初始狀態為空，若它的輸入序列為a、b、c、d，則它的輸出序列為( )
A．a、b、c、d B．d、c、b、a
C．b、a、c、d D．d、b、a、c
二、填空題
16．有一維數組1、2、3、4、5，依次按照某一線性存儲，請回答以下問題：
（1）如果該線性結構是隊列，寫出出隊序列。
（2）如果該線性結構是棧，輸出序列可能是4、3、5、1、2嗎？為什么？
（3）在一維數組A中有5個元素：8、12、20、25、33，采用二分查找25，請寫出每次查找的過程？
三、操作題
17．暑假期間，小明擔任了天文館售票處的志愿者工作，工作內容是維持游客的買票秩序，在開始售票前后的一段時間內（7：50-8：00），他觀察到排隊買票的隊列發生了以下變化。（買票中不算排隊）
時間 狀態
7：50 售票窗口前沒有人排隊
7：55 售票窗口前有5個人（用P1，P2，P3，P4，P5表示）依次在排隊
8：00 開始售票，有3個人（P1，P2，P3）陸續買票離開，又來了4個人（P6，P7，P8，P9）依次排入隊中
根據上述觀察，思考并回答下面的問題。
（1）最先進入隊列的是 ，P3買完票離開后，排在隊首的人是 ，隊列里有 個人在排隊。
（2）為了便于游客參觀，天文館配置了伴游機器人，此機器人不僅可以當小導游陪伴游覽，還可以利用其自帶的搜索功能輕松查找館內餐廳、洗手間及各個展館位置，搜索功能主要依賴于 。
A．DNS B．GPS C．CSS D．iOS
（3）經過暑假志愿服務的經驗，小明想為天文館設計一款網上自助售票系統，請你幫助小明完成預約流程圖。（填字母）
① ；② ；③ ；④ 。
A．是B．選擇預約日期C．選擇預約時間段D．否
18．為鼓勵綠色出行，某市推出了優惠方案：乘一次地鐵后可以獲得一張優惠券，在有效期45分鐘內(含)可免費搭乘一次公交車。有效期指乘公交車與乘地鐵的開始時刻之差。搭乘公交車時，可以使用優惠券則一定會使用，如果有多張優惠券滿足條件，則優先消費獲得最早的優惠券。有人用Python編寫程序計算出行的費用。他的某次出行過程如圖a所示，程序運行結果如圖b所示。
請回答下列問題：
（1）請在劃線處填入合適的代碼。
def Ctime(t):
# 自定義函數Ctime功能為將時間轉為分鐘計存入變量s，代碼略。
return s
'''
讀取出行記錄，存儲在列表a中，a[i][0]、a[i][1]、a[i][2]依次存儲交通工具類型、票價、乘坐開始時刻。交通工具類型a[i][0]值為0表示地鐵，1表示公交車。代碼略。
'''
n = len(a)
for i in range(n):
a[i][2] = Ctime(a[i][2])
for i in range(n - 1):
for j in range(n - 1, i, -1):
a[j], a[j - 1]= a[j - 1], a[j]
# 輸出出行記錄，代碼略。
total = 0
head = tail = 0
q = [-1] * n
for i in range(n):
if a[i][0] == 0:
total += a[i][1]
tail += 1
else:
while head < tail and q[head] < a[i][2] - 45:
head += 1
if :
total += a[i][1]
else:
print(a[i][2],"時刻使用了優惠券")
print("總共花費為:", total)
（2）程序中加框處代碼有錯，請改正。
（3）該程序主要應用的數據結構類型是 (選填：隊列 / 棧 / 鏈表 / 二叉樹)。
19．小明對入棧、出棧規則研究發現， 若有 n 個數字 1，2，3，……，n 按由小到大的順 序入棧，則出棧序列必須遵循下述原則： 當數字 x 出棧后，則在x后出棧的小于x 的 所有數字必定以降序排列，比x大的數字可以夾雜在該降序序列中。現編寫 Python 程 序，按上述原則驗證一個隨機產生的出棧序列是否可能， 程序運行界面如圖所示。
(1) 根據題意，若有 7 個數字入棧， 則出棧序列“3→2→5→4→7→1→6”是 (單選，填字母： A．可能 / B．不可能)
(2) 實現上述功能的Python程序代碼如下，程序中加框處代碼有錯，請改正 。
(3)請在劃線①②處填入合適代碼 、 。
import random
n=int(input('請輸入入棧元素的個數：'))
data=[i+1 for i in range(n)]
random.shuffle(data) #將序列的所有元素隨機排序
s=” ”
for i in range(n):
print('隨機產生的出棧序列為： '+s[1:])
flag=True;i=0
while i①
for j in range(i+1,n):
if data[j]if data[j]x=data[j]
else:
②#去除最后多余的'→'
break
i+=1
if flag:
print('該出棧序列是可能的！')
else:
print('該出棧序列是不可能的！ ')
參考答案：
1．A
2．C
3．A
4．B
5．B
6．C
7．C
8．D
9．C
10．B
11．C
12．A
13．C
14．B
15．B
16．1、2、3、4、5
不可能，因為：4是第一出棧字符，說明1,2已別壓入棧內；并且壓入棧的次序為12345;由以上得出：12出棧的順序只能是2、1，而不是1、2。所以，出棧序列4,3,5,1,2是不可能的 第一次查找，找到的元素為20，此時20小于目標數，所以在列表的后半部分查找，第二次查找到的元素為25，此時找到，所以共需要兩次找到
17．P1 P4 5 B B C A D
18．q[tail]=a[i][2] head==tail 或 q[head]==-1 head+=1 a[j][2] < a[j - 1][2] 隊列
19．B s+=’ →’+str(data[i]) x=data[i] flag=False

展開更多......

收起↑