2023-2024学年高二上学期教科版(2019)选择性必修一 5.1 栈结构及其实现

2023-2024学年高二上学期教科版(2019)选修一5.1 栈结构及其实现 一、选择题 1．利用栈求逆波兰表达式（表达式由操作数和运算符组成）的方法是:从左往右扫描该表达式，遇到操作数时入栈；遇到运算符时，把处于栈上方的两个元素依次出栈，用运算符计算，并把计算结果压入栈中。如此反复操作，直至表达式扫描结束。当用该算法求逆波兰表达式abcd-*e/+f-的值时（abcdef表示不同的操作数），所使用的栈的深度至少为（   ） A．3 B．4 C．5 D．6 2．一个序列的入栈顺序为 a，b，c，d，e，则该序列的出栈顺序不可能为（ ） A．b，a，d，c，e B．d，c，b，a，e C．d，c，e，a，b D．c，b，a，e，d 3．有一个空栈，若元素“P”、“y”、“t”、“h”、“o”、“n”依次入栈，其中“o”第一个出栈。则当所有元素全部出栈后，下列说法正确的是（   ） A．出栈的最后一个元素一定为“P” B．出栈的最后一个元素一定为“n” C．元素“h”一定比“P”、“y”、“t”先出栈 D．元素“P”、“y”、“t”、“h”、“o”的出栈序列是不确定的 4．下列关于队列和栈的说法，不正确的是（   ） A．队列是一种先进先出的线性表，可在队尾进行插入操作 B．栈的特性是″先进后出，后进先出″ C．某栈的入栈的顺序为″abc″，出栈顺序只有3种 D．队列和栈都是线性数据结构，都可以用数组来实现 5．队列Q从队首到队尾的元素依次为1，2，3，4，栈S初始为空。约定：H操作是指元素出队后入队，T操作是指元素出队后入栈。经过HTTHT操作后，栈S中从栈底到栈顶的元素依次为（    ） A．1，2，4 B．2，3，1 C．3，1，2 D．4，2，1 6．有一空栈S，对待进栈的数据元素序列a，b，c，d，e，f依次进栈、进栈、出栈、进栈、进栈、出栈的操作，操作完成后，栈S的栈顶元素是（   ） A．c B．d C．e D．f 7．若已知元素的入栈顺序是1，2，3，4，其出栈顺序不可能的是（   ） A．1，2，3，4 B．3，1，4，2 C．3，2，1，4 D．2，1，4，3 8．栈s和队列q的初始状态均为空，元素a1、a2、a3、a4、a5、a6依次入栈，再将出栈后的元素依次进入队列，若入队的顺序为a2、a4、a3、a6、a5、a1，则栈s的容量至少是（    ） A．2 B．3 C．4 D．5 9．有四个元素 A,B,C,D 按顺序入栈。约定：P 操作是指一个元素入栈，O 操作是指一个元素出栈。 经过一系列操作后，四个元素的出栈顺序为 C,D,B,A ，则经过的操作是（   ） A．PPPOOPOO B．PPPOPOOO C．PPOOPPOO D．PPPPOOOO 10．有如下程序： wz=[0,1,2,3,4,5,6] start=0 qu=[0]*len(wz) wm="abcdefg" h=0;t=0 while len(wz)>0:     for i in range(2):         start=(start+1)%len(wz)     qu[t]=wz[start]     t=t+1     wz.pop(start) mm="" while h<t:     mm=mm+wm[qu[h]]     h=h+1 print(mm) 程序运行后，显示的结果为（    ） A．bdfaecg B．bdfaceg C．cfbgead D．cfbeadg 11．一个序列的入栈顺序为9,8,7,6,5,4。若7第一个出栈，则下列出栈序列中不可能的是（   ） A．7,8,9,6,5,4 B．7,8,9,5,6,4 C．7,9,8,4,5,6 D．7,8,9,6,4,5 12．某栈入栈序列为“A、B、C、D、E”，若第一个出栈的元素为“C”，最后一个出栈的元素为“E”，则可能的出栈序列有（    ） A．3种 B．4种 C．5种 D．6种 13．有一T型结构，通道右侧是入口，左侧是出口，通道宽度仅能容纳一个小球通过，通道下部有一个能上下叠放两个小球、底部封闭的空间，如图所示。ABCDE五个小球依次从入口进入，若C球第一个从出口移出，B球第二个从出口移出。则移出序列不可能的是（   ） A．CBDEA B．CBDAE C．CBEAD D．CBEDA 14．用一带盖的玻璃筒来放取乒乓球，放、取球只能在带盖的一端进行（另一端为封闭状态），且筒的直径只允许一个乒乓球进出。若放入球的编号序列为1、2、3、4，则取出球的编号序列不可能的是（   ） A．1、2、3、4 B．2、3、4、1 C．4、2、3、1 D．3、2、1、4 15．用栈的数据结构编写进制转换中的“除二取余法”的程序段如下： st=[-1]*100 top=-1 n=int(input("请输入一个十进制数： ")) while n>0: while top!=-1: print(st[top],end="") top-=1 方框处的代码由以下四部分组成： ①n=n//2       ②top+=1       ③x=n%2       ④st[top]=x 下列选项中，代码顺序正确的是（    ） A．③④②① B．③①②④ C．①②③④ D．①③④② 二、填空题 16．数据结构中的栈是一种特殊的列表，它只允许在 进行数据的添加和删除操作。 三、判断题 17．用栈来存储数据时，可以快速地通过下标精确地访问序列中的某个数据元素。( ) 四、操作题 18．小明对入栈、出栈规则研究发现， 若有 n 个数字 1，2，3，……，n 按由小到大的顺 序入栈，则出栈序列必须遵循下述原则： 当数字 x 出栈后，则在x后出栈的小于x 的 所有数字必定以降序排列，比x大的数字可以夹杂在该降序序列中。现编写 Python 程 序，按上述原则验证一个随机产生的出栈序列是否可能， 程序运行界面如图所示。 (1) 根据题意，若有 7 个数字入栈， 则出栈序列“3→2→5→4→7→1→6”是 (单选，填字母： A．可能 / B．不可能) (2) 实现上述功能的Python程序代码如下，程序中加框处代码有错，请改正 。 (3)请在划线①②处填入合适代码 、 。 import random n=int(input('请输入入栈元素的个数：')) data=[i+1 for i in range(n)] random.shuffle(data)           #将序列的所有元素随机排序 s=” ” for i in range(n): print('随机产生的出栈序列为： '+s[1:]) flag=True;i=0 while i<n-1 and flag: ① for j in range(i+1,n): if data[j]<data[i]: if data[j]<x: x=data[j] else: ②#去除最后多余的'→' break i+=1 if flag: print('该出栈序列是可能的！') else: print('该出栈序列是不可能的！ ') 五、简答题 19．请简述什么是堆栈（Stack）数据结构，并说明其特点。 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．B 2．C 3．C 4．C 5．B 6．A 7．B 8．B 9．B 10．C 11．C 12．A 13．C 14．C 15．B 16．顶端（或顶部） 17．错误 18． B s+=’ →’+str(data[i]) x=data[i] flag=False 19．堆栈是一种后进先出（LIFO）的数据结构，其特点是只能在一端（栈顶）进行数据的添加（push）和删除（pop）操作。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$