5.1 数据结构与算法效率（分层作业）信息技术浙教版选择性必修1

5.1数据结构与算法效率 1课时（分层作业） 【基础达标】 1.算法效率的高低可由 来度量。 2.算法的时间耗费是 。 3.算法的空间耗费是 。 4.用O( )来体现算法时间复杂度，称之为 。 5.常见的算法的时间复杂度有： 、 、 、 、 、 、 。 6.算法的特征包括： 、 、 、 、 。 7..时间复杂度常用符号 表示。 8.下列常见的时间复杂度耗费时间的大小中的最小值是（） A.O(1) B.O(n) C.O(n3 ) )D.O(n!) 9.某算法的时间复杂度是〇(n),表明该算法()。 A.问题规模是n B.问题规模与n成正比 C.执行时间等于n D.执行时间与n成正比 【巩固提升】 1.下列有关算法的时间复杂度的说法,错误的是() A.如果时间复杂度为常数,则时间复杂度为〇(0) B.仅包含顺序结构的算法的时间复杂度为〇(1) C.如果算法中语句的执行次数与问题规模n呈线性增大关系,则时间复杂度为〇(n) D.如果算法中语句的执行次数与问题规模n呈平方增大关系,则时间复杂度为〇(n2) 2.递归算法的函数调用时,处理参数和返回地址,通常使用的数据结构是 A.数组 B.链表 C.队列 D.栈 3.算法的时间复杂度是指什么?() A.算法执行所需的时间 B.算法中语句的数量 C.算法所需内存空间 D.算法执行所需时间随输入规模增长的趋势 4.下列关于算法效率分析的说法,正确的是() A.算法复杂度是指算法控制结构的复杂程度 B.算法的时间复杂度是指算法执行的速度 C.算法的空间复杂度是指算法执行所需的时间 D.算法的时间复杂度是指算法在执行过程中基本运算的次数 5.有如下 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) 6.有如下 Python程序代码: s=0 n=int(input( "n=")) s=n*(n+1)//2 print("s=",s) 则该算法的时间复杂度为() A.〇(1) B.〇(n) C.〇(n2） D.〇(2n) 7.用对分查找法从数列3、6、7、10、12、16、25、30、75中找到数据10的查找次数是() A.2 B.3 C.4 D.7 8.有如下Python程序代码: a=int(input("a=")) b=int(input("b=")) print("a=",a,"b=",b) a,b=b,a print("a=",a,"b=",b) 则该算法的时间复杂度为() A.〇(1) B.〇(n) C.〇(n) D.〇(2") 9.某 Python 程序如下： n=int(input("n=") ansl=ans2=0 fori in range(0,n,2): for j in range(n): ansl=ans1+2 ans2=ans2+2*ans1 print("ansl=",ans1,"ans2=",ans2) 该算法的时间复杂度是 A.〇(1) B.〇(n) C.〇(n²) D.〇(2n) 10.有如下 Python程序段: n=int(input('请输入n:')) s=0 x=0 for i in range(n-1): for j in range(i+1,n): x=i+j s=s+x print(s) 该算法的时间复杂度为() A.〇(1) B.〇(n) C.〇(n²) D.〇(log2n) 11.某同学网购的书,三本书是三个不同的物流公司派送的,将图中每个节点进行编号,作为根节点的“家”编号为“H”其3个子节点(快递门店A，快递门店 B，快递门店 C)分别编号为“A”“B”“C”，图中两结点的连接线表示“权”,值为用时，详见下图。依次列出所有可能走法的分析树，求出取书用时最短时的路径，下列选择正确的是() A.H-A-C-B-H B.H-C-B-A-H C.H-A-B-C-H D.H-B-A-C-H 12.有如下 Python程序代码: n=int(input("please input n:")) s=0 for i in range(n-1): for j in range(n): s=s+i print("s=",s) 则该程序的时间复杂度为() A.〇(1) C.〇(log2n) B.〇(n) D.〇(n2) 【链接高考】 1.某算法的部分流程图如图所示，下列说法正确的是（） A.执行结束后，s的值为127 B.执行结束后，i的值为101 C.该算法的时间复杂度为〇(n) D.调换s ←s+i和i<←i*2的顺序，对结果没有影响 2.杭州模拟)某算法的部分流程图如图所示。执行这部分流程,若输入n的值为2980,则输出s的值为() A.993 B.1993 C.1090 D.2990 3.某算法的部分流程图如图所示。执行这部分流程后，下列说法正确的是() A.输出ans的结果为0101 B.条件“a>0?”共判断5次 C.虚线框内的语句等价为“t←a%2 + b%2” D.该算法使用的控制结构有顺序、分支和循环结构 4.对线性表，在下列哪种情况下应当采用链表表示?(). A.经常需要随机地存取元素 B.经常需要进行插入和删除操作。 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 5.某 Python 程序代码如下: def imax(a,x,y): if x==y: return a[x] else : m=(x+y)//2 return max(imax(a,x,m),imax(a,m+l,y)) a-[1,2,6,5,11,4] n=len(a) print(imax(a,0,n-1)) 则下列说法不正确的（） A.该程序体现了递归的算法思想 B该程序体现了二分查找的算法思想 C.该算法的时间复杂度为(n) D.将语句m=(x+y)//2修改为m=(x+y+1)//2,程序可能会出错 6.用二分查找法查找列表[3,9,16,25,33,47,56]中的数字33，需要查找 次。 7.已知数组a[0:n]为非递减有序序列,输出第一个不小于key的元素下标,若a[n-1]<key,则输出n。可以把该问题抽象成一个自定义函数,函数说明如下: 函数功能:输出非递减有序序列中第一个不小于key的元素下标,若都不小于key,则输 出n。 函数名:search_first( a,key)。 参数表:a一存储了非递减有序序列的数组;key一待查找的特定数据。 返回值:返回第一个不小于key的元素下标，若都不小于key,则返回n。 (1)下列代码为使用顺序查找算法从左向右扫描,寻找最优解的算法实现,请在划线处填入合适的代码。 def search_first_1( a,key): L,R=0,len(a)-1 while L<=R: if a[L]<key: #L位于非解区间,寻找最优解。 L= ① else: #此时L指向最优解 break Return ② (2)若采用顺序查找算法从右向左扫描,则该如何编写代码? (3)下列代码为采用二分查找算法寻找最优解的算法实现,请在划线处填入合适的代码。 def search_first_3(a,key): L,R=0,len(a)-1 while L<=R: m= ① if a[m]>=key: #m位于解区间,寻找更优解 R=m-1 else: #m位于非解区间,寻找最优解 L= ② Return ③ 8.有以下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))。 9.质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。判断某个 大于1的自然数n是否为质数,可以通过查找[2,n-1]之间是否存在因数来实现算法 Python代码如下: def zhishu(x): if x<2: return False Flag=True for i in range(2,x): if x%i=0: flag=False break #① return flag n=int(input( )) ifzhishu(n): print(str(n)+"是质数!") clse: print(str(n)+"不是质数!") (1)自定义函数zhishu()的时间复杂度为 (单选,填字母:A.〇(n)B.〇(I))。 (2)阅读上述代码,回答下述问题。 若删除①处的break语句,程序运行结果是否会发生变化?分析brcak语句在该函数中对算法效率是否有影响,请举例说明。 参考答案 【基础达标】 1.算法复杂度 2.时间复杂度 3.空间复杂度 4.大O记法 5.O(1)、O(log2n)、O(n)、O(n2 )、O(n3 ) 、O(2n )、O(n!) 6.有穷性、确定性、可行性、有0个或多个输入、有1个或多个输出 7.〇 8.【答案】A [解析]常见的时间复杂度耗费时间的大小关系为：O(1)＜O(log2n)＜O(n)＜O(n2 )＜O(n3 ) ＜O(2n )＜O(n!)。 9.【答案】D [解析]算法的时间复杂度是〇(n),这是设定问题规模为n的分析结果,所以A、B都不对;它也不表明执行时间等于n,它只表明算法的执行时间T(n)≤cXn(c为比例常数)。有的算法,如nXn矩阵的转置,时间复杂度为〇(n),不表明问题规模是n。 【巩固提升】 1.【答案】A [解析]本题主要考查的是时间复杂度的表示。如果时间复杂度为常数,则时间复杂度为〇(1),因此答案为A。 2.【答案】D [解析]本题主要考查的是递归算法。计算机在执行递归程序时，是通过栈结构的调用来实现的，因此答案为D。 3.【答案】A [解析]所谓算法的时间复杂度，是指执行算法所需要的计算:工作量。为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程叶，所需基本运算的执行次数米度量.算法的工作量。故选:A。 4.【答案】D [解析]算法复杂度分为时间复杂度和空间复杂度,其中时间复杂度反映了算法执行所需要的时间,而空间复杂度反映了算法执行所需要占用的存储空间。 5.【答案】C [解析]本题主要考查的是时间复杂度的计算。观察程序,可计算出t=log2n，因此其时间复杂度〇(log2n),答案为C。 6.【答案】A [解析]本程序只包含顺序结构，时间复杂度为〇(1),因此,答案为A。 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. 8.【答案】A [解析]本题主要考查的是时间复杂度的计算。本题中的程序控制结构只包含顺序结构，可知时间复杂度为〇(1),因此,答案为A。 9.【答案】C [解析]本题考查时间复杂度的计算。题中的程序为二重循环,语句的执行次数为一㎡,与量级㎡ 相同,因此其时间复杂度为〇(n2)。 10.【答案】C [解析]本题使用二重循环求s的值,因此时间复杂度为〇(n),答案为C。 11.【答案】A [解析]将图中的图结构可以转换为下图的数结构，依次计算每一种情况。其中路径H-A-C-B-H、H-B-C-A-H用时最短，其时长为2+6+4+5=17故选:A。 12.【答案】D [解析]本题程序使用的是二重循环,外循环共执行n一1次,内循环共执行n次,因此,时间复杂度为 〇(n),答案为 D。 【链接高考】 1.【答案】B [解析]已知s=0，i= 1，判断I<100成立，执行8=s+i=l,i=I*2=2;已知s=1，i= 2，判断I<100成立，执行8=s+i=3，i=I*2=4;由此可知I的值分别为1，2，4，8...;所以s的值也就是I的相加，得到s的值为127，I的值为64*2=128;所以选项B说错误。故选:B。 2.【答案】B [解析]本流程图是循环结构中嵌套分支结构,进入循环执行a=n Mod10语句,a的值分别为0， 8,9,2,这些数字中只有0、8、2才使a\2=a/2成立,因此第一次循环结束后,a=0+1=1,s=1;第二次循环结束后,a=8+1=9,s=9+1*10=19;第三次循环结束后,a=9,s=9+19* 10=199;第四 次循环结束后,a=2+1=3,s=3+199*10= 1993,因此选项B正确。 3.【答案】B [解析]阅读流程图可知，输出ans的结果为1010;条件“a>0?”共判断5次;由于a与b的和可以为偶数或者奇数，所以不能等同;该算法使用的控制结构有顺序和循环结构但没有分支结构。故选:B。 4.【答案】A [解析]本题考查数据结构基础知识。线性表的顺序存储表示需要一片连续的存储空间,而链式存储表示则不需要。当线性表的数据元素在物理存储位置上呈任意分布状态时,存储表示只能用链式存储结构。在链式存储结构中,数据元素之间的逻辑关系是由附加的指针表示的。链式存储结构是通过链指针来体现数据元素之间的逻辑关系的,而数据元素本身在物理存储位置上不一定连续。当线性表的元素在物理存储位置上呈连续分布状态时,用顺序存储结构存储线性表是方便和有效的。顺序存储结构是利用元素的存储位置来体现数据元素之间的逻辑关系的。顺序存储结构是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。由此可以看出,若线性表的逻辑结构确定后,其存储结构形式的选择在一定程度上与线性表的运算有关,也与存储空间的利用率有关。若线性表的元素总数基本稳定，且很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素,则应采用顺序存储结构。若线性表的元素总数不固定,且经常进行插入和删除操作,则应采用链式存储结构。 5.【答案】C [解析]本题考查二分查找的算法思想。二分算法的时间复杂度为O(logn)。D选项m=(x+y+1)//2,当x十y为偶数时，计算的是后个半，而调用时imax(a,x，m),immax(a,m+1,y)与之区间不对应。 6.【答案】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次。 7.【答案】(1)①L+1②L (2) def scarch_first_2( a,key): L,R=0,len(a)-1 while L<=R: if a[R]>=key; R=R-1 else: break return R+1 (3)①(L+R)//2或(L+R+1)//2②m+1 ③L或R+1 [解析](1)①使用顺序查找法从左往右扫描,当a[L]<key时,查找下一个元素。②函数返回第一个不小于key 的元素下标。(3)①采用二分查找算法查找最优解,m为中间位置左偏或右偏的下标。②如果查找到的元素大于等于key,需要在(m+1,R)范围内继续查找;③若使用二分查找中间位置左偏,函数返回值应为L,若使用二分查找中间位置右偏,函数查找值应为R+1。 8.【答案】(1) 4 (2)5 (3) B [解析]代码实现的功能是统计正整数n的二进制表示中1的个数，利用while循不每次将n整除2。直到商是0为止。23D-10111B，所以有4个"1"；"23”在统计过程中“s+=n%2”会执行5次，所以该算法的时间复杂度为〇(log2n)。 9.【答案】 (1)A (2)程序运行结果不会发生变化,break的作用是一旦找到n的因数,则马上退出循环,能 有效提升质数判断效率。比如n=8982126时,i运行到2的时候就可以判定该数不是质 数,即可结束循环。 [解析]自定义函数zhishu()是利用一重循环枚举x的所有因子,时间复杂度为〇(n),所以该题答案选A。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$