资源简介 第七单元 数据结构与算法信息技术(50分)一、选择题(本大题共12小题,每小题2分,共24分。每小题列出的四个备选项中只有一个是符合题目要求的,不选、多选、错选均不得分)1.定义如下递归函数:def f(a,n):n=n-1if n==0:return aelse:return f(a-1,n)+f(a+1,n)print(f(5,3))程序运行后﹐输出的结果是( )A.10 B.20C.30 D.402.定义如下函数:def f(s):if len(s)==1:return s[0]elif len(s)==2:return s[0]+s[1]else:return f(s[0:len(s)//3])+f(s[len(s)//3:len(s)])执行语句s=f([1,2,3,4,5,6]),函数f被调用的次数是( )A.3 B.5C.7 D.153.定义如下函数:def jc (n):if n==l: #①return nreturn n*jc(n-1) #②执行语句x=jc(5),下列说法正确的是( )A.x的计算结果为120B.程序执行完毕,①处代码共执行1次C.程序执行完毕,②处代码共执行5次D.如果①处代码改成n<2,程序将无法正常执行4.有如下Python程序段:def f(s):if len(s)==1:return Trueelif len(s)==2:return s[0]==s[1]elif s[0]==s[-1]:return f(s[1:-1])else:return Falseprint(f(″1234321″))执行该程序段后,下列说法正确的是( )A.输出结果为FalseB.函数f运用了迭代算法C.函数f的调用次数为4D.函数f的时间夏杂度为O(n2)5.采用冒泡排序算法对数据序列“8,7,2,3,9,6,5”完成升序排序,排序2趟后,正确的顺序是( )A.2,3,8,7,5,6,9 B.2,3,8,7,9,6,5C.2,3,5,6,7,8,9 D.2,3,7,5,6,8,96.采用冒泡排序算法对数据序列“2,3,4,5,1,0”完成升序排序,则需要交换的次数为( )A.9次 B.12次 C.15次 D.18次7.下列代码采用冒泡排序对a列表中的n个数据升序排序,则①②两处不可用的选项是( )for i in range(①________):for j in range(②________):if a[j] a[i],a[j-1]=a[j-1],a[j]A.①1,n ②n-1,i-1,-1B.①n,1,-1 ②1,i-1C.①1,n ②1,n-i+1D.①0,n-1 ②n-1,i-18.有如下Python程序段:s=″ccbbac″a=[i for i in range(6)]for i in range(5):for j in range(5-i):if s[a[j]]>s[a[j+1]]: a[j],a[j+1]=a[j+1],a[j]print(a)运行该程序段输出的结果为( )A.[4,3,2,5,1,0] B.[4,5,3,2,1,0]C.[4,2,3,0,1,5] D.[4,3,2,5,0,1]9.某排序算法的Python程序段如下:'读取n个整数,依次存入a[1]到a[n]中,代码略for i in range(1,n-1):for j in range(n,i+1,-1):if a[j]>a[j-1]: a[j],a[j]=a[j-1],a[j-1]执行上述程序段,下列说法正确的是A.交换过位置的数据,可能会再回到其初始位置B.执行完成后,数组元素a[1]到a[n]从小到大排列C.若n为6,整个排序过程总的比较次数是30D.整个排序过程总的交换次数至少为110.某对分查找算法的Python程序段如下:key=int(input(″请输入待查数据值:″))d=[17,18,20,23,24,25,28,32,34,35]f=False;s=″″i=0;j=len(d)-1while i<=j:m=(i+j)//2s=s+″,″+str(d[m])if d[m]==key:f=Truebreakif keyj=m-1else:i=m+1print(s)输入待查数据值为23,执行该程序段,则输出的结果是( )A.25,20,24,23 B.24,18,20,23C.25,20,23 D.24,20,2311.有如下Python程序段:key=int(input(″请输入任意一个整数:″))a=[12,18,22,27,36,45]ans=0i=0;j=len(a)-1while i<=j:m=(i+j+1)//2if a[m]<=key:i=m+1else:j=m-1ans+=a[m]print(ans)执行以上程序段,输入任意的key值,则ans的值不可能是( )A.45 B.57C.67 D.7212.有如下对分查找程序,a为按非降序排序的整型数组;import randomkey=random.randint(0,4)*2+20a=[12,14,15,15,19,x,20,24,y,26]c=0i=0;j=len(a)-1while i<=j:m=(i+j)//2if a[m]<=key:i=m+1else:j=m-1c+=1测试所有可能的key值,程序执行后c均等于4,下列正确的x,y值可以为( )A.19,25 B.20,26C.20,25 D.20,24二、非选择题(本大题共3小题,其中第13小题7分,第14小题10分,第15小题9分,共26分)13.小T编写了一个Python程序功能如下:输入需随机生成的坐标点数量,经过程序执行后,自动生成并显示相应数量的途经点坐标(坐标值为大于等于1小于10的实数,四舍五入保留一位小数),试图求出平面坐标系中一端(最左和最右的点称为端)出发,按照一定的规则途经所有点到达另一端的路径长度(四舍五入保留一位小数)。程序执行界面如图所示。(1)实现上述功能的Python程序如下,将划横线部分的代码补充完整。from random import*from math import*data=[[0,0] for i in range(100)]k=int(input(″请输入点的个数″)) #产生k个点的随机坐标for i in range(k):data[i][0]=randint(0,90)/10+1data[i][1]=randint(0,90)/10+1print('x:',data[i][0],' y:',data[i][1])flag=False ; i=0while i<=k-2 and not flag:flag=Truej=0while ①________:if data[j][0]*100+data[j][1]>data[j+1][0]*100+data[j+1][1]: data[j],data[j+1]=data[j+1],data[j] flag=Falsej+=1②________s=0;length=0for i in range(k-1):x1=③________ #y1的计算方式同x1,代码略length=sqrt(x1+y1)s+=lengthprint(″路径长度是:″,④________)(2)由程序看,访问坐标系中所有点的规则是________(单选,填字母:A.左上到右下/B.左下到右上/C.右下到左上/D.右上到左下)。 14.某工厂收到了n个产品的订单,这n个产品分别在A、B两个车间加工,并且必须先在A车间加工后才可以送到B车间加工。为了使得总加工时间最短,我们可以将这n个产品分为两类,第一类在A车间加工时长少于在B车间加工时长,第二类在A车间加工时长不少于在B车间加工时长。第一类应将在A车间花费时间少的产品排在前面,第二类应将在B车间花费时间少的产品排在后面,然后先处理所有第一类产品,再处理第二类产品。可以证明,这样排序后所有产品加工完成花费的总时间最少。例如有4种产品,它们在A车间加工时长分别为3、5、8、4,在B车间加工时长分别为6、1、2、7,产品分类、排序、合并、计算时长的过程如第15题图所示,最后得出总时长为21。(每个产品在B车间开始加工需同时满足它在A车间加工完并且B车间已加工完上一个产品这两个条件)。编写程序模拟工厂对这n个产品的处理过程,计算总加工时间。请回答下列问题:(1)由题意可知,若3种产品在A车间加工时长分别为5、7、3,B车间加工时长分别为6、1、2,则总加工时长为________。(2)小华先编写了如下将第一类产品排序的函数:def sort1(a,b): #参数a、b的元素分别表示每个产品在A、B车间的加工时长。n=len(a)for i in range(n-1):for j in________: if a[j]>a[j+1]: a[j],a[j+1]=a[j+1],a[j] b[j],b[j+1]=b[j+1],b[j]划线处可以填写的代码有________(多选,填字母。全部选对的得2分,选对但不全的得1分,不选或有选错的得0分)A.range(n-1-i) B.range(n-1,i,-1)C.range(i,n-1) D.range(n-2,i-1,-1)(3)小强编写了如下将第二类产品排序的函数:def sort2(a,b): #参数a、b的元素分别表示每个产品在A、B车间的加工时长。n=len(a)for i in range(1,n):k1,k2=a[i],b[i]j=i-1while________: a[j+1],b[j+1]=a[j],b[j] j-=1 a[j+1],b[j+1]=k1,k2①请在划线处填入合适的代码。②此程序时间复杂度为________。(单选,填字母)A.O(1) B.O(n)C.O(n2) D.O(nlog2n)(4)小张结合前两位同学的程序,计算产品加工总时长。请在划线处填入合适的代码。'''读取n个产品在A、B两车间加工的时间,根据题目要求分为两类,第一类产品在A、B两车间加工的时间分别存储在列表a1和列表b1中,并通过sort1()函数排序,第二类产品在A、B两车间加工的时间分别存储在列表a2和列表b2中,并通过sort2()函数排序,代码略'''a=a1+a2b=b1+b2n=len(a)k,t=0,0 #k为A加工时间,t为B加工时间for i in range(n):k+=a[i]if ①________:t=k②________print(″总加工时长最短为:″,t)15.进入新学期第一天,班主任老师将班上N个同学(学号为1-N)排成一排,分配座位。从排队到分配座位步骤如下:步骤一:先将1号同学安排进队;步骤二:2~N号同学由老师依次指定入队位置,如学号为i的同学由老师指定站在队中某位同学的左侧或右侧;步骤三:所有同学按照上述方法入队完毕后,2人一组的方式依次分配到四个组别中;步骤四:输出每组学生的名单。请回答下列问题。(1)若某班有4位同学,学号为1~4,完成步骤一后,执行步骤二的指令3次,每次指令包含两个整数k和p(p为0或1)。若p为0,则表示插在k号同学的左侧,p为1则表示插在k号同学的右侧。若三条指令分别为10、21、10,则执行指令后队伍从左到右学号分别为:________。(2)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。def insert(k,x):R[x]=R[k]L[x]=k①________R[k]=xL=[0]*100;R=[0]*100insert(0,1) #0的右边插入1号同学#info列表存储各学生姓名和学号,格式如[[″张三″,1],[″李四″,2]…],代码略n=len(info)for i in range(2,n+1):k=int(input(″请问插入在几号同学旁边?″))p=int(input(″请输入该同学的左侧还是右侧″))if p==0:②________else:insert(k,i)q=[[]for i in range(4)]i=m=0③________while x!=0:q[i].append(x)m=m+1if m%2==0:④________x=R[x]for i in range(4):for j in q[i]:print(info[j-1][0],end=″ ″)print()第七单元 数据结构与算法1.B [f(5,3)=f(4,2)+f(6,2)=f(3,1)+f(5,1)+f(5,1)+f(7,1)=20。]2.C [s的长度为6,f(s)返回f([1,2])+f([[3,4,5,6]]),调用2次,函数f([1,2])值为3,调用1次。f([[3,4,5,6]])返回f([[3,4])+f([[5,6]]),调用2次。f([[3,4])和f([[5,6]])各调用1次,共调用7次。]3.A [本题考查递归的应用。该程序实现计算n的阶乘。A选项jc(5)=5*4*3*2*1=120。B选项函数调用5次,该语句执行5次。C选项执行4次。D选项n<2和n==1是等效的。]4.C [本题考查函数递归的分析和理解。该程序段的功能是利用递归判断一个字符串是否是“回文串”。A选项″1234321″是回文串。B选项该函数内部调用了自身,是递归算法。C选项f(″1234321″)→f(″23432″)→f(″343″)→f(″4″)→True,调用4次。D选项程序内部只调用本身一次,算法复杂度是O(n)。]5.A [本题考查冒泡排序的算法思想。从后往前依次比较相邻两个位置数据的大小,并把较小数据换到前一位置。排序结果为2,3,8,7,5,6,9。从前往后冒泡的结果为2,3,7,6,5,8,9。]6.A [本题考查教材上的冒泡排序算法基本原理。第一趟交换5次,序列为“0,2,3,4,5,1,”。第二趟交换4次,序列为“0,1,2,3,4,5”。至此数据已经有序,无需交换。共交换9次。所以答案为A。]7.B [本题考查冒泡排序的算法思想。当i=n时,j in range(1,n-1),当j为最后一个值n-2时(range右边为开区间,n-1取不到),a[n-2]与a[n-3]比较大小,缺少a[n-1]与a[n-2]比较大小,不能完成所有n个数据的升序排序。]8.C [本题考查索引排序。数组a存储的0~5的索引位置,程序实现从前往后冒泡,当条件s[a[j]]>s[a[j+1]]成立时交换,实现升序排列,因此排序后的结果是abbccc,找到这些字母的索引位置。]9.A [本题考查冒泡排序算法思想。算法实现从左往右降序排列。A选项例如某个数后面有2个数,且一个数大他小,一个数比他大,当大的数往前交换后,第2次比他小的数又把换回来了。总的比较次数为n*(n-1)/2=15。D选项如果原数据已经有序了,不会发生交换。]10.B [本题考查对分查找。根据对分查找的特点、中点位置取值(i+j)//2是偏左的,最后输出的应该24、18、20、23。]11.A [本题考查二分查找,找到后不退出,直到i>j为止后退出,ans记录的是查找过程中所访问到的数之和。]12.D [c表示查找次,查找到结果后并没有结束循环,画出如图所示二叉树,x的值介于20和24之间,但要查找4次,x的值必定为20。y的值介于24和26之间,但要查找4次,y的的值不能为26。由于查找的key是偶数,若y的值为25,须查找5次。]13.(1)①j<=k-i-2或者j解析 本题考查冒泡算法。(1)本程序实现从前往后冒泡,后面的数据先有序,flag表示某趟排序是否有数据交换的标志,若有没有数据交换,提前结束排序。①坐标值为大于等于1小于10的实数,将x的坐标*100,意味着扩大x坐标的权重,即x是主关键字,若产生两个x相等,那么再加上y坐标。从前往后冒泡,每次是i的对称位置k-i-1有序,由于比较对象为j和j+1,因此内循环的终点为k-i-2。②外循环i每次加1。③k个点,只有k-1条线段,因此循环k-1次。每次利用两点距离公式进行求线段长度。④四舍五入保留一位小数显示路径长度。(2)以x为主关键字升序,y为次关键字升序,因此是从左下向右上形成路径。14.(1)16 (2)AD (3)①j>=0 and k2>b[j] ②C (4)①t解析 本题考查排序相关概念及算法时间复杂度。(1)根据划分标准将3种产品分别编号为①②③,加工顺序为①③②,加工时间段为:产品①0-5,5-11;产品③5-8,11-13;产品②8-15,15-16,总加工时长为16。(2)内循环表示扫描方向,若从左向右排序,比较对象为a[j]和a[j+1],左端点固定为0,第i趟排序右端点为n-1-i,当j+1达到n-1-i时,j的值为n-2-i,由于该位置取不到,因此range值为(0,n-1-i)。若从右向左排序,右端点(j+1的值)固定为n-1,左端点为i,因此range值为(n-2,i-1,-1)。(3)①对第二类产品按在B车间的加工时长做插入排序。内层循环寻找插入位置,将比k2小的元素依次右移一位,关注j的边界不能小于0,此时j+1处即为插入位置,对b[j+1]赋值为k2。②插入排序的时间复杂度为O(n^2)。(4)计算总加工时长,累加产品时长,k为A加工时间,t为B加工时间;根据输出最后的结果为t即为总时长,如果当前产品A车间加工的时长大于B车间加工时长,那当前产品进入B车间开始加工的时间即t=k,故①处为t15.(1)2341 (2)①L[R[k]]=x ②insert(L[k],i) ③x=R[0] ④i=(i+1)%4解析 本题考查索引数组和双向链表的知识。(1)在1左侧插入2,队伍为21,在2的右侧插入3为231,在1的左侧插入4,队伍为2314。(2)①在学号k的右侧插入x,则x的左侧是k,右侧是原k的右侧,同时要修改k的右侧指向。②insert程序的功能是在k的右侧插入x,那么现在在x的左侧插入意味着在k的前一个数L[k]的右侧插入x。③由于0没有存放学号,但他的右侧是第1个学号,因此当前节点从R[x]开始遍历各个元素。④i表示组别,共有4组,其值从0,1,2,3循环变化。 展开更多...... 收起↑ 资源预览