首页 › 题库 › Python编程考级 › 5.1 时间复杂度

Python编程四级 题库

共 35 道题 ,第 1 / 2 页 · 按题型筛选,点「查看答案」核对解析
章节 5.1 时间复杂度 清除
1 单选题 适中 Python编程考级 ·Python编程四级 · 5.1 时间复杂度

下面的程序输出1~100之间能被7整除但不能同时被5整除的所有整数。

k=1

while k<101:

   if k%7==0 and k%5 !=0:

       print(k)

   k += 1

根据下面哪个选项的方法优化后,程序的运行效率最高?( )

A
将k=1改为k=7
B
将k
C
将k += 1改为k += 7
D
将k=1改为k=7,同时将k += 1改为k += 7
答案与解析
正确答案:D

选项A可以少执行6次,选项B可以少执行2次,选项D可以少执行86次。选项C程序不能实现设计的功能。

题目详情
2 单选题 适中 Python编程考级 ·Python编程四级 · 5.1 时间复杂度

对比两个求等差数列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)

A
程序1比程序2高
B
程序2比程序1高
C
一样高
D
不能判断
答案与解析
正确答案:A

理解算法性能、算法效率概念

题目详情
3 单选题 适中 Python编程考级 ·Python编程四级 · 5.1 时间复杂度

下列哪个语句段的时间复杂度最低?( )

A
if n%2==0:
    x=x*2
else:
    x=x+2

B
n=1
while n<=100:
    x=x+2

C
for i in range(100):
    for j in range(10):
        x=x+2


D
for i in range(100):
    for j in range(i):
        x=x+2


答案与解析
正确答案:A

时间复杂度按数量级递增顺序为:常数阶、对数阶、线性阶、线性对数阶、平方阶

题目详情
4 单选题 适中 Python编程考级 ·Python编程四级 · 5.1 时间复杂度

下列关于递归的描述不正确的是?( )

A
递归函数一定包含条件控制语句
B
递归函数一定包含调用自身的语句
C
在调用自身函数时需要明确的边界终止条件
D
递归算法一般代码简洁,执行效率高,空间复杂度低
答案与解析
正确答案:D

递归算法一般代码简洁,易于理解,但执行效率较低,空间复杂度高。

题目详情
5 单选题 适中 Python编程考级 ·Python编程四级 · 5.1 时间复杂度

下列不是评判一个算法优劣的标准是?( )

A
时间复杂度
B
空间复杂度
C
难易度
D
健壮性
答案与解析
正确答案:C

评价算法的优劣是:时间复杂度,空间复杂度,健壮性,正确性,可读性。因此选C。

题目详情
6 单选题 适中 Python编程考级 ·Python编程四级 · 5.1 时间复杂度

关于评价算法的优劣,以下说法正确的是?( )

A
只要考虑是否得出正确答案。
B
只要考虑算法的执行时间。
C
只要考虑算法所占用的空间。
D
从算法执行时间和需占用的空间两方面考虑。
答案与解析
正确答案:D

评价算法的指标主要有时间复杂度和空间复杂度。

题目详情
7 单选题 适中 Python编程考级 ·Python编程四级 · 5.1 时间复杂度

下列排序算法中,时间复杂度最小的是?( )

A
插入排序
B
冒泡排序
C
快速排序
D
选择排序
答案与解析
正确答案:C

快速排序时间复杂度是O(nlogn),其他都是O(n*n)。

题目详情
8 单选题 适中 Python编程考级 ·Python编程四级 · 5.1 时间复杂度

用枚举算法求解“100以内既能被3整除又能被4整除的元素”时,在下列数值范围内,算法执行效率最高的是?( )

A
1~101
B
4~100
C
12~100
D
12~96
答案与解析
正确答案:D

题目详情
9 单选题 适中 Python编程考级 ·Python编程四级 · 5.1 时间复杂度

关于求解“找出所有满足各位数字之和等于8的三位数”时,在下列数值范围内,算法执行效率最高的是?( )

A

0—999

B

0—1000

C

100—800

D

107—800

答案与解析
正确答案:D

枚举的范围应尽可能小但又不遗漏.

题目详情
10 单选题 适中 Python编程考级 ·Python编程四级 · 5.1 时间复杂度

下列关于递归的描述不正确的是?( )

A
递归函数一定包含 if 语句
B
递归函数体内一定包含调用自身的语句
C
在调用自身函数时需要明确的边界终止条件与边界值
D
递归算法一般代码简洁,执行效率高,空间复杂度低
答案与解析
正确答案:D

递归算法一般代码简洁,易于理解,但执行效率较低,空间复杂度高。

题目详情
11 单选题 适中 Python编程考级 ·Python编程四级 · 5.1 时间复杂度

解决下列问题时,时间复杂度最大的是?( )

A
输入 n 个不同的包含两位小数的实数,计算这 n 个数的和
B
在 n 个数据中,查找数据 k
C
将 n 个数据用冒泡排序实现排序
D
计算算式 1-2+3-4+...-n 的结果,n 为偶数
答案与解析
正确答案:C

算法优化。

题目详情
12 单选题 适中 Python编程考级 ·Python编程四级 · 5.1 时间复杂度

用枚举算法求解“各位数之和等于8的所有三位数”时,下列枚举范围中效率最高的是?( )

A
0-999
B
100-999
C
100-800
D
107-800
答案与解析
正确答案:D

枚举的范围尽可能小但不能遗漏。

题目详情
13 单选题 适中 Python编程考级 ·Python编程四级 · 5.1 时间复杂度

陈明同学利用Python语言编写了一段“根据出生年月判断生肖属相”的程序,调试运行时,程序没有报错且顺利运行,但未能正确输出对应属相,造成这个结果的原因可能是?( )

A
程序语句语法错误
B
程序复杂度高,算法效率低
C
Python的环境配置不对
D
求解算法的逻辑错误
答案与解析
正确答案:D

如果语句语法错误,程序运行会报错;输出结果是否正确,取决于算法逻辑是否正确,跟程序复杂度和算法效率没有关联。

题目详情
14 单选题 适中 Python编程考级 ·Python编程四级 · 5.1 时间复杂度
以下代码的时间复杂度是多少?
i = 1
n = 100
while i < n:
    i = i * 2
A
O(n)
B
O(log2N)
C
O(n*n)
D
O(n2)
答案与解析
正确答案:B

量级为对数阶,2^x=n,所以时间复杂度为O(log2N)。

题目详情
15 单选题 适中 Python编程考级 ·Python编程四级 · 5.1 时间复杂度
以下关于列表p内元素排序程序的时间复杂度为?
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
A
O(n)
B
O(nlogn)
C
O(n^2)
D
O(n^3)
答案与解析
正确答案:C

内循环的作用是比较相邻两个数的值,如果前数小于后数,就交换两个数。所以双重循环的时间复杂度是O(n^2)。

题目详情
16 单选题 适中 Python编程考级 ·Python编程四级 · 5.1 时间复杂度
下面关于递归函数的说法,正确的是?
A
一般来说,递归函数的执行效率高于非递归函数
B
递归算法一般代码简洁,执行效率高,空间复杂度低
C
递归函数必须明确嵌套调用的次数
D
递归函数必须有明确的边界终止条件
答案与解析
正确答案:D

递归算法的优点是代码简洁,容易验证正确性。缺点是运行需要较多次数的函数调用,如果调用层数比较深,需要增加额外的堆栈处理,空间复杂度较高,会对执行效率有影响。同时递归函数的调用不需要明确次数,但是要有明确的边界条件。

题目详情
17 单选题 适中 Python编程考级 ·Python编程四级 · 5.1 时间复杂度

以下Python代码的时间复杂度是?( )

for i in range( 1 ,10 ):  #外循环
    for j in range( i, 10  ):   #内循环
        print('%d*%d=%2d '%( i , j, i*j ), end='  ')  
    print()
A
O(1)
B
O(2)
C
O(n)
D
O(n2)
答案与解析
正确答案:D


题目详情
18 单选题 适中 Python编程考级 ·Python编程四级 · 5.1 时间复杂度

小明正在用枚举算法解决一个问题:找出所有满足各位数字之积等于12的三位数。为了提高程序运行效率,他需要选择一个合适的数值范围进行枚举。在以下选项中,哪种数值范围能让算法的执行效率最高?( )

A
0~999
B
100~900
C
126~621
D
126~431
答案与解析
正确答案:C

枚举的范围应尽可能小但又不遗漏。

题目详情
19 单选题 适中 Python编程考级 ·Python编程四级 · 5.1 时间复杂度

下列哪种情况的程序,时间复杂度最低?( )

A
一个for循环,循环 100 次
B
两个嵌套的for循环,每个循环 100 次
C
执行一次print语句
D
用while循环找列表里的某个元素
答案与解析
正确答案:C

执行一次print语句,操作次数固定,时间复杂度是 O (1) ;一个for循环循环 100 次是 O (n) ;两个嵌套for循环是 O (n2) ;用while循环找列表元素,最坏情况要遍历整个列表,也是 O (n) ,O (1) 是最低的时间复杂度。

题目详情
20 单选题 适中 Python编程考级 ·Python编程四级 · 5.1 时间复杂度

解决下列问题时,时间复杂度最大的是?( )

A
打印输出100个已知的整数
B
在100个数据中,查找数据25
C
将100个数据用冒泡排序实现排序
D
计算算式1-2+3-4+...-100的结果
答案与解析
正确答案:C

逐个分析时间复杂度

设数据规模 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。

题目详情