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

第 12 题

答案与解析

本题解析

参考答案

D

解题思路

函数以长度不超过1的列表为出口，对划分后规模更小的列表调用自身，再拼接结果，属于递归。

程序分析

if len(lst) <= 1:  # ①
    return lst

空列表或单元素列表直接返回，不再划分。

p = lst[0]
left, right = [], []
for x in lst[1:]:
    if x[0] <= p[0]:  # ②
        left.append(x)  # 将元素x放置在列表left的最末尾处
    else:
        right.append(x)  # 将元素x放置在列表right的最末尾处

以首元素p为基准，按第1个数据项比较：不大于p[0]的元素依次加入left，其余元素加入right。等值元素也进入left。

return q(left) + [p] + q(right)

两侧分别处理后，按“左侧结果＋基准＋右侧结果”拼接，得到按第1个数据项升序排列的列表。

选项分析

A

正确。函数的出口和自调用构成上述递归结构。

B

正确。第一层以[7,0]为基准，左侧为[[2,1],[2,3],[5,4]]，右侧为[[9,2]]。左侧再以[2,1]为基准，[2,3]进入其左侧，[5,4]进入其右侧；三个单元素列表直接返回。逐层拼接得到[[2,3],[2,1],[5,4],[7,0],[9,2]]。

C

正确。出口改为len(lst)<1后，单元素列表会再划分一次，两侧均为空列表；返回时仍拼接为原来的单元素列表，结果不变。

D

错误。比较条件改为x[0]<p[0]后，[2,3]进入[2,1]的右侧，两个第1项为2的元素次序交换，结果发生变化。