深耕专业教研，探索前沿技术
信息技术来源：宁波市 2025 学年第二学期高考模拟考试

第 11 题

答案与解析

本题解析

参考答案

D

程序分析

top1 = len(s1)-1
top2 = -1
k = 0
while top1 != -1:
    ...

题目已说明s1、s2用于存储两个栈。top1、top2分别指向栈顶，下标0为栈底，-1表示空栈；s1初始有n个有效元素，s2初始为空。外层循环在s1非空时继续处理。栈的有效范围由栈顶下标决定，不能用列表中是否还留有旧值来判断栈是否为空。

temp = s1[top1]
top1 -= 1
k += 1

取出s1栈顶元素保存到temp，再将栈顶下标减1，完成一次出栈。k每次加1，统计从s1取出元素的总次数；此处没有删除或清空列表中的原存储项。

while top2 != -1 and temp < s2[top2]:
    top1 += 1
    s1[top1] = s2[top2]
    top2 -= 1

当s2非空且其栈顶元素大于temp时，将该元素压回s1，并把s2栈顶下标减1。循环持续移走s2顶部比temp大的元素，直到s2为空或栈顶元素不大于temp。这里比较的是字符串，按字符编码逐位比较，例如'105' < '33'。

top2 += 1
s2[top2] = temp

将temp压入s2。此前比temp大的栈顶元素已移走，因此这次插入保持s2从栈底到栈顶按字符串顺序非降序。被移回s1的元素还会在后续外层循环中再次取出。

选项分析

A

错误。该过程通过移动元素保持s2有序，类似插入排序。最坏情况下，第j个原始元素插入时需移回此前的j−1个元素，移动总数为0＋1＋…＋(n−1)，后续再次取出这些元素的次数也与该数量同阶，时间复杂度为O(n²)。

B

错误。根据前述字符串比较规则，s2从栈底到栈顶为['105','110','33','98','99']。

C

错误。k包含原有n个元素各取出一次，以及移回s1后再次取出的次数。当s1从栈底到栈顶已按字符串顺序非升序时，取出顺序非降序，无须移回任何元素，此时k＝n。

D

正确。仅列出内层循环改写s1的关键时刻：

外层轮次 temp 从s2移回s1的元素顺序 改写后的完整s1列表
3 '105' '99'、'33' ['110','98','99','33','33']
6 '98' '99' ['110','99','99','33','33']
8 '110' '99'、'98'、'33' ['99','98','33','33','33']

此后依次取出'33'、'98'、'99'，没有元素再移回s1。最终top1＝−1，s1作为栈已空，但出栈只改变栈顶下标，完整列表仍为['99','98','33','33','33']。