深耕专业教研，探索前沿技术
信息技术来源：浙江省县域教研联盟高三年级5月高考模拟考试

第 15 题

答案与解析

第(1)小题

参考答案

4

08:50～09:20期间，101、201、104、202四个班同时训练，每个班都需要一根绳子，所以至少需要4根。

4根绳子也能满足全部安排：

绳子编号 班级及使用时段
1 101：07:30～10:30
2 201：08:20～09:30
3 104：08:30～09:20；301：09:40～11:30
4 202：08:50～09:55

104班09:20结束后，该绳子从09:21起可复用，满足301班09:40开始的要求。因此最少需要4根。

第(2)①小题

参考答案

B

程序分析

def d_sort(data,k):
    i = p = q = len(data) - 1
    while i > 1 and q != 0:
        j = q = 0
        while j < p:
            if data[j][k] > data[j+1][k]:
                data[j],data[j+1] = data[j+1],data[j]
                q = j+1
            j += 1
        p = q - 1
        i -= 1
    return data

初始p=len(data)−1，内层j从0到p−1，比较位置j与j+1。每轮先令q=0；发生交换时执行q=j+1，因此一轮结束后的q记录最后一次交换涉及的右侧位置，没有交换时q仍为0。

一轮扫描后，从位置q开始的后缀已经就位，下一轮只需继续处理0～q−1，所以原程序令p=q−1。若整轮没有交换，则p变为−1，之后因q=0退出。

另需注意，i初值为n−1而循环要求i>1，最多只执行n−2轮，少于冒泡排序一般所需的最多n−1轮。例如关键字[3,2,1]只执行一轮就返回[2,1,3]。下面两个小问均依据给出的实际程序分析，不将其视为对任意输入都能完成排序。

解题思路

内层循环从左向右比较相邻记录，若左侧第k项较大就交换，使较大的关键字向右移动，这是冒泡排序。这里用最后一次交换的位置缩小下一轮比较范围。

原写法p=q−1使下一轮最后一次比较位置q−2与q−1；改为p=q后，只增加位置q−1与q的比较。上一轮最后一次交换后，位置q及其右侧元素已就位，这次额外比较不会交换，也不会改变最后交换位置的记录。

若上一轮没有交换，则q=0，外层循环直接结束。因此两种写法返回的数据相同，选B。

第(2)②小题

参考答案

-1

共用程序分析见第(2)①小题。

按第1项排序，开始时间的初始顺序为450、500、510、580、530，初始p=4。

轮次 本轮交换情况 扫描后的开始时间顺序 q 更新后的p
第1轮 只在j=3时交换580与530 450、500、510、530、580 4 3
第2轮 j=0、1、2的比较均不交换 450、500、510、530、580 0 −1

第2轮结束后仍会先执行p=q−1，得到−1，下一次检查循环条件时才因q=0退出。因此p经历4、3、−1，最小值为−1。

第(3)小题

参考答案

  1. p==head

  2. data[0][3]=cnt

  3. head=ins(lnk,head,data[i][2],data[i][3])

程序分析

ans_cnt,ans_lst = proc(data,n)

主程序把各班的训练记录传给proc。原始data每行依次为班级编号、开始时间、结束时间；proc需要返回绳子总数及附有绳子编号的各班记录。

def proc(data,n):
    lnk = []  # 构造一个空链表
    data = d_sort(data,1)
    for i in range(n):
        data[i].append(0)
    cnt = 1  # 采购的绳子从1开始编号
    ②
    lnk.append([data[0][2],data[0][3],-1])
    head = 0

第（3）小题将d_sort的功能约定为升序排序，此处按开始时间安排处理顺序。每行追加一个0，为后续记录分配结果预留位置；cnt从1开始计数。

lnk的首条记录为[data[0][2],data[0][3],−1]，其中第0项是结束时间。后续通过lnk[p][2]转向下一结点，可知第2项保存后继结点下标，−1表示没有后继；head保存首结点下标。

    for i in range(1,n):
        if data[i][1] > lnk[head][0]:
            data[i][3] = lnk[head][1]
        else:
            cnt += 1
            data[i][3] = cnt
        ③

后续班级按开始时间依次处理。若当前开始时间严格大于首结点的结束时间，就把该结点第1项赋给data[i][3]；否则增加绳子数量cnt，再把新编号赋给data[i][3]。由两分支可知，data的第3项和lnk的第1项都保存绳子编号。

题干规定绳子从结束时间的下一分钟才能复用，所以比较使用严格大于。要让这一步优先找到可复用的绳子，链首需要对应最早结束的占用记录。

def ins(lnk,head,x,y):  # 插入
    p = head
    ...
    return head

ins接收链表、头指针和待插入的两个数据项x、y，先从首结点开始查找，最后返回插入后的头指针。

while p != -1 and lnk[p][0] <= x:  # 找到插入位置
    q = p
    p = lnk[p][2]

当当前结点第0项不大于x时，先让q保存该结点下标，再让p沿第2项转到后继。循环结束时，p指向第一个第0项大于x的结点，或为−1表示到达表尾；若已经向后移动过，q就是插入位置的前驱结点下标。因此该遍历用于保持第0项升序。

if ①:
    lnk.append([x,y,head])
    head = len(lnk)-1
else:
    lnk.append([x,y,p])
    lnk[q][2] = len(lnk)-1

第一个分支把新结点的后继设为原head，再让head指向新结点，完成首部插入。另一个分支让新结点连接p，再把前驱q的后继改为新结点，完成中间或尾部插入。append只增加存储结点，链接修改决定它在链表中的逻辑位置。

ans_lst = d_sort(ans_lst,0)  # 根据班级编号进行排序
for i in range(len(ans_lst)):  # 输出各班级训练用的绳子编号
    print(ans_lst[i][0],ans_lst[i][3])

proc返回后，按班级编号重新排列结果，并输出每个班与所分配绳子编号的对应关系；这次排序只用于整理输出顺序。

填空分析

①

首部插入发生在遍历没有向后移动时，此时p仍等于head，填写p==head。空链表中p和head同时为−1，也会进入这一分支。若p已经离开head，说明循环至少执行过一次，q已经保存前驱下标，可以使用后面的lnk[q][2]完成链接。

②

第一个班使用编号为1的绳子，cnt已设为1；其记录追加的第3项用于保存绳子编号，并且下一句会读取data[0][3]建立链表结点，所以填写：

data[0][3]=cnt

③

两个分支都已为当前班确定data[i][3]，还需把它的结束时间data[i][2]与绳子编号一起插入链表。ins可能改变首结点，必须用返回值更新head，填写：

head=ins(lnk,head,data[i][2],data[i][3])

这条语句完成插入，但原程序在复用绳子后没有移除旧的首结点，会留下该绳子的过期结束时间。例如三个训练区间依次为[0,1]、[2,10]、[3,9]：第二个班复用绳子1后，旧的结束时间1仍在链首，第三个班也会被分配绳子1，而后两个班的训练时间重叠。这说明原程序还缺少复用后移除过期结点的操作。