資源簡介

非選擇題專項(xiàng)(一)
二、非選擇題(本大題共3小題，其中第13題9分，第14題8分，第15題9分，共26分)
13.小明為蔬菜大棚搭建了一個簡易溫度監(jiān)測控制系統(tǒng)，可以設(shè)定閾值，系統(tǒng)提供自動及手動工作模式。自動工作模式時，系統(tǒng)會自動根據(jù)溫度變化情況控制是否加熱，使蔬菜大棚保持適合的溫度。手工工作模式，可以通過瀏覽器遠(yuǎn)程訪問系統(tǒng)控制網(wǎng)頁，直接開啟或關(guān)閉加熱器。該系統(tǒng)結(jié)構(gòu)示意圖如圖所示。系統(tǒng)為B/S開發(fā)模式，使用micro：bit作為智能終端，溫度傳感器采集數(shù)據(jù)。傳感器采集的數(shù)據(jù)由智能終端經(jīng)IoT模塊發(fā)送到Web服務(wù)器，用戶可通過瀏覽器查詢實(shí)時和歷史數(shù)據(jù)。執(zhí)行器用于實(shí)現(xiàn)溫度的控制。根據(jù)以上功能描述，請回答下列問題：
(1)下列關(guān)于該信息系統(tǒng)的說法，正確的是________(單選，填字母)。
A.在該信息系統(tǒng)中，智能終端的作用相當(dāng)于中央處理器CPU
B.在該信息系統(tǒng)中，傳感器和執(zhí)行器沒有智能終端的控制不能正常工作
C.概要設(shè)計階段，包括系統(tǒng)的模塊結(jié)構(gòu)設(shè)計、系統(tǒng)物理配置和數(shù)據(jù)庫設(shè)計三大部分
(2)通過瀏覽器遠(yuǎn)程手動模式開啟加熱器操作時，指令數(shù)據(jù)的傳輸過程為________。(單選，填字母)
A.瀏覽器→數(shù)據(jù)庫→智能終端 B.瀏覽器→智能終端→服務(wù)器
C.瀏覽器→Web服務(wù)器→智能終端
(3)根據(jù)題意，下列功能需要在智能終端程序中實(shí)現(xiàn)的是________。(多選，填字母：A.采集溫度傳感器上的數(shù)據(jù)/B.處理瀏覽器訪問請求/C.接收服務(wù)器指令/D.打開或關(guān)閉加熱器)。(注：全部選對的得2分，選對但不全的得1分，不選或有選錯的得0分)
(4)智能終端上的程序具有如下功能：每隔5分鐘從傳感器獲取1次溫度值：加熱器處于關(guān)閉狀態(tài)時，若溫度值小于等于閾值temp1，則打開加熱器；加熱過程中，若溫度值大于等于閾值temp2，則關(guān)閉加熱器；并將溫度數(shù)據(jù)傳輸?shù)椒?wù)器。部分Python程序如下，請在程序中劃線處填入合適的代碼。
#導(dǎo)入相關(guān)庫，代碼略
flag＝False
while True：
　　#從傳感器獲取溫度值，保存在newtemp中，代碼略
　　#從服務(wù)器獲取溫度閾值temp1和temp2及工作模式數(shù)據(jù)auto代碼略
　　if auto＝＝True：
　 if newtemp<＝temp1 and flag＝＝False：
　　　 ①　　　　
　　　 #打開加熱器，代碼略
　 elif ②　　　　 and flag＝＝ True：
　　　 flag＝False
　　　 #關(guān)閉加熱器，代碼略
　else：
　 #執(zhí)行手動控制加熱器，代碼略
　#將newtemp，flag等數(shù)據(jù)傳輸?shù)椒?wù)器。代碼略
　sleep(1000*5*60)　#延時5分鐘
(5)該系統(tǒng)使用后發(fā)現(xiàn)通過瀏覽器遠(yuǎn)程訪問系統(tǒng)控制網(wǎng)頁，能直接開啟或關(guān)閉加熱器。小明希望實(shí)際溫度低于20攝氏度時，加熱器開啟加熱，當(dāng)溫度高于26攝氏度時，加熱器關(guān)閉加熱，但在實(shí)際應(yīng)用中自動模式下溫度低于20攝氏度時，加熱器沒有開啟，而此時手動模式開啟正常，請分析可能的原因
______________________________________________________________________
______________________________________________________________________
(注：回答2項(xiàng)，1項(xiàng)正確得1分)。
14.小紅從網(wǎng)上下載收集了浙江省部分海島2022年10月～12月的天氣預(yù)報信息，存儲在Excel文件中，包含預(yù)報時間、站點(diǎn)編號、浪高、溫度、風(fēng)向以及風(fēng)速，如圖a所示，海浪等級信息如圖b所示，她要編寫一個Python程序快速對海島天氣數(shù)據(jù)進(jìn)行分析。
圖a
浪高值 風(fēng)浪等級
0 無浪
1～10 微浪
10～25 小浪
25～100 中浪
>100 大浪
圖b
(1)為了獲取該數(shù)據(jù)集中預(yù)報信息最多的海島站點(diǎn)編號及該島某月各風(fēng)浪等級的預(yù)報次數(shù)，小紅需要對圖a所示的表中數(shù)據(jù)進(jìn)行整理，下列說法正確的是________。(多選，填字母)
A.第4行和第5行數(shù)據(jù)重復(fù)，刪除其中一行即可
B.通過檢測發(fā)現(xiàn)D7單元格的數(shù)據(jù)存在錯誤，應(yīng)進(jìn)行修正
C.刪除“風(fēng)向”和“風(fēng)速”兩列數(shù)據(jù)，不影響分析結(jié)果
D.“浪高”為0的數(shù)據(jù)沒有任何價值，可以直接刪除
(2)小紅利用整理好的數(shù)據(jù)，編寫并運(yùn)行程序，求出預(yù)報信息最多的海島站點(diǎn)編號并根據(jù)給定月份，分析該月的數(shù)據(jù)并可視化，可視化結(jié)果如圖c所示，請在劃線處填入合適的代碼。
import pandas as pd
import matplotlib.pyplot as plt
plt.rcParams['font.sans－serif']＝['KaiTi'，'SimHei'，'FangSong']　#設(shè)置中文字體顯示
df＝pd.read_excel(″浙江省海島預(yù)報信息.xls″)
def zhengli()：　#整理數(shù)據(jù)
　 df[″風(fēng)浪等級″]＝″無浪″
　 for i in df.index：
　 t＝df[″浪高″][i]
if t>100：
　　　 df[″風(fēng)浪等級″][i]＝″大浪″
　elif t>25：
　　　 df[″風(fēng)浪等級″][i]＝″中浪″
　elif t>10：
　　 　df[″風(fēng)浪等級″][i]＝″小浪″
　①　　　　
　　　 df[″風(fēng)浪等級″][i]＝″微浪″
for i in df. index：#截取″預(yù)報時間″列中的月份日期信息，添加到″月份″列和″日期″列
　 df.at[i，″月份″]＝str(df.at[i，″預(yù)報時間″])[5：7]
　 df.at[i，″日期″]＝str(df.at[i，″預(yù)報時間″])[8：10]
zhengli()
df1＝df.groupby(②　　　　， as_index＝False).count()
df1_sort＝df1.sort_values(″預(yù)報時間″ ， ascending＝False，ignore_index＝True)
top＝df1_sort[″站點(diǎn)編號″][0]
print(″預(yù)報信息最多的海島站點(diǎn)編號是：″， top)
df2＝df[df.站點(diǎn)編號＝＝top]
m＝input(″請輸入要查詢的月份：″)
df3＝③　　　　
df3＝df3.groupby(″風(fēng)浪等級″).預(yù)報時間.count()
x＝df3.index
y＝df3.values
plt.plot(x，y)
#設(shè)置繪圖參數(shù)，繪制如圖c所示線形圖，代碼略。
圖c
(3)觀察圖c圖表可知，該海島12月出現(xiàn)天數(shù)最多的風(fēng)浪等級為　　　　。
15.某倉庫有一排連續(xù)相鄰的貨位，現(xiàn)有多批貨物需要臨時存放，每批貨物占用不同長度的相鄰貨位，其中將未放置貨物的連續(xù)貨位，稱為一個“空閑區(qū)間”。在貨物存放和搬離的過程中，可能會產(chǎn)生大量的“碎片區(qū)間”(碎片區(qū)間是長度小于等于10的連續(xù)貨位)。為解決上述問題，小辰設(shè)計一種貨位分配方案，即每次都將新貨物存放在滿足存放要求且最長的空閑區(qū)間的頭部(不會出現(xiàn)貨物無法存放的情況)，并在貨物搬離后將連續(xù)的空閑區(qū)間合并。
若倉庫貨位長度n為100，按圖a所示的操作順序執(zhí)行(操作類型為0表示存放、1表示搬離)，則貨物存放和搬離過程如圖b所示，最終貨物的存放方案存儲在“區(qū)間分配表”中，如圖c所示。表中區(qū)間按地址順序存放且貨物編號為“0”表示該區(qū)間為空閑區(qū)間，最終可知該存放方案的碎片區(qū)間個數(shù)為1。編寫程序，根據(jù)分配方案執(zhí)行貨物存放或搬離操作，并統(tǒng)計操作后碎片區(qū)間的數(shù)量。請回答以下問題：
貨物編號 操作類型 貨物長度
1 0 30
2 0 20
1 1
3 0 30
4 0 20
3 1
圖a
圖b
起始地址 區(qū)間長度 貨物編號
0 20 4
20 10 0
30 20 2
50 50 0
圖c　區(qū)間分配表
貨物編號 操作類型 貨物長度
1 0 40
2 0 30
3 0 50
4 0 60
1 1
5 0 35
3 1
6 0 40
4 1
圖d
(1)若倉庫貨位長度n為200，需要執(zhí)行的貨物操作流程如圖d所示，則執(zhí)行完流程后，“區(qū)間分配表”中碎片區(qū)間的起始地址和區(qū)間長度分別為________。
(2)為了能夠快速地獲取到最長空閑區(qū)間的信息，小辰創(chuàng)建了包含所有空閑區(qū)間的空閑鏈表，并在貨物放置和搬離過程中保持鏈表按照區(qū)間長度降序。為實(shí)現(xiàn)上述功能定義如下sort(k)函數(shù)，參數(shù)k表示待插入鏈表的節(jié)點(diǎn)地址。函數(shù)功能為將新節(jié)點(diǎn)插入至空閑鏈表中并保持降序。鏈表節(jié)點(diǎn)lst[k]中的地址k為區(qū)間的起始地址，數(shù)據(jù)域lst[k][0]為區(qū)間長度，指針域lst[k][1]、lst[k][2]分別為前驅(qū)指針和后繼指針，請將以下代碼補(bǔ)充完整。
def sort(k)：　#降序鏈表
　 global head　#可以在函數(shù)中修改 head 變量的值
　 q＝－1；p＝head
　 while p！＝－1 and lst[k][0]<＝lst[p][0]：
　　 q＝p
　　 p＝lst[p][2]
　 if p＝＝head：
　　 lst[p][1]＝k
　　 head＝k
　 elif p＝＝－1：
　　 lst[q][2]＝k
　 else：
　　 lst[q][2]＝k
　　 lst[p][1]＝k
　 　　　　　　　
　 lst[k][2]＝p
(3)實(shí)現(xiàn)上述功能的部分 Python 程序代碼如下，請在劃線處填入合適的代碼。
def delete(k)：
　 #從空閑鏈表中刪除地址為 k 的節(jié)點(diǎn)，同時更新頭指針 head，代碼略
def alloc(num，length)：
　 global head
　 for i in range(len(fq))：
　 if fq[i][0]＝＝head and fq[i][2]＝＝0：
　　　break
　 fq[i][1]＝length
　 fq[i][2]＝num
　 sy＝lst[head][0]－length
　 ①　　　　
　 delete(head)　#刪除頭節(jié)點(diǎn)
if sy>0：
　 fq.insert(i＋1，[k，sy，0])　#在i之后添加新的空閑區(qū)
　 lst[k]＝[sy，－1，－1]　#更新空閑區(qū)長度
　 sort(k)
def releace(num)：
　 for i in range(len(fq))：
　　 if num＝＝fq[i][2]：
　　　 break
　　②　　　　
　　lst[fq[i][0]]＝[fq[i][1]，－1，－1]
　　#若區(qū)間 fq[i]和 fq[i＋1]為相鄰空閑區(qū)間則合并，并修改“區(qū)間分配表”和“空閑鏈表”，代碼略
　　if i！＝0 and fq[i－1][2]＝＝0：
　　 fq[i－1][1]＋＝fq[i][1]
　　 ③　　　　
　　 delete(fq[i－1][0])
　　fq.pop(i)　#刪除“區(qū)間分配表”索引為i的區(qū)間
　　 sort(fq[i－1][0])
　 else：
　　 sort(fq[i][0])
#按行讀取操作流程，并將數(shù)據(jù)存儲值列表d中，其中d[i][0]和d[i][1]分別表示區(qū)間i的貨物編號和操作類型，d[i][2]表示存儲操作時的貨物長度。
n＝200　#貨位長度
fq＝[[0，n，0]]　#區(qū)間分配表
lst＝[[0，－1，－1] for i in range(n)]　#空閑鏈表
head＝0；lst[head][0]＝n
for i in range(len(d))：
　 if d[i][1]＝＝″0″：
　　 alloc(int(d[i][0])，int(d[i][2]))
　 else：
　　 releace(int(d[i][0]))
#遍歷鏈表lst，統(tǒng)計碎片區(qū)間數(shù)量并輸出，代碼略
非選擇題專項(xiàng)(一)
13.(1)B　(2)C　(3)ACD　(4)①flag＝True
②newtemp>＝temp2　(5)溫度傳感器損壞或服務(wù)器閾值設(shè)置不正確或web服務(wù)器程序代碼有誤
解析　(1)A選項(xiàng)智能終端負(fù)責(zé)數(shù)據(jù)采集與傳輸，并控制執(zhí)行器工作。C選項(xiàng)概要設(shè)計階段包括系統(tǒng)的模塊結(jié)構(gòu)設(shè)計、系統(tǒng)物理配置、數(shù)據(jù)庫管理系統(tǒng)選擇等。
(2)通過瀏覽器遠(yuǎn)程手動模式開啟加熱器操作時指令數(shù)據(jù)的傳輸過程為從瀏覽器至Web服務(wù)器，再從Web服務(wù)器傳輸至智能終端。(3)智能終端通過溫度傳感器采集的數(shù)據(jù)由智能終端經(jīng)過IoT模塊發(fā)送到Web服務(wù)器，再接收服務(wù)器的控制指令打開或關(guān)閉加熱器。(4)①flag表示加熱器的工作狀態(tài)，其值為False且條件newtemp<＝temp1成立，設(shè)置flag為True。②加熱過程中，若溫度值newtemp大于等于閾值temp2，則關(guān)閉加熱器。(5)略。
14.(1)BC　(2)①elif t>＝1：或elif t>0：　②″站點(diǎn)編號″　③df2[df2.月份＝＝m]　(3)微浪
解析　(1)略。(2)①除此外還有″微浪″和″無浪″情況，因此加上微浪的條件。②預(yù)報信息最多的海島站點(diǎn)編號，因此需對海島站點(diǎn)編號進(jìn)行分組。③輸入要查詢的月份m，因此需篩選出符合條件的數(shù)據(jù)。(3)略。
15.(1)35　5　(2)lst[k][1]＝q　(3)①k＝head＋length
②fq[i][2]＝0　③lst[fq[i－1][0]][0]＋＝fq[i][1]
解析　(1)35 5，本題使用了一種稱為“最壞適配”的算法，即每次都從剩余空閑區(qū)間中選擇最大的區(qū)間用于分配，這樣的算法能夠使空閑區(qū)間的大小趨于均勻，盡量避免出現(xiàn)無法使用的碎片區(qū)間。(2)lst[k][1]＝q，將地址為k的節(jié)點(diǎn)降序連接至雙向鏈表lst中。(3)①k＝head＋length；②fq[i][2]＝0；③lst[fq[i－1][0]][0]＋＝fq[i][1]。本題的核心問題在于分配和釋放區(qū)間的過程中，需要同時維護(hù)好“區(qū)間分配表”fq和“空閑鏈表”lst。為實(shí)現(xiàn)快速的區(qū)間分配和合并，空閑鏈表lst的節(jié)點(diǎn)的地址為區(qū)間分配表fq中空閑區(qū)間的起始地址。函數(shù)alloc(num，length)中，需要從lst的頭節(jié)點(diǎn)中分配出一個長度為length的區(qū)域。為實(shí)現(xiàn)上述功能，需要先將lst中的頭節(jié)點(diǎn)刪除，在fq中修改好分區(qū)后，再將剩余空閑區(qū)間重新連接至降序雙向鏈表lst中。函數(shù)release(num)，則用于將編號為num的區(qū)間刪除，即釋放num區(qū)間并轉(zhuǎn)換為空閑區(qū)間。新增的空閑區(qū)間需要和前后區(qū)間進(jìn)行對比，若前后存在空閑區(qū)間，則需與新空閑區(qū)間進(jìn)行合并。上述的區(qū)間的釋放與更新都需要修改fq和lst中的區(qū)間。(共21張PPT)
非選擇題專項(xiàng)(一)
第四部分　考前題型特訓(xùn)
二、非選擇題(本大題共3小題，其中第13題9分，第14題8分，第15題9分，共26分)
13.小明為蔬菜大棚搭建了一個簡易溫度監(jiān)測控制系統(tǒng)，可以設(shè)定閾值，系統(tǒng)提供自動及手動工作模式。自動工作模式時，系統(tǒng)會自動根據(jù)溫度變化情況控制是否加熱，使蔬菜大棚保持適合的溫度。手工工作模式，可以通過瀏覽器遠(yuǎn)程訪問系統(tǒng)控制網(wǎng)頁，直接開啟或關(guān)閉加熱器。該系統(tǒng)結(jié)構(gòu)示意圖如圖所示。系統(tǒng)為B/S開發(fā)模式，使用micro：bit作為智能終端，溫度傳感器采集數(shù)據(jù)。傳感器采集的數(shù)據(jù)由智能終端經(jīng)IoT模塊發(fā)送到Web服務(wù)器，用戶可通過瀏覽器查詢實(shí)時和歷史數(shù)據(jù)。執(zhí)行器用于實(shí)現(xiàn)溫度的控制。根據(jù)以上功能描述，請回答下列問題：
(1)下列關(guān)于該信息系統(tǒng)的說法，正確的是　　　　(單選，填字母)。
A.在該信息系統(tǒng)中，智能終端的作用相當(dāng)于中央處理器CPU
B.在該信息系統(tǒng)中，傳感器和執(zhí)行器沒有智能終端的控制不能正常工作
C.概要設(shè)計階段，包括系統(tǒng)的模塊結(jié)構(gòu)設(shè)計、系統(tǒng)物理配置和數(shù)據(jù)庫設(shè)計三大部分
(2)通過瀏覽器遠(yuǎn)程手動模式開啟加熱器操作時，指令數(shù)據(jù)的傳輸過程為　　　　。(單選，填字母)
A.瀏覽器→數(shù)據(jù)庫→智能終端 B.瀏覽器→智能終端→服務(wù)器
C.瀏覽器→Web服務(wù)器→智能終端
(3)根據(jù)題意，下列功能需要在智能終端程序中實(shí)現(xiàn)的是　　　　。(多選，填字母：A.采集溫度傳感器上的數(shù)據(jù)/B.處理瀏覽器訪問請求/C.接收服務(wù)器指令/D.打開或關(guān)閉加熱器)。(注：全部選對的得2分，選對但不全的得1分，不選或有選錯的得0分)
(5)該系統(tǒng)使用后發(fā)現(xiàn)通過瀏覽器遠(yuǎn)程訪問系統(tǒng)控制網(wǎng)頁，能直接開啟或關(guān)閉加熱器。小明希望實(shí)際溫度低于20攝氏度時，加熱器開啟加熱，當(dāng)溫度高于26攝氏度時，加熱器關(guān)閉加熱，但在實(shí)際應(yīng)用中自動模式下溫度低于20攝氏度時，加熱器沒有開啟，而此時手動模式開啟正常，請分析可能的原因__________________
______________________________________________________________________
(注：回答2項(xiàng)，1項(xiàng)正確得1分)。
答案　(1)B　(2)C　(3)ACD　(4)①flag＝True　②newtemp>＝temp2　(5)溫度傳感器損壞或服務(wù)器閾值設(shè)置不正確或web服務(wù)器程序代碼有誤
解析　(1)A選項(xiàng)智能終端負(fù)責(zé)數(shù)據(jù)采集與傳輸，并控制執(zhí)行器工作。C選項(xiàng)概要設(shè)計階段包括系統(tǒng)的模塊結(jié)構(gòu)設(shè)計、系統(tǒng)物理配置、數(shù)據(jù)庫管理系統(tǒng)選擇等。
(2)通過瀏覽器遠(yuǎn)程手動模式開啟加熱器操作時指令數(shù)據(jù)的傳輸過程為從瀏覽器至Web服務(wù)器，再從Web服務(wù)器傳輸至智能終端。(3)智能終端通過溫度傳感器采集的數(shù)據(jù)由智能終端經(jīng)過IoT模塊發(fā)送到Web服務(wù)器，再接收服務(wù)器的控制指令打開或關(guān)閉加熱器。(4)①flag表示加熱器的工作狀態(tài)，其值為False且條件newtemp<＝temp1成立，設(shè)置flag為True。②加熱過程中，若溫度值newtemp大于等于閾值temp2，則關(guān)閉加熱器。(5)略。
14.小紅從網(wǎng)上下載收集了浙江省部分海島2022年10月～12月的天氣預(yù)報信息，存儲在Excel文件中，包含預(yù)報時間、站點(diǎn)編號、浪高、溫度、風(fēng)向以及風(fēng)速，如圖a所示，海浪等級信息如圖b所示，她要編寫一個Python程序快速對海島天氣數(shù)據(jù)進(jìn)行分析。
圖a
浪高值 風(fēng)浪等級
0 無浪
1～10 微浪
10～25 小浪
25～100 中浪
>100 大浪
圖b
(1)為了獲取該數(shù)據(jù)集中預(yù)報信息最多的海島站點(diǎn)編號及該島某月各風(fēng)浪等級的預(yù)報次數(shù)，小紅需要對圖a所示的表中數(shù)據(jù)進(jìn)行整理，下列說法正確的是　　　　。(多選，填字母)
A.第4行和第5行數(shù)據(jù)重復(fù)，刪除其中一行即可
B.通過檢測發(fā)現(xiàn)D7單元格的數(shù)據(jù)存在錯誤，應(yīng)進(jìn)行修正
C.刪除“風(fēng)向”和“風(fēng)速”兩列數(shù)據(jù)，不影響分析結(jié)果
D.“浪高”為0的數(shù)據(jù)沒有任何價值，可以直接刪除
(2)小紅利用整理好的數(shù)據(jù)，編寫并運(yùn)行程序，求出預(yù)報信息最多的海島站點(diǎn)編號并根據(jù)給定月份，分析該月的數(shù)據(jù)并可視化，可視化結(jié)果如圖c所示，請在劃線處填入合適的代碼。
import pandas as pd
import matplotlib.pyplot as plt
plt.rcParams['font.sans－serif']＝['KaiTi'，'SimHei'，'FangSong']　#設(shè)置中文字體顯示
df＝pd.read_excel(″浙江省海島預(yù)報信息.xls″)
def zhengli()：　#整理數(shù)據(jù)
圖c
(3)觀察圖c圖表可知，該海島12月出現(xiàn)天數(shù)最多的風(fēng)浪等級為　　　　。
答案　(1)BC　(2)①elif t>＝1：或elif t>0：　②″站點(diǎn)編號″　③df2[df2.月份＝＝m]　(3)微浪
解析　(1)略。(2)①除此外還有″微浪″和″無浪″情況，因此加上微浪的條件。
②預(yù)報信息最多的海島站點(diǎn)編號，因此需對海島站點(diǎn)編號進(jìn)行分組。③輸入要查詢的月份m，因此需篩選出符合條件的數(shù)據(jù)。(3)略。
15.某倉庫有一排連續(xù)相鄰的貨位，現(xiàn)有多批貨物需要臨時存放，每批貨物占用不同長度的相鄰貨位，其中將未放置貨物的連續(xù)貨位，稱為一個“空閑區(qū)間”。在貨物存放和搬離的過程中，可能會產(chǎn)生大量的“碎片區(qū)間”(碎片區(qū)間是長度小于等于10的連續(xù)貨位)。為解決上述問題，小辰設(shè)計一種貨位分配方案，即每次都將新貨物存放在滿足存放要求且最長的空閑區(qū)間的頭部(不會出現(xiàn)貨物無法存放的情況)，并在貨物搬離后將連續(xù)的空閑區(qū)間合并。
若倉庫貨位長度n為100，按圖a所示的操作順序執(zhí)行(操作類型為0表示存放、1表示搬離)，則貨物存放和搬離過程如圖b所示，最終貨物的存放方案存儲在“區(qū)間分配表”中，如圖c所示。表中區(qū)間按地址順序存放且貨物編號為“0”表示該區(qū)間為空閑區(qū)間，最終可知該存放方案的碎片區(qū)間個數(shù)為1。編寫程序，根據(jù)分配方案執(zhí)行貨物存放或搬離操作，并統(tǒng)計操作后碎片區(qū)間的數(shù)量。請回答以下問題：
貨物編號 操作類型 貨物長度
1 0 30
2 0 20
1 1
3 0 30
4 0 20
3 1
圖a
圖b
起始 地址 區(qū)間 長度 貨物
編號
0 20 4
20 10 0
30 20 2
50 50 0
圖c　區(qū)間分配表
貨物編號 操作類型 貨物長度
1 0 40
2 0 30
3 0 50
4 0 60
1 1
5 0 35
3 1
6 0 40
4 1
圖d
(1)若倉庫貨位長度n為200，需要執(zhí)行的貨物操作流程如圖d所示，則執(zhí)行完流程后，“區(qū)間分配表”中碎片區(qū)間的起始地址和區(qū)間長度分別為　　　　。
(2)為了能夠快速地獲取到最長空閑區(qū)間的信息，小辰創(chuàng)建了包含所有空閑區(qū)間的空閑鏈表，并在貨物放置和搬離過程中保持鏈表按照區(qū)間長度降序。為實(shí)現(xiàn)上述功能定義如下sort(k)函數(shù)，參數(shù)k表示待插入鏈表的節(jié)點(diǎn)地址。函數(shù)功能為將新節(jié)點(diǎn)插入至空閑鏈表中并保持降序。鏈表節(jié)點(diǎn)lst[k]中的地址k為區(qū)間的起始地址，數(shù)據(jù)域lst[k][0]為區(qū)間長度，指針域lst[k][1]、lst[k][2]分別為前驅(qū)指針和后繼指針，請將以下代碼補(bǔ)充完整。
答案　(1)35　5　(2)lst[k][1]＝q　(3)①k＝head＋length　②fq[i][2]＝0　③lst[fq[i－1][0]][0]＋＝fq[i][1]
解析　(1)35 5，本題使用了一種稱為“最壞適配”的算法，即每次都從剩余空閑區(qū)間中選擇最大的區(qū)間用于分配，這樣的算法能夠使空閑區(qū)間的大小趨于均勻，盡量避免出現(xiàn)無法使用的碎片區(qū)間。(2)lst[k][1]＝q，將地址為k的節(jié)點(diǎn)降序連接至雙向鏈表lst中。(3)①k＝head＋length；②fq[i][2]＝0；③lst[fq[i－1][0]][0]＋＝fq[i][1]。本題的核心問題在于分配和釋放區(qū)間的過程中，需要同時維護(hù)好“區(qū)間分配表”fq和“空閑鏈表”lst。為實(shí)現(xiàn)快速的區(qū)間分配和合并，空閑鏈表lst的節(jié)點(diǎn)的地址為區(qū)間分配表fq中空閑區(qū)間的起始地址。函數(shù)alloc(num，length)中，需要從lst的頭節(jié)點(diǎn)中分配出一個長度為length的區(qū)域。為實(shí)現(xiàn)上述功能，需要先將lst中的頭節(jié)點(diǎn)刪除，在fq中修改好分區(qū)后，再將剩余空閑區(qū)間重新連接至降序雙向鏈表lst中。函數(shù)release(num)，則用于將編號為num的區(qū)間刪除，即釋放num區(qū)間并轉(zhuǎn)換為空閑區(qū)間。新增的空閑區(qū)間需要和前后區(qū)間進(jìn)行對比，若前后存在空閑區(qū)間，則需與新空閑區(qū)間進(jìn)行合并。上述的區(qū)間的釋放與更新都需要修改fq和lst中的區(qū)間。

展開更多......

收起↑