資源簡介

專題13　隊　列
知識點一　隊列的性質
1.在該系統中，可以利用隊列來儲存當前正在排隊顧客的編號，head指向隊首元素，tail指向隊尾元素的下一個位置，若tail＝head＋3，則現在排隊的顧客數量為(　　)
A.2 B.3
C.4 D.5
2.約定：T操作是指在隊列中1個元素出隊后再入隊，E操作是指將1個元素入隊，P操作是指隊列中1個元素出隊，隊首指針head和隊尾指針tail初始值均為0。則經過EETPETEP系列操作后，隊首指針head和隊尾指針tail的值分別為(　　)
A.3　4 B.3　5
C.4　5 D.4　6
3.有1個隊列，隊首到隊尾的元素依次為8，10，12，9。若隊首元素是偶數則先出隊，再將偶數整除2后重新入隊，若隊首元素是奇數，直接出隊。入隊或出隊各算一次操作，經過6次操作后，隊列中隊首到隊尾的元素依次為(　　)
A.2，3 B.6，2，3
C.9，4，5 D.9，4，5，6
4.已知隊列元素的個數為5，則隊首指針head和隊尾指針tail的值不可能是(　　)
A.head＝1，tail＝6 B.head＝2，tail＝6
C.head＝5，tail＝0 D.head＝3，tail＝2
5.假設隊列的空間足夠，隊首指針head和隊尾指針tail經過“出隊、入隊、出隊、出隊、入隊、入隊、出隊”這一系列操作后，head＝7，tail＝9。則操作前的head和tail的值分別為(　　)
A.11　12 B.2　5
C.3　6 D.3　5
6.某隊列的數據結構如圖所示，head和tail分別是隊列的頭指針和尾指針。
現對該隊列進行下列操作：①隊首元素出隊后再入隊；②隊首元素出隊并輸出，重復①②操作直到隊列為空。若隊列的數據元素為“Python”，則輸出的順序是(　　)
A.Python B.Ptoynh
C.yhntPo D.yhntoP
7.假設高鐵站的售票窗口平均每分鐘過來一個人購票，每人的購票時間平均約為2分鐘，某車站在中午時段開了一個售票窗口，12：01：00的時候有1個人剛開始購票，3個人在等待，那么12：11：00時隊伍中等待購票的人數為(　　)
A.7 B.8
C.9 D.10
知識點二　隊列的算法實現
1.有如下Python程序段：
Q＝[0]*10
cnt，head，tail＝0，0，0
S＝input()
for i in range(0，9，2)：
t＝S[i]
n＝int(S[i＋1])
if t＝＝'A'：
for j in range(n)：
　　　　Q[tail]＝cnt
　　 　tail＋＝1
　　　 　cnt＋＝1
elif t＝＝″D″：
while head ！＝tail and n>0：
　　　 　head＋＝1
　　 　　n －＝1
print(Q[head：tail])
若輸入S的值為″A2D1A1D3A2″，則程序的輸出結果是(　　)
A.[3，4，5] B.[3，4]
C.[4，5] D.[4]
2.有如下Python程序段：
que＝['A'，'B'，'C'，'D'，'E']
for i in range(10)：
que.append(－1)
n＝5；head＝0；tail＝5
for i in range(n)：
print(que[head]，end＝' ')
head＋＝1
for j in range(i)：
que[tail]＝que[head]
tail＋＝1
head＋＝1
執行該程序段后，顯示的結果是(　　)
A.ACBED B.ABDCE
C.ABDEC D.ACBDE
3.執行如下程序段后，輸出的結果是(　　)
q＝[6，8，9，7，4，5，2，3]
pre＝10
head，tail＝0，len(q)
while head！＝tail：
if pre>q[head]：
pre＝q[head]
print(q[head]，end＝' ')
head＋＝1
A.6 8 9 B.6 4 2
C.6 5 3 D.6
4.使用Python自帶的隊列模塊queue可以更便捷地實現隊列的操作，代碼如下：
import queue
q＝queue.Queue(5)
q.put(″A″)　#字符A入隊
q.put(″B″)
q.put(″C″)
已知get函數可以按照隊列特性出隊，若要使字符“C”從隊列q中出隊正確的方法是(　　)
A.直接使用語句q.get(″C″)
B.直接使用語句q.get()
C.使用兩次語句q.get()
D.使用三次語句q.get()
5.有如下Python程序段：
q＝[chr(i) for i in range(65，70)]
ans＝″″
head，tail＝0，len(q)
while headans＝ans＋q[head]
head＋＝1
if headq＋＝q[head]
tail＋＝1
head＋＝1
print(ans)
執行該程序段后，輸出的ans值為(　　)
A.ABCDE B.ACEDB
C.ADCEB D.EDCAB
6.有如下Python程序段：
import random
q＝[1]*12；s＝0
head＝0；tail＝1
k＝random.randint(1，5)
while k>0：
q[tail]＝q[head]*2
tail＋＝1
q[tail]＝q[head]*2＋1
tail＋＝1；head＋＝1；k－＝1
while heads＋＝q[head]
head＋＝1
執行該程序段后，s的值不可能的是(　　)
A.7 B.22
C.35 D.51
7.有如下Python程序：
s＝input()
sq＝[″″]*100
head＝tail＝0
flag，res＝True，″″
for i in range(len(s))：
if s[i]＝＝″－″：
while head ！＝tail：
　　　 　res＋＝sq[head]
　　　 　head＝head＋1
　　 　　if flag：
　　　　 　　sq[tail]＝sq[head]
　　　　　 　tail，head＝tail＋1，head＋1
　　　　 flag＝not flag
else：
sq[tail]＝s[i]
tail＝tail＋1
如輸入的s為″Python－2023－″，執行該程序，則變量res的值為(　　)
A.″Pthnyo2230″ B.″Ptoynh2203″
C.″tPyhno2302″ D.″yPntho2023″
8.有如下Python程序段：
lst＝[5，9，2，6，4，7，3，0]
que＝[0]*len(lst)
head＝tail＝0
i＝0
while iif lst[i] %2＝＝0：
que[tail]＝lst.pop(i)
#lst.pop(i)刪除列表1st中索引為i的元素，返回刪除的元素
tail＋＝1
else：
i＋＝1
while head ！＝tail：
lst.append(que[head])
head＋＝1
執行該程序段后，lst 的值為(　　)
A.[5，9，7，3，2，6，4，0] B.[5，9，7，3，0，4，6，2]
C.[2，6，4，0，5，9，7，3] D.[3，7，9，5，0，4，6，2]
9.有如下Python程序段：
import random
q＝[0]*5
head＝tail＝0
for i in range(5)：
if random.randint(0，1)＝＝0：
q[tail]＝random.randint(1，9)
tail＋＝1
elif head ！＝tail and q[tail－1]q[tail]＝q[head]
head＋＝1
tail＋＝1
執行該程序段后，q的值不可能是(　　)
A.[0，0，0，0，0] B.[5，4，3，2，1]
C.[5，8，3，0，0] D.[0，5，6，0，0]
10.有如下Python程序段：
from random import randint
s＝″14257″；q＝[″″]*10；ans＝″″
head＝tail＝0
for i in s：
q[tail]＝i
tail＋＝1
for i in range(len(s))：
t＝randint(0，1)
if t＝＝0：
q[tail]＝q[head]
tail＋＝1
head＋＝1
while tail>head：
ans＋＝q[head]
head＋＝1
print(ans)
運行該程序段，則輸出的值不可能的是(　　)
A.5 B.41
C.457 D.14257
11.某Python程序如下：
que＝[0]*7
a＝[2，3，5，1，3，5，2]
head＝0；tail＝0
for i in a：
if tail－head＝＝3：
head＋＝1
elif i not in que[head：tail]：
que[tail]＝i
tail＋＝1
print(que[head：tail])
執行上述程序后，輸出的結果為(　　)
A.[2，3，5，1] B.[3，5，2]
C.[2，3，5] D.[5，1，2]
12.n位志愿者分別來自5所學校，用1－5對每所學校志愿者進行編號，按報名參加志愿服務的先后順序依次存入數組s，對應的姓名分別存入數組xm中。組委會從中選擇若干名志愿者，要求每個報名的學校至少包含1名志愿者，且滿足條件的志愿者人數最少，輸出區間內的志愿者名單。部分代碼如下：
#讀取全體志愿者編號到數組s中，并輸出，代碼略
head＝0；tail＝0
minn＝len(s)；ta＝0
while tailtail＋＝1
if tail！＝1 and s[tail－1]＝＝s[head]：　#①
head＋＝1
②________：
head＋＝1
p＝head
③________
while ptotn[p]＝＋1　#④
p＋＝1
if sum(totn)＝＝5：　# sum(totn)統計totn列表中所有元素之和
if tail－head　　 　　minn＝tail－head
　　 　　ta＝head
下列關于程序代碼的完善和修改，說法正確的是(　　)
A.①處語句修改為if s[tail－1]＝＝s[head]：，功能不變
B.②處語句應為if s[head]＝＝s[head＋1]
C.③處語句應為totn＝[0]*5
D.④處語句修改為totn[s[p]]＝1
13.某城市規模較小，人口流動量不大，通常兩個完全不認識的陌生人通過2－3個親戚或朋友的牽線搭橋就可以建立聯系。王老師建立了一種人際關系矩陣來模擬這種現象，如圖所示有甲、乙、丙、丁、戊、己、庚、辛8人，分別用1－8進行編號，相互之間認識，在矩陣中用1表示；相互之間不認識，在矩陣中用0表示；對于自身，用0表示，即矩陣左上角到右下角的對角線全為0。當前甲和乙不認識，只需通過2人(辛和丁)牽線即可建立聯系。程序運行的效果如圖所示：
(1)實現上述功能的Python程序如下，請在劃線處填入合適的代碼。
(2)程序中加框處代碼有錯，請改正。
#列表a用于存儲聯系是否是朋友的關系
n＝8　#人員數量
p1＝int(input(″輸入第1個聯系人編號：″))－1
p2＝int(input(″輸入第2個聯系人編號：″))－1
b＝[0]*n；b[0]＝p1　#存儲訪問過的聯系人列表
ren＝[0]*n　#從p1開始訪問過的聯系人人數
head＝0；tail＝1
find＝[False]*n
find[p1]＝True
lxr＝[0]*n　#上一個訪問的聯系人
while not find[p2]：
①________
for i in range(n)：
if a[cur][i]＝＝1 and find[i]＝＝False：
　　　 　b[tail]＝i
　　　　　　tail＋＝1
　　　　 find[i]＝True
　　　 　②________
　　　 　lxr[i]＝cur
head＋＝1
if head＝＝tail：
break
if ③__________：
print(″需要″＋str(ren[p2]－1)＋″個介紹人″)
else：
print(″無法建立聯系″)
p＝p2；s＝″″
while ：
s＝str(lxr[p]＋1)＋″，″＋s
p＝lxr[p]
print(″依次訪問的聯系人為：″＋s＋str(p2＋1))
14.題目要求同題13，現找出所有的聯系人路徑，程序運行的結果如圖所示：
輸入第1個聯系人編號：1 輸入第2個聯系人編號：2 路徑：1，5，8，3，4，2 路徑：1，5，8，3，4，6，7，2
實現上述功能的Python程序如下，請在劃線處填入合適的代碼。
#列表a用于存儲聯系是否是朋友的關系
n＝8　#人員數量
p1＝int(input(″輸入第1個聯系人編號：″))－1
p2＝int(input(″輸入第2個聯系人編號：″))－1
b＝[0]*n；ren＝[0]*n
b[0]＝p1
head＝0；tail＝1
find＝[False]*n
find[p1]＝True
lxr＝[″″]*n
lxr[p1]＝str(b[head]＋1)＋″，″
while ①________：
cur＝b[head]
for i in range(n)：
if a[cur][i]＝＝1 and not find[i]：
　 　　　if ②________：
　　　　　 　print(″路徑：″＋lxr[cur]＋str(p2＋1))
　　　　 else：
　　　　　 　b[tail]＝i
　　　　 　　tail＋＝1
　　　　 　　find[i]＝True
　　 　　　　ren[i]＝ren[cur]＋1
③________
if head！＝tail：
lxr[b[head]]＝lxr[b[head－1]]＋str(b[head]＋1)＋″，″
專題13　隊　列
知識點一
1.B　[隊列的長度計算公式為tail－head，因此隊列中有3人排隊。]
2.D　[本題考查隊列的基本操作。T操作既有入隊，又有出隊，因此共有6次入隊，4次出隊，每次出隊和入隊，指針分別加1。]
3.D　[本題考查隊列性質和操作。根據隊列的特點“先進先出，后進后出”，8出隊后4入隊(2 次)，10 出隊后5入隊(2 次)，12 出隊后6入隊(2 次)。共 6 次，其結果為 9，4，5，6。]
4.B　[本題隊列的相關概念。隊列的元素計算公式為(tail－head＋n)%n，其中n是隊列存儲空間。B選項head＝2，tail＝6，長度是4。]
5.C　[本題考查隊列的性質。入隊3次，出隊4次，在3次入隊前tail應為6，在4次出隊前head應為3。]
6.C　[題目中隊列的元素執行隊首元素出隊，再從隊尾入隊，接下來隊首元素出隊并輸出，直至隊列空，輸出的順序為C選項結果。]
7.C　[根據題目描述，10分鐘過來了10個人購票，總共14人，期間4人結束購票，所以隊伍還有10人，1人在購票，9人在等待。]
知識點二
1.B　[本題考查隊列的入隊與出隊操作。字符串S中兩個字符為一組，第1個元素t代表入隊或出隊，第2個元素代表n入隊或出隊的次數。A是入隊，D是出隊，若出隊過程中隊空，則中止出隊。]
2.C　[本題考查隊列的基本操作。外循環循環5次，每次先出隊一個元素，內循環分別循環0，1，2，3，4將，每次循環將隊列元素出隊并入隊到最后。當i為0時，A出隊，不循環移動。i為1時，B出隊，C后移，隊列中為DEC。i為2時，D出隊，EC后移，隊列中為EC。i為3時，E出隊，C后移3次，隊列中為C。最后C出隊。]
3.B　[本題考查隊列的基本操作。程序的功能是查找隊列中最小值，pre初值為10，每次出隊一個元素，出隊元素也pre比較，記錄其最小值的過程。]
4.D　[本題考查隊列類實現。題中所給代碼實現了字符“A”“B”“C”依次入隊，要讓字符“C”出隊，根據隊列先進先出的特性，應執行三次出隊操作。]
5.B　[本題主要考查隊列的應用。程序實現的功能是：當隊不為空時，先出隊一個元素，再將隊首放在隊尾，并再次出隊一個元素。]
6.A　[本題考查隨機數和隊列及其代碼實現知識。變量k是1～5之間的整數，表示循環次數。每次將頭首乘以2和乘以2加1的2個數入隊，并將隊首出隊。變量s將隊列中的數據進行求和。]
7.A　[本題考查隊列的應用。遍歷到'－'字符，隊列中的元素按照一定的規則出隊，否則字符入隊。第1個出隊的元素一定是P，此時flag值為True，字符'y'重新進入隊尾。接下來't'出隊，flag值為False，依此類推。]
8.A　[本題考查隊列和列表的相關知識。根據題意可知，que當中追加的是lst中從前向后遍歷偶數值，且把該偶數從lst中刪除，最后將que中的偶數追加到lst后面，所以該程序段實現的是提取lst中的偶數放置末尾。]
9.D　[本題隊列的基本操作。入隊的條件是產生的隨機數為0，出隊的條件是隊不空且隊尾元素比較隊首元素小。A選項產生隨機數均為1，沒有任何元素入隊。B選項依次入隊過程中，隊尾元素大于隊尾元素值。C選項隊列中只有3個元素，先產生8，5，再進行出隊和入隊，最后再產生3，循環了4次，還有一次產生的隨機數為1，不做任何操作。D選項只要有元素入隊，第一個元素不可能為0。]
10.B　[本題考查隊列的性質。語句q[tail]＝q[head]表示將隊首出隊，再入隊，中間也可能有元素出隊，最后輸出隊列中元素。隊列的特性是先進先出，無論有多少元素全部出隊后，部分數據再入隊，在隊列的位置還是按原來的次序排列，因此選項B不可能。]
11.B　[本題考查隊列的基本操作。當i的值為2，3，5時，i均不在隊列中，因此入列3次，tail＝3，當i的值為1時，條件tail－head＝＝3成立，因此進行出隊(隊首指向2)操作，隊列中值依次為[3，5]，當i的值為3，5，不符合條件，當i的值為2時，入隊。]
12.D　[本題考查隊列的基本操作。A選項本語句塊的功能是當隊尾入隊一個元素后，入隊的值與隊首相同，則隊首出隊一個元素，當tail＝1時，隊列中只有一個元素，條件成立，形成死循環，因此必須判斷tail不等于1。B選項出隊后，新的隊首后面可能存在多個與隊首相同的元素，因此必須要采用循環結構。使其不斷地出隊。C選項totn用于存儲1－5各個序號的數量，語句totn＝[0]*5預設最大的下標元素為totn[4]，應為totn＝[0]*6。D選項p是下標，要統計的是s[p]的值，sum(totn)統計totn列表中所有元素之和，不管某個編號出現多少次，該編號的統計值為1，表示出現過，0表示未出現過。]
13.(1)①cur＝b[head]　②ren[i]＝ren[cur]＋1 ③find[p2]　(2)p！＝p1
解析　本題考查隊列和鏈表的基本操作。(1)b數組存儲訪問過的聯系人列表，語句b[0]＝p1表示從隊首開始遍歷隊列，下方用到a[cur][i]＝＝1，因此需對cur進行賦值。ren＝[0]*n#從p1開始訪問過的聯系人人數，從輸出語句print(″需要″＋str(ren[p2]－1)＋″個介紹人″)，因此第i個人訪問是在當前訪問次數加1。③空比較簡單，當找到find[p2]為真，可以輸出。(2)此次考查鏈表操作，p的初值為p2，p作為數組lxr中的下標，訪問lxr[p]的值，然后把lxr[p]作為新的下標，依次向前訪問，當訪問到p1時結束訪問，如數組lxr的值依次為[0，3，4，7，0，7，7，0]，p＝1，lxr[1]＝3，p＝3，lxr[3]＝4，p＝4，lxr[4]＝0，而要訪問的p1就是0號索引，因此須修改為p！＝p1。
14.①head！＝tail　②i＝＝p2　③head＋＝1
解析　本題考查隊列的基本操作。①由于要查找所有路徑，因此把b數組看成隊列，當隊列中沒有數據時，結束遍歷，因此條件是head！＝tail。②print(″路徑：″＋lxr[cur]＋str(p2＋1))，輸出一條路徑，因此必須是找到了，即i＝＝p2。③遍歷完一個數據，要對該數據進行出隊操作。

展開更多......

收起↑