Python编程四级 题库
下面的程序输出1~100之间能被7整除但不能同时被5整除的所有整数。
k=1
while k<101:
if k%7==0 and k%5 !=0:
print(k)
k += 1
根据下面哪个选项的方法优化后,程序的运行效率最高?( )
选项A可以少执行6次,选项B可以少执行2次,选项D可以少执行86次。选项C程序不能实现设计的功能。
对比两个求等差数列1+2+…+n的和的程序,其算法效率?( )
程序1:
n=int(input())
s=(1+n)*n/2
print(s)
程序2:
n=int(input())
s=0
for i in range(n+1):
s=s+i
print(s)
理解算法性能、算法效率概念
下列关于递归的描述不正确的是?( )
递归算法一般代码简洁,易于理解,但执行效率较低,空间复杂度高。
下列不是评判一个算法优劣的标准是?( )
评价算法的优劣是:时间复杂度,空间复杂度,健壮性,正确性,可读性。因此选C。
关于评价算法的优劣,以下说法正确的是?( )
评价算法的指标主要有时间复杂度和空间复杂度。
下列排序算法中,时间复杂度最小的是?( )
快速排序时间复杂度是O(nlogn),其他都是O(n*n)。
用枚举算法求解“100以内既能被3整除又能被4整除的元素”时,在下列数值范围内,算法执行效率最高的是?( )
关于求解“找出所有满足各位数字之和等于8的三位数”时,在下列数值范围内,算法执行效率最高的是?( )
0—999
0—1000
100—800
107—800
枚举的范围应尽可能小但又不遗漏.
下列关于递归的描述不正确的是?( )
递归算法一般代码简洁,易于理解,但执行效率较低,空间复杂度高。
解决下列问题时,时间复杂度最大的是?( )
算法优化。
用枚举算法求解“各位数之和等于8的所有三位数”时,下列枚举范围中效率最高的是?( )
枚举的范围尽可能小但不能遗漏。
陈明同学利用Python语言编写了一段“根据出生年月判断生肖属相”的程序,调试运行时,程序没有报错且顺利运行,但未能正确输出对应属相,造成这个结果的原因可能是?( )
如果语句语法错误,程序运行会报错;输出结果是否正确,取决于算法逻辑是否正确,跟程序复杂度和算法效率没有关联。
i = 1 n = 100 while i < n: i = i * 2
量级为对数阶,2^x=n,所以时间复杂度为O(log2N)。
for a in range(n-1): for b in range(n-1-i): if(p[b]<p[b+1]): tmp=p[b] p[b]=p[b+1] p[b+1]=tmp
内循环的作用是比较相邻两个数的值,如果前数小于后数,就交换两个数。所以双重循环的时间复杂度是O(n^2)。
递归算法的优点是代码简洁,容易验证正确性。缺点是运行需要较多次数的函数调用,如果调用层数比较深,需要增加额外的堆栈处理,空间复杂度较高,会对执行效率有影响。同时递归函数的调用不需要明确次数,但是要有明确的边界条件。
以下Python代码的时间复杂度是?( )
for i in range( 1 ,10 ): #外循环
for j in range( i, 10 ): #内循环
print('%d*%d=%2d '%( i , j, i*j ), end=' ')
print()小明正在用枚举算法解决一个问题:找出所有满足各位数字之积等于12的三位数。为了提高程序运行效率,他需要选择一个合适的数值范围进行枚举。在以下选项中,哪种数值范围能让算法的执行效率最高?( )
枚举的范围应尽可能小但又不遗漏。
下列哪种情况的程序,时间复杂度最低?( )
执行一次print语句,操作次数固定,时间复杂度是 O (1) ;一个for循环循环 100 次是 O (n) ;两个嵌套for循环是 O (n2) ;用while循环找列表元素,最坏情况要遍历整个列表,也是 O (n) ,O (1) 是最低的时间复杂度。
解决下列问题时,时间复杂度最大的是?( )
逐个分析时间复杂度
设数据规模 n=100
A 打印 100 个已知整数
循环遍历 100 个数依次输出,执行次数固定为 n,时间复杂度 O(n)。
B 在 100 个数据里查找 25
最坏情况需要遍历全部 100 个元素,最多执行 n 次,时间复杂度 O(n)。
C 冒泡排序对 100 个数据排序
冒泡排序最坏情况下需要外层 n 轮、内层每轮依次少 1 次比较,属于平方级,时间复杂度 O(n2)。
D 计算 1−2+3−4+⋯−100
可以直接用数学公式一步算出结果,无需循环遍历 100 次也能求解;即便循环累加也只是 n 次运算,时间复杂度 O(n)。
结论
O(n2)>O(n),时间复杂度最大的是 C。