資源簡(jiǎn)介

專題19　基于數(shù)據(jù)結(jié)構(gòu)的算法實(shí)現(xiàn)
知識(shí)點(diǎn)　鏈表在數(shù)據(jù)組織中的作用
1.使用Python編寫(xiě)按文件后綴名進(jìn)行分類的程序。要求實(shí)現(xiàn)的功能為：從文件夾中讀取所有文件名，存儲(chǔ)到file列表中，如：[[″000.mp3″]，[″001.pptx″]，[″002.pptx″]，[″003.jpg″]，…，[″099.jpg″]]，然后按文件后綴名進(jìn)行分類，并統(tǒng)計(jì)每個(gè)類別下文件的數(shù)量，輸出結(jié)果如圖所示。
(1)定義如下ft(s)函數(shù)，參數(shù)s為文件名(如″000.mp3″)。函數(shù)功能是將文件名中的后綴名取出，并返回該后綴名。完成程序空白處代碼。
def ft(s)：
n＝len(s)－1
while________：
n－＝1
return s[n＋1：]
(2)按后綴名將文件名分為五類，分別為“mp3、pptx、jpg、xlsx、docx”。分類的具體代碼如下，請(qǐng)?jiān)趧澗€處填入合適的代碼。
#從目錄讀取文件名到file列表過(guò)程略
for i in range(len(file))：
file[i].append(－1)　#append()功能：為列表增加一個(gè)元素
fhead＝[]
for i in range(len(file))：
①________
j＝0
while jj＋＝1
if jfile[i][1]＝fhead[j][1]
②________
else：
fhead.append([a，i])#append()功能：為列表增加一個(gè)元素
(3)按后綴名類型將文件名輸出，效果如圖所示(文件名輸出每10個(gè)換一行)。具體代碼如下，請(qǐng)?jiān)趧澗€處填入合適的代碼。
mp3類型的文件： 005.mp3 000.mp3 共2個(gè) pptx類型的文件： 007.pptx 006.pptx 002.pptx 001.pptx 共4個(gè) jpg類型的文件： 099.jpg 008.jpg 0004.jpg 003.jpg 共4個(gè)
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)＋″個(gè)″)
2.某學(xué)校工會(huì)舉行飛鏢大賽，共有n位老師報(bào)名參賽，每位選手共擲5支鏢，每鏢得分為0至10分，選手總分為5鏢成績(jī)之和，每位選手的比賽數(shù)據(jù)記錄在文本文件中，如圖a所示。
處理要求：數(shù)據(jù)讀入數(shù)組data中，計(jì)算出每位選手的總分，在不改變數(shù)據(jù)在原數(shù)組data中的位置的條件下，按總分從高到低輸出選手的編號(hào)和總分。
(1)主程序。采用鏈表結(jié)構(gòu)處理數(shù)據(jù)。程序運(yùn)行結(jié)果如圖b所示。請(qǐng)?jiān)诔绦蛑袆澗€處填入合適的代碼。
data＝readdata(″scores.txt″)　#讀取數(shù)據(jù)，計(jì)算總分
print(″處理前的數(shù)據(jù)為：\n″，data)
n＝len(data)
flag＝[True]*n　#標(biāo)記數(shù)據(jù)被使用情況
head＝findmax()　#返回data中可使用狀態(tài)最大數(shù)的位置
k＝head
for i in range(1，n)：
　 posi＝findmax()
　 data[k].append(posi)
　 ______________
data[k].append(－1)
print(″處理后的數(shù)據(jù)為： \n″，data)
print(″從高分到低分輸出為：″)
output(head)
(2)編寫(xiě)readdata函數(shù)，功能為從文本文件讀取數(shù)據(jù)，計(jì)算出總分，返回列表。代碼如下，請(qǐng)?jiān)诔绦蛑袆澗€處填入合適的代碼。
def readdata(filename)：
f＝open(filename)
line＝f.readline()
lst＝[]
while line：　#獲取每位選手的編號(hào)和總分?jǐn)?shù)據(jù)
line＝line.split(″，″)
s＝0
for i in range(1，len(line))：
　　　　 __________
lst.append([line[0]，s])
line＝f.readline()
return lst
(3)編寫(xiě) findmax函數(shù)，功能為返回data中可使用狀態(tài)最大數(shù)的位置pos，并設(shè)置該數(shù)的使用狀態(tài)為False。請(qǐng)?jiān)诔绦蛑袆澗€處填入合適的代碼。
def findmax()：
maxnum＝0
for i in range(n)：
if ①________：
　　　 maxnum＝data[i][1]
　　　 pos＝i
②________
return pos
(4)編寫(xiě)output函數(shù)，功能為從高分到低分輸出選手的信息。代碼如下，加框處的代碼有誤，請(qǐng)改正。
def output(q)：
while ：
print(data[q][0：2]，end＝″>>″)
q＝data[q][2]
print(″NULL″)　#表示結(jié)束
3.王老師組織同學(xué)參加答題游戲，由“A”，“B”，“C”，“D”4個(gè)小組參與游戲，每個(gè)小組由k名學(xué)生組成，由1人代表小組答題。抽簽確定開(kāi)始的小組，每一輪按A→B→C→D→A順序輪流作答，每答對(duì)一題加10分，每個(gè)選手答錯(cuò)一題即遭淘汰，由同組下一個(gè)選手補(bǔ)上，若該組所有選手都已淘汰，則該組即遭淘汰，其他小組繼續(xù)輪流作答，直到剩下最后一組，即為獲勝小組，若最后一輪沒(méi)有小組幸存，則分?jǐn)?shù)最高的小組獲勝。
(1)若每組有兩個(gè)選手，從A組開(kāi)始，經(jīng)過(guò)3輪答題，答題結(jié)果為“TFTF”，“FFFT”，“FTF”(答對(duì)用T表示，答錯(cuò)用F表示)，則獲勝的小組是________。
(2)王老師用鏈表數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)了答題游戲的算法，并用Python編寫(xiě)程序模擬，實(shí)現(xiàn)了輸入每組人數(shù)，隨機(jī)產(chǎn)生開(kāi)始的小組，輸入每輪答題的情況，輸出最后獲勝的隊(duì)伍。
該程序的Python代碼如下，在劃線處填入合適的代碼，完善程序。
def findmax(score)：
#findmax 函數(shù)功能是在 4 個(gè)小組查找分?jǐn)?shù)最高的小組并輸出，代碼略
def printlist(head)：　#輸出當(dāng)前剩余小組的得分情況
print(dlist[head][0]，″組得分是″，score[dlist[head][0]])
cur＝①________
while cur！＝head：
　 print(dlist[cur][0]，″組得分是″，score [dlist[cur][0]])
　 cur＝dlist[cur][1]
k＝int(input(″輸入每個(gè)組的人數(shù)：″))
code＝″ABCD″
dlist＝[[code[i]，i＋1] for i in range(4) ]　
#初始化鏈表dlist
dlist[3][1]＝②________
head＝randint(0，3)　#隨機(jī)產(chǎn)生開(kāi)始的小組
print(″從″，code[head]，″開(kāi)始答題″)
number＝{}　#存儲(chǔ)每組剩余替補(bǔ)人數(shù)
score＝{}　#存儲(chǔ)每組得分?jǐn)?shù)據(jù)
for i in dlist：
number[i[0]]＝k－1
score[i[0]]＝0
cur＝head
pre＝(head－1)%4
left＝4
while left>1：
ans＝input(″輸入本輪答題情況″)
for j in ans：
if j＝＝″T″：
　　　　　　score[dlist[cur][0]]＋＝10
　　　　 pre＝dlist[pre][1]
　　　　 cur＝dlist[cur][1]
else：
　　　 　if number[dlist[cur][0]]！＝0：
#該組還有替補(bǔ)選手，則繼續(xù)參賽
　　　　　 　number[dlist[cur][0]]－＝1
　　　　　 　pre＝dlist[pre][1]
　　　　　 　cur＝dlist[cur][1]
　　　 　else：
　　　　　　 ③________　#在鏈表中刪除當(dāng)前節(jié)點(diǎn)
　　　　　 　if cur＝＝head：
　　　　　　　 　head＝dlist[cur][1]
　　　　　　 print(dlist[cur][0]，″組被淘汰″)
　　　　　　 cur＝dlist[cur][1]
　　　　　　 left－＝1
if left！＝0：
print(″剩余小組得分情況″)
printlist(head)
if ④________：
print(″最終獲勝的組是：″，dlist[head][0])
else：
findmax(score)
4.操作系統(tǒng)在管理磁盤(pán)時(shí)，會(huì)將磁盤(pán)分為一個(gè)個(gè)“盤(pán)塊”。在為文件分配空間時(shí)，可以將文件裝到離散的盤(pán)塊中。讀取一個(gè)文件時(shí)，首先在目錄結(jié)構(gòu)中找到文件項(xiàng)。從文件項(xiàng)中可以獲取文件名、存儲(chǔ)時(shí)間、該文件在存儲(chǔ)塊中的起始地址等基本信息，但不包含文件具體內(nèi)容，然后在磁盤(pán)文件分配表中找到對(duì)應(yīng)的文件。磁盤(pán)文件分配表如圖a所示。
文件結(jié)束塊用－1表示，空閑盤(pán)塊用0xff表示。
(1)根據(jù)文件的起始地址，能方便地找到文件的其它盤(pán)塊。如圖a中，文件abc在磁盤(pán)中的盤(pán)塊號(hào)依次是________(注：各盤(pán)塊號(hào)用→分隔)。
(2)如果目錄結(jié)構(gòu)損壞，就不能獲取文件的基本信息和起始地址。但我們可以借助文件分配表來(lái)恢復(fù)部分?jǐn)?shù)據(jù)(不考慮恢復(fù)文件名、存儲(chǔ)時(shí)間等信息)。
函數(shù)regain的功能是模擬數(shù)據(jù)恢復(fù)，找到各個(gè)文件的起始地址和大小(盤(pán)塊數(shù)量)，并返回以[[起始地址，文件大小]，…]形式的列表lst。變量allot存儲(chǔ)文件分配表信息。
def regain(allot)：
lst＝[]
visited＝[]　#記錄allot的訪問(wèn)情況
for i in range(len(allot))：
　 if allot[i] ！＝0xff and i not in visited：　#盤(pán)塊i需要處理
　　　 　fsize＝0
　　　 　p＝i
　　　　 while p！＝－1 and p not in visited：
　　　　　 　visited.append(p)
　　　　　 　fsize＋＝1
　　　　　 　p＝allot[p]
　　　　 if p＝＝－1：
　　　　　 　lst.append([i，fsize])
　　　　 else：
　　　　　 　for j in range(len(lst))：
　　　　　　　 　if lst[j][0]＝＝p：
　　　　　　　　 　　lst[j][0]＝i
　　　　　　　　 　　lst[j][1]＝lst[j][1]＋fsize
return lst
若allot為[3，7，13，9，0xff，0xff，0xff，8，－l，－l，0xff，l，0，1l，0xff，0xff]，調(diào)用regain函數(shù)，
①則語(yǔ)句lst[j][1]＝lst[j][1]＋fsize一共會(huì)被執(zhí)行________次。
②如果把while p！＝－1 and p not in visited改寫(xiě)為while p！＝－l，對(duì)程序的影響是________(多選，填字母)。
A.會(huì)增加while的循環(huán)體執(zhí)行次數(shù)
B.返回的lst中的節(jié)點(diǎn)數(shù)量保持不變
C.while循環(huán)不能正常結(jié)束
D.返回的lst中，文件的起始地址部分不正確
(3)在創(chuàng)建文件時(shí)，若新文件需要占據(jù)5個(gè)盤(pán)塊大小，只需要從頭到尾找到空閑盤(pán)塊，并依次鏈接，并把首地址存放到文件項(xiàng)中。為了有效管理空閑塊，我們可以將所有空閑盤(pán)區(qū)(每個(gè)空閑盤(pán)區(qū)可以包括若干個(gè)空閑盤(pán)塊)構(gòu)建到一條空閑鏈freelst中。freelst每個(gè)節(jié)點(diǎn)存儲(chǔ)本空閑盤(pán)區(qū)的盤(pán)塊號(hào)、長(zhǎng)度和指向下個(gè)盤(pán)塊的指針，創(chuàng)建時(shí)把新節(jié)點(diǎn)鏈接到freelst尾部。
如圖b所示，共有3個(gè)空閑盤(pán)區(qū)，盤(pán)塊號(hào)依次為4、5、6、10、14、15。
請(qǐng)?jiān)趧澗€處填上合適的代碼。
def mergefree(allot)：　#mergefree的功能是從頭到尾掃描文件分配表，創(chuàng)建空白盤(pán)區(qū)鏈
freeh＝－1；freelst＝[]
n＝len(allot)
i＝0
while iif allot[i]＝＝0xff：
　　 　　j＝i＋1
　　 　while ①________：
　　　　　 　j＋＝1
　　　　 freelst.append([i，j－i，－1])
　　　 　if freeh＝＝－1：
　　　　 　　freeh＝cur＝len(freelst)－1
　　　　 else：
　　　　　　 freelst[cur][2]＝len(freelst)－1
　　　　　　 ②________
i＝j(luò)＋1
else：
i＋＝1
return freeh，freelst
#讀取文件分配表信息存儲(chǔ)到a11ot中，代碼略
head，freelst＝mergefree(allot)
p＝head
while p！＝－1：　#打印出所有空閑盤(pán)塊號(hào)
for i in range(freelst[p][1])：
print(③________，end＝'，')
p＝freelst[p][2]
5.某工廠每天會(huì)收到多個(gè)訂單，有n臺(tái)機(jī)器對(duì)零件進(jìn)行加工。為減少機(jī)器的損耗，需要在滿足所有訂單加工的情況下(訂單即到即加工)，機(jī)器開(kāi)啟數(shù)量盡量少。若開(kāi)啟n臺(tái)機(jī)器不能滿足訂單即到即加工，則計(jì)算所有訂單最少的平均等待時(shí)間。若給定某天內(nèi)所有的訂單信息，請(qǐng)計(jì)算需要開(kāi)啟的機(jī)器數(shù)量以及訂單平均等待時(shí)間，代碼運(yùn)行效果圖如圖所示。
訂單信息如下：(批次，到達(dá)時(shí)間，加工時(shí)間min) (A1，9：00，30)(A2，11：30，50)(A3，10：40，50)(A4，10：00，60)(A5，9：20，40) (A6，11：00，20)(A7，10：20，40)(A8，9：30，20) 機(jī)器數(shù)量：2 2臺(tái)機(jī)器全部開(kāi)啟，訂單平均等待2.5 min 第1臺(tái)機(jī)器： A1：09：00～09：30，A8：09：30～09：50，A4：10：00～11：00，A3：11：00～11：50 第2臺(tái)機(jī)器： A5：9：20～10：00，A7：10：20～11：00，A6：11：00～11：20，A2：11：30～12：20
(注意：若上一個(gè)訂單結(jié)束時(shí)間為9：00，下一個(gè)訂單開(kāi)啟時(shí)間最早為9：00)。請(qǐng)回答下列問(wèn)題：
(1)上圖所示的例子中，若機(jī)器有10臺(tái)，則只需要開(kāi)啟________臺(tái)機(jī)器。
(2)定義如下data_sort(a)函數(shù)，參數(shù)a為列表，列表中每個(gè)元素包含三個(gè)數(shù)據(jù)項(xiàng)，依次分別對(duì)應(yīng)訂單批次、到達(dá)時(shí)間、加工時(shí)間(時(shí)間均轉(zhuǎn)為分鐘)。該函數(shù)實(shí)現(xiàn)將列表a按照訂單到達(dá)時(shí)間升序排序。
def data_sort(a)：
for i in range(len(a))：
　　for j in ：
　　　 　if________：
　　　　　　 　a[j]，a[j＋1]＝a[j＋1]，a[j]
①劃線處填入的語(yǔ)句為_(kāi)_______，可實(shí)現(xiàn)上述功能。
②若將加框處語(yǔ)句寫(xiě)錯(cuò)為range(i，len(a)－1)，則下列4組數(shù)據(jù)中，若列表a的值為_(kāi)_______(單選，填字母)不能測(cè)試出問(wèn)題。
A.[['A1'，100，30]，['A2'，120，30]，['A3'，110，30]，['A4'，140，30]，['A5'，130，30]]
B.[['A1'，120，30]，['A2'，110，30]，['A3'，100，30]，['A4'，130，30]，['A5'，140，30]]
C.[['A1'，110，30]，['A2'，140，30]，['A3'，130，30]，['A4'，100，30]，['A5'，120，30]]
D.[['A1'，110，30]，['A2'，120，30]，['A3'，130，30]，['A4'，140，30]，['A5'，100，30]]
(3)實(shí)現(xiàn)計(jì)算開(kāi)啟機(jī)器數(shù)量的部分Python程序如下，請(qǐng)?jiān)趧澗€處填入合適的代碼。
def huan(n)：
pass　#將分鐘轉(zhuǎn)換為時(shí)間AA：BB格式，返回值為字符串，代碼略　#讀取文件中的信息，并存儲(chǔ)在列表order中，代碼略
data_sort(order)
n＝int(input(″機(jī)器數(shù)量：″))
for i in range(len(order))：
order[i].append(－1)　#order[i]追加一個(gè)元素－1
mach＝[－1]*n
num，wait＝0，0
for i in range(len(order))：
　 k＝time＝－1
　 for j in ①________：
　 　　t1＝mach[j]
　 if k＝＝－1：
　 　　　　k＝j(luò)
　　　 time＝order[t1][1]＋order[t1][2]
else：
　　　　 t2＝mach[k]
　　　　 if order[t1][1]＋order[t1][2]　　　　　　 k＝j(luò)
　　　　　　 time＝order[t1][1]＋order[t1][2]
if k＝＝－1 or nummach[num]＝i
num＋＝1
else：
order[i][3]＝mach[k]
mach[k]＝i
if time>order[i][1]：
　　　 　wait＋＝time－order[i][1]
　　　 　order[i][1]＝time
if numprint(″只需開(kāi)啟″＋str(num)＋″臺(tái)機(jī)器″)
else：
print(str(n)＋″臺(tái)機(jī)器全部開(kāi)啟，訂單平均等待″＋str(round(wait/len(order)，2))＋″min″)
for i in range(num)：
print('第'＋str(i＋1)＋'臺(tái)機(jī)器：')
p＝mach[i]
ans＝''
while p！＝－1：
ans＝order[p][0]＋'：'＋huan(order[p][1])＋'～'＋huan(order[p][1]＋order[p][2])＋'，'＋ans
p＝③________
print(ans[：－1])
6.程序運(yùn)行時(shí)，以內(nèi)存單元為基本單位對(duì)內(nèi)存進(jìn)行分配，若干個(gè)連續(xù)的內(nèi)存單元稱為一個(gè)內(nèi)存塊，每個(gè)內(nèi)存塊的信息包含首地址和大小。編寫(xiě)Python程序模擬內(nèi)存分配和釋放的過(guò)程。
1)初始化空閑內(nèi)存塊，將信息存儲(chǔ)在鏈表flink中。
2)分配大小為size的內(nèi)存。先依次查找鏈表flink中是否存在不小于size的內(nèi)存塊。若存在且等于size，則將其從鏈表flink中刪除；若存在且大于size，則修改該內(nèi)存塊的信息；若不存在，則對(duì)不連續(xù)的空閑內(nèi)存塊按順序進(jìn)行分配，如果空閑內(nèi)存塊之和仍小于size，則分配失敗。
3)釋放內(nèi)存。將釋放的內(nèi)存塊信息插入鏈表flink，鏈表flink各節(jié)點(diǎn)按首地址從小到大排列。如果釋放的內(nèi)存塊與鏈表中的某個(gè)內(nèi)存塊相鄰，則將它們合并成一個(gè)更大的內(nèi)存塊。
請(qǐng)回答下列問(wèn)題：
(1)初始空閑內(nèi)存塊大小為16，進(jìn)行兩次分配和一次釋放的過(guò)程如圖所示。若繼續(xù)分配大小為8的內(nèi)存塊，________(填寫(xiě)：能/不能)成功。
①初始化空閑內(nèi)存塊，大小為16
②第1次分配，大小為4，分配后空閑12
③第2次分配，大小為8，分配后空閑4
④釋放第1次分配的內(nèi)存，釋放后空閑8(不連續(xù))
(2)定義如下allocate(flink，head，size)函數(shù)，參數(shù)flink是空閑內(nèi)存塊鏈表，head是flink頭指針，size為所需內(nèi)存塊大小。函數(shù)功能為分配size大小的空閑內(nèi)存塊，并返回分配的內(nèi)存塊信息及頭指針head。請(qǐng)?jiān)趧澗€處填入合適的代碼。
def allocate(flink，head，size)：
block＝[]
pre＝cur＝head
while cur ！＝－1：
if flink[cur][1] >＝size：
　　 break
pre＝cur
①________
if cur！＝－1 and flink[cur][1]＝＝size：
block.append([flink[cur][0]，size])
if pre＝＝cur：
　　　　 head＝flink[cur][2]
else：
　　　　 ②________
elif cur！＝－1 and flink[cur][1]>size：
block.append([flink[cur][0]，size])
flink[cur][0]＝flink[cur][0]＋size
flink[cur][1]＝flink[cur][1]－size
if len(block)＝＝0：
#對(duì)不連續(xù)的空閑內(nèi)存塊按順序進(jìn)行分配，如果空閑內(nèi)存塊之和仍小于size，則分配失敗，代碼省略
return block，head
(3)實(shí)現(xiàn)模擬過(guò)程及內(nèi)存釋放的部分Python程序如下，請(qǐng)?jiān)趧澗€處填入合適的代碼。
def release(flink，head，block)：
for i in range(len(block))：
if head＝＝－1：
　　　 　flink.append([block[i][0]，block[i][1]，－1])
　　　 　head＝len(flink)－1
else：
　　　　 pre＝cur＝head
　　　　 while cur ！＝－1：
　　　　　 　if flink[cur][0]>block[i][0]：
　　　　　　 　　break
　　　　 　 　pre＝cur
　　　　　　 cur＝flink[cur][2]
　　　　 flink.append([block[i][0]，block[i][1]，cur])
　　　　 if ①________：
　　　　　 　pre＝len(flink)－1
　　　　 　　head＝len(flink)－1
　　　 　else：
　　　　 　　flink[pre][2]＝len(flink)－1
　　　 　cur＝flink[pre][2]
　　　　 #合并相鄰空閑塊
　　　　 while cur！＝－1：
　　　　　　 if flink[pre][0]＋flink[pre][1]＝＝flink[cur][0]：
　　　　　　　　 ②________
　　　　　　　 　flink[pre][2]＝flink[cur][2]
　　　　　　　 　cur＝flink[cur][2]
　　　　　　　 　continue
　　　　　 　pre＝cur
　　　　　 　cur＝flink[cur][2]
return [[－1，－1，－1]]，head
flink＝[[0，16，－1]]　#初始化空閑內(nèi)存塊鏈表，0：起始地址，16：長(zhǎng)度
head＝0
block1，head＝allocate(flink，head，4)
block2，head＝allocate(flink，head，8)
block1，head＝release(flink，head，block1)
綜合題　基于數(shù)據(jù)結(jié)構(gòu)的算法
1.某工廠生產(chǎn)的產(chǎn)品包含n個(gè)(編號(hào)為0～n－1)組件，其組裝可由多名工人共同協(xié)助完成。組裝時(shí)每個(gè)組件都不可遺漏并能按序完成，有些組件存在前置組件(以下簡(jiǎn)稱“前置”)，即安裝有先后順序。例如，某產(chǎn)品有6個(gè)組件，如圖a所示，組件3的前置是組件1和組件2，即安裝組件3需要在組件1和組件2完成之后。若0～5號(hào)組件的組裝所需單位時(shí)間分別為2，5，2，4，3，5，則在工人數(shù)量不限的情況下，所有組件安裝完成最短需要14個(gè)單位時(shí)間。
圖a
為了梳理產(chǎn)品組件的組裝順序，并計(jì)算所有組件安裝完成所需的最短時(shí)間，編寫(xiě)程序模擬組裝過(guò)程：先同時(shí)組裝前置總數(shù)為0的組件，完成后更新每個(gè)組件的前置總數(shù)，再重復(fù)以上步驟，直至所有組件安裝完畢，程序運(yùn)行結(jié)果如圖b所示，請(qǐng)回答下列問(wèn)題：
編號(hào)為0～5的組件組裝所需單位時(shí)間分別為：[2，5，2，4，3，5] 組件組裝順序：[0，1，4，2，3，5]，安裝完成所需最短時(shí)間：14
圖b
(1)圖a所示產(chǎn)品的1號(hào)組件組裝時(shí)長(zhǎng)若縮短為3個(gè)單位時(shí)間，其它時(shí)間保持不變，則所有組件安裝完成所需最短時(shí)間為_(kāi)_______個(gè)單位時(shí)間。
(2)定義如下cal(a，n)函數(shù)，參數(shù)a列表的每個(gè)元素包含兩項(xiàng)，a[i][1]是組件編號(hào)，a[i][0]是a[i][1]的前置編號(hào)，例如a中某個(gè)元素值為[2, 3]，表示組件2是組件3的前置。該函數(shù)的返回值是列表s和列表pre，其中s記錄所有組件的相互關(guān)系，pre[i]記錄初始情況下組件i的前置總數(shù)。
def cal(a, n)：
pre＝[0]*n
s＝[[0 for i in range(n)] for j in range(n)]　#創(chuàng)建n×n的二維數(shù)組s，元素初始值為0
for i in range(len(a)) ：
x, y＝a[i][0]，a[i][1]
s[x][y]＝1
pre[y]＝________
return pre, s
(3)定義如下 proc(n, s, pre)函數(shù)，該函數(shù)的返回值是列表v, v[i]代表從開(kāi)始到組件i完成組裝所需的最短時(shí)間。請(qǐng)?jiān)趧澗€處填入合適的代碼。
def proc(n, s, pre)：
head＝tail＝0
que＝[0]*n
for i in range(n)：
if pre[i]＝＝0：
　　　　 que[tail]＝i
　　　　tail＋＝1
while ：
x＝que[head]
head＋＝1
for i in range(n) ：
　　　　 if s[x][i]＝＝1：
　　　　　　 pre[i]－＝1
　　　　　　 if pre[i]＝＝0：
　　　　　　　　 que[tail]＝i
　　　　　　　　 tail＋＝1
　　　　　　v[i]＝max(v[i]，①________)
return v
″″″
組裝編號(hào)0～n－1的單個(gè)組件所需時(shí)間存入t列表，組件前置關(guān)系存入a列表，如圖a所需時(shí)間t＝[2，5，2，4，3，5]；a＝[[0，2]，[2，3]，[1，3]，[3，5]，[3，4] ，[4，5]]
″″″
n＝len(t)
print(″編號(hào)為0～″＋str(n－1)＋″的組件組裝所需單位時(shí)間分別為： ″， t)
v＝t[：]
pre，s＝cal(a, n)
v＝proc(n, s, pre)
data＝[0]*n
result＝[i for i in range(n)]　#創(chuàng)建列表result＝[0，1，2，……，n－1]
for i in range(n)：
data[i]＝v[i]－t[i]　#data[i]表示組件i開(kāi)始安裝時(shí)間
for i in range(n－1)：　#按組件開(kāi)始安裝時(shí)間升序排序，開(kāi)始安裝時(shí)間相同時(shí)按組件序號(hào)升序
for j in range(n－1－i):
if data[result[j]]>data[result[j＋1]]：
　　　　②________
print(″組件組裝順序：″，result，″，安裝完成所需最短時(shí)間：″， max(v))
(4)以下選項(xiàng)與題(3)加框處代碼功能相同的是__________(多選，填字母)。(注：全部選對(duì)的得2分，選對(duì)但不全的得1分，不選或有選錯(cuò)的得0分)
A.head！＝tail B.headC.tail<＝n D.len(que)> 0
2.某工廠的業(yè)務(wù)較多，每個(gè)業(yè)務(wù)i都有對(duì)應(yīng)的截止時(shí)間t_i以及收益v_i，工廠每天最多能完成k個(gè)業(yè)務(wù)，且每個(gè)業(yè)務(wù)所需的加工時(shí)長(zhǎng)相同。由于業(yè)務(wù)量多，有時(shí)候無(wú)法完成所有的業(yè)務(wù)，因此工廠管理者需要對(duì)一段時(shí)間內(nèi)的業(yè)務(wù)進(jìn)行規(guī)劃安排，以實(shí)現(xiàn)工廠累計(jì)收益的最大化。
例如工廠3天內(nèi)的業(yè)務(wù)明細(xì)如圖a所示，已知工廠每天能夠完成的業(yè)務(wù)量k為2。為了實(shí)現(xiàn)3天的累計(jì)收益最大化，工廠安排的業(yè)務(wù)方案如圖b所示，這樣工廠能夠獲得最大累計(jì)收益為105。編寫(xiě)程序，實(shí)現(xiàn)在任意時(shí)間段內(nèi)，根據(jù)每個(gè)業(yè)務(wù)的截止時(shí)間和收益，統(tǒng)計(jì)工廠在該時(shí)間段內(nèi)的最大累計(jì)收益。
請(qǐng)回答下列問(wèn)題：
(1)如圖a所示，若加工廠每天能夠完成的業(yè)務(wù)量k為3，則工廠在3天內(nèi)獲得的最大收益為_(kāi)_______。
(2)定義如下insert(lst，head，pos)函數(shù)，參數(shù)lst是一個(gè)由列表模擬的鏈表結(jié)構(gòu)數(shù)據(jù)，其每個(gè)節(jié)點(diǎn)由收益數(shù)據(jù)和指向下一個(gè)位置的指針組成；參數(shù)head是其中一條鏈表的頭指針，由該指針構(gòu)建的鏈表已經(jīng)按收益數(shù)據(jù)升序排列，參數(shù)pos是某個(gè)節(jié)點(diǎn)的指針。函數(shù)功能是將pos節(jié)點(diǎn)插入到head指針指向的鏈表中，并保持鏈表按收益數(shù)據(jù)升序排列，最后返回頭指針數(shù)據(jù)。
def insert(lst，head，pos)：
p＝head
while ：
q＝p
p＝lst[p][1]
if p＝＝head：
lst[pos][1]＝head
head＝pos
else：
lst[pos][1]＝p
　 　________
return head
①若函數(shù)加框處代碼誤寫(xiě)為“l(fā)st[p][0]A.lst＝[ [5，－1]，[3，0]，[2，1]，[4，－1] ] head＝2; pos＝3
B.lst＝[ [5，－1]，[3，3]，[2，1]，[4，－1] ] head＝2; pos＝0
C.lst＝[[5，－1]，[3，－1]，[2，3]，[4，0]] head＝2; pos＝1
D.lst＝[ [5，－1]，[3，3]，[2，－1]，[4，0] ] head＝1; pos＝2
②請(qǐng)?jiān)趧澗€處填入合適的代碼。
(3)實(shí)現(xiàn)對(duì)每個(gè)業(yè)務(wù)完成時(shí)間的合理安排，使得工廠獲得最大累計(jì)收益的部分 Python 程序如下，請(qǐng)?jiān)趧澗€處填入合適的代碼。
def pushlst(info，lst，cur，v)：　#cur 代表開(kāi)始的時(shí)間
if info[cur][1]lst.append([v，－1])　#列表 lst 追加一個(gè)元素
pos＝len(lst)－1
if info[cur][0]＝＝－1：
　　　　 ①________
else：
　　　　 info[cur][0]＝insert(lst，info[cur][0]，pos)
info[cur][1]＋＝1
else：
pos＝info[cur][0]
　　　 if v　　　 #如果 cur>0，嘗試將當(dāng)前業(yè)務(wù)提至前一天完成，代碼略
else：
　　　 　tmpv＝lst[pos][0]　#獲取原安排中收益最少的業(yè)務(wù)收益
　　　　 lst[pos][0]＝v
　　　　p＝lst[pos][1]
　　　　info[cur][0]＝insert(lst，②________，pos)
　　 　　#如果 cur>0，嘗試將原安排中收益最少的業(yè)務(wù)提至前一天完成，代碼略
'''
先輸入規(guī)劃安排的天數(shù) n 和每天能夠處理的最大業(yè)務(wù)量 k，代碼略。
依次輸入 m 個(gè)業(yè)務(wù)的截止時(shí)間 t(t≤n)和收益 v，存儲(chǔ)在數(shù)組 tran 中，如：[[1，25]，[1，10]，[2，15]]，表示共有 3 個(gè)業(yè)務(wù)，第一個(gè)業(yè)務(wù)的截止時(shí)間為 1，收益為 25……，代碼略
'''
info＝[]; lst＝[]; j＝0
for i in range(n)：
info.append([－1，0])　#列表 info 追加一個(gè)元素
while kcur＝tran[k][0]; v＝tran[k][1]　#獲取截止時(shí)間和對(duì)應(yīng)收益
pushlst(info，lst，cur－1，v)
k＋＝1
s＝0
for i in range(n)：
p＝info[i][0]
while p！＝－1：
s＋＝③________
p＝lst[p][1]
print(″最大收益為：″，s)
3.在某圖形操作系統(tǒng)中有N個(gè)窗口，每個(gè)窗口都是一個(gè)兩邊與坐標(biāo)軸分別平行的矩形區(qū)域。窗口邊界上的點(diǎn)也屬于該窗口。窗口之間有層次的區(qū)別，在多于一個(gè)窗口重疊的區(qū)域里，只會(huì)顯示位于頂層的窗口里的內(nèi)容。
當(dāng)你點(diǎn)擊屏幕上一個(gè)點(diǎn)的時(shí)候，你就選擇了處于被點(diǎn)擊位置的最頂層窗口，并且這個(gè)窗口就會(huì)被移到所有窗口的最頂層，而剩余的窗口的層次順序不變。如果你點(diǎn)擊的位置不屬于任何窗口，則系統(tǒng)會(huì)忽略你這次點(diǎn)擊。
如圖a所示的三個(gè)窗口，自頂向下的窗口編號(hào)為3、2、1，窗口用一對(duì)頂點(diǎn)坐標(biāo)(x1, y1)和(x2, y2)表示。若此時(shí)鼠標(biāo)點(diǎn)擊(1，1)位置，則自頂向下的窗口編號(hào)為2、3、1，當(dāng)前選中的為窗口2。
編寫(xiě)程序，根據(jù)已有的窗口信息(已按自底往上的層級(jí)輸入窗口信息)，模擬每次點(diǎn)擊鼠標(biāo)操作，輸出當(dāng)前選中的窗口編號(hào)，若鼠標(biāo)點(diǎn)擊位置不屬于任何窗口，則顯示“ignore”。
(1)根據(jù)題意，某次程序運(yùn)行過(guò)程如圖b所示，第2次鼠標(biāo)點(diǎn)擊后，當(dāng)前選中的窗口號(hào)為_(kāi)_______。
(2)定義如下check(t)函數(shù)，參數(shù)t列表存儲(chǔ)兩個(gè)頂點(diǎn)(x1，y1), (x2，y2)的坐標(biāo)值。函數(shù)功能是對(duì)能構(gòu)成矩形區(qū)域窗口的坐標(biāo)，返回該矩形區(qū)域左下角和右上角的坐標(biāo)值。
def check(t)：
s＝[]
if t[0]！＝t[2] and t[1]！＝t[3]：
if t[0]>t[2]：
　 　　　t[0]，t[2]＝t[2], t[0]
if t[1]>t[3]：
　　 　　t[1]，t[3]＝t[3], t[1]
s＝t
return s
若t＝[4, 1，2，3]，則函數(shù)返回的結(jié)果為_(kāi)_______。
(3)實(shí)現(xiàn)上述功能的Python程序下，請(qǐng)?jiān)趧澗€處填入合適的代碼。
def inside(x, y，w)：
x1, y1, x2, y2＝w[0]，w[1]，w[2]，w[3]
if x1<＝x<＝x2 and y1<＝y(tǒng)<＝y(tǒng)2：
return True
else：
return False
#讀取窗口數(shù)和鼠標(biāo)點(diǎn)擊次數(shù)保存在變量n，m中，代碼略
w＝[]；head＝－1
for i in range(n)：
t＝[int(s) for s in input().split()]　#讀取坐標(biāo)數(shù)據(jù)，保存在列表t中
if len(check(t))！＝0：
w.append([i＋1, t, head])　#i＋1是窗口編號(hào)，從1開(kāi)始
①________
for i in range(m)：
x, y＝[int(s) for s in input().split()]　#讀取鼠標(biāo)點(diǎn)擊數(shù)據(jù)，保存在x, y中
p＝q＝head
while ②__________：
p＝q
q＝w[q][2]
if q＝＝－1：
print(″ignore″)
else：
print(″當(dāng)前選中的窗口號(hào)為：″，w[q][0])
③________
if q！＝head：
　　　 　w[q][2]＝head
head＝q
專題19　基于數(shù)據(jù)結(jié)構(gòu)的算法實(shí)現(xiàn)
知識(shí)點(diǎn)
1.(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]
解析　本題考查鏈表的構(gòu)建和遍歷。(1)文件名最后一個(gè)點(diǎn)的后面為后綴名，因此查找若不是點(diǎn)，繼續(xù)查找。(2)①語(yǔ)句fhead.append([a，i])為列表增加一個(gè)元素，結(jié)合語(yǔ)句print(fhead[i][0]＋″類型的文件：″)，因此a為后綴名，調(diào)用函數(shù)求file[i][0]的后綴。②變量j在fhead遍歷，因此若在該列表中能找到a，則j的值小于len(fhead)，語(yǔ)句file[i][1]＝fhead[j][1]的功能是將該節(jié)點(diǎn)指向原頭指針位置，需更新該鏈表的頭指針。(3)①變量i遍歷列表fhead，因此表示第幾條鏈表，當(dāng)前節(jié)點(diǎn)q從第幾條鏈表的頭指針開(kāi)始遍歷整個(gè)鏈表。②當(dāng)前節(jié)點(diǎn)將指向下一個(gè)位置，鏈表信息存儲(chǔ)在數(shù)組file中。
2.(1)k＝posi　(2)s＋＝int(line[i])　(3)①maxnum解析　(1)查找數(shù)組中的最大值的位置，利用位置關(guān)系串成一個(gè)降序鏈表，最后遍歷鏈表輸出。k是當(dāng)前元素的位置，posi是下一個(gè)元素的位置，找到的數(shù)應(yīng)該在節(jié)點(diǎn)posi后面。(2)readdata函數(shù)功能是讀取“scores.txt”文件，生成一個(gè)二維列表。變量s累計(jì)的總分。(3)findmax函數(shù)找到最大數(shù)所在位置，同時(shí)將該位置設(shè)置為False。(4)遍歷鏈表，輸出節(jié)點(diǎn)相關(guān)數(shù)據(jù)域的內(nèi)容。
3.(1)C　(2)①dlist[head][1]　②0　③dlist[pre][1]＝dlist[cur][1]　④left＝＝1
解析　(1)A組各輪次結(jié)果分別為T(mén)FF，B組為FF，C組為T(mén)FT，D組為FTF，因此獲勝的為C組。(2)①鏈表dlist數(shù)據(jù)區(qū)域值為組的名稱，指針為下一組的索引，已經(jīng)輸出頭節(jié)點(diǎn)的信息，因此當(dāng)前節(jié)點(diǎn)cur的初值為頭節(jié)點(diǎn)的下一節(jié)點(diǎn)。②每一輪按A→B→C→D→A順序輪流作答，將要構(gòu)建一個(gè)循環(huán)鏈表，尾節(jié)點(diǎn)將指向第1個(gè)節(jié)點(diǎn)。③在鏈表中刪除當(dāng)前節(jié)點(diǎn)cur，將前驅(qū)指向當(dāng)前節(jié)點(diǎn)的后繼。④最后剩下一組，該組獲勝。
4.(1)9→4→3→7　(2)①2　②AD　(3)①j解析　本題考查鏈表節(jié)點(diǎn)插入和連續(xù)子串問(wèn)題的處理。(1)文件abc起始地址9，分配表allot[p]表示地址p的下一個(gè)文件的地址，直到allot[p]＝－1為止。(2)題①讀取已記錄的文件，將當(dāng)前文件合并到已記錄的文件中，lst[j][0]＝i重置文件起點(diǎn)，lst[j][1]＝lst[j][1]＋fsize修改文件大小。文件連接關(guān)系：文件1：0→3→9、文件2：1→7→8、文件3：2→13→11→1、文件4：12→0。文件4與文件1合并，文件3與文件2合并，修改大小的語(yǔ)句執(zhí)行2次。②刪除語(yǔ)句后，對(duì)已記錄文件會(huì)重復(fù)訪問(wèn)，因此會(huì)增加while循環(huán)的次數(shù)。循環(huán)結(jié)束后文件必定以－1結(jié)束，合并文件部分代碼將不會(huì)執(zhí)行，無(wú)法完成重置文件起點(diǎn)的操作，所以結(jié)果中的文件起點(diǎn)可能不正確。(3)記錄連續(xù)的空白區(qū)域，實(shí)際上就是連續(xù)重復(fù)子序列問(wèn)題。①空查找連續(xù)的重復(fù)數(shù)據(jù)，注意j的邊界；②空將當(dāng)前新增空白區(qū)域的節(jié)點(diǎn)插入到鏈表freelist末尾，其中cur標(biāo)記了鏈表的尾結(jié)點(diǎn)，代碼freelst[cur][2]＝len(freelst)－1將尾節(jié)點(diǎn)的后繼更新為當(dāng)前新增節(jié)點(diǎn)，同時(shí)移動(dòng)尾節(jié)點(diǎn)標(biāo)記cur為當(dāng)前新增節(jié)點(diǎn)。③空輸出連續(xù)的空白盤(pán)符，freelst[p][1]是p指針?biāo)赶蚬?jié)點(diǎn)的連續(xù)盤(pán)符的長(zhǎng)度，freelst[p][0]是其起始地址，所以從freelst[p][0]開(kāi)始的freelst[p][0]＋i就是連續(xù)盤(pán)符的。
5.(1)3　(2)①a[j][1]>a[j＋1][1]　②A (3)①range(num)　②time>order[i][1]
③order[p][3]
解析　(1)根據(jù)題圖所示，只有訂單A3有等待時(shí)間。若機(jī)器數(shù)量增加，只需要增加一臺(tái)機(jī)器即可滿足所有訂單。(2)①函數(shù)data_sort(a)實(shí)現(xiàn)對(duì)a按照到達(dá)時(shí)間升序排序，則判斷條件為a[j][1]>a[j＋1][1]。②若將加框處的語(yǔ)句寫(xiě)錯(cuò)為range(i，len(a)－1)，則a[0]處只會(huì)被比較一次，若最小值不在a[0]或a[1]，則無(wú)法檢測(cè)此處錯(cuò)誤，故選擇A。(3)根據(jù)輸出的結(jié)果可知mach[i]存儲(chǔ)了每個(gè)機(jī)器最后一個(gè)加工的訂單索引，變量p為該機(jī)器依次加工的訂單索引。變量wait記錄了所有訂單的等待時(shí)間，根據(jù)語(yǔ)句order[i][3]＝mach[k]和mach[k]＝i可知，通過(guò)order[i][3]來(lái)記錄第k臺(tái)機(jī)器的加工索引，故③處填寫(xiě)p＝order[p][3]。根據(jù)程序可知變量time記錄了最早空閑時(shí)間的機(jī)器，根據(jù)語(yǔ)句mach[num]＝i和num＋＝1可知num為開(kāi)啟機(jī)器的數(shù)量，此處新開(kāi)啟一臺(tái)機(jī)器。變量j為mach數(shù)組依次遍歷的索引，而①處填寫(xiě)mach數(shù)組的索引為range(num)。開(kāi)啟一臺(tái)機(jī)器的條件為當(dāng)前數(shù)量少于n臺(tái)且最早空閑機(jī)器的時(shí)間要大于當(dāng)前訂單到達(dá)的時(shí)間，故②處填寫(xiě)numorder[i][1]。
6.(1)能　(2)①cur＝flink[cur][2] ②flink[pre][2]＝flink[cur][2]
(3)①cur＝＝head　②flink[pre][1]＋＝flink[cur][1]
解析　本題考查鏈表的遍歷、插入、刪除等基本操作。(1)有兩塊大小都是4的內(nèi)存塊，要求分配大小為8的內(nèi)存塊，能滿足要求。(2)①更改當(dāng)前節(jié)點(diǎn)中指針遍歷鏈表。cur從頭節(jié)點(diǎn)開(kāi)始，依次遍歷各個(gè)節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)中指針區(qū)域存儲(chǔ)的是下一節(jié)點(diǎn)的位置。②條件flink[cur][0]＝＝size成立，說(shuō)明空閑塊的大小和要求的size相等，要將當(dāng)前空閑內(nèi)存塊從鏈表刪除。(3)①在頭部插入新節(jié)點(diǎn)。內(nèi)存塊釋放，要在flink中增加相應(yīng)的節(jié)點(diǎn)，插入節(jié)點(diǎn)分為在頭部和其他節(jié)點(diǎn)之前插入節(jié)點(diǎn)兩種情況。若待釋放內(nèi)存塊的起始地址小于頭節(jié)點(diǎn)，當(dāng)cur＝＝head時(shí)，則更新頭指針為len(flink)－1。注意：pre＝＝head答案是錯(cuò)的。②將兩個(gè)相鄰空閑塊位置合并為一個(gè)，則當(dāng)前pre和cur節(jié)點(diǎn)可以合并，將cur節(jié)點(diǎn)吸收掉，同時(shí)需修改存儲(chǔ)容量flink[pre][1]。同時(shí)pre節(jié)點(diǎn)指向cur的下一節(jié)點(diǎn)，并且更新pre節(jié)點(diǎn)的空閑內(nèi)存塊大小。
綜合題
1.(1)13　(2)pre[y]＋1　(3)①t[i]＋v[x]　②result[j]，result[j＋1]＝result[j＋1]，result[j]　(4)AB
解析　(1)有三個(gè)組件鏈，分別為0→2→3→5，1→3→5，4→5，在組件3前面兩個(gè)并行的任務(wù)鏈，1號(hào)組件組裝時(shí)長(zhǎng)若縮短為3個(gè)單位時(shí)間，其時(shí)間分為2＋2，3，較長(zhǎng)時(shí)間為4，組件3的時(shí)間為4，合計(jì)為8，而組件4所需時(shí)間為3，因此總共所需時(shí)間為8＋5＝13。(2)函數(shù)cal統(tǒng)計(jì)各個(gè)組件的前置總數(shù)，組件y的前置是組件x，因此組件y的前置總數(shù)pre[y]等于自身加1。(3)①函數(shù)proc功能是計(jì)算每個(gè)組件i從開(kāi)始到組件i完成組裝所需的最短時(shí)間v[i]。先將前置組件數(shù)為0的索引入隊(duì)，因此隊(duì)列元素依次為0，1，4。隊(duì)首為組件0，其后置組件2所需時(shí)間為前置組件0與他本身時(shí)間之和，v[2]＝2＋2＝4。執(zhí)行語(yǔ)句pre[i]－＝1，i入隊(duì)，接著組件1出隊(duì)計(jì)算其后置組件3，即v[3]的時(shí)間為3＋4＝7；接著4出隊(duì)，v[5] 時(shí)間為3＋5＝8。接著2出隊(duì)，v[x]值為4，組件3即v[3]的時(shí)間為4＋4＝8，在兩個(gè)前置中找一個(gè)較大值作為最短時(shí)間。遍歷各個(gè)組件，條件s[x][i]＝＝1表示組件x是組件i的前置，完成組件x所需時(shí)間為v[x]，那么完成組件i總共所需時(shí)間為v[x]＋t[i]。完成組件i可能有多個(gè)前置，完成組件x之前的最長(zhǎng)時(shí)間為v[i]，在兩個(gè)時(shí)間中取出一個(gè)較大值。②data[i]表示組件i開(kāi)始安裝時(shí)間，result存儲(chǔ)的是從小到大排列的組件序號(hào)，當(dāng)條件data[result[j]]>data[result[j＋1]]成立就交換兩個(gè)索引位置。若data[result[j]]和data[result[j＋1]]相等，本身也是按序號(hào)排列的，因此無(wú)需交換。(4)加框處代碼為隊(duì)列不為空的意思，而隊(duì)列的長(zhǎng)度就是n，因此AB選項(xiàng)符合題意。
2.(1)135　(2)①B　②lst[q][1]＝pos (3)①infor[cur][0]＝pos或infor[cur][0]＝len(lst)－1 ②p　③lst[p][0]
解析　(1)將每天的收益進(jìn)行降序排列，第1天的收益分別為25，15，10，第2天收益分別為30，25，20，15，第3天收益5。將第2天的15提前一天完成，代替第1天的10。(2)①修改后，若鏈表為空，則鏈表節(jié)點(diǎn)不存在，B選項(xiàng)插入的值為5，而鏈表節(jié)點(diǎn)的值依次為2，3，4，因此會(huì)出現(xiàn)問(wèn)題。②將節(jié)點(diǎn)p的前驅(qū)節(jié)點(diǎn)q指向新插入的節(jié)點(diǎn)。(3)①?gòu)恼Z(yǔ)句info.append([－1，0])和條件info[cur][1]3.(1)2　(2)[2，1，4，3]　(3)①head＝i或head＝len(w)－1　②q！＝－1 and inside(x，y，w[q][1])＝＝False ③w[p][2]＝w[q][2]
解析　(1)坐標(biāo)(2，2)在第2個(gè)窗口。(2)略。(3)①改變頭指針，語(yǔ)句w.append([i＋1, t, head])將創(chuàng)建一個(gè)新節(jié)點(diǎn)，該節(jié)點(diǎn)指向原頭節(jié)點(diǎn)，因此屬于頭插法，將改變頭指針。②在鏈表節(jié)點(diǎn)中查找所在窗口，當(dāng)鏈表不空時(shí)，如果不是則繼續(xù)查找。③將找到節(jié)點(diǎn)q移動(dòng)到頭節(jié)點(diǎn)的前面，成為新的頭節(jié)點(diǎn)。在鏈表中刪除節(jié)點(diǎn)q，即將其前驅(qū)節(jié)點(diǎn)p指向q的后繼。

展開(kāi)更多......

收起↑