教科版（2019）选修一5.1栈结构及其实现同步训练

教科版（2019）选修一5.1栈结构及其实现同步训练 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．有如下Python程序段： import random a=['A'，'B'，'#'，'#'，'C'，'D'，'#'] stk=[0]*len（a）；top=-l for i in range（len（a））：       op=random. randint（0，1）        # 随机生成0或1       if op= =l and a[i]!='#"：               top+=l；stk[top]=a[i]               a[i]='#'       elif op= =0 and top!=-1 and a[i]= ='#'：              a[i]=stk[top]；top-=l 执行该程序段后，a的值不可能的是（   ） A．['A'，'B'，'#'，'#'，'C'，'D'，'#'] B．['#'，'#'，'#'，'#'，'#'，'#'，'#'] C．['#'，'B'，'#'，'#'，'C'；'D'，'A'] D．['#'，'#'，'A'，'B'，'C'，'D'，'#'] 2．用栈的数据结构编写进制转换中的“除二取余法”的程序段如下： 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．①③④② 3．栈s的最大长度为3，初始为空，经过一系列入栈、出栈操作，若元素入栈的顺序是a，b，c，d，e，f，则可能的出栈序列为（    ） A．f，e，d，c，b，a B．c，b，a，f，e，d C．c，a，b，d，e，f D．c，e，d，b，a，f 4．下列有关栈和队列说法，正确的是(　　) A．栈的特点是先进先出，队列的特点是先进后出 B．栈只允在一端进行插入，在另一端进行删除 C．队列限定仅能在一端进行插入和删除操作 D．栈和队列均为操作受限的线性表 5．有如下 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”，则输出的结果是（   ） A．acegbdf B．acegfdb C．gecafdb D．ecafdb 6．有如下Python程序段： import random lst=['A'，'B'，'C'，'D'] st=[0]*len（lst） i，top=0，-1 while i<len（lst）：   k=random.randint（0，1）   if k==0：     top+=1     st[top]=lst[i]     i+=1   elif top!=-1：     lst[i]=st[top]     top-=1 执行该程序段后，lst的值不可能是（   ） A．['A'，'B'，'C'，'D'] B．['A'，'B'，'A'，'C'] C．['A'，'A'，'C'，'D'] D．['A'，'A'，'C'，'A'] 7．已知一个栈的入栈序列是a，c，e，h，r，t，e，其出栈序列可能的是（    ） A．c，h，e，a，t，e，r B．h，e，c，t，a，r，e C．t，e，a，c，h，e，r D．r，e，t，e，a，c，h 8．有如下程序： 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 9．栈S从栈底到栈顶的元素依次为1，2，3，队列Q初始为空。约定：U操作是指元素出栈后入队，H操作是指元素出队后再入队。经过UUHU系列操作后，队列中队首到队尾的元素依次为（   ） A．2,1,3 B．3,1,2 C．1,3,2 D．2,3,1 10．某Python程序如下： from random import randint a=[1,8,3,6,7,2,9,0,5,1,3] s=[-1]*100;top=-1 i=0 x=randint（5,8） while i<x;    while top!=-1 and a[i] < s[top]:       top-=1    top+=1;s[top]=a[i]    i+=1 while top!=-1:    print(s[top],end="")    top-=1 执行该程序段后，输出的结果不可能是（    ） A．0 B．21 C．631 D．921 11．有如下程序段： bt=["A","B","C","D",None,"E","F"] result=[] stack=[] i=0 while stack or (i<len(bt) and bt[i] is not None):     if i < len(bt) and bt[i] is not None:         stack.append(i)         i=2*i+1     else:         i=stack.pop()         result.append(bt[i])         i=2*i+2 print("-".join(result)) 则程序运行后输出的结果为（   ） A．A-B-D-C-E-F B．D-B-E-F-C-A C．D-B-A-E-C-F D．A-B-C-D-E-F 12．设栈S初始状态为空，元素A、B、C、D、E、F依次入栈，出栈的序列为D、F、E、C、B、A，则栈S的容量至少应该是（   ） A．5 B．4 C．3 D．2 13．若用1表示进栈操作，用0表示出栈操作，若元素的进栈顺序是“q，w，e，r，t”，为了得到出栈序列“ewrtq”，则应进行的操作序列为(　　) A．1101010100 B．1110010100 C．1110011000 D．1110100100 14．一个栈的入栈序列为“6、9、5、7、8、3”，其出栈序列不可能是(     ) A．3、8、7、5、9、6 B．7、5、9、8、6、3 C．6、5、7、9、3、8 D．5、9、6、3、7、8 15．一个栈的初始状态为空，若它的输入序列为a、b、c、d，则它的输出序列为(    ) A．a、b、c、d B．d、c、b、a C．b、a、c、d D．d、b、a、c 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．D 【详解】本题考查的是堆栈的操作。堆栈的操作原则先进后出。stk可以看做一个堆栈，阅读程序可知对列表a中的字母进行入栈和出栈操作。选项A没有进行入栈和出栈操作，有可能；选项B把字母全部压入栈，有可能；选项C对字母A进行入栈，最后出栈，有可能；选项D，先把字母A、B进行入栈，然后出栈，出栈顺序应为B、A，故选项D不可能。 2．B 【详解】本题主要考查栈及Python程序调试。根据题意“除二取余法”可知先要执行取余，然后才能整除2更新n的值。top初值为-1标记此时栈中无元素，每递增一个元素，top先递增1，再将x保存到栈中，即st[top]=x，故代码顺序正确的是③①②④，故本题选B选项。 3．B 【详解】本题考查栈的基本操作。栈是先进后出，题干中限定条件栈s的最大长度为3，初始为空。A选项f最先出栈，说明a，b，c，d，e，f需要全部入栈后，f才能出栈，但这种情况下栈长度需要为6，不符合题意，故A选项错误；B选项c最先出栈，此时a，b，c入栈，接着c，b，a依次出栈，此时栈s内为空，接下来f出栈，说明d，e，f需要入栈，接着f，e，d出栈，过程中栈内长度符合题意，故B选项正确；C选项c最先出栈，此时a，b，c入栈，接着c出栈，此时栈内a，b，由于b是栈顶元素，所以接下来出栈元素不可能是a，故C选项错误；D选项c最先出栈，此时a，b，c入栈，接着c出栈，此时栈内a，b，接下来e出栈，需要d，e入栈，此时栈内a，b，d，e，栈长度为4，不符合题意，故D答案错误。本题应选B。 4．D 【详解】本题主要考查栈和队列的描述。栈的特点是先进后出，队列的特点是先进先出；队列只允在一端进行插入，在另一端进行删除； 栈限定仅能在一端进行插入和删除操作； 栈和队列均为操作受限的线性表，故本题选D选项。 5．D 【详解】本题主要考查Python及数据结构的应用。根据题意，s1为队列，s2为栈，每读取s一个字母时，偶数次取出放入s1中，奇数次取出放入s2中，存储后再依次取出，取时必须同时满足 head<tail and top>-1，故只取最少次数。故输入字母串 abcdefg 时，存入队列中的为aceg，存入栈中的为bdf。队列从head指向处顺序取出，反接在x中；栈从top指向处逆序取出，正接在x中，故输出的结果是ecafdb，故本题选D选项。 6．B 【详解】本题考查数据结构栈的相关操作。以下仅取部分随机数序列进行解析： A选项，若每次使用random．randint（0，1）时，都产生随机数0，即0、0、0、0，则只执行入栈操作（if部分），lst并未发生变化（elif部分未执行），其值仍然为['A'，'B'，'C'，'D'] ，选项A正确； C选项，当产生随机数依次为：0、1、0、0、0时，第一次值为0，将lst第一个元素'A'入栈，i+1变为1，第二次值为1时，将栈st中元素出栈且赋值给lst[1]，则lst[1]='A'，第三、四、五次值为0时，进行入栈操作，i值由1变为4，结束循环，lst中对应位置元素并未发生变化，lst中元素最终为：['A'，'A'，'C'，'D'] ，选项C正确； D选项，当产生随机数依次为：0、1、0、0、1、1、0时，第一次值为0，将lst第一个元素'A'入栈，i+1变为1，第二次值为1时，将栈st中元素出栈且赋值给lst[1]，则lst[1]='A'，第三、四次值为0时，进行入栈操作，st=['A'，'C']，第五、六次执行出栈，lst中元素为：['A'，'A'，'C'，'A]，第七次执行出栈，lst不变还是['A'，'A'，'C'，'A]，i值由1变为4，结束循环。选项D正确。 排除ACD，故本题答案是B选项。 7．A 【详解】本题主要考查栈的操作。根据栈的特点“先进后出”的原则，可知入栈序列是a，c，e，h，r，t，e，结合选项，其出栈序列可能的是c，h，e，a，t，e，r，故本题选A选项。 8．C 【详解】本题主要考查Python程序的执行。第一次循环后start=2，qu[0]=wz[start]=2；第二至第七次循环后，qu[1]=5，qu[2]=1，qu[3]=6，qu[4]=4，qu[5]=0，qu[6]=3。h初值为0，执行完最后一个while循环，即根据列表qu的值从wm中取对应的元素拼接到mm中，mm=mm+wm[qu[h]]，程序运行后，显示的结果为mm="cfbgead"，故本题选C选项。 9．D 【详解】本题考查栈、队列相关内容。栈的特点是后进先出，队列的特点是先进先出。初始状态，栈中从栈顶到栈底的元素为3、2、1，队列为空。第一次操作：U，即将栈顶元素3出栈后入队，队列中队首元素为3；第二次操作：U，即将栈顶元素2出栈后入队，队列中队首元素为3，队尾元素为2；第三次操作：H，即将队首元素3出队后再入队，队列中队首元素为2，队尾元素为3；第四次操作：U，即将栈顶元素1出栈后再入队，队列中从队首到队尾各元素依次为2、3、1。故本题答案是D选项。 10．C 【详解】本题主要考查栈数据结构及Python程序实现。分析程序可知，x随机生成5~8之间的整数，即外循环的次数，嵌套while循环中，栈中保存的数从栈底到栈顶成递增趋势，如果出现了不符合的数，则依次出栈直到符合递增趋势。因此x=5时，输出的结果是7631；x=6时，输出的结果是21；x=7时，输出的结果是921；x=8时，输出的结果是0，因此输出的结果不可能是631，故本题选C选项。 11．C 【详解】本题主要考查Python中stack()用法。分析程序可知，前3轮循环，即当i=0、1、3时均满足if判断条件，此时stack=[0,1,3]，接下来i=2*i+1=7不满足if判断条件，执行else部分， i=stack.pop()=3，result.append(bt[i])=["D"]，i=2*i+2=8，继续执行else，i=stack.pop()=1，result.append(bt[i])=["D","B"]，i=2*i+2=4，不满足if判断条件，继续执行else部分，i=stack.pop()=0，result.append(bt[i])=["D","B","A"]，此时结合选项可知程序运行后输出的结果为D-B-A-E-C-F，选C选项。 12．A 【详解】本题考查栈相关内容。栈的特点是先入后出。栈S 的初始状态为空，元素A、B、C、D、E、F依次入栈，出栈顺序为D、F、E、C、B、A。D出栈，说明D要先进栈，此时C、B、A已在栈内，栈的容量至少为4；D出栈后，F出栈，说明F需要先进栈，此时E、C、B、A在栈内，栈的容量至少为5；后续出栈序列为E、C、B、A，期间没有元素再入栈，栈的容量不会再增加，故栈的容量至少为5。本题答案是A选项。 13．B 【详解】本题主要考查栈的操作。为了得到出栈序列“ewrtq”，即e先出栈，按照进栈顺序，则qwe先进栈，对应111，接着是ew出栈，对应00，后面依次类推可得到应进行的操作序列为1110010100，故本题选B选项。 14．D 【详解】本题主要考查栈数据结构。选项D中，先入栈6、9、5，再依次出栈，此时再入栈7、8、3，则出栈顺序只能是3、8、7，故出栈序列不可能是5、9、6、3、7、8，故本题选D选项。 15．B 【详解】本题考查的栈的操作。堆栈是一个后进先出的数据结构，若它的输入序列为a、b、c、d，则它的输出序列为d、c、b、a。故本题应选B。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$