操作系统在管理磁盘时，会将磁盘分为一个个“盘块”。在为文件分配空间时，可以将文件装到离散的盘块中。读取一个文件时，首先在目录结构中找到文件项。从文件项中可以获取文件名、存储时间、该文件在存储块中的起始地址等基本信息，但不包含文件具体内容，然后在磁盘文件分配表中找到对应的文件。磁盘文件分配表如图 1 所示。文件结束块用-1 表示，空闲盘块用 0xff 表示。

0 返回首页

1. 操作系统在管理磁盘时，会将磁盘分为一个个“盘块”。在为文件分配空间时，可以将文件装到离散的盘块中。读取一个文件时，首先在目录结构中找到文件项。从文件项中可以获取文件名、存储时间、该文件在存储块中的起始地址等基本信息，但不包含文件具体内容，然后在磁盘文件分配表中找到对应的文件。磁盘文件分配表如图 1 所示。

文件结束块用-1 表示，空闲盘块用 0xff 表示。

(1) 根据文件的起始地址，能方便地找到文件的其它盘块。如图 1中，文件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+=l

p=allot[p]

if p==-1:

lst.append([i,fsize])

else:

for j in range(len(Ist)):

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!=-1，对程序的影响是（多选，填字母）。

A.会增加 while 的循环体执行次数

B.返回的 lst 中的节点数量保持不变

C.while 循环不能正常结束

D.返回的 lst 中，文件的起始地址部分不正确

(3) 在创建文件时，若新文件需要占据 5 个盘块大小，只需要从头到尾找到空闲盘块，并依次链接，并把首地址存放到文件项中。为了有效管理空闲块，我们可以将所有空闲盘区（每个空闲盘区可以包括若干个空闲盘块）构建到一条空闲链 freelst 中。freelst 每个节点存储本空闲盘区的盘块号、长度和指向下个盘块的指针，创建时把新节点链接到 freelst 尾部。

如图 2所示，共有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+l

else:

i+=l

return freeh,freelst

#读取文件分配表信息存储到 a11ot 中，代码略

head,freelst=mergefree(allot)

p=head

whi1e p!=-1: #打印出所有空闲盘块号

for i in range(freelst[p][1]):

print(,end=',')

p=freelst[p][2]

【考点】

过程与自定义函数; 分支结构语句及程序实现; 循环结构语句及程序实现;

【答案】

您现在未登录，无法查看试题答案与解析。登录

综合题困难

1. 某咖啡店，店里共有4种咖啡，类型编号为0到3，每次只能制作一种类型的咖啡，咖啡都是批量现做(制作过程中不能更改数量或类型)。店员需按照订单的先后顺序完成订单(即当前订单完成之前不能换订单)，已经接到的订单中的同一类型咖啡可以一起制作(假设咖啡机能同时制作的数量上限足够高)，且不需要额外增加时间(即只需制作一杯的时间)。如图1为每个订单的咖啡数量，初始“订单0”中[6, 0, 2, 4]表示0到3号咖啡的购买数量。此时店员先做数量最多的6份0号咖啡，1分钟后接到新订单[1, 18, 0, 2]，之后每分钟都会接到1个新订单，这些订单都计入每种咖啡的待做数量。3分钟后这6份0号咖啡制作完成，程序会在“订单0”中选择还没制作的且待做数量最多的(数量相同时先后不作要求)咖啡作为下一次要制作的咖啡。编写python程序，每次制作完一种咖啡，输出接下来要制作的咖啡，运行界面如图2：

图 1

图 2

(1) 由图1的订单信息，3 分钟后" 咖啡 0"制作完成，那么图2 中(1)处店员接下来要做的咖啡是咖啡。

(2) 根据待制作的咖啡数量，对链表初始化，生成降序链表 lnk，则代码运行后 y的值为。

def sort():

for i in range(3):

for j in range(3,i,- 1):

if waitlist[index[j]][1] > waitlist[index[j - 1]][1]:

index[j], index[j - 1] = index[j - 1], index[j]

if waitlist[index[j]][1]==0:

return j

return 4

waitlist=[[3,6],[4,0],[1,2],[2,4]] # "咖啡 0" 的批量制作时间为 3 分钟，目前待做量为 6，以此类推

q=[[6, 0, 2, 4], [1, 18, 0, 2], [2, 1, 2, 1], [0, 1, 0, 5],…… #如图 1，代码略

#q 保存订单流，第一个订单[6,0,2,4]作为初始订单已计入 waitlist

index=[0,1,2,3]

y=sort()

lnk=[- 1]*4

for i in range(y- 1): #创建降序链表

lnk[index[i]]=index[i+1]

p=lnk_h=index[0]

print("请制作咖啡"+str(p))

waitlist[p][1]=0 #咖啡 p 进入制作，待做数量回 0

(3) 请在划线处填入合适的代码。

defenqueue(order): #order 是一个订单，例如[1,2,0,3]

global lnk_h

flag.append([0,0,0,0]) #新订单 4 种咖啡未完成

for i in range(4): f = True

if waitlist[i][1]==0: f=False

if order[i]==0: continue

waitlist[i][1]+=order[i] #将订单 order 中的咖啡 i 累加到待制作数量中

cur=lnk_h

while cur!=- 1 and waitlist[i][1]<waitlist[cur][1]:

pr,cur=cur,lnk[cur]

if cur!=i:

tmp = lnk[i]

lnk[i]=cur

if cur==lnk_h:

lnk_h=i

else:

lnk[pr]=i

if f:

while cur!=i:

pr,cur=cur, lnk[cur]

def nextfood(qhead,qtail): #找到下一次要做的咖啡

global lnk_h

cur=lnk_h

while :

pr,cur=cur,lnk[cur]

if cur==lnk_h:

lnk_h=lnk[lnk_h]

elif cur==- 1:

return – 1

else:

lnk[pr]=lnk[cur]

waitlist[cur][1]=0

for i in range( ):

if q[i][cur]!=0: flag[i][cur] = 1

return cur

qhead,qtail=0,1

order=q[qhead]

flag=[[1,0,0,0]] #flag[i][j]=1 标记"订单 i" 中的"咖啡j" 已经在做或已经做完。 lnk_h, time =lnk[lnk_h],0

while True:

time=(time+1)%waitlist[p][0]

if qtail<len(q):

enqueue(q[qtail]) #接新订单

qtail+=1

if time==0:

while qhead<qtail- 1 and sum(flag[qhead])+q[qhead].count(0)==4: #订单完成时

qhead+=1

order=q[qhead]

p=nextfood(qhead,qtail)

if p == - 1 : break

print("请制作咖啡"+str(p))

综合题困难

2. 某酒店共有A、B、C三种房间型号，A、B、C型房间的住宿团队价分别为500元/晚、300元/晚、200元/晚。因房型和房间数量原因，酒店规定A型房间只能订1-9个，而B型和C型房间都必须订10-99个。每两个团队的订房信息共同组成一个订单码，该订单码以第一个团队编号“g1”和字符“-”开头，后面由房间型号及其数量组成，两个团队的信息编号以逗号分隔。例如，订单码“g1-A2B15C27,g2-A6B11C22”，表示团队g1所订A、B、C型房间的数量分别为2个、15个、27个，团队g2所订A、B、C型房间的数量分别为6个、11个、22个。请回答下列问题：

(1) 若某订单码为“g1-A2B11C17,g2-A8B19C23”，则该订单一天住宿的总金额为元。

(2) 实现上述功能的部分 Python 程序如下，请在划线处填入合适的代码。

def fi(s,b,e):

income=0

i=b

while i<=e:

if s[i]=="A":

income+=

i+=2

elif s[i]=="B":

income+=int(s[i+1:i+3])*300

i+=3

elif s[i]=="C":

income+=int(s[i+1:i+3])*200

i+=3

return income

s=input("请输入订单码：")

flag=False

for i in range(len(s)):

if s[i]=="-" and not flag:

flag=True

elif s[i]=="-":

q=i

elif s[i]==",":

e=i

total=fi(s,p+1,e- 1)

total+=fi(s, ,len(s)- 1)

print(total)

综合题困难

3. 地图染色问题可以根据四色定理来解决。所谓四色定理，就是指可以用不多于四种的颜色对地图着色，使相邻的行政区域不重色，因此我们可以用四色定理的结论，用回溯算法对一幅给定的地图染色。

算法的基本思想是：从第(1)号行政区域开始染色，每个区域逐次用颜色 1#、2#、3#、4#进行试探，若当前所取的颜色与周围已染色的行政区域不重色，则用栈记下该区域的颜色序号，否则依次用下一颜色进行试探；若出现用 1#到 4#颜色均与相邻区域的颜色重色，则需退栈回溯，修改当前栈顶的颜色序号，再进行试探。直到所有行政区域都已分配合适的颜色。某县行政地图如图所示：

(1) 若邻接矩阵 adjamat=[[0,1,1,1,1],[1,0,1,1,0],[1,1,0,1,1],[1,1,1,0,1],[1,0,1,1,0]]，则下列涂色方案中可行的是（）(单选，填字母) A. 1->1,2->2,3->3,4->4,5->2 B. 1->1,2->2,3->3,4->1,5->2 C. 1->1,2->2,3->3,4->2,5->4

(2) 实现上述功能的Python程序如下，请在划线处填入合适的代码。

def mapcolor(adjamat): #自定义填色函数部分

signcolor=[0]*N

color = 1

signcolor[0] = 1

area = 1

while area < N:

while color <= 4:

if area >= N:

break

k = 0

# 以下代码判断区域是否重色

while (k < area) and (signcolor[k] * adjamat[area][k] != color):

k += 1

if (k < area):

color += 1

else:

#给该区域上色

area += 1

color = 1

if color > 4: # 没有找到合适的颜色，需要进行回溯

color = signcolor[area] + 1

return signcolor

#主程序部分

city = {1: '海游街道', 2: '海润街道', 3: '沙柳街道', 4: '亭旁镇', 5: '珠岙镇', 6: '横渡镇', 7: '蛇蟠乡', 8: '健跳镇', 9: '花桥镇', 10: '浦坝港镇'}

N =

colordict = {1: '红色', 2: '橙色', 3: '黄色', 4: '青色'}

adjamat = [[0 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 0]

[1 , 0 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 0]

[1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0]

[1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0]

[1 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0]

[0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 1]

[0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0]

[0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0]

[0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1]

[0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 0]]

signcolor1 = mapcolor(adjamat)

print(signcolor1)

# zip 函数可以将多个序列，如列表、元组、字典、集合压缩成一个对象。

for key1,key2 in zip(city,signcolor1): #将相对应的区域与地图颜色输出

print(city[key1] + ":" + colordict[key2])

综合题困难