高效作业12 第12课 栈2——栈应用-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参（浙教版2019）

高效作业12[第12课　栈2——栈应用](见学生用书P216) 学科网（北京）股份有限公司 【A级　新教材落实与巩固】 1．利用栈求逆波兰表达式的值时，若栈只有两个存储单元，下列表达式中，不会发生溢出的是(　C　) A． ABC*－D－　　　　B．ABCD－*－ C． AB－C*D－ D．AB－CD－* 【解析】 逆波兰表达式在处理时，是从前向后遍历表达式字符串，数字入栈，当遇到操作符时，弹出栈顶的两个数字，结合操作符进行计算，再将结果压回栈内，继续这一过程直到结束。选项A、B，入栈的数字量均大于2，超出题干的要求，选项错误；选项D，A－B的计算结果重新压入栈后，CD会继续入栈，此时要求的存储单元数为3，选项错误。故选项C符合题意。 2． 当栈为空时，栈顶top＝－1，利用栈计算逆波兰式“682－2*3/＋”，当即将计算“8－2”时，top的值为(　C　) A．0　 　B．1　 　C．2　 　D．3 【解析】 在利用栈计算逆波兰式“682－2*3/＋”时，6入栈(top＝0)，8入栈(top＝1)，2入栈(top＝2)，当遇到“－”时，即将计算“8－2”，所以此时top的值为2，选项C正确。 3． 执行如下Python 程序段，其中eval(s)函数用来计算参数s 一个字符串表达式，并返回表达式的值，示例：eval('3＋4*3')的值为15。 a＝input('输入字符串').split('，') st＝['']*len(a)；top＝－1 for i in range(len(a))： if a[i] not in'＋－*/' ： 　top＋＝1；st[top]＝a[i] else： st[top－1]＝str(eval(st[top－1]＋a[i]＋st[top]))；top－＝1 print(st[top]) 若输入字符串为“8，4，2，－，2，*，/”， 则输出的结果是(　B　) A．1 B．2 C．4 D．8 【解析】 根据代码分析逆波兰表达式用栈解决的过程：用一个栈存储数字，从左往右扫描该表达式，遇到数字时，入栈；遇到运算符号时，把处于栈最上方的两个元素依次出栈，用运算符计算，并把计算结果压入栈中。如此反复操作，直至表达式扫描结束。所以字符串“8，4，2，－，2，*，/”的计算过程为8/((4－2)*2)＝2，选项B正确。 4．2023·慈溪中学检测小明对入栈、出栈规则研究发现，若有n个数字1，2，3，…，n按由小到大的顺序入栈，则出栈序列必须遵循下述原则：当数字x出栈后，则在x后出栈的小于x的所有数字必定以降序排列，比x大的数字可以夹杂在该降序序列中。现编写Python程序，按上述的原则来验证一个随机产生的出栈序列是否为可能的，程序运行界面如下图所示。 (1)根据题意，若有7个数字入栈，则出栈序列“3→2→5→4→7→1→6”是__B__(单选，填字母：A.可能/B.不可能)的。 (2)实现上述功能的Python程序如下，程序中加框处代码有误，请改正：__s[：－1]__或__s[0：2*n－1]____。 (3)请在横线处填入合适的代码。 import random n＝int(input('请输入入栈元素的个数：　')) data＝[i＋1 for i in range(n)] random.shuffle(data) #将序列的所有元素随机排序 s＝'' for i in range(n)： s＋＝str(data[i])＋'→' print('随机产生的出栈序列为：　'＋) #去除最后多余的'→' flag＝True；i＝0 while i<n－1 and flag： ①__x＝data[i]__ for j in range(i＋1，n)： if data[j]<data[i]： if data[j]<x： x＝data[j] else： ②__flag＝False__ break i＋＝1 if flag： print('该出栈序列是可能的！') else： print('该出栈序列是不可能的！') 【解析】 (1)栈的思维是后进先出，已知当数字x出栈后，则在x后出栈的小于x的所有数字必定以降序排列，比x大的数字可以夹杂在该降序序列中，出栈序列为“3→2→5→4→7→1→6”，其中“7→1→6”，不符合要求。 (2)去除最后多余的'→'，答案为s[：－1] 或 s[0：2*n－1]。 (3)① i位置上的值与之后的每一个位置上的值进行比较，将i位置上的值存储到x中，答案为x＝data[i]；②条件“data[j]<data[i]”表示新遇到数字比i位置值小，再用条件“data[j]<x”判断是否是降序，不成立的话，循环结束，结合后续代码，需要设置flag的值为False，答案为flag＝False。 5．为四则运算式转后缀表达式设计算法： 如：6 ＋ ( 8 － 2 ) * 2 / 3 转换后结果为：6 8 2 － 2 * 3 / ＋ ①用栈来存储运算符号，从左往右扫描四则运算式，遇到数字则直接输出； ②若栈为空或当前运算符号为”(” 时，入栈； ③若栈非空：当栈顶为”(” 则当前运算符入栈；否则将比较优先级，当前运算符大于栈顶元素则入栈，否则栈顶元素出栈输出，直至栈顶元素小于或等于当前运算符时，当前运算符入栈； ④遇到右括号时，则栈顶元素依次出栈输出，直至遇到左括号，左括号出栈但不输出。 (1)四则运算式2 * 6 ＋( 3 ＋ 2 ) / 3 转后缀表达式结果为__2____6__*__3____2__＋__3__/__＋__。 (2)实现上述功能的Python程序如下，请在横线处填入合适的代码。 # 四则运算式6＋( 8 － 2 ) * 2 / 3(中间有一个空格分开) ops_rule＝{'＋': 1，'－': 1，'*': 2，'/': 2} #运算规则的优先级 s＝input(”输入中缀表达式(格式如6＋( 8－2 ) * 2 / 3)：　”) ss＝s.split()；ops＝[] for item in ss： if①__item>＝”0”__and__item<＝”9”__ ： 　　　print(item，” ”，end＝””) else： if len(ops)＝＝0： 　　　②__ops.append(item)__ else： if item＝＝”(”： ops.append(item) elif item＝＝”)”： while len(ops)>0： if ops[－1]＝＝”(”： ops.pop() ③__break__ else： print(ops.pop()，” ”，end＝””) else： while len(ops)>＝0： if len(ops)＝＝0： ops.append(item) break else： if ops[－1]＝＝”(” or ops_rule[item]>ops_rule[ops[－1]]： ops.append(item) break else： print(ops.pop()，” ”，end＝””) while len(ops)>0： print(ops.pop()，” ”，end＝””) 【解析】 (1)后缀表达式，运算符放在运算对象之后。 (2)①遇到数字直接输出，用于判断数字，答案为item>＝”0” and item<＝”9”；②条件“len(ops)＝＝0”成立，表示栈空，直接入栈，答案为ops.append(item)；③遇到“)”右括号出栈，直到遇到“(”结束，答案为break。 6．某一副扑克牌，里面有2个大王和2个小王，看能否抽到顺子。其中大、小王可以看成任何数字，并且A看作1，J为11，Q为12，K 为13。若抽到的牌为“红心A，黑桃3，小王，大王，方块5”，就可以看成“1，2，3，4，5”(大、小王分别看作2和4)，构成顺子。若牌能组成顺子，就输出“可以组成顺子”，否则就输出“无法组成顺子”。 为了方便起见，你可以认为大、小王在输入时用“0”表示。Python程序如下： st＝[＂＂]*5 top＝－1 flag＝True king＝0 str＝input(＂请按扑克牌的从小到大的次序依次输入牌面数值　(大王次序任意，用逗号分隔)：　＂) s＝str.split(”，”) if len(s)＜5： flag＝False else： for i in range(len(s))： if s[i]＝＝＂0＂： king＝king＋1 elif top＝＝－1： ①__top＋＝1__ st[top]＝s[i] elif int(s[i])－int(st[top])＝＝1： top＋＝1 st[top]＝s[i] elif int(s[i])－int(st[top])＜＝king＋1 and②__int(s[i])－int(st[top])＞0__： top＋＝1 st[top]＝s[i] king＝ else： flag＝False break if ③__flag＝＝True__： print(＂可以组成顺子＂) else： print(＂无法组成顺子＂) (1)在横线处填入合适的代码。 (2)程序中加框处代码有误，请改正：__king－(int(s[i])－int(st[top－1]))＋1__。 【解析】 本题通过栈来实现，并用flag标记是否能构成顺子，空①处实现当前的牌入栈； 若当前牌与栈顶牌面值之差不超过king＋1，表示可以用王来补足，当前牌可以入栈，王的数量减少，改错为“king－(int(s[i])－int(st[top－1]))＋1”，其他情况无法构成顺子，将flag值标记为False。 7．2023·温州中学检测某简易作业批改系统由扫描和评分两个子系统组成，现编写Python 程序实现以下功能： ①扫描子系统功能：用扫描程序扫描作业，生成“扫描数据．txt”文件，文件中数据元素各数据项说明如图1所示。 ②评分子系统功能：读取“扫描数据．txt”文件，按序显示作业图片，参照图2所示的规则进行操作，将评分结果保存到Excel 文档中。 (1)实现评分子系统功能的算法程序如下，请在横线处填入合适的代码。 from PIL import Image a＝[””]*1000 head＝tail＝0 f＝open(”扫描数据．txt”，”r”) line＝f.readline() while line： a[tail]＝line.rstrip(” ”).split(”，”) #读取一行数据以逗号分隔保存到列表 tail＋＝1 line＝f.readline() while head<tail： im＝Image.open(①__a[head][1]__ ) #打开图片文件 im.show() #显示 score＝int(input(”请打分：　”)) if score＝＝－1： ②__top＝head－1__ while top>－1： im＝Image.open(a[top][1]) im.show() print(”已评分：　”，a[top][2]) score＝int(input(”请重新打分：　”)) if score>－1： a[top][2]＝score elif score＝＝－2： break top－＝1 else： print(”已经到达第一份”) else： if 0<＝score<＝9： a[head][2]＝score ③__head＋＝1__ else： print(”请重新输入分数：　”) #阅卷完成根据编号获取每份作业得分并保存到Excel 文件中，代码略 (2)若当前显示的是第4 份作业，回评2 份作业后结束回评，则将显示的作业是第__4__份(选填数字：2 /3 /4)。 【解析】 结合题图1与语句“a[tail]＝line.rstrip(” ”).split(”，”)”可以看出，“扫描数据．txt”分行放入了列表a 中。列表a为二维列表，如索引为i 的数据元素，a[i][0]存储编号，a[i][1]存储图片文件名，a[i][2]存储分数。文件中数据逐行读取，tail 指针不断后移，相当于入队操作。接下来逐个批阅，即要进行出队操作。图片文件放在第2 个数据项中，①处填a[head][1]。 依题意，score＝－1 表示回评上一份，程序中直接打开了a[top][1]，说明top 指针指向了head上一条，故②处填top＝head－1；③处为正常打分结束后的处理，head 指针应向后移，准备处理下一个数据，故③处填head＋＝1。 (2)回评使用了top 指针，回评结束后head 指针未加1 保持原位，故填4。 【B级　素养形成与评价】 8．小赵同学在某游戏平台中获得虚拟的食物、装备、材料等物品，他们分别有不同的价值，现游戏平台有兑换机制，可用多种不同物品换取一个等值的物品(每个物品只能取一样)，下表为小赵同学已获得的物品。 序号 物品 数量 单价 0 A 2 1 1 B 1 2 2 C 3 5 3 D 1 7 4 E 1 9 5 F 5 10 6 G 1 15 7 H 1 20 如要换取游戏中的物品“M”，需要35 个金币，有多种置换方式，为方便计算以节省时间，小赵同学编写了如下Python程序，运行界面和代码如下，请在横线处填入合适的代码。 目标置换物品的价值：35 已获得物品价值依次是： 1，2，5，7，9, 10, 15, 20 依次拿取物品序号的方案有： 取序号为[0，1，2，3，7]的物品 取序号为[0，1，3，5，6]的物品 取序号为[0，2，4，7]的物品 取序号为[0，4，5, 6]的物品 取序号为[2，5，7]的物品 取序号为[6, 7]的物品 def exchange(t，pricelist)： n＝len(pricelist) stack＝[] i＝0 num＝0 while①__stack__or__i<n__或len(stack)！＝0__or__i<n__或其他等价答案__： while t>0 and i<n： if t>＝int(pricelist[i])： stack.append(i) ②__t＝t－int(pricelist[i])__或其他等价答案__ i＋＝1 if t＝＝0： print(”取序号为”，stack，”的物品”) num＋＝1 if③__len(stack)！＝0__或其他等价答案__： 　　　i＝stack.pop() 　　　t＋＝int(pricelist[i]) ④__i＋＝1__ if num＝＝0： print(”无方案”) m＝int(input(”目标置换物品的价值：　”)) price＝input(”已获得物品价值依次是：　”) p＝price.split(”，”)#将输入的内容以“，”作分隔，并转换为列表 print(”依次拿取物品序号的方案有：　”) exchange(m，p) 【解析】 本题算法：依次将可能满足条件的物品(t>＝int(pricelist[i]))入栈，同时更新剩余价值(②t－＝int(pricelist[i]))。如果t 为0，说明找到了一种组合方案，输出。一趟查找结束后(内while 循环)，剔除组合的最后一个物品(出栈：i＝stack.pop())，继续尝试下一个编号的物品④i＋＝1 为了找到所有的可能组合，一直要尝试到i＝＝n 并且栈空为止，所以循环条件是：①stack or i<n；为了更好地理解以上算法，分析一下，在得到第一种合适的组合前，栈内物品编号的变化情况： [0，1，2，3，4，5] [0，1，2，3，4] [0，1，2，3，5] [0，1，2，3，6] 第一种组合：取序号为[0，1，2，3，7] 的物品；接下来7 号物品出栈，此时已经没有可以进栈的物品。但是栈不为空，3 号物品出栈，继续以0，1，2 为基础重复以上算法，尝试下一种可能的组合。 9． 一面木板墙，每块木板的宽度都是1，现在想在木板墙上沿着平行于地面的方向切割出一块矩形区域。如果知道每块木板的高度，如何使切出的矩形的面积最大？木板墙如图所示： 图中有7 块木板，每块木板的高度分别为：2、4、4、3、5、1、1。尝试后，我们发现最大的矩形就是波浪部分所示，也就是切割了高度，分别为4、4、3、5的四块木板，形成了一个高度为3、宽度为4 的矩形，这个矩形的最大面积为12。经过尝试可以发现：切下来的最大矩形，一定是以其所在的区域中最短的那块木板为矩形的高度值。 这样我们可以枚举每一块木板，每次都以当前木板作为高度。就是把当前木板当成是切出来的矩形区域中最矮的木板，然后分别向左右延伸，切出此时的最大矩形区域。当把所有的木板都分别尝试过一遍后，我们在所有的结果中比较出最大值，这个最大值就是我们要求的最大矩形的面积。如果木板的数量为n，那么这种算法的时间复杂度接近于O(n2)。但是，如果利用好栈这种数据结构，就能快速的定位左右延伸的最远位置，将算法的时间复杂度降低到O(n)。实现上述时间复杂度为O(n)的Python 程序代码如下，回答以下问题。 (1)如果7 块木板从左往右依次的高度是2、1、4、5、1、3、3，切割出来的最大矩形面积是__8__。 (2)请在横线处填入合适的代码。 h＝[2，4，4，3，5，1，1] n＝len(h) # L[i]保存的是比当前木板高度低的且离当前木板最近的左侧木板位置 # R[i]保存的是比当前木板高度低的且离当前木板最近的右侧木板位置 L，R＝[0]*n，[0]*n st，top＝[0]*n，－1 for i in range(n): # 生成列表L相应数据 while top！＝－1 and①__h[st[top]]>＝h[i]__： top－＝1 if top＝＝－1： L[i]＝－1 else： L[i]＝②__st[top]__ top＋＝1 st[top]＝i top＝－1 for i in range(n－1，－1，－1): # 生成列表R 相应数据 # 代码略 ans＝0 for i in range(n): # 遍历所有木板，取最大面积 s＝③____(R[i]－L[i]－1)*h[i]__ if s>ans： ans＝s print(ans) 【解析】 本题通过栈结构将O(n2)的算法优化为O(n)的算法，体现出了算法与数据结构的相辅相成。在栈优化后的算法中，由于每个元素至多入栈、出栈1 次(即至多被访问2 次)，因此计算L[i]和R[i]的过程复杂度均为O(n)。以L[i]的计算为例，由于L[i]的含义为“在第i 个木板左侧，高度低于h[i]的最近木板位值”，因此只需要维护一个升序栈st，记录在第i 个木板之前连续位置木板高度的升序列，在计算L[i]时从栈顶依次访问该序列时实际上就变成了降序列，找到第一个h[st[top]]<h[i]的位值st[top]为止。关于L[i]与R[i]的关系示意图如下： (1)根据题意模拟数据即可，以4 为最低木板的矩形切割为最大矩形，面积为8。 (2)代码填空的难点是第①空，需要理解上图中关于L[i]的含义。在初读代码时，可以根据for 循环末尾的st[top]＝i 的入栈操作，明确栈中存储的元素类型：索引(即序列中的元素位置)，那么h[st[top]]才是栈顶元素所表示的木板高度。要使得i 入栈时维持h[st[top]]是升序的，则必须将大于等于h[i]的元素位置依次出栈后再入栈，即第①空答案为h[st[top]]>＝h[i]。第②空计算L[i]，若栈未空，即h[st[top]]< h[i]，那么距离第i 个木板最近的高度低于该木板的位置为当前栈顶元素位置st[top]，即答案l[i]＝st[top]。第③空时答案的计算，根据题意，枚举每一块木板，以第i 块木板为最低高度，计算切割的矩形面积同时求最大值。 由上表可知，矩形左端点为L[i]＋1、右端点为R[i]－1，利用矩形面积公式s＝长×宽得到答案：(R[i]－L[i]－1)*h[i]。 10．2023·知临中学检测一款智力玩具有x 种颜色的n 个不同直径的同心圆盘(x<n)。将圆盘串在倒T 字形支架上，垂直俯视，直径不大于上方的圆盘将被遮挡，现从上方依次取走一片圆盘，记下能看到的颜色。最后说出取走几片圆盘后看到哪种颜色的种数最多，并说出颜色。某人取了6 片5 种颜色的圆盘随机叠放，如图1所示。他编写了如下程序来验证自己的结果是否正确，程序运行结果如图2所示。 请回答下列问题： (1)函数pop() 的功能是__将看不见的木板出栈(小于等于当前木板)，返回新的栈顶位置(top)和可以看见的颜色数量(cnum)__。 (2)实现上述功能的部分Python程序如下，请在横线处填入合适的代码。 ''' 随机选取n 个圆盘，其半径与颜色分别存储在列表r 和color 中并输出，如图2所示 ''' r＝[9，3，6，4，8，5]；color＝['红'，'紫'，'蓝'，'绿'，'橙'，'红'] n＝len(r) f＝{} # f 中键为颜色，值为该颜色的可见数量，如：{”蓝”：2} def pop(top，cnum，rad)： while top！＝－1 and rad >＝r[z[top]]： f[color[z[top]]]－＝1 if①__f[color[z[top]]]＝＝0__： cnum－＝1 top－＝1 return top, cnum z＝[－1]*n top＝－1 cnum＝cmax＝0 for i in range(n)： top, cnum＝pop(top，cnum，r[i]) top＋＝1 ②__z[top]＝i__ if color[z[top]] not in f： f[color[z[top]]]＝1 else： f[color[z[top]]]＋＝1 if f[color[z[top]]]＝＝1： cnum＋＝1 if cnum>＝cmax： cmax＝cnum res＝dict(f)　# 将此时的f 另存到res 中 m＝③__n－(i＋1)__ s＝”” for i in res： if res[i]>0： s＋＝i print(”拿走”，m，”片后，可看到圆盘的颜色种数最多，分别为：　”，s) 【解析】 (1)对于函数pop(top，cnum，rad)，根据代码“top，cnum＝pop(top，cnum，r[i])”可知，该函数的目的是更新top 和cnum 变量。而这两个变量top 用于记录栈顶索引，cnum 用于记录当前可见圆盘的种类数，且在pop()函数内这两个变量值只会减少不会增加，因此推测pop()函数的功能是出栈操作。从第三个实参r[i]分析，对于当前圆盘半径r[i]，对小于等于该半径的圆盘出栈，则pop()函数的功能可以具体描述为“随着第i 个圆盘的插入，垂直俯视下，删除不可见圆盘，计算可见圆盘的个数top 与种类cnum”。 (2)当半径为rad 的圆盘插入后，半径小于等于rad 的圆盘将不再可见，维护降序栈规则为依次将栈顶开始的小于等于rad 的圆盘出栈。随着圆盘出栈，可见圆盘的颜色种类可能发生变化， 即如果该圆盘是该颜色唯一圆盘， 出栈后种类数减1, 即第①空答案f[color[z[top]]]＝＝0。将不可见圆盘出栈后当前圆盘可以入栈，此时保证当前栈顶元素是栈内最小元素，即降序栈，所以第②空答案为z[top]＝i。这一空可能会犹豫是i 还是r[i]，需要关注z 列表的元素访问，z[top]的值可以作为r 和color 的索引，说明z[top]的值表示的是圆盘原始编号而非半径，因此z[top]＝i 是唯一答案。最后在更新cmax 时，随之更新的变量m 可以从输出语句中知道，m 记录当前拿走的圆盘数。根据一般模拟：当i＝0 时，插入了第1 个圆盘，此时相当于拿走了n－1 个圆盘，当i＝n－1 时，插入了最后一个圆盘，此时相当于拿走了0 个圆盘，因此第③空答案为n－(i＋1)。 11．一列货运列车有n 节车厢，每节车厢将停放在不同车站。假定n 个车站的编号分别为1～n，列车按照由第n 站至第1站的顺序停靠，车厢编号与目的站序号相同。为了到每个站时只需卸掉最后一节车厢，必须将任意次序的车厢进行重排，使得各车厢从前往后的编号顺序是1～n。重排车厢的工作在一个转轨站里完成，如图所示，在转轨站中有一个入轨、一个出轨和k(k＝3)个缓冲轨H1，H2，H3。开始时n 节车厢从入轨处进入转轨站，转轨结束后，车厢按编号1～n 的次序离开转轨站。 编写程序模拟有n(n＝9)节车厢的“入轨”和“出轨”过程(入轨车厢次序满足缓冲轨为3 的情况)。 车厢可以从入轨的前部移动到一个缓冲轨的顶部或者是出轨处的后部。进入缓冲轨的车厢编号要满足： ①小于要进入的缓冲轨的栈顶元素编号。 ②满足条件①里面栈顶元素编号最小的缓冲轨。 ③若没有满足条件①的缓冲轨，则进入空的缓冲轨。 (1)若在入轨处的车厢次序是3，6，9，2，4，7，1，8，5，则2 号车厢进入的缓冲轨是__H1__(选填：H1/H2/H3)。 (2)实现上述功能的Python程序如下，请在横线处填入合适的代码。 def inputStack(bh，stacks，n): # 将车厢移到缓冲轨处 　　　global minNum，minStack，k bestStack＝－1 # bestStack 记录最小车厢编号所在的缓冲轨编号 bestTop＝n＋1 # bestTop 记录缓冲轨中的最小车厢编号 for i in range(k)： if len(stacks[i])>0： top＝stacks[i][－1] if①__bestTop>top>bh__或其他等价答案__： 　　　bestTop＝top 　bestStack＝i else： if bestStack＝＝－1： bestStack＝i if bestStack＝＝－1： return False stacks[bestStack].append(bh) print('将%d号车厢从入轨处移到缓冲轨道H%d 处。　' %(bh，bestStack＋1)) if bh<minNum： minNum＝bh minStack＝bestStack return True def output(stacks，n)： #将缓冲轨中的剩余车厢按顺序依次移到出轨处，代码略 #主程序开始 list＝[3，6，9，2，4，7，1，8，5] #车厢的原始编号存放在列表list 中 n＝len(list) k＝3 hStacks＝[②__[]__ for i in range(k)] curBH＝1 minStack＝－1 print(”车厢重排过程如下：　”) i＝0 while i<n： if list[i]＝＝curBH： print(”将%d号车厢从入轨处直接移到出轨处。　”%list[i]) ③__curBH＋＝1__ i＋＝1 continue while True： minNum＝n＋1 for j in range(k)： if len(hStacks[j])>0： if hStacks[j][－1]<minNum： minNum＝hStacks[j][－1] minStack＝j if minNum＝＝curBH： print(”将%d号车厢从缓冲轨道H%d移到出轨处。　”%(minNum，minStack＋1)) hStacks[minStack].pop() curBH＋＝1 else： ④__inputStack(list[i]，hStacks，n)__或其他等价答案__ i＋＝1；break while curBH<n＋1： output(hStacks，n)；curBH＋＝1 print(”完成车厢重排　！”) 【解析】 (1)根据算法，编号3、6、9 分别入H1、H2、H3 缓冲轨，最小的编号是H1 缓冲轨，且2 比3 小，进入H1 缓冲轨。 (2)将入轨处的车厢次序(列表)位置调整为车厢按编号1～n 的次序离开转轨站，若入轨的次序正好与出轨次序一致，则无须进入缓冲轨，如入轨处的车厢次序是1，2，5，3，4，其中1 和2 号车厢直接出轨。①是找到进入第几个缓冲轨的条件，并找到最小车厢编号所在的缓冲轨编号。遍历3 个缓冲轨，如果当前缓冲轨为空，则直接入轨，若不空则找到编号最小的栈，先取出栈顶元素编号top，入轨编号bh 要小于top，bestTop 的初值为－1，在3 个缓冲轨中的找到一个最小车厢编号，因此入轨的条件有两个，一是bh 小于top，二是找到最小编号缓冲轨。②创建k 个空栈，保存各个缓冲轨中车辆编号。③处理直接出轨的情况，那么出轨的序号加1。④调用inputStack 对列表list 中索引号为i 的编号进行入栈操作。minNum 是当前栈中最小的编号，肯定在栈顶，若其值与curBH 相等，则先处理出栈操作，否则对第i 个元素进行入栈操作。 学科网（北京）股份有限公司 $$