第五章 数据结构与算法（单元测试）信息技术浙教版2019选择性必修1

第五章 数据结构与算法 单元测试 姓名： 班级： 分数： （满分：100分 时间：90分钟） 题型 选择题 填空题 总计 题数 20 11 31题 分数 60 40 100分 得分 一、单项选择题（每题3分，共60分） 1.某算法的时间复杂度是〇(n),表明该算法()。 A.问题规模是n B.问题规模与n成正比 C.执行时间等于n D.执行时间与n成正比 【答案】D [解析]算法的时间复杂度是〇(n),这是设定问题规模为n的分析结果,所以A、B都不对;它也不表明执行时间等于n,它只表明算法的执行时间T(n)≤cXn(c为比例常数)。有的算法,如nXn矩阵的转置,时间复杂度为〇(n),不表明问题规模是n。 2.下列关于算法效率分析的说法,正确的是()。 A.算法复杂度是指算法控制结构的复杂程度 B.算法的时间复杂度是指算法执行的速度 C.算法的空间复杂度是指算法执行所需的时间 D.算法的时间复杂度是指算法在执行过程中基本运算的次数 【答案】D [解析]算法复杂度分为时间复杂度和空间复杂度,其中时间复杂度反映了算法执行所需要的时间,而空间复杂度反映了算法执行所需要占用的存储空间。 3.下列有关迭代算法和递归算法的描述，不正确的是()。 A.在使用递归算法时，必须有一个明确的递归结束条件，称为递归出口 B.一般来说，迭代算法效率较低，而递归算法效率较高 C.递归中一定有迭代，但迭代中不一定有递归 D.通常情况下，迭代算法和递归算法可以相互转换 答案：B [解析]迭代算法通常效率较高，而递归算法可能效率较低。这是因为递归算法在递归调用时需要保存上下文，包括局部变量和返回地址，而这可能导致开销较大。此外，递归算法在递归深度较深时可能引起栈溢出，因此需要小心处理递归深度。所以选项B符合题意。故选:B。 4.运用分治策略将一个难以直接解决的大问题分割成规模较小的子问题分别解决，最终达到解决大问题的目的。这要求原问题和子问题的（）。 A.问题性质相同，问题规模相同 B.问题性质不同，问题规模相同 C.问题性质相同，问题规模不同 D.问题性质不同，问题规模不同 答案：C [解析]运用分治策略将一个难以直接解决的大问题分割成规模较小的子问题分别解决，最终达到解决大问题的目的。这要求原问题和子问题的问题性质相同，问题规模不同，所以选项C符合题意。故选: C。 5.通常是为了接近并达到所需的目标或结果，对过程进行重复，每一次重复得到的结果会被用来作为下一次的初始值。这种用计算机解决问题的一种基本方法是()。 A.迭代法 B.查找法 C.分析法 D.排序法 答案：A [解析]本题考查计算机解决问题的方法。迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法(或者称为一次解法)，即一次性解决问题。迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值，迭代法又分为精确迭代和近似迭代。查找法是指对指定数据在数组中进行查找。排序法是对数据排序后进行后续处理。分析法是“综合法”的对称。把复杂的经济现象分解成许多简单组成部分，分别进行研究的方法。其实质是通过调查研究，找出事物的内在矛盾，并对矛盾的各个方面进行深入研究。故本题选A。 6.采用冒泡排序算法对数据序列18,13,15,2,1,20进行排序，第一轮排序后的结果为20,18,13,15,2,1,则完成整个序列的排序需要进行数据交换的次数总共是( )。 A.6 B.7 C.8 D.9 答案：D [解析]数据序列“18，13，15，2，1，20”进行排序，第一轮排序后的结果为“1，18，13，15，2，20”，可知冒泡算法的思想进行升序排列数组，要完成最终的排序需要进行9轮比较最终完成故选:D。 7.下列关于冒泡排序的叙述，正确的是()。 A.10个数冒泡排序每一趟都要进行9次数据比较 B.冒泡排序相邻的数据一定要比较并交换 C.冒泡排序相邻的数据一定要比较，但不一定交换 D.冒泡排序是所有排序算法最快的一种算法 答案：C [解析]由冒泡排序算法基本思想知:依次比较两个相邻的数据，如果顺序错误就交换它们，所以相邻的数据一定会比较，但不一定交换，所以B错误，C正确;冒泡排序中，几个数要进行n -1次比较，在第j趟中要进行n-j趟比较，所以A错误;在排序算法中，根据原始数据的不同，不同算法的效率不一样，速度也不一样，所以D错误。故选C。 8.对“842715”中的数字进行选择排序中的两遍“加工”即为某密码锁的密码，则该密码可能是( )。 A.842715 B.142785 C.872415 D.124578 答案：.C [解析]如果选择升序排序,第1遍后为142785.找到最小的值与第1个位置交换,其他不动。第2遍后为124785。如果选择是降序排序,第1遍后为842715.因为第1个位置数本身是最大,不用交换。第2遍后为872415。第二大的数与第2位置数交换。 9.若线性表采用链式存储结构，则适用的查找方法为()。 A.随机查找 B.散列查找 C.二分查找 D.顺序查找 答案：A [解析]随机查找表中元素时，访问表中任一元素所需时间与元素的位置和排列次序无关。以散列方式存储和查找数据时，元素的存储位置与其关键字相关。二分法查找只能在有序顺序表中进行。由于链表中的元素只能通过取得元素所在的节点的指针进行，因此只能顺序查找表中的元素。 10.数组里有12个元素，依次为:34、40、41、43、53、55、65、70、72、74、80、95，下列选项中不正确的是()。 A.如使用顺序查找法，53需要查找5次 B.如使用对分法查找，53需要查找3次 C.如使用顺序查找法，70需要查找8次 D.如使用对分法查找，70需要查找4次 答案：B [解析]顺序查找是比数据的第一个元素开始依次比较，AC两项分别查找53和70的次数为5次和8次，说法正确;B项对分查找53，i=1，j=12，m=(i+j)2=6，第6个元素为55，比53大，因此i=1，j=m-1=5，m=(i+j)\2=3，第3个元素为41,41比53小，i=m+1=4，j=5，m=(i+j)\2=4,第4个元素为43，43比53小，因此，i=m+1=5，j=5，m=(i+j)\2=5，第5个元素为53，找到元素，共查找了4次，而非3次;故选:B. 11.有如下 Python程序代码: n=int(input("n=")) t=1 while 2 ** t<n: t=t+1 print("t=",t) 则该算法的时间复杂度为（）。 A.〇(1) B.〇(n) C.〇(log2n) D.〇(2n) 【答案】C [解析]本题主要考查的是时间复杂度的计算。观察程序,可计算出t=log2n，因此其时间复杂度〇(log2n),答案为C。 12.有如下 Python程序代码: s=0 n=int(input( "n=")) s=n*(n+1)//2 print("s=",s) 则该算法的时间复杂度为()。 A.〇(1) B.〇(n) C.〇(n2） D.〇(2n) 【答案】A [解析]本程序只包含顺序结构，时间复杂度为〇(1),因此,答案为A。 13.用对分查找法从数列3、6、7、10、12、16、25、30、75中找到数据10的查找次数是() A.2 B.3 C.4 D.7 【答案】C [解析]假设数列存储于数组a中，以下为查找10的过程: 第一次查找:i=1，j=9，m=(i+j)\2=5，a(5)=12，12>10，j=m-1=4; 第二次查找:i=1，j=4，m=(i+j)\2=2，a(2)=6，6<10，i=m+1=3; 第三次查找:i=3，j=4，m=(i+j)\2=3，a(3)=7，7<10，i=m+1=4; 第四次查找:i=4，j=4，m=(i+j)\2=4，a(4)=10，找到数据，共查找了四次，故选:C. 14.定义如下函数: def f(a,b): ifa<b: #① a,b=b,a ifa%b==0: return b else: return f(b,a%b) 执行语句print(f(27,121)),注释①处的代码执行的次数是（）。 A.1 B.2 C.3 D.4 答案：C [解析]本题函数f的功能是通过辗转相除法求两数的最大公约数,27和121的最大公约数求解过程为:121%27=13;27%13=1;13%1=0,总共需要调用函数f3次,注释①处语句也执行3次。 15.有如下python程序段: a =[33,24,45,16,77 for i in range (0, 2): for j in range (4,i,-1): if a|j]> a[i]: a|j],a[i]=a[i],alj] 经过该程序段“加工”后，数组元素a的值依次为()。 A.77，45，33，16，24 B.77，33，45，16，24 C.77，24，45，16，33 D.77，45，33，24，16 答案：A [解析].foriinrange(0,2):外循环次数=2，内循环forjinrange(4,i,-1):，内循环i.fa [j] > al]:a|j]与a[]交换，i=0，第一次比较完成后a =[77,24,45,16,33]，i=1第二次比较完成后，a=[77,45,33,16,24，A选项正确。故选:A。 16.某二分查找算法的程序如下： i＝0 j＝7 n＝10 while i<＝ j ： n＝n＋1 m＝(i ＋ j)//2 if key＝＝d[m]： break elif key > d[m]： j＝m－1 else： i＝m＋1 数组元素d[0]到d[7]的值依次为″83，75，62，41，33，27，16，2″，若运行该程序段后，n的值为2，则key的值可能是()。 A.62或16 B.62或27 C.75或27 D.75或16 答案：C [解析]考查二分查找。根据n的值,可知在第二次进行折半查找时,key 查找成功。 查找次数 i j M取下整：（i+j）//2 d[m] 1 0 7 M=(0+7)//2=3 41 2（key>d[m]) 0 2 M=(0+7)//2=1 75 2（key<d[m]) 4 7 M=(0+7)//2=5 27 故选C. 17.某python程序段代码如下: s = input() n=1 ss=” ” for i in range (1,len (s)): if s[i] == s[i- 1]: n+=1 else: ss+=str(n)+s[i-1] n=1 print (ss) 程序段执行后，输入的字符串为AACCCCCDEEEE”，则输出的结果为()。 A.2A5C0D4E B.2A5C1D4E C.5C1D4E D.2A5C1D 答案：B [解析]阅读程序可知，程序实现的是将字符中相邻的重复的字母进行累加，然后简化字符串的表示方法，所以输入的字符串为“AACCCCCDEEEE”，则输出的结果为2A5C1D4E。故选:B。 18.定义如下函数: def peach (day): if day == 7: num =1 else: num=(peach(day+1)+1)*2 return num print (peach(1)) 执行该程序段后，输出的结果是（）。 A.14 B.94 C.190 D.382 答案：C [解析]阅读程序段可知，只有当day==7时，num的值为1，所以从1到6，需要调用6次，numm的值分别为4，10，21，45，95，190。故选:C。 19.运行以下程序段后,输出的列表为（） def bubble_sort(L): length=len(L) for i in range(l ,3): for j in range(0,length-i): if L[j]<L[j+1]: temp=L[j] L[j]=L[j+1] L[j+1]=temp A=[6,8,2,4,3,7] bubble_sort(a) print(a) A.[2.3.4.6.7,8] B.[8,7.6.4.3,2] C.[8,6.4.7.3.2] D. 16,8.7,4.3,2] 答案：C [解析]观察代码“foriin range(1,3)”,变量i只执行两次,循环体是利用冒泡排序,从前往后比较实现降序。i=1执行完后a的状态为[8,6,4,3,7,2],i=2执行完后a的状态为[8,6,4,7.3,2],所以答案选C。 20.实现某排序算法的部分Python程序段如下 def bubble_sort(L): length=len(L) for i in range(1,5): for j in range(0,length-i): if L[j]<L[j+1]: temp=L[j] L[j]=L[j+1] L[j+1]=temp ans.append(L[length-i]) a=[3,9,2,1,5,2,6] ans=[ ] bubble_sort(a) print(ans) 经过该程序段“加工”后,输出的结果是()。 A.[9,6,5,3] B. [1,2,2,3] C.[3,9,2,1] D.[6,2,5,1] 答案：B [解析]该程序中,兩数bubble_sort(L)是利用冒泡排序的思想对数组L按从前往后比较方式进行降序排序,一趟加工完成后最后面的元素是当前的最小数据,将该元素添加进数组ans,所以第一趟完成后数组ans中的元素是[1],观察到i的循环范围是1~4,即只进行4趟比较与交换,数组ans中依次记录[1,2,2,3],因此正确答案是B。 2、 填空题（每空2分，共计40分） 1.用二分查找法查找列表[3,9,16,25,33,47,56]中的数字33，需要查找 次。 【答案】3 [解析]用变量i和1分别表示列表数据的开始和结束位置，i=1，j=7。第一次查找:(i+j)//2=4，25<33，i=4+1=5;第二次查找:(i+j)//2=6，47>33,j=6-1-5;第三次查找:(i+j)//2=33，故需要查找3次。 2.在某篮球赛季中，明星队6场比赛得分依次为103,77,95,71,68,89,若采用冒泡排序算法对其进行排序，第一轮排序结果是68,103,77,95,71,89.则第三轮排序中共进行 次数据交换。 答案：1 [解析]第一轮排序结果是68,103,77,95,71,89.第二轮排序结果是68,71,103,77,95,89.第三轮排序结果是68,71,77,103,95,89.则第三轮排序中共进行了1次数据交换综上所述，答案:1。 3.一段楼梯共有10级台阶，规定每步只能跨1级或2级，要登上第10级台阶有 种不同的走法。 答案：89 [解析]由于登台阶每次只能跨1级或2级，因此登上第n级台阶的情形仅与登上第n-1级和第n一2级台阶有关，可以考虑建立递推关系。列表如下: 级数 1 2 3 4 5 6 …… 10 走法 1 2 3 4 8 13 …… 89 登上第1级台阶只有1种走法，即a1=1;登上第2级台阶有2种走法，即az-2;登上第3级台阶有3种走法，即a:-3;登上第4级台阶有5种走法，即a-5。以此类推，登上各级台阶的走法依次为1，2，3，5，8，13，21，34，55，89。其中a1=89，即登上第10级台阶有89种不同走法。 4.下列程序代码采用的算法是 。 def mi (x,n): if n==0: return 1 else: return x*mi (x,n-1) A.迭代法 B.枚举法 C.递归法 D.解析法 答案：递归法 [解析]递归算法是一种直接或者间接调用自身函数或者方法的算法。说简单了就是程序自身的调用。分析本题代码可知采用的算法是递归法。故填递归法。 5.某查找算法的代码如下: key=inl(inpul("请输人待査元素key:")) a=[62,5,11,17,5.6,99,5,73,45] loc=-1 for i in range(len(a)): if a[i]==key: loc=i break if loc!=-1: print(loc) else: print("查无此数") (1)当输入key的值为5时,执行该代码处理后输出的结果是 。 (2)若希望输出key最后一次出现的位置,只需要对代码进行 修改操作。 (3)该查找算法的时间复杂度为 。 答案：(1)1 (2)将break语句删除 (3)0() [解析]该代码实现的是输出顺序查找数组中key第一次出现的位置,key=5,所以输出的结果为1;想修改为查找出key最后一次出现的位置并输出,只需要让for循环继续查找到最后一次出现的位置并输出,所以只需要删除break语句;该代码采用一重循环枚举a数组中的所有数再与key进行对比,所以时间复杂度为O(n)。 6.有如下程序段 a=[8,1,2,6,3,4,7,5] n=len(a) for i in range (0,n, 2): for j in range(n-l,i*2 + 1,-1): if a|j] < a[j- 2]: a[j], a[j- 2]= a[j- 2],a[j] 则程序运行后，a[4]的值为 。 答案：4 [解析]阅读程序可知，外循环i的取值分别为0，2，4，6。当i= 2时，内循环的取值范围最大为[7,2，此时的排序适用于整个数组，根据a[j] < a[j- 2]的条件进行交换a[j],aj-2]=aj-2]，a|j]的值后，最终得到a[4]的值为4，因为第一个元素的下标为0。故填:4。 7.以下Python代码段: def jishu(n): s=0 while n>0: s+=n%2 n//=2 return s n=int(input("输入一个正整数:")) ans=jishu(n) print(ans) 阅读以上代码,回答以下问题: (1)该程序运行后输入整数23,输出结果为 。 (2)若输入整数23,则程序中自定义函数jishu( )中语句"s+=n%2”执行的次数是 。 (3)函数jishu( )的时间复杂度为 (单选:A.〇(n) B.〇(log2n))。 【答案】(1) 4 (2)5 (3) B [解析]代码实现的功能是统计正整数n的二进制表示中1的个数，利用while循不每次将n整除2。直到商是0为止。23D-10111B，所以有4个"1"；"23”在统计过程中“s+=n%2”会执行5次，所以该算法的时间复杂度为〇(log2n)。 8.编写递归函数计算前n个正整数的和,即计算s=1+2+…+n。请在划线处填人合适的代码。 def s(n) : if n==1: return 1 else : return 答案：n+s(n-1) [解析]本题考查递归算法。递归函数功能是求n个正整数的和:s=1+2+…+n,所以n项和为n+s(n-1)。 9.斐波那契在《计算之书》中提出了一个有趣的兔子问题:假设一对兔子每个月可以生一对小兔子，一对兔子出生后第2个月就开始生小兔子。则一对兔子一年内能繁殖成多少对?程序 代码如下，请补全划线处对应的代码: def fib(n): f2=f1= (1) for i in range (3, (2) ): f1,f2=f2,f1=f2 retum (3) n=int(input("输入月份数:")) print("兔子总对数为:"，fib(n)) n=int(input("输入月份数:")) print("兔子总对数为:",fib(n)) (1) (2) (3) 答案：(1)1、(2)n +1、(3)f2 [解析](1)分析题干可知，这是一个斐波那契数列，即满足数量1、1、2、3、5、8..，即从第三项开始，后一项等于前两项之和，故f1和f2的初值是1。 (2)循环变量i表示月份，其范围是从3 ~ n。range(start,stop,[step]),start:计数从start开始。默认是从0开始。例如range(5)等价于range(0,5);stop:计数到stop结束，但不包括stop。故此空填n +1。 (3)循环结束后，f2的值即出生第n个月能繁殖的总对数，故填f2。 10.某 Python程序如下： a=[92,22, 11,98,96,71] n=len(a) for i in range(n): for j in range( ): if a[j]>a[j+1]: a[j],a[j+1]=a[j+1],a[j] print(a) 为实现n个数的升序排序，划线处应填入的代码是 。 答案：range(n-2,i-1,-1) [解析]本题主要考查冒泡排序算法。分析程序,外层循环变量i的范围是0~n-1,该程序实现升序排序,比较的是索引j与j+1,内层循环可以从左往右比较,每次将一个最大值放到最右边,代码为ange(n-i-1);也可以从右往左比较交换,每次将一个最小值放到最左边,代码为 range(n-2,i-1,-1)。 11.数组a存放着一组正整数,其中奇数在前,偶数在后。奇数与偶数已分别升序排序,形如[1,7,13,15,21,2,4,8,22,26,30,36,40]。 依据二分查找思想,小萌设计了一个从数组a中查找数据 key 的算法,其程序如下： i=0;j=9 key=int(input("请输人待查数据:")) while i<=j: m=(i+j)//2 if a[m]= =key:break if key%2==0 and a[m]%2==1: ① elif key%2==1 and a[m]%2==0： ② else : if ③ ： j=m-1 else : i=m+1 if i>j: print("未找到") else : print("数组元素a["+str(m)+"]即为所求!") 请在程序划线处填人合适的代码。 ① 。 ② 。 ③ 。 答案：①i=m+1 ②j=m-1③key<a[ m ] [解析]根据题目的描述“奇数在前,偶数在后”可知:若满足 key 是偶数且中间项a[m]为奇数,则向后找;若满足 key是奇数且中间项a[m]为偶数,则向前找;如果中间项a[m]与 key同奇同偶,那么根据二分查找的思想继续查找。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$ 第五章 数据结构与算法 单元测试 姓名： 班级： 分数： （满分：100分 时间：90分钟） 题型 选择题 填空题 总计 题数 20 11 31题 分数 60 40 100分 得分 一、单项选择题（每题3分，共60分） 1.某算法的时间复杂度是〇(n),表明该算法()。 A.问题规模是n B.问题规模与n成正比 C.执行时间等于n D.执行时间与n成正比 2.下列关于算法效率分析的说法,正确的是()。 A.算法复杂度是指算法控制结构的复杂程度 B.算法的时间复杂度是指算法执行的速度 C.算法的空间复杂度是指算法执行所需的时间 D.算法的时间复杂度是指算法在执行过程中基本运算的次数 3.下列有关迭代算法和递归算法的描述，不正确的是()。 A.在使用递归算法时，必须有一个明确的递归结束条件，称为递归出口 B.一般来说，迭代算法效率较低，而递归算法效率较高 C.递归中一定有迭代，但迭代中不一定有递归 D.通常情况下，迭代算法和递归算法可以相互转换 4.运用分治策略将一个难以直接解决的大问题分割成规模较小的子问题分别解决，最终达到解决大问题的目的。这要求原问题和子问题的（）。 A.问题性质相同，问题规模相同 B.问题性质不同，问题规模相同 C.问题性质相同，问题规模不同 D.问题性质不同，问题规模不同 5.通常是为了接近并达到所需的目标或结果，对过程进行重复，每一次重复得到的结果会被用来作为下一次的初始值。这种用计算机解决问题的一种基本方法是()。 A.迭代法 B.查找法 C.分析法 D.排序法 6.采用冒泡排序算法对数据序列18,13,15,2,1,20进行排序，第一轮排序后的结果为20,18,13,15,2,1,则完成整个序列的排序需要进行数据交换的次数总共是( )。 A.6 B.7 C.8 D.9 7.下列关于冒泡排序的叙述，正确的是()。 A.10个数冒泡排序每一趟都要进行9次数据比较 B.冒泡排序相邻的数据一定要比较并交换 C.冒泡排序相邻的数据一定要比较，但不一定交换 D.冒泡排序是所有排序算法最快的一种算法 8.对“842715”中的数字进行选择排序中的两遍“加工”即为某密码锁的密码，则该密码可能是( )。 A.842715 B.142785 C.872415 D.124578 9.若线性表采用链式存储结构，则适用的查找方法为()。 A.随机查找 B.散列查找 C.二分查找 D.顺序查找 10.数组里有12个元素，依次为:34、40、41、43、53、55、65、70、72、74、80、95，下列选项中不正确的是()。 A.如使用顺序查找法，53需要查找5次 B.如使用对分法查找，53需要查找3次 C.如使用顺序查找法，70需要查找8次 D.如使用对分法查找，70需要查找4次 11.有如下 Python程序代码: n=int(input("n=")) t=1 while 2 ** t<n: t=t+1 print("t=",t) 则该算法的时间复杂度为（）。 A.〇(1) B.〇(n) C.〇(log2n) D.〇(2n) 12.有如下 Python程序代码: s=0 n=int(input( "n=")) s=n*(n+1)//2 print("s=",s) 则该算法的时间复杂度为()。 A.〇(1) B.〇(n) C.〇(n2） D.〇(2n) 13.用对分查找法从数列3、6、7、10、12、16、25、30、75中找到数据10的查找次数是() A.2 B.3 C.4 D.7 14.定义如下函数: def f(a,b): ifa<b: #① a,b=b,a ifa%b==0: return b else: return f(b,a%b) 执行语句print(f(27,121)),注释①处的代码执行的次数是（）。 A.1 B.2 C.3 D.4 15.有如下python程序段: a =[33,24,45,16,77 for i in range (0, 2): for j in range (4,i,-1): if a|j]> a[i]: a|j],a[i]=a[i],alj] 经过该程序段“加工”后，数组元素a的值依次为()。 A.77，45，33，16，24 B.77，33，45，16，24 C.77，24，45，16，33 D.77，45，33，24，16 16.某二分查找算法的程序如下： i＝0 j＝7 n＝10 while i<＝ j ： n＝n＋1 m＝(i ＋ j)//2 if key＝＝d[m]： break elif key > d[m]： j＝m－1 else： i＝m＋1 数组元素d[0]到d[7]的值依次为″83，75，62，41，33，27，16，2″，若运行该程序段后，n的值为2，则key的值可能是()。 A.62或16 B.62或27 C.75或27 D.75或16 17.某python程序段代码如下: s = input() n=1 ss=” ” for i in range (1,len (s)): if s[i] == s[i- 1]: n+=1 else: ss+=str(n)+s[i-1] n=1 print (ss) 程序段执行后，输入的字符串为AACCCCCDEEEE”，则输出的结果为()。 A.2A5C0D4E B.2A5C1D4E C.5C1D4E D.2A5C1D 18.定义如下函数: def peach (day): if day == 7: num =1 else: num=(peach(day+1)+1)*2 return num print (peach(1)) 执行该程序段后，输出的结果是（）。 A.14 B.94 C.190 D.382 19.运行以下程序段后,输出的列表为（） def bubble_sort(L): length=len(L) for i in range(l ,3): for j in range(0,length-i): if L[j]<L[j+1]: temp=L[j] L[j]=L[j+1] L[j+1]=temp A=[6,8,2,4,3,7] bubble_sort(a) print(a) A.[2.3.4.6.7,8] B.[8,7.6.4.3,2] C.[8,6.4.7.3.2] D. 16,8.7,4.3,2] 20.实现某排序算法的部分Python程序段如下 def bubble_sort(L): length=len(L) for i in range(1,5): for j in range(0,length-i): if L[j]<L[j+1]: temp=L[j] L[j]=L[j+1] L[j+1]=temp ans.append(L[length-i]) a=[3,9,2,1,5,2,6] ans=[ ] bubble_sort(a) print(ans) 经过该程序段“加工”后,输出的结果是()。 A.[9,6,5,3] B. [1,2,2,3] C.[3,9,2,1] D.[6,2,5,1] 2、 填空题（每空2分，共计40分） 1.用二分查找法查找列表[3,9,16,25,33,47,56]中的数字33，需要查找 次。 2.在某篮球赛季中，明星队6场比赛得分依次为103,77,95,71,68,89,若采用冒泡排序算法对其进行排序，第一轮排序结果是68,103,77,95,71,89.则第三轮排序中共进行 次数据交换。 3.一段楼梯共有10级台阶，规定每步只能跨1级或2级，要登上第10级台阶有 种不同的走法。 4.下列程序代码采用的算法是 。 def mi (x,n): if n==0: return 1 else: return x*mi (x,n-1) A.迭代法 B.枚举法 C.递归法 D.解析法 5.某查找算法的代码如下: key=inl(inpul("请输人待査元素key:")) a=[62,5,11,17,5.6,99,5,73,45] loc=-1 for i in range(len(a)): if a[i]==key: loc=i break if loc!=-1: print(loc) else: print("查无此数") (1)当输入key的值为5时,执行该代码处理后输出的结果是 。 (2)若希望输出key最后一次出现的位置,只需要对代码进行 修改操作。 (3)该查找算法的时间复杂度为 。 6.有如下程序段 a=[8,1,2,6,3,4,7,5] n=len(a) for i in range (0,n, 2): for j in range(n-l,i*2 + 1,-1): if a|j] < a[j- 2]: a[j], a[j- 2]= a[j- 2],a[j] 则程序运行后，a[4]的值为 。 7.以下Python代码段: def jishu(n): s=0 while n>0: s+=n%2 n//=2 return s n=int(input("输入一个正整数:")) ans=jishu(n) print(ans) 阅读以上代码,回答以下问题: (1)该程序运行后输入整数23,输出结果为 。 (2)若输入整数23,则程序中自定义函数jishu( )中语句"s+=n%2”执行的次数是 。 (3)函数jishu( )的时间复杂度为 (单选:A.〇(n) B.〇(log2n))。 8.编写递归函数计算前n个正整数的和,即计算s=1+2+…+n。请在划线处填人合适的代码。 def s(n) : if n==1: return 1 else : return 9.斐波那契在《计算之书》中提出了一个有趣的兔子问题:假设一对兔子每个月可以生一对小兔子，一对兔子出生后第2个月就开始生小兔子。则一对兔子一年内能繁殖成多少对?程序 代码如下，请补全划线处对应的代码: def fib(n): f2=f1= (1) for i in range (3, (2) ): f1,f2=f2,f1=f2 retum (3) n=int(input("输入月份数:")) print("兔子总对数为:"，fib(n)) n=int(input("输入月份数:")) print("兔子总对数为:",fib(n)) (1) (2) (3) 10.某 Python程序如下： a=[92,22, 11,98,96,71] n=len(a) for i in range(n): for j in range( ): if a[j]>a[j+1]: a[j],a[j+1]=a[j+1],a[j] print(a) 为实现n个数的升序排序，划线处应填入的代码是 。 11.数组a存放着一组正整数,其中奇数在前,偶数在后。奇数与偶数已分别升序排序,形如[1,7,13,15,21,2,4,8,22,26,30,36,40]。 依据二分查找思想,小萌设计了一个从数组a中查找数据 key 的算法,其程序如下： i=0;j=9 key=int(input("请输人待查数据:")) while i<=j: m=(i+j)//2 if a[m]= =key:break if key%2==0 and a[m]%2==1: ① elif key%2==1 and a[m]%2==0： ② else : if ③ ： j=m-1 else : i=m+1 if i>j: print("未找到") else : print("数组元素a["+str(m)+"]即为所求!") 请在程序划线处填人合适的代码。 ① 。 ② 。 ③ 。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$