深耕专业教研，探索前沿技术
信息技术来源：诸暨市2026年5月高三诊断性考试

第 15 题

答案与解析

第(1)小题

参考答案

不能

没有共同成员的两个项目才能相邻。逐对比较参加人员，得到：

项目 可以与它相邻的项目
1 6
2 3、4、5、6
3 2
4 2、5
5 2、4
6 1、2

项目1只能与项目6相邻，项目3只能与项目2相邻，因此项目1、3必须分别位于整个展示顺序的两端。若从项目1这一端开始，前两个项目只能是1、6；项目6除项目1外只能连接项目2，所以接下来必须是2。另一端的项目3又必须紧邻项目2，于是形成1、6、2、3这一条顺序，项目4、5无法插入。因此不能排定包含全部6个项目的合理顺序。

第(2)小题

参考答案

has_common(last, new)

程序分析

def can_place(last, new):
    if last == 0:
        return True
    if :
        return False
    else:
        return True

last表示前一个项目的编号，new表示准备放入的项目编号。last为0时表示前面没有项目，可直接返回True；否则执行后面的判断，条件成立时返回False，不成立时返回True。题目提供的has_common函数可用于判断两个项目是否有共同成员。

填空分析

划线处

有共同成员时，new不能紧接在last后面，应进入return False分支。因此直接调用has_common判断这两个项目，填写：

has_common(last, new)

第(3)小题

参考答案

  1. used[cur]

  2. top += 1

  3. used[prepro] = False

程序分析

order = []
success = find_valid_order()

主程序调用find_valid_order寻找合法展示顺序，返回值保存到success。进入函数后，global order使函数中的赋值更新主程序使用的order。

def find_valid_order():
    global order
    used = [False] * (pcount + 1)
    order = [0] * pcount  # 记录最终排好项目顺序
    stack = [[0,0] for i in range(pcount)]; top = -1
    pos = 0; cur = 1
    while pos < pcount:
        if pos == 0:
            ...
        else:
            ...
        found = False
        while cur <= pcount:
            ...
        if not found:
            ...
    return True

函数先创建used、order和stack，分别初始化为布尔值列表、长度为pcount的列表和保存两个数据项的列表，并将top设为-1。pos从0开始，cur从1开始；外层循环反复尝试安排项目，直到pos达到pcount。下面结合读取、写入和回退操作确定这些变量的具体作用。

if pos == 0:
    pre = 0
else:
    pre = order[pos - 1]
found = False

pos为0时，将pre设为0；否则读取order[pos-1]作为pre，与第（2）问的参数last对应。由此可知，pos是当前待安排位置的下标，pre是前一个位置的项目编号。每次尝试安排当前位置前，将found设为False。

while cur <= pcount:
    if ①:
        cur = cur + 1
    else:
        if can_place(pre, cur):
            used[cur] = True; order[pos] = cur
            ②; stack[top] = [pos, cur]
            pos = pos + 1; cur = 1
            found = True
            break
        else:
            cur = cur + 1

内层循环用cur从当前候选编号开始逐个尝试项目。进入第一个分支时直接将cur增加1，跳过该候选；否则调用can_place(pre, cur)，判断它能否接在前一个项目后面。

若可以相邻，程序把used[cur]设为True，并将cur写入order[pos]。这两条语句共同表示项目cur已被选入当前顺序，因此used按项目编号记录是否已选用，order按展示位置保存项目编号。

随后把[pos, cur]写入stack[top]，保存本次选择的位置和项目编号。pos增加1后转向下一个位置，cur重置为1，从项目1重新尝试；found设为True并通过break结束本轮候选搜索。若不能相邻，则继续尝试下一个编号。

if not found:
    if top == -1:
        return False
    pos, prepro = stack[top]; top = top - 1
    ③; order[pos] = 0
    cur = prepro + 1

如果本轮没有找到可放入的项目，就进入回退分支。top为-1时返回False；否则从stack[top]取回最近一次选择的[pos, cur]，将两个数据分别交给pos和prepro，再把top减1。结合前面的保存操作，可以确定stack用作栈，top是栈顶下标：每次回退取出最近一次选择，符合后进先出的顺序，top=-1表示栈为空。

回退后，order[pos]=0撤销这个位置的项目，cur=prepro+1使下一轮从被撤销项目的下一个编号继续尝试。此时还需要同步撤销相应的已选用标记。若没有可退回的选择，则全部方案已尝试完；若外层循环正常结束，则所有位置均已排好，返回True。

if success:
    print("合法展示顺序：")
    # 输出代码略
else:
    print("无法生成合理顺序！")

函数返回True时，主程序输出order中保存的合法顺序；返回False时，输出无法生成合理顺序的提示。

整体功能

程序逐个位置尝试未使用且可与前一项目相邻的项目，并用栈保存选择。某个位置无法继续安排时，就撤销最近一次选择，改试其他项目；因此它能通过回溯搜索寻找完整的合法顺序。

填空分析

①

每个项目只能安排一次。used[cur]为True表示项目cur已在当前顺序中，此时应跳过它，执行cur=cur+1。因此填写：

used[cur]

②

选定项目后，要将本次选择入栈。top指向原栈顶，应先将top增加1，再由已有语句stack[top]=[pos, cur]写入新栈顶。填写：

top += 1

空栈时top=-1，增加1后为0，首次选择正好存入stack[0]。

③

出栈后prepro保存被撤销的项目编号。order[pos]=0只清除了展示位置，还要把该项目的已选用标记恢复为False，使它能在后续位置重新参与选择。填写：

used[prepro] = False

used按项目编号索引，因此使用prepro，而不是展示位置pos。