资源简介 第六单元 数据结构信息技术(50分)一、选择题(本大题共12小题,每小题2分,共24分。每小题列出的四个备选项中只有一个是符合题目要求的,不选、多选、错选均不得分)1.已知一棵完全二叉树的节点总数为10,则有关该二叉树的说法正确的是( )A.树的度为10 B.树的层数为3C.最后一层有3个节点 D.叶子节点数为32.现有一棵二叉树的前序遍历为ABCDEF,中序遍历为BCADFE,则该二叉树的后序遍历为( )A.CBFEDA B.BCFEDAC.CBDFEA D.BCEFDA3.用一维数组表示二叉树,如下表所示:0 1 2 3 4 5 6 7 8 9 10A B C D E F G下列有关该二叉树的说法正确的是( )A.该树中共有4个叶子节点B.该树是完全二叉树,其深度为4C.该树的中序遍历为B-F-D-G-A-C-ED.该二叉树的结构图为(如图所示)4.某二叉树的树形结构如图所示,其前序遍历结果为BADCFGE,则字符“G”所在的位置为( )A.① B.②C.③ D.④5.创建一个容量为3的队列,元素2,3,5,1,3,5,2依次等待入队。入队规则为:①若当前待入队元素已经在队列中,则跳过该元素,否则转②②若当前队列已满,将队首元素出队列,否则转③③将当前待入队元素入队列操作完成后,队列中的元素为( )A.2,3,5,1 B.1,2,3,5C.2,3,5 D.5,1,26.某种特殊的队列Q,支持以下3个操作:操作Q1,若队列非空,队首元素出队,并输出;操作Q2,若队列非空,队首元素出队;操作Q3,一个元素入队;以上任意一种操作后,若队列非空,新的队首元素仍为队列中所有元素的最小值。若队列Q初始状态为空,依次进行Q3、Q2、Q1、Q2、Q3、Q1、Q3七次操作后,下列说法正确的是( )A.当前队列中的元素个数为2B.输出的元素个数为2C.第一个输出的元素肯定比当前队首元素大D.队列初始状态是否为空对输出结果有影响7.用“除二取余”法将十进制转换为二进制数,用栈的方法操作,需要把得到的余数依次入栈,除尽后再把余数出栈即可。若要将十进制数n(0≤n<64)转换为二进制数,则设置栈的长度至少为( )A.3 B.4C.5 D.68.用I表示进栈操作,O表示出栈操作,若元素进栈的顺序为PQRST,为了得到PSRTQ的出栈顺序,则由I和O表示的操作串是( )A.IOIIIOOIOO B.IOIIOIOOIOC.IIIIOOIOOO D.IOIIIIOOOO9.有一个空栈,若元素“P”、“y”、“t”、“h”、“o”、“n”依次入栈,其中“o”第一个出栈。则当所有元素全部出栈后,下列说法正确的是( )A.出栈的最后一个元素一定为“P”B.出栈的最后一个元素一定为“n”C.元素“h”一定比“P”、“y”、“t”先出栈D.元素“P”、“y”、“t”、“h”、“o”的出栈序列是不确定的10.有如下Python程序段:a=[3,6,10,5,9,4]q=[0]*len(a)k=int(input(″输入k的值:″))head=tail=0s=ans=0for i in a:q[tail]=itail=tail+1s+=iif ansans=swhile ik:s-=q[head]head=head+1执行该程序段后,输入k的值为2,变量ans的值是( )A.18 B.19C.21 D.2211.有如下Python程序段:a=[2,1,5,7,3]n=len(a)s1=[-1]*n;top1=-1s2=[-1]*n;top2=-1for i in range(n):while top1!=-1 and a[i]top2+=1;s2[top2]=s1[top1];top1-=1top1+=1;s1[top1]=a[i]while top2!=-1:top1+=1;s1[top1]=s2[top2];top2-=1运行该程序段后,下列表达式不成立的是( )A.top1==5 B.top2==-1C.s1[0]==1 D.s1[3]==212.有如下Python程序段:sz=[″94″,″98″,″156″,″80″,″87″,″178″]dt=[0,1,0,1,0,0]st=[];top=0st.append(top)for i in range(1,len(sz)):flag=Falsewhile len(st)>0 and dt[st[top]]==1 and dt[i]==0:if sz[st[top]] st.pop() top=top-1else: flag=True;breakif not flag:top+=1st.append(i)执行该程序段后,st中的元素个数为( )A.6 B.2C.4 D.3二、非选择题(本大题共3小题,其中第13小题7分,第14小题10分,第15小题9分,共26分)13.给定一个只包括'(',')','{','}','[',']'的字符串s,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。程序运行的结果如图所示:(1)实现上述功能的Python程序如下,请在划线处填入合适的代码。dic={″(″:″)″,″[″:″]″,″{″:″}″}s=input(″输入的字符串是:″)st=[″″]*len(s)top=-1dic1={}for i in dic:dic1[dic[i]]=iflag=Truefor i in s:if ①________:top+=1st[top]=iif i in dic1:if top==-1 or ②________:flag=False breakelse: ③________if :print(″字符串有效!″)else:print(″字符串无效!″)(2)加框处的代码有错,请改正。14.一批集装箱陆续送达码头,要求叠放到指定的若干位置,每个位置最多可叠放5个集装箱,且轻的在上,重的在下。工作人员根据每个送达的集装箱的重量,利用临时位置经过最少的移动次数放到合适的位置,若移动次数相同,优先选择编号小的位置(临时位置不考虑集装箱重量大小关系)。例如:共有8个集装箱,要求叠放到2个位置。已依次送达6号、2号、3号、5号,叠放情况如图a所示。新送达的集装箱为7号,重量为28。·若叠放到位置0,需要移动3次:①2号→临时位置②7号→位置0③2号→位置0·若叠放到位置1,需要移动5次:①5号→临时位置②3号→临时位置③7号→位置1④3号→位置1⑤5号→位置1叠放到位置0的移动次数<叠放到位置1的移动次数,所以叠放到位置0。编写Python程序实现上述功能,请回答下列问题:已送达集装箱信息: {6:29,2:18,3:20,5:19} 当前集装箱叠放情况: 位置0:[6,2] 位置1:[3,5] 请输入到达的集装箱编号:7 请输入到达的集装箱重量:28 移动过程为: 2→临时位置 7→位置0 2→位置0 叠放结果: 位置0:[6,7,2] 位置1:[3,5]图b(1)函数judge(x,st)的功能是:返回x号集装箱放入某位置时需移动的次数。列表st存储了该位置从下到上已叠放的集装箱编号。请在划线处填入合适的代码。#goods存储了已送达集装箱的信息,如:{6:29,2:18,3:20,5:19}。def judge(x,st):if len(st)==5:return-1cnt=0i=len(st)-1while i>=0 and____________:cnt+=1i-=1return cnt*2+1(2)当某个集装箱送达时,输入其编号和重量,将该集装箱放到移动次数最少的位置,并输出移动过程。程序执行结果的部分截图如图b所示。请在划线处填入合适的代码。goods={}n=8k=(n-1)//5+1p=[[]for i in range(k)]for i in range(n):#输出当前集装箱叠放情况,代码略x=int(input('请输入到达的集装箱编号:'))weight=int(input('请输入到达的集装箱重量:'))goods[x]=weightmin_steps=999for j in range(k):t=judge(x,p[j])if ①________: minp=j min_steps=tprint('移动过程为:')tmp=[]for j in range(②________):print(p[minp][-1],'→临时位置')tmp.append(p[minp].pop()) #删除p[minp]的最后一个元素,并追加到tmpp[minp].append(x)print(x,'→','位置'+str(minp))while ③________:print(tmp[-1],'→','位置'+str(minp))p[minp].append(tmp.pop())#输出叠放结果,代码略(3)若送达的集装箱编号和重量依次为4:20,2:18,1:23,3:20,7:28,6:29,0:17,5:19,根据要求叠放到位置0和位置1,则位置1从下往上叠放的集装箱编号依次为________。15.某餐厅餐桌设置如下表:餐桌型号 2人小桌 4人方桌 6人大方桌 12人大圆桌餐桌数量 8 15 10 4平均就餐时间(分钟) 25 45 60 80有客人来就餐时其叫号系统会自动生成一个号码,并根据人数安排餐桌型号;当对应餐桌型号有空桌时,按餐桌编号(由小到大)即时分配餐桌安排客人就餐;当对应餐桌型号没有空桌时,客人按先后顺序排队。程序部分运行界面如下:(1)定义如下gettype函数,功能为输入客人人数,返回对应桌型,请在程序划线处填入合适代码。def gettype(num):type=-1for i in range(len(size)):if num<=size[i]: type=i __________return type(2)定义如下checktable()函数,功能为输入桌型,返回对应桌型空桌的编号,返回值类型为列表,请在程序划线处填入合适代码。def checktable(n):ans=[]for i in range(nums[n]):if____________: ans.append(i)return ans(3)解决上述问题的主程序如下,请在程序划线处填入合适代码。size=[2,4,6,12] #每种桌型最大就餐人数nums=[8,15,10,4] #每种桌型的餐桌数量times=[25,45,60,80] #每种桌型平均就餐时间flags=[[True]*nums[i] for i in range(4)] #标记每张桌子的初始状态s_time=10*60*60 #开始营业时间——10点整,转化为秒e_time=14*60*60 #结束营业时间——14点整,转化为秒maxn=50 #假设队列已经足够深qc=[[0]*maxn for i in range(4)] #循环队列now_time=s_timeid=0head,tail=[0]*4,[0]*4while now_timenumber=getinfo() #调用函数getinfo(),获取客人人数if number>0:id+=1type=gettype(number)#根据就餐人数确定餐桌类型if type!=-1: qc[type][tail[type]]=id tail[type]=(tail[type]+1)%maxn qc_len=①________ print(id,″号客人,给您安排的是″,size[type],″人桌,前面还有″,qc_len-1,″人在等位″)else: print(id,″号客人,非常抱歉,没有适合您的桌型!″)for i in range(4):tables=checktable(i)if ②________: flags[i][tables[0]]=False #入座第一个空桌 print(qc[i][head[i]],″号客人请用餐→″,size[i],″人桌″,tables[0],″号″) head[i]=(head[i]+1)%maxnnow_time+=1#更新每张餐桌的就餐情况,代码略第六单元 数据结构1.C [本题考查树的性质。A选项二叉树的最大度为2,因此树的度也是2。B选项总节点数10介于7和15之间,因此该树层数为4。C选项由于是满二叉树,因此前3层为完全二叉树,前3层共有7节点,最后一层有3个节点。D选项由于最后一层有3个节点,因此该层的父亲节点有2个,第3层共有4个节点,因此第3层还有2个叶子节点。]2.A [本题考查二叉树的遍历。根据前序遍历和中序遍历的规则画出二叉树,前序遍历的第一个元素“A”为根节点,树分为(BC)A(DEF)。“BC”确定节点B为根节点,C是右子树。“DEF”中,节点D为根节点,“EF”是节点“D”的右子树。“EF”中E为根节点,F是右子树。得到后序遍历结果为CBFEDA。]3.C [本题考查二叉树的基本知识。第3层节点的索引号为3,4,5,可见B没有左子树,但有右子树,因此不可能是满二叉树,B也不是叶子节点。二叉树形态如图所示。]4.C [前序遍历是根左右,F为根,G在F的后面,因此G为F的右子树。]5.D [本题考查队列结构及其操作,各数据入队时状态如图所示。]6.D [操作Q3、Q2之后,队列为空。Q3、Q1,队列为空。因此队列中元素个数为1,Q1操作出队并输出元素,输出的元素个数为1。C选项没有可比性。D选项若队列不为空,则Q3、Q2、Q1、Q2输出的结果不一样。]7.D [十进制数n(0≤n<64)转换为二进制数,得到最大的是6位二进制数。]8.A [本题考查栈的操作。P入后马上出,QRS入,SR出,栈中只有Q,T入后马上出,Q再出。]9.C [本题考查栈的性质。o出栈时,n还没有入栈,因此n可能是最后一个出栈,也可能在其他元素出栈过程中,入栈后再出栈。o出栈时,P,y,t,h均已在栈中,故元素出栈序列是确定的。]10.C [遍历数组a并累加数组元素值,求队列的最大值;当遍历到的当前值小于队首或是长度大于k,将队首元素出队。s的值依次为[3,6,10]=19,[6,10,5]=21,[5,9]=14,[5,9,4]=18。]11.A [本题考查栈的基本应用。遍历列表a中数据,若栈s1不空,且s1栈顶元素大于等于a[i]时,不断地将s1中元素出栈,并入栈s2中,将a[i]入栈s1。因此栈s1中元素有1,3,栈s2中有元素[2,7,5],最后将栈s2中元素出栈并加入到栈s1中,因此栈s1中最终结果为[1,3,5,7,2]。]12.B [本题考查数组的索引和栈的算法实现。st.pop()表示出栈,st.append(i)表示元素i入栈,st[top]是栈顶元素。栈中存储的元素的编号,一开始栈中有一个元素,″94″对应的下标0入栈。对sz的第2个元素开始遍历。dt[1]==1,没有出栈动作,″98″下标1入栈;条件满足,但是″156″不比栈顶元素″98″大,flag=True,″156″下标2不会入栈;dt[3]==1,没有出栈动作,″80″下标3入栈;接下来条件满足,″87″比栈顶元素″80″大,″80″对应的下标3出栈,接下来的栈顶元素是″98″,flag=True,没有入栈动作;最后栈中只有[0,5]共2个元素。]13.(1)①i in dic ②i!=dic[st[top]] ③top-=1 (2)flag and top==-1解析 本题考查栈的操作。(1)①如果是括号的左半部分,则入栈,否则出栈。②出栈前判断栈是否为空,为空,说明右半部分先出现,顺序不对。若不为空,在字典dic中查找栈顶元素对应的右半分部,如果不相等,说明中间的顺序不对。③如果相等,出栈。(2)除了flag的值外,还要判断左半部分是否比右半部分多,即栈是否为空。14.(1)goods[x]>goods[st[i]] (2)①t!=-1 and t0 或 tmp(3)6,1,3,5解析 本题考查栈的应用。插入元素后,维护栈底到栈顶的降序排列。(1)judge函数计算将goods[x]插入到栈st需要移动元素的操作次数。参数x是集装箱编号,即字典goods的键,因此在访问栈顶元素时goods[st[i]]与goods[x]比较为非直接与x比较。(2)从k个位置选择移动次数最少的栈并插入元素。第①空获取当前栈p[j]插入编号为x的元素所需的移动次数与全局最小次数min_steps比较并更新min_steps。若栈已满将无法插入数据。第②空输出移动的过程。先将栈p[minp]大于goods[x]的元素暂存到临时栈中,这里需出栈的元素个数恰为min_steps//2。第③空将临时栈中的全部元素重新压入栈p[minp]中,因此len(tmp)>0时均需要执行入栈。(3)编号4、2依次在位置0入栈;3、7依次在位置1入栈;随后7插入到位置0的栈底、6插入到位置1栈底;最后0入栈位置0,5入栈位置1,从下到上的编号依次为:6 1 3 5。15.(1)break (2)flags[n][i]==True (3)①(tail[type]-head[type]+maxn)%maxn ②len(tables)>0 and head[i]!=tail[i]或tables and head[i]!=tail[i]解析 本题考查循环队列的基本应用。(1)gettype函数功能为输入客人人数,返回对应桌型。size数组存储每种桌型最大就餐人数,从小桌开始枚举,找到相应的规格就结束查找。(2)checktable函数功能找到对应桌型的空桌编号。nums每种桌型的餐桌数量,flags二维数组标记每种桌型每张桌子的初始状态,n为桌型编号,nums[n]表示该种桌型中最多就餐桌位,在flags[n]列表中从头开始(循环变量i从0至nums[n]-1中枚举)查找值为True(空桌)的编号,并将这些编号添加到列表ans中,因此答案为flag[n][j]==True。(3)①求队列长度,qc存储循环列表的信息,type表示餐桌类型,qc[type]就是存储该类型的循环列表,循环队列长度公式(tail-head+maxn)%maxn,因此①答案为(tail[type]-head[type]+maxn)%maxn。②输出安排就餐情况。变量i表示每种桌型,安排座位的条件有两个,一是这种桌型有客人来,即qc[i]队列不为空;二是这种桌型有空位,tables调用checktable(i)函数,获取空位列表。 展开更多...... 收起↑ 资源预览