学进去

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

过年期间，已经完成了所有作业的小吴同学和朋友们玩起了卡牌魔术：有13张扑克牌(A 2 3 4 5 6 7 8 9 10 J Q K)，预先排好，牌面朝下，从最上面开始，将第一张牌翻过来看正好是A；继续数手里的余牌，第二次数1，2将第一张牌放到这叠牌的下面，将第二张翻开，正好是黑桃2，也把它放在桌上；第三次数1，2，3，前面两张牌放到这叠牌的下面，取出第三张，正好是黑桃3，这样依次将13张牌翻出，正好是(A 2 3 4 5 6 7 8 9 10 J Q K)，求:牌的原始顺序应该怎样排呢？为解决这个问题，小吴编写了一个VB程序运行如下：

为实现上述功能，请在划线处填入合适的代码：
Private Sub Command1_Click()
Dim i As Integer, j As Integer, k As Integer
Dim t As Integer, temp As Integer
Dim a(1 To 13) As Integer
Dim jg As String
Const kp = "JQK"
a(13) = 1
For i = 12 To 1 Step -1
       ______
       For j = i + 1 To 13
             a(j) = a(j) + 1
       Next j
       For j = 1 To i - 1
             ________
             For k = 13 To i + 1 Step -1
                    t = k + 1
                    If t > 13 Then t = i
                         a(t) = a(k)
             Next k
             _________
       Next j
Next i
List1.AddItem "牌堆的原始顺序为:"
For i = 1 To 13
       If a(i) = 1 Then
             jg = "A"
       ElseIf a(i) > 10 Then
             jg = ________
       Else
             jg = CStr(a(i))
       End If
       List1.AddItem jg
Next i
End Sub

小娜想在高三暑假完成一次毕业旅行。她了解到旅行社对10个热门旅游城市进行了编号，每个城市有相应的名胜值，到达某个城市即可获得该城市的名胜值。旅行社还提供各城市之间的航线信息，她发现航线都是从编号小的城市到编号大的城市。已知小娜旅行会从1号城市出发，终点站（家）在11号城市，她想自己设计一条名胜值最大的游路线，为此小娜设计了一个算法来制定路线。设计思路是：
1）依次计算每个城市的路线名胜值。设到达某城市的n条路径的中，每条路径上的城市名胜值之和分别为{x₁，x₂…x_n}，该集合中的最大值xmax即为该城市的路线名胜值。路线名胜值的具体算法：该城市的名胜值加上能直接到达该城市的所有城市中最大的路线名胜值，同时记录下该前一城市的编号。
如图a所示，1、2、3、4、5、6号城市名胜值依次为5、6、5、4、9、8。
1号城市可到达2、3、4号城市，2、3号城市均可到达6号城市，则2号城市的路线名胜值为自身名胜值6加上1号城市的名胜值5，等于11；同理，3号城市的路线名胜值为5+5=10。6号城市路线名胜值为自身名胜值8加上2号城市的路线名胜值11，等于19，途经城市为1、2、6，而非途径1、3、6号城市。
2）依次遍历所有城市的路线名胜值，在能到达11号城市的城市中，存储最大路线名胜值的城市编号。若最大路线名胜值有并列，则这些城市编号全部存储。
3）输出最大路线名胜值对应的最佳旅游路线，若有多条，则全部输出。

图a

图b

程序界面如图a所示。在Text l中输入航线信息，如“3→6”，表示可以从3号城市到6号城市。
（1）若1~10号城市的名胜值分别为5，6，5，7，4，3，7，5，6，8，航线如图a所示，则最佳旅游路线为：1、________、11号城市（填城市编号）。
（2）实现上述功能的VB程序如下，请在划线处填入合适的代码。
Const n=10
Dim map（1 To n * n）As Boolean
Dim isBack（1 To n）As Boolean                    '表示1~n号城市是否有航线可以回到11号城市（家）。其值为True则表示可回家
Dim cityPoint（1 To n）As Integer
Dim pathPoints（1 To n）As Integer                  '到达1～n号城市时的路线名胜值
Dim maxPoints As Integer                                 '最终路线方案的最大名胜值
Private Sub Form_Load()

'初始化各城市名胜值，并在List l中输出，代码略。

'从Text 1中读取航线信息，存储到map数组，isBack数组，代码略。

'map（1）-map（10）分别表示1号城市到1~10号城市的航线情况。

'map（11）~map（20）分别表示2号城市到1~10号城市的航线情况，以此类推。

'16题图a中的航线信息在map数组中的表示如第16题图b所示。T表示值为True，空表示值为False。

'可知map（2）、map（3）、map（4）、map（15）……等元素的值为True

End Sub

Private Sub Command1_Click()

Dim endCity（1To n）As Integer

Dim prev（1 To n）As Integer

Dim tour As String

Dim cnt As Integer

For i=2 To n   '计算每个城市的路线名胜值

For j=1Toi-1

tmp=_____

If map（tmp）And pathPoints（i）<pathPoints（j）+cityPoint（i）Then

pathPoints（i）=pathPoints（j）+cityPoint（i）

prev（i）=j

End If

Next j

Next i

cnt=1：maxPoints=0       '找出符合条件的路线

For i=1To n

If isBack（i）And pathPoints（i）>maxPoints Then

maxPoints=pathPoints（i）

cnt=1

Elself isBack（i）And pathPoints（i）=maxPoints Then

cnt=cnt+1

End If

_________

Next i

ct=0：flag=False   '输出路线

maxPoints=maxPoints +cityPoint（1）

For i=1 To cnt

city=endCity（i）

tour=""

Do While city<>0

tour=Str（city）+"→"+tour

ct=city

________

Loop

tour="路线"+CStr（i）+"："+tour+"11，路线名胜值："+CStr（maxPoints）

If ct=1Then List2.Addltem tour:flag=True

Next i

If Not flag Then List2.Addltem"无符合要求的线路”

End Sub

计算机运行多个任务（又称进程）时，需要进行调度。有的进程需要优先响应，例如用户的交互操作，此时就需要暂停当前运行的进程，让CPU先执行需要优先响应的进程，这称为抢占。操作系统需要设计调度算法，来决定CPU运行进程的顺序。
优先级抢占式调度算法是一种简单的调度算法，规则如下：
1）将进程分为m个优先级，设置m个等待队列，分别对应每一级优先级。
2）每个进程具有三个要素：到达时间，运行所需时长，优先级数（数越大优先级越高）
3）相同优先级的进程，按照先到先服务的原则依次执行。
4）同一时刻中，先将到达的进程都加入队列，再按照优先级进行分配
5）只有当k级队列为空的时候，才会为k-1级队列队首的进程分配时间。
6）进程P_i运行时，如果有优先级更高的进程P_j到达，则立即发生抢占，先执行P_j，并将进程P_i剩余未执行完的部分，重新加入P_i优先级对应的队列末尾，等待继续执行。
编写程序模拟CPU分配计算资源的过程，已知按照到达时间升序排序的进程数据（包含到达时间、运行时长、优先级），计算并输出每个进程最终处理完成的时间。（时间单位均为毫秒）
请回答下列问题：
（1）有4个进程A、B、C、D如表1所示。

进程	到达时间	运行时长	优先级
A	0	7	1
B	2	4	2
C	4	1	3
D	5	4	2

表1

由优先级抢占式调度算法的规则可知，0毫秒时进程A到达并执行；2毫秒时进程B到达，B的优先级高于A，发生抢占，A剩余的5毫秒回到队列1，B开始执行；4毫秒时进程C到达，C的优先级高于B，发生抢占，B剩余的2毫秒回到队列2，C开始执行；则进程D执行完的时刻为_______。
（2）模拟实现优先级抢占式调度算法Python程序如下，请在划线处填入合适的代码。

def insert(p, remain):

data[p][2]=remain             #更新进程剩余的运行时间

lvl=data[p][3]                       #获取p进程的优先级

if queinfo[lvl][0]=-1:

queinfo[lvl][0]=p

if queinfo[lvl][1]!=-1:

data[queinfo[lvl][1]][-1]=p

queinfo[lvl][1]=p

m=int(input('设置优先级的数量m:'))

# 输入列表data存储进程，data中的节点包含信息有[名称，到达时间，运行时长，优先级]，

代码略

# 进程已经按到达时间升序排序

#例如：data=[['A'，0，7，1]，['B'，2，4，2]，['C'，4，1，3]，['D'，5，4，2]]

for i in range(len(data)):

data[i].append(-1)

queinfo=[[-1, -1] for i in range(m+1)]

insert(0, data[0][2])       #将第1个进程加入队列

time=data[0][1] 0

cnt=1       #所有队列内等待的进程总数

idx=1

lvl=m

while cnt>0:

if queinfo[lvl][0]!=-1:

cur=queinfo[lvl][0]               

queinfo[lvl][0]=data[queinfo[lvl][0]][-1]

cnt-=1

______

while idx < len(data) and time+data[cur][2]>=data[idx][1]:

if lvl >= data[idx][3] or time+data[cur][2]==data[idx][1]:

insert(idx, data[idx][2])

cnt+=1

idx +=1

elif time+data[cur][2]> data[idx][1]:

insert(idx, data[idx][2])       #抢占的进程也先入队

cnt +=1

inset(cur, ______)

cnt +=1

time=data[idx][1]

lvl =data[idx][3]

idx+=1

flag =True

break

if flag==False:

time = time+data[cur][2]

print（"时刻", time, ":进程", data[cur][0], "完成"）

lvl = m

if     ______       :       #仍然有未到达的进程等待入队

insert (idx, data[idx][2])

cnt +=1

time=data[idx][1]

idx += 1

else:

lvl-=1

if lvl==0:

lvl=m

（3）若将以上程序中insert函数内的加框处代码删除，会导致某些情况下无法得到符合程序功能的结果，下列4组数据中能测试出这一问题的是______（单选，填字母）
   

某工厂将送达的各批次物品按品种打包。小李将各批次物品信息按送达时间顺序合并，得到如图a-2所示数据data。同一个包裹只能装入同一品种任意批次的物品，当某一个品种物品A送达使得已送达的该品种物品总重量超过m时，则将在该物品之前送达的物品按重量由大到小依次装入包裹，其余重量不足m的品种，按各品种依次装入包裹。编写程序，读取物品合并更新后的信息，按送达时间顺序打包，输出各包裹中的物品序号，运行结果如图b所示。

序号	品种	送达时间	批次	重量（千克）		序号	品种	送达时间	批次	重量（千克）
1	2	8:35	1	6		1	0	8:30	2	3
2	1	8:50	1	8		2	2	8:35	1	6
3	0	9:10	1	2		3	0	8:40	3	4
4	0	9:15	1	4		4	1	8:50	1	8
						5	0	9:10	1	2
序号	品种	送达时间	批次	重量（千克）		6	0	9:15	1	4
1	0	8:30	2	3		图a-2
序号	品种	送达时间	批次	重量（千克）
1	0	8:40	3	4

图a-1

m=10 data=[1，0，’8:30’，2，3]，[2，2，’8:35’，1，6]，[3，0，’8:40’，3，4]， [4，1，’8:50’，1，8]，[5，0，’9:10’，1，2]，[6，0，’9:15’，1，4] 第1个包裹中品种为0，各物品的序号依次是：3，1，5， 第2个包裹中品种为0，各物品的序号依次是：6， 第3个包裹中品种为1，各物品的序号依次是：4， 第4个包裹中品种为2，各物品的序号依次是：2，

图b

请回答下列问题：
（1）送达物品信息合并后如图a-2所示，若包裹装入物品重量不能超过8千克，则首先打包完成的包裹中装入品种为0，各物品的序号依次是________。
（2）定义data_sort（lst）函数。先将数据（如图a-1中所示）合并得到1st列表（如图a-1中所示），函数data_sort（lst）的功能是对1st列表按送达时间升序排列，并对序号进行更新。
def data_sort（1st）:

for i in range（n-1）:

for j in range（n-1，i，-1）:

if   1st[j][2]<1st[j-1][2]:

1st[j]，1st[j-1]=1st[j-1]，1st[j]

1st[i][0]=i+1

return 1st

执行上述代码后，________（填写：能/不能）正确得到如图a-2中的数据。
（3）实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
def pack（k）:#对品种k已送达待打包的物品按重量由大到小输出

#部分代码略

p=b[k][1]

num+=1

print（″第″+str（num）+″个包裹中品种为″+str（k）+″，各物品的序号依次是:″，end=″ ″）

while p!=-1:

print（data[p][0]，end=″，″）

p=x[p]

″″
合并后排序得到n件物品的数据存储在数组data中并输出，包裹最大承受最大重量为m千克。物品品种的数量是sn，代码略
″″
b=[0，-1] for i in range（sn）]
x=[-1 for i in range（n）]
num=0
for i in range（n）:

k=data[i][1]

if b[k][0]+data[i][4]>m:

pack（k）

b[k]=[0，-1]

p=_______

if p==-1:

b[k][1]=i

else:

             if data[i][4]>data[p][4]:

             b[k][1]=i

_______

             else:

            q=-1

             while_______

        q=p

                 p=x[p]

             x[q]=i

             x[i]=p

b[k][0]+=data[i][4]

#重量不足m的品种，按各品种依次装入包裹
for i in range（sn）:

if   b[i][1]！=-1:

pack（i）

某酒店共有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)

长度为5的循环队列que，que[0] 至que[4]的值依次为'a'，'b'，'c'，'d'，'e'，执行如下程序段后，输出的最后一个字符为
n=5
head = 0
tail= 4
que=['a','b','c','d','e']
while head!=tail：

if head%4==0：

print(que[head] )

else：

tail=(tail+1) %n

que[tail] =que[head]

head=(head+1)%n
print(que[head])

A．b

B．c

C．d

D．e

编写 Python 程序段如下：输入图形的行数，输出由字母“Y”构成的图形，运行效果如图所示。

（1）当输入行数为 10，第 3 行输出____个Y。
（2）请在划线处填入合适代码。
n=int（input（"请输入行数 n:"））
for i in range（1,n+1）:
   s=""
   for j in range ( ) ① :
          s=s+" "
   for j in range( ) ② :
          s=s+"Y"
   print（s）

有如下Python程序段：
import random
a=[]
for i in range(6):
       a.append(random.randint(1,10))
for i in range(5):
       if i%2==0 and a[i] < a[i+1]:
             a[i],a[i+1]=a[i+1],a[i]
       else:
             a[i]-=1
print(a)
运行该程序后，输出结果不可能的是（       ）

A．[7, 3, 3, 4, 9, 4]

B．[8, 8, 10, 5, 7, 8]

C．[9, 4, 9, 4, 8, 7]

D．[7, 2, 9, 7, 4, 5]

读流程图写结果

若输入12，运行结果是__________________。