資源簡介

專題19　基于數據結構的算法實現
學業要求 知　識　點 學業水平等級
1.針對模型較為隱蔽的實際問題，能認識數組、鏈表在組織結構、操作特性等方面的差異 4
2.從數據結構的視角審視基于數組、鏈表與字符串的程序，解釋程序中數據的組織形式，描述數據的邏輯結構、存儲結構及其操作 4
知識點　鏈表在數據組織中的作用
【知識梳理】
1.創建一個鏈表data的兩條語句data＝[]；________＝－1。
2.鏈表data的指針區域索引為1，當前節點為q，則他下一個節點的索引是________。
3.鏈表data的指針區域索引為1，在頭節點head前插入索引為i的節點兩條語句data[i][1]＝head、________。
4.刪除頭鏈表data節點head的語句____________。
5.判斷鏈表為空的條件是____________，鏈表data的首尾兩個節點分別為head和tail，若鏈表中只有一個節點，兩者關系____________。
6.將索引為i節點鏈接到節點tail的后面，同時更新tail的兩條語句data[tail][1]＝i、________。
7.將索引為i節點插入到節點q(節點q不是頭節點)的前面，pre為節點q的前驅，語句為data[pre][1]＝i；________________。
【經典案例】
由于隊列是只能在隊首位置出隊，在隊尾位置入隊的受限的線性表，意味著隊列中間的元素不進行操作，因此用鏈表存儲的隊列往往只要用隊首head和隊尾tail兩個指針來記錄隊列的存儲情況，其他節點通過指針域的值依次連接起來。在鏈表的鏈尾插入元素，然后讓隊尾指針指向鏈尾元素。鏈式隊列的出隊，就是將鏈表的首元節點從鏈表中刪去，讓其后繼節點成為首元節點，然后讓隊頭指針指向該節點。
【例1】 某工程包含n個任務(編號為0～n－1)，每天可以有多個任務同時進行。某些任務之間有依賴關系，如圖a所示，任務4依賴于任務1，任務1依賴于任務2。即任務2完成后才可以開始任務1，任務1完成后才可以開始任務4。不存在一個任務依賴于多個任務，或多個任務依賴于同一個任務的情況。現已對該工程的依賴關系進行了梳理，結果如圖b所示，標記“T”表示依賴關系需保留，標記“F”表示依賴關系需刪除。
根據每個任務完成所需的天數和梳理后的依賴關系，編寫程序，首先刪除標記為“F”的依賴關系，然后計算工程最快完成所需的天數，并以工程最快完成所需的天數為期限，計算每個任務最晚必須開始的時間。
請回答下列問題：
(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(lst)的數，則語句“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
任務間的依賴關系存入lst列表
lst[0]包含3項，任務lst[i][0]依賴于任務lst[i][1]，lst[i][2]存放保留/刪除標記，任務數據存入task列表
task[i]包含2項，task[i][0]為完成任務所需天數，task[i][1]的初值為－1
代碼略
'''
proc(n，lst，task)
思維點撥
明考向 本題考查數組的遍歷、鏈表的遍歷、創建等操作
精點撥 (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不是尾節點，該任務必須在其后續任務完成前開始，開始時間為后續任務的最晚開始時間減去當前任務完成時間
【變式1】 題目描述如例1，請回答下列問題。
(1)任務2和任務4最晚開始時間分別為________，________。
(2)實現上述功能的部分Python程序如下，請在劃線處填入合適的代碼。
def proc(n，lst，task)：
　 pr＝[0]*n
　 for i in range(len(lst))：
　 　　if lst[i][2]＝＝″T″：
　 　　　　task[lst[i][1]][1]＝lst[i][0]
　　　 ①________
　 fhead＝[]；days＝0
　for i in range(n)：
　　　if pr[i]＝＝0：
　　 　 fhead.append([i，task[i][0]])
　 　　　　q＝task[i][1]
　　 　 while q！＝－1：
　 　　　　　　fhead[－1][1]＋＝task[q][0]
　　 　　　 ②________
　　　　　 if fhead[－1][1]>days：
　　 　　　 days＝fhead[－1][1]
　 w＝[0]*n
　 for i in range(len(fhead))：
　 　　pre＝fhead[i][0]
　 　　w[pre]＝days－fhead[i][1]＋1
　 　　q＝task[pre][1]
　 　　while q！＝－1：
　　 　 ③________
　 　　　　pre＝q
　　 　 q＝task[q][1]
print(″工期所需最短時間″＋str(days)＋″天，各任務最晚開始時間：″，w)
lst＝[[0，5，″T″]，[5，4，″F″]，[4，1，″T″]，[1，2，″T″]，[2，3，″F″]]
task＝[[2，－1]，[1，－1]，[3，－1]，[5，－1]，[1，－1]，[6，－1]]
n＝6
proc(n，lst，task)
【變式2】 題目描述如例1，實現上述功能的部分Python程序如下，請在劃線處填入合適的代碼。
def proc(n，lst，task)：
pre＝[0]*n
w＝[0]*n　#w[i]存放任務i最晚必須開始的時間
m＝len(lst)
for i in range(m)：
if lst[i][2]＝＝″T″：
　 　　　task[lst[i][0]][1]＝lst[i][1]　
#創建關系鏈表
　　　　 ①________
heads＝[]
days＝0　#days存放工程最快完成所需的天數
for i in range(n)：
if pre[i]＝＝0：　#若為鏈表的頭節點
　　　　 heads.append(i)
　　　　 ②________
　　　　 s＝0
　　　 　while k！＝－1：
　　　　　　 s＋＝task[k][0]
　　　　　 　k＝task[k][1]
　　　　 if s>days：
　　　　　 　days＝s
for h in heads：
w[h]＝days－task[h][0]＋1
p＝h
k＝task[h][1]
while k！＝－1：
　　　 　③________
　　　 　p＝k
　　　　 k＝task[k][1]
print(″工期所需最短時間″＋str(days)＋″天，各任務最晚開始時間：″，w)
lst＝[[0，5，″T″]，[5，4，″F″]，[4，1，″T″]，[1，2，″T″]，[2，3，″F″]]
task＝[[2，－1]，[1，－1]，[3，－1]，[5，－1]，[1，－1]，[6，－1]]
n＝6
proc(n，lst，task)
【例2】 有2組器件共n個，要用一臺檢測設備檢測。每個送檢器件的信息包含送達時間、檢測時長和優先級。優先級有m(1編寫程序模擬檢測過程，先合并2組器件的數據，然后計算所有器件的平均等待時長，其中每個器件等待時長為其開始檢測的時間與送達時間的時間差。(時間單位均為秒)
請回答下列問題：
(1)由題意可知，圖中器件A、B、C、D的檢測順序為A－C－D－B，A、C、D的等待時長分別為0、1、0，B的等待時長是________。
送達時間 檢測時長 優先級
A 0 3 2
B 1 1 2
C 2 1 1
D 4 3 0
11 3 2
12 2 2
(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]] lst1＝[[1，1，2]]
B.lst2＝[[1，1，2]] lst2＝[[0，3，2]，[4，3，0]]
C.lst1＝[[1，1，2]，[4，3，0]] lst1＝[[4，3，0]]
D.lst2＝[[0，3，2]] 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 i0：
if i　　　　 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的下一個器件位置，完成刪除操作
聽課筆記：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式3】 某花瓶廠有三臺不同型號的機器，可生產ABC三種不同型號的花瓶。廠家每天會收到很多網上訂單，每個客戶的訂單信息包含訂單號、型號、數量和狀態，其中狀態值為1表示確認訂單，－1表示取消訂單。工作人員首先挑選出確認的訂單，然后對訂單按花瓶型號進行分類統計，最后交給工作人員生產。訂單信息存儲在“orders.csv”文件中，文件數據格式如圖a所示。請回答下列問題。
(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所示。請在程序劃線處填入合適的代碼。
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 ik＝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 py＝tlist[p][0]
total＝0
while y！＝－1：
print(orders[y][0：3]，″→″，end＝″ ″)
②________
y＝orders[y][3]
print(″共計″，total，″個″)
③________
綜合題　基于數據結構的算法
【經典案例】
【例題】 某工程的A項目有n個任務組(編號為0～n－1)，供料商每小時只提供1份原料，各組按到達時刻(到達時刻各不相同)陸續加入領料隊列，領取1份原料后到隊列末尾重新等待，直至領完所需原料，離開隊列。若多組同時入隊，則到達時刻早的優先入隊。編寫程序模擬領料過程，先篩選出屬于A項目的任務組，再計算每個任務組完成領料的時刻(時間單位：小時)，請回答下列問題：
任務組別 到達時刻 原料需求量
第0組 0 3
第1組 1 2
第2組 2 1
圖a
時刻 領料隊列 輪到領料的組別
0 0 0
1 0，1 0
2 1，0，2 1
3 0，2，1 0
4 ▲
5 1 1
注：領料隊列中數字代表任務組編號
圖b
(1)某項目任務組信息如圖a所示，部分領料過程如圖 b 所示，結合題意，第 4 時刻的領料隊列是__________。(單選，填字母：A.2，1，0/B.2，1/C.2，0，1)
(2)定義如下 filte(task，st)函數
def filte(task，st)：
i＝0 ; j＝0 ; n＝len(task)－1
while j <＝n：
if task[j][0]＝＝st:
　　　　 task[i]＝task[j]
　　　　 i＋＝1
j＋＝1
return i
若 task 的值是[['A'，0，3]，['B'，1，3], ['B'，2，6], ['A'，3，4], ['A'，4，5]]，st 的值是'A'，執行語句 m＝filte(task，st)后，m的值是__________。
(3)編寫程序模擬任務組領料過程，輸出每個任務組完成領料的時刻，部分Python 程序如下，請在劃線處填入合適的代碼。
def proc(task, st)：
m＝filte(task, st)
for i in range(m)：
task[i].append(－1)
order＝[0] * m
i＝0；ct＝0；t＝0
while i < m or tif i < m and task[i][1] <＝ct：
　　　 　if i＝＝t：
　　　　 　　①________
　　　　　 　task[p][3]＝i
　　　　 else：
　　　　　 　task[i][3]＝task[p][3]
　　　　　 　task[p][3]＝i
　　　　　 　p＝i
　　　　i＋＝1
if i>t：
　　　 　②________
　　　　 task[k][2]＝task[k][2] － 1
　　　 　if task[k][2]＝＝0：
　　　　　 　order[k]＝ct
　　　　　 　③__________
　　　　　 　t＋＝1
　　　　 else：
　　　　　 　p＝task[p][3]
ct＋＝1
return order
'″每個任務初始數據存入 task 列表，task[i]包含 3 項，task[i][0]為該組項目名稱，task[i][1]為該組到達時刻，task[i][2]為該組原料需求量，數據按到達時刻升序排列，代碼略'″
st＝″A″
print(proc(task，st))　#輸出該項目中每個任務組完成領料的時刻
思維點撥
明考向 本題考查循環隊列的鏈式存儲運算
精點撥 (1)領料組0已經完成領料，不再入隊，因此隊列中為2，1，正在領料的是2。(2)變量j從0開始遍歷，當條件task[j][0]＝＝st成立時，執行i ＋＝1，因此i表示st 的值是'A'的數量。(3)①ct表示當前時間，當條件task[i][1] <＝ct成立，表示將索引i的task元素入隊。從條件task[k][2]＝＝0來看，表示該組任務完成，因此t表示完成任務的數量。當i和t相等時，表示鏈表隊列中數量為0，當前隊列中只有一個元素，語句task[p][3]＝i表示節點p的后繼是i，訪元素的后繼是本身，這就符合循環隊列的特征，隊尾指向隊首。單向隊列中若已知隊尾可以得到隊首位置，已知隊首須遍歷鏈表才能得到隊尾，因此p為隊尾，共初值為i。②當i大于t時，表示入隊的元素數量大于完成數量，需進行出隊操作，k為隊首指針，其值為隊尾p的后繼。③當隊首完成領料后，需從鏈表中刪除頭節點
聽課筆記：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式】 某醫院有m個類型的科室(編號為0至m－1)，每個科室都有若干位醫生坐診。假設每位患者都是就診后再離開，當患者到達時，如果就診的科室有空閑醫生就直接就診，無需等待；否則在門口排隊等待看病。當前面就診的患者離開時，后面排隊的患者按排隊順序就診。文件“mydlata.txt”記錄每個科室所有就診數據，患者等候的總時間，以便醫院合理調配醫生。數據樣例如圖a所示，每行數據包含到達或離開、就診科室類型、到達或離開時間3項，其中時間格式為HH：MM。程序的運行結果如圖b所示。
到達，0，08：00 到達，1，08：05 離開，0，08：10 到達，2，08：15 到達，1，08：25 離開，2，08：55 ……
圖a
請輸入科室類型的數量m：3 請輸入類型0的科室坐診醫生人數：2 請輸入類型1的科室坐診醫生人數：1 請輸入類型2的科室坐診醫生人數：3 0類型科室的總等待時間為80分鐘 1類型科室的總等待時間為80分鐘 2類型科室的總等待時間為30分鐘
圖b
到達，0，08：00 到達，1，08：10 到達，1，08：15 離開，1，08：45 離開，1，08：35 離開，2，08：55 ……
圖c
(1)若類型1的科室有兩名坐診醫生，患者到達或離開的數據如圖c所示，則該科室的患者總等待時間________分鐘。
(2)定義如下read_data(file_path，a)函數，參數file_path表示數據文件名，參數a為列表用于存儲數據，返回a。
def read_data(file_path, a)：
with open(file_path, 'r', encoding＝'utf－8') as file：　#讀取TXT文件
for line in file：　#逐行讀取
　　　 　row＝line.strip().split('，')
　　　 　a.append(list(map(str.strip，row)))　#將每行數據轉換為列表，添加到a中
n＝len(a)
for i in range(n － 1)：
for j in range(n －i －1)：
　　　 　if a[j][2] > a[j＋1][2]：
　　　　 　　a[j], a[j ＋ 1]＝a[j ＋ 1]，a[j]
return a
下列代碼和加框處代碼實現相同功能的是________。(多選，填字母)
A.for i in range(1，n)：
for j in range(i，0，－1)：
if a[j][2] < a[j－1][2]：
　　　　 a[j－1]，a[j]＝a[j]，a[j－1]
B.for i in range(n － 1)：
for j in range(n － i － 1)：
if a[j][2]< a[j＋1][2]：
　　　　 a[j]，a[j－1]＝a[j－1]，a[j]
C.for i in range(1，n)：
for j in range(i，1，－1)：
if a[j－1][2] > a[j][2]：
　　　 a[j－1], a[j]＝a[j]，a[j－1]
D.for i in range(n － 1)：
for j in range(1, n － i)：
if a[j][2]　　　　 a[j], a[j－1]＝a[j－1], a[j]
(3)實現上述功能的部分 Python程序如下，請在劃線處填入合適的代碼。
def ct(s)：　#時間HH：MM轉化為分鐘
minutes＝int(s[0：2])* 60 ＋ int(s[3：])
return minutes
m＝5　#科室類型的數量
num＝[2，1，3，2，3]　#每種科室的坐診醫生數量列
a＝[]
a＝read_data('mydata.txt'，a)　#調用read_data()函數完成數據讀取及排序
queinfo＝[]
for i in range(m)：
queinfo.append([－1，－1])
q＝[]
wait＝[0]* m
for i in range(len(a)) ：
k＝int(a[i][1])　#科室類型
if a[i][0]＝＝'離開'：　#a[i][0]代表狀態“到達”或“離開”
num[k] ＋＝1　#對應類型科室空閑醫生增加1
if queinfo[k][0] ！＝－1：
　　　 　t＝ct(a[i][2]) － ct(q[queinfo[k][0]][1])　#a[i][2]代表時間
　　　 　①________
　　　　 next_in_queue＝q[queinfo[k][0]][2]
　　　 　if next_in_queue ！＝－1：
　　　　　 　queinfo[k][0]＝next_in_queue
　　　　 else：
　　　　　 　queinfo[k][0]＝－1
　　　　 num[k] －＝1
else：
if num[k] > 0：
　　　　 ②________
else：
　　　　 q.append([k，a[i][2]，－1])
　　　 　if queinfo[k][0]＝＝－1：
　　　　　 　queinfo[k][0]＝len(q)－1
　　　　 else：
　　　　　 　③________
　　　　 queinfo[k][1]＝len(q) － 1
for i in range(m)：
print(i，″類型科室的總等待時間為″， wait[i]，″分鐘″)
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, 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 9：15時刻使用了積分翻倍卡； 10：20時刻使用了積分翻倍卡； 10：55時刻生效的積分翻倍卡過期； 總共獲得積分為：57分，剩余積分卡有：0張。
圖b
(1)若某同學參加游戲的記錄如圖c所示，則他獲得的積分是________分。
序號　 類型 積分 開始時間 完成時間 1, 0, 10, 14：15, 14：20 2, 1, 5, 14：30, 14：33 3, 0, 15, 14：40, 14：47， 4, 1, 5, 15：10, 15：13
圖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 headprint(que[head]//60，″：″，que[head] % 60，″時刻生效的″＋″積分翻倍卡過期；″)
head＋＝1
if headprint(b[i][3]//60，″：″，b[i][3]%60，″時刻使用了積分翻倍卡；″)
③________
head＋＝1
else：
total＋＝b[i][2]
print(″總共獲得積分為：″，total，″分，″，″剩余積分卡有：″，tail－head，″張。″)
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秒才能完成)。
(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 ilink.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 iq＝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.學校籌辦校慶，向校友提供“教室預約”服務。校友以班級為單位，在線提交預約申請。學校當前預備了 m個教室，按“教室名”升序排序后編定“教室序號”。教室信息和預約申請內容如下圖所示(教室已按教室名升序排序，預約申請中“預約序號”為 0 的記錄表示：91 屆 1 班的校友申請在 8：00－9：30 期間使用教室)。
教室序號 教室名
0 立德樓101
1 立德樓102
2 立德樓201
3 立德樓202
4 行知樓101
5 行知樓102
6 行知樓201
7 行知樓202
8 行知樓203
圖a
預約序號 校友班名 起始時間 結束時間 電話 …
0 91屆1班 08：00 09：30 … …
1 88屆1班 08：00 10：00 … …
2 07屆6班 13：00 14：30 … …
3 00屆5班 10：30 11：30 … …
4 94屆2班 09：30 11：30 … …
5 12屆3班 12：30 14：00 … …
6 15屆2班 09：30 11：00 … …
7 22屆9班 13：00 15：00 … …
8 20屆3班 15：00 16：30 … …
9 19屆3班 14：00 16：00 … …
圖b
學校按“預約序號”順序，逐條處理預約申請，處理時按“教室序號”順序，逐個教室檢查，安排使用第一個預約時間不沖突的教室。按此規則逐條處理上圖的 10 條申請，“立德樓 101”教室將安排“預約序號”為 0、2、 3、8 的申請。
編寫程序實現預約功能，按時間順序輸出各個教室接受的預約安排，如圖c所示。
接受申請的教室具體安排如下： 立德樓101： 91屆1班08：00—09：30　00屆5班10：30—11：30　07屆6班13：00—14：30　20屆3班15：00—16：30 立德樓102： 88屆1班08：00—10：00　12屆3班12：30—14：00　19屆3班14：00—16：00 立德樓201： 94屆2班09：30—11：30　22屆9班13：00—15：00 立德樓202： 15屆2班09：30—11：00 >>>
圖c
部分代碼如下，請回答以下問題。
(1)上例中若新增一個使用時間為“8：00－9：00”的申請，應安排的“教室序號”為________。(填寫 0－8 的數字)
(2)定義 check(k，i)函數，功能為判斷預約序號為 k 的申請，能否安排到序號為 i 的教室。
def check(k，i)：
n＝len(jslst[i][2])　#列表 jslst[i][2]存儲教室序號為 i 的教室已接受的預約序號
if n＝＝0：
return True
for p in jslst[i][2]：
if not(yylst[k][3] <＝yylst[p][2] or ________):
return False
return True
劃線處應填寫代碼：________
(3)定義 work(k)函數，功能為依次枚舉每個教室，為“預約序號”為 k 的申請安排教室。
def work(k)：
p＝－1
for i in range(len(jslst))：
if ________：
jslst[i][2].append(k)　#將“預約序號”k存入“教室序號”為i的教室
　　　 　p＝i
　　　 　break
return p
劃線處應填寫代碼：________
(4)定義sort(a)函數，參數列表a中的存儲“預約序號”，將這些申請按題意排序。
def sort(a)：
n＝len(a)
for i in range(n－1)：
for j in range(0，n－i－1)：
　　　 　if yylst[a[i]][2]__>__yylst[a[i＋1]][2]__：
　　　　 　　a[i]，a[i＋1]＝a[i＋1]，a[i]
若將劃線處的代碼修改為 yylst[a[i]][3] > yylst[a[i＋1]][3]，排序結果________改變。(填：會/不會)
(5)主程序。讀入預約申請信息存入列表 yylst，存儲格式為[預約班名，開始時間，結束時間，教室序號], 如[3，'00 屆 5 班'，'10：30'，'11：30'，1]，“預約序號”為 3 的申請，安排在“教室序號”為 1 的教室，時間格式統一為 5 位字符組成″××：××″。
讀入升序排序的教室清單存入一維數組 jslst，如[0，'立德樓 101'，[0，2，4]]，表示“教室序號”為 0 的教室，接受“預約序號”為 0，2，4 的 3 個預約申請。
for i in range(len(yylst))：　#按“預約序號”順序，逐條處理預約申請
t＝work(i)
if ________：
print(″預約序號為″，i，″的申請無法被安排″)
else：
yylst[i][4]＝t
for i in range(len(jslst)): #對各個教室接受的預約安排進行排序
sort(jslst[i][2])
#輸出各個教室接受的預約安排，代碼略。
劃線處應填寫代碼：________
5.某醫院的看病流程為：患者通過網上、自助設備或人工窗口成功掛號后，到門診的簽到處簽到，簽到成功后即可排隊等待叫號就診。簡化的排隊規則如下：
①當天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 ik＝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
6.某醫院為實現就診順序規則的相對公正，實行就診前“掛號＋簽到”模式，排隊規則如下：
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的患者信息，程序運行后，加框處的語句總共執行________次。
專題19　基于數據結構的算法實現
知識點
知識梳理
1.head　2.data[q][1]　3.head＝i　4.head＝data[head][1]　5.head＝＝－1　head＝＝tail　6.tail＝i　7.data[i][1]＝q
經典案例
例1　(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　(1)4，8　(2)①pr[lst[i][0]]＝1　②q＝task[q][1]
③w[q]＝w[pre]＋task[pre][0]
解析　本題考查鏈表的構建和遍歷。(1)任務2、1、4共需時間為5天，那么任務2作為大任務最晚開始時間為8－5＋1＝4，任務2的完成時間4＋3＝7，任務1的開始時間就是任務2的完成時間，任務1的完成時間為8，因此任務4的開始時間為第8天。(2)①在task鏈表中，節點lst[i][1]的后繼是lst[i][0]，從而說明節點lst[i][0]是有前驅的。②fhead數組中存儲每個鏈表頭指針和每項任務的天數和，在遍歷該鏈表時，節點q應向后移動。②計算每個節點的最晚開始時間，當作任務的開始時間就是前一任務的結束時間，而前一任務的結束時間為他的開始時間w[pre]與他的所需天數task[pre][0]之和。
變式2　①pre[lst[i][1]]＝1　②k＝i　③w[k]＝w[p]－task[k][0]
解析　本題與例1的不同點在于鏈表的構建語句：task[lst[i][0]][1]＝lst[i][1]，即lst[i][0]的后繼是lst[i][1]，因此是反向構建鏈表。①lst[i][1]有前驅。②當前節點k從沒有前驅的節點i開始遍歷。③鏈表的頭節點是這一組任務最后一個需完成的任務，因此他的后繼是他前面的任務，該后繼的開始時間是他的完成時間減去任務所需時間，而他任務的完成時間應該是他前驅的開始時間。
例2　(1)6　(2)①4　②A　(3)①total＝0　②p＝queinfo[k][1]　③queinfo[k][0]＝data[p][3]
變式3　(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。
綜合題
經典案例
例題　(1)B　(2)3　(3)①p＝i　②k＝task[p][3] ③task[p][3]＝task[k][3]
變式　(1)20　(2)AD　(3)①wait[k]＋＝t ②num[k]－＝1　③q[queinfo[k][1]][2]＝len(q)－1
解析　(1)前2名患者無需等待，隊列中只有第3名患者，08：35的患者離開后，隊列中的患者開始就診，因此他的等待時間為20分鐘。(2)程序的功能是按時間進行升序排列，A選項是插入排序，將第i個數據與前i－1個數據進行一趟相鄰數據的比較和交換，使得前i個數據有序。B選項實現了降序排列。C選項j的終值只能取到2，因此數據a[0]未參加排序。D選項從前往后排序，j的終值為n－i－1，當i的值為0時，能對全部數據區域進行排序。(3)①計算等待時間。num[k]表示類型k科室空閑醫生數量，當該元素值大于0，表示有閑醫生，可以不用等待，否則進行隊列等待就診，那么該科室的總等待時間就是隊列中患者的等待時間之和。queinfo[k]存儲類型k科室的隊首和隊尾指針，當隊首不為空時，表示隊列中有患者，那么其等待時間就是開始就診時間減去到達時間，而前面一名患者的離開時間恰好是該患者的就診時間。②條件num[k]>0表示科室有空閑醫生，患者無需等待，不用入隊，但空閑醫生的數量將要減少一名。③條件queinfo[k][0]＝＝－1表示隊列為空，否則隊列有元素，那么在隊尾queinfo[k][1]進行入隊，原隊尾節點q[queinfo[k][1]]將指向該新增節點，同時將更新隊尾指針。
當堂過關檢測
1.(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.(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.(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)yylst[k][2] >＝yylst[p][3]　(3)check(k，i)或check(k，i)＝＝True　
(4)不會　(5)t＝＝－1
解析　(1)序號0、1、2教室使用時間為[08：00－09：30]、[08：00－10：00]、[09：30－11：30]，因此安排序號為2號教室。(2)函數check的功能為判斷預約序號為k的申請能否安排到序號為i的教室，需要對已接受預約序號對應的時間區間進行遍歷，早于已預約區間的起始時間或遲于已預約區間的結束時間都能被安排到該教室。(3)調用check檢測當前預約序號k是否能夠安排教室序號i。(4)輸出結果按照每個預約申請占用的時間區間來排序，故自定義函數sort按照起始時間和結束時間都可以。(5)若預約申請無法被安排，函數work的返回結果為－1。
5.(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)略。
6.(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。

展開更多......

收起↑