链表+算法综合六
班级 姓名
1.【23.05临海新昌联考】程序运行时，以内存单元为根本单位对内存进行安排，假设干个连续的内存单元称为一个内存块，每个内存块的信息包含首地址和大小。编写Python程序模拟内存安排和释放的过程。
1)初始化空闲内存块，将信息存储在链表flink中。
2)安排大小为size的内存。先依次查链表flink 中是否存在不小于size的内存块。假设存在且等于size,那么将其从链表flink中删除；假设存在且大于size，那么修改该内存块的信息；假设不存在，那么对不连续的空闲内存块按挨次进行安排，假如空闲内存块之和仍小于size,那么安排失败。
它的作用是什么3)释放内存。将释放的内存块信息插入链表flink，链表flink各节点按首地址从小到大排列。假如释放的内存块与链表中的某个内存块相邻，那么将它们合并成一个更大的内存块。
mysql有安装包怎么安装
请答复以下问题：
(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=head
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=head
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安卓11专用框架
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)
2.【23.05义乌统测】汽车整车安装流水线有n个工序(编号为0到n1),每个工序可以有假设干个前置工序，但最多只有一个未完成的后续工序。对于每个工序，只有完成其全部的前置工序，才能开头作业，完成每个工序需要费用。编写程序模拟该安装过程，输入每个工序的编号、后续工序及费用，计算编号为m的工序需要的费用。
请答复以下问题:
如以下图所示，完成工序5有两个前置工序(2和4)，需要先完成两个流程:工序0→工序1→工序2，以及工序3→工序4，才能开头工序5的作业。总费用为(1+2+8)+(4+2)+3=20。完成工序7总费用是 。
(2)定义sort(info)函数，将输入的工序信息info排序。
def sort(info):
m=len(info)
for i in range(1,m):
for j in rang(0,mi):
if info[j][0]>info[j+1][0]:
info[j],info[j+1]=info[j+1],info[j]
假设输入的info=[[1,2,1],[0,1,3],[2,3,4],[3,1,2]]，运行sort(info)后，info中的数据为
python教材下载(单项选择，填字母)。
A.[[3,1,2],[2,3,4],[1,2,1],[0,1,3]] B.[[0,1,3],[1,2,1],[2,3,4],[3,1,2]]
C.[[3,1,2],[0,1,3],[1,2,1],[2,3,4]] D.[[2,3,4],[1,2,1],[0,1,3],[3,1,2]]
(3)实现输入工序m，计算完成工序m所需费用的局部python程序如下，请在划线处填入适宜的代码。
def crt_Ink(): #创立工序链表，维护相关信息
for job in info:
①
lnk.append([job[0],job[1]])
for i in range(n):
if pre[i]==0:
cur=i
while cur!=1:
src[cur].append(i)
②
def cal_ans(obj): #计算完成工序obj的费用
flag=[0]*n
res=info[obj][2]
for i in src[obj]:
p=i
while p!=obj:
if flag[p]==0:
③
flag[p]=1
p=lnk[p][1]
return res
#读取数据到列表info，每个元素依次为工序编号、后续工序及该工序的费用，代码略
n=len(info)
pre=[0]*n #pre列表用于存储每个工序的前置工序的数量
lnk=[]
src=[[]for i in range(n)]
sort(info)
m=int(input())
crt_Ink()
print(cal_ans(m))
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论