資源簡介

專題18　基于數據結構的算法實現
學習目標　1.掌握隊列中元素入隊和出隊的條件；
2.掌握鏈表的構建方法.
隊列是線性結構的一種，因此也可以用鏈式結構的方式來實現。并且鏈式結構的隊列，由于節點空間都是在入隊的時候動態申請的 ，因此在計算機內存空間足夠的情況下，一般不需要考慮隊滿的情況，也就不存在溢出的情況，所以不需要使用循環鏈式隊列來處理假溢出的情況。 鏈式隊列在鏈表的鏈尾插入元素，然后讓隊尾指針指向鏈尾元素。鏈式隊列的出隊，就是將鏈表的首元節點從鏈表中刪去，讓其后繼節點成為首元節點，然后讓隊頭指針指向該節點。
(2024年1月浙江省選考)某項活動有n個單位(編號1到n)參加，需將員工分成若干個小組，每個小組的人數上限為m，小組編號按新建次序從1開始編號。分組時，首先按單位編號次序依次在各單位內部分分組，每m人分配到一個新建小組中，不足m人的剩余員工暫不分配；然后按剩余員工人數由大到小的順序，依次為各單位剩余員工分配小組。
若某單位剩余員工人數為k，則分配方法為：在已建的小組中查找空位數(該小組還可容納的人數)大于或等于k的小組，如果找到的小組有多個，則選擇空位數最少的小組，將此k人分配到該小組中；如果沒有找到，則新建一個小組，將此k人分配到該小組中。
設n為5，m為20，各單位員工人數及單位內部的分組過程如圖a所示，各單位剩余員工的分組過程如圖b所示。
編寫程序：給定各單位編號及員工人數，根據上述方法進行分組處理，按單位編號次序輸出各單位所分配的分組編號。請回答下列問題：
(1)由題意可知，若僅將圖a中1號單位的員工人數修改為25，然后對圖中5個單位重新分組，則1號單位所分配的分組編號為________。
(2)定義如下bubble_sort(lst)函數，參數lst的每個元素由單位編號和剩余員工人數2個數據項組成。函數的功能是根據每個單位的剩余員工人數，對lst進行降序排序。
def bubble_sort(lst):
　 n＝len(lst)
for i in range(0, n－1)：
　 return
調用該函數，若lst為[[1，0]，[2，0]，[3，18]，[4，0]，[5，19]，[6，17]]，請回答①和②兩個問題。
①虛線框中的程序段第1次執行后，關于lst中的剩余員工人數，下列說法正確的是________(單選，填字母)。
A.lst[0][1]數值最小 B.lst[0][1]數值最大
C.lst[5][1]數值最小 D.lst[5][1]數值最大
②虛線框中的程序段執行的次數為________。
(3)實現分組功能的部分Python程序如下，程序中用到的列表函數與方法如圖c所示，請在程序中劃線處填入合適的代碼。
函數與方法 功能
w.append(x) 在列表w末尾添加元素x
x＝w.pop() 將列表w末尾元素賦值給x，并將其從w中刪除
圖c
def group(data, m):
　 n＝len(data)
　 a＝[]
　 for i in range(n＋1)：
　 a.append([])　#a[i]初始化為空列表，存放編號為i的單位所分配的分組編號
　　gnum＝0
　　for i in range(n)：　#各單位內部分組
　 while data[i][1]>＝m：
　　　 gnum＋＝1
　　　　　 k＝data[i][0]
　　　 a[k].append(gnum)
　　　 ①________
　　bubble_sort(data)　#根據每個單位的剩余員工人數，對data進行降序排序
　　b＝[]
　　for i in range(m):
　b.append([])
　　i＝0
　　while i　 ②________
　 while j　　　 j＋＝1
　 if j　　　 v＝b[j].pop()
　 else：
　　　 gnum＋＝1
　　　 v＝gnum
　 a[data[i][0]].append(v)
　 ③________
　 i＋＝1
　　#輸出各單位的分組編號，代碼略
'''
讀取小組人數上限存入 m；讀取 1 至 n 號單位的數據，依次存入列表 data 的 data[0]至 data[n－1]中。data[i]包含 2 個數據項，data[i][0]，data[i][1]分別存放單位編號及員工人數，代碼略
'''
group(data, m)
重難點1　構建鏈表建立索引關系
高中階段的數據結構不是討論如何使用數據結構，而是通過對數據集進行簡單的操作，理解和創建數據結構。能將有限制條件的、真實情境中的數據關系進行抽象，根據數據特點與求解要求，選擇適當的數據類型表示各種數據，并用合適的數據結構表達數據的邏輯關系。在已有數據集的基礎上，通過鏈接關系構造邏輯上先后遍歷順序，構建鏈表，將有層次非線性結構或二維數組轉換為一維數組，再遍歷一維數組，得到問題的解。當原始數據量大，且每個數據元素有多個數據項時，直接對進行復制會浪費大量空間和時間，可進行基于索引的引用，提高效率。
例題 有2組器件共n個，要用一臺檢測設備檢測。每個送檢器件的信息包含送達時間、檢測時長和優先級。優先級有m(1編寫程序模擬檢測過程，先合并2組器件的數據，然后計算所有器件的平均等待時長，其中每個器件等待時長為其開始檢測的時間與送達時間的時間差。(時間單位均為秒)
請回答下列問題：
(1)由題意可知，圖中器件A、B、C、D的檢測順序為A－C－D－B，A、C、D的等待時長分別為0、1、0，B的等待時長是　　　　。
(2)定義如下merge(lst1， lst2)函數，參數lst1和lst2的每個元素由送達時間、檢測時長和優先級3項構成，lst1和lst2均已按送達時間升序排列。函數功能是將lst2中的元素合并到lst1中，并將lst1按送達時間升序排列，函數返回lst1。
def merge(lst1， lst2)：
　 i ＝ len(lst1) － 1
　 j ＝ len(lst2) － 1
　 for t in range(len(lst2))：
　　 lst1.append([0， 0， 0]) #為lst1追加一個元素[0， 0， 0]
　 k ＝ len(lst1) － 1
　 while j >＝ 0：
　　 if i >＝ 0 and lst1[i][0] > lst2[j][0]：
　　　 lst1[k] ＝ lst1[i]
　　　 i －＝ 1
　　 else：
　　　 lst1[k] ＝ lst2[j]
　　　 j －＝ 1
　　 k －＝ 1
　 return lst1
①調用merge(lst1， lst2)函數，若lst1為[[0， 3， 2]，[1， 1， 2] ， [12， 2， 2]]，lst2為[[2， 1， 1] ， [4， 3，0] ， [11， 3， 2]]，則while語句中循環體的執行次數是　　　　。
②若函數中while 語句的條件“j >＝ 0”誤寫為“k>＝0”，會導致某些情況下無法得到符合函數功能的結果。調用merge(lst1， lst2)函數，下列4組數據中能測試出這一問題的是　　　　(單選，填字母)。
A.lst1 ＝ [[0，3，2]，[4，3，0]] lst2 ＝ [[1，1，2]]
B.lst1 ＝ [[1，1，2]] lst2 ＝ [[0，3，2]，[4，3，0]]
C.lst1 ＝ [[1，1，2]，[4，3，0]] lst2 ＝ [[0，3，2]]
D.lst1 ＝ [[4，3，0]] lst2 ＝ [[0，3，2]，[1，1，2]]
(3)實現模擬檢測過程并計算平均等待時長的部分Python程序如下，請在劃線處填入合適的代碼。
def proc(data， m)：
　 n ＝ len(data)
　 queinfo ＝ []
　 for i in range(m)：
　 queinfo.append([－1， －1])　#queinfo追加一個元素[－1，－1]
　 for i in range(n)：
　 data[i].append(－1)　#data[i]追加一個元素－1
　 curtime ＝ 0
　 waitnum ＝ 0
　 i ＝ 0
　 ①　　　　
　 while i < n or waitnum > 0：
　　 if i < n and data[i][0] <＝ curtime：
　　　 k ＝ data[i][2]
　　　 if queinfo[k][0] ＝＝ －1：
　　　　　 queinfo[k][0] ＝ i
　　　 else：
　　　　　 ②　　　　
　　　　　 data[p][3] ＝ i
　　　 queinfo[k][1] ＝ i
　　　 waitnum ＋＝ 1
　　　 i ＋＝ 1
　　 elif waitnum > 0：
　　　 k ＝ 0
　　　 while queinfo[k][0] ＝＝ －1：
　　　　　 k ＋＝ 1
　　　 p ＝ queinfo[k][0]
　　　 total ＋＝ curtime － data[p][0]
　　　 curtime ＋＝ data[p][1]
　　　 ③　　　　
　　　 waitnum －＝ 1
　 else：
　　　 curtime ＝ data[i][0]
　return total / n
'''
讀取2組器件的數據，分別存入列表data1和data2中。2個列表的每個元素包含3個數據項，分別對應器件的送達時間、檢測時長和優先級。data1 和data2中的數據已分別按送達時間升序排列，代碼略
讀取優先級等級個數存入m，代碼略
'''
data ＝ merge(data1， data2)
print(proc(data， m))
變式 某工程包含n個任務(編號為0～n－1)，每天可以有多個任務同時進行。某些任務之間有依賴關系，如圖a所示，任務4依賴于任務1，任務1依賴于任務2。即任務2完成后才可以開始任務1，任務1完成后才可以開始任務4。不存在一個任務依賴于多個任務，或多個任務依賴于同一個任務的情況。現已對該工程的依賴關系進行了梳理，結果如圖b所示，標記“T”表示依賴關系需保留，標記“F”表示依賴關系需刪除。
根據每個任務完成所需的天數和梳理后的依賴關系，編寫程序，首先刪除標記為“F”的依賴關系，然后計算工程最快完成所需的天數，并以工程最快完成所需的天數為期限，計算每個任務最晚必須開始的時間。
圖a
任務A 任務B 標記
0 5 T
5 4 F
4 1 T
1 2 T
2 3 F
注：任務a依賴于任務b。
圖b
請回答下列問題：
(1)若某工程有6個任務，任務間依賴關系如圖a所示，完成任務0～5所需天數分別為2，1，3，5，1，6，則工程最快完成需要　　　　天。
(2)定義如下erase(lst)函數，參數lst列表的每個元素表示一個依賴關系。函數的功能是刪除標記為“F”的依賴關系，返回保留的依賴關系的個數。
def erase(lst)：
　 i＝0
　 j ＝ len(lst)－1
　 while i<＝ j：
　 if lst[i][2]＝＝ 'T'：
　　　 i＋＝1
　 else：
　　　 if lst[j][2] ＝＝ 'T'：
　　　 lst[i]＝lst[j]
　　　　 i ＋ ＝ 1
　　　 j － ＝ 1
return i
若lst列表依次存儲圖b所示的依賴關系，如lst[0]為[0，5，'T']，調用erase(Ist)的數，則語句“lst[i] ＝lst[j]”的執行次數為　　　　。
(3)實現上述功能的部分Python程序如下，請在劃線處填入合適的代碼。
def proc(n，lst，task)：
　 pr＝[0]*n
　 w＝[0]*n　#w[i]存放任務1最晚必須開始的時間
　 m＝erase(lst)
　 for i in ①　　　　：
　　 task[lst[i][1]][1]＝lst[i][0]
　　 pr[lst[i][0]]＝1
　 c＝[]
　 days＝0　#days存放工程最快完成所需的天數
　 for i in range(n)：
　 if pr[i]＝＝0：
　　　 k＝i
　　　 s＝0
　　　 while k！＝－1：
　　　　　　 c.append(k)
　　　　　　 s＋＝task[k][0]
　　　　　　 ②　　　　
　　　 if s>days：
　　　　　　 days＝s
　　for i in range(n－1，－1，－1)：
　　 k＝c[i]
　　 if task[k][1]＝＝－1：
　　　　 w[k]＝days－task[k][0]＋1
　　 else：
　　　 ③　　　　
　　　#輸出days，以及保存在w中的每個任務最晚必須開始的時間，代碼略
'''
工程包含的任務數存入變量n
任務間的依賴關系存入1st列表
1st[0]包含3項，任務1st[i][0]依賴于任務1st[i][1]，1st[i][2]存放保留/刪除標記，任務數據存入task列表
task[i]包含2項，task[i][0]為完成任務所需天數，task[i][1]的初值為－1
代碼略
'''
proc(n，lst，task)
重難點2　構建數組存儲臨時數據
針對情境較為復雜、結構化程度較低的問題，能抽象數據特征、創造性地運用數據結構優化算法。數據往往經過采集、傳輸、處理和存儲的過程，而數據在加工處理過程中，要考慮算法的優越性，提高算法的效率。數據在加工過程中，臨時存放的數據可以存儲在隊列、棧和二維數組中，利用其不用查找就可以操作或者把當前正在處理的數據放置一個較小的數組中的特性，加快數據的處理時間。
例題 某店使用加工設備制作m種類型的甜品，每分鐘只能制作一種類型，且不超過n個。每個訂單包含訂單編號、下單時間、類型和數量。編排制作順序的規則為：下單時間早的類型優先，下單時間相同時數量多的類型優先。下單時間最早的訂單數量不足n，可以先制作部分已下單相同類型甜品。每分鐘完成后，有新增訂單時，合并相同類型訂單，按上述規則重新編排順序，若編排后，新訂單仍有剩余，則剩余數量按實際下單時間繼續參與編排。
設m為3，n為10，某時段各個訂單如圖a所示，則制作甜品的順序為AABACB，數量為10、10、10、4、8、5，如圖b所示。編寫Python程序，根據訂單，輸出甜品的制作順序和數量。
訂單編號 下單時間 類型 數量
0406001 8：01 A 24
0406002 8：01 B 3
0406003 8：03 C 8
0406004 8：03 B 12
圖a
圖b
(1)如圖a所示，若訂單0406003提前到8：01下單，則制作順序為　　　　。
(2)定義如下least(tpr，ud，m)函數，參數tpr存儲當前各類甜品的下單時間，如tpr＝[[481，482]，[]，[]]表示當前A類型有8：01(將字符串時間格式8：01轉換為分鐘數字481)和8：02共2個訂單，B和C無訂單。參數ud存儲當前各個類型的訂單數量之和，如ud＝[4，0，0]表示當前A類型所有訂單數量和為4，B和C無訂單。參數m表示甜品種類。函數功能是查找當前待制作甜品的類型。
def least(tpr，ud，m)：
　 post＝0
　 for i in range(1，m)：
　 if len(tpr[i])>0：
　　　　 if
：
　　　　　　post＝i
　　　　elif tpr[i][0]＝＝tpr[post][0]：
　　　　　　if ud[i]>ud[post]：
　　　　　　　 post＝i
　　　return post
若加框處條件誤寫為“tpr[i][0]A.tpr＝[[481]，[481]，[482，483]]
ud＝[2，25，5]
B.tpr＝[[]，[482]，[482，483]]
ud＝[0，3，2]
C.tpr＝[[481，485]，[]，[482，483]]
ud＝[2，0，5]
D.tpr＝[[481，485]，[]，[]]
ud＝[2，0，0]
(3)實現上述功能的部分Python程序如下，程序中用到的列表函數與方法如下表所示，請在劃線處填入合適的代碼。
函數與方法 功能
w.append(x) 在列表w末尾添加元素x
w.pop(i) 刪除列表w索引為i的元素
sum(w) 累加列表w中的元素
#讀取各個訂單的數據，存入列表lst，每個元素包含訂單編號、下單時間、類型和數量。lst中的數據已按下單時間升序排列，代碼略。
#讀取甜品種類和每分鐘最多加工的數量，分別存入變量m和n，代碼略。
def convert(s)：
　 #將字符串格式時間s轉換成分鐘數，如convert(″08：00″)的值為480，代碼略。
tpr＝[[]for i in range(m)]
npr＝[[]for i in range(m)]
ud＝[0 for i in range(m)]
curtime＝convert(lst[0][1])　#當前時間為第1個訂單的下單時間
i＝0
while i 0：
　　while i　 t＝ord(lst[i][2])－ord(″A″)
　 tpr[t].append(convert(lst[i][1]))
　 npr[t].append(lst[i][3])
　 ①　　　　
　 i＋＝1
　　k＝least(tpr，ud，m)
　　tot＝0　　
　　while　ud[k]>0 and tot　 if 　 ②　 ：
　　　 ud[k]－＝npr[k][0]
　　　 tot＋＝npr[k][0]
　　　 tpr[k].pop(0)
　　　 npr[k].pop(0)
　 else：
　　　 npr[k][0]－＝n－tot
　　　 ud[k]－＝n－tot
　　　 tot＝n
　　　 #輸出當前時間加工的甜品類型及數量，代碼略
　　　 curtime＋＝1
　　　 if i　 ③　　　　
變式 有新訂單產生。公司安排的打包工作時間為12：00－18：00，假設當日訂單在工作時間內就能完成。公司有甲、乙、丙三位師傅對貨品進行打包，貨品按照甲、乙、丙的順序分配給各師傅處理，每位師傅一次打包一件貨品。打包規則：若下單時間相同，優先級越高(數字越小，優先級越高)的貨品，先全部打包完成；若不同，則下單時間更早的貨品先處理完成。
訂單輸入格式示例：7A2B、4B10A(說明：4B10A指訂單中有4件B類貨品，10件A類貨品)。編寫程序，輸出某天甲、乙、丙貨品打包順序和打包報酬，甲的輸出示例：3A5B1C，200元。
貨品 優先級 打包報酬(元/件)
A 1 30
B 2 20
C 3 10
表1
下單時間 貨品及數量
12：00 2B7A
14：00 7B
15：00 6B5C
表2
(1)若某天貨品下單信息如表2所示，則甲的打包順序為3A5B1C，乙的打包報酬為　　　　元。
(2)定義如下convert(data)函數，參數data為一個訂單，包括貨品和數量，函數功能將訂單轉換成貨品名稱序列，如訂單2B1A1C轉換成ABBC。請在劃線處填上合適的代碼。
def convert(data)：
　 num，q ＝ 0，″″
　 qsort ＝ [″″，″″，″″]
　 for i in range(len(data))：
　 if data[i] >＝″0″ and data[i] <″9″：
　　　 num ＝ 　　　　
　 else：
　　　 for j in range(num)：
　　　　　 q ＋＝ data[i]
　　　 qsort[ord(data[i])－ord(″A″)] ＝ q
　　　 num，q ＝ 0，″″
　　　s ＝ qsort[0]＋qsort[1]＋qsort[2]
　　　return s
(3)實現該功能的 Python 主程序如下，請在劃線處填入合適的代碼。
goods ＝ [30， 20， 10]
m ＝ (18－12)*2　#12：00－18：00之間每半個小時為一個時間節點
b ＝ [ ]
for i in range(m)：
　 b.append(″″)　#append()用于在列表的末尾添加一個元素
a ＝ [[″12：00″，″2B7A″][″14：00″，″7B″]，[″15：00″，″6B3C″]]
for i in range(len(a))：
　 que ＝ convert(①　　　　)
　 x ＝ (int(a[i][0][0：2])－12)*2　#將時間轉換為對應的結點
　 while len(b[x]) ＝＝ 3：
　　　 x ＝ x＋1
　 while len(que) > 0：
　　 t ＝ 3－len(b[x])
　　 if len(que) < t：
　　　 t ＝ len(que)
　　 b[x] ＝ ②　　　　
　　 if t ＝＝ len(que)：
　　　 que＝″″
　　 else：
　　　 que ＝ que[t：]
　　 x ＋＝ 1
s1， salary ＝″″， 0
for i in range(m)：　#甲處理順序和打包報酬輸出
　 if b[i] ！＝″″：
　　 s1 ＋＝ b[i][0]
　　 salary ＋＝③　　　　
#將s1中形如“ABBCC”的格式，轉換成“1A2B2C”的格式，代碼略
print(″甲處理順序和打包報酬：″， s1， str(salary)＋″元″)
#乙、丙處理順序和打包報酬輸出略
重難點1　構建鏈表建立索引關系
1.某花瓶廠有三臺不同型號的機器，可生產ABC三種不同型號的花瓶。廠家每天會收到很多網上訂單，每個客戶的訂單信息包含訂單號、型號、數量和狀態，其中狀態值為1表示確認訂單，－1表示取消訂單。工作人員首先挑選出確認的訂單，然后對訂單按花瓶型號進行分類統計，最后交給工作人員生產。訂單信息存儲在“orders.csv”文件中，文件數據格式如圖a所示。請回答下列問題。
圖a
訂單號 型號 數量 狀態
s001 A 1000 1
s002 B 2000 1
s003 B 1500 －1
s004 C 900 1
s005 B 800 1
s006 C 700 1
s007 A 500 －1
s008 B 600 1
圖b
(1)若某天的訂單如圖b所示，則當天應生產的B型號花瓶數量為　　　　。
(2)定義如下readdata()函數，函數功能是從訂單文件中挑選出確認的訂單，并將訂單的訂單號、型號和數量存儲在列表orders中，程序劃線處應填入的語句為　　　　。
def readdata()：
　 import csv
　 f＝open(″orders.csv″，″r″，encoding＝″utf－8″)
　 f_csv＝csv.reader(f)
　 title＝next(f_csv)　#讀取標題行
　 for line in f_csv：　#逐行讀取數據
　 if line[3]＝＝″1″：
　　　　orders.append([line[0]， 　　　　　，int(line[2])])
　 f.close()
　 return orders
(3)實現按花瓶型號分類統計花瓶數量的Python程序如下，程序運行結果如圖c所示。請在程序劃線處填入合適的代碼。
當天訂單信息為： [['s001'，'B'，6000]，['s002'，'A'，9000]，['s003'，'C'，9500]，['s008'，'A'，5000]] 分類訂單統計結果為： ['s002'，'A'，9000]→['s005'，'A'，6200]→['s008'，'A'，5000]→共計20200個 ['s001'，'B'，6000]→['s006'，'B'，3000]→共計9000個 ['s003'，'C'，7000]→['s007'，'C'，9500]→共計16500個
圖c
orders＝[]　#存儲訂單信息
readdata()
print(″當天訂單信息為：\\n″，orders)
n＝len(orders)；m＝3
tlist＝[]　#以鏈表形式存儲相同型號花瓶首尾訂單的索引值
for i in range(n)：
　 orders[i].append(－1)　#orders[i]追加一個元素－1
for i in range(m)：
　 tlist.append([－1，－1])　#tlist 追加一個元素[－1，－1]
i＝0
while i　　k＝ord(orders[i][1])－ord(″A″)
　　　if tlist[k][0]＝＝－1：
　 tlist[k][0]＝i
　 else：
　　 p＝tlist[k][1]
　　 ①　　　　
　 tlist[k][1]＝i
　 i＋＝1
p＝0
print(″分類訂單統計結果為：″)
while p　　　y＝tlist[p][0]
　　　total＝0
　　　while y！＝－1：
　　print(orders[y][0：3]，″→″，end＝″″)
　　②　　　　
　　y＝orders[y][3]
　　　print(″共計″，total，″個″)
　　　③　　　　
2.張三是一名計算機專業的大學生，為了幫助同學們學習專業相關的英語詞匯，編寫一個簡易字典程序。該程序中存放詞匯數據庫，在學習中輸入英文單詞，可以獲得中文翻譯結果。程序中的詞匯數據庫采用鏈表方式存儲，首字母相同時按升序排序。查找單詞時，首先根據首字母找到同首字母最小單詞所在鏈表，再按照鏈表順序查找該單詞。
(1)根據題意，部分的單詞庫數據邏輯結構如圖所示，查找單詞”byte”的過程是”binary”→”bit”→”byte”， 補充圖中空白單元格的值為　　　　。
列表索引 數據區域 指針區域
0 audio 音頻 －1
1 binary 二進制數 6
2 byte 字節 －1
3 cursor 光標 －1
4 access 存取 0
5 cache 高速緩存 3
6 bit 比特 　　　　
(2)wordlist(data，info)函數實現將詞匯數據庫data以鏈表的方式按字母序升序排列。info表示詞匯數據庫中各字母開頭的最小單詞位置，如info[0]表示字母a開頭的最小單詞在詞匯數據庫data中的位置。實現該功能的程序如下，請在劃線處填入合適的代碼。
info＝[]
def wordlist(data，info)：
　 n ＝ len(data)
　 for i in range(n)：
　 data[i].append(－1) #data[i]追加一個元素－1
　 for i in range(n)：
　 d ＝ data[i][0]
　 ①　　　　
　 if info[k] ＝＝ －1：
　　　 info[k] ＝ i
　 else：
　　　 head ＝ info[k]
　　　　　q ＝ head
　　　 while ②　　　　 ：
　　　　　 p ＝ q
　　　　　 q ＝ data[q][2]
　　　 if q ！＝ head：
　　　　　 data[p][2] ＝ i
　　　　　 data[i][2] ＝ q
　　　 else：
　　　　　 data[i][2] ＝ head
　　　　　 ③　　　　
　 return data，info
(3)searchword(data，info，key)函數實現單詞的查找。程序如下，請在劃線處填入合適的代碼。
def searchword(data，info，key)：
　 k ＝ ord(key[0]) － ord(″a″)
　 head ＝ info[k]
　 p ＝ head
　 while p ！＝ －1：
　 if data[p][0] ＝＝ key：
　　 　return 　　　　　
　 p ＝ data[p][2]
　 return″沒有找到該單詞″
'''
讀取詞匯數據庫，存入列表data中，列表的每個元素包含2個數據項，分別為英文單詞和中文翻譯，如data ＝ [[‘audio’，‘音頻’]，[‘binary’，‘二進制數’] …]，數據讀取存入的代碼略。
'''
info ＝ [－1] * 26
data，info ＝ wordlist(data，info)
key ＝ input(″請輸入查找單詞：″).lower()　#轉化為小寫字母
res ＝ searchword(data，info，key)
print(key，″查找結果是：″， res)
3.某外賣平臺推出同城代購服務，外賣騎手可接多個訂單，但是同一時間只能完成一項訂單。接單規則為：
·若騎手當前沒有訂單任務，則自動接收最先提交的訂單任務；
·若騎手在當前訂單完成前都沒有接到新的訂單，則輸出當前訂單，并接收排在最前面的訂單任務；
·若騎手當前正在執行訂單任務，期間有用戶提交訂單，則訂單進入等候區，并按照所需用時升序排列。
訂單信息存儲在“dingdan.txt”文件中，文件格式如圖a所示。文件按照下單時間升序存儲所有訂單信息，每一行數據存儲每個訂單的接收時間和完成訂單的所需用時，如
(“D1，07：15：36，2400”表示：D1號訂單，于07：15：36下單，需要2400秒才能完成)。
圖a
訂單名稱　 完成時間　 　D1　　　　07：55：36　 　D3　　　　09：05：36　 　D2　　　　10：35：36　 　D4　　　　11：32：02　 　D5　　　　14：37：30　
圖b
(1)如果某騎手一天內接到的訂單如表所示：
訂單號 接收時間 所需用時(秒)
D1 08：00：00 600
D2 08：05：00 1500
D3 08：30：00 1800
D4 08：33：00 900
D5 08：33：00 600
騎手在完成所有訂單后，各個訂單的完成順序為：　　　　(訂單號之間用逗號隔開，如D1，D2，D3，D4，D5)。
(2)定義如下convert()函數，函數功能是轉換時間格式，如將3663秒轉換為“01：01：03”，程序劃線處應填入的語句為　　　　。
def convert(t)：
　 s ＝″″
　 while t ！＝ 0：
　　 trs ＝ str(t % 60)
　　 if len(trs) < 2：
　　　 trs ＝″0″ ＋ trs
　　 s ＝″：″ ＋ trs ＋ s
　　 　　　　
　 return s[1：]
(3)運行如下程序，從文件中讀取訂單信息，經過加工處理后，按照騎手的完成順序依次輸出各個訂單的名稱以及該訂單的完成時間，運行結果如圖b所示。請在劃線處填入合適的代碼。
def read(file)：
　 #read()函數讀取訂單文件中的數據，整理后返回data列表
　 #若第一條訂單數據為：“D1，01：01：00，600”則存儲到列表data中的第一個元素data[0]＝['D1'， 3660， 600]
　 #代碼略
data ＝ read(″dingdan.txt″)
link ＝ []
n ＝ len(data)
head ＝ －1；i ＝ 0
finish ＝ 0 #結束時間
print(″訂單名稱 完成時間″)
while ①　　　　：
　 if head ＝＝ －1 and i < n：　#騎手當前沒有任務
　 link.append([data[i][0]，data[i][2]，－1])#向列表link中添加元素
　head ＝ len(link) － 1
　
　 i ＋＝ 1
　elif i ＝＝ n or data[i][1] > finish ：
　 print(link[head][0]，convert(finish))
　　head ＝ link[head][2]　#每完成一個訂單，頭節點指向下一個節點
　 finish ＋＝ link[head][1]
　elif data[i][1] <＝ finish and i < n：　#頭節點訂單正在執行，新訂單加入鏈表等待
　 q ＝ head
　 k ＝②　　　
　 link.append([data[i][0]，data[i][2]，－1])
　 while k ！＝ －1 and link[k][1] <＝ data[i][2]：
　　　 q ＝ k
　　　 k ＝ link[k][2]
　 link[len(link)－1][2] ＝ k
　 link[q][2] ＝ len(link) － 1
　 i ＋＝ 1
(4)程序加框處有誤，請改正。
4.某醫院為實現就診順序規則的相對公正，實行就診前“掛號＋簽到”模式，排隊規則如下：
1)初診患者簽到后，按掛號序號自小到大的順序排隊
2)復診患者按簽到順序，以“隔2插1”的規則排隊
3)年齡大于等于80歲的患者，可以優先就診
現系統根據簽到順序記錄了某天下午某科室掛號患者的信息如圖a所示，包括掛號序號、姓名、年齡、初診復診情況(0表示初診，1表示復診)。經系統處理后，輸出患者的就診順序如圖b所示，請回答問題。
(1)若有7位患者“掛號＋簽到”后的信息如圖c所示，則輸出的就診順序中，第三位就診的患者姓名是　　　　。
(2)實現按排隊規則輸出患者就診順序的部分Python程序如下，請在劃線處填入合適的代碼。
def insert(a，i)：
　 p＝head
　 while a[p][4]！＝－1 and a[a[p][4]][2]>＝80：
　
　 a[i][4]＝a[p][4]
　 a[p][4]＝i
def sort(a，i)：
　 p＝head
　 while p！＝－1 and ①　　　　：
　　 q＝p
　　 p＝a[p][4]
　 a[q][4]＝i
　 a[i][4]＝p
#讀取患者信息存入列表a中，列表的每個元素包含4個數據項，分別對應掛號序號、姓名、年齡、初診/復診，為方便處理，在列表前加入一個虛擬節點，如a＝[[0，'姓名'，200，0]，[3，'阮*倩'，30，1]，[9，'岑*光'，85，1]，……]，代碼略
n＝len(a)
for i in range(n)：
　 a[i].append(－1)
b＝[]
head＝0
for i in range(1，n)：
　 if a[i][2]>＝80：
　 a[i][1]＝a[i][1]＋'(優)'
　 insert(a，i)
　 elif a[i][3]＝＝0：
　 sort(a，i)
　 else：
　 a[i][1]＝a[i][1]＋'(復)'
　 b.append(a[i])
print('患者就診順序：')
left＝0；right＝len(b)
p＝②　　　　
while p！＝－1 and left！＝right：
　 for k in range(2)：
　 print(a[p][0]，'號'，a[p][1])
　 p＝a[p][4]
　 if p＝＝－1：break
　 print(b[left][0]，'號'，b[left][1])
　 ③　　　　
#輸出剩余就診患者信息，代碼略
(3)若列表a依次存儲圖c的患者信息，程序運行后，加框處的語句總共執行　　　　次。
重難點2　構建數組存儲臨時數據
1.某單位有多個部門，部門編號0～n－1，人數不盡相同，如圖a所示。現舉行某項活動，需要將所有人重新分組。分組前按部門人數由少到多的順序(升序)排列，從人數最少的部門開始，按每m人一組劃分，最后一組若不足m人，則該組不參加活動轉做后勤。例如設定每組人數m＝7，各部門人數存于列表a中，a＝[3，4，2，1，6，4]，則分組情況如圖b所示。
(1)由題意可知，若僅將圖a中1號部門的員工人數修改為2，則分組后第2組內的部門是　　　　。(請填寫正確的部門編號，若有多個編號則用逗號隔開，例如1，2，3)
(2)定義如下rank(a)函數，該函數的功能是返回1個列表，列表元素為各部門編號，并按部門人數升序排列。
def rank(a)：　#參數 a 為列表，表示各部門人數，例如[3， 6， 2， 1]
　 n ＝ len(a) ；
　 p ＝ [0] * n　#各部門初始排名號為0
　 b ＝ [0] * n
　return b　#返回列表b，例如[3，2，0，1]，表示人數最少是3號部門，最多的是1號部門
若a的值是[5，3，4，1]，執行rank(a)，函數中虛線框內程序結束后p列表的值是　　　　。
(3)實現分組的部分Python程序如下，請在程序中劃線處填入合適的代碼。
def group(a，m)：
　 b ＝ rank(a)
　 n ＝ len(a) ； gnum ＝ 0 ； c ＝ [[]]
　 ①　　　　
　 for i in range(n)： 　#共 n 個部門
　 tot ＋＝ a[b[i]]
　 c[gnum].append(b[i])
　 while　②　　　　：
　　　 tot ＝ tot － m
　　　 c.append([])
　　　③　　　　
　　　if tot > 0：
　　　　　　c[gnum].append(b[i])
　　　#判斷最后一個部門的分組情況
　　　if tot > 0： 　#最后一個部門有剩余且不足 m 人
　 c.pop() 　#去掉多余數據，將列表 c 最后一個元素刪除
　 print(tot，″人轉做后勤″)
　　　print(″團建共有″，gnum，″組，分組情況為：″ ， c)
'''讀取每組人數 m 值；讀取每個部門原始人數，依次存入列表 a 的 a[0]至 a[n－1]中。a[i]包含 1 個數據項，表示第 i 號部門的原始人數，代碼略'''
group(a， m)
2.設計一個簡單的快遞算法。有n位騎手為一個大型超市提供同城配送服務，假設每送完一單，騎手需回超市取貨。由于該超市的顧客有不同等級，因此騎手先送優先級高的訂單，若優先級相同，則先送距離近的訂單。編寫程序實現該算法，假設不考慮路況，忽略取貨、卸貨花費的時間并且每位騎手的平均速度相同，則可將距離轉換成單程配送時間(單位：分鐘)，優先級用數字表示，數字越小，優先級越高。請回答下列問題：
訂單號 優先級 單程配送時間
A 4 3
B 4 5
C 3 6
D 2 2
E 1 3
F 3 2
G 1 6
(1)若有如圖所示的訂單，并有2位騎手甲和乙，訂單總是先派給空閑的騎手，若都空閑，則先給甲。則訂單“C”的顧客需要等待的時間為　　　　分鐘。(填數字)
(2)定義sort_bag(a)函數，參數a列表中每個元素由優先級、單程配送時間2項構成。函數功能是將a的元素按優先級和配送時間按題意中的要求排序。代碼如下：
def sort_bag(a)：
　 n＝len(a)
　 for i in range(n－1)：
　 for j in range()：
　　 if a[j][0]>a[j＋1][0]：
　　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
　　　　 elif　②　　　　：
　　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
　 return a
①程序加框處代碼有錯，請改正。
②請補充程序劃線處。
(3)以下代碼模擬派送過程，并計算顧客的平均等待時長和訂單完成(以最后一位騎手返回超市的時間為準)的總時間，請在劃線處補充代碼。
#讀入訂單數據 data，由優先級、單程配送時間 2 項構成，并使用 sort_bag 函數 進行排序。代碼略
n＝int(input())　#騎手數量
rider＝[0]*n
nowtime，waittime，i＝0，0，0
while i　 for j in range(n)：
　 if ①　　　　：
　　　　 rider[j]＝rider[j]＋data[i][1]*2
　　　　 waittime＝waittime＋ ②　　　　
　　　 　i＝i＋1
　 if i＝＝len(data)：　#如果所有快遞都已經送出
　　　　 break
　 nowtime＝nowtime＋1
maxt＝0
for i in range(n)：
　　　if maxt　maxt＝rider[i]
print('顧客平均等待時長：'，waittime/len(data))
print('訂單完成時間：'，maxt)
3.某驛站每個時刻(以秒計)都可能有一批商品到達，編寫Python程序，統計商品到達時，在過去一個小時內共有幾個地區(用兩個大寫字母表示)的商品以及商品的數量，并按商品數量從多到少顯示。部分商品按到達時刻到達信息以及統計結果如表所示。
時刻(秒) 商品所屬地區 各地區商品情況
1 SU KU KA KA KA SU SU KU 3　KA 3　SU 3　KU 2
3 SG KA SU SU 4　SU 5　KA 4　KU 2　SG 1
3601 KA KA SG 3　KA 3　SU 2　SG 2
3604 SG SG AU SG (略)
如上表所示，第1秒有8個商品達到，分屬于3個地區。第3秒的4個商品到達后，地區數量有4個，其中商品最多的是SU。第3601秒的3個商品到達后，由于只統計1小時內的數據，因此第1秒的商品不能計算在內，該時刻的商品地區數只有3個。
請回答以下問題。
(1)對于上表中第3604秒時刻，一共有　　　　個不同地區的商品(填數量)。
(2)主程序。小林用數組c保存各個地區的商品數量和它的排名位次，用數組rank保存地區序號和商品數量并用以排序。地區序號由大寫字母對應的序號轉換而來。實現程序如下，請將劃線處程序補充完整。
def toInt(s)：
　 res ＝ ord(s[1])－ord('A')
　 res ＋＝ (ord(s[0])－ord('A')) * 26
　 return res
def toStr(x)：
　 res ＝ chr(x % 26 ＋ 65)
　 res ＝ chr(x ∥ 26 % 26 ＋ 65) ＋ res
　 return res
rank， c， q ＝ []， []， []
for i in range(26 * 26 ＋ 1)：
　 c.append([0， －1])　#c元素的第1個區域表示商品數量，第2個區域表示排名位次
　 rank.append([0，－1])
rank[0] ＝ [99999，－1]
head ＝ tail ＝ ans ＝ 0
delta ＝ 1 * 60 * 60
for i in range(n)：
　 #rank元素的第1個區域表示商品數量，第2個區域表示國家
　 #0號位置上放一個數量異常大的虛擬元素
　 #n表示需要處理的數據數量，即一共有n個時刻要處理
　 #讀入一個數據到line，line[0]表示時刻，line[1：]表示各國家(地區)對應字母
　 t ＝ int(line[0])
　 while head ！＝ tail：
　　　 if ①　　　　 ：
　　　 x ＝ q[head][1]
　　　 c[x][0] －＝ 1
　　　 if c[x][0] ＝＝ 0：
　　　　　　 ans －＝ 1
　　　 move_bottom(x)　#x國家(地區)的排位可能要往后移動，該程序代碼略
　　　 head ＋＝ 1
　　　 else：
　　　 break
for s in line[1：]：
　 x ＝ toInt(s)
　 c[x][0] ＋＝ 1
　 if c[x][0] ＝＝ 1：
　　　②　　　　
　　　c[x][1] ＝ ans
　 move_top(x)　#x國家(地區)的排名可能要往前移動
　 q.append([t， x])
　 tail ＋＝ 1
#輸出該時刻的國家(地區)數量與各國(地區) 商品數量，輸出結果如表中第三列所示
print(ans)
for i in range(1， ans＋1)：
　 print(toStr(rank[i][1])， rank[i][0])
(3)數據移動函數。為了保持數據按商品數量從大到小排序，當某國(地區)的商品數量變大時， 該國(地區) 的排名位次可能要往前移動，同時還要調整 c 數組中該國(地區) 商品數量排名位次的更新。小林用 move_top 函數實現了數據的移動，請將程序補充完整。
def move_top(x)：
　　num ＝ c[x][0]　#取x國(地區)商品的數量值
　　i ＝ c[x][1] － 1　#取x國(地區)的排位次序
　　while num > rank[i][0]：
　　　 ①　　　　
　　　 rank[i＋1] ＝ rank[i]
　　　 i －＝ 1
　　②　　　　
　　c[x][1] ＝ i＋1
重難點1　構建鏈表建立索引關系
1.使用Python編寫按文件后綴名進行分類的程序。要求實現的功能為：從文件夾中讀取所有文件名，存儲到 file 列表中，如：[[″000. mp3″]， [″001. pptx″]， [″002. pptx″]， [″003. jpg″]，…，[″099. jpg″]]，然后按文件后綴名進行分類，并統計每個類別下文件的數量，輸出結果如圖所示。
mp3類型的文件： 097.mp3 095.mp3 090.mp3 087.mp3 086.mp3 077.mp3 056.mp3 055.mp3 053.mp3 052.mp3 048.mp3 033.mp3 026.mp3 022.mp3 021.mp3 008.mp3 006.mp3 000.mp3 共18個 pptx類型的文件： 091.pptx 089.pptx 081.pptx 079.pptx 078.pptx 073.pptx 071.pptx 065.pptx 062.pptx 051.pptx 044.pptx 032.pptx 029.pptx 017.pptx 013.pptx 007.pptx 004.pptx 002.pptx 001.pptx 共19個 jpg類型的文件： 099.jpg 098.jpg 096.jpg 085.jpg 082.jpg 069.jpg 068.jpg 067.jpg 064.jpg 061.jpg 060.jpg 058.jpg 050.jpg 045.jpg 041.jpg 037.jpg 036.jpg 035.jpg 034.jpg 031.jpg 030.jpg 012.jpg 010.jpg 005.jpg 003.jpg 共25個 xlsx類型的文件： 094.xlsx 093.xlsx 088.xlsx 083.xlsx 080.xlsx 076.xlsx 074.xlsx 072.xlsx 066.xlsx 057.xlsx 049.xlsx 047.xlsx 042.xlsx 040.xlsx 027.xlsx 024.xlsx 023.xlsx 019.xlsx 018.xlsx 016.xlsx 共23個 docx類型的文件： 092.docx 084.docx 075.docx 070.docx 063.docx 059.docx 054.docx 046.docx 043.docx 039.docx 038.docx 028.docx 025.docx 020.docx 011.docx 共15個
(1)定義如下ft(s)函數，參數s為文件名(如″000.mp3″)。函數功能是將文件名中的后綴名取出，并返回該后綴名。完成程序空白處代碼。
def ft(s)：
　 n＝len(s)－1
　 while 　　　　：
　　 n－＝1
　 return s[n＋1：]
(2)按后綴名將文件名分為五類，分別為“mp3、pptx、jpg、xlsx、docx”。分類的具體代碼如下，請在劃線處填入合適的代碼。
#從目錄讀取文件名到file列表過程略
for i in range(len(file))：
　 file[i].append(－1)　#append()功能：為列表增加一個元素
fhead＝[]
for i in range(len(file))：
　 ①　　　　
　 j＝0
　 while j　　 j＋＝1
　 if j　　 file[i][1]＝fhead[j][1]
　　 ②　　　　
　 else：
　　 fhead.append([a，i])　#append()功能：為列表增加一個元素
(3)按后綴名類型將文件名輸出，效果如圖所示(文件名輸出每10個換一行)。具體代碼如下，請在劃線處填入合適的代碼。
for i in range(len(fhead))：
　 print(fhead[i][0]＋″類型的文件：″)
　 ①　　　　
　 n＝0
　 while p！＝－1：
　　 n＋＝1
　　 print(file[p][0]，end＝″″)
　　 if n%10＝＝0：
　　　 print(″″)
　　②　　　　
　print(″″)
　print(″共″＋str(n)＋″個″)
2.某學校工會舉行飛鏢大賽，共有n位老師報名參賽，每位選手共擲5支鏢，每鏢得分為0至10分，選手總分為5鏢成績之和，每位選手的比賽數據記錄在文本文件中，如圖a所示。
圖a
處理前的數據為： [['s001'，38]，['s002'，8]，['s003'，26]，['s004'，25]，['s005'，36]，['s006'，27]，['s007'，28]，['s008'，18]] 處理后的數據為： [['s001'，38，4]，['s002'，8，－1]，['s003'，26，3]，['s004'，25，7]，['s005'，36，6]，['s006'，27，2]，['s007'，28，5]，['s008'，18，1]] 從高分到低分依次輸出選手的編號和總分為： ['s001'，38] ['s005'，36] ['s007'，28] ['s006'，27] ['s003'，26] ['s004'，25] ['s008'，18] ['s002'，8] NULL
圖b
處理要求：數據讀入數組data中，計算出每位選手的總分，在不改變數據在原數組data中的位置的條件下，按總分從高到低輸出選手的編號和總分。
(1)主程序。采用鏈表結構處理數據。程序運行結果如圖b所示。請在程序中劃線處填入合適的代碼。
data ＝ readdata(″scores.txt″)　#讀取數據，計算總分
print(″處理前的數據為：\\n″，data)
n＝len(data)
flag＝[True]*n　#標記數據被使用情況
head＝findmax()　#返回data中可使用狀態最大數的位置
k＝head
for i in range(1，n)：
　 posi＝findmax()
　 data[k].append(posi)
　 　　　　　　
data[k].append(－1)
print(″處理后的數據為：\\n″，data)
print(″從高分到低分輸出為：″)
output(head)
(2)編寫readdata函數，功能為從文本文件讀取數據，計算出總分，返回列表。代碼如下，請在程序中劃線處填入合適的代碼。
def readdata(filename)：
　 f＝open(filename)
　 line＝f.readline()
　 lst＝[]
　 while line：　#獲取每位選手的編號和總分數據
　 line＝line.split(″，″)
　s＝0
　for i in range(1，len(line))：
　　　 　　　　
　 lst.append([line[0]，s])
　line＝f.readline()
　 return lst
(3)編寫findmax函數，功能為返回data中可使用狀態最大數的位置pos，并設置該數的使用狀態為False。請在程序中劃線處填入合適的代碼。
def findmax()：
　 maxnum＝0
　 for i in range(n)：
　 if ①　　　　：
　　　 maxnum＝data[i][1]
　　　 pos＝i
　 ②　　　　
　 return pos
(4)編寫output函數，功能為從高分到低分輸出選手的信息。代碼如下，加框處的代碼有誤，請改正。
def output(q)：
　 while　：
　 print(data[q][0：2]，end＝″ ″)
　q＝data[q][2]
print(″NULL″)　#表示結束
3.某醫院的看病流程為：患者通過網上、自助設備或人工窗口成功掛號后，到門診的簽到處簽到，簽到成功后即可排隊等待叫號就診。簡化的排隊規則如下：
①當天08：00之前完成簽到的患者，按照掛號順序從小到大排隊就診；
②08：00之后簽到的患者，按照掛號的序號從小到大的次序插入候診隊伍中；
③隊伍中前3名患者(包括正在就診患者)視為已進入待診狀態，插隊的患者只能插到這3名待診患者后的隊伍中。
假設醫生從08：00開始叫號就診，對每位患者的診斷時間均為3分鐘，忽略相鄰患者就診的時間間隔。編寫程序實現以下功能：若有患者簽到，則根據規則更新候診隊伍；醫生每完成一名患者的診斷，電子屏幕上按順序顯示待診的患者姓名和每個患者預計就診的時間。
(1)若當前已簽到患者信息如表所示：
姓名 掛號序號 簽到時間
A 3 07：47：03
B 1 07：51：12
C 6 07：55：32
D 4 07：57：10
E 8 07：59：52
F 2 08：02：07
則患者F的預計就診時間為　　　　(格式如08：07：20)。
(2)08：00：00之前簽到的患者原始數據存在列表lst中，每位患者信息包括姓名、掛號序號、簽到時間，以下函數將列表中的數據按掛號序號從小到大排序，并構建候診隊伍。
def init(lst)：　#構建 8 點前簽到的候診隊伍
　 i＝0；n＝len(lst)
　 while i　 k＝i；i＝n－1
　for j in range(n－1，k，－1)：
　　　 if lst[j][1]　　　　　 lst[j]，lst[j－1]＝lst[j－1]，lst[j]
　 　　　　　　　　　
　　for i in range(n)：
　 lst[i][2]＝180*i　#修改時間格式，每位患者診斷時間為3分鐘
　lst[i].append(i＋1)
　　lst[n－1][3]＝－1　#尾結點指針域處理，如['E'， 8， 720， －1]
程序劃線處的代碼是　　　　(單選，填字母)。
A.i＝i＋1 B.i＝j＋1
C.i＝k－1 D.i＝j
(3)每當一位患者就診結束，更新隊伍并按就診順序輸出待診的患者姓名和每個患者預計就診的時間。請補充程序劃線處。
def gs(t)：　#時間格式轉換，將時間戳127轉成“08：02：07”形式
　 t＝t＋8*60*60
　 h＝t∥3600
　 m＝　　　　　　
　 s＝t%60
　 time＝'%02d'%h＋'：'＋'%02d'%m＋'：'＋'%02d'%s
　 return time
def mov(lst，head)：
　 #更新隊伍并輸出，代碼略
　 return head
(4)若有患者簽到，則更新候診隊伍。請將程序劃線處代碼補充完整。
def tc(time)：　#時間格式轉換，將“08：02：07”轉換成以秒為單位的時間戳127
　 t＝int(time[0：2])*60*60＋int(time[3：5])*60＋int(time[6：])
　 t＝t－8*60*60　#8點開始叫號看診
　 return t
def insnew(lst，head，data)：　#將新簽到的患者插入候診隊伍中，并更新每個患者預計就診的時間
　 data[2]＝tc(data[2])
　 data.append(－1)
　 p＝head； q＝p； k＝0
　 if head＝＝－1：　#無人排隊
　 lst.append(data)
　 ①　　　　
　 else：
　 while q！＝－1 and (②　　　　)：
　　　 k＝k＋1
　　　 p＝q
　　　q＝lst[q][3]
　 data[2]＝lst[p][2]＋180
　 data[3]＝q
　 lst.append(data)
　 lst[p][3]＝len(lst)－1
　 p＝len(lst)－1
　 while q！＝－1：
　　　 lst[q][2]＝lst[p][2]＋180
　　　 p＝q
　　　 q＝lst[q][3]
　 return head
4.現有n項先后出現的任務，每項任務需要一定的時間完成，且每個時刻只能執行某一項任務。任務的處理規則如下：
1)每項任務有一個緊急程度，用數字表示，數字越大緊急程度越高。緊急程度最高的任務優先執行，緊急程度相同先出現先執行。
2)若某項任務在執行過程中出現了一個緊急程度更高的任務，則正在執行的任務將被暫停，執行該緊急程度更高的任務。
編寫Python程序，實現如下功能：程序運行時，按編號升序輸出各項任務數據顯示如圖a所示，然后根據任務先后完成的情況顯示結果，如圖b所示。
請回答下列問題：
(1)若有3個任務需要完成，數據如下：
1號任務：時刻1出現，完成所需時長4，緊急程度1
2號任務：時刻2出現，完成所需時長2，緊急程度2
3號任務：時刻7出現，完成所需時長1，緊急程度3
則這3個任務的完成的順序為　　　　(單選，填字母：A.1號、2號、3號 /B.2號、3號、1號 / C.2號、1號、3號)。
(2)實現上述功能的Python程序如下，請在劃線處填入合適的代碼。
n＝8　#n保存總任務數
w＝[[4，20，2，3]，[5，21，9，4]，[1，1，5，3]，[7，23，5，2]，[8，24，2，4]，[2，10，5，1]，[3，12，7，2]，
　[6，22，9，4]]　#w中每個元素依次保存，任務編號、出現時刻、所需時長和緊急程度數據
#讀取任務編號、出現時刻、完成所需時長和緊急程度的數據，代碼略
for i in range(n－1)：
　 for j in range(0，①　　　　)：
　　 if w[j][0]>w[j＋1][0]：
　　　　　w[j]，w[j＋1]＝w[j＋1]，w[j]
#輸出圖a數據，代碼略
cur＝1　#記錄當前任務時刻
q＝[－1]*20　#q數組按優先順序存儲已出現的任務編號
t＝[i[2] for i in w]
tail＝head＝0
print(″任務編號″，″完成時刻″)
i＝0
while ②　　　　：
　 if tail>head：
　　　t[q[head]]－＝1
　　　if ③　　　　：
　　　　　print(w[q[head]][0]，cur)
　　　　　head＋＝1
　 if i　　　④　　　　
　　　tail＋＝1
　　　i＋＝1
　　j＝tail－1
　　while j>head and w[q[j]][3]>w[q[j－1]][3]：
　　　　q[j]，q[j－1]＝q[j－1]，q[j]
　　　　j－＝1
　　cur＋＝1
重難點2　構建數組存儲臨時數據
1.某市舉辦科技嘉年華活動，為了激發學生的參與積極性，舉辦方推出了玩游戲得積分，積分兌換禮物的活動。活動中游戲分為簡單和困難兩種，參與游戲就可以獲得相應的積分，當完成困難游戲時，除了獲得相應積分外，還可獲得一張“積分翻倍卡”，一張“積分翻倍卡”可用于一個簡單游戲，使簡單游戲的積分翻倍。
“積分翻倍卡”使用規則如下：
(1)當簡單游戲開始時，如果有“積分翻倍卡”可用，則一定會使用。
(2)“積分翻倍卡”需在15分鐘內使用。比如困難游戲完成時間是9：15分，則獲得的“積分翻倍卡”將在9：15分激活，且超過9：30分將失效。
3)如果有多張“積分翻倍卡”，則優先使用最早的“積分翻倍卡”。
某同學的游戲記錄如圖a所示(類型0表示困難游戲，類型1表示簡單游戲)，小明讀取游戲記錄，編寫Python程序計算出該同學游戲的最終得分。程序運行結果如圖b 所示，請回答下列問題：
序號 類型 積分 開始時間 完成時間
1 0 10 9：10 9：15
2 1 3 9：15 9：28
3 1 5 9：38 9：42
4 0 12 9：58 10：05
5 1 3 10：20 10：36
6 0 15 10：48 10：55
7 1 3 11：25 11：29
圖a
(1)若某同學參加游戲的記錄如圖c所示，則他獲得的積分是　　　　分。
(2)定義如下函數 change(t)，參數t為游戲時間，函數功能是將時間t轉換為分鐘并返回。如：t＝″9：20″時，轉換為整數(分鐘)值是560，函數返回值為560。函數代碼如下，請在劃線處填入合適的語句。
def change(t)：　#參數t的時間格式為：″小時：分鐘″
　 m＝t.split(″：″)
　 s＝　　　　
return s
(3)計算游戲積分的部分Python程序如下，請在劃線處填入合適的代碼。
從Excel文件中讀取游戲過程記錄，存儲在列表s中，如s＝[[1，0，10，550，565]，[2，1，3，565，568]，...]，s[i]表示第i個游戲記錄，s[i][0]，s[i][1]，s[i][2]，s[i][3]，s[i][4]依次存儲游戲的序號、類型、積分、開始時間，完成時間；當游戲類型s[i][1]值為日時表示困難游戲，為1則表示簡單游戲；
將困難游戲取出存入列表a中，列表 a按游戲完成時間升序排序；
將簡單游戲取出存入列表b中，列表b按游戲開始時間升序排序，代碼略
que＝[－1]*(len(a)＋len(b)＋1)
head＝tail＝0
total＝0
for i in range(len(a))：　#累加游戲積分，將“積分翻倍卡”激活時間加入隊列
　 total＋＝a[i][2]
　 ①　　　　
　 tail＋＝1
for i in range(len(b)) ：
　 while head　 print(que[head]∥60，″：″， que[head] % 60，″時刻生效的″＋″積分翻倍卡過期；″)
　 head＋＝1
　 if head　 print(b[i][3]∥60，″：″， b[i][3]%60，″時刻使用了積分翻倍卡；″)
　 ③　　　　
　 head＋＝1
　 else：
　 total＋＝b[i][2]
print(″總共獲得積分為：″，total，″分，″，″剩余積分卡有：″，tail－head，″張。″)
2.某學校有n個社團組織招新(社團編號為1－n)，每個社團最多可招收m人。學生在線提交申請信息，提交內容為社團編號和對該社團的喜好程度(1－5分)，學生可同時提交報名多個社團，但只能被1個社團錄取。后臺自動記錄學生的報名序號和全部報名信息。報名序號從1開始編號，申請信息的記錄格式如圖a所示，報名序號為1的學生報名3號社團喜好程度為3，同時報名2號社團喜好程度為4，還報名了1號社團喜好程度為5。
學生報名完畢后，n個社團通過抽簽決定招新順序，抽簽號為1－100的隨機整數，抽到數字小的社團先招錄學生。每個社團招錄時，系統調取報名該社團的申請信息，根據學生提交的喜好程度從高到低錄取，尚未被其他社團錄取的學生，喜好程度相同則按報名序號(學生的報名先后順序)從小到大錄取。
編寫程序，讀取每位學生的報名序號及報名信息、各社團的抽簽序號，程序自動完成社團招新并輸出錄取結果。
例如，3個社團招新，每社團最多招收2人，社團的抽簽序號依次為1、3、2，那么圖a中的報名信息，招新結果如圖b所示。
報名 序號 申請信息(每2個數字為一組，表示社團編號，喜好程度)
1 3，3，2，4，1，5
2 3，1
3 3，2，1，4，2，4
4 3，1，1，1
5 2，1，3，1
圖a
社團編號 抽簽序號 有意向學生(括號中為喜好程度) 錄取結果
1 1 1(5)，3(4)，4(1) 1，3
2 3 1(4)，3(4)，5(1) 5
3 2 1(3)，2(1)，3(2)，4(1)，5(1) 2，4
圖b
請回答下列問題：
(1)若每個社團最多招收人數為3人，1、2、3號社團抽簽序號仍為1、3、2時，對圖a中的數據進行重新執行招錄操作，則3號社團錄取的學生為　　　　。
(2)定義如下px(clubs)函數，參數clubs存儲社團數據，club[i]包含2個數據項，club[i][0]和club[i][1]分別存儲社團編號及抽簽序號。
def px(clubs)：
　 n ＝ len(clubs)
　 ans＝[]
　 for i in range(n)：　#①
　 for j in range(n－1，i，－1)：
　　　　 if clubs[j][1] < clubs[j－1][1]：
　　　　 clubs[j]，clubs[j－1]＝clubs[j－1]，clubs[j]
　 ans.append(clubs[i][0])
　 return ans
已知clubs為[[1，8]，[2，25]，[3，3]，[4，9]，[5，1]，[6，25]]，若①處的語句改為“for i in range(n－1)”，執行a＝px(clubs)，a的值為　　　　。(單選，填字母)。
A.[5，3，1，4，2，6] B.[5，3，1，4，2]
C.[5，3，1，4，6，2] D.[5，3，1，4，6]
(3)實現社團招錄功能的Python代碼如下，請在程序中劃線處填入合適的代碼。
def assign(stus，clubs，n，m)：
　 ans＝[[] for i in range(n＋1)]
　 #預處理，對社團i，好感j分的全部報名序號存入f[i][j]
　 f＝[[[] for j in range(6)] for i in range(n＋1)]
　 for item in stus：
　for x in range(0， len(item[1])， 2)：
　　　　 st＝item[1][x]
　　　　 fs＝①　　　　
　　　　 f[st][fs].append(item[0])
　　rs＝len(stus)
　　flag＝[False]*(rs＋1)
　　b＝px(clubs)
　　for i in b：　#各社團按順序依次招新
　t＝m
　fs＝5
　while fs>0 ：
　　　　 ②　　　　
　　　　 for j in x：
　　　　 if ③　　　　：
　　　　　 ans[i].append(j)
　　　　　 flag[j]＝True
　　　　　 t－＝1
　　　 fs－＝1
　return ans
#讀取學生報名信息，報名序號為i的信息存儲在stus[i]中，stus[i][0]存儲報名序號，stus[i][1]存儲申請信息，代碼略。
#讀取社團數n和每個社團可招錄的學生數m，代碼略。
#讀取社團編號和抽簽序號，存入clubs中，clubs[i][0]存儲社團編號，clubs[i][1]存儲抽簽序號，代碼略。
ans＝assign(stus，clubs，n，m)
for i in range(1，len(ans))：
　 print(″社團″＋str(i)＋″：″，ans[i])
3.某餐廳的訂單數據由線上、線下多條訂單合并而成。各條訂單含下單時間、菜品列表兩個數據項，下單時間(各訂單下單時間互不相同)的數據格式為“時：分鐘”；菜品列表由互不重復的大寫字母構成，按字母升序排列如“ABC”，每個字母代表一種菜品，合并后的訂單數據如圖a所示。
由于廚師一鍋能烹飪5份同種菜品，為了提升烹飪效率，餐廳打算為廚師提供烹飪提示隊列。按合并訂單數據中下單時間的先后順序逐條處理，對各條訂單中的不同菜品進行統計：當某種菜品中首份菜品的下單時間超過10分鐘時，或某種菜品累計份數達到5份時，該種菜品及累計份數將進入烹飪提示隊列，入隊后該種菜品重新開始統計。
當多種菜品符合某個入隊條件時，按各菜品中首份菜品下單時間先后時間順序入隊。所有訂單處理完畢，剩余未入隊的菜品直接進入派單提示器隊列，處理結果如圖b所示。
編寫程序：給定訂單數據，根據上述方法進行處理，輸出派單提示器隊列。請回答下列問題：
(1)由題意可知，若僅將圖a中的數據項['10：00'， 'ABC']修改為['10：00'， 'BC']，則A菜品第1次烹飪的數量為　　　　份。
(2)定義如下merged_list(lst1，lst2)函數，參數lst1和lst2的每個元素由下單時間和菜品列表2項構成，lst1和lst2均已按下單時間升序排列。函數功能是將lst2中的元素合并到lst1中，lst1按下單時間保持升序排列，函數返回lst1。
def merged_list(lst1，lst2)：
　 m ＝ len(lst1) － 1
　 n ＝ len(lst2) － 1
　 tail ＝ m ＋ n ＋ 1　#①
　 for i in range(n ＋ 1)：　#②
　 lst1.append([″″，″″])
　 while n >＝ 0：
　 if lst1[m][0] > lst2[n][0]：　#③
　　　　 lst1[tail] ＝ lst1[m]
　　　 m －＝ 1
　 else：
　　　 lst1[tail] ＝ lst2[n]
　　　 n －＝ 1
　 tail －＝ 1
　 return lst1
若lst1為[['10：01'，'AFHM']，['10：04'，'EIQZ']，['10：05'，'CPVXZ']]，lst2為[['10：00'，'AKVY']，['10：02'，'GLQS']，['10：06'，'FGQY']]，調用merged_list(lst1，lst2)，發現運行結果有誤，應從程序中①、②、③三處語句中選擇　　　　(單選：填序號)處，將其修改為　　　　。
(3)實現派單提示器隊列功能的部分Python程序如下，程序中用到的列表函數與方法如表所示，請在程序劃線處填入合適的代碼。
函數與方法 功能
dc.append(x) 在列表dc末尾添加元素x
head＝qu.pop(x) 將列表x位置元素賦值給head，并將其從qu中刪除
def inttime(time)：
　 t＝int(time[0：2])*60＋int(time[3：])
　 return t
def proc(orders)：
　 dc，qu＝[]，[]
　 for i in range(26)：
　 dc.append([0，0])
　 for i in range(len(orders))：
　 t＝inttime(orders[i][0])
　①　　　　
　for j in range(len(dishes_str))：　#處理單個訂單中的每種菜品
　　　　dish＝ord(dishes_str[j])－ord(″A″)
　　　　dc[dish][0] ＋＝ 1
　　　　if dc[dish][0]＝＝1：
　　　　　 dc[dish][1]＝t
　　　　　 qu.append(dish)
　 pret＝0　#檢查某種菜品是否需要進入烹飪派單提示器隊列
　 if i　　　pret＝inttime(orders[i＋1][0])
　 while ②　　　　：　#當某種菜品中首份菜品的下單時間超過10分鐘時
　　　head＝qu.pop(0)
　　　print(″菜品″， chr(head＋ord('A'))，″烹飪″，dc[head][0]，″份。″)
　　　dc[head][0] ＝ 0
　 k＝0
　 while k　　　 if dc[qu[k]][0]＝＝5：
　　　 ③　　　　
　　　　 print(″菜品″， chr(pdish＋ord('A'))，″烹飪″，dc[pdish][0]，″份。″)
　　　　 dc[pdish][0] ＝ 0
　　　 else：
　　　　 k＋＝1
#所有訂單完畢后，剩余未入隊的菜品直接進入派單提示器隊列，代碼略
″″″
讀取線上、線下多條訂單存入列表order1、order2，2個列表中的每個元素包含2個數據項，分別存放下單時間、菜品列表。2個列表的數據已分別按下單時間升序排列，代碼略
″″″
orders ＝ merged_list(order2， order1)
proc(orders)
專題18　基于數據結構的算法實現
學習目標　1.掌握隊列中元素入隊和出隊的條件；
2.掌握鏈表的構建方法.
隊列是線性結構的一種，因此也可以用鏈式結構的方式來實現。并且鏈式結構的隊列，由于節點空間都是在入隊的時候動態申請的 ，因此在計算機內存空間足夠的情況下，一般不需要考慮隊滿的情況，也就不存在溢出的情況，所以不需要使用循環鏈式隊列來處理假溢出的情況。 鏈式隊列在鏈表的鏈尾插入元素，然后讓隊尾指針指向鏈尾元素。鏈式隊列的出隊，就是將鏈表的首元節點從鏈表中刪去，讓其后繼節點成為首元節點，然后讓隊頭指針指向該節點。
(2024年1月浙江省選考)某項活動有n個單位(編號1到n)參加，需將員工分成若干個小組，每個小組的人數上限為m，小組編號按新建次序從1開始編號。分組時，首先按單位編號次序依次在各單位內部分分組，每m人分配到一個新建小組中，不足m人的剩余員工暫不分配；然后按剩余員工人數由大到小的順序，依次為各單位剩余員工分配小組。
若某單位剩余員工人數為k，則分配方法為：在已建的小組中查找空位數(該小組還可容納的人數)大于或等于k的小組，如果找到的小組有多個，則選擇空位數最少的小組，將此k人分配到該小組中；如果沒有找到，則新建一個小組，將此k人分配到該小組中。
設n為5，m為20，各單位員工人數及單位內部的分組過程如圖a所示，各單位剩余員工的分組過程如圖b所示。
編寫程序：給定各單位編號及員工人數，根據上述方法進行分組處理，按單位編號次序輸出各單位所分配的分組編號。請回答下列問題：
(1)由題意可知，若僅將圖a中1號單位的員工人數修改為25，然后對圖中5個單位重新分組，則1號單位所分配的分組編號為________。
(2)定義如下bubble_sort(lst)函數，參數lst的每個元素由單位編號和剩余員工人數2個數據項組成。函數的功能是根據每個單位的剩余員工人數，對lst進行降序排序。
def bubble_sort(lst):
　 n＝len(lst)
for i in range(0, n－1)：
　 return
調用該函數，若lst為[[1，0]，[2，0]，[3，18]，[4，0]，[5，19]，[6，17]]，請回答①和②兩個問題。
①虛線框中的程序段第1次執行后，關于lst中的剩余員工人數，下列說法正確的是________(單選，填字母)。
A.lst[0][1]數值最小 B.lst[0][1]數值最大
C.lst[5][1]數值最小 D.lst[5][1]數值最大
②虛線框中的程序段執行的次數為________。
(3)實現分組功能的部分Python程序如下，程序中用到的列表函數與方法如圖c所示，請在程序中劃線處填入合適的代碼。
函數與方法 功能
w.append(x) 在列表w末尾添加元素x
x＝w.pop() 將列表w末尾元素賦值給x，并將其從w中刪除
圖c
def group(data, m):
　 n＝len(data)
　 a＝[]
　 for i in range(n＋1)：
　 a.append([])　#a[i]初始化為空列表，存放編號為i的單位所分配的分組編號
　　gnum＝0
　　for i in range(n)：　#各單位內部分組
　 while data[i][1]>＝m：
　　　 gnum＋＝1
　　　　　 k＝data[i][0]
　　　 a[k].append(gnum)
　　　 ①________
　　bubble_sort(data)　#根據每個單位的剩余員工人數，對data進行降序排序
　　b＝[]
　　for i in range(m):
　b.append([])
　　i＝0
　　while i　 ②________
　 while j　　　 j＋＝1
　 if j　　　 v＝b[j].pop()
　 else：
　　　 gnum＋＝1
　　　 v＝gnum
　 a[data[i][0]].append(v)
　 ③________
　 i＋＝1
　　#輸出各單位的分組編號，代碼略
'''
讀取小組人數上限存入 m；讀取 1 至 n 號單位的數據，依次存入列表 data 的 data[0]至 data[n－1]中。data[i]包含 2 個數據項，data[i][0]，data[i][1]分別存放單位編號及員工人數，代碼略
'''
group(data, m)
答案　(1)1，8　(2)①B　②4次　(3)①data[i][1]－＝m　②j＝data[i][1]　③b[j－data[i][1]].append(v)
解析　本題考查冒泡排序和桶的應用。(1)1號剩余5人，5號和2號剩余人數單獨分組后，再次剩余人數為2和3，因此圴不能加入到這些新分組中。3號剩余人數編碼為第8組，1號的剩余人數可以加入到該組。(2)①程序實現從后往前冒泡降序排序，因此第1次執行后，最左邊的數據最大。②第4趟排序后，lst[i][1]的值為0，執行break語句，結束排序。(3)①每m人分配到一個新建小組中，不足m人的剩余員工暫不分配。新建一個分組后，該組內的人數將減少m個。②新一個大小為m列表b表示各個分組的剩余人數，b[0]至b[m－1]的初值均為0。對每個單位的剩余員工人數降序排序，并遍歷n個單位，首先查找是否存在一個大于等于該單位剩余人數最小分組，其方法是用循環while j重難點1　構建鏈表建立索引關系
高中階段的數據結構不是討論如何使用數據結構，而是通過對數據集進行簡單的操作，理解和創建數據結構。能將有限制條件的、真實情境中的數據關系進行抽象，根據數據特點與求解要求，選擇適當的數據類型表示各種數據，并用合適的數據結構表達數據的邏輯關系。在已有數據集的基礎上，通過鏈接關系構造邏輯上先后遍歷順序，構建鏈表，將有層次非線性結構或二維數組轉換為一維數組，再遍歷一維數組，得到問題的解。當原始數據量大，且每個數據元素有多個數據項時，直接對進行復制會浪費大量空間和時間，可進行基于索引的引用，提高效率。
例題 有2組器件共n個，要用一臺檢測設備檢測。每個送檢器件的信息包含送達時間、檢測時長和優先級。優先級有m(1編寫程序模擬檢測過程，先合并2組器件的數據，然后計算所有器件的平均等待時長，其中每個器件等待時長為其開始檢測的時間與送達時間的時間差。(時間單位均為秒)
請回答下列問題：
(1)由題意可知，圖中器件A、B、C、D的檢測順序為A－C－D－B，A、C、D的等待時長分別為0、1、0，B的等待時長是　　　　。
(2)定義如下merge(lst1， lst2)函數，參數lst1和lst2的每個元素由送達時間、檢測時長和優先級3項構成，lst1和lst2均已按送達時間升序排列。函數功能是將lst2中的元素合并到lst1中，并將lst1按送達時間升序排列，函數返回lst1。
def merge(lst1， lst2)：
　 i ＝ len(lst1) － 1
　 j ＝ len(lst2) － 1
　 for t in range(len(lst2))：
　　 lst1.append([0， 0， 0]) #為lst1追加一個元素[0， 0， 0]
　 k ＝ len(lst1) － 1
　 while j >＝ 0：
　　 if i >＝ 0 and lst1[i][0] > lst2[j][0]：
　　　 lst1[k] ＝ lst1[i]
　　　 i －＝ 1
　　 else：
　　　 lst1[k] ＝ lst2[j]
　　　 j －＝ 1
　　 k －＝ 1
　 return lst1
①調用merge(lst1， lst2)函數，若lst1為[[0， 3， 2]，[1， 1， 2] ， [12， 2， 2]]，lst2為[[2， 1， 1] ， [4， 3，0] ， [11， 3， 2]]，則while語句中循環體的執行次數是　　　　。
②若函數中while 語句的條件“j >＝ 0”誤寫為“k>＝0”，會導致某些情況下無法得到符合函數功能的結果。調用merge(lst1， lst2)函數，下列4組數據中能測試出這一問題的是　　　　(單選，填字母)。
A.lst1 ＝ [[0，3，2]，[4，3，0]] lst2 ＝ [[1，1，2]]
B.lst1 ＝ [[1，1，2]] lst2 ＝ [[0，3，2]，[4，3，0]]
C.lst1 ＝ [[1，1，2]，[4，3，0]] lst2 ＝ [[0，3，2]]
D.lst1 ＝ [[4，3，0]] lst2 ＝ [[0，3，2]，[1，1，2]]
(3)實現模擬檢測過程并計算平均等待時長的部分Python程序如下，請在劃線處填入合適的代碼。
def proc(data， m)：
　 n ＝ len(data)
　 queinfo ＝ []
　 for i in range(m)：
　 queinfo.append([－1， －1])　#queinfo追加一個元素[－1，－1]
　 for i in range(n)：
　 data[i].append(－1)　#data[i]追加一個元素－1
　 curtime ＝ 0
　 waitnum ＝ 0
　 i ＝ 0
　 ①　　　　
　 while i < n or waitnum > 0：
　　 if i < n and data[i][0] <＝ curtime：
　　　 k ＝ data[i][2]
　　　 if queinfo[k][0] ＝＝ －1：
　　　　　 queinfo[k][0] ＝ i
　　　 else：
　　　　　 ②　　　　
　　　　　 data[p][3] ＝ i
　　　 queinfo[k][1] ＝ i
　　　 waitnum ＋＝ 1
　　　 i ＋＝ 1
　　 elif waitnum > 0：
　　　 k ＝ 0
　　　 while queinfo[k][0] ＝＝ －1：
　　　　　 k ＋＝ 1
　　　 p ＝ queinfo[k][0]
　　　 total ＋＝ curtime － data[p][0]
　　　 curtime ＋＝ data[p][1]
　　　 ③　　　　
　　　 waitnum －＝ 1
　 else：
　　　 curtime ＝ data[i][0]
　return total / n
'''
讀取2組器件的數據，分別存入列表data1和data2中。2個列表的每個元素包含3個數據項，分別對應器件的送達時間、檢測時長和優先級。data1 和data2中的數據已分別按送達時間升序排列，代碼略
讀取優先級等級個數存入m，代碼略
'''
data ＝ merge(data1， data2)
print(proc(data， m))
思維點撥
明考向 本題考查鏈表節點元素的構建
精點撥 ((1)A在處理時，B和C在等待，A在時刻3處結束，B和C等待了2秒和1秒，C的優先級比B的優先級高，C先處理，從時刻2到達，在時刻4結束。D在時刻4到達，優先級比B高，D先處理，在時刻7結束，因此B在7時刻開始處理，每個器件等待時長為其開始檢測的時間與送達時間的時間差，因此B的等待時長為7－1＝6。(2)①先在lst1后添加len(lst2)個數據元素，從兩個列表的后面開始，將lst2歸并到lst1中。依次歸并[12，2，2]、[11，3，2]、[4，3，0]、[2，1，1]，j的值小于0，結束歸并，共循環4次。②若函數中while 語句的條件“j >＝ 0”誤寫為“k>＝0”，j是指向lst2的指針，則當lst2中的數據已經處理完時，會出問題，因此答案選A。(3)①總時間的變量total，通過total ＋＝ curtime － data[p][0]累計total值，設置初始值為0。解決問題的方式采用鏈表實現的隊列，即鏈式隊列，二維列表queinfo就用來存儲每個優先級的頭尾指針。data追加一個元素－1用來存儲下一個處理的指針，存儲鏈表信息。②若該等級已存在其他器件，由于器件是按時間升序遍歷。因此將該器件添加到k等級鏈表表尾。通過訪問k等級虛點對應的鏈表表尾，找到表尾位置p(p＝queinfo[k][1])，然后在鏈表表尾追加當前器件的索引位置i，完成待處理器件的入隊操作。③在k等級鏈表中，找到最高k等級單鏈表指向的位置p，p為單鏈表中隊首器件位置。此處是將p指向的器件刪除，通過更新k等級鏈表表頭queinfo[k][0]，使鏈表表頭指向p的下一個器件位置，完成刪除操作
答案　(1)6　(2)①4　②A　(3)①total ＝ 0　②p ＝ queinfo[k][1]　③queinfo[k][0] ＝ data[p][3]
變式 某工程包含n個任務(編號為0～n－1)，每天可以有多個任務同時進行。某些任務之間有依賴關系，如圖a所示，任務4依賴于任務1，任務1依賴于任務2。即任務2完成后才可以開始任務1，任務1完成后才可以開始任務4。不存在一個任務依賴于多個任務，或多個任務依賴于同一個任務的情況。現已對該工程的依賴關系進行了梳理，結果如圖b所示，標記“T”表示依賴關系需保留，標記“F”表示依賴關系需刪除。
根據每個任務完成所需的天數和梳理后的依賴關系，編寫程序，首先刪除標記為“F”的依賴關系，然后計算工程最快完成所需的天數，并以工程最快完成所需的天數為期限，計算每個任務最晚必須開始的時間。
圖a
任務A 任務B 標記
0 5 T
5 4 F
4 1 T
1 2 T
2 3 F
注：任務a依賴于任務b。
圖b
請回答下列問題：
(1)若某工程有6個任務，任務間依賴關系如圖a所示，完成任務0～5所需天數分別為2，1，3，5，1，6，則工程最快完成需要　　　　天。
(2)定義如下erase(lst)函數，參數lst列表的每個元素表示一個依賴關系。函數的功能是刪除標記為“F”的依賴關系，返回保留的依賴關系的個數。
def erase(lst)：
　 i＝0
　 j ＝ len(lst)－1
　 while i<＝ j：
　 if lst[i][2]＝＝ 'T'：
　　　 i＋＝1
　 else：
　　　 if lst[j][2] ＝＝ 'T'：
　　　 lst[i]＝lst[j]
　　　　 i ＋ ＝ 1
　　　 j － ＝ 1
return i
若lst列表依次存儲圖b所示的依賴關系，如lst[0]為[0，5，'T']，調用erase(Ist)的數，則語句“lst[i] ＝lst[j]”的執行次數為　　　　。
(3)實現上述功能的部分Python程序如下，請在劃線處填入合適的代碼。
def proc(n，lst，task)：
　 pr＝[0]*n
　 w＝[0]*n　#w[i]存放任務1最晚必須開始的時間
　 m＝erase(lst)
　 for i in ①　　　　：
　　 task[lst[i][1]][1]＝lst[i][0]
　　 pr[lst[i][0]]＝1
　 c＝[]
　 days＝0　#days存放工程最快完成所需的天數
　 for i in range(n)：
　 if pr[i]＝＝0：
　　　 k＝i
　　　 s＝0
　　　 while k！＝－1：
　　　　　　 c.append(k)
　　　　　　 s＋＝task[k][0]
　　　　　　 ②　　　　
　　　 if s>days：
　　　　　　 days＝s
　　for i in range(n－1，－1，－1)：
　　 k＝c[i]
　　 if task[k][1]＝＝－1：
　　　　 w[k]＝days－task[k][0]＋1
　　 else：
　　　 ③　　　　
　　　#輸出days，以及保存在w中的每個任務最晚必須開始的時間，代碼略
'''
工程包含的任務數存入變量n
任務間的依賴關系存入1st列表
1st[0]包含3項，任務1st[i][0]依賴于任務1st[i][1]，1st[i][2]存放保留/刪除標記，任務數據存入task列表
task[i]包含2項，task[i][0]為完成任務所需天數，task[i][1]的初值為－1
代碼略
'''
proc(n，lst，task)
答案　(1)8　(2)1　(3) ①range(m)或range(0，m)或range(0，m，1)或range(m－1，－1，－1)或range(erase(lst))或range(0，erase(lst))或range(0，erase(lst)，1)或range(erase(lst) －1，－1，－1)　②k＝task[k][1]　③w[k]＝w[task[k][1]]－task[k][0]或w[k]＝w[c[i＋1]]－task[k][0]
解析　本題考查數組的遍歷、鏈表的遍歷、創建等操作。(1)任務5和任務0有依賴關系，完成天數為8天，任務4、1、2有依賴關系，完成天數為5天，任務3需5天，存在3條鏈表，每天可以有多個任務同時進行，因此取最長鏈表所花時間，至少需要8天。(2)變量i和j分別指向數組lst的頭尾元素位置，從頭元素開始遍歷，若遍歷的元素lst[i][2]不是'T'，將尾元素為'T'的元素覆蓋當前元素，并將變量j向前移動。在圖b中，當i值為1時，標記為F，由于尾元素也不是T，因此僅僅變量j向前移動，變量i并未增加，再次遍歷時，將一條為T的元素覆蓋，因此該語句只執行了一次。(3)①首先刪除標記為“F”的依賴關系，從圖中可以看出，任務a依賴于任務b，任務b完成后才可以開始任務a，任務b的后繼是任務a，因此語句task[lst[i][1]][1]＝lst[i][0]的作用是創建鏈表，并將不是頭節點的元素用pr數組標記為1。變量m調用函數返回保留的依賴關系的個數，因此需對有依賴關系的記錄進行標記。②遍歷每一個任務，當條件pr[i]＝＝0成立時，表示當前任務是某條鏈表的頭節點，并開始遍歷該條鏈表，將節點添加到列表c中，并統計該條鏈表所需天數s。當前節點完成遍歷后，要到下一節點。③以工程最快完成所需的天數為期限，計算每個任務最晚必須開始時間，如圖a中，工程最快完成所需的8天，任務5最遲在第1天完成，任務5完成在第6天，任務0則完成時間在第7、8兩天，因此最遲在第7天開始。當條件task[k][1] ＝＝－1 成立時，表示任務k是任務鏈的尾節點，至少應該從倒數第task[k][0]天開始，或者順數第days－task[k][0]＋1開始；若任務 k不是尾節點，該任務必須在其后續任務完成前開始，開始時間為后續任務的最晚開始時間減去當前任務完成時間。
重難點2　構建數組存儲臨時數據
針對情境較為復雜、結構化程度較低的問題，能抽象數據特征、創造性地運用數據結構優化算法。數據往往經過采集、傳輸、處理和存儲的過程，而數據在加工處理過程中，要考慮算法的優越性，提高算法的效率。數據在加工過程中，臨時存放的數據可以存儲在隊列、棧和二維數組中，利用其不用查找就可以操作或者把當前正在處理的數據放置一個較小的數組中的特性，加快數據的處理時間。
例題 某店使用加工設備制作m種類型的甜品，每分鐘只能制作一種類型，且不超過n個。每個訂單包含訂單編號、下單時間、類型和數量。編排制作順序的規則為：下單時間早的類型優先，下單時間相同時數量多的類型優先。下單時間最早的訂單數量不足n，可以先制作部分已下單相同類型甜品。每分鐘完成后，有新增訂單時，合并相同類型訂單，按上述規則重新編排順序，若編排后，新訂單仍有剩余，則剩余數量按實際下單時間繼續參與編排。
設m為3，n為10，某時段各個訂單如圖a所示，則制作甜品的順序為AABACB，數量為10、10、10、4、8、5，如圖b所示。編寫Python程序，根據訂單，輸出甜品的制作順序和數量。
訂單編號 下單時間 類型 數量
0406001 8：01 A 24
0406002 8：01 B 3
0406003 8：03 C 8
0406004 8：03 B 12
圖a
圖b
(1)如圖a所示，若訂單0406003提前到8：01下單，則制作順序為　　　　。
(2)定義如下least(tpr，ud，m)函數，參數tpr存儲當前各類甜品的下單時間，如tpr＝[[481，482]，[]，[]]表示當前A類型有8：01(將字符串時間格式8：01轉換為分鐘數字481)和8：02共2個訂單，B和C無訂單。參數ud存儲當前各個類型的訂單數量之和，如ud＝[4，0，0]表示當前A類型所有訂單數量和為4，B和C無訂單。參數m表示甜品種類。函數功能是查找當前待制作甜品的類型。
def least(tpr，ud，m)：
　 post＝0
　 for i in range(1，m)：
　 if len(tpr[i])>0：
　　　　 if
：
　　　　　　post＝i
　　　　elif tpr[i][0]＝＝tpr[post][0]：
　　　　　　if ud[i]>ud[post]：
　　　　　　　 post＝i
　　　return post
若加框處條件誤寫為“tpr[i][0]A.tpr＝[[481]，[481]，[482，483]]
ud＝[2，25，5]
B.tpr＝[[]，[482]，[482，483]]
ud＝[0，3，2]
C.tpr＝[[481，485]，[]，[482，483]]
ud＝[2，0，5]
D.tpr＝[[481，485]，[]，[]]
ud＝[2，0，0]
(3)實現上述功能的部分Python程序如下，程序中用到的列表函數與方法如下表所示，請在劃線處填入合適的代碼。
函數與方法 功能
w.append(x) 在列表w末尾添加元素x
w.pop(i) 刪除列表w索引為i的元素
sum(w) 累加列表w中的元素
#讀取各個訂單的數據，存入列表lst，每個元素包含訂單編號、下單時間、類型和數量。lst中的數據已按下單時間升序排列，代碼略。
#讀取甜品種類和每分鐘最多加工的數量，分別存入變量m和n，代碼略。
def convert(s)：
　 #將字符串格式時間s轉換成分鐘數，如convert(″08：00″)的值為480，代碼略。
tpr＝[[]for i in range(m)]
npr＝[[]for i in range(m)]
ud＝[0 for i in range(m)]
curtime＝convert(lst[0][1])　#當前時間為第1個訂單的下單時間
i＝0
while i 0：
　　while i　 t＝ord(lst[i][2])－ord(″A″)
　 tpr[t].append(convert(lst[i][1]))
　 npr[t].append(lst[i][3])
　 ①　　　　
　 i＋＝1
　　k＝least(tpr，ud，m)
　　tot＝0　　
　　while　ud[k]>0 and tot　 if 　 ②　 ：
　　　 ud[k]－＝npr[k][0]
　　　 tot＋＝npr[k][0]
　　　 tpr[k].pop(0)
　　　 npr[k].pop(0)
　 else：
　　　 npr[k][0]－＝n－tot
　　　 ud[k]－＝n－tot
　　　 tot＝n
　　　 #輸出當前時間加工的甜品類型及數量，代碼略
　　　 curtime＋＝1
　　　 if i　 ③　　　　
思維點撥
明考向 本題考查隊列和二維數組的應用
精點撥 (1)8：01有A，B，C共3種類型的訂單，數量分別為24，3，8。前2分鐘制作A類型甜品，完成后A，B，C數量分別為4，3，8，8：03時B類型訂單有12，可以提前完成7個甜品，接下來制作B，C類型甜品，剩余A，B類型的數量分別為4和5，由于B類型下單時間為8：03，因此最后制作B類型甜品。(2)本題考查順序查找，post的初值為0，變量i從1開始遍歷，B選項中初值為空，因此tpr[post][0]的值為空，程序會報錯。(3)①變量t為類型的編號，該訂單數量u[t]數量增加lst[i][3]。②調用自定義函數least求當前制作訂單編號k，語句tpr[k].pop(0)的功能是彈出訂單k，表示該訂單已完成，因此該訂單數量須滿足小于等于n－tot。③若當前時間小于新訂單到來時間，須更新當前時間為新訂單的到來時間
答案　(1)AABCAB　(2)B　(3)①ud[t]＋＝lst[i][3]
②npr[k][0]<＝n－tot
③curtime＝convert(lst[i][1])
變式 有新訂單產生。公司安排的打包工作時間為12：00－18：00，假設當日訂單在工作時間內就能完成。公司有甲、乙、丙三位師傅對貨品進行打包，貨品按照甲、乙、丙的順序分配給各師傅處理，每位師傅一次打包一件貨品。打包規則：若下單時間相同，優先級越高(數字越小，優先級越高)的貨品，先全部打包完成；若不同，則下單時間更早的貨品先處理完成。
訂單輸入格式示例：7A2B、4B10A(說明：4B10A指訂單中有4件B類貨品，10件A類貨品)。編寫程序，輸出某天甲、乙、丙貨品打包順序和打包報酬，甲的輸出示例：3A5B1C，200元。
貨品 優先級 打包報酬(元/件)
A 1 30
B 2 20
C 3 10
表1
下單時間 貨品及數量
12：00 2B7A
14：00 7B
15：00 6B5C
表2
(1)若某天貨品下單信息如表2所示，則甲的打包順序為3A5B1C，乙的打包報酬為　　　　元。
(2)定義如下convert(data)函數，參數data為一個訂單，包括貨品和數量，函數功能將訂單轉換成貨品名稱序列，如訂單2B1A1C轉換成ABBC。請在劃線處填上合適的代碼。
def convert(data)：
　 num，q ＝ 0，″″
　 qsort ＝ [″″，″″，″″]
　 for i in range(len(data))：
　 if data[i] >＝″0″ and data[i] <″9″：
　　　 num ＝ 　　　　
　 else：
　　　 for j in range(num)：
　　　　　 q ＋＝ data[i]
　　　 qsort[ord(data[i])－ord(″A″)] ＝ q
　　　 num，q ＝ 0，″″
　　　s ＝ qsort[0]＋qsort[1]＋qsort[2]
　　　return s
(3)實現該功能的 Python 主程序如下，請在劃線處填入合適的代碼。
goods ＝ [30， 20， 10]
m ＝ (18－12)*2　#12：00－18：00之間每半個小時為一個時間節點
b ＝ [ ]
for i in range(m)：
　 b.append(″″)　#append()用于在列表的末尾添加一個元素
a ＝ [[″12：00″，″2B7A″][″14：00″，″7B″]，[″15：00″，″6B3C″]]
for i in range(len(a))：
　 que ＝ convert(①　　　　)
　 x ＝ (int(a[i][0][0：2])－12)*2　#將時間轉換為對應的結點
　 while len(b[x]) ＝＝ 3：
　　　 x ＝ x＋1
　 while len(que) > 0：
　　 t ＝ 3－len(b[x])
　　 if len(que) < t：
　　　 t ＝ len(que)
　　 b[x] ＝ ②　　　　
　　 if t ＝＝ len(que)：
　　　 que＝″″
　　 else：
　　　 que ＝ que[t：]
　　 x ＋＝ 1
s1， salary ＝″″， 0
for i in range(m)：　#甲處理順序和打包報酬輸出
　 if b[i] ！＝″″：
　　 s1 ＋＝ b[i][0]
　　 salary ＋＝③　　　　
#將s1中形如“ABBCC”的格式，轉換成“1A2B2C”的格式，代碼略
print(″甲處理順序和打包報酬：″， s1， str(salary)＋″元″)
#乙、丙處理(共159張PPT)
第一部分　信息與信息系統
專題18　基于數據結構的算法實現
1.掌握隊列中元素入隊和出隊的條件；
2.掌握鏈表的構建方法.
目 錄
CONTENTS
體系構建
01
真題再現
02
考點精練
03
當堂檢測
04
課后練習
05
體系構建
1
隊列是線性結構的一種，因此也可以用鏈式結構的方式來實現。并且鏈式結構的隊列，由于節點空間都是在入隊的時候動態申請的 ，因此在計算機內存空間足夠的情況下，一般不需要考慮隊滿的情況，也就不存在溢出的情況，所以不需要使用循環鏈式隊列來處理假溢出的情況。 鏈式隊列在鏈表的鏈尾插入元素，然后讓隊尾指針指向鏈尾元素。鏈式隊列的出隊，就是將鏈表的首元節點從鏈表中刪去，讓其后繼節點成為首元節點，然后讓隊頭指針指向該節點。
真題再現
2
(2024年1月浙江省選考)某項活動有n個單位(編號1到n)參加，需將員工分成若干個小組，每個小組的人數上限為m，小組編號按新建次序從1開始編號。分組時，首先按單位編號次序依次在各單位內部分分組，每m人分配到一個新建小組中，不足m人的剩余員工暫不分配；然后按剩余員工人數由大到小的順序，依次為各單位剩余員工分配小組。
若某單位剩余員工人數為k，則分配方法為：在已建的小組中查找空位數(該小組還可容納的人數)大于或等于k的小組，如果找到的小組有多個，則選擇空位數最少的小組，將此k人分配到該小組中；如果沒有找到，則新建一個小組，將此k人分配到該小組中。
設n為5，m為20，各單位員工人數及單位內部的分組過程如圖a所示，各單位剩余員工的分組過程如圖b所示。
編寫程序：給定各單位編號及員工人數，根據上述方法進行分組處理，按單位編號次序輸出各單位所分配的分組編號。請回答下列問題：
(1)由題意可知，若僅將圖a中1號單位的員工人數修改為25，然后對圖中5個單位重新分組，則1號單位所分配的分組編號為________。
(2)定義如下bubble_sort(lst)函數，參數lst的每個元素由單位編號和剩余員工人數2個數據項組成。函數的功能是根據每個單位的剩余員工人數，對lst進行降序排序。
　 return
調用該函數，若lst為[[1，0]，[2，0]，[3，18]，[4，0]，[5，19]，[6，17]]，請回答①和②兩個問題。
①虛線框中的程序段第1次執行后，關于lst中的剩余員工人數，下列說法正確的是________(單選，填字母)。
A.lst[0][1]數值最小 B.lst[0][1]數值最大
C.lst[5][1]數值最小 D.lst[5][1]數值最大
②虛線框中的程序段執行的次數為________。
(3)實現分組功能的部分Python程序如下，程序中用到的列表函數與方法如圖c所示，請在程序中劃線處填入合適的代碼。
函數與方法 功能
w.append(x) 在列表w末尾添加元素x
x＝w.pop() 將列表w末尾元素賦值給x，并將其從w中刪除
圖c
讀取小組人數上限存入 m；讀取 1 至 n 號單位的數據，依次存入列表 data 的 data[0]至 data[n－1]中。data[i]包含 2 個數據項，data[i][0]，data[i][1]分別存放單位編號及員工人數，代碼略
'''
group(data, m)
答案　(1)1，8　(2)①B　②4次　(3)①data[i][1]－＝m　②j＝data[i][1]　
③b[j－data[i][1]].append(v)
解析　本題考查冒泡排序和桶的應用。(1)1號剩余5人，5號和2號剩余人數單獨分組后，再次剩余人數為2和3，因此圴不能加入到這些新分組中。3號剩余人數編碼為第8組，1號的剩余人數可以加入到該組。(2)①程序實現從后往前冒泡降序排序，因此第1次執行后，最左邊的數據最大。②第4趟排序后，lst[i][1]的值為0，執行break語句，結束排序。(3)①每m人分配到一個新建小組中，不足m人的剩余員工暫不分配。新建一個分組后，該組內的人數將減少m個。②新一個大小為m列表b表示各個分組的剩余人數，b[0]至b[m－1]的初值均為0。對每個單位的剩余員工人數降序排序，并遍歷n個單位，首先查找是否存在一個大于等于該單位剩余人數最小分組，其方法是用循環while j考點精練
3
重難點1　構建鏈表建立索引關系
高中階段的數據結構不是討論如何使用數據結構，而是通過對數據集進行簡單的操作，理解和創建數據結構。能將有限制條件的、真實情境中的數據關系進行抽象，根據數據特點與求解要求，選擇適當的數據類型表示各種數據，并用合適的數據結構表達數據的邏輯關系。在已有數據集的基礎上，通過鏈接關系構造邏輯上先后遍歷順序，構建鏈表，將有層次非線性結構或二維數組轉換為一維數組，再遍歷一維數組，得到問題的解。當原始數據量大，且每個數據元素有多個數據項時，直接對進行復制會浪費大量空間和時間，可進行基于索引的引用，提高效率。
例題 有2組器件共n個，要用一臺檢測設備檢測。每個送檢器件的信息包含送達時間、檢測時長和優先級。優先級有m(1編寫程序模擬檢測過程，先合并2組器件的數據，然后計算所有器件的平均等待時長，其中每個器件等待時長為其開始檢測的時間與送達時間的時間差。(時間單位均為秒)
請回答下列問題：
(1)由題意可知，圖中器件A、B、C、D的檢測順序為A－C－D－B，A、C、D的等待時長分別為0、1、0，B的等待時長是　　　　。
(2)定義如下merge(lst1， lst2)函數，參數lst1和lst2的每個元素由送達時間、檢測時長和優先級3項構成，lst1和lst2均已按送達時間升序排列。函數功能是將lst2中的元素合并到lst1中，并將lst1按送達時間升序排列，函數返回lst1。
思維點撥
明考向 本題考查鏈表節點元素的構建
精點撥 (1)A在處理時，B和C在等待，A在時刻3處結束，B和C等待了2秒和1秒，C的優先級比B的優先級高，C先處理，從時刻2到達，在時刻4結束。D在時刻4到達，優先級比B高，D先處理，在時刻7結束，因此B在7時刻開始處理，每個器件等待時長為其開始檢測的時間與送達時間的時間差，因此B的等待時長為7－1＝6。(2)①先在lst1后添加len(lst2)個數據元素，從兩個列表的后面開始，將lst2歸并到lst1中。依次歸并[12，2，2]、[11，3，2]、[4，3，0]、
思維點撥
明考向 本題考查鏈表節點元素的構建
精點撥 [2，1，1]，j的值小于0，結束歸并，共循環4次。②若函數中while 語句的條件“j >＝ 0”誤寫為“k>＝0”，j是指向lst2的指針，則當lst2中的數據已經處理完時，會出問題，因此答案選A。(3)①總時間的變量total，通過total ＋＝ curtime － data[p][0]累計total值，設置初始值為0。解決問題的方式采用鏈表實現的隊列，即鏈式隊列，二維列表queinfo就用來存儲每個優先級的頭尾指針。data追加一個元素－1用來存儲下一個處理的指針，存儲鏈表信息。②若該等級已存在其他器件，由于器件是按時間升序遍歷。因此將該器件添加到k等級鏈表表尾。通過訪問k等級虛點對應的鏈表表尾，找到表尾位置p(p＝queinfo[k][1])，然后在鏈表表尾追加當前器件的索引位置i，完成待處理器件的入隊操作。③在k等級鏈表中，找到最高k等級單鏈表指向的位置p，p為單鏈表中隊首器件位置。此處是將p指向的器件刪除，通過更新k等級鏈表表頭queinfo[k][0]，使鏈表表頭指向p的下一個器件位置，完成刪除操作
答案　(1)6　(2)①4　②A　(3)①total ＝ 0　②p ＝ queinfo[k][1]　③queinfo[k][0] ＝ data[p][3]
變式 某工程包含n個任務(編號為0～n－1)，每天可以有多個任務同時進行。某些任務之間有依賴關系，如圖a所示，任務4依賴于任務1，任務1依賴于任務2。即任務2完成后才可以開始任務1，任務1完成后才可以開始任務4。不存在一個任務依賴于多個任務，或多個任務依賴于同一個任務的情況。現已對該工程的依賴關系進行了梳理，結果如圖b所示，標記“T”表示依賴關系需保留，標記“F”表示依賴關系需刪除。
根據每個任務完成所需的天數和梳理后的依賴關系，編寫程序，首先刪除標記為“F”的依賴關系，然后計算工程最快完成所需的天數，并以工程最快完成所需的天數為期限，計算每個任務最晚必須開始的時間。
圖a
任務A 任務B 標記
0 5 T
5 4 F
4 1 T
1 2 T
2 3 F
圖b
注：任務a依賴于任務b。
答案　(1)8　(2)1　(3) ①range(m)或range(0，m)或range(0，m，1)或range(m－1，－1，－1)或range(erase(lst))或range(0，erase(lst))或range(0，erase(lst)，1)或range(erase(lst) －1，－1，－1)　②k＝task[k][1]　③w[k]＝w[task[k][1]]－task[k][0]或w[k]＝w[c[i＋1]]－task[k][0]
解析　本題考查數組的遍歷、鏈表的遍歷、創建等操作。(1)任務5和任務0有依賴關系，完成天數為8天，任務4、1、2有依賴關系，完成天數為5天，任務3需5天，存在3條鏈表，每天可以有多個任務同時進行，因此取最長鏈表所花時間，至少需要8天。(2)變量i和j分別指向數組lst的頭尾元素位置，從頭元素開始遍歷，若遍歷的元素lst[i][2]不是'T'，將尾元素為'T'的元素覆蓋當前元素，并將變量j向前移動。在圖b中，當i值為1時，標記為F，由于尾元素也不是T，因此僅僅變量j向前移動，變量i并未增加，再次遍歷時，將一條為T的元素覆蓋，因此該語句只執行了一次。(3)①首先刪除標記為“F”的依賴關系，從圖中可以看出，任務a依賴于任務b，任務b完成后才可以開始任務a，任務b的后繼是任務a，因此語句task[lst[i][1]][1]＝lst[i][0]的作用是創建鏈表，并將不是頭節點的元素用pr數組標
記為1。變量m調用函數返回保留的依賴關系的個數，因此需對有依賴關系的記錄進行標記。②遍歷每一個任務，當條件pr[i]＝＝0成立時，表示當前任務是某條鏈表的頭節點，并開始遍歷該條鏈表，將節點添加到列表c中，并統計該條鏈表所需天數s。當前節點完成遍歷后，要到下一節點。③以工程最快完成所需的天數為期限，計算每個任務最晚必須開始時間，如圖a中，工程最快完成所需的8天，任務5最遲在第1天完成，任務5完成在第6天，任務0則完成時間在第7、8兩天，因此最遲在第7天開始。當條件task[k][1] ＝＝－1 成立時，表示任務k是任務鏈的尾節點，至少應該從倒數第task[k][0]天開始，或者順數第days－task[k][0]＋1開始；若任務 k不是尾節點，該任務必須在其后續任務完成前開始，開始時間為后續任務的最晚開始時間減去當前任務完成時間。
重難點2　構建數組存儲臨時數據
針對情境較為復雜、結構化程度較低的問題，能抽象數據特征、創造性地運用數據結構優化算法。數據往往經過采集、傳輸、處理和存儲的過程，而數據在加工處理過程中，要考慮算法的優越性，提高算法的效率。數據在加工過程中，臨時存放的數據可以存儲在隊列、棧和二維數組中，利用其不用查找就可以操作或者把當前正在處理的數據放置一個較小的數組中的特性，加快數據的處理時間。
例題 某店使用加工設備制作m種類型的甜品，每分鐘只能制作一種類型，且不超過n個。每個訂單包含訂單編號、下單時間、類型和數量。編排制作順序的規則為：下單時間早的類型優先，下單時間相同時數量多的類型優先。下單時間最早的訂單數量不足n，可以先制作部分已下單相同類型甜品。每分鐘完成后，有新增訂單時，合并相同類型訂單，按上述規則重新編排順序，若編排后，新訂單仍有剩余，則剩余數量按實際下單時間繼續參與編排。
設m為3，n為10，某時段各個訂單如圖a所示，則制作甜品的順序為AABACB，數量為10、10、10、4、8、5，如圖b所示。編寫Python程序，根據訂單，輸出甜品的制作順序和數量。
訂單編號 下單時間 類型 數量
0406001 8：01 A 24
0406002 8：01 B 3
0406003 8：03 C 8
0406004 8：03 B 12
圖a
圖b
(1)如圖a所示，若訂單0406003提前到8：01下單，則制作順序為　　　　。
(3)實現上述功能的部分Python程序如下，程序中用到的列表函數與方法如下表所示，請在劃線處填入合適的代碼。
函數與方法 功能
w.append(x) 在列表w末尾添加元素x
w.pop(i) 刪除列表w索引為i的元素
sum(w) 累加列表w中的元素
思維點撥
明考向 本題考查隊列和二維數組的應用
精點撥 (1)8：01有A，B，C共3種類型的訂單，數量分別為24，3，8。前2分鐘制作A類型甜品，完成后A，B，C數量分別為4，3，8，8：03時B類型訂單有12，可以提前完成7個甜品，接下來制作B，C類型甜品，剩余A，B類型的數量分別為4和5，由于B類型下單時間為8：03，因此最后制作B類型甜品。(2)本題考查順序查找，post的初值為0，變量i從1開始遍歷，B選項中初值為空，因此tpr[post][0]的值為空，程序會報錯。(3)①變量t為類型的編號，該訂單數量u[t]數量增加lst[i][3]。②調用自定義函數least求當前制作訂單編號k，語句tpr[k].pop(0)的功能是彈出訂單k，表示該訂單已完成，因此該訂單數量須滿足小于等于n－tot。③若當前時間小于新訂單到來時間，須更新當前時間為新訂單的到來時間
答案　(1)AABCAB　(2)B　(3)①ud[t]＋＝lst[i][3]
②npr[k][0]<＝n－tot
③curtime＝convert(lst[i][1])
變式 有新訂單產生。公司安排的打包工作時間為12：00－18：00，假設當日訂單在工作時間內就能完成。公司有甲、乙、丙三位師傅對貨品進行打包，貨品按照甲、乙、丙的順序分配給各師傅處理，每位師傅一次打包一件貨品。打包規則：若下單時間相同，優先級越高(數字越小，優先級越高)的貨品，先全部打包完成；若不同，則下單時間更早的貨品先處理完成。
訂單輸入格式示例：7A2B、4B10A(說明：4B10A指訂單中有4件B類貨品，10件A類貨品)。編寫程序，輸出某天甲、乙、丙貨品打包順序和打包報酬，甲的輸出示例：3A5B1C，200元。
貨品 優先級 打包報酬(元/件)
A 1 30
B 2 20
C 3 10
表1
下單時間 貨品及數量
12：00 2B7A
14：00 7B
15：00 6B5C
表2
(1)若某天貨品下單信息如表2所示，則甲的打包順序為3A5B1C，乙的打包報酬為　　　　元。
答案　(1)180　(2)num*10＋int(data[i])(3)①a[i][1]　②b[x]＋que[0：t]　
③goods[ord(b[i][0])－ord(″A″)]或goods[ord(b[i][0])－65]
解析　(1)12：00下單的貨品需1.5個小時，在下一個時間點之前能處理完，因此甲乙丙分別處理3A、2A1B、2A1B，后面2個單子可以合并處理，甲乙丙分別處理5B1C、4B2C、4B2C。(2)取出訂單data貨品的數量，當數量的值大于9時，如字符串“192”轉換成數字192時，依次表示為0＋1，10＋9，190＋2。(3)①遍歷若干個訂單數據，采用convert(data)函數將參數data訂單(如2B1A1C)轉換成ABBC的形式。②將當前訂單寫入隊列que中，先找到處理的時間節點x。變量m為每半個小時為一個時間節點數量，b列表記錄每個結點甲乙丙打包的貨品。當b列表長度為3時，表示每個人都有工作，接下來的貨品將在下一個節點完成。若貨品序列沒放完則需要繼續按照時間節點放置，t 表示當前第 x 個時間節點還可以存放貨品的個數，將新放入的貨品從序列中切出來累加到當前結點 b[x]中去。③在列表中找出對應貨品的打包報酬累加到總報酬中。
當堂檢測
4
重難點1　構建鏈表建立索引關系
重難點2　構建數組存儲臨時數據
1.某花瓶廠有三臺不同型號的機器，可生產ABC三種不同型號的花瓶。廠家每天會收到很多網上訂單，每個客戶的訂單信息包含訂單號、型號、數量和狀態，其中狀態值為1表示確認訂單，－1表示取消訂單。工作人員首先挑選出確認的訂單，然后對訂單按花瓶型號進行分類統計，最后交給工作人員生產。訂單信息存儲在“orders.csv”文件中，文件數據格式如圖a所示。請回答下列問題。
圖a
訂單號 型號 數量 狀態
s001 A 1000 1
s002 B 2000 1
s003 B 1500 －1
s004 C 900 1
s005 B 800 1
s006 C 700 1
s007 A 500 －1
s008 B 600 1
圖b
(3)實現按花瓶型號分類統計花瓶數量的Python程序如下，程序運行結果如圖c所示。請在程序劃線處填入合適的代碼。
當天訂單信息為：
[['s001'，'B'，6000]，['s002'，'A'，9000]，['s003'，'C'，9500]，['s008'，'A'，5000]]
分類訂單統計結果為：
['s002'，'A'，9000]→['s005'，'A'，6200]→['s008'，'A'，5000]→共計20200個
['s001'，'B'，6000]→['s006'，'B'，3000]→共計9000個
['s003'，'C'，7000]→['s007'，'C'，9500]→共計16500個
圖c
答案　(1)3400　(2)line[1]　(3)①orders[p][3]＝I ②total＝total＋orders[y][2]或total＋＝orders[y][2]　③p＝p＋1或p＋＝1
解析　(1)當天應生產B型號花瓶數量為2000＋800＋600＝3400個。(2)readdata()函數的功能是過濾撤消的訂單，根據第4列的訂單狀態，從文件中讀取的前3列的數據，因此劃線處代碼為line[1]。(3)先根據訂單中的花瓶型號構建三張鏈表(tlist[0]、tlist[1]和tlist[2])，分別存儲不同型號花瓶的訂單信息，鏈表tlist[]只記錄首尾兩張訂單的索引號，中間的訂單信息則記錄在orders表示的鏈表中。要在鏈表中增加一個節點，可以通過tlist[i][1]直接找到鏈表尾節點，然后接在后面，并且更新tlist[i][1]作為新的鏈表尾節點，因此①處代碼為orders[p][3]＝i；然后統計每張鏈表中的花瓶數量，統計時，首先獲取當前鏈表中第一張訂單的索引號，然后按照鏈表順序將各訂單的花瓶數量累加，從而求出各種型號花瓶的總數量，因此②處代碼為total＝total＋orders[y][2]，接下去對存儲另外型號花瓶的鏈表進行處理，因此③處代碼為p＝p＋1或p＋＝1。
2.張三是一名計算機專業的大學生，為了幫助同學們學習專業相關的英語詞匯，編寫一個簡易字典程序。該程序中存放詞匯數據庫，在學習中輸入英文單詞，可以獲得中文翻譯結果。程序中的詞匯數據庫采用鏈表方式存儲，首字母相同時按升序排序。查找單詞時，首先根據首字母找到同首字母最小單詞所在鏈表，再按照鏈表順序查找該單詞。
(1)根據題意，部分的單詞庫數據邏輯結構如圖所示，查找單詞”byte”的過程是”binary”→”bit”→”byte”， 補充圖中空白單元格的值為　　　　。
列表索引 數據區域 指針區域
0 audio 音頻 －1
1 binary 二進制數 6
2 byte 字節 －1
3 cursor 光標 －1
4 access 存取 0
5 cache 高速緩存 3
6 bit 比特 　　　　
答案　(1)2　(2)①k ＝ ord(d[0]) － ord(″a″)　②q ！＝ －1 and d > data[q][0]　
③info[k] ＝ I (3)data[p][1]
解析　 本題考查鏈表的構建、遍歷和節點的插入。(1)采用鏈表方式存儲字母，首字母相同時按升序排序。單詞bit的下一個單詞為byte，因此其指針區域值為索引2。(2)①將單詞d首字母轉換為字母表中對應數字，info[0]表示字母 a 開頭的最小單詞，因此k為字母a－z對應0－25的索引號。②遍歷data鏈表，找到單詞d位置。當前節點q從頭節點開始，當q值不為－1，且滿足d比當前節點數據區域值大。(3)返回單詞key對應的中文。每個元素包含英文單詞和中文翻譯。
3.某外賣平臺推出同城代購服務，外賣騎手可接多個訂單，但是同一時間只能完成一項訂單。接單規則為：
·若騎手當前沒有訂單任務，則自動接收最先提交的訂單任務；
·若騎手在當前訂單完成前都沒有接到新的訂單，則輸出當前訂單，并接收排在最前面的訂單任務；
·若騎手當前正在執行訂單任務，期間有用戶提交訂單，則訂單進入等候區，并按照所需用時升序排列。
訂單信息存儲在“dingdan.txt”文件中，文件格式如圖a所示。文件按照下單時間升序存儲所有訂單信息，每一行數據存儲每個訂單的接收時間和完成訂單的所需用時，如
(“D1，07：15：36，2400”表示：D1號訂單，于07：15：36下單，需要2400秒才能完成)。
圖a
訂單名稱　 完成時間　
　D1　　　　07：55：36　
　D3　　　　09：05：36　
　D2　　　　10：35：36　
　D4　　　　11：32：02　
　D5　　　　14：37：30　
圖b
(1)如果某騎手一天內接到的訂單如表所示：
訂單號 接收時間 所需用時(秒)
D1 08：00：00 600
D2 08：05：00 1500
D3 08：30：00 1800
D4 08：33：00 900
D5 08：33：00 600
騎手在完成所有訂單后，各個訂單的完成順序為：　　　　(訂單號之間用逗號隔開，如D1，D2，D3，D4，D5)。
答案　(1)D1，D2，D5，D4，D3　(2)t＝t∥60
(3)①i(4)finish＝data[i][1]＋data[i][2]
解析　(1)D1在9：10完成，D2在9：35完成，D3、D4、D5在等候區，按時間小的先完成。(2)將數字的時間轉換為小時、分鐘和秒，t除以60的余數得到秒，整除60得到后的數，除以60的余數為分，整數為小時。(3)①遍歷完所有訂單，即訂單均完成或都進入等候區，還一種情況是有訂單還在等候區沒有完成，即所有訂單鏈表為空。②k表示當前節點，從頭節點的下一個節點開始遍歷。(4)該訂單的完成時間為訂單到達時間和所需時間之和。
4.某醫院為實現就診順序規則的相對公正，實行就診前“掛號＋簽到”模式，排隊規則如下：
1)初診患者簽到后，按掛號序號自小到大的順序排隊
2)復診患者按簽到順序，以“隔2插1”的規則排隊
3)年齡大于等于80歲的患者，可以優先就診
現系統根據簽到順序記錄了某天下午某科室掛號患者的信息如圖a所示，包括掛號序號、姓名、年齡、初診復診情況(0表示初診，1表示復診)。經系統處理后，輸出患者的就診順序如圖b所示，請回答問題。
(3)若列表a依次存儲圖c的患者信息，程序運行后，加框處的語句總共執行　　　　次。
答案　(1)沈*思　(2)①(a[p][2]>＝80 or a[p][0]解析　(1)復診患者按簽到順序，以“隔2插1”的規則排隊。(2)①不能插在80歲老人或比他號小的前面。②為方便處理，在列表前加入一個虛擬節點，即頭節點的后繼才是鏈表的第1個有效節點。③依次從a隊列出隊2個元素，再從b隊列出隊1個元素，因此left需加1。(3)由于a鏈表有一個虛擬的頭節點， 3個老人依次插入隊列，指針p的移動次數依次為0、1、2。
1.某單位有多個部門，部門編號0～n－1，人數不盡相同，如圖a所示。現舉行某項活動，需要將所有人重新分組。分組前按部門人數由少到多的順序(升序)排列，從人數最少的部門開始，按每m人一組劃分，最后一組若不足m人，則該組不參加活動轉做后勤。例如設定每組人數m＝7，各部門人數存于列表a中，a＝[3，4，2，1，6，4]，則分組情況如圖b所示。
答案　(1)0，5，4　(2)[3，1，2，0]　(3)①tot＝0　②tot>＝m　③gnum＋＝1
解析　(1)第1組為3號1人，1號2人，2號2人，0號2人。第2組0號1人，5號4人，4號2人。(2)p[i]數組用于統計比了a[i]小的數的個數。比5小的數有3個，比3小的數有1個，比4小的數有2個，比0小的數有0個，因此p的值為[3，1，2，0]。(3)①從語句tot ＋＝ a[b[i]]可以得出該處應對tot賦值為0。②先按人數進行升序排列，將各組的人數累加到tot中，并將組號添加到c[gnum]。若人數達到或超過m人，將新增一組，gnum表示組號。
2.設計一個簡單的快遞算法。有n位騎手為一個大型超市提供同城配送服務，假設每送完一單，騎手需回超市取貨。由于該超市的顧客有不同等級，因此騎手先送優先級高的訂單，若優先級相同，則先送距離近的訂單。編寫程序實現該算法，假設不考慮路況，忽略取貨、卸貨花費的時間并且每位騎手的平均速度相同，則可將距離轉換成單程配送時間(單位：分鐘)，優先級用數字表示，數字越小，優先級越高。請回答下列問題：
訂單號 優先級 單程配送時間
A 4 3
B 4 5
C 3 6
D 2 2
E 1 3
F 3 2
G 1 6
答案　(1)18　(2)①n－i－1或0，n－i－1或n－2，i－1，－1　②a[j][0]＝＝a[j＋1][0]anda[j][1]>a[j＋1][1]　(3)①rider[j]<＝nowtime或rider[j]＝＝nowtime　②nowtime＋data[i][1]或rider[j]－data[i][1]
解析　(1)先送優先級高的訂單，若優先級相同，則先送距離近的訂單。訂單順序為EGDFCAB，甲和乙先送訂單E和G，甲回到超市時間為6，接著送D，回到超市時間為10，接著送F。乙回到超市時間為12，接著送C，所需時間為6，顧客需要等待的時間為18。(2)冒泡排序一定是一端固定，可以從前往后冒泡，也可以從后往前冒泡。若從前往后冒泡，可以修改為n－i－1。若從后往前冒泡，應為n－2，i－1，－1。(3)①rider數組存儲每個騎手回到超市的時間點，nowtime表示當前時間，當前時間等于騎手回到超市時rider[j]，開始分配配送任務。②計算顧客等待時長為當前時間加上單程配送時間。由于已經更新騎手回到超市時間，也可以用騎手返回超市時間減去單程配送時間。
3.某驛站每個時刻(以秒計)都可能有一批商品到達，編寫Python程序，統計商品到達時，在過去一個小時內共有幾個地區(用兩個大寫字母表示)的商品以及商品的數量，并按商品數量從多到少顯示。部分商品按到達時刻到達信息以及統計結果如表所示。
時刻(秒) 商品所屬地區 各地區商品情況
1 SU KU KA KA KA SU SU KU 3　KA 3　SU 3　KU 2
3 SG KA SU SU 4　SU 5　KA 4　KU 2　SG 1
3601 KA KA SG 3　KA 3　SU 2　SG 2
3604 SG SG AU SG (略)
如上表所示，第1秒有8個商品達到，分屬于3個地區。第3秒的4個商品到達后，地區數量有4個，其中商品最多的是SU。第3601秒的3個商品到達后，由于只統計1小時內的數據，因此第1秒的商品不能計算在內，該時刻的商品地區數只有3個。
請回答以下問題。
(1)對于上表中第3604秒時刻，一共有　　　　個不同地區的商品(填數量)。
(2)主程序。小林用數組c保存各個地區的商品數量和它的排名位次，用數組rank保存地區序號和商品數量并用以排序。地區序號由大寫字母對應的序號轉換而來。實現程序如下，請將劃線處程序補充完整。
def toInt(s)：
答案　(1)3 (2)①t－q[head][0]>＝delta　②ans＋＝1
(3)①c[rank[i][1]][1]＋＝1或c[rank[0][1]][1]＝i＋1 ②rank[i＋1]＝[num，x]
解析　(1)在第3604秒，第3秒的商品不能計算在內，則第3601秒只有KASG，當第3604秒的商品達到后，增加了AU，所以一共有3個地區，答案填寫3。(2)列表c存儲地區的商品數量和名次，列表rank存儲商品數量和地區，列表q存儲所有地區和到達時間。①符合條件c[x][0]＝1(x地區商品減1)和head＋＝1(出隊列)時，q隊列中head指向的節點時刻與當前時刻t已經超過1小時了。②處理每個時刻到達的所有地區的數據，c[x][0]為1，說明x地區的貨物首次到達，從后面輸出該時刻的地區數量和各國商品數量可知，ans是當前時刻的總的地區數量，那么當x地區首次出現的時候，ans應該增加1。(3)用插入排序的方式來實現x地區在rank列表中的位置。①while條件成立時，x地區商品數量超過第i名地區的商品數量，將第i名地區數據在rank列表中后移一位，那么第i名地區的相應的名次數字也要增加1。②完成數據移動后，就要把x國的數據[商品數量，地區編碼]放到rank列表的合適位置，因while循環結束時num已經小于等于rank[i][0]，那么x國數據應放到rank的i＋1位置。
課后練習
5
重難點1　構建鏈表建立索引關系
重難點2　構建數組存儲臨時數據
1.使用Python編寫按文件后綴名進行分類的程序。要求實現的功能為：從文件夾中讀取所有文件名，存儲到 file 列表中，如：[[″000. mp3″]， [″001. pptx″]， [″002. pptx″]， [″003. jpg″]，…，[″099. jpg″]]，然后按文件后綴名進行分類，并統計每個類別下文件的數量，輸出結果如圖所示。
mp3類型的文件：
097.mp3 095.mp3 090.mp3 087.mp3 086.mp3 077.mp3 056.mp3 055.mp3 053.mp3 052.mp3 048.mp3 033.mp3 026.mp3 022.mp3 021.mp3 008.mp3 006.mp3 000.mp3
共18個
pptx類型的文件：
091.pptx 089.pptx 081.pptx 079.pptx 078.pptx 073.pptx 071.pptx 065.pptx 062.pptx 051.pptx 044.pptx 032.pptx 029.pptx 017.pptx 013.pptx 007.pptx 004.pptx 002.pptx 001.pptx
共19個
jpg類型的文件：
099.jpg 098.jpg 096.jpg 085.jpg 082.jpg 069.jpg 068.jpg 067.jpg 064.jpg 061.jpg 060.jpg 058.jpg 050.jpg 045.jpg 041.jpg 037.jpg 036.jpg 035.jpg 034.jpg 031.jpg 030.jpg 012.jpg 010.jpg 005.jpg 003.jpg
共25個
xlsx類型的文件：
094.xlsx 093.xlsx 088.xlsx 083.xlsx 080.xlsx 076.xlsx 074.xlsx 072.xlsx 066.xlsx 057.xlsx 049.xlsx 047.xlsx 042.xlsx 040.xlsx 027.xlsx 024.xlsx 023.xlsx 019.xlsx 018.xlsx 016.xlsx
共23個
docx類型的文件：
092.docx 084.docx 075.docx 070.docx 063.docx 059.docx 054.docx 046.docx 043.docx 039.docx 038.docx 028.docx 025.docx 020.docx 011.docx
共15個
答案　(1)n>＝0 and s[n]！＝″.″　(2)①a＝ft(file[i][0])　②fhead[j][1]＝i　
(3)①p＝fhead[i][1]　②p＝file[p][1]
解析　本題考查鏈表的構建和遍歷。(1)文件名最后一個點的后面為后綴名，因此查找若不是點，繼續查找。 (2)①語句fhead.append([a，i])為列表增加一個元素，結合語句print(fhead[i][0]＋″類型的文件：″)，因此a為后綴名，調用函數求file[i][0]的后綴。②變量j在fhead遍歷，因此若在該列表中能找到a，則j的值小于len(fhead)，語句file[i][1]＝fhead[j][1]的功能是將該節點指向原頭指針位置，需更新該鏈表的頭指針。(3)①變量i遍歷列表fhead，因此表示第幾條鏈表，當前節點q從第幾條鏈表的頭指針開始遍歷整個鏈表。②當前節點將指向下一個位置，鏈表信息存儲在數組file中。
2.某學校工會舉行飛鏢大賽，共有n位老師報名參賽，每位選手共擲5支鏢，每鏢得分為0至10分，選手總分為5鏢成績之和，每位選手的比賽數據記錄在文本文件中，如圖a所示。
圖a
處理前的數據為：
[['s001'，38]，['s002'，8]，['s003'，26]，['s004'，25]，['s005'，36]，['s006'，27]，['s007'，28]，['s008'，18]]
處理后的數據為：
[['s001'，38，4]，['s002'，8，－1]，['s003'，26，3]，['s004'，25，7]，['s005'，36，6]，['s006'，27，2]，['s007'，28，5]，['s008'，18，1]]
從高分到低分依次輸出選手的編號和總分為：
['s001'，38] ['s005'，36] ['s007'，28] ['s006'，27] ['s003'，26] ['s004'，25] ['s008'，18] ['s002'，8] NULL
圖b
處理要求：數據讀入數組data中，計算出每位選手的總分，在不改變數據在原數組data中的位置的條件下，按總分從高到低輸出選手的編號和總分。
(1)主程序。采用鏈表結構處理數據。程序運行結果如圖b所示。請在程序中劃線處填入合適的代碼。
data ＝ readdata(″scores.txt″)　#讀取數據，計算總分
print(″處理前的數據為：\\n″，data)
n＝len(data)
flag＝[True]*n　#標記數據被使用情況
head＝findmax()　#返回data中可使用狀態最大數的位置
k＝head
for i in range(1，n)：
答案　(1)k＝posi　(2)s＋＝ int(line[i])
(3)①maxnum②flag[pos]＝False　(4)q！＝－1
解析　(1)查找數組中的最大值的位置，利用位置關系串成一個降序鏈表，最后遍歷鏈表輸出。k是當前元素的位置，posi是下一個元素的位置，找到的數應該在節點posi后面。(2)readdata函數功能是讀取“scores.txt”文件，生成一個二維列表。變量s累計的總分。(3)findmax函數找到最大數所在位置，同時將改位置設置位False。(4)遍歷鏈表，輸出節點相關數據域的內容。
3.某醫院的看病流程為：患者通過網上、自助設備或人工窗口成功掛號后，到門診的簽到處簽到，簽到成功后即可排隊等待叫號就診。簡化的排隊規則如下：
①當天08：00之前完成簽到的患者，按照掛號順序從小到大排隊就診；
②08：00之后簽到的患者，按照掛號的序號從小到大的次序插入候診隊伍中；
③隊伍中前3名患者(包括正在就診患者)視為已進入待診狀態，插隊的患者只能插到這3名待診患者后的隊伍中。
假設醫生從08：00開始叫號就診，對每位患者的診斷時間均為3分鐘，忽略相鄰患者就診的時間間隔。編寫程序實現以下功能：若有患者簽到，則根據規則更新候診隊伍；醫生每完成一名患者的診斷，電子屏幕上按順序顯示待診的患者姓名和每個患者預計就診的時間。
(1)若當前已簽到患者信息如表所示：
姓名 掛號序號 簽到時間
A 3 07：47：03
B 1 07：51：12
C 6 07：55：32
D 4 07：57：10
E 8 07：59：52
F 2 08：02：07
則患者F的預計就診時間為　　　　(格式如08：07：20)。
答案　(1)08：09：00　(2)D　(3)t%3600∥60或t∥60%60　(4)①head＝len(lst)－1　②k<3 or data[1]>lst[q][1]
解析　(1)按照掛號的序號從小到大的次序插入前3名患者后面的候診隊伍中，每位患者的診斷時間均為3分鐘，因此預計時間為08：09：00。(2)構建8點前簽到的按掛號的序號從小到大候診隊伍。實現從后往前冒泡排序，前面的數據先有序，變量i記錄最后一次數據交換的位置，即有序數據的個數，也就是下一趟排序的左端點。(3)m表示將時間戳轉換為分，t是以秒為單位，則去除完整的小時數為t%3600，在這個數據中有多少個完整的60。(4)當無人排隊時，將新簽到患者直接插入候診隊伍，head將指向列表表尾；當隊伍中有人排隊且待診人數不足3人時需要按優先級進入待診隊伍。
4.現有n項先后出現的任務，每項任務需要一定的時間完成，且每個時刻只能執行某一項任務。任務的處理規則如下：
1)每項任務有一個緊急程度，用數字表示，數字越大緊急程度越高。緊急程度最高的任務優先執行，緊急程度相同先出現先執行。
2)若某項任務在執行過程中出現了一個緊急程度更高的任務，則正在執行的任務將被暫停，執行該緊急程度更高的任務。
編寫Python程序，實現如下功能：程序運行時，按編號升序輸出各項任務數據顯示如圖a所示，然后根據任務先后完成的情況顯示結果，如圖b所示。
請回答下列問題：
(1)若有3個任務需要完成，數據如下：
1號任務：時刻1出現，完成所需時長4，緊急程度1
2號任務：時刻2出現，完成所需時長2，緊急程度2
3號任務：時刻7出現，完成所需時長1，緊急程度3
則這3個任務的完成的順序為　　　　(單選，填字母：A.1號、2號、3號 /B.2號、3號、1號 / C.2號、1號、3號)。
答案　(1)C　(2)①n－i－1　②i head ③t[q[head]]＝＝0　
④q[tail]＝w[i][0]
解析　本題考查隊列的操作。(1)1號任務在時刻1出現，在時刻2被任務2中斷，時刻4任務完成，任務1繼續，直到時刻7。(2)①按任務編號從前往后冒泡升序排列。第i趟實現第n－1－i個數據有序，因此j的終值為n－i－2，但range是一個左閉右開的區間。②任務沒有結束的條件，變量i表示任務數量，當前入隊數量i小于n或者隊列中還有任務時，繼續任務。③列表t存儲每個任務所需時長，每次總是隊首的所需時長減1，當隊首元素所需時長為0時，表示該元素已經完成，需要出隊。④cur記錄當前任務時刻，若當前時刻有元素要入隊。從輸出語句print(w[q[head]][0]，cur)來看，需將任務編號w[i][0]入隊。
1.某市舉辦科技嘉年華活動，為了激發學生的參與積極性，舉辦方推出了玩游戲得積分，積分兌換禮物的活動。活動中游戲分為簡單和困難兩種，參與游戲就可以獲得相應的積分，當完成困難游戲時，除了獲得相應積分外，還可獲得一張“積分翻倍卡”，一張“積分翻倍卡”可用于一個簡單游戲，使簡單游戲的積分翻倍。
“積分翻倍卡”使用規則如下：
(1)當簡單游戲開始時，如果有“積分翻倍卡”可用，則一定會使用。
(2)“積分翻倍卡”需在15分鐘內使用。比如困難游戲完成時間是9：15分，則獲得的“積分翻倍卡”將在9：15分激活，且超過9：30分將失效。
3)如果有多張“積分翻倍卡”，則優先使用最早的“積分翻倍卡”。
某同學的游戲記錄如圖a所示(類型0表示困難游戲，類型1表示簡單游戲)，小明讀取游戲記錄，編寫Python程序計算出該同學游戲的最終得分。程序運行結果如圖b 所示，請回答下列問題：
序號 類型 積分 開始時間 完成時間
1 0 10 9：10 9：15
2 1 3 9：15 9：28
3 1 5 9：38 9：42
4 0 12 9：58 10：05
5 1 3 10：20 10：36
6 0 15 10：48 10：55
7 1 3 11：25 11：29
圖a
(1)若某同學參加游戲的記錄如圖c所示，則他獲得的積分是　　　　分。
答案　(1)40　(2)int(m[0])*60＋int(m[1])　(3)①que[tail]＝a[i][4]　②que[head]＋15解析　本題考查隊列的基本操作。(1)完成困難游戲獲得積分翻倍卡，一張積分翻倍卡使簡單游戲的積分翻倍，但積分卡在15分鐘內有效，14：47激活卡，15：10已經過期。積分為10＋5*2＋15＋5。(2)將時間按冒號分隔，得到一個列表，列表中有兩個值，分別為m[0]和m[1]。(3)①將積分卡激活時間加入隊列，困難游戲完成時間就是卡激活時間。②遍歷列表b，簡單游戲一開始就可以使用翻倍卡，因此計算翻倍卡的激活時間與當前簡單游戲開始時間的時間差，該時間差大于15分鐘時，卡失效。③使用翻倍卡，積分將翻倍。
2.某學校有n個社團組織招新(社團編號為1－n)，每個社團最多可招收m人。學生在線提交申請信息，提交內容為社團編號和對該社團的喜好程度(1－5分)，學生可同時提交報名多個社團，但只能被1個社團錄取。后臺自動記錄學生的報名序號和全部報名信息。報名序號從1開始編號，申請信息的記錄格式如圖a所示，報名序號為1的學生報名3號社團喜好程度為3，同時報名2號社團喜好程度為4，還報名了1號社團喜好程度為5。
學生報名完畢后，n個社團通過抽簽決定招新順序，抽簽號為1－100的隨機整數，抽到數字小的社團先招錄學生。每個社團招錄時，系統調取報名該社團的申請信息，根據學生提交的喜好程度從高到低錄取，尚未被其他社團錄取的學生，喜好程度相同則按報名序號(學生的報名先后順序)從小到大錄取。
編寫程序，讀取每位學生的報名序號及報名信息、各社團的抽簽序號，程序自動完成社團招新并輸出錄取結果。
例如，3個社團招新，每社團最多招收2人，社團的抽簽序號依次為1、3、2，那么圖a中的報名信息，招新結果如圖b所示。
報名序號 申請信息(每2個數字為一組，表示社團編號，喜好程度)
1 3，3，2，4，1，5
2 3，1
3 3，2，1，4，2，4
4 3，1，1，1
5 2，1，3，1
圖a
社團編號 抽簽序號 有意向學生(括號中為喜好程度) 錄取結果
1 1 1(5)，3(4)，4(1) 1，3
2 3 1(4)，3(4)，5(1) 5
3 2 1(3)，2(1)，3(2)，4(1)，5(1) 2，4
圖b
請回答下列問題：
(1)若每個社團最多招收人數為3人，1、2、3號社團抽簽序號仍為1、3、2時，對圖a中的數據進行重新執行招錄操作，則3號社團錄取的學生為　　　　。
已知clubs為[[1，8]，[2，25]，[3，3]，[4，9]，[5，1]，[6，25]]，若①處的語句改為“for i in range(n－1)”，執行a＝px(clubs)，a的值為　　　　。(單選，填字母)。
A.[5，3，1，4，2，6] B.[5，3，1，4，2]
C.[5，3，1，4，6，2] D.[5，3，1，4，6]
答案　(1)2，5　(2)B　(3)①item[1][x＋1]　②x＝f[i][fs]　③flag[j]＝＝False and t>0
解析　(1)招生人數為三人時，1號社團將錄取：1，3，4號同學；故第二個錄取的3號社團只能錄取：2，5同學。(2)排序后clubs數組為[[5，1]，[3，3]，[1，8]，[4，9]，[2，25]，[6，25]]，若抽簽序號相同，則數組原順序不變。只剩2個元素時，ans僅存儲了倒數第2個(n－2)，最后一個元素(n－1)未被添加。(3)把原來的報名信息轉換存儲為每個社團的報名情況(包含報名序號和喜好程度)用f來存儲，f[st][fs]表示社團st喜好fs的報名序號。①空所在代碼是求得該報名情況的喜好程度fs＝item[1][x＋1]；②空所在代碼是枚舉各社團按喜好程度從高到低去選擇出m個序號。fs這里起到了從最高分5分逐次到低分的選擇過程(也是排序思想)，那么x的賦值就應該是各個報名序號，所以為x＝f[i][fs]；③空所在條件需要表達該社團人數未滿，且該報名序號未被選擇，所以應該填寫為flag[j]＝＝False and t>0。
3.某餐廳的訂單數據由線上、線下多條訂單合并而成。各條訂單含下單時間、菜品列表兩個數據項，下單時間(各訂單下單時間互不相同)的數據格式為“時：分鐘”；菜品列表由互不重復的大寫字母構成，按字母升序排列如“ABC”，每個字母代表一種菜品，合并后的訂單數據如圖a所示。
由于廚師一鍋能烹飪5份同種菜品，為了提升烹飪效率，餐廳打算為廚師提供烹飪提示隊列。按合并訂單數據中下單時間的先后順序逐條處理，對各條訂單中的不同菜品進行統計：當某種菜品中首份菜品的下單時間超過10分鐘時，或某種菜品累計份數達到5份時，該種菜品及累計份數將進入烹飪提示隊列，入隊后該種菜品重新開始統計。
當多種菜品符合某個入隊條件時，按各菜品中首份菜品下單時間先后時間順序入隊。所有訂單處理完畢，剩余未入隊的菜品直接進入派單提示器隊列，處理結果如圖b所示。
(3)實現派單提示器隊列功能的部分Python程序如下，程序中用到的列表函數與方法如表所示，請在程序劃線處填入合適的代碼。
函數與方法 功能
dc.append(x) 在列表dc末尾添加元素x
head＝qu.pop(x) 將列表x位置元素賦值給head，并將其從qu中刪除
答案　(1)5　
(2)③　if m>＝0 and lst1[m][0]>lst2[n][0]：或if m>＝0 and lst1[m][0]>＝lst2[n][0]：
(3)①dishes_str＝orders[i][1]
②len(qu)>0 and pret－dc[qu[0]][1]>10
③pdish＝qu.pop(k)
解析　(1)從10：03分到10：11分沒超過10分鐘，但A菜品累計份數到達了5份，需要進入烹飪。(2)從后往前比較lst1和lst2中將下單時間晚的合并到lst1中，但如果lst1的下單時間均大于lst2的下單時間，則會發現運行有誤。將變量m的邊界進行限制，故答案為if m >＝ 0 and lst1[m][0] > lst2[n][0]。(3)將完成菜品k出隊，并將菜品名稱賦值給pbish.

展開更多......

收起↑