0 返回首页
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))
【考点】
过程与自定义函数; 分支结构语句及程序实现; 循环结构语句及程序实现;
【答案】

您现在未登录，无法查看试题答案与解析。 登录
综合题 困难
能力提升
真题演练
换一批
1. 某酒店共有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)
综合题 困难
2. 操作系统在管理磁盘时，会将磁盘分为一个个“盘块”。在为文件分配空间时，可以将文件装到离散的盘块中。读取一个文件时，首先在目录结构中找到文件项。从文件项中可以获取文件名、存储时间、该文件在存储块中的起始地址等基本信息，但不包含文件具体内容，然后在磁盘文件分配表中找到对应的文件。磁盘文件分配表如图 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]
综合题 困难
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])
综合题 困难