资源简介

专题19　基于数据结构的算法实现
知识点　链表在数据组织中的作用
1.使用Python编写按文件后缀名进行分类的程序。要求实现的功能为：从文件夹中读取所有文件名，存储到file列表中，如：[[″000.mp3″]，[″001.pptx″]，[″002.pptx″]，[″003.jpg″]，…，[″099.jpg″]]，然后按文件后缀名进行分类，并统计每个类别下文件的数量，输出结果如图所示。
(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 jj＋＝1
if jfile[i][1]＝fhead[j][1]
②________
else：
fhead.append([a，i])#append()功能：为列表增加一个元素
(3)按后缀名类型将文件名输出，效果如图所示(文件名输出每10个换一行)。具体代码如下，请在划线处填入合适的代码。
mp3类型的文件： 005.mp3 000.mp3 共2个 pptx类型的文件： 007.pptx 006.pptx 002.pptx 001.pptx 共4个 jpg类型的文件： 099.jpg 008.jpg 0004.jpg 003.jpg 共4个
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所示。
处理要求：数据读入数组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.王老师组织同学参加答题游戏，由“A”，“B”，“C”，“D”4个小组参与游戏，每个小组由k名学生组成，由1人代表小组答题。抽签确定开始的小组，每一轮按A→B→C→D→A顺序轮流作答，每答对一题加10分，每个选手答错一题即遭淘汰，由同组下一个选手补上，若该组所有选手都已淘汰，则该组即遭淘汰，其他小组继续轮流作答，直到剩下最后一组，即为获胜小组，若最后一轮没有小组幸存，则分数最高的小组获胜。
(1)若每组有两个选手，从A组开始，经过3轮答题，答题结果为“TFTF”，“FFFT”，“FTF”(答对用T表示，答错用F表示)，则获胜的小组是________。
(2)王老师用链表数据结构设计了答题游戏的算法，并用Python编写程序模拟，实现了输入每组人数，随机产生开始的小组，输入每轮答题的情况，输出最后获胜的队伍。
该程序的Python代码如下，在划线处填入合适的代码，完善程序。
def findmax(score)：
#findmax 函数功能是在 4 个小组查找分数最高的小组并输出，代码略
def printlist(head)：　#输出当前剩余小组的得分情况
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(″输入每个组的人数：″))
code＝″ABCD″
dlist＝[[code[i]，i＋1] for i in range(4) ]　
#初始化链表dlist
dlist[3][1]＝②________
head＝randint(0，3)　#随机产生开始的小组
print(″从″，code[head]，″开始答题″)
number＝{}　#存储每组剩余替补人数
score＝{}　#存储每组得分数据
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：
#该组还有替补选手，则继续参赛
　　　　　 　number[dlist[cur][0]]－＝1
　　　　　 　pre＝dlist[pre][1]
　　　　　 　cur＝dlist[cur][1]
　　　 　else：
　　　　　　 ③________　#在链表中删除当前节点
　　　　　 　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.操作系统在管理磁盘时，会将磁盘分为一个个“盘块”。在为文件分配空间时，可以将文件装到离散的盘块中。读取一个文件时，首先在目录结构中找到文件项。从文件项中可以获取文件名、存储时间、该文件在存储块中的起始地址等基本信息，但不包含文件具体内容，然后在磁盘文件分配表中找到对应的文件。磁盘文件分配表如图a所示。
文件结束块用－1表示，空闲盘块用0xff表示。
(1)根据文件的起始地址，能方便地找到文件的其它盘块。如图a中，文件abc在磁盘中的盘块号依次是________(注：各盘块号用→分隔)。
(2)如果目录结构损坏，就不能获取文件的基本信息和起始地址。但我们可以借助文件分配表来恢复部分数据(不考虑恢复文件名、存储时间等信息)。
函数regain的功能是模拟数据恢复，找到各个文件的起始地址和大小(盘块数量)，并返回以[[起始地址，文件大小]，…]形式的列表lst。变量allot存储文件分配表信息。
def regain(allot)：
lst＝[]
visited＝[]　#记录allot的访问情况
for i in range(len(allot))：
　 if allot[i] ！＝0xff and i not in visited：　#盘块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]，调用regain函数，
①则语句lst[j][1]＝lst[j][1]＋fsize一共会被执行________次。
②如果把while p！＝－1 and p not in visited改写为while p！＝－l，对程序的影响是________(多选，填字母)。
A.会增加while的循环体执行次数
B.返回的lst中的节点数量保持不变
C.while循环不能正常结束
D.返回的lst中，文件的起始地址部分不正确
(3)在创建文件时，若新文件需要占据5个盘块大小，只需要从头到尾找到空闲盘块，并依次链接，并把首地址存放到文件项中。为了有效管理空闲块，我们可以将所有空闲盘区(每个空闲盘区可以包括若干个空闲盘块)构建到一条空闲链freelst中。freelst每个节点存储本空闲盘区的盘块号、长度和指向下个盘块的指针，创建时把新节点链接到freelst尾部。
如图b所示，共有3个空闲盘区，盘块号依次为4、5、6、10、14、15。
请在划线处填上合适的代码。
def mergefree(allot)：　#mergefree的功能是从头到尾扫描文件分配表，创建空白盘区链
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＋1
else：
i＋＝1
return freeh，freelst
#读取文件分配表信息存储到a11ot中，代码略
head，freelst＝mergefree(allot)
p＝head
while p！＝－1：　#打印出所有空闲盘块号
for i in range(freelst[p][1])：
print(③________，end＝'，')
p＝freelst[p][2]
5.某工厂每天会收到多个订单，有n台机器对零件进行加工。为减少机器的损耗，需要在满足所有订单加工的情况下(订单即到即加工)，机器开启数量尽量少。若开启n台机器不能满足订单即到即加工，则计算所有订单最少的平均等待时间。若给定某天内所有的订单信息，请计算需要开启的机器数量以及订单平均等待时间，代码运行效果图如图所示。
订单信息如下：(批次，到达时间，加工时间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) 机器数量：2 2台机器全部开启，订单平均等待2.5 min 第1台机器： A1：09：00～09：30，A8：09：30～09：50，A4：10：00～11：00，A3：11：00～11：50 第2台机器： A5：9：20～10：00，A7：10：20～11：00，A6：11：00～11：20，A2：11：30～12：20
(注意：若上一个订单结束时间为9：00，下一个订单开启时间最早为9：00)。请回答下列问题：
(1)上图所示的例子中，若机器有10台，则只需要开启________台机器。
(2)定义如下data_sort(a)函数，参数a为列表，列表中每个元素包含三个数据项，依次分别对应订单批次、到达时间、加工时间(时间均转为分钟)。该函数实现将列表a按照订单到达时间升序排序。
def data_sort(a)：
for i in range(len(a))：
　　for j in ：
　　　 　if________：
　　　　　　 　a[j]，a[j＋1]＝a[j＋1]，a[j]
①划线处填入的语句为________，可实现上述功能。
②若将加框处语句写错为range(i，len(a)－1)，则下列4组数据中，若列表a的值为________(单选，填字母)不能测试出问题。
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)实现计算开启机器数量的部分Python程序如下，请在划线处填入合适的代码。
def huan(n)：
pass　#将分钟转换为时间AA：BB格式，返回值为字符串，代码略　#读取文件中的信息，并存储在列表order中，代码略
data_sort(order)
n＝int(input(″机器数量：″))
for i in range(len(order))：
order[i].append(－1)　#order[i]追加一个元素－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
　　　 time＝order[t1][1]＋order[t1][2]
else：
　　　　 t2＝mach[k]
　　　　 if order[t1][1]＋order[t1][2]　　　　　　 k＝j
　　　　　　 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(″只需开启″＋str(num)＋″台机器″)
else：
print(str(n)＋″台机器全部开启，订单平均等待″＋str(round(wait/len(order)，2))＋″min″)
for i in range(num)：
print('第'＋str(i＋1)＋'台机器：')
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.程序运行时，以内存单元为基本单位对内存进行分配，若干个连续的内存单元称为一个内存块，每个内存块的信息包含首地址和大小。编写Python程序模拟内存分配和释放的过程。
1)初始化空闲内存块，将信息存储在链表flink中。
2)分配大小为size的内存。先依次查找链表flink中是否存在不小于size的内存块。若存在且等于size，则将其从链表flink中删除；若存在且大于size，则修改该内存块的信息；若不存在，则对不连续的空闲内存块按顺序进行分配，如果空闲内存块之和仍小于size，则分配失败。
3)释放内存。将释放的内存块信息插入链表flink，链表flink各节点按首地址从小到大排列。如果释放的内存块与链表中的某个内存块相邻，则将它们合并成一个更大的内存块。
请回答下列问题：
(1)初始空闲内存块大小为16，进行两次分配和一次释放的过程如图所示。若继续分配大小为8的内存块，________(填写：能/不能)成功。
①初始化空闲内存块，大小为16
②第1次分配，大小为4，分配后空闲12
③第2次分配，大小为8，分配后空闲4
④释放第1次分配的内存，释放后空闲8(不连续)
(2)定义如下allocate(flink，head，size)函数，参数flink是空闲内存块链表，head是flink头指针，size为所需内存块大小。函数功能为分配size大小的空闲内存块，并返回分配的内存块信息及头指针head。请在划线处填入合适的代码。
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：
#对不连续的空闲内存块按顺序进行分配，如果空闲内存块之和仍小于size，则分配失败，代码省略
return block，head
(3)实现模拟过程及内存释放的部分Python程序如下，请在划线处填入合适的代码。
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]]　#初始化空闲内存块链表，0：起始地址，16：长度
head＝0
block1，head＝allocate(flink，head，4)
block2，head＝allocate(flink，head，8)
block1，head＝release(flink，head，block1)
综合题　基于数据结构的算法
1.某工厂生产的产品包含n个(编号为0～n－1)组件，其组装可由多名工人共同协助完成。组装时每个组件都不可遗漏并能按序完成，有些组件存在前置组件(以下简称“前置”)，即安装有先后顺序。例如，某产品有6个组件，如图a所示，组件3的前置是组件1和组件2，即安装组件3需要在组件1和组件2完成之后。若0～5号组件的组装所需单位时间分别为2，5，2，4，3，5，则在工人数量不限的情况下，所有组件安装完成最短需要14个单位时间。
图a
为了梳理产品组件的组装顺序，并计算所有组件安装完成所需的最短时间，编写程序模拟组装过程：先同时组装前置总数为0的组件，完成后更新每个组件的前置总数，再重复以上步骤，直至所有组件安装完毕，程序运行结果如图b所示，请回答下列问题：
编号为0～5的组件组装所需单位时间分别为：[2，5，2，4，3，5] 组件组装顺序：[0，1，4，2，3，5]，安装完成所需最短时间：14
图b
(1)图a所示产品的1号组件组装时长若缩短为3个单位时间，其它时间保持不变，则所有组件安装完成所需最短时间为________个单位时间。
(2)定义如下cal(a，n)函数，参数a列表的每个元素包含两项，a[i][1]是组件编号，a[i][0]是a[i][1]的前置编号，例如a中某个元素值为[2, 3]，表示组件2是组件3的前置。该函数的返回值是列表s和列表pre，其中s记录所有组件的相互关系，pre[i]记录初始情况下组件i的前置总数。
def cal(a, n)：
pre＝[0]*n
s＝[[0 for i in range(n)] for j in range(n)]　#创建n×n的二维数组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)函数，该函数的返回值是列表v, v[i]代表从开始到组件i完成组装所需的最短时间。请在划线处填入合适的代码。
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
″″″
组装编号0～n－1的单个组件所需时间存入t列表，组件前置关系存入a列表，如图a所需时间t＝[2，5，2，4，3，5]；a＝[[0，2]，[2，3]，[1，3]，[3，5]，[3，4] ，[4，5]]
″″″
n＝len(t)
print(″编号为0～″＋str(n－1)＋″的组件组装所需单位时间分别为： ″， t)
v＝t[：]
pre，s＝cal(a, n)
v＝proc(n, s, pre)
data＝[0]*n
result＝[i for i in range(n)]　#创建列表result＝[0，1，2，……，n－1]
for i in range(n)：
data[i]＝v[i]－t[i]　#data[i]表示组件i开始安装时间
for i in range(n－1)：　#按组件开始安装时间升序排序，开始安装时间相同时按组件序号升序
for j in range(n－1－i):
if data[result[j]]>data[result[j＋1]]：
　　　　②________
print(″组件组装顺序：″，result，″，安装完成所需最短时间：″， max(v))
(4)以下选项与题(3)加框处代码功能相同的是__________(多选，填字母)。(注：全部选对的得2分，选对但不全的得1分，不选或有选错的得0分)
A.head！＝tail B.headC.tail<＝n D.len(que)> 0
2.某工厂的业务较多，每个业务i都有对应的截止时间t_i以及收益v_i，工厂每天最多能完成k个业务，且每个业务所需的加工时长相同。由于业务量多，有时候无法完成所有的业务，因此工厂管理者需要对一段时间内的业务进行规划安排，以实现工厂累计收益的最大化。
例如工厂3天内的业务明细如图a所示，已知工厂每天能够完成的业务量k为2。为了实现3天的累计收益最大化，工厂安排的业务方案如图b所示，这样工厂能够获得最大累计收益为105。编写程序，实现在任意时间段内，根据每个业务的截止时间和收益，统计工厂在该时间段内的最大累计收益。
请回答下列问题：
(1)如图a所示，若加工厂每天能够完成的业务量k为3，则工厂在3天内获得的最大收益为________。
(2)定义如下insert(lst，head，pos)函数，参数lst是一个由列表模拟的链表结构数据，其每个节点由收益数据和指向下一个位置的指针组成；参数head是其中一条链表的头指针，由该指针构建的链表已经按收益数据升序排列，参数pos是某个节点的指针。函数功能是将pos节点插入到head指针指向的链表中，并保持链表按收益数据升序排列，最后返回头指针数据。
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
①若函数加框处代码误写为“lst[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
②请在划线处填入合适的代码。
(3)实现对每个业务完成时间的合理安排，使得工厂获得最大累计收益的部分 Python 程序如下，请在划线处填入合适的代码。
def pushlst(info，lst，cur，v)：　#cur 代表开始的时间
if info[cur][1]lst.append([v，－1])　#列表 lst 追加一个元素
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，尝试将当前业务提至前一天完成，代码略
else：
　　　 　tmpv＝lst[pos][0]　#获取原安排中收益最少的业务收益
　　　　 lst[pos][0]＝v
　　　　p＝lst[pos][1]
　　　　info[cur][0]＝insert(lst，②________，pos)
　　 　　#如果 cur>0，尝试将原安排中收益最少的业务提至前一天完成，代码略
'''
先输入规划安排的天数 n 和每天能够处理的最大业务量 k，代码略。
依次输入 m 个业务的截止时间 t(t≤n)和收益 v，存储在数组 tran 中，如：[[1，25]，[1，10]，[2，15]]，表示共有 3 个业务，第一个业务的截止时间为 1，收益为 25……，代码略
'''
info＝[]; lst＝[]; j＝0
for i in range(n)：
info.append([－1，0])　#列表 info 追加一个元素
while kcur＝tran[k][0]; v＝tran[k][1]　#获取截止时间和对应收益
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.在某图形操作系统中有N个窗口，每个窗口都是一个两边与坐标轴分别平行的矩形区域。窗口边界上的点也属于该窗口。窗口之间有层次的区别，在多于一个窗口重叠的区域里，只会显示位于顶层的窗口里的内容。
当你点击屏幕上一个点的时候，你就选择了处于被点击位置的最顶层窗口，并且这个窗口就会被移到所有窗口的最顶层，而剩余的窗口的层次顺序不变。如果你点击的位置不属于任何窗口，则系统会忽略你这次点击。
如图a所示的三个窗口，自顶向下的窗口编号为3、2、1，窗口用一对顶点坐标(x1, y1)和(x2, y2)表示。若此时鼠标点击(1，1)位置，则自顶向下的窗口编号为2、3、1，当前选中的为窗口2。
编写程序，根据已有的窗口信息(已按自底往上的层级输入窗口信息)，模拟每次点击鼠标操作，输出当前选中的窗口编号，若鼠标点击位置不属于任何窗口，则显示“ignore”。
(1)根据题意，某次程序运行过程如图b所示，第2次鼠标点击后，当前选中的窗口号为________。
(2)定义如下check(t)函数，参数t列表存储两个顶点(x1，y1), (x2，y2)的坐标值。函数功能是对能构成矩形区域窗口的坐标，返回该矩形区域左下角和右上角的坐标值。
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]，则函数返回的结果为________。
(3)实现上述功能的Python程序下，请在划线处填入合适的代码。
def inside(x, y，w)：
x1, y1, x2, y2＝w[0]，w[1]，w[2]，w[3]
if x1<＝x<＝x2 and y1<＝y<＝y2：
return True
else：
return False
#读取窗口数和鼠标点击次数保存在变量n，m中，代码略
w＝[]；head＝－1
for i in range(n)：
t＝[int(s) for s in input().split()]　#读取坐标数据，保存在列表t中
if len(check(t))！＝0：
w.append([i＋1, t, head])　#i＋1是窗口编号，从1开始
①________
for i in range(m)：
x, y＝[int(s) for s in input().split()]　#读取鼠标点击数据，保存在x, y中
p＝q＝head
while ②__________：
p＝q
q＝w[q][2]
if q＝＝－1：
print(″ignore″)
else：
print(″当前选中的窗口号为：″，w[q][0])
③________
if q！＝head：
　　　 　w[q][2]＝head
head＝q
专题19　基于数据结构的算法实现
知识点
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]
解析　本题考查链表的构建和遍历。(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.(1)k＝posi　(2)s＋＝int(line[i])　(3)①maxnum解析　(1)查找数组中的最大值的位置，利用位置关系串成一个降序链表，最后遍历链表输出。k是当前元素的位置，posi是下一个元素的位置，找到的数应该在节点posi后面。(2)readdata函数功能是读取“scores.txt”文件，生成一个二维列表。变量s累计的总分。(3)findmax函数找到最大数所在位置，同时将该位置设置为False。(4)遍历链表，输出节点相关数据域的内容。
3.(1)C　(2)①dlist[head][1]　②0　③dlist[pre][1]＝dlist[cur][1]　④left＝＝1
解析　(1)A组各轮次结果分别为TFF，B组为FF，C组为TFT，D组为FTF，因此获胜的为C组。(2)①链表dlist数据区域值为组的名称，指针为下一组的索引，已经输出头节点的信息，因此当前节点cur的初值为头节点的下一节点。②每一轮按A→B→C→D→A顺序轮流作答，将要构建一个循环链表，尾节点将指向第1个节点。③在链表中删除当前节点cur，将前驱指向当前节点的后继。④最后剩下一组，该组获胜。
4.(1)9→4→3→7　(2)①2　②AD　(3)①j解析　本题考查链表节点插入和连续子串问题的处理。(1)文件abc起始地址9，分配表allot[p]表示地址p的下一个文件的地址，直到allot[p]＝－1为止。(2)题①读取已记录的文件，将当前文件合并到已记录的文件中，lst[j][0]＝i重置文件起点，lst[j][1]＝lst[j][1]＋fsize修改文件大小。文件连接关系：文件1：0→3→9、文件2：1→7→8、文件3：2→13→11→1、文件4：12→0。文件4与文件1合并，文件3与文件2合并，修改大小的语句执行2次。②删除语句后，对已记录文件会重复访问，因此会增加while循环的次数。循环结束后文件必定以－1结束，合并文件部分代码将不会执行，无法完成重置文件起点的操作，所以结果中的文件起点可能不正确。(3)记录连续的空白区域，实际上就是连续重复子序列问题。①空查找连续的重复数据，注意j的边界；②空将当前新增空白区域的节点插入到链表freelist末尾，其中cur标记了链表的尾结点，代码freelst[cur][2]＝len(freelst)－1将尾节点的后继更新为当前新增节点，同时移动尾节点标记cur为当前新增节点。③空输出连续的空白盘符，freelst[p][1]是p指针所指向节点的连续盘符的长度，freelst[p][0]是其起始地址，所以从freelst[p][0]开始的freelst[p][0]＋i就是连续盘符的。
5.(1)3　(2)①a[j][1]>a[j＋1][1]　②A (3)①range(num)　②time>order[i][1]
③order[p][3]
解析　(1)根据题图所示，只有订单A3有等待时间。若机器数量增加，只需要增加一台机器即可满足所有订单。(2)①函数data_sort(a)实现对a按照到达时间升序排序，则判断条件为a[j][1]>a[j＋1][1]。②若将加框处的语句写错为range(i，len(a)－1)，则a[0]处只会被比较一次，若最小值不在a[0]或a[1]，则无法检测此处错误，故选择A。(3)根据输出的结果可知mach[i]存储了每个机器最后一个加工的订单索引，变量p为该机器依次加工的订单索引。变量wait记录了所有订单的等待时间，根据语句order[i][3]＝mach[k]和mach[k]＝i可知，通过order[i][3]来记录第k台机器的加工索引，故③处填写p＝order[p][3]。根据程序可知变量time记录了最早空闲时间的机器，根据语句mach[num]＝i和num＋＝1可知num为开启机器的数量，此处新开启一台机器。变量j为mach数组依次遍历的索引，而①处填写mach数组的索引为range(num)。开启一台机器的条件为当前数量少于n台且最早空闲机器的时间要大于当前订单到达的时间，故②处填写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的内存块，要求分配大小为8的内存块，能满足要求。(2)①更改当前节点中指针遍历链表。cur从头节点开始，依次遍历各个节点，当前节点中指针区域存储的是下一节点的位置。②条件flink[cur][0]＝＝size成立，说明空闲块的大小和要求的size相等，要将当前空闲内存块从链表删除。(3)①在头部插入新节点。内存块释放，要在flink中增加相应的节点，插入节点分为在头部和其他节点之前插入节点两种情况。若待释放内存块的起始地址小于头节点，当cur＝＝head时，则更新头指针为len(flink)－1。注意：pre＝＝head答案是错的。②将两个相邻空闲块位置合并为一个，则当前pre和cur节点可以合并，将cur节点吸收掉，同时需修改存储容量flink[pre][1]。同时pre节点指向cur的下一节点，并且更新pre节点的空闲内存块大小。
综合题
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)有三个组件链，分别为0→2→3→5，1→3→5，4→5，在组件3前面两个并行的任务链，1号组件组装时长若缩短为3个单位时间，其时间分为2＋2，3，较长时间为4，组件3的时间为4，合计为8，而组件4所需时间为3，因此总共所需时间为8＋5＝13。(2)函数cal统计各个组件的前置总数，组件y的前置是组件x，因此组件y的前置总数pre[y]等于自身加1。(3)①函数proc功能是计算每个组件i从开始到组件i完成组装所需的最短时间v[i]。先将前置组件数为0的索引入队，因此队列元素依次为0，1，4。队首为组件0，其后置组件2所需时间为前置组件0与他本身时间之和，v[2]＝2＋2＝4。执行语句pre[i]－＝1，i入队，接着组件1出队计算其后置组件3，即v[3]的时间为3＋4＝7；接着4出队，v[5] 时间为3＋5＝8。接着2出队，v[x]值为4，组件3即v[3]的时间为4＋4＝8，在两个前置中找一个较大值作为最短时间。遍历各个组件，条件s[x][i]＝＝1表示组件x是组件i的前置，完成组件x所需时间为v[x]，那么完成组件i总共所需时间为v[x]＋t[i]。完成组件i可能有多个前置，完成组件x之前的最长时间为v[i]，在两个时间中取出一个较大值。②data[i]表示组件i开始安装时间，result存储的是从小到大排列的组件序号，当条件data[result[j]]>data[result[j＋1]]成立就交换两个索引位置。若data[result[j]]和data[result[j＋1]]相等，本身也是按序号排列的，因此无需交换。(4)加框处代码为队列不为空的意思，而队列的长度就是n，因此AB选项符合题意。
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)将每天的收益进行降序排列，第1天的收益分别为25，15，10，第2天收益分别为30，25，20，15，第3天收益5。将第2天的15提前一天完成，代替第1天的10。(2)①修改后，若链表为空，则链表节点不存在，B选项插入的值为5，而链表节点的值依次为2，3，4，因此会出现问题。②将节点p的前驱节点q指向新插入的节点。(3)①从语句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)坐标(2，2)在第2个窗口。(2)略。(3)①改变头指针，语句w.append([i＋1, t, head])将创建一个新节点，该节点指向原头节点，因此属于头插法，将改变头指针。②在链表节点中查找所在窗口，当链表不空时，如果不是则继续查找。③将找到节点q移动到头节点的前面，成为新的头节点。在链表中删除节点q，即将其前驱节点p指向q的后继。

展开更多......

收起↑