資源簡介

2023-2024學年高二上學期浙教版(2019)選修一3.2隊列
一、選擇題
1．有2個隊列a和b，隊首到隊尾的元素依次分別為“5，7，9”和“6，4，8”。約定：T操作是指隊列a中1個元素先出隊，若大于隊列b的隊首元素則再入b隊列，否則不入；Q操作是指隊列b中1個元素先出隊，若大于隊列b的隊尾元素則再入b隊列，否則不入。則經過TTQQQQT系列操作后，隊列b中的元素個數為（ ）
A．1 B．2 C．3 D．4
2．在數據結構中，隊列的特點是（ ）
A．先進先出 B．先進后出 C．后進先出 D．后進后出
3．若用一個規模為8的數組來實現循環隊列，且當前隊頭指針head和隊尾指針tail的值分別為5和7，當從隊列中刪除一個元素，再加入兩個元素后，head和tail的值分別為（ ）
A．5和1 B．6和1 C．5和9 D．6和9
4．在某餐廳點餐系統中， 利用隊列來儲存當前正在排隊顧客的編號，head 指向隊首元素，tail 指向隊尾元素的下一個位置， 若 tail=head+3，則現在排隊的顧客數量為（ ）
A．2 B．3 C．4 D．5
5．某已知隊列元素的的個數為5，則隊首指針head和隊尾指針（指向隊尾一個元素的后一個位置）tail的值不可能是（ ）
A．head=1, tail=6 B．head=6, tail=1 C．head=2, tail=3 D．head=3, tail=2
6．棧和隊列的共同特點是（ ）
A．都是線性表 B．都只允許在表的一端進行插入或刪除
C．操作受限的線性表 D．允許在兩端進行插入和刪除
7．某隊列使用head記錄隊首元素所在的位置，tail記錄隊尾元素的下一個位置，若head=4，tail=8，則該隊列中元素的個數是（ ）
A．3 B．4 C．5 D．8
8．有一個非循環隊列S如圖所示，其中指針head指向隊首元素的位置，指針tail指向隊尾元素的下一個位置。
關于該隊列說法正確的是（ ）
A．隊列中元素個數為tail-head+1 B．新元素入隊時，指針head向右移動
C．元素出隊時，指針tail向右移動 D．當tail==len（S）時，無法再入隊新元素
9．某隊列中存有12張撲克牌，如題圖所示，游戲規則如下：①取隊首撲克牌，然后加入到隊尾，②打出隊首撲克牌；重復①、②兩個操作，直到隊列為空。
若要根據上述規則用撲克牌打出“一條龍”游戲（注：總共13張牌，從隊列中出牌的次序為“A2345678910JQK” ）。請你設計游戲，將撲克牌“10”放到初始隊列中正確的位置（ ）
A．放置在撲克牌6的后面 B．放置在撲克牌5與撲克牌K之間
C．放置在撲克牌2與撲克牌8之間 D．以上說法均錯誤
10．某隊列經過“出隊”“入隊”操作后，隊首指針head=2，隊尾指針tail=6，則該隊列中剩余的元素個數是（ ）
A．2 B．4 C．5 D．6
11．隊列Q初始從隊首到隊尾分別是abc，棧S中有de，e為棧頂。約定：操作1是指一個元素出棧后入隊，操作2是指一個元素出隊后再入隊。經過21221系列操作后，隊列中隊首到隊尾的元素依次為素（ ）
A．aebcd B．edabc C．aedcb D．cbde
12．假設隊列空間足夠，隊列中的元素個數為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
13．有如下Python程序段：
st = [″h″,″a″,″p″,″*″,″p″,″Y″]
que = [0]*20; key = 2
head,tail = 0, 0
for i in range (len(st)):
if ″a″ <= st[i] <= ″z″:
que[tail] = chr((ord(st[i]) - ord(″a″) + key)%26 + ord(″a″))
tail += 1
else:
head += 1
while head != tail:
print (que[head],end =″ ″)
head += 1
程序運行后，輸出的結果是（ ）
A．r r B．p p C．c r r a D．c r r A
14．隊列屬于（ ）
A．線性結構 B．樹結構 C．圖結構 D．以上均不是
15．用列表模擬隊列對數據進行操作，python程序如下
a=[3,4,5,6,7]
head=0;tail=len(a)
a+=[0]*100
while head+2<=tail:
if a[head]%2==0
a[tail]=a[head]//2
head+=1;tail+=1
elif a[head]<=5:
head+=1
else:
a[head]-=5
print(a[head])
程序運行后輸出的結果是（ ）
A．0 B．1 C．2 D．3
二、填空題
16．隊列是一種有限制的 結構。特點是數據元素只能在 依次添加（稱為進隊），在另一端依次刪除（稱為 ）。
17．在數據結構中， 是一種特殊的線性表，只允許在表的兩端進行插入和刪除操作。
18．在計算機編程中， 是一種用于存儲和管理數據的集合，它允許數據項以有序的方式添加和刪除。
三、操作題
19．為鼓勵綠色出行，某市推出了優惠方案：乘一次地鐵后可以獲得一張優惠券，在有效期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）該程序主要應用的數據結構類型是 (選填：隊列 / 棧 / 鏈表 / 二叉樹)。
20．楊輝三角，是二項式系數在三角形中的一種幾何排列，其最左側一列數字和右邊的斜邊數字均為1，內部其他位置上的每個數字均為上一行同一列數字與上一行前一列數字之和，前8行的楊輝三角如第圖a所示。
圖a楊輝三角 圖b三角形數壘
（1）如果用數據結構中的隊列構建楊輝三角，編寫輸出前n行楊輝三角的python程序代碼如下，請在程序劃線處填入合適的代碼。
n=int(input("輸入行數:"))
que=[0]*1000
head=tail=0
que[tail]=1
print(que[tail]);tail=tail+1
for i in range(2,n+1):
print(que[tail],end="");tail=tail+1
for j in range(① ):
que[tail]=②
print(que[tail],end="");tail=tail+1
head=head+1
print(que[tail]);tail=tail+1
③
（2）三角形數壘（如圖b所示），是楊輝三角的變形，與楊輝三角不同的是最左側一列數字和右邊的斜邊數字均為1、2…n。若要使得程序能輸出三角形數壘，可通過將第（1）小題程序中的兩條加框語句que[tail]=1都修改為 實現。
（3）在上述程序中，給隊列que分配的最大空間為1000，存在空間浪費問題。為了提高空間利用效率，小北將隊列que改為了循環隊列，即將第2條語句que=[0]*1000修改為que=[0]*n，同時將程序中所有的head=head+1和tail=tail+1進行了修改，其中head=head+1應修改為 。
參考答案：
1．B
2．A
3．B
4．B
5．C
6．C
7．B
8．D
9．A
10．B
11．A
12．B
13．A
14．A
15．C
16． 線性數據 隊尾 出隊
17．隊列
18．隊列
19． q[tail]=a[i][2] head==tail 或 q[head]==-1 head+=1 a[j][2] < a[j - 1][2] 隊列
20． i-2 或 1，i-1 que[head]+que[head+1] head=head+1 que[tail]=i head=(head+1)%n

展開更多......

收起↑