操作系统在管理磁盘时，会将磁盘分为一个个“盘块”。在为文件分配空间时，可以将文件装到离散的盘块中。读取一个文件时，首先在目录结构中找到文件项。从文件项中可以获取文件名、存储时间、该文件在存储块中的起始地址等基本信息，但不包含文件具体内容，然后在磁盘文件分配表中找到对应的文件。磁盘文件分配表如图a所示。文件结束块用-1表示，空闲盘块用0xff表示。
图a
（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:
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
return lst
若 allot 为[3,7,13,9,0xff,0xff,0xff,8,-1,-1,0xff,1,0,11,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
如图b所示，共有3个空闲盘区，盘块号依次为4、5、6、10、14、15，请在划线处填上合适的代码。
def mergefree(allot):#mergefree 的功能是从头到尾扫描文件分配表，创建空白盘区链
freeh=-1;freelst=[]
n=len(allot)
i=0
while i<n:
if 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
#读取文件分配表信息存储到allot中，代码略
allot=[3,7,13,9,0xff,0xff,0xff,8,-1,-1,0xff,1,0,11,0xff,0xff]
head,freelst=mergefree(allot)
p=head
while p!=-1:#打印出所有空闲盘块号
for i in range(freelst[p][1]):
print(③____,end=',')
p=freelst[p][2]
搜索
