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

高效作业11[第11课　栈1——初识栈](见学生用书P213) 学科网（北京）股份有限公司 【A级　新教材落实与巩固】 1．我们用浏览器上网时，页面左上角有一个“后退”键，点击后可以按访问顺序逆序加载浏览过的网页，由此可知，我们浏览过的网页信息最有可能存储在下列哪种数据结构中？(　C　) A．链表　　B．字典　　C．栈　　D．队列 【解析】 题目中逆序加载浏览过的网页，符合栈的先进后出的特点，选项C正确。 2． 下列事件操作的原理与栈的特点不同的是(　C　) A．杂技演员在表演叠罗汉的时候，最后上去的人总是第一个下来 B．在Word、Photoshop等文档或图像编辑的软件中，执行“撤销”操作 C．在火车站排队买票或者在超市排队购票 D．多个函数嵌套调用时，按照“后调用先返回”的原则进行 【解析】 排队买票与栈的先进后出的特点不符，与队列的特点相符，选项C错误。 3． 下列关于出栈和进栈操作的说法中，正确的是(　D　) A．入栈操作时，先存放元素，然后栈顶指针top加1 B．出栈操作时，先栈顶指针top减1，然后取出栈顶元素 C．若栈为空，将不能进行出栈和入栈操作 D．若栈已满，可以进行出栈操作，但不能进行入栈操作 【解析】 根据栈的特性，若栈已满，只能进行出栈操作，选项D正确。 4．有A、B、C、D、E 五个人依次进入电梯，结果警告超重了，需要出去一个人，才能正常运行，按照数据结构中栈和队列的思维，应离开电梯的人分别是(　C　) A．栈：A　 队列：E B．栈：A　 队列：A C．栈：E　 队列：A D．栈：E　 队列：E 【解析】 栈的思维为后进先出，则E出；队列的思维为先进先出，则A出。选项C正确。 5． 一个序列的入栈顺序为a，b，c，d，e，则该序列的出栈顺序不可能为(　C　) A．b，a，d，c，e B．d，c，b，a，e C．d，c，e，a，b D．c，b，a，e，d 【解析】 b应当在a的前面，选项C错误。 6．已知5个元素的出栈序列是1，2，3，4，5，则入栈序列可能是(　D　) A．2，4，3，1，5 B．2，3，1，5，4 C．3，1，4，2，5 D．3，1，2，5，4 【解析】 根据出栈顺序：选项A，1应比3入栈晚，选项错误；选项B，2应比3入栈晚，选项错误；选项C，3应比4入栈晚，选项错误。 7．元素x1，x2，x3，x4，x5，x6依次入栈，若第1个出栈的元素是x4，则不可能是第3个出栈的元素是(　A　) A．x1 B．x2 C．x3 D．x5 【解析】 由于第1个出栈的是x4，此时栈中有元素x1、x2和x3，因此x3、x2 必在x1之前出栈，即x1不可能第3个出栈，选项A正确。 8．有一组数据4，2，6，3，1，5，按顺序入栈，则出栈的顺序可能是(　D　) A．4，2，5，3，1，6 B．1，3，5，2，6，4 C．6，4，2，3，5，1 D．6，2，4，3，1，5 【解析】 选项A，5 出栈意味着6、3、1 在栈内只能1 比3 先出，选项错误；选项B，1 出栈意味着4、2、6、3 在栈内只能2 比4 先出，选项错误；选项C，6 出栈意味着4、2 在栈内只能2 比4 先出，选项错误。 9． 公交车上有时候会出现由于人太多无法挤到后门下车而从前门下车的情况，因此，若一个序列在有3 个或以下元素时，按队列方式离开序列，但在(3 个以上)元素时，按栈方式离开序列，则对于依次进入序列的x1，x2，x3，x4，x5，x6，离开序列的顺序可能为(　B　) A．x1，x4，x6，x2，x3，x5 B．x4，x1，x6，x2，x3，x5 C．x1，x2，x3，x6，x4，x5 D．x6，x5，x4，x3，x1，x2 【解析】 选项A，x1 离开，x4 上车时，车上有3 个人，此时人要应遵循队列方式，离开的应为x2，选项错误；选项B，x4 上车后，车上4 人，遵循栈的方式故x4 可离开。之后剩3 人，遵循队列，故x1 可离开，此时剩余x2，x3 两人，x6上车后，车上4 人，故x6 可离开，剩3 人，按队列方式，x2，x3，x5 依次离开，选项正确；选项C，在x1，x2，x3 分别离开后，剩3 人，离开顺序应为x4，x5，x6，选项错误；当6 人都上车后，按栈方式分别离开x6，x5，x4，剩3 人，按队列离开，选项错误。 10．若入栈顺序为1，2，3，4，5，6，7，出栈序列为1，4，3，2，7，6，5，则栈深度至少是(　A　) A．3 B．4 C．5 D．6 【解析】 由“入栈顺序为1，2，3，4，5，6，7，出栈序列为1，4，3，2，7，6，5” ，可以推测出元素出入栈的过程，即1入栈，1出栈，2入栈， 3 入栈， 4入栈， 4出栈， 3 出栈， 2 出栈， 5入栈，6入栈，7入栈， 7出栈， 6 出栈， 5出栈。因此在整个操作过程中达到的栈深度最大为3，选项A正确。 11．某APP 采用栈结构处理数据，具体的规则如下： ①输入待加入的元素，并转到②； ②若栈为空，则转到⑤，否则转到③； ③若当前待加入元素与栈顶元素的值相同，则转到④，否则转到⑤； ④将栈顶元素出栈，并转到①； ⑤将当前待加入元素入栈，并转到①。 将元素“ABBACAAAD”按以上规则依次入栈，则处理后栈中元素从栈底至栈顶依次是(　B　) A．C D B．C A D C．A A C D D．A B C A D 【解析】 ①入栈时，若栈为空，直接入栈；②入栈时，若栈不为空，若与栈顶相同，不入栈，且让栈顶出栈；③入栈时，若栈不为空，若与栈顶不同，直接入栈。则该题为，A 入栈，B 入栈，B 不入栈且让B 出栈，A 不入栈且让A 出栈，此时栈为空；C 入栈，A 入栈，A 不入栈且让A 出栈，A 入栈，D 入栈；最终，结果为CAD，选项B正确。 12．2023·北仑中学检测用一个带盖的玻璃筒来放取乒乓球，放、取只能在带盖的一端进行(另一端为封闭状态)，且筒的直径只允许一个乒乓球进出。若放入球的编号序列为1、2、3、4，则取出球的编号序列不可能的是(　C　) A．1、2、3、4 B．2、3、4、1 C．4、2、3、1 D．3、2、1、4 【解析】 乒乓球入栈的顺序为1－2－3－4，当4 号乒乓球出栈时，栈顶的球为3 号，选项C错误。 13．将一个数的质因数进行分解并输出，如300＝5×5×3×2×2，Python程序段如下： n＝int(input(＂请输入一个正整数：　＂)) s＝[] i＝2 while n>1： if n%i！＝0： (1)____________# else： n//＝i (2)____________# while len(s)！＝0： print((3)____________，end＝＂＂) if len(s)！＝0： print(＂*＂，end＝＂＂) 上述程序段中横线处的代码由以下三部分组成： ①s.append(i)　②i＋＝1　③s.pop() 下列选项中，代码顺序正确的是(　B　) A．①②③ B．②①③ C．②③① D．①③② 【解析】 程序把分解出的质数逐个入栈，入栈后再按先进后出的规律出栈，选项B正确。 14．有如下Python 程序段： s＝input(”请输入字符串：　”) a＝[””]*10；a[0]＝s[0]；t＝0 for i in range(1，len(s))： if t>＝0 and s[i]＝＝a[t]： t＝t－1 else： t＝t＋1 a[t]＝s[i] 执行该程序段，输入以下字符串后，变量 t 的值与其他三项不同的是(　B　) A．＋＋**＋ B．＋*＋** C． *＋**＋ D．*＋＋*＋ 【解析】 利用栈的思维进行去重操作，选项B为t＝2；其余选项为t＝0，选项B不同。 【B级　素养形成与评价】 15．有如下Python程序段： s＝[0]*10 a＝[6，3，2，4，2，1，5] n＝len(a)；top＝0；s[top]＝a[0] for i in range(1，n)： while top！＝－1 and a[i]>s[top]： top－＝1 top＋＝1 s[top]＝a[i] while top！＝－1： print(s[top]，end＝' ') top－＝1 执行该程序段后，输出的结果是(　A　) A． 5 6 B． 4 5 6 C． 0 1 2 3 4 D．2 3 4 5 6 【解析】 栈的变化过程，初始s＝[6，0，0，0，0，0，0，0，0，0] i＝1，s＝[6，3，0，0，0，0，0，0，0，0], top＝1 i＝21，s＝[6，3，2，0，0，0，0，0，0，0], top＝2 i＝31，s＝[6，4，2，0，0，0，0，0，0，0], top＝1 i＝41，s＝[6，4，2，0，0，0，0，0，0，0], top＝2 i＝51，s＝[6，4，2，1，0，0，0，0，0，0], top＝3 i＝61，s＝[6，5，2，1，0，0，0，0，0，0], top＝1 top＝1时开始输出s[top]，先输出s[1]，后输出s[0]，选项A正确。 16．2023·知临中学检测有如下Python 程序段： import random s1＝”AsiaGames”；s2＝[]；s3＝”” n＝len(s1)；i＝0 while i<n： if random.randint(0，1)＝＝0： if len(s2)＝＝0 or s1[i]>s2[－1]： s2.append(s1[i]) i＋＝1 else： if len(s2)>0： s3＋＝s2.pop(－1) while len(s2)>0： s3＋＝s2.pop(－1) print(s3) 执行该程序段后，输出的结果不可能是(　B　) A．saAsm B．sAise C．sAiaGmsea D．AsiaGames 【解析】 逐个遍历s1 字符串，在遍历的过程中分为两种情况，第一种情况是：若s1 中的字符大于s2 的最后一个元素，则添加到s2 中；第二种情况是：把s2 的最后一个元素删除并顺序添加到s3 中。可以以栈的思想来看，进栈(进入s2 列表)的条件是随机整数为0，并且s2 空或者当前字符串大于列表的最后一个字符。选项B，“A”加入s2，“s”加入s2，“s”弹出s2，“A”弹出s2，s2 空。“i”加入s2，若“i”弹出s2，则“a”会加入s2，后续也一定会弹出；若“i”暂时不弹出s2，根据字符大小“m”一定会加入s2，后续也一定会弹出。选项B 错误。 17．有如下Python程序段： s＝input('请输入一串小写字母：　') head＝0; tail＝0; top＝－1 s1＝[””]*((len(s)＋1)//2) s2＝[””]*(len(s)//2) for i in range(len(s))： if i %2＝＝0： s1[tail]＝s[i] tail＋＝1 else： top＋＝1 s2[top]＝s[i] x＝”” while head<tail and top>－1： x＝s1[head]＋x head＋＝1 x＝x＋s2[top] top－＝1 print(x) 执行该程序段，若输入的字符串是“abcdefg”，则输出的结果是(　D　) A．acegbdf B．acegfdb C．gecafdb D．ecafdb 【解析】 根据题意，s1为队列，s2为栈，每读取s一个字母时，偶数次取出放入s1中，奇数次取出放入s2中，存储后再依次取出，取时必须同时满足head<tail and top>－1，故只取最少次数。故输入字母串abcdefg时，存入队列中的为aceg，存入栈中的为bdf。队列从head指向处顺序取出，反接在x中；栈从top指向处逆序取出，正接在x中，选项D正确。 18．下列Python 程序段用于定义判断字符串是否为回文字符串的自定义函数。(注：回文字符串是一个正读和反读都一样的字符串，如“12321”或者“noon”等，是回文字符串，而“1232”则不是) def pal(s)：#判断字符串是否为回文字符串 st＝[””]*100 top＝－1 k＝len(s)//2 for i in range(k)： top＋＝1 st[top]＝s[i] if len(s)%2＝＝1： for i in range(k，len(s))： tmp＝st[top] top－＝1 if： 　return False return True 上述程序段中加框处可选的代码有： ①k＝k＋1　②k＝k－1　③tmp＝＝s[i] ④tmp！＝s[i] 下列选项中，代码顺序正确的是(　D　) A．①③ B．②④ C．②③ D．①④ 【解析】 阅读程序可知，(1)处为if 条件的语句块，(2)处为if 的判断条件。本程序的思想为先取字符串的左半子串依次入栈，再依次出栈分别与右半子串比较。k 为待判断字符串s 长度的一半，若字符串s 长度为偶数，则右半子串开始的索引即为k，若为奇数，右半子串开始的索引应为k＋1，故(1)处应选择①。(2)处所在的for 循环是存储左半子串的栈中元素依次出栈分别与右半子串比较，出栈元素为tmp，如果出栈元素tmp 与右半子串取出字符s[i]不同，则该字符串s 不是回文字符串，返回False，所以(2)处应选择④。选项D正确。 19． 有如下Python程序： import random a＝input(＂输入一个数：　＂) n＝len(a)；c＝random.randint(0，n－1) st＝[0]*n；top＝0；st[top]＝0 for i in range(1，n)： while top！＝－1 and a[i]＜a[st[top]]： top－＝1；c－＝1 top＋＝1 st[top]＝i if c＝＝0： break s＝a[i＋1：] while top！＝－1： s＝a[st[top]]＋s top－＝1 print(＂输出结果： ＂，s[：len(s)－c]) 输入内容：23641287，程序执行结束后，输出的结果可能是(　D　) A．628 B．687 C．21 D．12 【解析】 单调栈问题，“while top！＝－1 and a[i]＜a[st[top]]”这段循环维护了栈内元素的单调性，若有更小的元素进来会破坏栈内从小到大的单调性，a[i]比a[top]小，若直接进栈则该部分就是由大到小，破坏原有单调性，通过while循环把比a[i]大的都出掉，进栈后能继续保持从小到大的关系，根据从数值高位到低位，若尽量保持逐位数字从小到大的关系，则应该是删除c1个数字后，用这种方法维护栈里的数字，则会使最后的数字达到最小的效果。选项D，12是有可能出现的值，其他不可能。len(s)－c是为了防止没有删足c个，后面低位的数字太大了，保持住了从小到大，则去掉后面低位的，得到更小的，选项正确。 20． 2023·学军中学检测如下Python 程序段的功能是判断一个表达式中的括号(只有小括号)是否匹配，则横线处填入的代码应为(　C　) exp＝input(”请输入表达式：　”) top＝－1；n＝len(exp)//2；flag＝True stack＝[””]*n for ch in exp： if ch＝＝”(”： if ①____________ ： flag＝False；break top＋＝1；stack[top]＝”(” elif ch＝＝”)”： if top<0： flag＝False；break top－＝1 if ②______________： 　　　print(”括号匹配”) else： print(”括号不匹配”) A．①top>＝n　②flag and top＝＝0 B．①top>n　②flag and top＝＝0 C．①top>＝n　②flag and top＝＝－1 D．①top>n　②flag and top＝＝－1 【解析】 利用栈的思维进行括号匹配，当top>＝n成立时，则遍历完成，flag置为False，①答案为top>＝n；当遇到“)”，此时top<0，表示“)”多，匹配失败，flag置为False；②处表示flag为True且栈空，填写flag and top＝＝－1，选项C正确。 21． 一个手机上的趣味小游戏，有3个杯子里装了一些有颜色的液体(如图所示)，现在希望通过相互倒水实现将杯子stC装满红色液体，现编写代码如下： stA，stB，stC＝['灰'，'红'，'蓝']，['红'，'灰'，'']，['红'，'，'] tops＝[2，1，0] ①tops[2]＋＝1 stC[tops[2]]＝stB[tops[1]] tops[1]－＝1 ②tops[0]＋＝1 stA[tops[0]]＝stB[tops[1]] tops[1]－＝1 ③tops[1]＋＝1 stB[tops[1]]＝stA[tops[0]] tops[0]－＝1 ④stA[tops[0]]＝stB[tops[1]] tops[1]－＝1 ⑤tops[2]＋＝1 stC[tops[2]]＝stA[tops[0]] 在空白处填入哪一种方案，可以将stC杯子中装满红色液体？(　B　) A． ③⑤①②④ B． ③⑤④②① C．③⑤④①② D．③②①⑤④ 【解析】 分析三个杯子里的液体分布情况，要将stC装满红色液体，操作的步骤如下： (1)将stA蓝色液体倒入stB；(2)将stA红色液体倒入stC；(3)将stB蓝色液体倒入stA；(4)将stB灰色液体倒入stA；(5)将stB红色液体倒入stC。对应的操作顺序是：③⑤④②①，选项B正确。具体做题时，4个选项前面相同的较多，但最后一个均不相同。操作的最后一步是将B栈的液体倒入C栈，只有①是这个操作，可以快速找到正确答案 学科网（北京）股份有限公司 $$