资源简介

数据结构与算法效率
一 、选择题(每小题列出的四个备选项中只有一个是符合题目要求
的，不选、多选、错选均不得分)
1.某算法的时间复杂度为O(n ),表明该算法的
A.问题规模是n
B.执行时间等于n
C.问题规模与n 成正比
D.执行次数与n 呈线性增大关系
2. 某Python 程序如下：
i=1
k=0
n=int(input())
while i<=n:
k+=2*i
i+=1
该算法的时间复杂度是
A.O(1)
B.O(n)
C.O(n )
D.0(log n)
3. 某 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.O( 1)
B.O(n)
C.O(n )
D.O(2")
4.某算法的部分流程图如图所示。
(
开始
输入
a
a<5
Y
a>10
b~-a%2
输出
b
结束
b--abs(a)
b*-a/2
N
N
Y
)
该算法的时间复杂度是
A.常量阶
B.线性阶
C.指数阶
D.对数阶
5. 某 Python 程序如下：
def f(n):
if n<=2:
return n
else:
return f(n- 1)*n
x=int(input("x=")
print(f(x))
该算法的时间复杂度是
A.O(n)
B.O(n )
C.O(n!)
D.O(nlog n)
6. 对于线性表，适合采用数组存储数据的情况是
A. 经常需要随机地访问查询数据元素
B.经常需要进行插人和删除操作
C.表中数据元素经常需要移动位置
D.表中数据元素的个数经常变动
( )
( )
( )
二、非选择题
7.某算法的Python代码如下：
def BSearch(key,a):
L=0
R=len(a)-1
while L<=R:
m=(L+R)//2
if a[m]=key:
return m #找到key值则返回m
if a[m]L=m+1
else:
R=m- 1
return None #未找到则返回None
已知列表a的元素已实现升序排序，则函数BSearch()的算法时间复
杂度为 。
8. 某Python程序如下：
def ct(n):
s=0
while n>0:
s+=n%2
n//=2
return s
n=int(input("输入一个正整数：")
ans=ct(n)
print(ans)
请回答下列问题：
程序运行后，输入整数23,自定义函数ct(n)中语句“s+=n%2”执 行的次数是
(2)该算法的时间复杂度为 (单选，填字母：A.O(n)/B.O(log n))。
迭代与递归
选择题(每小题列出的四个备选项中只有一个是符合题目要求的，不
选、多选、错选均不得分)
1.某Python程序如下：
n=int(input())
s=x=0
while n!=0：
x=n%10
s=x+s
n=n//10
print(s)
程序运行后，输入n 的值为20220412,输出的结果是 ( )
A.13 B.1119 C.2022 D.9
2. 下列Python程序的功能是求斐波那契数列的第n 项的值：
n=int(input())
t1=t2=1
for i in range(3,n+1):
print("斐波那契数列第"+str(n)+"项的值为："+str(t)
方框中的代码由以下三部分组成：①tl=t2 ②t2=t ③t=t1+t2
下列选项中代码顺序正确的是 ( )
A.①②③
B.①③②
C.③②①
D.③①②
3. 利用迭代算法求圆周率π值的方法是：计算公式π/4=1-1/3+1/5-
1/7+…,直到最后一项的绝对值小于10- 为止。 Python程序如下：
pi=0
fm=1
k=1
while abs(1/fm*k)>=0.0000001:
pi=pi*4
print(round(pi,6)
方框中的代码由以下三部分组成：
① fm=fm+2 ②k=-k ③pi=pi+1/fm*k 下列选项中代码顺序正确的是
A.①②③
B.③②①
C.②①③
D.②③①
4.某Python程序如下：
def add(n):
if n==1 or n==2:
s=1
else:
s=2*(add(n- 1)+add(n-2))
return s
m=5
sum=0
for i in range(1,m+1):
sum+=add(i)
print(str(sum))
程序运行后，输出的结果是
A.44
C.16
5.某 Python程序如下：
def convert(n,base):
s="0123456789ABCDEF"
if nreturn s[n]
else:
( )
B.32
D.6
return convert(n//base,base)+s[n%base]
x=int(input())
y=int(input())
print(convert(x,y))
程序运行后，输入x的值为164,y 的值为16,输出的结果是( )
A.104 B.401 C.4A D.A4
6. 编写一个简短的递归Python 函数，它接受一个字符串s 并且输出其
逆置字符串。例如字符串“dog”的逆置字符串为“god”。程序代码
如下：
s=input("请输入字符串：")
def reverse(s):
if len(s)<=1:
return s
return
print("逆置字符串为：",reverse(s))
划线处应填入的代码应是 ( )
A.s[- 1]+reverse(s[1:])
B.reverse(s[1:])+s[- 1]
C.s[- 1]+reverse(s[:- 1])
D.reverse(s[:- 1])+s[- 1]
7.有如下两个Python自定义函数：
def gcd1(a,b):
if a%b==0:
ans=b
else:
ans=gcd1(b,a%b)
return ans
def gcd2(a,b):
r=a%b
while r!=0:
a=b
b=r
r=a%b
return b
下列说法不正确的是
A.函数gcd1采用了递归算法
B.函数gcd2采用了迭代算法
C.gcd1(18,gcd2(9,30))返回的结果是9
D.gcd1(6,15)和gcd2(9,24)返回的结果是相等的
数据结构与数据算法 参考答案
1.D 2.B 3.C 4.A 5.A 6.A
O(log2n)
(1)5 (2)B
迭代与递归 参考答案
1.A 2.D 3.B 4.A 5.D 6.C 7.C

展开更多......

收起↑