浙教版(2019)信息技术选考二轮复习之链表算法综合
|
2份
|
5页
|
666人阅读
|
179人下载
内容正文:
链表+算法综合六
班级 姓名
1.【23.05临海新昌联考】程序运行时,以内存单元为基本单位对内存进行分配,若干个连续的内存单元称为一个内存块,每个内存块的信息包含首地址和大小。编写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=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